Home | History | Annotate | Download | only in utils
      1 /*
      2  * Bitfield
      3  * Copyright (c) 2013, Jouni Malinen <j (at) 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 }
     90