1 /*-------------------------------------------------------------------------*/
2 /**
3 @file dictionary.c
4 @author N. Devillard
5 @brief Implements a dictionary for string variables.
6
7 This module implements a simple dictionary object, i.e. a list
8 of string/string associations. This object is useful to store e.g.
9 informations retrieved from a configuration file (ini files).
10 */
11 /*--------------------------------------------------------------------------*/
12
13 /*---------------------------------------------------------------------------
14 Includes
15 ---------------------------------------------------------------------------*/
16 #include "dictionary.h"
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <unistd.h>
22
23 /** Maximum value size for integers and doubles. */
24 #define MAXVALSZ 1024
25
26 /** Minimal allocated number of entries in a dictionary */
27 #define DICTMINSZ 128
28
29 /** Invalid key token */
30 #define DICT_INVALID_KEY ((char*)-1)
31
32 /*---------------------------------------------------------------------------
33 Private functions
34 ---------------------------------------------------------------------------*/
35
36 /*-------------------------------------------------------------------------*/
37 /**
38 @brief Duplicate a string
39 @param s String to duplicate
40 @return Pointer to a newly allocated string, to be freed with free()
41
42 This is a replacement for strdup(). This implementation is provided
43 for systems that do not have it.
44 */
45 /*--------------------------------------------------------------------------*/
xstrdup(const char * s)46 static char * xstrdup(const char * s)
47 {
48 char * t ;
49 size_t len ;
50 if (!s)
51 return NULL ;
52
53 len = strlen(s) + 1 ;
54 t = (char*) malloc(len) ;
55 if (t) {
56 memcpy(t, s, len) ;
57 }
58 return t ;
59 }
60
61 /*-------------------------------------------------------------------------*/
62 /**
63 @brief Double the size of the dictionary
64 @param d Dictionary to grow
65 @return This function returns non-zero in case of failure
66 */
67 /*--------------------------------------------------------------------------*/
dictionary_grow(dictionary * d)68 static int dictionary_grow(dictionary * d)
69 {
70 char ** new_val ;
71 char ** new_key ;
72 unsigned * new_hash ;
73
74 new_val = (char**) calloc(d->size * 2, sizeof * d->val);
75 new_key = (char**) calloc(d->size * 2, sizeof * d->key);
76 new_hash = (unsigned*) calloc(d->size * 2, sizeof * d->hash);
77 if (!new_val || !new_key || !new_hash) {
78 /* An allocation failed, leave the dictionary unchanged */
79 if (new_val)
80 free(new_val);
81 if (new_key)
82 free(new_key);
83 if (new_hash)
84 free(new_hash);
85 return -1 ;
86 }
87 /* Initialize the newly allocated space */
88 memcpy(new_val, d->val, d->size * sizeof(char *));
89 memcpy(new_key, d->key, d->size * sizeof(char *));
90 memcpy(new_hash, d->hash, d->size * sizeof(unsigned));
91 /* Delete previous data */
92 free(d->val);
93 free(d->key);
94 free(d->hash);
95 /* Actually update the dictionary */
96 d->size *= 2 ;
97 d->val = new_val;
98 d->key = new_key;
99 d->hash = new_hash;
100 return 0 ;
101 }
102
103 /*---------------------------------------------------------------------------
104 Function codes
105 ---------------------------------------------------------------------------*/
106 /*-------------------------------------------------------------------------*/
107 /**
108 @brief Compute the hash key for a string.
109 @param key Character string to use for key.
110 @return 1 unsigned int on at least 32 bits.
111
112 This hash function has been taken from an Article in Dr Dobbs Journal.
113 This is normally a collision-free function, distributing keys evenly.
114 The key is stored anyway in the struct so that collision can be avoided
115 by comparing the key itself in last resort.
116 */
117 /*--------------------------------------------------------------------------*/
dictionary_hash(const char * key)118 unsigned dictionary_hash(const char * key)
119 {
120 size_t len ;
121 unsigned hash ;
122 size_t i ;
123
124 if (!key)
125 return 0 ;
126
127 len = strlen(key);
128 for (hash = 0, i = 0 ; i < len ; i++) {
129 hash += (unsigned)key[i] ;
130 hash += (hash << 10);
131 hash ^= (hash >> 6) ;
132 }
133 hash += (hash << 3);
134 hash ^= (hash >> 11);
135 hash += (hash << 15);
136 return hash ;
137 }
138
139 /*-------------------------------------------------------------------------*/
140 /**
141 @brief Create a new dictionary object.
142 @param size Optional initial size of the dictionary.
143 @return 1 newly allocated dictionary objet.
144
145 This function allocates a new dictionary object of given size and returns
146 it. If you do not know in advance (roughly) the number of entries in the
147 dictionary, give size=0.
148 */
149 /*-------------------------------------------------------------------------*/
dictionary_new(size_t size)150 dictionary * dictionary_new(size_t size)
151 {
152 dictionary * d ;
153
154 /* If no size was specified, allocate space for DICTMINSZ */
155 if (size < DICTMINSZ) size = DICTMINSZ ;
156
157 d = (dictionary*) calloc(1, sizeof * d) ;
158
159 if (d) {
160 d->size = size ;
161 d->val = (char**) calloc(size, sizeof * d->val);
162 d->key = (char**) calloc(size, sizeof * d->key);
163 d->hash = (unsigned*) calloc(size, sizeof * d->hash);
164 }
165 return d ;
166 }
167
168 /*-------------------------------------------------------------------------*/
169 /**
170 @brief Delete a dictionary object
171 @param d dictionary object to deallocate.
172 @return void
173
174 Deallocate a dictionary object and all memory associated to it.
175 */
176 /*--------------------------------------------------------------------------*/
dictionary_del(dictionary * d)177 void dictionary_del(dictionary * d)
178 {
179 ssize_t i ;
180
181 if (d == NULL) return ;
182 for (i = 0 ; i < d->size ; i++) {
183 if (d->key[i] != NULL)
184 free(d->key[i]);
185 if (d->val[i] != NULL)
186 free(d->val[i]);
187 }
188 free(d->val);
189 free(d->key);
190 free(d->hash);
191 free(d);
192 return ;
193 }
194
195 /*-------------------------------------------------------------------------*/
196 /**
197 @brief Get a value from a dictionary.
198 @param d dictionary object to search.
199 @param key Key to look for in the dictionary.
200 @param def Default value to return if key not found.
201 @return 1 pointer to internally allocated character string.
202
203 This function locates a key in a dictionary and returns a pointer to its
204 value, or the passed 'def' pointer if no such key can be found in
205 dictionary. The returned character pointer points to data internal to the
206 dictionary object, you should not try to free it or modify it.
207 */
208 /*--------------------------------------------------------------------------*/
dictionary_get(const dictionary * d,const char * key,const char * def)209 const char * dictionary_get(const dictionary * d, const char * key, const char * def)
210 {
211 unsigned hash ;
212 ssize_t i ;
213
214 hash = dictionary_hash(key);
215 for (i = 0 ; i < d->size ; i++) {
216 if (d->key[i] == NULL)
217 continue ;
218 /* Compare hash */
219 if (hash == d->hash[i]) {
220 /* Compare string, to avoid hash collisions */
221 if (!strcmp(key, d->key[i])) {
222 return d->val[i] ;
223 }
224 }
225 }
226 return def ;
227 }
228
229 /*-------------------------------------------------------------------------*/
230 /**
231 @brief Set a value in a dictionary.
232 @param d dictionary object to modify.
233 @param key Key to modify or add.
234 @param val Value to add.
235 @return int 0 if Ok, anything else otherwise
236
237 If the given key is found in the dictionary, the associated value is
238 replaced by the provided one. If the key cannot be found in the
239 dictionary, it is added to it.
240
241 It is Ok to provide a NULL value for val, but NULL values for the dictionary
242 or the key are considered as errors: the function will return immediately
243 in such a case.
244
245 Notice that if you dictionary_set a variable to NULL, a call to
246 dictionary_get will return a NULL value: the variable will be found, and
247 its value (NULL) is returned. In other words, setting the variable
248 content to NULL is equivalent to deleting the variable from the
249 dictionary. It is not possible (in this implementation) to have a key in
250 the dictionary without value.
251
252 This function returns non-zero in case of failure.
253 */
254 /*--------------------------------------------------------------------------*/
dictionary_set(dictionary * d,const char * key,const char * val)255 int dictionary_set(dictionary * d, const char * key, const char * val)
256 {
257 ssize_t i ;
258 unsigned hash ;
259
260 if (d == NULL || key == NULL) return -1 ;
261
262 /* Compute hash for this key */
263 hash = dictionary_hash(key) ;
264 /* Find if value is already in dictionary */
265 if (d->n > 0) {
266 for (i = 0 ; i < d->size ; i++) {
267 if (d->key[i] == NULL)
268 continue ;
269 if (hash == d->hash[i]) { /* Same hash value */
270 if (!strcmp(key, d->key[i])) { /* Same key */
271 /* Found a value: modify and return */
272 if (d->val[i] != NULL)
273 free(d->val[i]);
274 d->val[i] = (val ? xstrdup(val) : NULL);
275 /* Value has been modified: return */
276 return 0 ;
277 }
278 }
279 }
280 }
281 /* Add a new value */
282 /* See if dictionary needs to grow */
283 if (d->n == d->size) {
284 /* Reached maximum size: reallocate dictionary */
285 if (dictionary_grow(d) != 0)
286 return -1;
287 }
288
289 /* Insert key in the first empty slot. Start at d->n and wrap at
290 d->size. Because d->n < d->size this will necessarily
291 terminate. */
292 for (i = d->n ; d->key[i] ; ) {
293 if (++i == d->size) i = 0;
294 }
295 /* Copy key */
296 d->key[i] = xstrdup(key);
297 d->val[i] = (val ? xstrdup(val) : NULL) ;
298 d->hash[i] = hash;
299 d->n ++ ;
300 return 0 ;
301 }
302
303 /*-------------------------------------------------------------------------*/
304 /**
305 @brief Delete a key in a dictionary
306 @param d dictionary object to modify.
307 @param key Key to remove.
308 @return void
309
310 This function deletes a key in a dictionary. Nothing is done if the
311 key cannot be found.
312 */
313 /*--------------------------------------------------------------------------*/
dictionary_unset(dictionary * d,const char * key)314 void dictionary_unset(dictionary * d, const char * key)
315 {
316 unsigned hash ;
317 ssize_t i ;
318
319 if (key == NULL || d == NULL) {
320 return;
321 }
322
323 hash = dictionary_hash(key);
324 for (i = 0 ; i < d->size ; i++) {
325 if (d->key[i] == NULL)
326 continue ;
327 /* Compare hash */
328 if (hash == d->hash[i]) {
329 /* Compare string, to avoid hash collisions */
330 if (!strcmp(key, d->key[i])) {
331 /* Found key */
332 break ;
333 }
334 }
335 }
336 if (i >= d->size)
337 /* Key not found */
338 return ;
339
340 free(d->key[i]);
341 d->key[i] = NULL ;
342 if (d->val[i] != NULL) {
343 free(d->val[i]);
344 d->val[i] = NULL ;
345 }
346 d->hash[i] = 0 ;
347 d->n -- ;
348 return ;
349 }
350
351 /*-------------------------------------------------------------------------*/
352 /**
353 @brief Dump a dictionary to an opened file pointer.
354 @param d Dictionary to dump
355 @param f Opened file pointer.
356 @return void
357
358 Dumps a dictionary onto an opened file pointer. Key pairs are printed out
359 as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
360 output file pointers.
361 */
362 /*--------------------------------------------------------------------------*/
dictionary_dump(const dictionary * d,FILE * out)363 void dictionary_dump(const dictionary * d, FILE * out)
364 {
365 ssize_t i ;
366
367 if (d == NULL || out == NULL) return ;
368 if (d->n < 1) {
369 fprintf(out, "empty dictionary\n");
370 return ;
371 }
372 for (i = 0 ; i < d->size ; i++) {
373 if (d->key[i]) {
374 fprintf(out, "%20s\t[%s]\n",
375 d->key[i],
376 d->val[i] ? d->val[i] : "UNDEF");
377 }
378 }
379 return ;
380 }
381