From 266d6c0bfd9bce408aca73bb0d621e5d4d9fab6f Mon Sep 17 00:00:00 2001 From: Florent Bruneau Date: Wed, 10 Sep 2008 19:52:35 +0200 Subject: [PATCH] Fixes and add small tests. Signed-off-by: Florent Bruneau --- common/Makefile | 4 ++- common/trie.c | 71 ++++++++++++++++++++++++++++++++++++++++------- common/trie.h | 3 ++ common/tst-trie.c | 51 ++++++++++++++++++++++++++++++++++ 4 files changed, 118 insertions(+), 11 deletions(-) create mode 100644 common/tst-trie.c diff --git a/common/Makefile b/common/Makefile index 8c5c1f4..0f09ebf 100644 --- a/common/Makefile +++ b/common/Makefile @@ -29,8 +29,10 @@ # THE POSSIBILITY OF SUCH DAMAGE. # ############################################################################## -LIBS = lib +LIBS = lib +TESTS = tst-trie lib_SOURCES = str.c buffer.c common.c epoll.c server.c trie.c +tst-trie_SOURCES = tst-trie.c lib.a include ../mk/common.mk diff --git a/common/trie.c b/common/trie.c index 4575a63..5ed957f 100644 --- a/common/trie.c +++ b/common/trie.c @@ -76,6 +76,7 @@ void trie_delete(trie_t **trie) } p_delete(&(entry->children)); } + p_delete(&(*trie)->entries); p_delete(trie); } } @@ -132,23 +133,37 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie, return NULL; } -static void trie_grow(trie_t *trie, int delta) +static inline void trie_grow(trie_t *trie, int delta) { - p_allocgrow(&trie->entries, trie->entries_len + delta, &trie->entries_size); + 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); + printf("After grow: %d\n", trie->entries_size); +} + +static inline int trie_entry_new(trie_t *trie) +{ + 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 = &trie->entries[trie_entry_new(trie)]; entry->c = m_strdup(key); entry->c_len = m_strlen(key) + 1; entry->c_own = true; 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]; int start = 0; @@ -176,13 +191,13 @@ 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; @@ -194,7 +209,7 @@ static void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos) child->c = entry->c + pos; child->c_len = entry->c_len - pos; child->c_own = false; - entry->c_len -= pos; + entry->c_len = pos; } child->children = entry->children; child->children_len = entry->children_len; @@ -207,6 +222,7 @@ 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 { @@ -214,6 +230,9 @@ void trie_insert(trie_t *trie, const char* key) 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; + } trie_entry_t *next = NULL; key += pos; next = trie_entry_child(trie, current, key); @@ -257,3 +276,35 @@ 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) +{ + for (int i = 0 ; i < level ; ++i) { + fputs(" ", stdout); + } + if (entry->c == NULL) { + fputs("(nil)", stdout); + } else { + for (int i = 0 ; i < entry->c_len ; ++i) { + if (entry->c[i]) { + printf("%c ", entry->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); + } +} + +void trie_inspect(const trie_t *trie) +{ + trie_entry_inspect(trie, trie->entries, 0); +} diff --git a/common/trie.h b/common/trie.h index 7a132c9..a0fd6ac 100644 --- a/common/trie.h +++ b/common/trie.h @@ -52,4 +52,7 @@ bool trie_lock(trie_t *trie); */ __attribute__((nonnull(1,2))) bool trie_lookup(const trie_t *trie, const char* key); +__attribute__((nonnull(1))) +void trie_inspect(const trie_t *trie); + #endif diff --git a/common/tst-trie.c b/common/tst-trie.c new file mode 100644 index 0000000..20ca5e3 --- /dev/null +++ b/common/tst-trie.c @@ -0,0 +1,51 @@ +/******************************************************************************/ +/* pfixtools: a collection of postfix related tools */ +/* ~~~~~~~~~ */ +/* ________________________________________________________________________ */ +/* */ +/* Redistribution and use in source and binary forms, with or without */ +/* modification, are permitted provided that the following conditions */ +/* are met: */ +/* */ +/* 1. Redistributions of source code must retain the above copyright */ +/* notice, this list of conditions and the following disclaimer. */ +/* 2. Redistributions in binary form must reproduce the above copyright */ +/* notice, this list of conditions and the following disclaimer in the */ +/* documentation and/or other materials provided with the distribution. */ +/* 3. The names of its contributors may not be used to endorse or promote */ +/* products derived from this software without specific prior written */ +/* permission. */ +/* */ +/* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND */ +/* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE */ +/* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ +/* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS */ +/* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR */ +/* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF */ +/* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS */ +/* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN */ +/* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) */ +/* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF */ +/* THE POSSIBILITY OF SUCH DAMAGE. */ +/******************************************************************************/ + +/* + * Copyright © 2008 Florent Bruneau + */ + +#include "common.h" +#include "trie.h" + +int main(void) +{ + trie_t *trie = trie_new(); + trie_insert(trie, "abcdefghi"); + trie_insert(trie, "abcde123654789"); + trie_insert(trie, "abcde123456789"); + trie_insert(trie, "abcde123654789"); + trie_insert(trie, "coucou"); + trie_insert(trie, "coucou chez vous"); + trie_inspect(trie); + trie_delete(&trie); + return 0; +} -- 2.20.1