From 74f388a893add09ba6a1e35151e0d2600cd688cb Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 23 Mar 2024 10:21:44 -0400 Subject: trie: Calculate representative indices branchlessly --- src/trie.c | 7 ++++--- 1 file 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]; } -- cgit v1.2.3