| 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 | } |