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         113 : struct bitfield * bitfield_alloc(size_t max_bits)
      22             : {
      23             :         struct bitfield *bf;
      24             : 
      25         113 :         bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8);
      26         113 :         if (bf == NULL)
      27           1 :                 return NULL;
      28         112 :         bf->bits = (u8 *) (bf + 1);
      29         112 :         bf->max_bits = max_bits;
      30         112 :         return bf;
      31             : }
      32             : 
      33             : 
      34         349 : void bitfield_free(struct bitfield *bf)
      35             : {
      36         349 :         os_free(bf);
      37         349 : }
      38             : 
      39             : 
      40         672 : void bitfield_set(struct bitfield *bf, size_t bit)
      41             : {
      42         672 :         if (bit >= bf->max_bits)
      43         749 :                 return;
      44         595 :         bf->bits[bit / 8] |= BIT(bit % 8);
      45             : }
      46             : 
      47             : 
      48         541 : void bitfield_clear(struct bitfield *bf, size_t bit)
      49             : {
      50         541 :         if (bit >= bf->max_bits)
      51         618 :                 return;
      52         464 :         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         344 : static int first_zero(u8 val)
      65             : {
      66             :         int i;
      67        1206 :         for (i = 0; i < 8; i++) {
      68        1206 :                 if (!(val & 0x01))
      69         344 :                         return i;
      70         862 :                 val >>= 1;
      71             :         }
      72           0 :         return -1;
      73             : }
      74             : 
      75             : 
      76         345 : int bitfield_get_first_zero(struct bitfield *bf)
      77             : {
      78             :         size_t i;
      79        2146 :         for (i = 0; i < (bf->max_bits + 7) / 8; i++) {
      80        2145 :                 if (bf->bits[i] != 0xff)
      81         344 :                         break;
      82             :         }
      83         345 :         if (i == (bf->max_bits + 7) / 8)
      84           1 :                 return -1;
      85         344 :         i = i * 8 + first_zero(bf->bits[i]);
      86         344 :         if (i >= bf->max_bits)
      87           2 :                 return -1;
      88         342 :         return i;
      89             : }