Commit | Line | Data |
---|---|---|
33858ce2 AT |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*-------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | /*--------------------------------------------------------------------------*/ | |
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 | } |