|
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. */ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 /*--------------------------------------------------------------------------*/ |
|
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 |
|
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 */ |