src/utils/bitfield.c

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