common/trie.c

   1 /******************************************************************************/
   2 /*          pfixtools: a collection of postfix related tools                  */
   3 /*          ~~~~~~~~~                                                         */
   4 /*  ________________________________________________________________________  */
   5 /*                                                                            */
   6 /*  Redistribution and use in source and binary forms, with or without        */
   7 /*  modification, are permitted provided that the following conditions        */
   8 /*  are met:                                                                  */
   9 /*                                                                            */
  10 /*  1. Redistributions of source code must retain the above copyright         */
  11 /*     notice, this list of conditions and the following disclaimer.          */
  12 /*  2. Redistributions in binary form must reproduce the above copyright      */
  13 /*     notice, this list of conditions and the following disclaimer in the    */
  14 /*     documentation and/or other materials provided with the distribution.   */
  15 /*  3. The names of its contributors may not be used to endorse or promote    */
  16 /*     products derived from this software without specific prior written     */
  17 /*     permission.                                                            */
  18 /*                                                                            */
  19 /*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
  20 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
  21 /*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
  22 /*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
  23 /*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
  24 /*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
  25 /*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
  26 /*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
  27 /*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
  28 /*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
  29 /*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
  30 /******************************************************************************/
  31
  32 /*
  33  * Copyright © 2008 Florent Bruneau
  34  */
  35
  36 #include "str.h"
  37 #include "trie.h"
  38
  39 typedef struct trie_entry_t trie_entry_t;
  40
  41 struct trie_entry_t {
  42     char *c;
  43     int  c_len;
  44     bool c_own;
  45
  46     int* children;
  47     int children_len;
  48     int children_size;
  49
  50     bool locked;
  51 };
  52
  53 struct trie_t {
  54     trie_entry_t* entries;
  55     int entries_len;
  56     int entries_size;
  57
  58     bool locked;
  59 };
  60
  61
  62 trie_t *trie_new()
  63 {
  64     return p_new(trie_t, 1);
  65 }
  66
  67 void trie_delete(trie_t **trie)
  68 {
  69     if (*trie) {
  70         for (int i = 0 ; i < (*trie)->entries_len ; ++i) {
  71             trie_entry_t *entry = &(*trie)->entries[i];
  72             if (entry->c_own) {
  73                 p_delete(&entry->c);
  74             } else {
  75                 entry->c = NULL;
  76             }
  77             p_delete(&(entry->children));
  78         }
  79         p_delete(&(*trie)->entries);
  80         p_delete(trie);
  81     }
  82 }
  83
  84 /** Check that the given entry is a prefix for the given key.
  85  */
  86 static inline bool trie_entry_c_match(const trie_entry_t* entry,
  87                                       const char *key, int *pos)
  88 {
  89     int i = 0;
  90     for (i = 0 ; i < entry->c_len ; ++i) {
  91         if (key[i] != entry->c[i]) {
  92             if (pos) {
  93                 *pos = i;
  94             }
  95             return false;
  96         }
  97     }
  98     if (pos) {
  99         *pos = i;
 100     }
 101     return true;
 102 }
 103
 104 /** Lookup for a child of entry matching the given entry at the given pos.
 105  * Only the first character of the children is taken into account in the
 106  * lookup. The current entry is assumed to match the key.
 107  */
 108 static inline trie_entry_t* trie_entry_child(const trie_t *trie,
 109                                              const trie_entry_t* entry,
 110                                              const char *key)
 111 {
 112     int start = 0;
 113     int end   = entry->children_len;
 114     const char c = *key;
 115
 116     while (start < end) {
 117         int mid = (start + end) / 2;
 118         trie_entry_t* child = &trie->entries[entry->children[mid]];
 119
 120         if (child->c_len) {
 121             if (child->c[0] == c) {
 122                 return child;
 123             }
 124             if (c < child->c[0]) {
 125                 end = mid;
 126             } else {
 127                 start = mid + 1;
 128             }
 129         } else {
 130             abort();
 131         }
 132     }
 133     return NULL;
 134 }
 135
 136 static inline void trie_grow(trie_t *trie, int delta)
 137 {
 138     int next_size = trie->entries_size;
 139     if (next_size > trie->entries_len + delta) {
 140         return;
 141     }
 142     do {
 143         next_size = p_alloc_nr(next_size);
 144     } while (trie->entries_len + delta > next_size);
 145     p_allocgrow(&trie->entries, next_size, &trie->entries_size);
 146     printf("After grow: %d\n", trie->entries_size);
 147 }
 148
 149 static inline int trie_entry_new(trie_t *trie)
 150 {
 151     memset(trie->entries + trie->entries_len, 0, sizeof(trie_entry_t));
 152     return trie->entries_len++;
 153 }
 154
 155 static inline int trie_add_leaf(trie_t *trie, const char *key)
 156 {
 157     trie_entry_t *entry;
 158     entry = &trie->entries[trie_entry_new(trie)];
 159     entry->c     = m_strdup(key);
 160     entry->c_len = m_strlen(key) + 1;
 161     entry->c_own = true;
 162     return trie->entries_len - 1;
 163 }
 164
 165 static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry,
 166                                            int pchild)
 167 {
 168     const char c = trie->entries[pchild].c[0];
 169     int start = 0;
 170     int end   = entry->children_len;
 171
 172     p_allocgrow(&entry->children, entry->children_len + 1, &entry->children_size);
 173     while (start < end) {
 174         int mid = (start + end) / 2;
 175         trie_entry_t* child = &trie->entries[entry->children[mid]];
 176
 177         if (child->c_len) {
 178             if (child->c[0] == c) {
 179                 abort();
 180             }
 181             if (c < child->c[0]) {
 182                 end = mid;
 183             } else {
 184                 start = mid + 1;
 185             }
 186         } else {
 187             abort();
 188         }
 189     }
 190     memmove(entry->children + start + 1,
 191             entry->children + start,
 192             sizeof(int) * (entry->children_len - start));
 193     entry->children[start] = pchild;
 194     ++entry->children_len;
 195 }
 196
 197 static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos)
 198 {
 199     trie_entry_t *child;
 200     child    = &trie->entries[trie_entry_new(trie)];
 201     if (pos == 0) {
 202         child->c     = entry->c;
 203         child->c_len = entry->c_len;
 204         child->c_own = entry->c_own;
 205         entry->c     = NULL;
 206         entry->c_len = 0;
 207         entry->c_own = false;
 208     } else {
 209         child->c     = entry->c + pos;
 210         child->c_len = entry->c_len - pos;
 211         child->c_own = false;
 212         entry->c_len = pos;
 213     }
 214     child->children      = entry->children;
 215     child->children_len  = entry->children_len;
 216     child->children_size = entry->children_size;
 217     entry->children      = NULL;
 218     entry->children_len  = 0;
 219     entry->children_size = 0;
 220     trie_entry_insert_child(trie, entry, trie->entries_len - 1);
 221 }
 222
 223 void trie_insert(trie_t *trie, const char* key)
 224 {
 225     trie_grow(trie, 2);
 226     if (trie->entries_len == 0) {
 227         (void)trie_add_leaf(trie, key);
 228     } else {
 229         trie_entry_t *current = trie->entries;
 230         while (true) {
 231             int pos = 0;
 232             if (trie_entry_c_match(current, key, &pos)) {
 233                 if (current->c_len && current->c[current->c_len - 1] == '\0') {
 234                     return;
 235                 }
 236                 trie_entry_t *next = NULL;
 237                 key += pos;
 238                 next = trie_entry_child(trie, current, key);
 239                 if (next == NULL) {
 240                     trie_entry_insert_child(trie, current,
 241                                             trie_add_leaf(trie, key));
 242                     return;
 243                 } else {
 244                     current = next;
 245                 }
 246             } else {
 247                 trie_entry_split(trie, current, pos);
 248                 trie_entry_insert_child(trie, current,
 249                                         trie_add_leaf(trie, key + pos));
 250                 return;
 251             }
 252         }
 253     }
 254 }
 255
 256 bool trie_lookup(const trie_t *trie, const char *key)
 257 {
 258     if (trie->entries_len == 0) {
 259         return false;
 260     } else {
 261         trie_entry_t *current = trie->entries;
 262         while (true) {
 263             int pos = 0;
 264             if (trie_entry_c_match(current, key, &pos)) {
 265                 if (current->c_len && current->c[current->c_len - 1] == '\0') {
 266                     return true;
 267                 }
 268                 key += pos;
 269                 current = trie_entry_child(trie, current, key);
 270                 if (current == NULL) {
 271                     return false;
 272                 }
 273             } else {
 274                 return false;
 275             }
 276         }
 277     }
 278 }
 279
 280
 281 /* Debug {{{1
 282  */
 283
 284 static inline void trie_entry_inspect(const trie_t *trie,
 285                                       const trie_entry_t *entry, int level)
 286 {
 287     for (int i = 0 ; i < level ; ++i) {
 288         fputs("  ", stdout);
 289     }
 290     if (entry->c == NULL) {
 291         fputs("(nil)", stdout);
 292     } else {
 293         for (int i = 0 ; i < entry->c_len ; ++i) {
 294             if (entry->c[i]) {
 295                 printf("%c ", entry->c[i]);
 296             } else {
 297                 fputs("\\0 ", stdout);
 298             }
 299         }
 300     }
 301     fputs("\n", stdout);
 302     for (int i = 0 ; i < entry->children_len ; ++i) {
 303         trie_entry_inspect(trie, &trie->entries[entry->children[i]], level + 1);
 304     }
 305 }
 306
 307 void trie_inspect(const trie_t *trie)
 308 {
 309     trie_entry_inspect(trie, trie->entries, 0);
 310 }