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