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 16size_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 24void 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 35void 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 45int 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 54void 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 61void 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 68void 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