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