X-Git-Url: http://git.madism.org/?a=blobdiff_plain;f=common%2Ftrie.c;h=3cc093a3036c2f0df88c99a04f63a4da87d78c3b;hb=fb519b0c3a78183d3fad3778d7d57bc2693598fc;hp=4575a636680f826d3681f6b99847306df12159d0;hpb=4967e5b5d3bba84232eebf9763eb214ef395e061;p=apps%2Fpfixtools.git diff --git a/common/trie.c b/common/trie.c index 4575a63..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,15 +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); } @@ -69,25 +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,38 +145,61 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie, return NULL; } -static void trie_grow(trie_t *trie, int delta) +#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) +{ + GROW(trie->entries, delta, trie->entries_len, trie->entries_size); +} + +static inline int trie_entry_new(trie_t *trie) { - p_allocgrow(&trie->entries, trie->entries_len + delta, &trie->entries_size); + memset(trie->entries + trie->entries_len, 0, sizeof(trie_entry_t)); + return trie->entries_len++; } -static int trie_add_leaf(trie_t *trie, const char *key) +static inline int trie_add_leaf(trie_t *trie, const char *key) { trie_entry_t *entry; - trie_grow(trie, 1); - entry = &trie->entries[trie->entries_len++]; - entry->c = m_strdup(key); - entry->c_len = m_strlen(key) + 1; - entry->c_own = true; + int len = m_strlen(key) + 1; + entry = &trie->entries[trie_entry_new(trie)]; + 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 void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, int pchild) +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; @@ -176,25 +212,22 @@ static void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, int pchil entry->children + start, sizeof(int) * (entry->children_len - start)); entry->children[start] = pchild; + ++entry->children_len; } -static 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, int pos) { trie_entry_t *child; - trie_grow(trie, 2); - child = &trie->entries[trie->entries_len++]; + 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; @@ -207,13 +240,17 @@ static void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos) void trie_insert(trie_t *trie, const char* key) { + trie_grow(trie, 2); if (trie->entries_len == 0) { (void)trie_add_leaf(trie, key); } else { trie_entry_t *current = trie->entries; while (true) { int pos = 0; - if (trie_entry_c_match(current, key, &pos)) { + if (trie_entry_c_match(trie, current, key, &pos)) { + if (trie_entry_is_leaf(current)) { + return; + } trie_entry_t *next = NULL; key += pos; next = trie_entry_child(trie, current, key); @@ -242,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) { @@ -257,3 +293,44 @@ bool trie_lookup(const trie_t *trie, const char *key) } } } + + +/* Debug {{{1 + */ + +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_len == 0) { + fputs("(nil)", stdout); + } else { + const char *c = trie->c + entry->c_offset; + for (int i = 0 ; i < entry->c_len ; ++i) { + if (c[i]) { + printf("%c ", c[i]); + } else { + fputs("\\0 ", stdout); + } + } + } + fputs("\n", stdout); + 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) +{ + trie_entry_inspect(trie, trie->entries, 0); +}