summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/trie.c34
1 files changed, 28 insertions, 6 deletions
diff --git a/src/trie.c b/src/trie.c
index 3e3d84e..f6cea7b 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -103,6 +103,12 @@
#include <stdlib.h>
#include <string.h>
+#if __GNUC__ && (__i386__ || __x86_64__)
+# define TARGET_CLONES_POPCNT __attribute__((target_clones("popcnt", "default")))
+#else
+# define TARGET_CLONES_POPCNT
+#endif
+
#if CHAR_BIT != 8
# error "This trie implementation assumes 8-bit bytes."
#endif
@@ -183,9 +189,7 @@ static bool is_power_of_two(size_t n) {
/** Compute the popcount (Hamming weight) of a bitmap. */
static unsigned int trie_popcount(unsigned int n) {
-#if __POPCNT__
- // Use the x86 instruction if we have it. Otherwise, GCC generates a
- // library call, so use the below implementation instead.
+#if __GNUC__
return __builtin_popcount(n);
#else
// See https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
@@ -219,6 +223,7 @@ static unsigned char trie_key_nibble(const void *key, size_t offset) {
* that case, the first mismatch between the key and the representative will be
* the depth at which to make a new branch to insert the key.
*/
+TARGET_CLONES_POPCNT
static struct trie_leaf *trie_representative(const struct trie *trie, const void *key, size_t length) {
uintptr_t ptr = trie->root;
if (!ptr) {
@@ -297,7 +302,8 @@ static bool trie_check_prefix(struct trie_leaf *leaf, size_t skip, const char *k
}
}
-struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
+TARGET_CLONES_POPCNT
+static struct trie_leaf *trie_find_prefix_impl(const struct trie *trie, const char *key) {
uintptr_t ptr = trie->root;
if (!ptr) {
return NULL;
@@ -339,6 +345,10 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
return best;
}
+struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
+ return trie_find_prefix_impl(trie, key);
+}
+
/** Create a new leaf, holding a copy of the given key. */
static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, size_t length) {
struct trie_leaf *leaf = malloc(BFS_FLEX_SIZEOF(struct trie_leaf, key, length));
@@ -447,6 +457,7 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t
* | Z
* +--->...
*/
+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);
@@ -569,7 +580,8 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key) {
return trie_insert_mem(trie, key, strlen(key) + 1);
}
-struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length) {
+TARGET_CLONES_POPCNT
+static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key, size_t length) {
struct trie_leaf *rep = trie_representative(trie, key, length);
size_t mismatch = trie_mismatch(rep, key, length);
if (mismatch >= (length << 1)) {
@@ -618,6 +630,10 @@ struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t len
return trie_split(trie, ptr, leaf, rep, offset, mismatch);
}
+struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length) {
+ return trie_insert_mem_impl(trie, key, length);
+}
+
/** Free a chain of singleton nodes. */
static void trie_free_singletons(struct trie *trie, uintptr_t ptr) {
while (!trie_is_leaf(ptr)) {
@@ -666,7 +682,8 @@ static int trie_collapse_node(uintptr_t *parent, struct trie_node *parent_node,
return 0;
}
-void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
+TARGET_CLONES_POPCNT
+static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
uintptr_t *child = &trie->root;
uintptr_t *parent = NULL;
unsigned int child_bit = 0, child_index = 0;
@@ -723,7 +740,12 @@ void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
}
}
+void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
+ trie_remove_impl(trie, leaf);
+}
+
/** Free an encoded pointer to a node. */
+TARGET_CLONES_POPCNT
static void free_trie_ptr(uintptr_t ptr) {
if (trie_is_leaf(ptr)) {
free(trie_decode_leaf(ptr));