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)21struct 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)34void bitfield_free(struct bitfield *bf) 35 { 36 os_free(bf); 37 } 38 39 bitfield_set(struct bitfield * bf,size_t bit)40void 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)48void 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)56int 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)64static 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)76int 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