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);
  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 void trie_grow(trie_t *trie, int delta)
 136 {
 137     p_allocgrow(&trie->entries, trie->entries_len + delta, &trie->entries_size);
 138 }
 139
 140 static int trie_add_leaf(trie_t *trie, const char *key)
 141 {
 142     trie_entry_t *entry;
 143     trie_grow(trie, 1);
 144     entry = &trie->entries[trie->entries_len++];
 145     entry->c     = m_strdup(key);
 146     entry->c_len = m_strlen(key) + 1;
 147     entry->c_own = true;
 148     return trie->entries_len - 1;
 149 }
 150
 151 static void trie_entry_insert_child(trie_t *trie, trie_entry_t *entry, int pchild)
 152 {
 153     const char c = trie->entries[pchild].c[0];
 154     int start = 0;
 155     int end   = entry->children_len;
 156
 157     p_allocgrow(&entry->children, entry->children_len + 1, &entry->children_size);
 158     while (start < end) {
 159         int mid = (start + end) / 2;
 160         trie_entry_t* child = &trie->entries[entry->children[mid]];
 161
 162         if (child->c_len) {
 163             if (child->c[0] == c) {
 164                 abort();
 165             }
 166             if (c < child->c[0]) {
 167                 end = mid;
 168             } else {
 169                 start = mid + 1;
 170             }
 171         } else {
 172             abort();
 173         }
 174     }
 175     memmove(entry->children + start + 1,
 176             entry->children + start,
 177             sizeof(int) * (entry->children_len - start));
 178     entry->children[start] = pchild;
 179 }
 180
 181 static void trie_entry_split(trie_t *trie, trie_entry_t *entry, int pos)
 182 {
 183     trie_entry_t *child;
 184     trie_grow(trie, 2);
 185     child    = &trie->entries[trie->entries_len++];
 186     if (pos == 0) {
 187         child->c     = entry->c;
 188         child->c_len = entry->c_len;
 189         child->c_own = entry->c_own;
 190         entry->c     = NULL;
 191         entry->c_len = 0;
 192         entry->c_own = false;
 193     } else {
 194         child->c     = entry->c + pos;
 195         child->c_len = entry->c_len - pos;
 196         child->c_own = false;
 197         entry->c_len -= pos;
 198     }
 199     child->children      = entry->children;
 200     child->children_len  = entry->children_len;
 201     child->children_size = entry->children_size;
 202     entry->children      = NULL;
 203     entry->children_len  = 0;
 204     entry->children_size = 0;
 205     trie_entry_insert_child(trie, entry, trie->entries_len - 1);
 206 }
 207
 208 void trie_insert(trie_t *trie, const char* key)
 209 {
 210     if (trie->entries_len == 0) {
 211         (void)trie_add_leaf(trie, key);
 212     } else {
 213         trie_entry_t *current = trie->entries;
 214         while (true) {
 215             int pos = 0;
 216             if (trie_entry_c_match(current, key, &pos)) {
 217                 trie_entry_t *next = NULL;
 218                 key += pos;
 219                 next = trie_entry_child(trie, current, key);
 220                 if (next == NULL) {
 221                     trie_entry_insert_child(trie, current,
 222                                             trie_add_leaf(trie, key));
 223                     return;
 224                 } else {
 225                     current = next;
 226                 }
 227             } else {
 228                 trie_entry_split(trie, current, pos);
 229                 trie_entry_insert_child(trie, current,
 230                                         trie_add_leaf(trie, key + pos));
 231                 return;
 232             }
 233         }
 234     }
 235 }
 236
 237 bool trie_lookup(const trie_t *trie, const char *key)
 238 {
 239     if (trie->entries_len == 0) {
 240         return false;
 241     } else {
 242         trie_entry_t *current = trie->entries;
 243         while (true) {
 244             int pos = 0;
 245             if (trie_entry_c_match(current, key, &pos)) {
 246                 if (current->c_len && current->c[current->c_len - 1] == '\0') {
 247                     return true;
 248                 }
 249                 key += pos;
 250                 current = trie_entry_child(trie, current, key);
 251                 if (current == NULL) {
 252                     return false;
 253                 }
 254             } else {
 255                 return false;
 256             }
 257         }
 258     }
 259 }