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