]>
Commit | Line | Data |
---|---|---|
613f5e1a | 1 | /* Array bitsets. |
98744608 | 2 | Copyright (C) 2002, 2003, 2006, 2009 Free Software Foundation, Inc. |
7086e707 AD |
3 | Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). |
4 | ||
f16b0819 | 5 | This program is free software: you can redistribute it and/or modify |
ef017502 | 6 | it under the terms of the GNU General Public License as published by |
f16b0819 | 7 | the Free Software Foundation, either version 3 of the License, or |
ef017502 | 8 | (at your option) any later version. |
7086e707 | 9 | |
ef017502 AD |
10 | This program is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
7086e707 | 14 | |
ef017502 | 15 | You should have received a copy of the GNU General Public License |
f16b0819 | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
7086e707 | 17 | |
231ed89a | 18 | #include <config.h> |
7086e707 | 19 | |
613f5e1a | 20 | #include "abitset.h" |
d4d399fc | 21 | #include <stddef.h> |
7086e707 | 22 | #include <stdlib.h> |
ef017502 | 23 | #include <string.h> |
7086e707 AD |
24 | |
25 | /* This file implements fixed size bitsets stored as an array | |
26 | of words. Any unused bits in the last word must be zero. */ | |
27 | ||
613f5e1a AD |
28 | #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) |
29 | #define ABITSET_WORDS(X) ((X)->a.words) | |
7086e707 AD |
30 | |
31 | ||
62a34c3e | 32 | static bitset_bindex |
68cae94e | 33 | abitset_resize (bitset src, bitset_bindex size) |
7086e707 | 34 | { |
eaef5507 | 35 | /* These bitsets have a fixed size. */ |
c21493b8 PE |
36 | if (BITSET_SIZE_ (src) != size) |
37 | abort (); | |
38 | ||
39 | return size; | |
eaef5507 | 40 | } |
7086e707 AD |
41 | |
42 | /* Find list of up to NUM bits set in BSET starting from and including | |
ef017502 AD |
43 | *NEXT and store in array LIST. Return with actual number of bits |
44 | found and with *NEXT indicating where search stopped. */ | |
62a34c3e | 45 | static bitset_bindex |
a911db9c PE |
46 | abitset_small_list (bitset src, bitset_bindex *list, |
47 | bitset_bindex num, bitset_bindex *next) | |
7086e707 AD |
48 | { |
49 | bitset_bindex bitno; | |
50 | bitset_bindex count; | |
51 | bitset_windex size; | |
52 | bitset_word word; | |
53 | ||
613f5e1a | 54 | word = ABITSET_WORDS (src)[0]; |
7086e707 AD |
55 | |
56 | /* Short circuit common case. */ | |
57 | if (!word) | |
58 | return 0; | |
59 | ||
eaef5507 | 60 | size = BITSET_SIZE_ (src); |
7086e707 AD |
61 | bitno = *next; |
62 | if (bitno >= size) | |
63 | return 0; | |
64 | ||
65 | word >>= bitno; | |
66 | ||
67 | /* If num is 1, we could speed things up with a binary search | |
68 | of the word of interest. */ | |
69 | ||
70 | if (num >= BITSET_WORD_BITS) | |
ef017502 | 71 | { |
7086e707 | 72 | for (count = 0; word; bitno++) |
ef017502 | 73 | { |
7086e707 | 74 | if (word & 1) |
ef017502 | 75 | list[count++] = bitno; |
7086e707 | 76 | word >>= 1; |
ef017502 AD |
77 | } |
78 | } | |
7086e707 | 79 | else |
ef017502 | 80 | { |
7086e707 | 81 | for (count = 0; word; bitno++) |
ef017502 | 82 | { |
7086e707 | 83 | if (word & 1) |
ef017502 | 84 | { |
7086e707 AD |
85 | list[count++] = bitno; |
86 | if (count >= num) | |
ef017502 | 87 | { |
7086e707 AD |
88 | bitno++; |
89 | break; | |
ef017502 AD |
90 | } |
91 | } | |
7086e707 | 92 | word >>= 1; |
ef017502 AD |
93 | } |
94 | } | |
7086e707 AD |
95 | |
96 | *next = bitno; | |
97 | return count; | |
98 | } | |
99 | ||
100 | ||
101 | /* Set bit BITNO in bitset DST. */ | |
102 | static void | |
a911db9c | 103 | abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED) |
7086e707 | 104 | { |
eaef5507 PE |
105 | /* This should never occur for abitsets since we should always hit |
106 | the cache. It is likely someone is trying to access outside the | |
107 | bounds of the bitset. */ | |
ef017502 | 108 | abort (); |
7086e707 AD |
109 | } |
110 | ||
111 | ||
112 | /* Reset bit BITNO in bitset DST. */ | |
113 | static void | |
a911db9c PE |
114 | abitset_reset (bitset dst ATTRIBUTE_UNUSED, |
115 | bitset_bindex bitno ATTRIBUTE_UNUSED) | |
7086e707 | 116 | { |
eaef5507 PE |
117 | /* This should never occur for abitsets since we should always hit |
118 | the cache. It is likely someone is trying to access outside the | |
119 | bounds of the bitset. Since the bit is zero anyway, let it pass. */ | |
7086e707 AD |
120 | } |
121 | ||
122 | ||
123 | /* Test bit BITNO in bitset SRC. */ | |
d0829076 | 124 | static bool |
a911db9c PE |
125 | abitset_test (bitset src ATTRIBUTE_UNUSED, |
126 | bitset_bindex bitno ATTRIBUTE_UNUSED) | |
7086e707 | 127 | { |
6aa452a6 AD |
128 | /* This should never occur for abitsets since we should always |
129 | hit the cache. */ | |
d0829076 | 130 | return false; |
7086e707 AD |
131 | } |
132 | ||
133 | ||
134 | /* Find list of up to NUM bits set in BSET in reverse order, starting | |
135 | from and including NEXT and store in array LIST. Return with | |
136 | actual number of bits found and with *NEXT indicating where search | |
137 | stopped. */ | |
62a34c3e | 138 | static bitset_bindex |
a911db9c PE |
139 | abitset_list_reverse (bitset src, bitset_bindex *list, |
140 | bitset_bindex num, bitset_bindex *next) | |
7086e707 AD |
141 | { |
142 | bitset_bindex bitno; | |
143 | bitset_bindex rbitno; | |
144 | bitset_bindex count; | |
345cea78 | 145 | bitset_windex windex; |
7086e707 AD |
146 | unsigned int bitcnt; |
147 | bitset_bindex bitoff; | |
613f5e1a | 148 | bitset_word *srcp = ABITSET_WORDS (src); |
eaef5507 | 149 | bitset_bindex n_bits = BITSET_SIZE_ (src); |
7086e707 AD |
150 | |
151 | rbitno = *next; | |
152 | ||
153 | /* If num is 1, we could speed things up with a binary search | |
154 | of the word of interest. */ | |
155 | ||
156 | if (rbitno >= n_bits) | |
ef017502 | 157 | return 0; |
7086e707 AD |
158 | |
159 | count = 0; | |
160 | ||
161 | bitno = n_bits - (rbitno + 1); | |
162 | ||
345cea78 | 163 | windex = bitno / BITSET_WORD_BITS; |
7086e707 | 164 | bitcnt = bitno % BITSET_WORD_BITS; |
345cea78 | 165 | bitoff = windex * BITSET_WORD_BITS; |
7086e707 | 166 | |
d6eba423 | 167 | do |
7086e707 | 168 | { |
6aa452a6 AD |
169 | bitset_word word; |
170 | ||
345cea78 | 171 | word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); |
7086e707 AD |
172 | for (; word; bitcnt--) |
173 | { | |
174 | if (word & BITSET_MSB) | |
175 | { | |
176 | list[count++] = bitoff + bitcnt; | |
177 | if (count >= num) | |
178 | { | |
179 | *next = n_bits - (bitoff + bitcnt); | |
180 | return count; | |
181 | } | |
182 | } | |
183 | word <<= 1; | |
184 | } | |
d6eba423 PE |
185 | bitoff -= BITSET_WORD_BITS; |
186 | bitcnt = BITSET_WORD_BITS - 1; | |
7086e707 | 187 | } |
d6eba423 | 188 | while (windex--); |
7086e707 AD |
189 | |
190 | *next = n_bits - (bitoff + 1); | |
191 | return count; | |
192 | } | |
193 | ||
194 | ||
195 | /* Find list of up to NUM bits set in BSET starting from and including | |
ef017502 AD |
196 | *NEXT and store in array LIST. Return with actual number of bits |
197 | found and with *NEXT indicating where search stopped. */ | |
62a34c3e | 198 | static bitset_bindex |
a911db9c PE |
199 | abitset_list (bitset src, bitset_bindex *list, |
200 | bitset_bindex num, bitset_bindex *next) | |
7086e707 AD |
201 | { |
202 | bitset_bindex bitno; | |
203 | bitset_bindex count; | |
345cea78 | 204 | bitset_windex windex; |
7086e707 | 205 | bitset_bindex bitoff; |
ef017502 | 206 | bitset_windex size = src->b.csize; |
613f5e1a | 207 | bitset_word *srcp = ABITSET_WORDS (src); |
7086e707 AD |
208 | bitset_word word; |
209 | ||
210 | bitno = *next; | |
211 | ||
212 | count = 0; | |
ef017502 | 213 | if (!bitno) |
7086e707 AD |
214 | { |
215 | /* Many bitsets are zero, so make this common case fast. */ | |
345cea78 | 216 | for (windex = 0; windex < size && !srcp[windex]; windex++) |
7086e707 | 217 | continue; |
345cea78 | 218 | if (windex >= size) |
7086e707 AD |
219 | return 0; |
220 | ||
221 | /* If num is 1, we could speed things up with a binary search | |
222 | of the current word. */ | |
223 | ||
345cea78 | 224 | bitoff = windex * BITSET_WORD_BITS; |
7086e707 AD |
225 | } |
226 | else | |
227 | { | |
eaef5507 | 228 | if (bitno >= BITSET_SIZE_ (src)) |
7086e707 AD |
229 | return 0; |
230 | ||
345cea78 | 231 | windex = bitno / BITSET_WORD_BITS; |
7086e707 AD |
232 | bitno = bitno % BITSET_WORD_BITS; |
233 | ||
234 | if (bitno) | |
235 | { | |
236 | /* Handle the case where we start within a word. | |
237 | Most often, this is executed with large bitsets | |
238 | with many set bits where we filled the array | |
239 | on the previous call to this function. */ | |
240 | ||
345cea78 AD |
241 | bitoff = windex * BITSET_WORD_BITS; |
242 | word = srcp[windex] >> bitno; | |
7086e707 AD |
243 | for (bitno = bitoff + bitno; word; bitno++) |
244 | { | |
245 | if (word & 1) | |
246 | { | |
247 | list[count++] = bitno; | |
248 | if (count >= num) | |
249 | { | |
250 | *next = bitno + 1; | |
251 | return count; | |
252 | } | |
253 | } | |
254 | word >>= 1; | |
255 | } | |
345cea78 | 256 | windex++; |
7086e707 | 257 | } |
345cea78 | 258 | bitoff = windex * BITSET_WORD_BITS; |
7086e707 AD |
259 | } |
260 | ||
345cea78 | 261 | for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) |
7086e707 | 262 | { |
345cea78 | 263 | if (!(word = srcp[windex])) |
7086e707 AD |
264 | continue; |
265 | ||
266 | if ((count + BITSET_WORD_BITS) < num) | |
ef017502 AD |
267 | { |
268 | for (bitno = bitoff; word; bitno++) | |
269 | { | |
270 | if (word & 1) | |
271 | list[count++] = bitno; | |
272 | word >>= 1; | |
273 | } | |
274 | } | |
7086e707 AD |
275 | else |
276 | { | |
277 | for (bitno = bitoff; word; bitno++) | |
278 | { | |
279 | if (word & 1) | |
280 | { | |
281 | list[count++] = bitno; | |
282 | if (count >= num) | |
283 | { | |
284 | *next = bitno + 1; | |
285 | return count; | |
286 | } | |
287 | } | |
288 | word >>= 1; | |
289 | } | |
290 | } | |
291 | } | |
292 | ||
293 | *next = bitoff; | |
294 | return count; | |
295 | } | |
296 | ||
297 | ||
298 | /* Ensure that any unused bits within the last word are clear. */ | |
299 | static inline void | |
a911db9c | 300 | abitset_unused_clear (bitset dst) |
7086e707 AD |
301 | { |
302 | unsigned int last_bit; | |
303 | ||
eaef5507 | 304 | last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; |
7086e707 | 305 | if (last_bit) |
613f5e1a | 306 | ABITSET_WORDS (dst)[dst->b.csize - 1] &= |
d6eba423 | 307 | ((bitset_word) 1 << last_bit) - 1; |
7086e707 AD |
308 | } |
309 | ||
310 | ||
6aa452a6 | 311 | static void |
a911db9c | 312 | abitset_ones (bitset dst) |
7086e707 | 313 | { |
613f5e1a | 314 | bitset_word *dstp = ABITSET_WORDS (dst); |
62a34c3e | 315 | size_t bytes; |
7086e707 | 316 | |
ef017502 | 317 | bytes = sizeof (bitset_word) * dst->b.csize; |
7086e707 | 318 | |
6aa452a6 AD |
319 | memset (dstp, -1, bytes); |
320 | abitset_unused_clear (dst); | |
321 | } | |
322 | ||
323 | ||
324 | static void | |
a911db9c | 325 | abitset_zero (bitset dst) |
6aa452a6 AD |
326 | { |
327 | bitset_word *dstp = ABITSET_WORDS (dst); | |
62a34c3e | 328 | size_t bytes; |
6aa452a6 AD |
329 | |
330 | bytes = sizeof (bitset_word) * dst->b.csize; | |
331 | ||
332 | memset (dstp, 0, bytes); | |
333 | } | |
7086e707 | 334 | |
6aa452a6 | 335 | |
d0829076 | 336 | static bool |
a911db9c | 337 | abitset_empty_p (bitset dst) |
6aa452a6 | 338 | { |
62a34c3e | 339 | bitset_windex i; |
6aa452a6 AD |
340 | bitset_word *dstp = ABITSET_WORDS (dst); |
341 | ||
342 | for (i = 0; i < dst->b.csize; i++) | |
343 | if (dstp[i]) | |
d0829076 | 344 | return false; |
7086e707 | 345 | |
d0829076 | 346 | return true; |
7086e707 AD |
347 | } |
348 | ||
349 | ||
6aa452a6 | 350 | static void |
a911db9c | 351 | abitset_copy1 (bitset dst, bitset src) |
6aa452a6 AD |
352 | { |
353 | bitset_word *srcp = ABITSET_WORDS (src); | |
354 | bitset_word *dstp = ABITSET_WORDS (dst); | |
355 | bitset_windex size = dst->b.csize; | |
356 | ||
357 | if (srcp == dstp) | |
358 | return; | |
359 | memcpy (dstp, srcp, sizeof (bitset_word) * size); | |
360 | } | |
361 | ||
362 | ||
363 | static void | |
a911db9c | 364 | abitset_not (bitset dst, bitset src) |
6aa452a6 | 365 | { |
62a34c3e | 366 | bitset_windex i; |
6aa452a6 AD |
367 | bitset_word *srcp = ABITSET_WORDS (src); |
368 | bitset_word *dstp = ABITSET_WORDS (dst); | |
369 | bitset_windex size = dst->b.csize; | |
370 | ||
371 | for (i = 0; i < size; i++) | |
372 | *dstp++ = ~(*srcp++); | |
373 | abitset_unused_clear (dst); | |
374 | } | |
375 | ||
a911db9c | 376 | |
d0829076 | 377 | static bool |
a911db9c | 378 | abitset_equal_p (bitset dst, bitset src) |
7086e707 | 379 | { |
62a34c3e | 380 | bitset_windex i; |
613f5e1a AD |
381 | bitset_word *srcp = ABITSET_WORDS (src); |
382 | bitset_word *dstp = ABITSET_WORDS (dst); | |
ef017502 | 383 | bitset_windex size = dst->b.csize; |
7086e707 | 384 | |
6aa452a6 AD |
385 | for (i = 0; i < size; i++) |
386 | if (*srcp++ != *dstp++) | |
d0829076 PE |
387 | return false; |
388 | return true; | |
6aa452a6 AD |
389 | } |
390 | ||
391 | ||
d0829076 | 392 | static bool |
a911db9c | 393 | abitset_subset_p (bitset dst, bitset src) |
6aa452a6 | 394 | { |
62a34c3e | 395 | bitset_windex i; |
6aa452a6 AD |
396 | bitset_word *srcp = ABITSET_WORDS (src); |
397 | bitset_word *dstp = ABITSET_WORDS (dst); | |
398 | bitset_windex size = dst->b.csize; | |
a911db9c | 399 | |
6aa452a6 AD |
400 | for (i = 0; i < size; i++, dstp++, srcp++) |
401 | if (*dstp != (*srcp | *dstp)) | |
d0829076 PE |
402 | return false; |
403 | return true; | |
6aa452a6 AD |
404 | } |
405 | ||
406 | ||
d0829076 | 407 | static bool |
a911db9c | 408 | abitset_disjoint_p (bitset dst, bitset src) |
6aa452a6 | 409 | { |
62a34c3e | 410 | bitset_windex i; |
6aa452a6 AD |
411 | bitset_word *srcp = ABITSET_WORDS (src); |
412 | bitset_word *dstp = ABITSET_WORDS (dst); | |
413 | bitset_windex size = dst->b.csize; | |
414 | ||
415 | for (i = 0; i < size; i++) | |
416 | if (*srcp++ & *dstp++) | |
d0829076 | 417 | return false; |
7086e707 | 418 | |
d0829076 | 419 | return true; |
7086e707 AD |
420 | } |
421 | ||
422 | ||
6aa452a6 | 423 | static void |
a911db9c | 424 | abitset_and (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 425 | { |
62a34c3e | 426 | bitset_windex i; |
6aa452a6 AD |
427 | bitset_word *src1p = ABITSET_WORDS (src1); |
428 | bitset_word *src2p = ABITSET_WORDS (src2); | |
429 | bitset_word *dstp = ABITSET_WORDS (dst); | |
430 | bitset_windex size = dst->b.csize; | |
431 | ||
432 | for (i = 0; i < size; i++) | |
433 | *dstp++ = *src1p++ & *src2p++; | |
434 | } | |
435 | ||
436 | ||
d0829076 | 437 | static bool |
a911db9c | 438 | abitset_and_cmp (bitset dst, bitset src1, bitset src2) |
7086e707 | 439 | { |
62a34c3e | 440 | bitset_windex i; |
d0829076 | 441 | bool changed = false; |
613f5e1a AD |
442 | bitset_word *src1p = ABITSET_WORDS (src1); |
443 | bitset_word *src2p = ABITSET_WORDS (src2); | |
444 | bitset_word *dstp = ABITSET_WORDS (dst); | |
ef017502 | 445 | bitset_windex size = dst->b.csize; |
7086e707 | 446 | |
6aa452a6 | 447 | for (i = 0; i < size; i++, dstp++) |
7086e707 | 448 | { |
6aa452a6 | 449 | bitset_word tmp = *src1p++ & *src2p++; |
a911db9c | 450 | |
6aa452a6 | 451 | if (*dstp != tmp) |
7086e707 | 452 | { |
d0829076 | 453 | changed = true; |
6aa452a6 | 454 | *dstp = tmp; |
7086e707 | 455 | } |
6aa452a6 AD |
456 | } |
457 | return changed; | |
458 | } | |
7086e707 | 459 | |
7086e707 | 460 | |
6aa452a6 | 461 | static void |
a911db9c | 462 | abitset_andn (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 463 | { |
62a34c3e | 464 | bitset_windex i; |
6aa452a6 AD |
465 | bitset_word *src1p = ABITSET_WORDS (src1); |
466 | bitset_word *src2p = ABITSET_WORDS (src2); | |
467 | bitset_word *dstp = ABITSET_WORDS (dst); | |
468 | bitset_windex size = dst->b.csize; | |
7086e707 | 469 | |
6aa452a6 AD |
470 | for (i = 0; i < size; i++) |
471 | *dstp++ = *src1p++ & ~(*src2p++); | |
472 | } | |
7086e707 | 473 | |
7086e707 | 474 | |
d0829076 | 475 | static bool |
a911db9c | 476 | abitset_andn_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 477 | { |
62a34c3e | 478 | bitset_windex i; |
d0829076 | 479 | bool changed = false; |
6aa452a6 AD |
480 | bitset_word *src1p = ABITSET_WORDS (src1); |
481 | bitset_word *src2p = ABITSET_WORDS (src2); | |
482 | bitset_word *dstp = ABITSET_WORDS (dst); | |
483 | bitset_windex size = dst->b.csize; | |
a911db9c | 484 | |
6aa452a6 AD |
485 | for (i = 0; i < size; i++, dstp++) |
486 | { | |
487 | bitset_word tmp = *src1p++ & ~(*src2p++); | |
a911db9c | 488 | |
6aa452a6 | 489 | if (*dstp != tmp) |
7086e707 | 490 | { |
d0829076 | 491 | changed = true; |
6aa452a6 | 492 | *dstp = tmp; |
7086e707 | 493 | } |
6aa452a6 AD |
494 | } |
495 | return changed; | |
496 | } | |
497 | ||
498 | ||
499 | static void | |
a911db9c | 500 | abitset_or (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 501 | { |
62a34c3e | 502 | bitset_windex i; |
6aa452a6 AD |
503 | bitset_word *src1p = ABITSET_WORDS (src1); |
504 | bitset_word *src2p = ABITSET_WORDS (src2); | |
505 | bitset_word *dstp = ABITSET_WORDS (dst); | |
506 | bitset_windex size = dst->b.csize; | |
507 | ||
508 | for (i = 0; i < size; i++) | |
509 | *dstp++ = *src1p++ | *src2p++; | |
510 | } | |
511 | ||
7086e707 | 512 | |
d0829076 | 513 | static bool |
a911db9c | 514 | abitset_or_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 515 | { |
62a34c3e | 516 | bitset_windex i; |
d0829076 | 517 | bool changed = false; |
6aa452a6 AD |
518 | bitset_word *src1p = ABITSET_WORDS (src1); |
519 | bitset_word *src2p = ABITSET_WORDS (src2); | |
520 | bitset_word *dstp = ABITSET_WORDS (dst); | |
521 | bitset_windex size = dst->b.csize; | |
522 | ||
523 | for (i = 0; i < size; i++, dstp++) | |
524 | { | |
525 | bitset_word tmp = *src1p++ | *src2p++; | |
a911db9c | 526 | |
6aa452a6 AD |
527 | if (*dstp != tmp) |
528 | { | |
d0829076 | 529 | changed = true; |
6aa452a6 AD |
530 | *dstp = tmp; |
531 | } | |
7086e707 | 532 | } |
6aa452a6 AD |
533 | return changed; |
534 | } | |
7086e707 | 535 | |
6aa452a6 AD |
536 | |
537 | static void | |
a911db9c | 538 | abitset_xor (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 539 | { |
62a34c3e | 540 | bitset_windex i; |
6aa452a6 AD |
541 | bitset_word *src1p = ABITSET_WORDS (src1); |
542 | bitset_word *src2p = ABITSET_WORDS (src2); | |
543 | bitset_word *dstp = ABITSET_WORDS (dst); | |
544 | bitset_windex size = dst->b.csize; | |
545 | ||
546 | for (i = 0; i < size; i++) | |
547 | *dstp++ = *src1p++ ^ *src2p++; | |
548 | } | |
549 | ||
550 | ||
d0829076 | 551 | static bool |
a911db9c | 552 | abitset_xor_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 | 553 | { |
62a34c3e | 554 | bitset_windex i; |
d0829076 | 555 | bool changed = false; |
6aa452a6 AD |
556 | bitset_word *src1p = ABITSET_WORDS (src1); |
557 | bitset_word *src2p = ABITSET_WORDS (src2); | |
558 | bitset_word *dstp = ABITSET_WORDS (dst); | |
559 | bitset_windex size = dst->b.csize; | |
560 | ||
561 | for (i = 0; i < size; i++, dstp++) | |
562 | { | |
563 | bitset_word tmp = *src1p++ ^ *src2p++; | |
a911db9c | 564 | |
6aa452a6 AD |
565 | if (*dstp != tmp) |
566 | { | |
d0829076 | 567 | changed = true; |
6aa452a6 AD |
568 | *dstp = tmp; |
569 | } | |
570 | } | |
7086e707 AD |
571 | return changed; |
572 | } | |
573 | ||
574 | ||
6aa452a6 | 575 | static void |
a911db9c | 576 | abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 | 577 | { |
62a34c3e | 578 | bitset_windex i; |
6aa452a6 AD |
579 | bitset_word *src1p = ABITSET_WORDS (src1); |
580 | bitset_word *src2p = ABITSET_WORDS (src2); | |
581 | bitset_word *src3p = ABITSET_WORDS (src3); | |
582 | bitset_word *dstp = ABITSET_WORDS (dst); | |
583 | bitset_windex size = dst->b.csize; | |
a911db9c | 584 | |
6aa452a6 AD |
585 | for (i = 0; i < size; i++) |
586 | *dstp++ = (*src1p++ & *src2p++) | *src3p++; | |
587 | } | |
588 | ||
589 | ||
d0829076 | 590 | static bool |
a911db9c | 591 | abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
7086e707 | 592 | { |
62a34c3e | 593 | bitset_windex i; |
d0829076 | 594 | bool changed = false; |
613f5e1a AD |
595 | bitset_word *src1p = ABITSET_WORDS (src1); |
596 | bitset_word *src2p = ABITSET_WORDS (src2); | |
597 | bitset_word *src3p = ABITSET_WORDS (src3); | |
598 | bitset_word *dstp = ABITSET_WORDS (dst); | |
ef017502 | 599 | bitset_windex size = dst->b.csize; |
a911db9c | 600 | |
6aa452a6 | 601 | for (i = 0; i < size; i++, dstp++) |
7086e707 | 602 | { |
6aa452a6 | 603 | bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; |
a911db9c | 604 | |
6aa452a6 | 605 | if (*dstp != tmp) |
7086e707 | 606 | { |
d0829076 | 607 | changed = true; |
6aa452a6 | 608 | *dstp = tmp; |
7086e707 | 609 | } |
6aa452a6 AD |
610 | } |
611 | return changed; | |
612 | } | |
7086e707 | 613 | |
7086e707 | 614 | |
6aa452a6 | 615 | static void |
a911db9c | 616 | abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 | 617 | { |
62a34c3e | 618 | bitset_windex i; |
6aa452a6 AD |
619 | bitset_word *src1p = ABITSET_WORDS (src1); |
620 | bitset_word *src2p = ABITSET_WORDS (src2); | |
621 | bitset_word *src3p = ABITSET_WORDS (src3); | |
622 | bitset_word *dstp = ABITSET_WORDS (dst); | |
623 | bitset_windex size = dst->b.csize; | |
a911db9c | 624 | |
6aa452a6 AD |
625 | for (i = 0; i < size; i++) |
626 | *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; | |
627 | } | |
7086e707 | 628 | |
7086e707 | 629 | |
d0829076 | 630 | static bool |
a911db9c | 631 | abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 | 632 | { |
62a34c3e | 633 | bitset_windex i; |
d0829076 | 634 | bool changed = false; |
6aa452a6 AD |
635 | bitset_word *src1p = ABITSET_WORDS (src1); |
636 | bitset_word *src2p = ABITSET_WORDS (src2); | |
637 | bitset_word *src3p = ABITSET_WORDS (src3); | |
638 | bitset_word *dstp = ABITSET_WORDS (dst); | |
639 | bitset_windex size = dst->b.csize; | |
a911db9c | 640 | |
6aa452a6 AD |
641 | for (i = 0; i < size; i++, dstp++) |
642 | { | |
643 | bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; | |
a911db9c | 644 | |
6aa452a6 AD |
645 | if (*dstp != tmp) |
646 | { | |
d0829076 | 647 | changed = true; |
6aa452a6 | 648 | *dstp = tmp; |
7086e707 | 649 | } |
7086e707 | 650 | } |
6aa452a6 AD |
651 | return changed; |
652 | } | |
653 | ||
654 | ||
655 | static void | |
a911db9c | 656 | abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 | 657 | { |
62a34c3e | 658 | bitset_windex i; |
6aa452a6 AD |
659 | bitset_word *src1p = ABITSET_WORDS (src1); |
660 | bitset_word *src2p = ABITSET_WORDS (src2); | |
661 | bitset_word *src3p = ABITSET_WORDS (src3); | |
662 | bitset_word *dstp = ABITSET_WORDS (dst); | |
663 | bitset_windex size = dst->b.csize; | |
a911db9c | 664 | |
6aa452a6 AD |
665 | for (i = 0; i < size; i++) |
666 | *dstp++ = (*src1p++ | *src2p++) & *src3p++; | |
667 | } | |
668 | ||
7086e707 | 669 | |
d0829076 | 670 | static bool |
a911db9c | 671 | abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 | 672 | { |
62a34c3e | 673 | bitset_windex i; |
d0829076 | 674 | bool changed = false; |
6aa452a6 AD |
675 | bitset_word *src1p = ABITSET_WORDS (src1); |
676 | bitset_word *src2p = ABITSET_WORDS (src2); | |
677 | bitset_word *src3p = ABITSET_WORDS (src3); | |
678 | bitset_word *dstp = ABITSET_WORDS (dst); | |
679 | bitset_windex size = dst->b.csize; | |
a911db9c | 680 | |
6aa452a6 AD |
681 | for (i = 0; i < size; i++, dstp++) |
682 | { | |
683 | bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; | |
a911db9c | 684 | |
6aa452a6 AD |
685 | if (*dstp != tmp) |
686 | { | |
d0829076 | 687 | changed = true; |
6aa452a6 AD |
688 | *dstp = tmp; |
689 | } | |
690 | } | |
7086e707 AD |
691 | return changed; |
692 | } | |
693 | ||
694 | ||
d4d399fc | 695 | static void |
a911db9c | 696 | abitset_copy (bitset dst, bitset src) |
6aa452a6 AD |
697 | { |
698 | if (BITSET_COMPATIBLE_ (dst, src)) | |
699 | abitset_copy1 (dst, src); | |
700 | else | |
701 | bitset_copy_ (dst, src); | |
702 | } | |
703 | ||
704 | ||
7086e707 | 705 | /* Vector of operations for single word bitsets. */ |
6aa452a6 | 706 | struct bitset_vtable abitset_small_vtable = { |
613f5e1a AD |
707 | abitset_set, |
708 | abitset_reset, | |
6aa452a6 | 709 | bitset_toggle_, |
613f5e1a | 710 | abitset_test, |
eaef5507 PE |
711 | abitset_resize, |
712 | bitset_size_, | |
6aa452a6 AD |
713 | bitset_count_, |
714 | abitset_empty_p, | |
715 | abitset_ones, | |
716 | abitset_zero, | |
717 | abitset_copy, | |
718 | abitset_disjoint_p, | |
719 | abitset_equal_p, | |
720 | abitset_not, | |
721 | abitset_subset_p, | |
722 | abitset_and, | |
723 | abitset_and_cmp, | |
724 | abitset_andn, | |
725 | abitset_andn_cmp, | |
726 | abitset_or, | |
727 | abitset_or_cmp, | |
728 | abitset_xor, | |
729 | abitset_xor_cmp, | |
730 | abitset_and_or, | |
731 | abitset_and_or_cmp, | |
732 | abitset_andn_or, | |
733 | abitset_andn_or_cmp, | |
734 | abitset_or_and, | |
735 | abitset_or_and_cmp, | |
613f5e1a | 736 | abitset_small_list, |
6aa452a6 | 737 | abitset_list_reverse, |
ef017502 AD |
738 | NULL, |
739 | BITSET_ARRAY | |
740 | }; | |
7086e707 AD |
741 | |
742 | ||
743 | /* Vector of operations for multiple word bitsets. */ | |
6aa452a6 | 744 | struct bitset_vtable abitset_vtable = { |
613f5e1a AD |
745 | abitset_set, |
746 | abitset_reset, | |
6aa452a6 | 747 | bitset_toggle_, |
613f5e1a | 748 | abitset_test, |
eaef5507 PE |
749 | abitset_resize, |
750 | bitset_size_, | |
6aa452a6 AD |
751 | bitset_count_, |
752 | abitset_empty_p, | |
753 | abitset_ones, | |
754 | abitset_zero, | |
755 | abitset_copy, | |
756 | abitset_disjoint_p, | |
757 | abitset_equal_p, | |
758 | abitset_not, | |
759 | abitset_subset_p, | |
760 | abitset_and, | |
761 | abitset_and_cmp, | |
762 | abitset_andn, | |
763 | abitset_andn_cmp, | |
764 | abitset_or, | |
765 | abitset_or_cmp, | |
766 | abitset_xor, | |
767 | abitset_xor_cmp, | |
768 | abitset_and_or, | |
769 | abitset_and_or_cmp, | |
770 | abitset_andn_or, | |
771 | abitset_andn_or_cmp, | |
772 | abitset_or_and, | |
773 | abitset_or_and_cmp, | |
613f5e1a | 774 | abitset_list, |
6aa452a6 | 775 | abitset_list_reverse, |
ef017502 AD |
776 | NULL, |
777 | BITSET_ARRAY | |
7086e707 AD |
778 | }; |
779 | ||
780 | ||
62a34c3e | 781 | size_t |
a911db9c | 782 | abitset_bytes (bitset_bindex n_bits) |
7086e707 | 783 | { |
62a34c3e PE |
784 | bitset_windex size; |
785 | size_t bytes; | |
d4d399fc PE |
786 | size_t header_size = offsetof (union bitset_union, a.words); |
787 | struct bitset_align_struct { char a; union bitset_union b; }; | |
788 | size_t bitset_alignment = offsetof (struct bitset_align_struct, b); | |
7086e707 | 789 | |
613f5e1a | 790 | size = ABITSET_N_WORDS (n_bits); |
d4d399fc PE |
791 | bytes = header_size + size * sizeof (bitset_word); |
792 | ||
793 | /* Align the size properly for a vector of abitset objects. */ | |
794 | if (header_size % bitset_alignment != 0 | |
795 | || sizeof (bitset_word) % bitset_alignment != 0) | |
796 | { | |
797 | bytes += bitset_alignment - 1; | |
798 | bytes -= bytes % bitset_alignment; | |
799 | } | |
800 | ||
801 | return bytes; | |
7086e707 AD |
802 | } |
803 | ||
804 | ||
805 | bitset | |
a911db9c | 806 | abitset_init (bitset bset, bitset_bindex n_bits) |
7086e707 AD |
807 | { |
808 | bitset_windex size; | |
809 | ||
613f5e1a | 810 | size = ABITSET_N_WORDS (n_bits); |
eaef5507 | 811 | BITSET_NBITS_ (bset) = n_bits; |
7086e707 AD |
812 | |
813 | /* Use optimized routines if bitset fits within a single word. | |
814 | There is probably little merit if using caching since | |
815 | the small bitset will always fit in the cache. */ | |
816 | if (size == 1) | |
6aa452a6 | 817 | bset->b.vtable = &abitset_small_vtable; |
7086e707 | 818 | else |
6aa452a6 | 819 | bset->b.vtable = &abitset_vtable; |
7086e707 | 820 | |
ef017502 AD |
821 | bset->b.cindex = 0; |
822 | bset->b.csize = size; | |
613f5e1a | 823 | bset->b.cdata = ABITSET_WORDS (bset); |
7086e707 AD |
824 | return bset; |
825 | } |