summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-05-16 11:01:25 -0400
committerTavian Barnes <tavianator@tavianator.com>2023-05-16 11:29:48 -0400
commit8302f1d0441b3105470426105b3031961e066535 (patch)
tree01cc7826eb6116faedeca395755babfd85c6bc1c /src
parentc860ad15979ac0cc6060529aa2027b2724825ca0 (diff)
downloadbfs-8302f1d0441b3105470426105b3031961e066535.tar.xz
trie: Use standard bit utilities
Diffstat (limited to 'src')
-rw-r--r--src/trie.c59
1 files changed, 15 insertions, 44 deletions
diff --git a/src/trie.c b/src/trie.c
index 02d1ae9..2226890 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -168,25 +168,6 @@ void trie_init(struct trie *trie) {
LIST_INIT(trie);
}
-/** Check if a number is a power of two. */
-static bool is_power_of_two(size_t n) {
- return (n & (n - 1)) == 0;
-}
-
-/** Compute the popcount (Hamming weight) of a bitmap. */
-static unsigned int trie_popcount(unsigned int n) {
-#if __GNUC__
- return __builtin_popcount(n);
-#else
- // See https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
- n -= (n >> 1) & 0x5555;
- n = (n & 0x3333) + ((n >> 2) & 0x3333);
- n = (n + (n >> 4)) & 0x0F0F;
- n = (n + (n >> 8)) & 0xFF;
- return n;
-#endif
-}
-
/** Extract the nibble at a certain offset from a byte sequence. */
static unsigned char trie_key_nibble(const void *key, size_t offset) {
const unsigned char *bytes = key;
@@ -226,7 +207,7 @@ static struct trie_leaf *trie_representative(const struct trie *trie, const void
unsigned char nibble = trie_key_nibble(key, offset);
unsigned int bit = 1U << nibble;
if (node->bitmap & bit) {
- index = trie_popcount(node->bitmap & (bit - 1));
+ index = count_ones(node->bitmap & (bit - 1));
}
}
ptr = node->children[index];
@@ -316,7 +297,7 @@ static struct trie_leaf *trie_find_prefix_impl(const struct trie *trie, const ch
unsigned char nibble = trie_key_nibble(key, offset);
unsigned int bit = 1U << nibble;
if (node->bitmap & bit) {
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
+ unsigned int index = count_ones(node->bitmap & (bit - 1));
ptr = node->children[index];
} else {
return best;
@@ -362,7 +343,7 @@ static size_t trie_node_size(unsigned int size) {
// Empty nodes aren't supported
assert(size > 0);
// Node size must be a power of two
- assert(is_power_of_two(size));
+ assert(has_single_bit(size));
return flex_sizeof(struct trie_node, children, size);
}
@@ -373,16 +354,6 @@ static size_t trie_node_size(unsigned int size) {
# define TRIE_BSWAP(n) bswap(n)
#endif
-#ifdef TRIE_BSWAP
-# if SIZE_WIDTH == LLONG_WIDTH
-# define TRIE_CTZ(n) __builtin_ctzll(n)
-# elif SiZE_WIDTH == LONG_WIDTH
-# define TRIE_CTZ(n) __builtin_ctzl(n)
-# elif SIZE_WIDTH == INT_WIDTH
-# define TRIE_CTZ(n) __builtin_ctz(n)
-# endif
-#endif
-
/** Find the offset of the first nibble that differs between two keys. */
static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t length) {
if (!rep) {
@@ -403,10 +374,10 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t
memcpy(&key_chunk, key_bytes + i, sizeof(key_chunk));
if (rep_chunk != key_chunk) {
-#ifdef TRIE_CTZ
+#ifdef TRIE_BSWAP
size_t diff = TRIE_BSWAP(rep_chunk ^ key_chunk);
i *= 2;
- i += TRIE_CTZ(diff) / 4;
+ i += trailing_zeros(diff) / 4;
return i;
#else
break;
@@ -449,10 +420,10 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t
TARGET_CLONES_POPCNT
static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, struct trie_leaf *leaf, unsigned char nibble) {
struct trie_node *node = trie_decode_node(*ptr);
- unsigned int size = trie_popcount(node->bitmap);
+ unsigned int size = count_ones(node->bitmap);
// Double the capacity every power of two
- if (is_power_of_two(size)) {
+ if (has_single_bit(size)) {
node = realloc(node, trie_node_size(2 * size));
if (!node) {
trie_leaf_free(trie, leaf);
@@ -467,7 +438,7 @@ static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, str
assert(!(node->bitmap & bit));
node->bitmap |= bit;
- unsigned int target = trie_popcount(node->bitmap & (bit - 1));
+ unsigned int target = count_ones(node->bitmap & (bit - 1));
for (size_t i = size; i > target; --i) {
node->children[i] = node->children[i - 1];
}
@@ -600,7 +571,7 @@ static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key
unsigned int bit = 1U << nibble;
if (node->bitmap & bit) {
assert(offset < mismatch);
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
+ unsigned int index = count_ones(node->bitmap & (bit - 1));
ptr = &node->children[index];
} else {
assert(offset == mismatch);
@@ -629,7 +600,7 @@ static void trie_free_singletons(struct trie *trie, uintptr_t ptr) {
struct trie_node *node = trie_decode_node(ptr);
// Make sure the bitmap is a power of two, i.e. it has just one child
- assert(is_power_of_two(node->bitmap));
+ assert(has_single_bit(node->bitmap));
ptr = node->children[0];
free(node);
@@ -686,10 +657,10 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
unsigned int bit = 1U << nibble;
unsigned int bitmap = node->bitmap;
assert(bitmap & bit);
- unsigned int index = trie_popcount(bitmap & (bit - 1));
+ unsigned int index = count_ones(bitmap & (bit - 1));
// Advance the parent pointer, unless this node had only one child
- if (!is_power_of_two(bitmap)) {
+ if (!has_single_bit(bitmap)) {
parent = child;
child_bit = bit;
child_index = index;
@@ -711,7 +682,7 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
trie_free_singletons(trie, *child);
node->bitmap ^= child_bit;
- unsigned int parent_size = trie_popcount(node->bitmap);
+ unsigned int parent_size = count_ones(node->bitmap);
assert(parent_size > 0);
if (parent_size == 1 && trie_collapse_node(parent, node, child_index) == 0) {
return;
@@ -721,7 +692,7 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
memmove(child, child + 1, (parent_size - child_index)*sizeof(*child));
}
- if (is_power_of_two(parent_size)) {
+ if (has_single_bit(parent_size)) {
node = realloc(node, trie_node_size(parent_size));
if (node) {
*parent = trie_encode_node(node);
@@ -740,7 +711,7 @@ static void free_trie_ptr(uintptr_t ptr) {
free(trie_decode_leaf(ptr));
} else {
struct trie_node *node = trie_decode_node(ptr);
- size_t size = trie_popcount(node->bitmap);
+ size_t size = count_ones(node->bitmap);
for (size_t i = 0; i < size; ++i) {
free_trie_ptr(node->children[i]);
}