dictionary.c

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