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          95 : struct bitfield * bitfield_alloc(size_t max_bits)
      22             : {
      23             :         struct bitfield *bf;
      24             : 
      25          95 :         bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8);
      26          95 :         if (bf == NULL)
      27           0 :                 return NULL;
      28          95 :         bf->bits = (u8 *) (bf + 1);
      29          95 :         bf->max_bits = max_bits;
      30          95 :         return bf;
      31             : }
      32             : 
      33             : 
      34         243 : void bitfield_free(struct bitfield *bf)
      35             : {
      36         243 :         os_free(bf);
      37         243 : }
      38             : 
      39             : 
      40         654 : void bitfield_set(struct bitfield *bf, size_t bit)
      41             : {
      42         654 :         if (bit >= bf->max_bits)
      43         731 :                 return;
      44         577 :         bf->bits[bit / 8] |= BIT(bit % 8);
      45             : }
      46             : 
      47             : 
      48         531 : void bitfield_clear(struct bitfield *bf, size_t bit)
      49             : {
      50         531 :         if (bit >= bf->max_bits)
      51         608 :                 return;
      52         454 :         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         333 : static int first_zero(u8 val)
      65             : {
      66             :         int i;
      67        1189 :         for (i = 0; i < 8; i++) {
      68        1189 :                 if (!(val & 0x01))
      69         333 :                         return i;
      70         856 :                 val >>= 1;
      71             :         }
      72           0 :         return -1;
      73             : }
      74             : 
      75             : 
      76         333 : int bitfield_get_first_zero(struct bitfield *bf)
      77             : {
      78             :         size_t i;
      79        2133 :         for (i = 0; i <= (bf->max_bits + 7) / 8; i++) {
      80        2133 :                 if (bf->bits[i] != 0xff)
      81         333 :                         break;
      82             :         }
      83         333 :         if (i > (bf->max_bits + 7) / 8)
      84           0 :                 return -1;
      85         333 :         i = i * 8 + first_zero(bf->bits[i]);
      86         333 :         if (i >= bf->max_bits)
      87           2 :                 return -1;
      88         331 :         return i;
      89             : }