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 15struct bitfield { 16 u8 *bits; 17 size_t max_bits; 18}; 19 20 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 34void bitfield_free(struct bitfield *bf) 35{ 36 os_free(bf); 37} 38 39 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 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 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 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 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