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