src/ast.c

   1 /*
   2  * ast.c: Support routines for put/get
   3  *
   4  * Copyright (C) 2008-2015 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 #include <config.h>
  24 #include <stdint.h>
  25
  26 #include "internal.h"
  27 #include "memory.h"
  28 #include "lens.h"
  29
  30 /* A dictionary that maps key to a list of (skel, dict) */
  31 struct dict_entry {
  32     struct dict_entry *next;
  33     struct skel *skel;
  34     struct dict *dict;
  35 };
  36
  37 /* Associates a KEY with a list of skel/dict pairs.
  38
  39    Dicts are used in two phases: first they are constructed, through
  40    repeated calls to dict_append. In the second phase, items are looked up
  41    and removed from the dict.
  42
  43    During construction, MARK points to the end of the list ENTRY. Once
  44    construction is done, MARK points to the head of that list, and ENTRY is
  45    moved towards the tail everytime an item is looked up.
  46 */
  47 struct dict_node {
  48     char *key;
  49     struct dict_entry *entry; /* This will change as entries are looked up */
  50     struct dict_entry *mark;  /* Pointer to initial entry, will never change */
  51 };
  52
  53 /* Nodes are kept sorted by their key, with NULL being smaller than any
  54    string */
  55 struct dict {
  56     struct dict_node **nodes;
  57     uint32_t          size;
  58     uint32_t          used;
  59     bool              marked;
  60 };
  61
  62 static const int dict_initial_size = 2;
  63 static const int dict_max_expansion = 128;
  64 static const uint32_t dict_max_size = (1<<24) - 1;
  65
  66 struct dict *make_dict(char *key, struct skel *skel, struct dict *subdict) {
  67     struct dict *dict = NULL;
  68     if (ALLOC(dict) < 0)
  69         goto error;
  70     if (ALLOC_N(dict->nodes, dict_initial_size) < 0)
  71         goto error;
  72     if (ALLOC(dict->nodes[0]) < 0)
  73         goto error;
  74     if (ALLOC(dict->nodes[0]->entry) < 0)
  75         goto error;
  76
  77     dict->size = dict_initial_size;
  78     dict->used = 1;
  79     dict->nodes[0]->key = key;
  80     dict->nodes[0]->entry->skel = skel;
  81     dict->nodes[0]->entry->dict = subdict;
  82     dict->nodes[0]->mark = dict->nodes[0]->entry;
  83
  84     return dict;
  85  error:
  86     if (dict->nodes) {
  87         if (dict->nodes[0])
  88             FREE(dict->nodes[0]->entry);
  89         FREE(dict->nodes[0]);
  90     }
  91     FREE(dict->nodes);
  92     FREE(dict);
  93     return NULL;
  94 }
  95
  96 void free_dict(struct dict *dict) {
  97     if (dict == NULL)
  98         return;
  99
 100     for (int i=0; i < dict->used; i++) {
 101         struct dict_node *node = dict->nodes[i];
 102         if (! dict->marked)
 103             node->mark = node->entry;
 104         while (node->mark != NULL) {
 105             struct dict_entry *del = node->mark;
 106             node->mark = del->next;
 107             free_skel(del->skel);
 108             free_dict(del->dict);
 109             free(del);
 110         }
 111         free(node->key);
 112         FREE(node);
 113     }
 114     FREE(dict->nodes);
 115     FREE(dict);
 116 }
 117
 118 /* Return the position of KEY in DICT as an integer between 0 and
 119    DICT->USED.  If KEY is not in DICT, return a negative number P such that
 120    -(P + 1) is the position at which KEY must be inserted to keep the keys
 121    of the nodes in DICT sorted.
 122 */
 123 static int dict_pos(struct dict *dict, const char *key) {
 124     if (key == NULL) {
 125         return (dict->nodes[0]->key == NULL) ? 0 : -1;
 126     }
 127
 128     int l = dict->nodes[0]->key == NULL ? 1 : 0;
 129     int h = dict->used;
 130     while (l < h) {
 131         int m = (l + h)/2;
 132         int cmp = strcmp(dict->nodes[m]->key, key);
 133         if (cmp > 0)
 134             h = m;
 135         else if (cmp < 0)
 136             l = m + 1;
 137         else
 138             return m;
 139     }
 140     return -(l + 1);
 141 }
 142
 143 static int dict_expand(struct dict *dict) {
 144     uint32_t size = dict->size;
 145
 146     if (size == dict_max_size)
 147         return -1;
 148     if (size > dict_max_expansion)
 149         size += dict_max_expansion;
 150     else
 151         size *= 2;
 152     if (size > dict_max_size)
 153         size = dict_max_size;
 154     dict->size = size;
 155     return REALLOC_N(dict->nodes, dict->size);
 156 }
 157
 158 int dict_append(struct dict **dict, struct dict *d2) {
 159     if (d2 == NULL)
 160         return 0;
 161
 162     if (*dict == NULL) {
 163         *dict = d2;
 164         return 0;
 165     }
 166
 167     struct dict *d1 = *dict;
 168     for (int i2 = 0; i2 < d2->used; i2++) {
 169         struct dict_node *n2 = d2->nodes[i2];
 170         int i1 = dict_pos(d1, n2->key);
 171         if (i1 < 0) {
 172             i1 = - i1 - 1;
 173             if (d1->size == d1->used) {
 174                 if (dict_expand(d1) < 0)
 175                     return -1;
 176             }
 177             memmove(d1->nodes + i1 + 1, d1->nodes + i1,
 178                     sizeof(*d1->nodes) * (d1->used - i1));
 179             d1->nodes[i1] = n2;
 180             d1->used += 1;
 181         } else {
 182             struct dict_node *n1 = d1->nodes[i1];
 183             list_tail_cons(n1->entry, n1->mark, n2->entry);
 184             FREE(n2->key);
 185             FREE(n2);
 186         }
 187     }
 188     FREE(d2->nodes);
 189     FREE(d2);
 190     return 0;
 191 }
 192
 193 void dict_lookup(const char *key, struct dict *dict,
 194                  struct skel **skel, struct dict **subdict) {
 195     *skel = NULL;
 196     *subdict = NULL;
 197     if (dict != NULL) {
 198         if (! dict->marked) {
 199             for (int i=0; i < dict->used; i++) {
 200                 dict->nodes[i]->mark = dict->nodes[i]->entry;
 201             }
 202             dict->marked = 1;
 203         }
 204         int p = dict_pos(dict, key);
 205         if (p >= 0) {
 206             struct dict_node *node = dict->nodes[p];
 207             if (node->entry != NULL) {
 208                 *skel = node->entry->skel;
 209                 *subdict = node->entry->dict;
 210                 node->entry = node->entry->next;
 211             }
 212         }
 213     }
 214 }
 215
 216
 217
 218 /*
 219  * Local variables:
 220  *  indent-tabs-mode: nil
 221  *  c-indent-level: 4
 222  *  c-basic-offset: 4
 223  *  tab-width: 4
 224  * End:
 225  */