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     int  c_offset;
  43     int  c_len;
  44
  45     int* children;
  46     int children_len;
  47     int children_size;
  48
  49     bool locked;
  50 };
  51
  52 struct trie_t {
  53     trie_entry_t *entries;
  54     int entries_len;
  55     int entries_size;
  56
  57     char *c;
  58     int  c_len;
  59     int  c_size;
  60
  61     bool locked;
  62 };
  63
  64 trie_t *trie_new(void)
  65 {
  66     return p_new(trie_t, 1);
  67 }
  68
  69 void trie_delete(trie_t **trie)
  70 {
  71     if (*trie) {
  72         for (int i = 0 ; i < (*trie)->entries_len ; ++i) {
  73             trie_entry_t *entry = &(*trie)->entries[i];
  74             p_delete(&(entry->children));
  75         }
  76         p_delete(&(*trie)->entries);
  77         p_delete(&(*trie)->c);
  78         p_delete(trie);
  79     }
  80 }
  81
  82 /** Check that the given entry is a prefix for the given key.
  83  */
  84 static inline bool trie_entry_c_match(const trie_t *trie,
  85                                       const trie_entry_t *entry,
  86                                       const char *key, int *pos)
  87 {
  88     const char *c = trie->c + entry->c_offset;
  89     int i = 0;
  90     for (i = 0 ; i < entry->c_len ; ++i) {
  91         if (key[i] != 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 static inline bool trie_entry_match(const trie_t *trie,
 105                                     const trie_entry_t *entry, const char *key)
 106 {
 107     return !!(strcmp(trie->c + entry->c_offset, key) == 0);
 108 }
 109
 110 static inline bool trie_entry_is_leaf(const trie_entry_t *entry)
 111 {
 112     return entry->children_len == 0;
 113 }
 114
 115 /** Lookup for a child of entry matching the given entry at the given pos.
 116  * Only the first character of the children is taken into account in the
 117  * lookup. The current entry is assumed to match the key.
 118  */
 119 static inline trie_entry_t* trie_entry_child(const trie_t *trie,
 120                                              const trie_entry_t* entry,
 121                                              const char *key)
 122 {
 123     int start = 0;
 124     int end   = entry->children_len;
 125     const char c = *key;
 126
 127     while (start < end) {
 128         int mid = (start + end) / 2;
 129         trie_entry_t* child = &trie->entries[entry->children[mid]];
 130         const char c2 = trie->c[child->c_offset];
 131
 132         if (child->c_len) {
 133             if (c2 == c) {
 134                 return child;
 135             }
 136             if (c < c2) {
 137                 end = mid;
 138             } else {
 139                 start = mid + 1;
 140             }
 141         } else {
 142             abort();
 143         }
 144     }
 145     return NULL;
 146 }
 147
 148 #define GROW(Buffer, Added, Len, Size)                  \
 149   do {                                                  \
 150       const int required_size = (Len) + (Added);        \
 151       int next_size = (Size);                           \
 152       if (next_size >= required_size) {                 \
 153           break;                                        \
 154       }                                                 \
 155       do {                                              \
 156           next_size = p_alloc_nr(next_size);            \
 157       } while (next_size < required_size);              \
 158       p_allocgrow(&(Buffer), next_size, &(Size));       \
 159   } while(0)
 160
 161 static inline void trie_grow(trie_t *trie, int delta)
 162 {
 163     GROW(trie->entries, delta, trie->entries_len, trie->entries_size);
 164 }
 165
 166 static inline int trie_entry_new(trie_t *trie)
 167 {
 168     memset(trie->entries + trie->entries_len, 0, sizeof(trie_entry_t));
 169     return trie->entries_len++;
 170 }
 171
 172 static inline int trie_add_leaf(trie_t *trie, const char *key)
 173 {
 174     trie_entry_t *entry;
 175     int len = m_strlen(key) + 1;
 176     entry = &trie->entries[trie_entry_new(trie)];
 177     GROW(trie->c, len, trie->c_len, trie->c_size);
 178     memcpy(trie->c + trie->c_len, key, len);
 179     entry->c_offset = trie->c_len;
 180     entry->c_len    = len;
 181     trie->c_len    += len;
 182     return trie->entries_len - 1;
 183 }
 184
 185 static inline void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry,
 186                                            int pchild)
 187 {
 188     const char c = trie->c[trie->entries[pchild].c_offset];
 189     int start = 0;
 190     int end   = entry->children_len;
 191
 192     p_allocgrow(&entry->children, entry->children_len + 1, &entry->children_size);
 193     while (start < end) {
 194         int mid = (start + end) / 2;
 195         const trie_entry_t* child = &trie->entries[entry->children[mid]];
 196         const char c2 = trie->c[child->c_offset];
 197
 198         if (child->c_len) {
 199             if (c2 == c) {
 200                 abort();
 201             }
 202             if (c < c2) {
 203                 end = mid;
 204             } else {
 205                 start = mid + 1;
 206             }
 207         } else {
 208             abort();
 209         }
 210     }
 211     memmove(entry->children + start + 1,
 212             entry->children + start,
 213             sizeof(int) * (entry->children_len - start));
 214     entry->children[start] = pchild;
 215     ++entry->children_len;
 216 }
 217
 218 static inline void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos)
 219 {
 220     trie_entry_t *child;
 221     child    = &trie->entries[trie_entry_new(trie)];
 222     if (pos == 0) {
 223         child->c_offset = entry->c_offset;
 224         child->c_len    = entry->c_len;
 225         entry->c_offset = 0;
 226         entry->c_len    = 0;
 227     } else {
 228         child->c_offset = entry->c_offset + pos;
 229         child->c_len    = entry->c_len - pos;
 230         entry->c_len    = pos;
 231     }
 232     child->children      = entry->children;
 233     child->children_len  = entry->children_len;
 234     child->children_size = entry->children_size;
 235     entry->children      = NULL;
 236     entry->children_len  = 0;
 237     entry->children_size = 0;
 238     trie_entry_insert_child(trie, entry, trie->entries_len - 1);
 239 }
 240
 241 void trie_insert(trie_t *trie, const char* key)
 242 {
 243     trie_grow(trie, 2);
 244     if (trie->entries_len == 0) {
 245         (void)trie_add_leaf(trie, key);
 246     } else {
 247         trie_entry_t *current = trie->entries;
 248         while (true) {
 249             int pos = 0;
 250             if (trie_entry_c_match(trie, current, key, &pos)) {
 251                 if (trie_entry_is_leaf(current)) {
 252                     return;
 253                 }
 254                 trie_entry_t *next = NULL;
 255                 key += pos;
 256                 next = trie_entry_child(trie, current, key);
 257                 if (next == NULL) {
 258                     trie_entry_insert_child(trie, current,
 259                                             trie_add_leaf(trie, key));
 260                     return;
 261                 } else {
 262                     current = next;
 263                 }
 264             } else {
 265                 trie_entry_split(trie, current, pos);
 266                 trie_entry_insert_child(trie, current,
 267                                         trie_add_leaf(trie, key + pos));
 268                 return;
 269             }
 270         }
 271     }
 272 }
 273
 274 bool trie_lookup(const trie_t *trie, const char *key)
 275 {
 276     if (trie->entries_len == 0) {
 277         return false;
 278     } else {
 279         trie_entry_t *current = trie->entries;
 280         while (true) {
 281             int pos = 0;
 282             if (trie_entry_is_leaf(current)) {
 283                 return trie_entry_match(trie, current, key);
 284             } else if (trie_entry_c_match(trie, current, key, &pos)) {
 285                 key += pos;
 286                 current = trie_entry_child(trie, current, key);
 287                 if (current == NULL) {
 288                     return false;
 289                 }
 290             } else {
 291                 return false;
 292             }
 293         }
 294     }
 295 }
 296
 297
 298 /* Debug {{{1
 299  */
 300
 301 static inline void trie_entry_inspect(const trie_t *trie,
 302                                       const trie_entry_t *entry, int level)
 303 {
 304     static int c_sum = 0;
 305     static int nodes = 0;
 306
 307     ++nodes;
 308     c_sum += entry->c_len;
 309     for (int i = 0 ; i < level ; ++i) {
 310         fputs("  ", stdout);
 311     }
 312     if (entry->c_len == 0) {
 313         fputs("(nil)", stdout);
 314     } else {
 315         const char *c = trie->c + entry->c_offset;
 316         for (int i = 0 ; i < entry->c_len ; ++i) {
 317             if (c[i]) {
 318                 printf("%c ", c[i]);
 319             } else {
 320                 fputs("\\0 ", stdout);
 321             }
 322         }
 323     }
 324     fputs("\n", stdout);
 325     for (int i = 0 ; i < entry->children_len ; ++i) {
 326         trie_entry_inspect(trie, &trie->entries[entry->children[i]], level + 1);
 327     }
 328     if (level == 0) {
 329         printf("Mean char per node: %d\n", c_sum / nodes);
 330     }
 331 }
 332
 333 void trie_inspect(const trie_t *trie)
 334 {
 335     trie_entry_inspect(trie, trie->entries, 0);
 336 }