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 
38 int
39 bitset_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 
59 void
60 bitset_fini(struct bitset *set)
61 {
62  assert(set);
63 
64  set->size = 0;
65  free(set->bits);
66  set->bits = NULL;
67 }
68 
69 int
70 bitset_size(const struct bitset *set)
71 {
72  return set->size * INT_BIT;
73 }
74 
75 int
76 bitset_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 
101 int
102 bitset_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 
109 void
110 bitset_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 
117 void
118 bitset_set_all(struct bitset *set)
119 {
120  for (int i = 0; i < set->size; i++)
121  set->bits[i] = ~0u;
122 }
123 
124 void
125 bitset_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 
132 void
133 bitset_clr_all(struct bitset *set)
134 {
135  for (int i = 0; i < set->size; i++)
136  set->bits[i] = 0;
137 }
138 
139 void
140 bitset_compl(struct bitset *set)
141 {
142  for (int i = 0; i < set->size; i++)
143  set->bits[i] = ~set->bits[i];
144 }
145 
146 int
147 bitset_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 
160 int
161 bitset_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 
174 int
175 bitset_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 
201 int
202 bitset_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
bitset_test
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
bitset_clr
void bitset_clr(struct bitset *set, int n)
Clears bit n in set.
Definition: bitset.c:125
bitset_ffs
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
bitset_set
void bitset_set(struct bitset *set, int n)
Sets bit n in set.
Definition: bitset.c:110
bitset_set_all
void bitset_set_all(struct bitset *set)
Sets all bits in set.
Definition: bitset.c:118
errno2c
int errno2c(int errnum)
Transforms a standard C error number to a native error code.
Definition: errnum.c:46
util.h
bitset_fns
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
set_errc
void set_errc(int errc)
Sets the current (thread-specific) native error code to errc.
Definition: errnum.c:944
MAX
#define MAX(a, b)
Returns the maximum of a and b.
Definition: util.h:65
bitset::size
int size
The number of integers in bits.
Definition: bitset.h:30
errnum.h
bitset_clr_all
void bitset_clr_all(struct bitset *set)
Clears all bits in set.
Definition: bitset.c:133
bitset_resize
int bitset_resize(struct bitset *set, int size)
Resizes a bitset.
Definition: bitset.c:76
bitset
A variable-sized bitset.
Definition: bitset.h:28
strings.h
bitset_init
int bitset_init(struct bitset *set, int size)
Initializes a bitset.
Definition: bitset.c:39
bitset_fini
void bitset_fini(struct bitset *set)
Finalizes a bitset.
Definition: bitset.c:60
bitset_ffz
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
stdlib.h
bitset_fnz
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
bitset_size
int bitset_size(const struct bitset *set)
Returns the size (in number of bits) of set.
Definition: bitset.c:70
bitset.h
bitset_compl
void bitset_compl(struct bitset *set)
Flip all bits in set.
Definition: bitset.c:140
bitset::bits
unsigned int * bits
An array of size integers.
Definition: bitset.h:32