michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @file dictionary.c michael@0: @author N. Devillard michael@0: @date Sep 2007 michael@0: @version $Revision: 1.27 $ michael@0: @brief Implements a dictionary for string variables. michael@0: michael@0: This module implements a simple dictionary object, i.e. a list michael@0: of string/string associations. This object is useful to store e.g. michael@0: informations retrieved from a configuration file (ini files). michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: michael@0: /* michael@0: $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $ michael@0: $Revision: 1.27 $ michael@0: */ michael@0: /*--------------------------------------------------------------------------- michael@0: Includes michael@0: ---------------------------------------------------------------------------*/ michael@0: #include "dictionary.h" michael@0: michael@0: #include michael@0: #include michael@0: #include michael@0: #ifndef _WIN32 michael@0: #include michael@0: #endif michael@0: michael@0: /** Maximum value size for integers and doubles. */ michael@0: #define MAXVALSZ 1024 michael@0: michael@0: /** Minimal allocated number of entries in a dictionary */ michael@0: #define DICTMINSZ 128 michael@0: michael@0: /** Invalid key token */ michael@0: #define DICT_INVALID_KEY ((char*)-1) michael@0: michael@0: /*--------------------------------------------------------------------------- michael@0: Private functions michael@0: ---------------------------------------------------------------------------*/ michael@0: michael@0: /* Doubles the allocated size associated to a pointer */ michael@0: /* 'size' is the current allocated size. */ michael@0: static void * mem_double(void * ptr, int size) michael@0: { michael@0: void * newptr ; michael@0: michael@0: newptr = calloc(2*size, 1); michael@0: if (newptr==NULL) { michael@0: return NULL ; michael@0: } michael@0: memcpy(newptr, ptr, size); michael@0: free(ptr); michael@0: return newptr ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Duplicate a string michael@0: @param s String to duplicate michael@0: @return Pointer to a newly allocated string, to be freed with free() michael@0: michael@0: This is a replacement for strdup(). This implementation is provided michael@0: for systems that do not have it. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: static char * xstrdup(char * s) michael@0: { michael@0: char * t ; michael@0: if (!s) michael@0: return NULL ; michael@0: t = malloc(strlen(s)+1) ; michael@0: if (t) { michael@0: strcpy(t,s); michael@0: } michael@0: return t ; michael@0: } michael@0: michael@0: /*--------------------------------------------------------------------------- michael@0: Function codes michael@0: ---------------------------------------------------------------------------*/ michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Compute the hash key for a string. michael@0: @param key Character string to use for key. michael@0: @return 1 unsigned int on at least 32 bits. michael@0: michael@0: This hash function has been taken from an Article in Dr Dobbs Journal. michael@0: This is normally a collision-free function, distributing keys evenly. michael@0: The key is stored anyway in the struct so that collision can be avoided michael@0: by comparing the key itself in last resort. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: unsigned dictionary_hash(char * key) michael@0: { michael@0: int len ; michael@0: unsigned hash ; michael@0: int i ; michael@0: michael@0: len = strlen(key); michael@0: for (hash=0, i=0 ; i>6) ; michael@0: } michael@0: hash += (hash <<3); michael@0: hash ^= (hash >>11); michael@0: hash += (hash <<15); michael@0: return hash ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Create a new dictionary object. michael@0: @param size Optional initial size of the dictionary. michael@0: @return 1 newly allocated dictionary objet. michael@0: michael@0: This function allocates a new dictionary object of given size and returns michael@0: it. If you do not know in advance (roughly) the number of entries in the michael@0: dictionary, give size=0. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: dictionary * dictionary_new(int size) michael@0: { michael@0: dictionary * d ; michael@0: michael@0: /* If no size was specified, allocate space for DICTMINSZ */ michael@0: if (sizesize = size ; michael@0: d->val = (char **)calloc(size, sizeof(char*)); michael@0: d->key = (char **)calloc(size, sizeof(char*)); michael@0: d->hash = (unsigned int *)calloc(size, sizeof(unsigned)); michael@0: return d ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Delete a dictionary object michael@0: @param d dictionary object to deallocate. michael@0: @return void michael@0: michael@0: Deallocate a dictionary object and all memory associated to it. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: void dictionary_del(dictionary * d) michael@0: { michael@0: int i ; michael@0: michael@0: if (d==NULL) return ; michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]!=NULL) michael@0: free(d->key[i]); michael@0: if (d->val[i]!=NULL) michael@0: free(d->val[i]); michael@0: } michael@0: free(d->val); michael@0: free(d->key); michael@0: free(d->hash); michael@0: free(d); michael@0: return ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Get a value from a dictionary. michael@0: @param d dictionary object to search. michael@0: @param key Key to look for in the dictionary. michael@0: @param def Default value to return if key not found. michael@0: @return 1 pointer to internally allocated character string. michael@0: michael@0: This function locates a key in a dictionary and returns a pointer to its michael@0: value, or the passed 'def' pointer if no such key can be found in michael@0: dictionary. The returned character pointer points to data internal to the michael@0: dictionary object, you should not try to free it or modify it. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: char * dictionary_get(dictionary * d, char * key, char * def) michael@0: { michael@0: unsigned hash ; michael@0: int i ; michael@0: michael@0: hash = dictionary_hash(key); michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]==NULL) michael@0: continue ; michael@0: /* Compare hash */ michael@0: if (hash==d->hash[i]) { michael@0: /* Compare string, to avoid hash collisions */ michael@0: if (!strcmp(key, d->key[i])) { michael@0: return d->val[i] ; michael@0: } michael@0: } michael@0: } michael@0: return def ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Set a value in a dictionary. michael@0: @param d dictionary object to modify. michael@0: @param key Key to modify or add. michael@0: @param val Value to add. michael@0: @return int 0 if Ok, anything else otherwise michael@0: michael@0: If the given key is found in the dictionary, the associated value is michael@0: replaced by the provided one. If the key cannot be found in the michael@0: dictionary, it is added to it. michael@0: michael@0: It is Ok to provide a NULL value for val, but NULL values for the dictionary michael@0: or the key are considered as errors: the function will return immediately michael@0: in such a case. michael@0: michael@0: Notice that if you dictionary_set a variable to NULL, a call to michael@0: dictionary_get will return a NULL value: the variable will be found, and michael@0: its value (NULL) is returned. In other words, setting the variable michael@0: content to NULL is equivalent to deleting the variable from the michael@0: dictionary. It is not possible (in this implementation) to have a key in michael@0: the dictionary without value. michael@0: michael@0: This function returns non-zero in case of failure. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: int dictionary_set(dictionary * d, char * key, char * val) michael@0: { michael@0: int i ; michael@0: unsigned hash ; michael@0: michael@0: if (d==NULL || key==NULL) return -1 ; michael@0: michael@0: /* Compute hash for this key */ michael@0: hash = dictionary_hash(key) ; michael@0: /* Find if value is already in dictionary */ michael@0: if (d->n>0) { michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]==NULL) michael@0: continue ; michael@0: if (hash==d->hash[i]) { /* Same hash value */ michael@0: if (!strcmp(key, d->key[i])) { /* Same key */ michael@0: /* Found a value: modify and return */ michael@0: if (d->val[i]!=NULL) michael@0: free(d->val[i]); michael@0: d->val[i] = val ? xstrdup(val) : NULL ; michael@0: /* Value has been modified: return */ michael@0: return 0 ; michael@0: } michael@0: } michael@0: } michael@0: } michael@0: /* Add a new value */ michael@0: /* See if dictionary needs to grow */ michael@0: if (d->n==d->size) { michael@0: michael@0: /* Reached maximum size: reallocate dictionary */ michael@0: d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ; michael@0: d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ; michael@0: d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ; michael@0: if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) { michael@0: /* Cannot grow dictionary */ michael@0: return -1 ; michael@0: } michael@0: /* Double size */ michael@0: d->size *= 2 ; michael@0: } michael@0: michael@0: /* Insert key in the first empty slot */ michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]==NULL) { michael@0: /* Add key here */ michael@0: break ; michael@0: } michael@0: } michael@0: /* Copy key */ michael@0: d->key[i] = xstrdup(key); michael@0: d->val[i] = val ? xstrdup(val) : NULL ; michael@0: d->hash[i] = hash; michael@0: d->n ++ ; michael@0: return 0 ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Delete a key in a dictionary michael@0: @param d dictionary object to modify. michael@0: @param key Key to remove. michael@0: @return void michael@0: michael@0: This function deletes a key in a dictionary. Nothing is done if the michael@0: key cannot be found. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: void dictionary_unset(dictionary * d, char * key) michael@0: { michael@0: unsigned hash ; michael@0: int i ; michael@0: michael@0: if (key == NULL) { michael@0: return; michael@0: } michael@0: michael@0: hash = dictionary_hash(key); michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]==NULL) michael@0: continue ; michael@0: /* Compare hash */ michael@0: if (hash==d->hash[i]) { michael@0: /* Compare string, to avoid hash collisions */ michael@0: if (!strcmp(key, d->key[i])) { michael@0: /* Found key */ michael@0: break ; michael@0: } michael@0: } michael@0: } michael@0: if (i>=d->size) michael@0: /* Key not found */ michael@0: return ; michael@0: michael@0: free(d->key[i]); michael@0: d->key[i] = NULL ; michael@0: if (d->val[i]!=NULL) { michael@0: free(d->val[i]); michael@0: d->val[i] = NULL ; michael@0: } michael@0: d->hash[i] = 0 ; michael@0: d->n -- ; michael@0: return ; michael@0: } michael@0: michael@0: /*-------------------------------------------------------------------------*/ michael@0: /** michael@0: @brief Dump a dictionary to an opened file pointer. michael@0: @param d Dictionary to dump michael@0: @param f Opened file pointer. michael@0: @return void michael@0: michael@0: Dumps a dictionary onto an opened file pointer. Key pairs are printed out michael@0: as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as michael@0: output file pointers. michael@0: */ michael@0: /*--------------------------------------------------------------------------*/ michael@0: void dictionary_dump(dictionary * d, FILE * out) michael@0: { michael@0: int i ; michael@0: michael@0: if (d==NULL || out==NULL) return ; michael@0: if (d->n<1) { michael@0: fprintf(out, "empty dictionary\n"); michael@0: return ; michael@0: } michael@0: for (i=0 ; isize ; i++) { michael@0: if (d->key[i]) { michael@0: fprintf(out, "%20s\t[%s]\n", michael@0: d->key[i], michael@0: d->val[i] ? d->val[i] : "UNDEF"); michael@0: } michael@0: } michael@0: return ; michael@0: } michael@0: michael@0: michael@0: /* Test code */ michael@0: #ifdef TESTDIC michael@0: #define NVALS 20000 michael@0: int main(int argc, char *argv[]) michael@0: { michael@0: dictionary * d ; michael@0: char * val ; michael@0: int i ; michael@0: char cval[90] ; michael@0: michael@0: /* Allocate dictionary */ michael@0: printf("allocating...\n"); michael@0: d = dictionary_new(0); michael@0: michael@0: /* Set values in dictionary */ michael@0: printf("setting %d values...\n", NVALS); michael@0: for (i=0 ; in != 0) { michael@0: printf("error deleting values\n"); michael@0: } michael@0: printf("deallocating...\n"); michael@0: dictionary_del(d); michael@0: return 0 ; michael@0: } michael@0: #endif michael@0: /* vim: set ts=4 et sw=4 tw=75 */