testing/mozbase/mozprocess/tests/iniparser/dictionary.c@6474c204b198
testing/mozbase/mozprocess/tests/iniparser/dictionary.c
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 /*-------------------------------------------------------------------------*/
2 /**
3 @file dictionary.c
4 @author N. Devillard
5 @date Sep 2007
6 @version $Revision: 1.27 $
7 @brief Implements a dictionary for string variables.
9 This module implements a simple dictionary object, i.e. a list
10 of string/string associations. This object is useful to store e.g.
11 informations retrieved from a configuration file (ini files).
12 */
13 /*--------------------------------------------------------------------------*/
15 /*
16 $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $
17 $Revision: 1.27 $
18 */
19 /*---------------------------------------------------------------------------
20 Includes
21 ---------------------------------------------------------------------------*/
22 #include "dictionary.h"
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #ifndef _WIN32
28 #include <unistd.h>
29 #endif
31 /** Maximum value size for integers and doubles. */
32 #define MAXVALSZ 1024
34 /** Minimal allocated number of entries in a dictionary */
35 #define DICTMINSZ 128
37 /** Invalid key token */
38 #define DICT_INVALID_KEY ((char*)-1)
40 /*---------------------------------------------------------------------------
41 Private functions
42 ---------------------------------------------------------------------------*/
44 /* Doubles the allocated size associated to a pointer */
45 /* 'size' is the current allocated size. */
46 static void * mem_double(void * ptr, int size)
47 {
48 void * newptr ;
50 newptr = calloc(2*size, 1);
51 if (newptr==NULL) {
52 return NULL ;
53 }
54 memcpy(newptr, ptr, size);
55 free(ptr);
56 return newptr ;
57 }
59 /*-------------------------------------------------------------------------*/
60 /**
61 @brief Duplicate a string
62 @param s String to duplicate
63 @return Pointer to a newly allocated string, to be freed with free()
65 This is a replacement for strdup(). This implementation is provided
66 for systems that do not have it.
67 */
68 /*--------------------------------------------------------------------------*/
69 static char * xstrdup(char * s)
70 {
71 char * t ;
72 if (!s)
73 return NULL ;
74 t = malloc(strlen(s)+1) ;
75 if (t) {
76 strcpy(t,s);
77 }
78 return t ;
79 }
81 /*---------------------------------------------------------------------------
82 Function codes
83 ---------------------------------------------------------------------------*/
84 /*-------------------------------------------------------------------------*/
85 /**
86 @brief Compute the hash key for a string.
87 @param key Character string to use for key.
88 @return 1 unsigned int on at least 32 bits.
90 This hash function has been taken from an Article in Dr Dobbs Journal.
91 This is normally a collision-free function, distributing keys evenly.
92 The key is stored anyway in the struct so that collision can be avoided
93 by comparing the key itself in last resort.
94 */
95 /*--------------------------------------------------------------------------*/
96 unsigned dictionary_hash(char * key)
97 {
98 int len ;
99 unsigned hash ;
100 int i ;
102 len = strlen(key);
103 for (hash=0, i=0 ; i<len ; i++) {
104 hash += (unsigned)key[i] ;
105 hash += (hash<<10);
106 hash ^= (hash>>6) ;
107 }
108 hash += (hash <<3);
109 hash ^= (hash >>11);
110 hash += (hash <<15);
111 return hash ;
112 }
114 /*-------------------------------------------------------------------------*/
115 /**
116 @brief Create a new dictionary object.
117 @param size Optional initial size of the dictionary.
118 @return 1 newly allocated dictionary objet.
120 This function allocates a new dictionary object of given size and returns
121 it. If you do not know in advance (roughly) the number of entries in the
122 dictionary, give size=0.
123 */
124 /*--------------------------------------------------------------------------*/
125 dictionary * dictionary_new(int size)
126 {
127 dictionary * d ;
129 /* If no size was specified, allocate space for DICTMINSZ */
130 if (size<DICTMINSZ) size=DICTMINSZ ;
132 if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
133 return NULL;
134 }
135 d->size = size ;
136 d->val = (char **)calloc(size, sizeof(char*));
137 d->key = (char **)calloc(size, sizeof(char*));
138 d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
139 return d ;
140 }
142 /*-------------------------------------------------------------------------*/
143 /**
144 @brief Delete a dictionary object
145 @param d dictionary object to deallocate.
146 @return void
148 Deallocate a dictionary object and all memory associated to it.
149 */
150 /*--------------------------------------------------------------------------*/
151 void dictionary_del(dictionary * d)
152 {
153 int i ;
155 if (d==NULL) return ;
156 for (i=0 ; i<d->size ; i++) {
157 if (d->key[i]!=NULL)
158 free(d->key[i]);
159 if (d->val[i]!=NULL)
160 free(d->val[i]);
161 }
162 free(d->val);
163 free(d->key);
164 free(d->hash);
165 free(d);
166 return ;
167 }
169 /*-------------------------------------------------------------------------*/
170 /**
171 @brief Get a value from a dictionary.
172 @param d dictionary object to search.
173 @param key Key to look for in the dictionary.
174 @param def Default value to return if key not found.
175 @return 1 pointer to internally allocated character string.
177 This function locates a key in a dictionary and returns a pointer to its
178 value, or the passed 'def' pointer if no such key can be found in
179 dictionary. The returned character pointer points to data internal to the
180 dictionary object, you should not try to free it or modify it.
181 */
182 /*--------------------------------------------------------------------------*/
183 char * dictionary_get(dictionary * d, char * key, char * def)
184 {
185 unsigned hash ;
186 int i ;
188 hash = dictionary_hash(key);
189 for (i=0 ; i<d->size ; i++) {
190 if (d->key[i]==NULL)
191 continue ;
192 /* Compare hash */
193 if (hash==d->hash[i]) {
194 /* Compare string, to avoid hash collisions */
195 if (!strcmp(key, d->key[i])) {
196 return d->val[i] ;
197 }
198 }
199 }
200 return def ;
201 }
203 /*-------------------------------------------------------------------------*/
204 /**
205 @brief Set a value in a dictionary.
206 @param d dictionary object to modify.
207 @param key Key to modify or add.
208 @param val Value to add.
209 @return int 0 if Ok, anything else otherwise
211 If the given key is found in the dictionary, the associated value is
212 replaced by the provided one. If the key cannot be found in the
213 dictionary, it is added to it.
215 It is Ok to provide a NULL value for val, but NULL values for the dictionary
216 or the key are considered as errors: the function will return immediately
217 in such a case.
219 Notice that if you dictionary_set a variable to NULL, a call to
220 dictionary_get will return a NULL value: the variable will be found, and
221 its value (NULL) is returned. In other words, setting the variable
222 content to NULL is equivalent to deleting the variable from the
223 dictionary. It is not possible (in this implementation) to have a key in
224 the dictionary without value.
226 This function returns non-zero in case of failure.
227 */
228 /*--------------------------------------------------------------------------*/
229 int dictionary_set(dictionary * d, char * key, char * val)
230 {
231 int i ;
232 unsigned hash ;
234 if (d==NULL || key==NULL) return -1 ;
236 /* Compute hash for this key */
237 hash = dictionary_hash(key) ;
238 /* Find if value is already in dictionary */
239 if (d->n>0) {
240 for (i=0 ; i<d->size ; i++) {
241 if (d->key[i]==NULL)
242 continue ;
243 if (hash==d->hash[i]) { /* Same hash value */
244 if (!strcmp(key, d->key[i])) { /* Same key */
245 /* Found a value: modify and return */
246 if (d->val[i]!=NULL)
247 free(d->val[i]);
248 d->val[i] = val ? xstrdup(val) : NULL ;
249 /* Value has been modified: return */
250 return 0 ;
251 }
252 }
253 }
254 }
255 /* Add a new value */
256 /* See if dictionary needs to grow */
257 if (d->n==d->size) {
259 /* Reached maximum size: reallocate dictionary */
260 d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ;
261 d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ;
262 d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
263 if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
264 /* Cannot grow dictionary */
265 return -1 ;
266 }
267 /* Double size */
268 d->size *= 2 ;
269 }
271 /* Insert key in the first empty slot */
272 for (i=0 ; i<d->size ; i++) {
273 if (d->key[i]==NULL) {
274 /* Add key here */
275 break ;
276 }
277 }
278 /* Copy key */
279 d->key[i] = xstrdup(key);
280 d->val[i] = val ? xstrdup(val) : NULL ;
281 d->hash[i] = hash;
282 d->n ++ ;
283 return 0 ;
284 }
286 /*-------------------------------------------------------------------------*/
287 /**
288 @brief Delete a key in a dictionary
289 @param d dictionary object to modify.
290 @param key Key to remove.
291 @return void
293 This function deletes a key in a dictionary. Nothing is done if the
294 key cannot be found.
295 */
296 /*--------------------------------------------------------------------------*/
297 void dictionary_unset(dictionary * d, char * key)
298 {
299 unsigned hash ;
300 int i ;
302 if (key == NULL) {
303 return;
304 }
306 hash = dictionary_hash(key);
307 for (i=0 ; i<d->size ; i++) {
308 if (d->key[i]==NULL)
309 continue ;
310 /* Compare hash */
311 if (hash==d->hash[i]) {
312 /* Compare string, to avoid hash collisions */
313 if (!strcmp(key, d->key[i])) {
314 /* Found key */
315 break ;
316 }
317 }
318 }
319 if (i>=d->size)
320 /* Key not found */
321 return ;
323 free(d->key[i]);
324 d->key[i] = NULL ;
325 if (d->val[i]!=NULL) {
326 free(d->val[i]);
327 d->val[i] = NULL ;
328 }
329 d->hash[i] = 0 ;
330 d->n -- ;
331 return ;
332 }
334 /*-------------------------------------------------------------------------*/
335 /**
336 @brief Dump a dictionary to an opened file pointer.
337 @param d Dictionary to dump
338 @param f Opened file pointer.
339 @return void
341 Dumps a dictionary onto an opened file pointer. Key pairs are printed out
342 as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
343 output file pointers.
344 */
345 /*--------------------------------------------------------------------------*/
346 void dictionary_dump(dictionary * d, FILE * out)
347 {
348 int i ;
350 if (d==NULL || out==NULL) return ;
351 if (d->n<1) {
352 fprintf(out, "empty dictionary\n");
353 return ;
354 }
355 for (i=0 ; i<d->size ; i++) {
356 if (d->key[i]) {
357 fprintf(out, "%20s\t[%s]\n",
358 d->key[i],
359 d->val[i] ? d->val[i] : "UNDEF");
360 }
361 }
362 return ;
363 }
366 /* Test code */
367 #ifdef TESTDIC
368 #define NVALS 20000
369 int main(int argc, char *argv[])
370 {
371 dictionary * d ;
372 char * val ;
373 int i ;
374 char cval[90] ;
376 /* Allocate dictionary */
377 printf("allocating...\n");
378 d = dictionary_new(0);
380 /* Set values in dictionary */
381 printf("setting %d values...\n", NVALS);
382 for (i=0 ; i<NVALS ; i++) {
383 sprintf(cval, "%04d", i);
384 dictionary_set(d, cval, "salut");
385 }
386 printf("getting %d values...\n", NVALS);
387 for (i=0 ; i<NVALS ; i++) {
388 sprintf(cval, "%04d", i);
389 val = dictionary_get(d, cval, DICT_INVALID_KEY);
390 if (val==DICT_INVALID_KEY) {
391 printf("cannot get value for key [%s]\n", cval);
392 }
393 }
394 printf("unsetting %d values...\n", NVALS);
395 for (i=0 ; i<NVALS ; i++) {
396 sprintf(cval, "%04d", i);
397 dictionary_unset(d, cval);
398 }
399 if (d->n != 0) {
400 printf("error deleting values\n");
401 }
402 printf("deallocating...\n");
403 dictionary_del(d);
404 return 0 ;
405 }
406 #endif
407 /* vim: set ts=4 et sw=4 tw=75 */
