libatalk/iniparser/dictionary.c

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