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