2 * ast.c: Support routines for put/get
4 * Copyright (C) 2008-2011 David Lutterkort
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.
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.
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
20 * Author: David Lutterkort <dlutter@redhat.com>
30 /* A dictionary that maps key to a list of (skel, dict) */
32 struct dict_entry *next;
37 /* Associates a KEY with a list of skel/dict pairs.
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.
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.
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 */
53 /* Nodes are kept sorted by their key, with NULL being smaller than any
56 struct dict_node **nodes;
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;
66 struct dict *make_dict(char *key, struct skel *skel, struct dict *subdict) {
67 struct dict *dict = NULL;
70 if (ALLOC_N(dict->nodes, dict_initial_size) < 0)
72 if (ALLOC(dict->nodes[0]) < 0)
74 if (ALLOC(dict->nodes[0]->entry) < 0)
77 dict->size = dict_initial_size;
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;
88 FREE(dict->nodes[0]->entry);
96 void free_dict(struct dict *dict) {
100 for (int i=0; i < dict->used; i++) {
101 struct dict_node *node = dict->nodes[i];
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);
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.
123 static int dict_pos(struct dict *dict, const char *key) {
125 return (dict->nodes[0]->key == NULL) ? 0 : -1;
128 int l = dict->nodes[0]->key == NULL ? 1 : 0;
132 int cmp = strcmp(dict->nodes[m]->key, key);
143 static int dict_expand(struct dict *dict) {
144 uint32_t size = dict->size;
146 if (size == dict_max_size)
148 if (size > dict_max_expansion)
149 size += dict_max_expansion;
152 if (size > dict_max_size)
153 size = dict_max_size;
155 return REALLOC_N(dict->nodes, dict->size);
158 int dict_append(struct dict **dict, struct dict *d2) {
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);
173 if (d1->size == d1->used) {
174 if (dict_expand(d1) < 0)
177 memmove(d1->nodes + i1 + 1, d1->nodes + i1,
178 sizeof(*d1->nodes) * (d1->used - i1));
182 struct dict_node *n1 = d1->nodes[i1];
183 list_tail_cons(n1->entry, n1->mark, n2->entry);
193 void dict_lookup(const char *key, struct dict *dict,
194 struct skel **skel, struct dict **subdict) {
198 if (! dict->marked) {
199 for (int i=0; i < dict->used; i++) {
200 dict->nodes[i]->mark = dict->nodes[i]->entry;
204 int p = dict_pos(dict, key);
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;
220 * indent-tabs-mode: nil