Fix duplicate management.

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

diff --git a/common/trie.c b/common/trie.c
index 030ff3a..3ac0c69 100644 (file)
--- a/common/trie.c
+++ b/common/trie.c
@@ -33,31 +33,33 @@
  * Copyright © 2008 Florent Bruneau
  */
 
+#include <sys/mman.h>
+
 #include "str.h"
 #include "trie.h"
 
 typedef struct trie_entry_t trie_entry_t;
 
 struct trie_entry_t {
-    int  c_offset;
-    int  c_len;
+    int32_t  c_offset;
+    int32_t  c_len;
 
-    int children_offset;
-    int children_len;
+    int32_t children_offset;
+    int32_t children_len;
 };
 
 struct trie_t {
     trie_entry_t *entries;
-    int entries_len;
-    int entries_size;
+    int32_t entries_len;
+    int32_t entries_size;
 
     char *c;
-    int  c_len;
-    int  c_size;
+    int32_t  c_len;
+    int32_t  c_size;
 
     char **keys;
-    int  keys_len;
-    int  keys_size;
+    int32_t  keys_len;
+    int32_t  keys_size;
 
     bool locked;
 };
@@ -67,9 +69,19 @@ trie_t *trie_new(void)
     return p_new(trie_t, 1);
 }
 
+static inline void trie_cleanup_build_data(trie_t *trie)
+{
+    for (int i = 0 ; i < trie->keys_len ; ++i) {
+        p_delete(&trie->keys[i]);
+    }
+    p_delete(&trie->keys);
+    trie->keys_len = trie->keys_size = 0;
+}
+
 void trie_delete(trie_t **trie)
 {
     if (*trie) {
+        trie_cleanup_build_data(*trie);
         p_delete(&(*trie)->entries);
         p_delete(&(*trie)->c);
         p_delete(trie);
@@ -246,6 +258,9 @@ static inline void trie_compile_aux(trie_t *trie, int id,
                 current = trie->keys[i][offset];
             }
         }
+        if (fork_pos == 0 && current == '\0') {
+            return;
+        }
     }
     forks[fork_pos] = last_key;
 
@@ -259,20 +274,25 @@ static inline void trie_compile_aux(trie_t *trie, int id,
     }
 }
 
-static inline void trie_cleanup_build_data(trie_t *trie)
-{
-    for (int i = 0 ; i < trie->keys_len ; ++i) {
-        p_delete(&trie->keys[i]);
-    }
-    p_delete(&trie->keys);
-}
 
 static inline void trie_shrink(trie_t *trie)
 {
+    p_shrink(&trie->entries, trie->entries_len, &trie->entries_size);
+    p_shrink(&trie->c, trie->c_len, &trie->c_size);
 }
 
 static inline void trie_lock(trie_t *trie)
 {
+    if (mlock(trie->entries, sizeof(trie_entry_t) * trie->entries_len) != 0) {
+        UNIXERR("mlock");
+        return;
+    }
+    if (mlock(trie->c, trie->c_len) != 0) {
+        UNIXERR("mlock");
+        munlock(trie->entries, sizeof(trie_entry_t) * trie->entries_len);
+        return;
+    }
+    trie->locked = true;
 }
 
 typedef char *str_t;
@@ -327,11 +347,17 @@ bool trie_lookup(const trie_t *trie, const char *key)
 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;
+    static int max_depth = 0;
+    static int leaves    = 0;
+    static int depth_sum = 0;
 
-    ++nodes;
-    c_sum += entry->c_len;
+    if (trie_entry_is_leaf(entry)) {
+        if (level > max_depth) {
+            max_depth = level;
+        }
+        ++leaves;
+        depth_sum += level;
+    }
     for (int i = 0 ; i < level ; ++i) {
         fputs("  ", stdout);
     }
@@ -339,6 +365,7 @@ static inline void trie_entry_inspect(const trie_t *trie,
         fputs("(nil)", stdout);
     } else {
         const char *c = trie->c + entry->c_offset;
+        printf("(%d) ", entry->c_len);
         for (int i = 0 ; i < entry->c_len ; ++i) {
             if (c[i]) {
                 printf("%c ", c[i]);
@@ -353,7 +380,13 @@ static inline void trie_entry_inspect(const trie_t *trie,
         trie_entry_inspect(trie, &trie->entries[i], level + 1);
     }
     if (level == 0) {
-        printf("Mean char per node: %d\n", c_sum / nodes);
+        printf("Average char per node: %d\n", trie->c_len / trie->entries_len);
+        printf("Number of nodes: %d\n", trie->entries_len);
+        printf("Number of leaves: %d\n", leaves);
+        printf("Max depth: %d\n", max_depth);
+        printf("Average leaf depth: %d\n", depth_sum / leaves);
+        printf("Memory used: %d\n", (trie->entries_size * sizeof(trie_entry_t))
+                                  + (trie->c_size) + sizeof(trie_t));
     }
 }