summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2024-03-23 10:21:44 -0400
committerTavian Barnes <tavianator@tavianator.com>2024-03-23 10:21:44 -0400
commit74f388a893add09ba6a1e35151e0d2600cd688cb (patch)
tree71060e420a389c715e7f0a18fd1e1667508163aa /src
parent9827b2bae1d3864dffb06b50e2f59af594154693 (diff)
downloadbfs-74f388a893add09ba6a1e35151e0d2600cd688cb.tar.xz
trie: Calculate representative indices branchlessly
Diffstat (limited to 'src')
-rw-r--r--src/trie.c7
1 files changed, 4 insertions, 3 deletions
diff --git a/src/trie.c b/src/trie.c
index 1ffb23a..f275064 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -206,9 +206,10 @@ static struct trie_leaf *trie_representative(const struct trie *trie, const void
if ((offset >> 1) < length) {
unsigned char nibble = trie_key_nibble(key, offset);
unsigned int bit = 1U << nibble;
- if (node->bitmap & bit) {
- index = count_ones(node->bitmap & (bit - 1));
- }
+ // bits = bitmap & bit ? bitmap & (bit - 1) : 0
+ unsigned int mask = -!!(node->bitmap & bit);
+ unsigned int bits = node->bitmap & (bit - 1) & mask;
+ index = count_ones(bits);
}
ptr = node->children[index];
}