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