]> git.ozlabs.org Git - ccan/blob - ccan/ciniparser/dictionary.c
alloc: reduce page header further, go down to 64k minimum.
[ccan] / ccan / ciniparser / dictionary.c
1 /* Copyright (c) 2000-2007 by Nicolas Devillard.
2  * Copyright (x) 2009 by Tim Post <tinkertim@gmail.com>
3  * MIT License
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a
6  * copy of this software and associated documentation files (the "Software"),
7  * to deal in the Software without restriction, including without limitation
8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9  * and/or sell copies of the Software, and to permit persons to whom the
10  * Software is furnished to do so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be included in
13  * all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21  * DEALINGS IN THE SOFTWARE.
22  */
23
24 /** @addtogroup ciniparser
25  * @{
26  */
27 /**
28  * @file dictionary.c
29  * @author N. Devillard
30  * @date Sep 2007
31  * @version $Revision: 1.27 $
32  * @brief Implements a dictionary for string variables.
33  *
34  * This module implements a simple dictionary object, i.e. a list
35  * of string/string associations. This object is useful to store e.g.
36  * informations retrieved from a configuration file (ini files).
37  */
38
39 #include "dictionary.h"
40
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <string.h>
44 #include <unistd.h>
45
46 /** Maximum value size for integers and doubles. */
47 #define MAXVALSZ        1024
48
49 /** Minimal allocated number of entries in a dictionary */
50 #define DICTMINSZ       128
51
52 /** Invalid key token */
53 #define DICT_INVALID_KEY        ((char*)-1)
54
55 /**
56  * @brief Double the allocated size associated to a pointer
57  * @param size the current allocated size
58  * @return re-allocated pointer on success, NULL on failure
59  */
60 static void *mem_double(void *ptr, int size)
61 {
62         void *newptr;
63
64         newptr = calloc(2 * size, 1);
65         if (newptr == NULL) {
66                 return NULL;
67         }
68         memcpy(newptr, ptr, size);
69         free(ptr);
70         return newptr;
71 }
72
73 /* The remaining exposed functions are documented in dictionary.h */
74
75 unsigned dictionary_hash(char *key)
76 {
77         int len;
78         unsigned hash;
79         int i;
80
81         len = strlen(key);
82         for (hash = 0, i = 0; i < len; i++) {
83                 hash += (unsigned) key[i];
84                 hash += (hash << 10);
85                 hash ^= (hash >> 6);
86         }
87         hash += (hash << 3);
88         hash ^= (hash >> 11);
89         hash += (hash << 15);
90         return hash;
91 }
92
93 dictionary *dictionary_new(int size)
94 {
95         dictionary *d;
96
97         /* If no size was specified, allocate space for DICTMINSZ */
98         if (size<DICTMINSZ) size=DICTMINSZ;
99
100         if (!(d = (dictionary *) calloc(1, sizeof(dictionary)))) {
101                 return NULL;
102         }
103         d->size = size;
104         d->val  = (char **) calloc(size, sizeof(char *));
105         d->key  = (char **) calloc(size, sizeof(char *));
106         d->hash = (unsigned int *) calloc(size, sizeof(unsigned));
107         return d;
108 }
109
110 void dictionary_del(dictionary *d)
111 {
112         int i;
113
114         if (d == NULL)
115                 return;
116         for (i = 0; i < d->size; i++) {
117                 if (d->key[i] != NULL)
118                         free(d->key[i]);
119                 if (d->val[i] != NULL)
120                         free(d->val[i]);
121         }
122         free(d->val);
123         free(d->key);
124         free(d->hash);
125         free(d);
126         return;
127 }
128
129 char *dictionary_get(dictionary *d, char *key, char *def)
130 {
131         unsigned hash;
132         int i;
133
134         hash = dictionary_hash(key);
135         for (i=0; i < d->size; i++) {
136                 if (d->key[i] == NULL)
137                         continue;
138                 /* Compare hash */
139                 if (hash == d->hash[i]) {
140                         /* Compare string, to avoid hash collisions */
141                         if (!strcmp(key, d->key[i])) {
142                                 return d->val[i];
143                         }
144                 }
145         }
146         return def;
147 }
148
149 int dictionary_set(dictionary *d, char *key, char *val)
150 {
151         int i;
152         unsigned hash;
153
154         if (d==NULL || key==NULL)
155                 return -1;
156
157         /* Compute hash for this key */
158         hash = dictionary_hash(key);
159         /* Find if value is already in dictionary */
160         if (d->n > 0) {
161                 for (i = 0; i < d->size; i++) {
162                         if (d->key[i] == NULL)
163                                 continue;
164                         /* Same hash value */
165                         if (hash == d->hash[i]) {
166                                 /* Same key */
167                                 if (!strcmp(key, d->key[i])) {
168                                         /* Found a value: modify and return */
169                                         if (d->val[i] != NULL)
170                                                 free(d->val[i]);
171                                         d->val[i] = val ? strdup(val) : NULL;
172                                         /* Value has been modified: return */
173                                         return 0;
174                                 }
175                         }
176                 }
177         }
178
179         /* Add a new value
180          * See if dictionary needs to grow */
181         if (d->n == d->size) {
182                 /* Reached maximum size: reallocate dictionary */
183                 d->val  = (char **) mem_double(d->val, d->size * sizeof(char *));
184                 d->key  = (char **) mem_double(d->key, d->size * sizeof(char *));
185                 d->hash = (unsigned int *)
186                         mem_double(d->hash, d->size * sizeof(unsigned));
187                 if ((d->val == NULL) || (d->key == NULL) || (d->hash == NULL))
188                         /* Cannot grow dictionary */
189                         return -1;
190                 /* Double size */
191                 d->size *= 2;
192         }
193
194         /* Insert key in the first empty slot */
195         for (i = 0; i < d->size; i++) {
196                 if (d->key[i] == NULL) {
197                         /* Add key here */
198                         break;
199                 }
200         }
201         /* Copy key */
202         d->key[i] = strdup(key);
203         d->val[i] = val ? strdup(val) : NULL;
204         d->hash[i] = hash;
205         d->n ++;
206         return 0;
207 }
208
209 void dictionary_unset(dictionary *d, char *key)
210 {
211         unsigned hash;
212         int i;
213
214         if (key == NULL)
215                 return;
216
217         hash = dictionary_hash(key);
218         for (i = 0; i < d->size; i++) {
219                 if (d->key[i] == NULL)
220                         continue;
221                 /* Compare hash */
222                 if (hash == d->hash[i]) {
223                         /* Compare string, to avoid hash collisions */
224                         if (!strcmp(key, d->key[i])) {
225                                 /* Found key */
226                                 break;
227                         }
228                 }
229         }
230         if (i >= d->size)
231                 /* Key not found */
232                 return;
233
234         free(d->key[i]);
235         d->key[i] = NULL;
236         if (d->val[i]!=NULL) {
237                 free(d->val[i]);
238                 d->val[i] = NULL;
239         }
240         d->hash[i] = 0;
241         d->n --;
242         return;
243 }
244
245 void dictionary_dump(dictionary *d, FILE *out)
246 {
247         int i;
248
249         if (d == NULL || out == NULL)
250                 return;
251         if (d->n < 1) {
252                 fprintf(out, "empty dictionary\n");
253                 return;
254         }
255         for (i = 0; i < d->size; i++) {
256                 if (d->key[i]) {
257                         fprintf(out, "%20s\t[%s]\n",
258                                 d->key[i],
259                                 d->val[i] ? d->val[i] : "UNDEF");
260                 }
261         }
262         return;
263 }
264
265 /** @}
266  */