Adds a rank-select data structure, see #14

tinygraph · Jun 27, 2024 · 0be8dd3 · 0be8dd3
1 parent a472101
commit 0be8dd3
Show file tree

Hide file tree

Showing 6 changed files with 437 additions and 4 deletions.
diff --git a/tinygraph/tinygraph-bits.c b/tinygraph/tinygraph-bits.c
@@ -192,7 +192,7 @@ uint32_t tinygraph_bits_select_512(const uint64_t *p, uint32_t n) {
   uint32_t count = 0;
 
   for (uint32_t i = 0; i < 7; ++i) {
-    uint32_t block = tinygraph_bits_count(p[i]);
+    const uint32_t block = tinygraph_bits_count(p[i]);
 
     if ((count + block) > n) {
       return i * 64 + tinygraph_bits_select(p[i], n - count);

diff --git a/tinygraph/tinygraph-bitset.c b/tinygraph/tinygraph-bitset.c
@@ -3,6 +3,7 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "tinygraph-align.h"
 #include "tinygraph-utils.h"
 #include "tinygraph-bitset.h"
 
@@ -33,14 +34,16 @@ tinygraph_bitset* tinygraph_bitset_construct(uint64_t size) {
 
   uint64_t num_blocks = ceil(size / 64.f);
 
-  uint64_t *blocks = calloc(num_blocks, sizeof(uint64_t));
+  uint64_t *blocks = tinygraph_align_malloc(64, num_blocks * sizeof(uint64_t));
 
   if (!blocks) {
     free(out);
 
     return NULL;
   }
 
+  memset(blocks, 0, num_blocks * sizeof(uint64_t));
+
   out->blocks = blocks;
   out->blocks_len = num_blocks;
 
@@ -53,12 +56,13 @@ tinygraph_bitset* tinygraph_bitset_copy(const tinygraph_bitset * const bitset) {
     return NULL;
   }
 
-  tinygraph_bitset *copy = tinygraph_bitset_construct(bitset->blocks_len);
+  tinygraph_bitset *copy = tinygraph_bitset_construct(bitset->size);
 
   if (!copy) {
     return NULL;
   }
 
+  TINYGRAPH_ASSERT(copy->size == bitset->size);
   TINYGRAPH_ASSERT(copy->blocks_len == bitset->blocks_len);
 
   if (bitset->blocks_len > 0) {
@@ -79,7 +83,7 @@ void tinygraph_bitset_destruct(tinygraph_bitset * const bitset) {
 
   TINYGRAPH_ASSERT(bitset->blocks || bitset->blocks_len == 0);
 
-  free(bitset->blocks);
+  tinygraph_align_free(bitset->blocks);
 
   bitset->blocks = NULL;
   bitset->blocks_len = 0;
@@ -91,6 +95,7 @@ void tinygraph_bitset_destruct(tinygraph_bitset * const bitset) {
 void tinygraph_bitset_set_at(tinygraph_bitset * const bitset, uint64_t i) {
   TINYGRAPH_ASSERT(bitset);
   TINYGRAPH_ASSERT(bitset->blocks_len > 0);
+  TINYGRAPH_ASSERT(i < bitset->size);
   TINYGRAPH_ASSERT((i >> 6) < bitset->blocks_len);
 
   bitset->blocks[i >> 6] |= (UINT64_C(1) << (i & UINT64_C(63)));
@@ -100,6 +105,7 @@ void tinygraph_bitset_set_at(tinygraph_bitset * const bitset, uint64_t i) {
 bool tinygraph_bitset_get_at(const tinygraph_bitset * const bitset, uint64_t i) {
   TINYGRAPH_ASSERT(bitset);
   TINYGRAPH_ASSERT(bitset->blocks_len > 0);
+  TINYGRAPH_ASSERT(i < bitset->size);
   TINYGRAPH_ASSERT((i >> 6) < bitset->blocks_len);
 
   return (bitset->blocks[i >> 6] & (UINT64_C(1) << (i & UINT64_C(63)))) != 0;
@@ -124,6 +130,13 @@ void tinygraph_bitset_clear(tinygraph_bitset * const bitset) {
 }
 
 
+const uint64_t * tinygraph_bitset_get_data(const tinygraph_bitset * const bitset) {
+  TINYGRAPH_ASSERT(bitset);
+
+  return bitset->blocks;
+}
+
+
 void tinygraph_bitset_not(tinygraph_bitset * const bitset) {
   TINYGRAPH_ASSERT(bitset);
 

diff --git a/tinygraph/tinygraph-bitset.h b/tinygraph/tinygraph-bitset.h
@@ -36,6 +36,9 @@ uint64_t tinygraph_bitset_get_size(tinygraph_bitset_const_s bitset);
 
 void tinygraph_bitset_clear(tinygraph_bitset_s bitset);
 
+TINYGRAPH_WARN_UNUSED
+const uint64_t * tinygraph_bitset_get_data(tinygraph_bitset_const_s bitset);
+
 void tinygraph_bitset_not(tinygraph_bitset_s bitset);
 void tinygraph_bitset_and(tinygraph_bitset_s bitset, tinygraph_bitset_const_s other);
 void tinygraph_bitset_or(tinygraph_bitset_s bitset, tinygraph_bitset_const_s other);