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 
bitfield_alloc(size_t max_bits)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 
bitfield_free(struct bitfield * bf)34 void bitfield_free(struct bitfield *bf)
35 {
36           os_free(bf);
37 }
38 
39 
bitfield_set(struct bitfield * bf,size_t bit)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 
bitfield_clear(struct bitfield * bf,size_t bit)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 
bitfield_is_set(struct bitfield * bf,size_t bit)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 
first_zero(u8 val)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 
bitfield_get_first_zero(struct bitfield * bf)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 }
90