Home | History | Annotate | Line # | Download | only in dist 
      1 /*
      2  * bitset.h -- Dynamic bitset.
      3  *
      4  * Copyright (c) 2001-2020, NLnet Labs. All rights reserved.
      5  *
      6  * See LICENSE for the license.
      7  *
      8  */
      9 #include "config.h"
     10 #include "bitset.h"
     11 
     12 #include <assert.h>
     13 #include <limits.h>
     14 #include <string.h>
     15 
     16 size_t nsd_bitset_size(size_t bits)
     17 {
     18 	if(bits == 0)
     19 		bits++;
     20 
     21 	return (bits / CHAR_BIT) + ((bits % CHAR_BIT) != 0) + sizeof(size_t);
     22 }
     23 
     24 void nsd_bitset_zero(struct nsd_bitset *bset)
     25 {
     26 	size_t sz;
     27 
     28 	assert(bset != NULL);
     29 
     30 	sz = nsd_bitset_size(bset->size) - sizeof(bset->size);
     31 	assert(sz > 0);
     32 	memset(bset->bits, 0, sz);
     33 }
     34 
     35 void nsd_bitset_init(struct nsd_bitset *bset, size_t bits)
     36 {
     37 	assert(bset != NULL);
     38 	if (bits == 0)
     39 		bits++;
     40 
     41 	bset->size = bits;
     42 	nsd_bitset_zero(bset);
     43 }
     44 
     45 int nsd_bitset_isset(struct nsd_bitset *bset, size_t bit)
     46 {
     47 	assert(bset != NULL);
     48 	if(bit >= bset->size)
     49 		return 0;
     50 
     51 	return (bset->bits[ (bit / CHAR_BIT) ] & (1 << (bit % CHAR_BIT))) != 0;
     52 }
     53 
     54 void nsd_bitset_set(struct nsd_bitset *bset, size_t bit)
     55 {
     56 	assert(bset != NULL);
     57 	assert(bset->size > bit);
     58 	bset->bits[ (bit / CHAR_BIT) ] |= (1 << (bit % CHAR_BIT));
     59 }
     60 
     61 void nsd_bitset_unset(struct nsd_bitset *bset, size_t bit)
     62 {
     63 	assert(bset != NULL);
     64 	assert(bset->size > bit);
     65 	bset->bits[ (bit / CHAR_BIT) ] &= ~(1 << (bit % CHAR_BIT));
     66 }
     67 
     68 void nsd_bitset_or(
     69 	struct nsd_bitset *destset,
     70 	struct nsd_bitset *srcset1,
     71 	struct nsd_bitset *srcset2)
     72 {
     73 	size_t i, n, size, bytes;
     74 	unsigned char bits;
     75 	unsigned int mask;
     76 
     77 	assert(destset != NULL);
     78 	assert(srcset1 != NULL);
     79 	assert(srcset2 != NULL);
     80 
     81 	size = destset->size;
     82 	bytes = (size / CHAR_BIT) + ((size % CHAR_BIT) != 0);
     83 
     84 	for(i = 0; i < bytes; i++) {
     85 		bits = 0;
     86 
     87 		n = (srcset1->size / CHAR_BIT);
     88 		if (n > i) {
     89 			bits |= srcset1->bits[i];
     90 		} else {
     91 			n += ((srcset1->size % CHAR_BIT) != 0);
     92 			mask = (1 << ((srcset1->size % CHAR_BIT) + 1)) - 1;
     93 			if (n > i) {
     94 				bits |= (srcset1->bits[i] & mask);
     95 			}
     96 		}
     97 		n = (srcset2->size / CHAR_BIT);
     98 		if (n > i) {
     99 			bits |= srcset2->bits[i];
    100 		} else {
    101 			n += ((srcset2->size % CHAR_BIT) != 0);
    102 			mask = (1 << ((srcset2->size % CHAR_BIT) + 1)) - 1;
    103 			if (n > i) {
    104 				bits |= (srcset2->bits[i] & mask);
    105 			}
    106 		}
    107 		destset->bits[i] = bits;
    108 	}
    109 }
    110