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