Branch data     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                 :         46 : struct bitfield * bitfield_alloc(size_t max_bits)
      22                 :            : {
      23                 :            :         struct bitfield *bf;
      24                 :            : 
      25                 :         46 :         bf = os_zalloc(sizeof(*bf) + (max_bits + 7) / 8);
      26         [ -  + ]:         46 :         if (bf == NULL)
      27                 :          0 :                 return NULL;
      28                 :         46 :         bf->bits = (u8 *) (bf + 1);
      29                 :         46 :         bf->max_bits = max_bits;
      30                 :         46 :         return bf;
      31                 :            : }
      32                 :            : 
      33                 :            : 
      34                 :         84 : void bitfield_free(struct bitfield *bf)
      35                 :            : {
      36                 :         84 :         os_free(bf);
      37                 :         84 : }
      38                 :            : 
      39                 :            : 
      40                 :         52 : void bitfield_set(struct bitfield *bf, size_t bit)
      41                 :            : {
      42         [ -  + ]:         52 :         if (bit >= bf->max_bits)
      43                 :         52 :                 return;
      44                 :         52 :         bf->bits[bit / 8] |= BIT(bit % 8);
      45                 :            : }
      46                 :            : 
      47                 :            : 
      48                 :         52 : void bitfield_clear(struct bitfield *bf, size_t bit)
      49                 :            : {
      50         [ -  + ]:         52 :         if (bit >= bf->max_bits)
      51                 :         52 :                 return;
      52                 :         52 :         bf->bits[bit / 8] &= ~BIT(bit % 8);
      53                 :            : }
      54                 :            : 
      55                 :            : 
      56                 :          0 : int bitfield_is_set(struct bitfield *bf, size_t bit)
      57                 :            : {
      58         [ #  # ]:          0 :         if (bit >= bf->max_bits)
      59                 :          0 :                 return 0;
      60                 :          0 :         return !!(bf->bits[bit / 8] & BIT(bit % 8));
      61                 :            : }
      62                 :            : 
      63                 :            : 
      64                 :         52 : static int first_zero(u8 val)
      65                 :            : {
      66                 :            :         int i;
      67         [ +  - ]:         62 :         for (i = 0; i < 8; i++) {
      68         [ +  + ]:         62 :                 if (!(val & 0x01))
      69                 :         52 :                         return i;
      70                 :         10 :                 val >>= 1;
      71                 :            :         }
      72                 :         52 :         return -1;
      73                 :            : }
      74                 :            : 
      75                 :            : 
      76                 :         52 : int bitfield_get_first_zero(struct bitfield *bf)
      77                 :            : {
      78                 :            :         size_t i;
      79         [ +  - ]:         52 :         for (i = 0; i <= (bf->max_bits + 7) / 8; i++) {
      80         [ +  - ]:         52 :                 if (bf->bits[i] != 0xff)
      81                 :         52 :                         break;
      82                 :            :         }
      83         [ -  + ]:         52 :         if (i > (bf->max_bits + 7) / 8)
      84                 :          0 :                 return -1;
      85                 :         52 :         i = i * 8 + first_zero(bf->bits[i]);
      86         [ -  + ]:         52 :         if (i >= bf->max_bits)
      87                 :          0 :                 return -1;
      88                 :         52 :         return i;
      89                 :            : }