roaring64.h 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675
  1. #ifndef ROARING64_H
  2. #define ROARING64_H
  3. #include <stdbool.h>
  4. #include <stddef.h>
  5. #include <stdint.h>
  6. #include <roaring/memory.h>
  7. #include <roaring/portability.h>
  8. #include <roaring/roaring_types.h>
  9. #ifdef __cplusplus
  10. extern "C" {
  11. namespace roaring {
  12. namespace api {
  13. #endif
  14. typedef struct roaring64_bitmap_s roaring64_bitmap_t;
  15. typedef struct roaring64_leaf_s roaring64_leaf_t;
  16. typedef struct roaring64_iterator_s roaring64_iterator_t;
  17. /**
  18. * A bit of context usable with `roaring64_bitmap_*_bulk()` functions.
  19. *
  20. * Should be initialized with `{0}` (or `memset()` to all zeros).
  21. * Callers should treat it as an opaque type.
  22. *
  23. * A context may only be used with a single bitmap (unless re-initialized to
  24. * zero), and any modification to a bitmap (other than modifications performed
  25. * with `_bulk()` functions with the context passed) will invalidate any
  26. * contexts associated with that bitmap.
  27. */
  28. typedef struct roaring64_bulk_context_s {
  29. uint8_t high_bytes[6];
  30. roaring64_leaf_t *leaf;
  31. } roaring64_bulk_context_t;
  32. /**
  33. * Dynamically allocates a new bitmap (initially empty).
  34. * Client is responsible for calling `roaring64_bitmap_free()`.
  35. */
  36. roaring64_bitmap_t *roaring64_bitmap_create(void);
  37. void roaring64_bitmap_free(roaring64_bitmap_t *r);
  38. /**
  39. * Returns a copy of a bitmap.
  40. */
  41. roaring64_bitmap_t *roaring64_bitmap_copy(const roaring64_bitmap_t *r);
  42. /**
  43. * Creates a new bitmap of a pointer to N 64-bit integers.
  44. */
  45. roaring64_bitmap_t *roaring64_bitmap_of_ptr(size_t n_args,
  46. const uint64_t *vals);
  47. #ifdef __cplusplus
  48. /**
  49. * Creates a new bitmap which contains all values passed in as arguments.
  50. *
  51. * To create a bitmap from a variable number of arguments, use the
  52. * `roaring64_bitmap_of_ptr` function instead.
  53. */
  54. // Use an immediately invoked closure, capturing by reference
  55. // (in case __VA_ARGS__ refers to context outside the closure)
  56. // Include a 0 at the beginning of the array to make the array length > 0
  57. // (zero sized arrays are not valid in standard c/c++)
  58. #define roaring64_bitmap_from(...) \
  59. [&]() { \
  60. const uint64_t roaring64_bitmap_from_array[] = {0, __VA_ARGS__}; \
  61. return roaring64_bitmap_of_ptr( \
  62. (sizeof(roaring64_bitmap_from_array) / \
  63. sizeof(roaring64_bitmap_from_array[0])) - \
  64. 1, \
  65. &roaring64_bitmap_from_array[1]); \
  66. }()
  67. #else
  68. /**
  69. * Creates a new bitmap which contains all values passed in as arguments.
  70. *
  71. * To create a bitmap from a variable number of arguments, use the
  72. * `roaring64_bitmap_of_ptr` function instead.
  73. */
  74. // While __VA_ARGS__ occurs twice in expansion, one of the times is in a sizeof
  75. // expression, which is an unevaluated context, so it's even safe in the case
  76. // where expressions passed have side effects (roaring64_bitmap_from(my_func(),
  77. // ++i))
  78. // Include a 0 at the beginning of the array to make the array length > 0
  79. // (zero sized arrays are not valid in standard c/c++)
  80. #define roaring64_bitmap_from(...) \
  81. roaring64_bitmap_of_ptr( \
  82. (sizeof((const uint64_t[]){0, __VA_ARGS__}) / sizeof(uint64_t)) - 1, \
  83. &((const uint64_t[]){0, __VA_ARGS__})[1])
  84. #endif
  85. /**
  86. * Create a new bitmap containing all the values in [min, max) that are at a
  87. * distance k*step from min.
  88. */
  89. roaring64_bitmap_t *roaring64_bitmap_from_range(uint64_t min, uint64_t max,
  90. uint64_t step);
  91. /**
  92. * Adds the provided value to the bitmap.
  93. */
  94. void roaring64_bitmap_add(roaring64_bitmap_t *r, uint64_t val);
  95. /**
  96. * Adds the provided value to the bitmap.
  97. * Returns true if a new value was added, false if the value already existed.
  98. */
  99. bool roaring64_bitmap_add_checked(roaring64_bitmap_t *r, uint64_t val);
  100. /**
  101. * Add an item, using context from a previous insert for faster insertion.
  102. *
  103. * `context` will be used to store information between calls to make bulk
  104. * operations faster. `*context` should be zero-initialized before the first
  105. * call to this function.
  106. *
  107. * Modifying the bitmap in any way (other than `-bulk` suffixed functions)
  108. * will invalidate the stored context, calling this function with a non-zero
  109. * context after doing any modification invokes undefined behavior.
  110. *
  111. * In order to exploit this optimization, the caller should call this function
  112. * with values with the same high 48 bits of the value consecutively.
  113. */
  114. void roaring64_bitmap_add_bulk(roaring64_bitmap_t *r,
  115. roaring64_bulk_context_t *context, uint64_t val);
  116. /**
  117. * Add `n_args` values from `vals`, faster than repeatedly calling
  118. * `roaring64_bitmap_add()`
  119. *
  120. * In order to exploit this optimization, the caller should attempt to keep
  121. * values with the same high 48 bits of the value as consecutive elements in
  122. * `vals`.
  123. */
  124. void roaring64_bitmap_add_many(roaring64_bitmap_t *r, size_t n_args,
  125. const uint64_t *vals);
  126. /**
  127. * Add all values in range [min, max).
  128. */
  129. void roaring64_bitmap_add_range(roaring64_bitmap_t *r, uint64_t min,
  130. uint64_t max);
  131. /**
  132. * Add all values in range [min, max].
  133. */
  134. void roaring64_bitmap_add_range_closed(roaring64_bitmap_t *r, uint64_t min,
  135. uint64_t max);
  136. /**
  137. * Removes a value from the bitmap if present.
  138. */
  139. void roaring64_bitmap_remove(roaring64_bitmap_t *r, uint64_t val);
  140. /**
  141. * Removes a value from the bitmap if present, returns true if the value was
  142. * removed and false if the value was not present.
  143. */
  144. bool roaring64_bitmap_remove_checked(roaring64_bitmap_t *r, uint64_t val);
  145. /**
  146. * Remove an item, using context from a previous insert for faster removal.
  147. *
  148. * `context` will be used to store information between calls to make bulk
  149. * operations faster. `*context` should be zero-initialized before the first
  150. * call to this function.
  151. *
  152. * Modifying the bitmap in any way (other than `-bulk` suffixed functions)
  153. * will invalidate the stored context, calling this function with a non-zero
  154. * context after doing any modification invokes undefined behavior.
  155. *
  156. * In order to exploit this optimization, the caller should call this function
  157. * with values with the same high 48 bits of the value consecutively.
  158. */
  159. void roaring64_bitmap_remove_bulk(roaring64_bitmap_t *r,
  160. roaring64_bulk_context_t *context,
  161. uint64_t val);
  162. /**
  163. * Remove `n_args` values from `vals`, faster than repeatedly calling
  164. * `roaring64_bitmap_remove()`
  165. *
  166. * In order to exploit this optimization, the caller should attempt to keep
  167. * values with the same high 48 bits of the value as consecutive elements in
  168. * `vals`.
  169. */
  170. void roaring64_bitmap_remove_many(roaring64_bitmap_t *r, size_t n_args,
  171. const uint64_t *vals);
  172. /**
  173. * Remove all values in range [min, max).
  174. */
  175. void roaring64_bitmap_remove_range(roaring64_bitmap_t *r, uint64_t min,
  176. uint64_t max);
  177. /**
  178. * Remove all values in range [min, max].
  179. */
  180. void roaring64_bitmap_remove_range_closed(roaring64_bitmap_t *r, uint64_t min,
  181. uint64_t max);
  182. /**
  183. * Empties the bitmap.
  184. */
  185. void roaring64_bitmap_clear(roaring64_bitmap_t *r);
  186. /**
  187. * Returns true if the provided value is present.
  188. */
  189. bool roaring64_bitmap_contains(const roaring64_bitmap_t *r, uint64_t val);
  190. /**
  191. * Returns true if all values in the range [min, max) are present.
  192. */
  193. bool roaring64_bitmap_contains_range(const roaring64_bitmap_t *r, uint64_t min,
  194. uint64_t max);
  195. /**
  196. * Check if an item is present using context from a previous insert or search
  197. * for faster search.
  198. *
  199. * `context` will be used to store information between calls to make bulk
  200. * operations faster. `*context` should be zero-initialized before the first
  201. * call to this function.
  202. *
  203. * Modifying the bitmap in any way (other than `-bulk` suffixed functions)
  204. * will invalidate the stored context, calling this function with a non-zero
  205. * context after doing any modification invokes undefined behavior.
  206. *
  207. * In order to exploit this optimization, the caller should call this function
  208. * with values with the same high 48 bits of the value consecutively.
  209. */
  210. bool roaring64_bitmap_contains_bulk(const roaring64_bitmap_t *r,
  211. roaring64_bulk_context_t *context,
  212. uint64_t val);
  213. /**
  214. * Selects the element at index 'rank' where the smallest element is at index 0.
  215. * If the size of the bitmap is strictly greater than rank, then this function
  216. * returns true and sets element to the element of given rank. Otherwise, it
  217. * returns false.
  218. */
  219. bool roaring64_bitmap_select(const roaring64_bitmap_t *r, uint64_t rank,
  220. uint64_t *element);
  221. /**
  222. * Returns the number of integers that are smaller or equal to x. Thus if x is
  223. * the first element, this function will return 1. If x is smaller than the
  224. * smallest element, this function will return 0.
  225. *
  226. * The indexing convention differs between roaring64_bitmap_select and
  227. * roaring64_bitmap_rank: roaring_bitmap64_select refers to the smallest value
  228. * as having index 0, whereas roaring64_bitmap_rank returns 1 when ranking
  229. * the smallest value.
  230. */
  231. uint64_t roaring64_bitmap_rank(const roaring64_bitmap_t *r, uint64_t val);
  232. /**
  233. * Returns true if the given value is in the bitmap, and sets `out_index` to the
  234. * (0-based) index of the value in the bitmap. Returns false if the value is not
  235. * in the bitmap.
  236. */
  237. bool roaring64_bitmap_get_index(const roaring64_bitmap_t *r, uint64_t val,
  238. uint64_t *out_index);
  239. /**
  240. * Returns the number of values in the bitmap.
  241. */
  242. uint64_t roaring64_bitmap_get_cardinality(const roaring64_bitmap_t *r);
  243. /**
  244. * Returns the number of elements in the range [min, max).
  245. */
  246. uint64_t roaring64_bitmap_range_cardinality(const roaring64_bitmap_t *r,
  247. uint64_t min, uint64_t max);
  248. /**
  249. * Returns the number of elements in the range [min, max]
  250. */
  251. uint64_t roaring64_bitmap_range_closed_cardinality(const roaring64_bitmap_t *r,
  252. uint64_t min, uint64_t max);
  253. /**
  254. * Returns true if the bitmap is empty (cardinality is zero).
  255. */
  256. bool roaring64_bitmap_is_empty(const roaring64_bitmap_t *r);
  257. /**
  258. * Returns the smallest value in the set, or UINT64_MAX if the set is empty.
  259. */
  260. uint64_t roaring64_bitmap_minimum(const roaring64_bitmap_t *r);
  261. /**
  262. * Returns the largest value in the set, or 0 if empty.
  263. */
  264. uint64_t roaring64_bitmap_maximum(const roaring64_bitmap_t *r);
  265. /**
  266. * Returns true if the result has at least one run container.
  267. */
  268. bool roaring64_bitmap_run_optimize(roaring64_bitmap_t *r);
  269. /**
  270. * (For advanced users.)
  271. * Collect statistics about the bitmap
  272. */
  273. void roaring64_bitmap_statistics(const roaring64_bitmap_t *r,
  274. roaring64_statistics_t *stat);
  275. /**
  276. * Perform internal consistency checks.
  277. *
  278. * Returns true if the bitmap is consistent. It may be useful to call this
  279. * after deserializing bitmaps from untrusted sources. If
  280. * roaring64_bitmap_internal_validate returns true, then the bitmap is
  281. * consistent and can be trusted not to cause crashes or memory corruption.
  282. *
  283. * If reason is non-null, it will be set to a string describing the first
  284. * inconsistency found if any.
  285. */
  286. bool roaring64_bitmap_internal_validate(const roaring64_bitmap_t *r,
  287. const char **reason);
  288. /**
  289. * Return true if the two bitmaps contain the same elements.
  290. */
  291. bool roaring64_bitmap_equals(const roaring64_bitmap_t *r1,
  292. const roaring64_bitmap_t *r2);
  293. /**
  294. * Return true if all the elements of r1 are also in r2.
  295. */
  296. bool roaring64_bitmap_is_subset(const roaring64_bitmap_t *r1,
  297. const roaring64_bitmap_t *r2);
  298. /**
  299. * Return true if all the elements of r1 are also in r2, and r2 is strictly
  300. * greater than r1.
  301. */
  302. bool roaring64_bitmap_is_strict_subset(const roaring64_bitmap_t *r1,
  303. const roaring64_bitmap_t *r2);
  304. /**
  305. * Computes the intersection between two bitmaps and returns new bitmap. The
  306. * caller is responsible for free-ing the result.
  307. *
  308. * Performance hint: if you are computing the intersection between several
  309. * bitmaps, two-by-two, it is best to start with the smallest bitmaps. You may
  310. * also rely on roaring64_bitmap_and_inplace to avoid creating many temporary
  311. * bitmaps.
  312. */
  313. roaring64_bitmap_t *roaring64_bitmap_and(const roaring64_bitmap_t *r1,
  314. const roaring64_bitmap_t *r2);
  315. /**
  316. * Computes the size of the intersection between two bitmaps.
  317. */
  318. uint64_t roaring64_bitmap_and_cardinality(const roaring64_bitmap_t *r1,
  319. const roaring64_bitmap_t *r2);
  320. /**
  321. * In-place version of `roaring64_bitmap_and()`, modifies `r1`. `r1` and `r2`
  322. * are allowed to be equal.
  323. *
  324. * Performance hint: if you are computing the intersection between several
  325. * bitmaps, two-by-two, it is best to start with the smallest bitmaps.
  326. */
  327. void roaring64_bitmap_and_inplace(roaring64_bitmap_t *r1,
  328. const roaring64_bitmap_t *r2);
  329. /**
  330. * Check whether two bitmaps intersect.
  331. */
  332. bool roaring64_bitmap_intersect(const roaring64_bitmap_t *r1,
  333. const roaring64_bitmap_t *r2);
  334. /**
  335. * Check whether a bitmap intersects the range [min, max).
  336. */
  337. bool roaring64_bitmap_intersect_with_range(const roaring64_bitmap_t *r,
  338. uint64_t min, uint64_t max);
  339. /**
  340. * Computes the Jaccard index between two bitmaps. (Also known as the Tanimoto
  341. * distance, or the Jaccard similarity coefficient)
  342. *
  343. * The Jaccard index is undefined if both bitmaps are empty.
  344. */
  345. double roaring64_bitmap_jaccard_index(const roaring64_bitmap_t *r1,
  346. const roaring64_bitmap_t *r2);
  347. /**
  348. * Computes the union between two bitmaps and returns new bitmap. The caller is
  349. * responsible for free-ing the result.
  350. */
  351. roaring64_bitmap_t *roaring64_bitmap_or(const roaring64_bitmap_t *r1,
  352. const roaring64_bitmap_t *r2);
  353. /**
  354. * Computes the size of the union between two bitmaps.
  355. */
  356. uint64_t roaring64_bitmap_or_cardinality(const roaring64_bitmap_t *r1,
  357. const roaring64_bitmap_t *r2);
  358. /**
  359. * In-place version of `roaring64_bitmap_or(), modifies `r1`.
  360. */
  361. void roaring64_bitmap_or_inplace(roaring64_bitmap_t *r1,
  362. const roaring64_bitmap_t *r2);
  363. /**
  364. * Computes the symmetric difference (xor) between two bitmaps and returns a new
  365. * bitmap. The caller is responsible for free-ing the result.
  366. */
  367. roaring64_bitmap_t *roaring64_bitmap_xor(const roaring64_bitmap_t *r1,
  368. const roaring64_bitmap_t *r2);
  369. /**
  370. * Computes the size of the symmetric difference (xor) between two bitmaps.
  371. */
  372. uint64_t roaring64_bitmap_xor_cardinality(const roaring64_bitmap_t *r1,
  373. const roaring64_bitmap_t *r2);
  374. /**
  375. * In-place version of `roaring64_bitmap_xor()`, modifies `r1`. `r1` and `r2`
  376. * are not allowed to be equal (that would result in an empty bitmap).
  377. */
  378. void roaring64_bitmap_xor_inplace(roaring64_bitmap_t *r1,
  379. const roaring64_bitmap_t *r2);
  380. /**
  381. * Computes the difference (andnot) between two bitmaps and returns a new
  382. * bitmap. The caller is responsible for free-ing the result.
  383. */
  384. roaring64_bitmap_t *roaring64_bitmap_andnot(const roaring64_bitmap_t *r1,
  385. const roaring64_bitmap_t *r2);
  386. /**
  387. * Computes the size of the difference (andnot) between two bitmaps.
  388. */
  389. uint64_t roaring64_bitmap_andnot_cardinality(const roaring64_bitmap_t *r1,
  390. const roaring64_bitmap_t *r2);
  391. /**
  392. * In-place version of `roaring64_bitmap_andnot()`, modifies `r1`. `r1` and `r2`
  393. * are not allowed to be equal (that would result in an empty bitmap).
  394. */
  395. void roaring64_bitmap_andnot_inplace(roaring64_bitmap_t *r1,
  396. const roaring64_bitmap_t *r2);
  397. /**
  398. * Compute the negation of the bitmap in the interval [min, max).
  399. * The number of negated values is `max - min`. Areas outside the range are
  400. * passed through unchanged.
  401. */
  402. roaring64_bitmap_t *roaring64_bitmap_flip(const roaring64_bitmap_t *r,
  403. uint64_t min, uint64_t max);
  404. /**
  405. * Compute the negation of the bitmap in the interval [min, max].
  406. * The number of negated values is `max - min + 1`. Areas outside the range are
  407. * passed through unchanged.
  408. */
  409. roaring64_bitmap_t *roaring64_bitmap_flip_closed(const roaring64_bitmap_t *r,
  410. uint64_t min, uint64_t max);
  411. /**
  412. * In-place version of `roaring64_bitmap_flip`. Compute the negation of the
  413. * bitmap in the interval [min, max). The number of negated values is `max -
  414. * min`. Areas outside the range are passed through unchanged.
  415. */
  416. void roaring64_bitmap_flip_inplace(roaring64_bitmap_t *r, uint64_t min,
  417. uint64_t max);
  418. /**
  419. * In-place version of `roaring64_bitmap_flip_closed`. Compute the negation of
  420. * the bitmap in the interval [min, max]. The number of negated values is `max -
  421. * min + 1`. Areas outside the range are passed through unchanged.
  422. */
  423. void roaring64_bitmap_flip_closed_inplace(roaring64_bitmap_t *r, uint64_t min,
  424. uint64_t max);
  425. /**
  426. * How many bytes are required to serialize this bitmap.
  427. *
  428. * This is meant to be compatible with other languages:
  429. * https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
  430. */
  431. size_t roaring64_bitmap_portable_size_in_bytes(const roaring64_bitmap_t *r);
  432. /**
  433. * Write a bitmap to a buffer. The output buffer should refer to at least
  434. * `roaring64_bitmap_portable_size_in_bytes(r)` bytes of allocated memory.
  435. *
  436. * Returns how many bytes were written, which should match
  437. * `roaring64_bitmap_portable_size_in_bytes(r)`.
  438. *
  439. * This is meant to be compatible with other languages:
  440. * https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
  441. *
  442. * This function is endian-sensitive. If you have a big-endian system (e.g., a
  443. * mainframe IBM s390x), the data format is going to be big-endian and not
  444. * compatible with little-endian systems.
  445. */
  446. size_t roaring64_bitmap_portable_serialize(const roaring64_bitmap_t *r,
  447. char *buf);
  448. /**
  449. * Check how many bytes would be read (up to maxbytes) at this pointer if there
  450. * is a valid bitmap, returns zero if there is no valid bitmap.
  451. *
  452. * This is meant to be compatible with other languages
  453. * https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
  454. */
  455. size_t roaring64_bitmap_portable_deserialize_size(const char *buf,
  456. size_t maxbytes);
  457. /**
  458. * Read a bitmap from a serialized buffer safely (reading up to maxbytes).
  459. * In case of failure, NULL is returned.
  460. *
  461. * This is meant to be compatible with other languages
  462. * https://github.com/RoaringBitmap/RoaringFormatSpec#extension-for-64-bit-implementations
  463. *
  464. * The function itself is safe in the sense that it will not cause buffer
  465. * overflows. However, for correct operations, it is assumed that the bitmap
  466. * read was once serialized from a valid bitmap (i.e., it follows the format
  467. * specification). If you provided an incorrect input (garbage), then the bitmap
  468. * read may not be in a valid state and following operations may not lead to
  469. * sensible results. In particular, the serialized array containers need to be
  470. * in sorted order, and the run containers should be in sorted non-overlapping
  471. * order. This is is guaranteed to happen when serializing an existing bitmap,
  472. * but not for random inputs.
  473. *
  474. * This function is endian-sensitive. If you have a big-endian system (e.g., a
  475. * mainframe IBM s390x), the data format is going to be big-endian and not
  476. * compatible with little-endian systems.
  477. */
  478. roaring64_bitmap_t *roaring64_bitmap_portable_deserialize_safe(const char *buf,
  479. size_t maxbytes);
  480. /**
  481. * Iterate over the bitmap elements. The function `iterator` is called once for
  482. * all the values with `ptr` (can be NULL) as the second parameter of each call.
  483. *
  484. * `roaring_iterator64` is simply a pointer to a function that returns a bool
  485. * and takes `(uint64_t, void*)` as inputs. True means that the iteration should
  486. * continue, while false means that it should stop.
  487. *
  488. * Returns true if the `roaring64_iterator` returned true throughout (so that
  489. * all data points were necessarily visited).
  490. *
  491. * Iteration is ordered from the smallest to the largest elements.
  492. */
  493. bool roaring64_bitmap_iterate(const roaring64_bitmap_t *r,
  494. roaring_iterator64 iterator, void *ptr);
  495. /**
  496. * Convert the bitmap to a sorted array `out`.
  497. *
  498. * Caller is responsible to ensure that there is enough memory allocated, e.g.
  499. * ```
  500. * out = malloc(roaring64_bitmap_get_cardinality(bitmap) * sizeof(uint64_t));
  501. * ```
  502. */
  503. void roaring64_bitmap_to_uint64_array(const roaring64_bitmap_t *r,
  504. uint64_t *out);
  505. /**
  506. * Create an iterator object that can be used to iterate through the values.
  507. * Caller is responsible for calling `roaring64_iterator_free()`.
  508. *
  509. * The iterator is initialized. If there is a value, then this iterator points
  510. * to the first value and `roaring64_iterator_has_value()` returns true. The
  511. * value can be retrieved with `roaring64_iterator_value()`.
  512. */
  513. roaring64_iterator_t *roaring64_iterator_create(const roaring64_bitmap_t *r);
  514. /**
  515. * Create an iterator object that can be used to iterate through the values.
  516. * Caller is responsible for calling `roaring64_iterator_free()`.
  517. *
  518. * The iterator is initialized. If there is a value, then this iterator points
  519. * to the last value and `roaring64_iterator_has_value()` returns true. The
  520. * value can be retrieved with `roaring64_iterator_value()`.
  521. */
  522. roaring64_iterator_t *roaring64_iterator_create_last(
  523. const roaring64_bitmap_t *r);
  524. /**
  525. * Re-initializes an existing iterator. Functionally the same as
  526. * `roaring64_iterator_create` without a allocation.
  527. */
  528. void roaring64_iterator_reinit(const roaring64_bitmap_t *r,
  529. roaring64_iterator_t *it);
  530. /**
  531. * Re-initializes an existing iterator. Functionally the same as
  532. * `roaring64_iterator_create_last` without a allocation.
  533. */
  534. void roaring64_iterator_reinit_last(const roaring64_bitmap_t *r,
  535. roaring64_iterator_t *it);
  536. /**
  537. * Creates a copy of the iterator. Caller is responsible for calling
  538. * `roaring64_iterator_free()` on the resulting iterator.
  539. */
  540. roaring64_iterator_t *roaring64_iterator_copy(const roaring64_iterator_t *it);
  541. /**
  542. * Free the iterator.
  543. */
  544. void roaring64_iterator_free(roaring64_iterator_t *it);
  545. /**
  546. * Returns true if the iterator currently points to a value. If so, calling
  547. * `roaring64_iterator_value()` returns the value.
  548. */
  549. bool roaring64_iterator_has_value(const roaring64_iterator_t *it);
  550. /**
  551. * Returns the value the iterator currently points to. Should only be called if
  552. * `roaring64_iterator_has_value()` returns true.
  553. */
  554. uint64_t roaring64_iterator_value(const roaring64_iterator_t *it);
  555. /**
  556. * Advance the iterator. If there is a new value, then
  557. * `roaring64_iterator_has_value()` returns true. Values are traversed in
  558. * increasing order. For convenience, returns the result of
  559. * `roaring64_iterator_has_value()`.
  560. *
  561. * Once this returns false, `roaring64_iterator_advance` should not be called on
  562. * the iterator again. Calling `roaring64_iterator_previous` is allowed.
  563. */
  564. bool roaring64_iterator_advance(roaring64_iterator_t *it);
  565. /**
  566. * Decrement the iterator. If there is a new value, then
  567. * `roaring64_iterator_has_value()` returns true. Values are traversed in
  568. * decreasing order. For convenience, returns the result of
  569. * `roaring64_iterator_has_value()`.
  570. *
  571. * Once this returns false, `roaring64_iterator_previous` should not be called
  572. * on the iterator again. Calling `roaring64_iterator_advance` is allowed.
  573. */
  574. bool roaring64_iterator_previous(roaring64_iterator_t *it);
  575. /**
  576. * Move the iterator to the first value greater than or equal to `val`, if it
  577. * exists at or after the current position of the iterator. If there is a new
  578. * value, then `roaring64_iterator_has_value()` returns true. Values are
  579. * traversed in increasing order. For convenience, returns the result of
  580. * `roaring64_iterator_has_value()`.
  581. */
  582. bool roaring64_iterator_move_equalorlarger(roaring64_iterator_t *it,
  583. uint64_t val);
  584. /**
  585. * Reads up to `count` values from the iterator into the given `buf`. Returns
  586. * the number of elements read. The number of elements read can be smaller than
  587. * `count`, which means that there are no more elements in the bitmap.
  588. *
  589. * This function can be used together with other iterator functions.
  590. */
  591. uint64_t roaring64_iterator_read(roaring64_iterator_t *it, uint64_t *buf,
  592. uint64_t count);
  593. #ifdef __cplusplus
  594. } // extern "C"
  595. } // namespace roaring
  596. } // namespace api
  597. #endif
  598. #endif /* ROARING64_H */