X-Git-Url: http://git.madism.org/?a=blobdiff_plain;f=common%2Ftrie.c;h=cb39cb205bcc486d0a9ccdef849d474d6a91273b;hb=4c821f0852e962886a47f9227d422050f378c6fd;hp=9ffa9b54eb1e4c01d16927360a37a9afdf898087;hpb=d66ec885e2c3680b1b42e5cf99b18865c6c1736c;p=apps%2Fpfixtools.git diff --git a/common/trie.c b/common/trie.c index 9ffa9b5..cb39cb2 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,20 +40,20 @@ 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) struct trie_t { - trie_entry_t_array_t entries; - char_array_t c; - char_array_t keys; - int_array_t keys_offset; + A(trie_entry_t) entries; + A(char) c; + A(char) keys; + A(int) keys_offset; bool locked; }; @@ -110,6 +108,12 @@ 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) +{ + return !!(strncmp(array_ptr(trie->c, entry->c_offset), key, entry->c_len) == 0); +} + static inline bool trie_entry_is_leaf(const trie_entry_t *entry) { return entry->children_len == 0; @@ -148,14 +152,14 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie, 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 +171,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 +186,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 +216,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 +246,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); @@ -299,18 +303,43 @@ bool trie_lookup(const trie_t *trie, const char *key) } } +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 { + trie_entry_t *current = array_ptr(trie->entries, 0); + while (true) { + int pos = 0; + if (trie_entry_is_leaf(current)) { + return trie_entry_prefix(trie, current, key); + } else if (trie_entry_c_match(trie, current, key, &pos)) { + key += pos; + current = trie_entry_child(trie, current, key); + if (current == NULL) { + return false; + } + } else { + return false; + } + } + } +} + 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 +350,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; } @@ -362,7 +392,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); }