array.c 18 KB

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