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
nsd_bitset_size(size_t bits)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
nsd_bitset_zero(struct nsd_bitset * bset)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
nsd_bitset_init(struct nsd_bitset * bset,size_t bits)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
nsd_bitset_isset(struct nsd_bitset * bset,size_t bit)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
nsd_bitset_set(struct nsd_bitset * bset,size_t bit)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
nsd_bitset_unset(struct nsd_bitset * bset,size_t bit)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
nsd_bitset_or(struct nsd_bitset * destset,struct nsd_bitset * srcset1,struct nsd_bitset * srcset2)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