libatalk/iniparser/dictionary.c

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