1 module roaring.c; 2 3 import core.stdc.inttypes: uint8_t, uint16_t, int32_t, uint32_t, uint64_t; 4 5 extern(C): 6 7 struct roaring_array_t { 8 int32_t size; 9 int32_t allocation_size; 10 void **containers; 11 uint16_t *keys; 12 uint8_t *typecodes; 13 } 14 15 struct roaring_bitmap_t { 16 roaring_array_t high_low_container; 17 bool copy_on_write; 18 } 19 20 struct roaring_uint32_iterator_t { 21 const roaring_bitmap_t *parent; // owner 22 int32_t container_index; // point to the current container index 23 int32_t in_container_index; // for bitset and array container, this is out 24 // index 25 int32_t run_index; // for run container, this points at the run 26 uint32_t in_run_index; // within a run, this is our index (points at the 27 // end of the current run) 28 29 uint32_t current_value; 30 bool has_value; 31 32 const void *container; // should be: 33 // parent->high_low_container.containers[container_index]; 34 uint8_t typecode; // should be: 35 // parent->high_low_container.typecodes[container_index]; 36 uint32_t highbits; // should be: 37 // parent->high_low_container.keys[container_index]) << 38 // 16; 39 } 40 41 extern(C) alias roaring_iterator = bool function(uint32_t value, void* param); 42 43 @nogc @safe 44 void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x); 45 46 /** 47 * Add value n_args from pointer vals, faster than repeatedly calling 48 * roaring_bitmap_add 49 * 50 */ 51 void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args, const uint32_t *vals); 52 53 /** 54 * Computes the intersection between two bitmaps and returns new bitmap. The 55 * caller is 56 * responsible for memory management. 57 * 58 */ 59 roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *x1, const roaring_bitmap_t *x2); 60 61 @nogc @safe 62 bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) pure; 63 roaring_bitmap_t *roaring_bitmap_create(); 64 roaring_bitmap_t *roaring_bitmap_create_with_capacity(uint32_t cap); 65 66 /** 67 * Return true if all the elements of ra1 are also in ra2. 68 */ 69 bool roaring_bitmap_is_subset(const roaring_bitmap_t *ra1, const roaring_bitmap_t *ra2); 70 71 72 /** use with roaring_bitmap_serialize 73 * see roaring_bitmap_portable_deserialize if you want a format that's 74 * compatible with Java and Go implementations 75 */ 76 roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf); 77 78 /** 79 * read a bitmap from a serialized version. This is meant to be compatible with 80 * the Java and Go versions. See format specification at 81 * https://github.com/RoaringBitmap/RoaringFormatSpec 82 * In case of failure, a null pointer is returned. 83 * This function is unsafe in the sense that if there is no valid serialized 84 * bitmap at the pointer, then many bytes could be read, possibly causing a buffer 85 * overflow. For a safer approach, 86 * call roaring_bitmap_portable_deserialize_safe. 87 */ 88 roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf); 89 90 /** 91 * read a bitmap from a serialized version in a safe manner (reading up to maxbytes). 92 * This is meant to be compatible with 93 * the Java and Go versions. See format specification at 94 * https://github.com/RoaringBitmap/RoaringFormatSpec 95 * In case of failure, a null pointer is returned. 96 */ 97 roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes); 98 99 /** 100 * Check how many bytes would be read (up to maxbytes) at this pointer if there 101 * is a bitmap, returns zero if there is no valid bitmap. 102 * This is meant to be compatible with 103 * the Java and Go versions. See format specification at 104 * https://github.com/RoaringBitmap/RoaringFormatSpec 105 */ 106 size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes); 107 108 /** 109 * Return true if the two bitmaps contain the same elements. 110 */ 111 bool roaring_bitmap_equals(const roaring_bitmap_t *ra1, const roaring_bitmap_t *ra2); 112 113 void roaring_bitmap_free(roaring_bitmap_t *r); 114 roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max, uint32_t step); 115 116 @nogc @safe 117 uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *ra) pure; 118 119 @nogc @safe 120 uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *bm) pure; 121 122 @nogc @safe 123 uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *bm) pure; 124 125 /** 126 * Computes the union between two bitmaps and returns new bitmap. The caller is 127 * responsible for memory management. 128 */ 129 roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *x1, const roaring_bitmap_t *x2); 130 131 /** 132 * roaring_bitmap_rank returns the number of integers that are smaller or equal 133 * to x. 134 */ 135 @nogc @safe 136 uint64_t roaring_bitmap_rank(const roaring_bitmap_t *bm, uint32_t x) pure; 137 138 /** 139 * write a bitmap to a char buffer. The output buffer should refer to at least 140 * roaring_bitmap_portable_size_in_bytes(ra) bytes of allocated memory. 141 * This is meant to be compatible with 142 * the 143 * Java and Go versions. Returns how many bytes were written which should be 144 * roaring_bitmap_portable_size_in_bytes(ra). See format specification at 145 * https://github.com/RoaringBitmap/RoaringFormatSpec 146 */ 147 size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *ra, char *buf); 148 149 /** 150 * How many bytes are required to serialize this bitmap (meant to be compatible 151 * with Java and Go versions). See format specification at 152 * https://github.com/RoaringBitmap/RoaringFormatSpec 153 */ 154 @nogc @safe 155 size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *ra) pure; 156 157 @nogc @safe 158 void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x); 159 160 @nogc @safe 161 bool roaring_bitmap_run_optimize(roaring_bitmap_t *r); 162 163 bool roaring_bitmap_select(const roaring_bitmap_t *bm, uint32_t rank, uint32_t *element); 164 165 /** 166 * write the bitmap to an output pointer, this output buffer should refer to 167 * at least roaring_bitmap_size_in_bytes(ra) allocated bytes. 168 * 169 * see roaring_bitmap_portable_serialize if you want a format that's compatible 170 * with Java and Go implementations 171 * 172 * this format has the benefit of being sometimes more space efficient than 173 * roaring_bitmap_portable_serialize 174 * e.g., when the data is sparse. 175 * 176 * Returns how many bytes were written which should be 177 * roaring_bitmap_size_in_bytes(ra). 178 */ 179 size_t roaring_bitmap_serialize(const roaring_bitmap_t *ra, char *buf); 180 181 /** 182 * How many bytes are required to serialize this bitmap (NOT compatible 183 * with Java and Go versions) 184 */ 185 @nogc @safe 186 size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *ra) pure; 187 188 /** 189 * Convert the bitmap to an array. Write the output to "ans", 190 * caller is responsible to ensure that there is enough memory 191 * allocated 192 * (e.g., ans = malloc(roaring_bitmap_get_cardinality(mybitmap) 193 * * sizeof(uint32_t)) ) 194 */ 195 void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *ra, uint32_t *ans); 196 197 /** 198 * Advance the iterator. If there is a new value, then it->has_value is true. 199 * The new value is in it->current_value. Values are traversed in increasing 200 * orders. For convenience, returns it->has_value. 201 */ 202 @nogc 203 bool roaring_advance_uint32_iterator(roaring_uint32_iterator_t *it); 204 205 /** 206 * Create an iterator object that can be used to iterate through the 207 * values. Caller is responsible for calling roaring_free_iterator. 208 * The iterator is initialized. If there is a value, then it->has_value is true. 209 * The first value is in it->current_value. The iterator traverses the values 210 * in increasing order. 211 * 212 * This function calls roaring_init_iterator. 213 */ 214 @nogc 215 roaring_uint32_iterator_t *roaring_create_iterator(const roaring_bitmap_t *ra); 216 217 /** 218 * Free memory following roaring_create_iterator 219 */ 220 @nogc 221 void roaring_free_uint32_iterator(roaring_uint32_iterator_t *it);