Line data    Source code

       1             : /*
       2             :  * Bitfield
       3             :  * Copyright (c) 2013, Jouni Malinen <j@w1.fi>
       4             :  *
       5             :  * This software may be distributed under the terms of the BSD license.
       6             :  * See README for more details.
       7             :  */
       8             : 
       9             : #include "includes.h"
      10             : 
      11             : #include "common.h"
      12             : #include "bitfield.h"
      13             : 
      14             : 
      15             : struct bitfield {
      16             :         u8 *bits;
      17             :         size_t max_bits;
      18             : };
      19             : 
      20             : 
      21          79 : struct bitfield * bitfield_alloc(size_t max_bits)
      22             : {
      23             :         struct bitfield *bf;
      24             : 
      25          79 :         bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8);
      26          79 :         if (bf == NULL)
      27           0 :                 return NULL;
      28          79 :         bf->bits = (u8 *) (bf + 1);
      29          79 :         bf->max_bits = max_bits;
      30          79 :         return bf;
      31             : }
      32             : 
      33             : 
      34         128 : void bitfield_free(struct bitfield *bf)
      35             : {
      36         128 :         os_free(bf);
      37         128 : }
      38             : 
      39             : 
      40         644 : void bitfield_set(struct bitfield *bf, size_t bit)
      41             : {
      42         644 :         if (bit >= bf->max_bits)
      43         721 :                 return;
      44         567 :         bf->bits[bit / 8] |= BIT(bit % 8);
      45             : }
      46             : 
      47             : 
      48         521 : void bitfield_clear(struct bitfield *bf, size_t bit)
      49             : {
      50         521 :         if (bit >= bf->max_bits)
      51         598 :                 return;
      52         444 :         bf->bits[bit / 8] &= ~BIT(bit % 8);
      53             : }
      54             : 
      55             : 
      56        1737 : int bitfield_is_set(struct bitfield *bf, size_t bit)
      57             : {
      58        1737 :         if (bit >= bf->max_bits)
      59         386 :                 return 0;
      60        1351 :         return !!(bf->bits[bit / 8] & BIT(bit % 8));
      61             : }
      62             : 
      63             : 
      64         323 : static int first_zero(u8 val)
      65             : {
      66             :         int i;
      67        1182 :         for (i = 0; i < 8; i++) {
      68        1182 :                 if (!(val & 0x01))
      69         323 :                         return i;
      70         859 :                 val >>= 1;
      71             :         }
      72           0 :         return -1;
      73             : }
      74             : 
      75             : 
      76         323 : int bitfield_get_first_zero(struct bitfield *bf)
      77             : {
      78             :         size_t i;
      79        2123 :         for (i = 0; i <= (bf->max_bits + 7) / 8; i++) {
      80        2123 :                 if (bf->bits[i] != 0xff)
      81         323 :                         break;
      82             :         }
      83         323 :         if (i > (bf->max_bits + 7) / 8)
      84           0 :                 return -1;
      85         323 :         i = i * 8 + first_zero(bf->bits[i]);
      86         323 :         if (i >= bf->max_bits)
      87           2 :                 return -1;
      88         321 :         return i;
      89             : }