From: Florent Bruneau <florent.bruneau@polytechnique.org>
Date: Wed, 17 Sep 2008 20:19:53 +0000 (+0200)
Subject: Some improvements to the trie:
X-Git-Url: http://git.madism.org/?p=apps%2Fpfixtools.git;a=commitdiff_plain;h=1ed216354a7c74d35906aeee845f1b688d888505

Some improvements to the trie:
  - add trie_prefix to check if the trie contains a prefix for    a string.
  - add comments
  - lock the trie_t structure, not only its content.

Signed-off-by: Florent Bruneau <florent.bruneau@polytechnique.org>
---

diff --git a/common/trie.c b/common/trie.c
index 59f1a9f..7d75d69 100644
--- a/common/trie.c
+++ b/common/trie.c
@@ -108,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;
@@ -297,6 +303,30 @@ 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) {
@@ -311,6 +341,12 @@ void trie_lock(trie_t *trie)
         array_unlock(trie->entries);
         return;
     }
+    if (mlock(trie, sizeof(trie_t)) != 0) {
+        UNIXERR("mlock");
+        array_unlock(trie->entries);
+        array_unlock(trie->c);
+        return;
+    }
     trie->locked = true;
 }
 
@@ -321,6 +357,7 @@ void trie_unlock(trie_t *trie)
     }
     array_unlock(trie->entries);
     array_unlock(trie->c);
+    munlock(trie, sizeof(trie_t));
     trie->locked = false;
 }
 
diff --git a/common/trie.h b/common/trie.h
index ddf984a..85ce031 100644
--- a/common/trie.h
+++ b/common/trie.h
@@ -44,21 +44,56 @@ PARRAY(trie_t)
 trie_t *trie_new(void);
 void trie_delete(trie_t **trie);
 
+/** Add a string in the trie.
+ * \ref trie_compile.
+ */
 __attribute__((nonnull(1,2)))
-void trie_insert(trie_t *trie, const char* key);
+void trie_insert(trie_t *trie, const char *key);
 
+/** Compile the trie.
+ * A trie must be compiled before lookup is possible. Compiling the trie
+ * consists in building the tree.
+ *
+ * \param memlock if true, the trie is locked into the RAM (mlock).
+ *
+ * Usage of a trie:
+ *   trie_insert(trie, ...);
+ *   trie_insert(trie, ...);
+ *   ...
+ *   trie_insert(trie, ...);
+ *
+ *   trie_compile(trie, lock);
+ *
+ *   trie_lookup(trie, ...);
+ *   trie_lookup(trie, ...);
+ */
 __attribute__((nonnull(1)))
 void trie_compile(trie_t *trie, bool memlock);
 
+/** Lock the trie into memory.
+ * \ref trie_unlock
+ */
 __attribute__((nonnull(1)))
 void trie_lock(trie_t *trie);
 
+/** Unlock the trie.
+ * \ref trie_lock
+ */
 __attribute__((nonnull(1)))
 void trie_unlock(trie_t *trie);
 
+/** Check if the trie contains \p key.
+ */
 __attribute__((nonnull(1,2)))
-bool trie_lookup(const trie_t *trie, const char* key);
+bool trie_lookup(const trie_t *trie, const char *key);
 
+/** Check if the trie contains a prefix of \p key.
+ */
+__attribute__((nonnull(1,2)))
+bool trie_prefix(const trie_t *trie, const char *key);
+
+/** Show the content of the trie and computes statistics.
+ */
 __attribute__((nonnull(1)))
 void trie_inspect(const trie_t *trie, bool show_content);