X-Git-Url: http://git.madism.org/?a=blobdiff_plain;ds=sidebyside;f=common%2Ftrie.c;h=5df379cd5131346eaedbbf6404964716b46f9ec1;hb=bb7b60d0431952e250109275b59eb70fb05df378;hp=5bf18ecd848a82d313c19f15694b3e100b9cfdf5;hpb=00bae73b4873e9c1e8d5526feecdb275f7bb756f;p=apps%2Fpfixtools.git

diff --git a/common/trie.c b/common/trie.c
index 5bf18ec..5df379c 100644
--- a/common/trie.c
+++ b/common/trie.c
@@ -33,8 +33,6 @@
  * Copyright © 2008 Florent Bruneau
  */
 
-#include <sys/mman.h>
-
 #include "array.h"
 #include "str.h"
 #include "trie.h"
@@ -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;
@@ -152,7 +156,7 @@ static inline int 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)
@@ -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;
 }