From fb519b0c3a78183d3fad3778d7d57bc2693598fc Mon Sep 17 00:00:00 2001 From: Florent Bruneau Date: Thu, 11 Sep 2008 00:24:11 +0200 Subject: [PATCH] Compacter trie, reduce the number of allocations. Signed-off-by: Florent Bruneau --- common/trie.c | 123 ++++++++++++++++++++++++++++------------------ common/tst-trie.c | 2 +- 2 files changed, 76 insertions(+), 49 deletions(-) diff --git a/common/trie.c b/common/trie.c index 8504128..3cc093a 100644 --- a/common/trie.c +++ b/common/trie.c @@ -39,9 +39,8 @@ typedef struct trie_entry_t trie_entry_t; struct trie_entry_t { - char *c; + int c_offset; int c_len; - bool c_own; int* children; int children_len; @@ -51,14 +50,18 @@ struct trie_entry_t { }; struct trie_t { - trie_entry_t* entries; + trie_entry_t *entries; int entries_len; int entries_size; + char *c; + int c_len; + int c_size; + bool locked; }; -trie_t *trie_new() +trie_t *trie_new(void) { return p_new(trie_t, 1); } @@ -68,26 +71,24 @@ void trie_delete(trie_t **trie) if (*trie) { for (int i = 0 ; i < (*trie)->entries_len ; ++i) { trie_entry_t *entry = &(*trie)->entries[i]; - if (entry->c_own) { - p_delete(&entry->c); - } else { - entry->c = NULL; - } p_delete(&(entry->children)); } p_delete(&(*trie)->entries); + p_delete(&(*trie)->c); p_delete(trie); } } /** Check that the given entry is a prefix for the given key. */ -static inline bool trie_entry_c_match(const trie_entry_t* entry, +static inline bool trie_entry_c_match(const trie_t *trie, + const trie_entry_t *entry, const char *key, int *pos) { + const char *c = trie->c + entry->c_offset; int i = 0; for (i = 0 ; i < entry->c_len ; ++i) { - if (key[i] != entry->c[i]) { + if (key[i] != c[i]) { if (pos) { *pos = i; } @@ -100,6 +101,17 @@ static inline bool trie_entry_c_match(const trie_entry_t* entry, return true; } +static inline bool trie_entry_match(const trie_t *trie, + const trie_entry_t *entry, const char *key) +{ + return !!(strcmp(trie->c + entry->c_offset, key) == 0); +} + +static inline bool trie_entry_is_leaf(const trie_entry_t *entry) +{ + return entry->children_len == 0; +} + /** Lookup for a child of entry matching the given entry at the given pos. * Only the first character of the children is taken into account in the * lookup. The current entry is assumed to match the key. @@ -115,12 +127,13 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie, while (start < end) { int mid = (start + end) / 2; trie_entry_t* child = &trie->entries[entry->children[mid]]; + const char c2 = trie->c[child->c_offset]; if (child->c_len) { - if (child->c[0] == c) { + if (c2 == c) { return child; } - if (c < child->c[0]) { + if (c < c2) { end = mid; } else { start = mid + 1; @@ -132,16 +145,22 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie, return NULL; } +#define GROW(Buffer, Added, Len, Size) \ + do { \ + const int required_size = (Len) + (Added); \ + int next_size = (Size); \ + if (next_size >= required_size) { \ + break; \ + } \ + do { \ + next_size = p_alloc_nr(next_size); \ + } while (next_size < required_size); \ + p_allocgrow(&(Buffer), next_size, &(Size)); \ + } while(0) + static inline void trie_grow(trie_t *trie, int delta) { - int next_size = trie->entries_size; - if (next_size > trie->entries_len + delta) { - return; - } - do { - next_size = p_alloc_nr(next_size); - } while (trie->entries_len + delta > next_size); - p_allocgrow(&trie->entries, next_size, &trie->entries_size); + GROW(trie->entries, delta, trie->entries_len, trie->entries_size); } static inline int trie_entry_new(trie_t *trie) @@ -153,31 +172,34 @@ static inline int trie_entry_new(trie_t *trie) static inline int trie_add_leaf(trie_t *trie, const char *key) { trie_entry_t *entry; + int len = m_strlen(key) + 1; entry = &trie->entries[trie_entry_new(trie)]; - entry->c = strdup(key); /* don't use m_strdup - since m_strdup("") == NULL */ - entry->c_len = m_strlen(key) + 1; - entry->c_own = true; + GROW(trie->c, len, trie->c_len, trie->c_size); + memcpy(trie->c + trie->c_len, key, len); + entry->c_offset = trie->c_len; + entry->c_len = len; + trie->c_len += len; return trie->entries_len - 1; } static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, int pchild) { - const char c = trie->entries[pchild].c[0]; + const char c = trie->c[trie->entries[pchild].c_offset]; int start = 0; int end = entry->children_len; p_allocgrow(&entry->children, entry->children_len + 1, &entry->children_size); while (start < end) { int mid = (start + end) / 2; - trie_entry_t* child = &trie->entries[entry->children[mid]]; + const trie_entry_t* child = &trie->entries[entry->children[mid]]; + const char c2 = trie->c[child->c_offset]; if (child->c_len) { - if (child->c[0] == c) { + if (c2 == c) { abort(); } - if (c < child->c[0]) { + if (c < c2) { end = mid; } else { start = mid + 1; @@ -198,17 +220,14 @@ static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos) trie_entry_t *child; child = &trie->entries[trie_entry_new(trie)]; if (pos == 0) { - child->c = entry->c; - child->c_len = entry->c_len; - child->c_own = entry->c_own; - entry->c = NULL; - entry->c_len = 0; - entry->c_own = false; + child->c_offset = entry->c_offset; + child->c_len = entry->c_len; + entry->c_offset = 0; + entry->c_len = 0; } else { - child->c = entry->c + pos; - child->c_len = entry->c_len - pos; - child->c_own = false; - entry->c_len = pos; + child->c_offset = entry->c_offset + pos; + child->c_len = entry->c_len - pos; + entry->c_len = pos; } child->children = entry->children; child->children_len = entry->children_len; @@ -228,8 +247,8 @@ void trie_insert(trie_t *trie, const char* key) trie_entry_t *current = trie->entries; while (true) { int pos = 0; - if (trie_entry_c_match(current, key, &pos)) { - if (current->c_len && current->c[current->c_len - 1] == '\0') { + if (trie_entry_c_match(trie, current, key, &pos)) { + if (trie_entry_is_leaf(current)) { return; } trie_entry_t *next = NULL; @@ -260,10 +279,9 @@ bool trie_lookup(const trie_t *trie, const char *key) trie_entry_t *current = trie->entries; while (true) { int pos = 0; - if (trie_entry_c_match(current, key, &pos)) { - if (current->c_len && current->c[current->c_len - 1] == '\0') { - return true; - } + 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; current = trie_entry_child(trie, current, key); if (current == NULL) { @@ -283,15 +301,21 @@ bool trie_lookup(const trie_t *trie, const char *key) static inline void trie_entry_inspect(const trie_t *trie, const trie_entry_t *entry, int level) { + static int c_sum = 0; + static int nodes = 0; + + ++nodes; + c_sum += entry->c_len; for (int i = 0 ; i < level ; ++i) { fputs(" ", stdout); } - if (entry->c == NULL) { + if (entry->c_len == 0) { fputs("(nil)", stdout); } else { + const char *c = trie->c + entry->c_offset; for (int i = 0 ; i < entry->c_len ; ++i) { - if (entry->c[i]) { - printf("%c ", entry->c[i]); + if (c[i]) { + printf("%c ", c[i]); } else { fputs("\\0 ", stdout); } @@ -301,6 +325,9 @@ static inline void trie_entry_inspect(const trie_t *trie, for (int i = 0 ; i < entry->children_len ; ++i) { trie_entry_inspect(trie, &trie->entries[entry->children[i]], level + 1); } + if (level == 0) { + printf("Mean char per node: %d\n", c_sum / nodes); + } } void trie_inspect(const trie_t *trie) diff --git a/common/tst-trie.c b/common/tst-trie.c index b4b064e..d2ccc14 100644 --- a/common/tst-trie.c +++ b/common/tst-trie.c @@ -90,7 +90,7 @@ static trie_t *create_trie_from_file(const char *file) p = eol - BUFSIZ; } int i = 0; -#if 0 +#if 1 for (const char *s = eol - 1 ; s >= p ; --s) { line[i++] = ascii_tolower(*s); } -- 2.20.1