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 trie_t *trie_new()
  62 {
  63     return p_new(trie_t, 1);
  64 }
  65
  66 void trie_delete(trie_t **trie)
  67 {
  68     if (*trie) {
  69         for (int i = 0 ; i < (*trie)->entries_len ; ++i) {
  70             trie_entry_t *entry = &(*trie)->entries[i];
  71             if (entry->c_own) {
  72                 p_delete(&entry->c);
  73             } else {
  74                 entry->c = NULL;
  75             }
  76             p_delete(&(entry->children));
  77         }
  78         p_delete(&(*trie)->entries);
  79         p_delete(trie);
  80     }
  81 }
  82
  83 /** Check that the given entry is a prefix for the given key.
  84  */
  85 static inline bool trie_entry_c_match(const trie_entry_t* entry,
  86                                       const char *key, int *pos)
  87 {
  88     int i = 0;
  89     for (i = 0 ; i < entry->c_len ; ++i) {
  90         if (key[i] != entry->c[i]) {
  91             if (pos) {
  92                 *pos = i;
  93             }
  94             return false;
  95         }
  96     }
  97     if (pos) {
  98         *pos = i;
  99     }
 100     return true;
 101 }
 102
 103 /** Lookup for a child of entry matching the given entry at the given pos.
 104  * Only the first character of the children is taken into account in the
 105  * lookup. The current entry is assumed to match the key.
 106  */
 107 static inline trie_entry_t* trie_entry_child(const trie_t *trie,
 108                                              const trie_entry_t* entry,
 109                                              const char *key)
 110 {
 111     int start = 0;
 112     int end   = entry->children_len;
 113     const char c = *key;
 114
 115     while (start < end) {
 116         int mid = (start + end) / 2;
 117         trie_entry_t* child = &trie->entries[entry->children[mid]];
 118
 119         if (child->c_len) {
 120             if (child->c[0] == c) {
 121                 return child;
 122             }
 123             if (c < child->c[0]) {
 124                 end = mid;
 125             } else {
 126                 start = mid + 1;
 127             }
 128         } else {
 129             abort();
 130         }
 131     }
 132     return NULL;
 133 }
 134
 135 static inline void trie_grow(trie_t *trie, int delta)
 136 {
 137     int next_size = trie->entries_size;
 138     if (next_size > trie->entries_len + delta) {
 139         return;
 140     }
 141     do {
 142         next_size = p_alloc_nr(next_size);
 143     } while (trie->entries_len + delta > next_size);
 144     p_allocgrow(&trie->entries, next_size, &trie->entries_size);
 145 }
 146
 147 static inline int trie_entry_new(trie_t *trie)
 148 {
 149     memset(trie->entries + trie->entries_len, 0, sizeof(trie_entry_t));
 150     return trie->entries_len++;
 151 }
 152
 153 static inline int trie_add_leaf(trie_t *trie, const char *key)
 154 {
 155     trie_entry_t *entry;
 156     entry = &trie->entries[trie_entry_new(trie)];
 157     entry->c     = strdup(key); /* don't use m_strdup
 158                                    since m_strdup("") == NULL */
 159     entry->c_len = m_strlen(key) + 1;
 160     entry->c_own = true;
 161     return trie->entries_len - 1;
 162 }
 163
 164 static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry,
 165                                            int pchild)
 166 {
 167     const char c = trie->entries[pchild].c[0];
 168     int start = 0;
 169     int end   = entry->children_len;
 170
 171     p_allocgrow(&entry->children, entry->children_len + 1, &entry->children_size);
 172     while (start < end) {
 173         int mid = (start + end) / 2;
 174         trie_entry_t* child = &trie->entries[entry->children[mid]];
 175
 176         if (child->c_len) {
 177             if (child->c[0] == c) {
 178                 abort();
 179             }
 180             if (c < child->c[0]) {
 181                 end = mid;
 182             } else {
 183                 start = mid + 1;
 184             }
 185         } else {
 186             abort();
 187         }
 188     }
 189     memmove(entry->children + start + 1,
 190             entry->children + start,
 191             sizeof(int) * (entry->children_len - start));
 192     entry->children[start] = pchild;
 193     ++entry->children_len;
 194 }
 195
 196 static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos)
 197 {
 198     trie_entry_t *child;
 199     child    = &trie->entries[trie_entry_new(trie)];
 200     if (pos == 0) {
 201         child->c     = entry->c;
 202         child->c_len = entry->c_len;
 203         child->c_own = entry->c_own;
 204         entry->c     = NULL;
 205         entry->c_len = 0;
 206         entry->c_own = false;
 207     } else {
 208         child->c     = entry->c + pos;
 209         child->c_len = entry->c_len - pos;
 210         child->c_own = false;
 211         entry->c_len = pos;
 212     }
 213     child->children      = entry->children;
 214     child->children_len  = entry->children_len;
 215     child->children_size = entry->children_size;
 216     entry->children      = NULL;
 217     entry->children_len  = 0;
 218     entry->children_size = 0;
 219     trie_entry_insert_child(trie, entry, trie->entries_len - 1);
 220 }
 221
 222 void trie_insert(trie_t *trie, const char* key)
 223 {
 224     trie_grow(trie, 2);
 225     if (trie->entries_len == 0) {
 226         (void)trie_add_leaf(trie, key);
 227     } else {
 228         trie_entry_t *current = trie->entries;
 229         while (true) {
 230             int pos = 0;
 231             if (trie_entry_c_match(current, key, &pos)) {
 232                 if (current->c_len && current->c[current->c_len - 1] == '\0') {
 233                     return;
 234                 }
 235                 trie_entry_t *next = NULL;
 236                 key += pos;
 237                 next = trie_entry_child(trie, current, key);
 238                 if (next == NULL) {
 239                     trie_entry_insert_child(trie, current,
 240                                             trie_add_leaf(trie, key));
 241                     return;
 242                 } else {
 243                     current = next;
 244                 }
 245             } else {
 246                 trie_entry_split(trie, current, pos);
 247                 trie_entry_insert_child(trie, current,
 248                                         trie_add_leaf(trie, key + pos));
 249                 return;
 250             }
 251         }
 252     }
 253 }
 254
 255 bool trie_lookup(const trie_t *trie, const char *key)
 256 {
 257     if (trie->entries_len == 0) {
 258         return false;
 259     } else {
 260         trie_entry_t *current = trie->entries;
 261         while (true) {
 262             int pos = 0;
 263             if (trie_entry_c_match(current, key, &pos)) {
 264                 if (current->c_len && current->c[current->c_len - 1] == '\0') {
 265                     return true;
 266                 }
 267                 key += pos;
 268                 current = trie_entry_child(trie, current, key);
 269                 if (current == NULL) {
 270                     return false;
 271                 }
 272             } else {
 273                 return false;
 274             }
 275         }
 276     }
 277 }
 278
 279
 280 /* Debug {{{1
 281  */
 282
 283 static inline void trie_entry_inspect(const trie_t *trie,
 284                                       const trie_entry_t *entry, int level)
 285 {
 286     for (int i = 0 ; i < level ; ++i) {
 287         fputs("  ", stdout);
 288     }
 289     if (entry->c == NULL) {
 290         fputs("(nil)", stdout);
 291     } else {
 292         for (int i = 0 ; i < entry->c_len ; ++i) {
 293             if (entry->c[i]) {
 294                 printf("%c ", entry->c[i]);
 295             } else {
 296                 fputs("\\0 ", stdout);
 297             }
 298         }
 299     }
 300     fputs("\n", stdout);
 301     for (int i = 0 ; i < entry->children_len ; ++i) {
 302         trie_entry_inspect(trie, &trie->entries[entry->children[i]], level + 1);
 303     }
 304 }
 305
 306 void trie_inspect(const trie_t *trie)
 307 {
 308     trie_entry_inspect(trie, trie->entries, 0);
 309 }