src/shared/dictionary.c

   1 /*
   2    Copyright (c) 2000-2011 by Nicolas Devillard.
   3    MIT License
   4
   5    Permission is hereby granted, free of charge, to any person obtaining a
   6    copy of this software and associated documentation files (the "Software"),
   7    to deal in the Software without restriction, including without limitation
   8    the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9    and/or sell copies of the Software, and to permit persons to whom the
  10    Software is furnished to do so, subject to the following conditions:
  11
  12    The above copyright notice and this permission notice shall be included in
  13    all copies or substantial portions of the Software.
  14
  15    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21    DEALINGS IN THE SOFTWARE.
  22 */
  23
  24 /*-------------------------------------------------------------------------*/
  25 /**
  26    @file    dictionary.c
  27    @author  N. Devillard
  28    @brief   Implements a dictionary for string variables.
  29
  30    This module implements a simple dictionary object, i.e. a list
  31    of string/string associations. This object is useful to store e.g.
  32    informations retrieved from a configuration file (ini files).
  33 */
  34 /*--------------------------------------------------------------------------*/
  35
  36 /*---------------------------------------------------------------------------
  37                                 Includes
  38  ---------------------------------------------------------------------------*/
  39 #ifdef HAVE_CONFIG_H
  40     #include "config.h"
  41 #endif
  42
  43 #include "dictionary.h"
  44
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <unistd.h>
  49
  50 /** Maximum value size for integers and doubles. */
  51 #define MAXVALSZ    1024
  52
  53 /** Minimal allocated number of entries in a dictionary */
  54 #define DICTMINSZ   128
  55
  56 /** Invalid key token */
  57 #define DICT_INVALID_KEY    ((char*)-1)
  58
  59 /*---------------------------------------------------------------------------
  60                             Private functions
  61  ---------------------------------------------------------------------------*/
  62
  63 /* Doubles the allocated size associated to a pointer */
  64 /* 'size' is the current allocated size. */
  65 static void * mem_double(void * ptr, size_t size)
  66 {
  67     void * newptr ;
  68
  69     newptr = calloc(2*size, 1);
  70     if (newptr==NULL) {
  71         return NULL ;
  72     }
  73     memcpy(newptr, ptr, size);
  74     free(ptr);
  75     return newptr ;
  76 }
  77
  78 /*-------------------------------------------------------------------------*/
  79 /**
  80   @brief    Duplicate a string
  81   @param    s String to duplicate
  82   @return   Pointer to a newly allocated string, to be freed with free()
  83
  84   This is a replacement for strdup(). This implementation is provided
  85   for systems that do not have it.
  86  */
  87 /*--------------------------------------------------------------------------*/
  88 static char * xstrdup(const char * s)
  89 {
  90     char * t ;
  91     if (!s)
  92         return NULL ;
  93     t = (char*)malloc(strlen(s)+1) ;
  94     if (t) {
  95         strcpy(t,s);
  96     }
  97     return t ;
  98 }
  99
 100 /*---------------------------------------------------------------------------
 101                             Function codes
 102  ---------------------------------------------------------------------------*/
 103 /*-------------------------------------------------------------------------*/
 104 /**
 105   @brief    Compute the hash key for a string.
 106   @param    key     Character string to use for key.
 107   @return   1 unsigned int on at least 32 bits.
 108
 109   This hash function has been taken from an Article in Dr Dobbs Journal.
 110   This is normally a collision-free function, distributing keys evenly.
 111   The key is stored anyway in the struct so that collision can be avoided
 112   by comparing the key itself in last resort.
 113  */
 114 /*--------------------------------------------------------------------------*/
 115 unsigned dictionary_hash(const char * key)
 116 {
 117     size_t      len ;
 118     unsigned    hash ;
 119     size_t      i ;
 120
 121     len = strlen(key);
 122     for (hash=0, i=0 ; i<len ; i++) {
 123         hash += (unsigned)key[i] ;
 124         hash += (hash<<10);
 125         hash ^= (hash>>6) ;
 126     }
 127     hash += (hash <<3);
 128     hash ^= (hash >>11);
 129     hash += (hash <<15);
 130     return hash ;
 131 }
 132
 133 /*-------------------------------------------------------------------------*/
 134 /**
 135   @brief    Create a new dictionary object.
 136   @param    size    Optional initial size of the dictionary.
 137   @return   1 newly allocated dictionary objet.
 138
 139   This function allocates a new dictionary object of given size and returns
 140   it. If you do not know in advance (roughly) the number of entries in the
 141   dictionary, give size=0.
 142  */
 143 /*--------------------------------------------------------------------------*/
 144 dictionary * dictionary_new(size_t size)
 145 {
 146     dictionary  *   d ;
 147
 148     /* If no size was specified, allocate space for DICTMINSZ */
 149     if (size<DICTMINSZ) size=DICTMINSZ ;
 150
 151     if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
 152         return NULL;
 153     }
 154     d->size = size ;
 155     d->val  = (char **)calloc(size, sizeof(char*));
 156     d->key  = (char **)calloc(size, sizeof(char*));
 157     d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
 158     return d ;
 159 }
 160
 161 /*-------------------------------------------------------------------------*/
 162 /**
 163   @brief    Delete a dictionary object
 164   @param    d   dictionary object to deallocate.
 165   @return   void
 166
 167   Deallocate a dictionary object and all memory associated to it.
 168  */
 169 /*--------------------------------------------------------------------------*/
 170 void dictionary_del(dictionary * d)
 171 {
 172     int     i ;
 173
 174     if (d==NULL) return ;
 175     for (i=0 ; i<d->size ; i++) {
 176         if (d->key[i]!=NULL)
 177             free(d->key[i]);
 178         if (d->val[i]!=NULL)
 179             free(d->val[i]);
 180     }
 181     free(d->val);
 182     free(d->key);
 183     free(d->hash);
 184     free(d);
 185     return ;
 186 }
 187
 188 /*-------------------------------------------------------------------------*/
 189 /**
 190   @brief    Get a value from a dictionary.
 191   @param    d       dictionary object to search.
 192   @param    key     Key to look for in the dictionary.
 193   @param    def     Default value to return if key not found.
 194   @return   1 pointer to internally allocated character string.
 195
 196   This function locates a key in a dictionary and returns a pointer to its
 197   value, or the passed 'def' pointer if no such key can be found in
 198   dictionary. The returned character pointer points to data internal to the
 199   dictionary object, you should not try to free it or modify it.
 200  */
 201 /*--------------------------------------------------------------------------*/
 202 char * dictionary_get(dictionary * d, const char * key, char * def)
 203 {
 204     unsigned    hash ;
 205     int         i ;
 206
 207     hash = dictionary_hash(key);
 208     for (i=0 ; i<d->size ; i++) {
 209         if (d->key[i]==NULL)
 210             continue ;
 211         /* Compare hash */
 212         if (hash==d->hash[i]) {
 213             /* Compare string, to avoid hash collisions */
 214             if (!strcmp(key, d->key[i])) {
 215                 return d->val[i] ;
 216             }
 217         }
 218     }
 219     return def ;
 220 }
 221
 222 /*-------------------------------------------------------------------------*/
 223 /**
 224   @brief    Set a value in a dictionary.
 225   @param    d       dictionary object to modify.
 226   @param    key     Key to modify or add.
 227   @param    val     Value to add.
 228   @return   int     0 if Ok, anything else otherwise
 229
 230   If the given key is found in the dictionary, the associated value is
 231   replaced by the provided one. If the key cannot be found in the
 232   dictionary, it is added to it.
 233
 234   It is Ok to provide a NULL value for val, but NULL values for the dictionary
 235   or the key are considered as errors: the function will return immediately
 236   in such a case.
 237
 238   Notice that if you dictionary_set a variable to NULL, a call to
 239   dictionary_get will return a NULL value: the variable will be found, and
 240   its value (NULL) is returned. In other words, setting the variable
 241   content to NULL is equivalent to deleting the variable from the
 242   dictionary. It is not possible (in this implementation) to have a key in
 243   the dictionary without value.
 244
 245   This function returns non-zero in case of failure.
 246  */
 247 /*--------------------------------------------------------------------------*/
 248 int dictionary_set(dictionary * d, const char * key, const char * val)
 249 {
 250     int         i ;
 251     unsigned    hash ;
 252
 253     if (d==NULL || key==NULL) return -1 ;
 254
 255     /* Compute hash for this key */
 256     hash = dictionary_hash(key) ;
 257     /* Find if value is already in dictionary */
 258     if (d->n>0) {
 259         for (i=0 ; i<d->size ; i++) {
 260             if (d->key[i]==NULL)
 261                 continue ;
 262             if (hash==d->hash[i]) { /* Same hash value */
 263                 if (!strcmp(key, d->key[i])) {   /* Same key */
 264                     /* Found a value: modify and return */
 265                     if (d->val[i]!=NULL)
 266                         free(d->val[i]);
 267                     d->val[i] = val ? xstrdup(val) : NULL ;
 268                     /* Value has been modified: return */
 269                     return 0 ;
 270                 }
 271             }
 272         }
 273     }
 274     /* Add a new value */
 275     /* See if dictionary needs to grow */
 276     if (d->n==d->size) {
 277
 278         /* Reached maximum size: reallocate dictionary */
 279         d->val  = (char **)mem_double(d->val,  d->size * sizeof(char*)) ;
 280         d->key  = (char **)mem_double(d->key,  d->size * sizeof(char*)) ;
 281         d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
 282         if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
 283             /* Cannot grow dictionary */
 284             return -1 ;
 285         }
 286         /* Double size */
 287         d->size *= 2 ;
 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     int         i ;
 319
 320     if (key == 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(dictionary * d, FILE * out)
 365 {
 366     int     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 }
 382
 383
 384 /* Test code */
 385 #ifdef TESTDIC
 386 #define NVALS 20000
 387 int main(int argc, char *argv[])
 388 {
 389     dictionary  *   d ;
 390     char    *   val ;
 391     int         i ;
 392     char        cval[90] ;
 393
 394     /* Allocate dictionary */
 395     printf("allocating...\n");
 396     d = dictionary_new(0);
 397
 398     /* Set values in dictionary */
 399     printf("setting %d values...\n", NVALS);
 400     for (i=0 ; i<NVALS ; i++) {
 401         sprintf(cval, "%04d", i);
 402         dictionary_set(d, cval, "salut");
 403     }
 404     printf("getting %d values...\n", NVALS);
 405     for (i=0 ; i<NVALS ; i++) {
 406         sprintf(cval, "%04d", i);
 407         val = dictionary_get(d, cval, DICT_INVALID_KEY);
 408         if (val==DICT_INVALID_KEY) {
 409             printf("cannot get value for key [%s]\n", cval);
 410         }
 411     }
 412     printf("unsetting %d values...\n", NVALS);
 413     for (i=0 ; i<NVALS ; i++) {
 414         sprintf(cval, "%04d", i);
 415         dictionary_unset(d, cval);
 416     }
 417     if (d->n != 0) {
 418         printf("error deleting values\n");
 419     }
 420     printf("deallocating...\n");
 421     dictionary_del(d);
 422     return 0 ;
 423 }
 424 #endif
 425 /* vim: set ts=4 et sw=4 tw=75 */