Save 4bytes per entry of the trie.

[apps/pfixtools.git] / common / trie.c

diff --git a/common/trie.c b/common/trie.c
index 9ffa9b5..cb39cb2 100644 (file)
--- 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"
@@ -42,20 +40,20 @@
 typedef struct trie_entry_t trie_entry_t;
 
 struct trie_entry_t {
-    int32_t  c_offset;
-    int32_t  c_len;
+    uint32_t c_offset;
+    uint32_t children_offset;
 
-    int32_t children_offset;
-    int32_t children_len;
+    uint16_t c_len;
+    uint16_t children_len;
 };
 #define TRIE_ENTRY_INIT { 0, 0, 0, 0 }
 ARRAY(trie_entry_t)
 
 struct trie_t {
-    trie_entry_t_array_t entries;
-    char_array_t         c;
-    char_array_t         keys;
-    int_array_t          keys_offset;
+    A(trie_entry_t) entries;
+    A(char)         c;
+    A(char)         keys;
+    A(int)          keys_offset;
 
     bool locked;
 };
@@ -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;
@@ -148,14 +152,14 @@ static inline trie_entry_t* trie_entry_child(const trie_t *trie,
     return NULL;
 }
 
-static inline int trie_entry_new(trie_t *trie)
+static inline uint32_t 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)
+static inline uint32_t trie_add_leaf(trie_t *trie, const char *key)
 {
     trie_entry_t *entry;
     int len = m_strlen(key) + 1;
@@ -167,7 +171,7 @@ static inline int trie_add_leaf(trie_t *trie, const char *key)
 }
 
 static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry,
-                                           int pchild)
+                                           uint32_t pchild)
 {
     if (entry->children_len == 0) {
         entry->children_offset = pchild;
@@ -182,7 +186,7 @@ static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry,
     }
 }
 
-static inline 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, uint16_t pos)
 {
     trie_entry_t *child;
     child    = array_ptr(trie->entries, trie_entry_new(trie));
@@ -212,17 +216,17 @@ void trie_insert(trie_t *trie, const char* key)
 }
 
 
-static inline void trie_compile_aux(trie_t *trie, int id,
-                                    int first_key, int last_key, int offset,
-                                    int initial_diff)
+static inline void trie_compile_aux(trie_t *trie, uint32_t id,
+                                    uint32_t first_key, uint32_t last_key,
+                                    int offset, int initial_diff)
 {
-    int forks[256];
-    int fork_pos = 0;
+    uint32_t forks[256];
+    uint32_t fork_pos = 0;
     char current = '\0';
 
     for (int off_diff = initial_diff ; fork_pos == 0 ; ++off_diff, ++offset) {
         current = array_elt(trie->keys, array_elt(trie->keys_offset, first_key) + offset);
-        for (int i = first_key + 1 ; i < last_key ; ++i) {
+        for (uint32_t i = first_key + 1 ; i < last_key ; ++i) {
             const char *str = array_ptr(trie->keys, array_elt(trie->keys_offset, i));
             const char c = str[offset];
             if (c != current) {
@@ -242,8 +246,8 @@ static inline void trie_compile_aux(trie_t *trie, int id,
     }
     forks[fork_pos] = last_key;
 
-    const int children_len = array_elt(trie->entries, id).children_len;
-    for (int i = 0 ; i < children_len ; ++i) {
+    const uint8_t children_len = array_elt(trie->entries, id).children_len;
+    for (uint16_t i = 0 ; i < children_len ; ++i) {
         int child = array_elt(trie->entries, id).children_offset + i;
         if (forks[i] - 1 > first_key) {
             trie_compile_aux(trie, child, first_key, forks[i], offset, 1);
@@ -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;
 }
 
@@ -362,7 +392,7 @@ static inline void trie_entry_inspect(const trie_t *trie, bool show_content,
         }
         fputs("\n", stdout);
     }
-    for (int i = entry->children_offset ;
+    for (uint32_t i = entry->children_offset ;
           i < entry->children_offset + entry->children_len ; ++i) {
         trie_entry_inspect(trie, show_content, array_ptr(trie->entries, i), level + 1);
     }