X-Git-Url: http://git.madism.org/?p=apps%2Fpfixtools.git;a=blobdiff_plain;f=common%2Ftrie.c;h=f16f0a64d7f24255c9d116b31728e39254303375;hp=5bf18ecd848a82d313c19f15694b3e100b9cfdf5;hb=ab82546953101224d09dcf2e44ff170e454e7282;hpb=00bae73b4873e9c1e8d5526feecdb275f7bb756f diff --git a/common/trie.c b/common/trie.c index 5bf18ec..f16f0a6 100644 --- a/common/trie.c +++ b/common/trie.c @@ -33,8 +33,6 @@ * Copyright © 2008 Florent Bruneau */ -#include - #include "array.h" #include "str.h" #include "trie.h" @@ -42,11 +40,11 @@ typedef struct trie_entry_t trie_entry_t; struct trie_entry_t { - int32_t c_offset; - int32_t c_len; + uint32_t c_offset; + uint32_t children_offset; - int32_t children_offset; - int32_t children_len; + uint16_t c_len; + uint16_t children_len; }; #define TRIE_ENTRY_INIT { 0, 0, 0, 0 } ARRAY(trie_entry_t) @@ -86,21 +84,15 @@ void trie_delete(trie_t **trie) */ static inline bool trie_entry_c_match(const trie_t *trie, const trie_entry_t *entry, - const char *key, int *pos) + const char *key) { const char *c = array_ptr(trie->c, entry->c_offset); int i = 0; for (i = 0 ; i < entry->c_len ; ++i) { if (key[i] != c[i]) { - if (pos) { - *pos = i; - } return false; } } - if (pos) { - *pos = i; - } return true; } @@ -110,6 +102,16 @@ static inline bool trie_entry_match(const trie_t *trie, return !!(strcmp(array_ptr(trie->c, entry->c_offset), key) == 0); } +static inline bool trie_entry_prefix(const trie_t *trie, + const trie_entry_t *entry, const char *key) +{ + int len = entry->c_len; + if (len > 0 && array_elt(trie->c, entry->c_offset + len - 1) == '\0') { + --len; + } + return !!(strncmp(array_ptr(trie->c, entry->c_offset), key, len) == 0); +} + static inline bool trie_entry_is_leaf(const trie_entry_t *entry) { return entry->children_len == 0; @@ -119,43 +121,39 @@ static inline bool trie_entry_is_leaf(const trie_entry_t *entry) * Only the first character of the children is taken into account in the * lookup. The current entry is assumed to match the key. */ -static inline trie_entry_t* trie_entry_child(const trie_t *trie, - const trie_entry_t* entry, - const char *key) +static inline const trie_entry_t* trie_entry_child(const trie_t *trie, + const trie_entry_t* entry, + const char *key) { - int start = entry->children_offset; - int end = start + entry->children_len; + uint32_t start = entry->children_offset; + uint32_t end = start + entry->children_len; const char c = *key; while (start < end) { - int mid = (start + end) / 2; - trie_entry_t* child = array_ptr(trie->entries, mid); + uint32_t mid = (start + end) >> 1; + const trie_entry_t* child = array_ptr(trie->entries, mid); const char c2 = array_elt(trie->c, child->c_offset); - if (child->c_len) { - if (c2 == c) { - return child; - } - if (c < c2) { - end = mid; - } else { - start = mid + 1; - } + if (c2 == c) { + return child; + } + if (c < c2) { + end = mid; } else { - abort(); + start = mid + 1; } } return NULL; } -static inline int trie_entry_new(trie_t *trie) +static inline uint32_t trie_entry_new(trie_t *trie) { const trie_entry_t e = TRIE_ENTRY_INIT; array_add(trie->entries, e); - return trie->entries.len; + return trie->entries.len - 1; } -static inline int trie_add_leaf(trie_t *trie, const char *key) +static inline uint32_t trie_add_leaf(trie_t *trie, const char *key) { trie_entry_t *entry; int len = m_strlen(key) + 1; @@ -167,7 +165,7 @@ static inline int trie_add_leaf(trie_t *trie, const char *key) } static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, - int pchild) + uint32_t pchild) { if (entry->children_len == 0) { entry->children_offset = pchild; @@ -182,7 +180,7 @@ static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, } } -static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos) +static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, uint16_t pos) { trie_entry_t *child; child = array_ptr(trie->entries, trie_entry_new(trie)); @@ -212,17 +210,17 @@ void trie_insert(trie_t *trie, const char* key) } -static inline void trie_compile_aux(trie_t *trie, int id, - int first_key, int last_key, int offset, - int initial_diff) +static inline void trie_compile_aux(trie_t *trie, uint32_t id, + uint32_t first_key, uint32_t last_key, + int offset, int initial_diff) { - int forks[256]; - int fork_pos = 0; + uint32_t forks[256]; + uint32_t fork_pos = 0; char current = '\0'; for (int off_diff = initial_diff ; fork_pos == 0 ; ++off_diff, ++offset) { current = array_elt(trie->keys, array_elt(trie->keys_offset, first_key) + offset); - for (int i = first_key + 1 ; i < last_key ; ++i) { + for (uint32_t i = first_key + 1 ; i < last_key ; ++i) { const char *str = array_ptr(trie->keys, array_elt(trie->keys_offset, i)); const char c = str[offset]; if (c != current) { @@ -242,8 +240,8 @@ static inline void trie_compile_aux(trie_t *trie, int id, } forks[fork_pos] = last_key; - const int children_len = array_elt(trie->entries, id).children_len; - for (int i = 0 ; i < children_len ; ++i) { + const uint8_t children_len = array_elt(trie->entries, id).children_len; + for (uint16_t i = 0 ; i < children_len ; ++i) { int child = array_elt(trie->entries, id).children_offset + i; if (forks[i] - 1 > first_key) { trie_compile_aux(trie, child, first_key, forks[i], offset, 1); @@ -281,13 +279,35 @@ bool trie_lookup(const trie_t *trie, const char *key) if (trie->entries.len == 0) { return false; } else { - trie_entry_t *current = array_ptr(trie->entries, 0); + const trie_entry_t *current = array_ptr(trie->entries, 0); while (true) { - int pos = 0; if (trie_entry_is_leaf(current)) { return trie_entry_match(trie, current, key); - } else if (trie_entry_c_match(trie, current, key, &pos)) { - key += pos; + } else if (trie_entry_c_match(trie, current, key)) { + key += current->c_len; + current = trie_entry_child(trie, current, key); + if (current == NULL) { + return false; + } + } else { + return false; + } + } + } +} + +bool trie_prefix(const trie_t *trie, const char *key) +{ + assert(trie->keys.len == 0L && "Can't lookup: trie not compiled"); + if (trie->entries.len == 0) { + return false; + } else { + const trie_entry_t *current = array_ptr(trie->entries, 0); + while (true) { + if (trie_entry_is_leaf(current)) { + return trie_entry_prefix(trie, current, key); + } else if (trie_entry_c_match(trie, current, key)) { + key += current->c_len; current = trie_entry_child(trie, current, key); if (current == NULL) { return false; @@ -304,13 +324,14 @@ void trie_lock(trie_t *trie) if (trie->locked) { return; } - if (mlock(trie->entries.data, sizeof(trie_entry_t) * trie->entries.len) != 0) { + if (!array_lock(trie->entries)) { + UNIXERR("mlock"); + } + if (!array_lock(trie->c)) { UNIXERR("mlock"); - return; } - if (mlock(trie->c.data, trie->c.len) != 0) { + if (mlock(trie, sizeof(trie_t)) != 0) { UNIXERR("mlock"); - munlock(trie->entries.data, sizeof(trie_entry_t) * trie->entries.len); return; } trie->locked = true; @@ -321,8 +342,9 @@ void trie_unlock(trie_t *trie) if (!trie->locked) { return; } - munlock(trie->entries.data, sizeof(trie_entry_t) * trie->entries.len); - munlock(trie->c.data, trie->c.len); + array_unlock(trie->entries); + array_unlock(trie->c); + munlock(trie, sizeof(trie_t)); trie->locked = false; } @@ -336,6 +358,11 @@ static inline void trie_entry_inspect(const trie_t *trie, bool show_content, static int leaves = 0; static int depth_sum = 0; + if (entry == array_ptr(trie->entries, 0)) { + max_depth = 0; + leaves = 0; + depth_sum = 0; + } if (trie_entry_is_leaf(entry)) { if (level > max_depth) { max_depth = level; @@ -362,7 +389,7 @@ static inline void trie_entry_inspect(const trie_t *trie, bool show_content, } fputs("\n", stdout); } - for (int i = entry->children_offset ; + for (uint32_t i = entry->children_offset ; i < entry->children_offset + entry->children_len ; ++i) { trie_entry_inspect(trie, show_content, array_ptr(trie->entries, i), level + 1); }