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