dictionary.c

00001 /*-------------------------------------------------------------------------*/
00002 /**
00003    @file    dictionary.c
00004    @author  N. Devillard
00005    @brief   Implements a dictionary for string variables.
00006 
00007    This module implements a simple dictionary object, i.e. a list
00008    of string/string associations. This object is useful to store e.g.
00009    informations retrieved from a configuration file (ini files).
00010 */
00011 /*--------------------------------------------------------------------------*/
00012 
00013 /*---------------------------------------------------------------------------
00014                                 Includes
00015  ---------------------------------------------------------------------------*/
00016 #include "dictionary.h"
00017 
00018 #include <stdio.h>
00019 #include <stdlib.h>
00020 #include <string.h>
00021 //#include <unistd.h> // Not required for MBED
00022 
00023 /** Maximum value size for integers and doubles. */
00024 #define MAXVALSZ    1024
00025 
00026 /** Minimal allocated number of entries in a dictionary */
00027 #define DICTMINSZ   128
00028 
00029 /** Invalid key token */
00030 #define DICT_INVALID_KEY    ((char*)-1)
00031 
00032 /*---------------------------------------------------------------------------
00033                             Private functions
00034  ---------------------------------------------------------------------------*/
00035 
00036 /* Doubles the allocated size associated to a pointer */
00037 /* 'size' is the current allocated size. */
00038 static void * mem_double(void * ptr, int size)
00039 {
00040     void * newptr ;
00041  
00042     newptr = calloc(2*size, 1);
00043     if (newptr==NULL) {
00044         return NULL ;
00045     }
00046     memcpy(newptr, ptr, size);
00047     free(ptr);
00048     return newptr ;
00049 }
00050 
00051 /*-------------------------------------------------------------------------*/
00052 /**
00053   @brief    Duplicate a string
00054   @param    s String to duplicate
00055   @return   Pointer to a newly allocated string, to be freed with free()
00056 
00057   This is a replacement for strdup(). This implementation is provided
00058   for systems that do not have it.
00059  */
00060 /*--------------------------------------------------------------------------*/
00061 static char * xstrdup(const char * s)
00062 {
00063     char * t ;
00064     if (!s)
00065         return NULL ;
00066     t = (char*)malloc(strlen(s)+1) ;
00067     if (t) {
00068         strcpy(t,s);
00069     }
00070     return t ;
00071 }
00072 
00073 /*---------------------------------------------------------------------------
00074                             Function codes
00075  ---------------------------------------------------------------------------*/
00076 /*-------------------------------------------------------------------------*/
00077 /**
00078   @brief    Compute the hash key for a string.
00079   @param    key     Character string to use for key.
00080   @return   1 unsigned int on at least 32 bits.
00081 
00082   This hash function has been taken from an Article in Dr Dobbs Journal.
00083   This is normally a collision-free function, distributing keys evenly.
00084   The key is stored anyway in the struct so that collision can be avoided
00085   by comparing the key itself in last resort.
00086  */
00087 /*--------------------------------------------------------------------------*/
00088 unsigned dictionary_hash(const char * key)
00089 {
00090     int         len ;
00091     unsigned    hash ;
00092     int         i ;
00093 
00094     len = strlen(key);
00095     for (hash=0, i=0 ; i<len ; i++) {
00096         hash += (unsigned)key[i] ;
00097         hash += (hash<<10);
00098         hash ^= (hash>>6) ;
00099     }
00100     hash += (hash <<3);
00101     hash ^= (hash >>11);
00102     hash += (hash <<15);
00103     return hash ;
00104 }
00105 
00106 /*-------------------------------------------------------------------------*/
00107 /**
00108   @brief    Create a new dictionary object.
00109   @param    size    Optional initial size of the dictionary.
00110   @return   1 newly allocated dictionary objet.
00111 
00112   This function allocates a new dictionary object of given size and returns
00113   it. If you do not know in advance (roughly) the number of entries in the
00114   dictionary, give size=0.
00115  */
00116 /*--------------------------------------------------------------------------*/
00117 dictionary * dictionary_new(int size)
00118 {
00119     dictionary  *   d ;
00120 
00121     /* If no size was specified, allocate space for DICTMINSZ */
00122     if (size<DICTMINSZ) size=DICTMINSZ ;
00123 
00124     if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
00125         return NULL;
00126     }
00127     d->size = size ;
00128     d->val  = (char **)calloc(size, sizeof(char*));
00129     d->key  = (char **)calloc(size, sizeof(char*));
00130     d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
00131     return d ;
00132 }
00133 
00134 /*-------------------------------------------------------------------------*/
00135 /**
00136   @brief    Delete a dictionary object
00137   @param    d   dictionary object to deallocate.
00138   @return   void
00139 
00140   Deallocate a dictionary object and all memory associated to it.
00141  */
00142 /*--------------------------------------------------------------------------*/
00143 void dictionary_del(dictionary * d)
00144 {
00145     int     i ;
00146 
00147     if (d==NULL) return ;
00148     for (i=0 ; i<d->size ; i++) {
00149         if (d->key[i]!=NULL)
00150             free(d->key[i]);
00151         if (d->val[i]!=NULL)
00152             free(d->val[i]);
00153     }
00154     free(d->val);
00155     free(d->key);
00156     free(d->hash);
00157     free(d);
00158     return ;
00159 }
00160 
00161 /*-------------------------------------------------------------------------*/
00162 /**
00163   @brief    Get a value from a dictionary.
00164   @param    d       dictionary object to search.
00165   @param    key     Key to look for in the dictionary.
00166   @param    def     Default value to return if key not found.
00167   @return   1 pointer to internally allocated character string.
00168 
00169   This function locates a key in a dictionary and returns a pointer to its
00170   value, or the passed 'def' pointer if no such key can be found in
00171   dictionary. The returned character pointer points to data internal to the
00172   dictionary object, you should not try to free it or modify it.
00173  */
00174 /*--------------------------------------------------------------------------*/
00175 char * dictionary_get(dictionary * d, const char * key, char * def)
00176 {
00177     unsigned    hash ;
00178     int         i ;
00179 
00180     hash = dictionary_hash(key);
00181     for (i=0 ; i<d->size ; i++) {
00182         if (d->key[i]==NULL)
00183             continue ;
00184         /* Compare hash */
00185         if (hash==d->hash[i]) {
00186             /* Compare string, to avoid hash collisions */
00187             if (!strcmp(key, d->key[i])) {
00188                 return d->val[i] ;
00189             }
00190         }
00191     }
00192     return def ;
00193 }
00194 
00195 /*-------------------------------------------------------------------------*/
00196 /**
00197   @brief    Set a value in a dictionary.
00198   @param    d       dictionary object to modify.
00199   @param    key     Key to modify or add.
00200   @param    val     Value to add.
00201   @return   int     0 if Ok, anything else otherwise
00202 
00203   If the given key is found in the dictionary, the associated value is
00204   replaced by the provided one. If the key cannot be found in the
00205   dictionary, it is added to it.
00206 
00207   It is Ok to provide a NULL value for val, but NULL values for the dictionary
00208   or the key are considered as errors: the function will return immediately
00209   in such a case.
00210 
00211   Notice that if you dictionary_set a variable to NULL, a call to
00212   dictionary_get will return a NULL value: the variable will be found, and
00213   its value (NULL) is returned. In other words, setting the variable
00214   content to NULL is equivalent to deleting the variable from the
00215   dictionary. It is not possible (in this implementation) to have a key in
00216   the dictionary without value.
00217 
00218   This function returns non-zero in case of failure.
00219  */
00220 /*--------------------------------------------------------------------------*/
00221 int dictionary_set(dictionary * d, const char * key, const char * val)
00222 {
00223     int         i ;
00224     unsigned    hash ;
00225 
00226     if (d==NULL || key==NULL) return -1 ;
00227     
00228     /* Compute hash for this key */
00229     hash = dictionary_hash(key) ;
00230     /* Find if value is already in dictionary */
00231     if (d->n>0) {
00232         for (i=0 ; i<d->size ; i++) {
00233             if (d->key[i]==NULL)
00234                 continue ;
00235             if (hash==d->hash[i]) { /* Same hash value */
00236                 if (!strcmp(key, d->key[i])) {   /* Same key */
00237                     /* Found a value: modify and return */
00238                     if (d->val[i]!=NULL)
00239                         free(d->val[i]);
00240                     d->val[i] = val ? xstrdup(val) : NULL ;
00241                     /* Value has been modified: return */
00242                     return 0 ;
00243                 }
00244             }
00245         }
00246     }
00247     /* Add a new value */
00248     /* See if dictionary needs to grow */
00249     if (d->n==d->size) {
00250 
00251         /* Reached maximum size: reallocate dictionary */
00252         d->val  = (char **)mem_double(d->val,  d->size * sizeof(char*)) ;
00253         d->key  = (char **)mem_double(d->key,  d->size * sizeof(char*)) ;
00254         d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
00255         if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
00256             /* Cannot grow dictionary */
00257             return -1 ;
00258         }
00259         /* Double size */
00260         d->size *= 2 ;
00261     }
00262 
00263     /* Insert key in the first empty slot. Start at d->n and wrap at
00264        d->size. Because d->n < d->size this will necessarily
00265        terminate. */
00266     for (i=d->n ; d->key[i] ; ) {
00267         if(++i == d->size) i = 0;
00268     }
00269     /* Copy key */
00270     d->key[i]  = xstrdup(key);
00271     d->val[i]  = val ? xstrdup(val) : NULL ;
00272     d->hash[i] = hash;
00273     d->n ++ ;
00274     return 0 ;
00275 }
00276 
00277 /*-------------------------------------------------------------------------*/
00278 /**
00279   @brief    Delete a key in a dictionary
00280   @param    d       dictionary object to modify.
00281   @param    key     Key to remove.
00282   @return   void
00283 
00284   This function deletes a key in a dictionary. Nothing is done if the
00285   key cannot be found.
00286  */
00287 /*--------------------------------------------------------------------------*/
00288 void dictionary_unset(dictionary * d, const char * key)
00289 {
00290     unsigned    hash ;
00291     int         i ;
00292 
00293     if (key == NULL) {
00294         return;
00295     }
00296 
00297     hash = dictionary_hash(key);
00298     for (i=0 ; i<d->size ; i++) {
00299         if (d->key[i]==NULL)
00300             continue ;
00301         /* Compare hash */
00302         if (hash==d->hash[i]) {
00303             /* Compare string, to avoid hash collisions */
00304             if (!strcmp(key, d->key[i])) {
00305                 /* Found key */
00306                 break ;
00307             }
00308         }
00309     }
00310     if (i>=d->size)
00311         /* Key not found */
00312         return ;
00313 
00314     free(d->key[i]);
00315     d->key[i] = NULL ;
00316     if (d->val[i]!=NULL) {
00317         free(d->val[i]);
00318         d->val[i] = NULL ;
00319     }
00320     d->hash[i] = 0 ;
00321     d->n -- ;
00322     return ;
00323 }
00324 
00325 /*-------------------------------------------------------------------------*/
00326 /**
00327   @brief    Dump a dictionary to an opened file pointer.
00328   @param    d   Dictionary to dump
00329   @param    f   Opened file pointer.
00330   @return   void
00331 
00332   Dumps a dictionary onto an opened file pointer. Key pairs are printed out
00333   as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
00334   output file pointers.
00335  */
00336 /*--------------------------------------------------------------------------*/
00337 void dictionary_dump(dictionary * d, FILE * out)
00338 {
00339     int     i ;
00340 
00341     if (d==NULL || out==NULL) return ;
00342     if (d->n<1) {
00343         fprintf(out, "empty dictionary\n");
00344         return ;
00345     }
00346     for (i=0 ; i<d->size ; i++) {
00347         if (d->key[i]) {
00348             fprintf(out, "%20s\t[%s]\n",
00349                     d->key[i],
00350                     d->val[i] ? d->val[i] : "UNDEF");
00351         }
00352     }
00353     return ;
00354 }
00355 
00356 
00357 /* Test code */
00358 #ifdef TESTDIC
00359 #define NVALS 20000
00360 int main(int argc, char *argv[])
00361 {
00362     dictionary  *   d ;
00363     char    *   val ;
00364     int         i ;
00365     char        cval[90] ;
00366 
00367     /* Allocate dictionary */
00368     printf("allocating...\n");
00369     d = dictionary_new(0);
00370     
00371     /* Set values in dictionary */
00372     printf("setting %d values...\n", NVALS);
00373     for (i=0 ; i<NVALS ; i++) {
00374         sprintf(cval, "%04d", i);
00375         dictionary_set(d, cval, "salut");
00376     }
00377     printf("getting %d values...\n", NVALS);
00378     for (i=0 ; i<NVALS ; i++) {
00379         sprintf(cval, "%04d", i);
00380         val = dictionary_get(d, cval, DICT_INVALID_KEY);
00381         if (val==DICT_INVALID_KEY) {
00382             printf("cannot get value for key [%s]\n", cval);
00383         }
00384     }
00385     printf("unsetting %d values...\n", NVALS);
00386     for (i=0 ; i<NVALS ; i++) {
00387         sprintf(cval, "%04d", i);
00388         dictionary_unset(d, cval);
00389     }
00390     if (d->n != 0) {
00391         printf("error deleting values\n");
00392     }
00393     printf("deallocating...\n");
00394     dictionary_del(d);
00395     return 0 ;
00396 }
00397 #endif
00398 /* vim: set ts=4 et sw=4 tw=75 */