Lely core libraries 2.3.4
bitset.c
Go to the documentation of this file.
1
24#include "util.h"
25
26#if !LELY_NO_MALLOC
27
28#include <lely/libc/strings.h>
29#include <lely/util/bitset.h>
30#include <lely/util/errnum.h>
31
32#include <assert.h>
33#include <stdlib.h>
34
35#undef INT_BIT
36#define INT_BIT (sizeof(int) * CHAR_BIT)
37
38int
39bitset_init(struct bitset *set, int size)
40{
41 assert(set);
42
43 size = MAX(0, (size + INT_BIT - 1) / INT_BIT);
44
45 unsigned int *bits = malloc(size * sizeof(unsigned int));
46 if (!bits && size) {
47#if !LELY_NO_ERRNO
48 set_errc(errno2c(errno));
49#endif
50 return -1;
51 }
52
53 set->size = size;
54 set->bits = bits;
55
56 return 0;
57}
58
59void
60bitset_fini(struct bitset *set)
61{
62 assert(set);
63
64 set->size = 0;
65 free(set->bits);
66 set->bits = NULL;
67}
68
69int
70bitset_size(const struct bitset *set)
71{
72 return set->size * INT_BIT;
73}
74
75int
76bitset_resize(struct bitset *set, int size)
77{
78 assert(set);
79 assert(set->size >= 0);
80
81 size = MAX(0, (size + INT_BIT - 1) / INT_BIT);
82
83 unsigned int *bits = realloc(set->bits, size * sizeof(unsigned int));
84 if (!bits && size) {
85#if !LELY_NO_ERRNO
86 set_errc(errno2c(errno));
87#endif
88 return 0;
89 }
90
91 // If the size increased, clear the new bits.
92 for (int i = set->size; i < size; i++)
93 bits[i] = 0;
94
95 set->size = size;
96 set->bits = bits;
97
98 return bitset_size(set);
99}
100
101int
102bitset_test(const struct bitset *set, int n)
103{
104 if (n < 0 || n >= bitset_size(set))
105 return 0;
106 return (set->bits[n / INT_BIT] >> (n & (INT_BIT - 1))) & 1u;
107}
108
109void
110bitset_set(struct bitset *set, int n)
111{
112 if (n < 0 || n >= bitset_size(set))
113 return;
114 set->bits[n / INT_BIT] |= 1u << (n & (INT_BIT - 1));
115}
116
117void
119{
120 for (int i = 0; i < set->size; i++)
121 set->bits[i] = ~0u;
122}
123
124void
125bitset_clr(struct bitset *set, int n)
126{
127 if (n < 0 || n >= bitset_size(set))
128 return;
129 set->bits[n / INT_BIT] &= ~(1u << (n & (INT_BIT - 1)));
130}
131
132void
134{
135 for (int i = 0; i < set->size; i++)
136 set->bits[i] = 0;
137}
138
139void
141{
142 for (int i = 0; i < set->size; i++)
143 set->bits[i] = ~set->bits[i];
144}
145
146int
147bitset_ffs(const struct bitset *set)
148{
149 const unsigned int *bits = set->bits;
150 int offset = 0;
151 for (int i = 0; i < set->size; i++) {
152 unsigned int x = *bits++;
153 if (x)
154 return offset + ffs(x);
155 offset += INT_BIT;
156 }
157 return 0;
158}
159
160int
161bitset_ffz(const struct bitset *set)
162{
163 const unsigned int *bits = set->bits;
164 int offset = 0;
165 for (int i = 0; i < set->size; i++) {
166 unsigned int x = *bits++;
167 if (~x)
168 return offset + ffs(~x);
169 offset += INT_BIT;
170 }
171 return 0;
172}
173
174int
175bitset_fns(const struct bitset *set, int n)
176{
177 if (n < 0)
178 n = 0;
179 if (n >= bitset_size(set))
180 return 0;
181
182 int size = set->size - n / INT_BIT;
183 const unsigned int *bits = set->bits + n / INT_BIT;
184 int offset = n & ~(INT_BIT - 1);
185 n -= offset;
186 while (size) {
187 unsigned int x = *bits++;
188 if (n) {
189 // Clear the bits smaller than n.
190 x &= ~0u << n;
191 n = 0;
192 }
193 if (x)
194 return offset + ffs(x);
195 size--;
196 offset += INT_BIT;
197 }
198 return 0;
199}
200
201int
202bitset_fnz(const struct bitset *set, int n)
203{
204 if (n < 0)
205 n = 0;
206 if (n >= bitset_size(set))
207 return 0;
208
209 int size = set->size - n / INT_BIT;
210 const unsigned int *bits = set->bits + n / INT_BIT;
211 int offset = n & ~(INT_BIT - 1);
212 n -= offset;
213 while (size) {
214 unsigned int x = *bits++;
215 if (n) {
216 // Set the bits smaller than n.
217 x |= ~0u >> (INT_BIT - n);
218 n = 0;
219 }
220 if (~x)
221 return offset + ffs(~x);
222 size--;
223 offset += INT_BIT;
224 }
225 return 0;
226}
227
228#endif // !LELY_NO_MALLOC
int bitset_ffs(const struct bitset *set)
Returns the index (starting from one) of the first set bit in set, or 0 if all bits are zero.
Definition bitset.c:147
int bitset_test(const struct bitset *set, int n)
Returns 1 if bit n in set is set, and 0 otherwise.
Definition bitset.c:102
int bitset_size(const struct bitset *set)
Returns the size (in number of bits) of set.
Definition bitset.c:70
int bitset_ffz(const struct bitset *set)
Returns the index (starting from one) of the first zero bit in set, or 0 if all bits are set.
Definition bitset.c:161
int bitset_resize(struct bitset *set, int size)
Resizes a bitset.
Definition bitset.c:76
void bitset_set(struct bitset *set, int n)
Sets bit n in set.
Definition bitset.c:110
int bitset_fnz(const struct bitset *set, int n)
Returns the index (starting from one) of the first zero bit higher or equal to n in set,...
Definition bitset.c:202
void bitset_compl(struct bitset *set)
Flip all bits in set.
Definition bitset.c:140
void bitset_clr_all(struct bitset *set)
Clears all bits in set.
Definition bitset.c:133
void bitset_clr(struct bitset *set, int n)
Clears bit n in set.
Definition bitset.c:125
void bitset_fini(struct bitset *set)
Finalizes a bitset.
Definition bitset.c:60
int bitset_init(struct bitset *set, int size)
Initializes a bitset.
Definition bitset.c:39
int bitset_fns(const struct bitset *set, int n)
Returns the index (starting from one) of the first set bit higher or equal to n in set,...
Definition bitset.c:175
void bitset_set_all(struct bitset *set)
Sets all bits in set.
Definition bitset.c:118
This header file is part of the utilities library; it contains the bitset declarations.
This header file is part of the utilities library; it contains the native and platform-independent er...
void set_errc(int errc)
Sets the current (thread-specific) native error code to errc.
Definition errnum.c:944
int errno2c(int errnum)
Transforms a standard C error number to a native error code.
Definition errnum.c:46
#define MAX(a, b)
Returns the maximum of a and b.
Definition util.h:65
This is the internal header file of the utilities library.
This header file is part of the C11 and POSIX compatibility library; it includes <stdlib....
This header file is part of the C11 and POSIX compatibility library; it includes <strings....
int ffs(int i)
Finds the index of the first (least significant) bit set in i.
Definition strings.h:58
A variable-sized bitset.
Definition bitset.h:28
unsigned int * bits
An array of size integers.
Definition bitset.h:32
int size
The number of integers in bits.
Definition bitset.h:30