Fix duplicate management.

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

diff --git a/common/trie.c b/common/trie.c
index 2e3ada1..3ac0c69 100644 (file)
--- a/common/trie.c
+++ b/common/trie.c
@@ -41,25 +41,25 @@
 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;
 };
@@ -258,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;
 
@@ -344,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);
     }
@@ -371,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));
     }
 }