From 3285a49dd871d54c1ec13076173ad617443baae1 Mon Sep 17 00:00:00 2001 From: Mike Frysinger Date: Sat, 25 Jun 2011 13:20:37 -0400 Subject: rewrite build system to avoid recursion The ubi-utils/src/ subdir is tossed as it just complicates things for no real gain. The dictionary.h header is relocated to the ubi-utils/include/ since other headers in there need it. The top level clean is replaced with a `find -delete` on objects, so it might prune more than necessary, but many projects now do this sort of thing and no one complained there. A "mkdep" helper generates the actual rule, and the variables are used with "foreach" to expand these automatically. The tests subdir is updated only to reflect the ubi-utils source move. Otherwise, it is left untouched as making that non-recursive isn't really worth the effort. While we're gutting things, also through in kbuild style output while building to make things more legible. Signed-off-by: Mike Frysinger Signed-off-by: Artem Bityutskiy --- ubi-utils/dictionary.c | 405 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 405 insertions(+) create mode 100644 ubi-utils/dictionary.c (limited to 'ubi-utils/dictionary.c') diff --git a/ubi-utils/dictionary.c b/ubi-utils/dictionary.c new file mode 100644 index 0000000..b7c9ebf --- /dev/null +++ b/ubi-utils/dictionary.c @@ -0,0 +1,405 @@ +/*-------------------------------------------------------------------------*/ +/** + @file dictionary.c + @author N. Devillard + @date Sep 2007 + @version $Revision: 1.27 $ + @brief Implements a dictionary for string variables. + + This module implements a simple dictionary object, i.e. a list + of string/string associations. This object is useful to store e.g. + informations retrieved from a configuration file (ini files). +*/ +/*--------------------------------------------------------------------------*/ + +/* + $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $ + $Revision: 1.27 $ +*/ +/*--------------------------------------------------------------------------- + Includes + ---------------------------------------------------------------------------*/ +#include "dictionary.h" + +#include +#include +#include +#include + +/** Maximum value size for integers and doubles. */ +#define MAXVALSZ 1024 + +/** Minimal allocated number of entries in a dictionary */ +#define DICTMINSZ 128 + +/** Invalid key token */ +#define DICT_INVALID_KEY ((char*)-1) + +/*--------------------------------------------------------------------------- + Private functions + ---------------------------------------------------------------------------*/ + +/* Doubles the allocated size associated to a pointer */ +/* 'size' is the current allocated size. */ +static void * mem_double(void * ptr, int size) +{ + void * newptr ; + + newptr = calloc(2*size, 1); + if (newptr==NULL) { + return NULL ; + } + memcpy(newptr, ptr, size); + free(ptr); + return newptr ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Duplicate a string + @param s String to duplicate + @return Pointer to a newly allocated string, to be freed with free() + + This is a replacement for strdup(). This implementation is provided + for systems that do not have it. + */ +/*--------------------------------------------------------------------------*/ +static char * xstrdup(char * s) +{ + char * t ; + if (!s) + return NULL ; + t = malloc(strlen(s)+1) ; + if (t) { + strcpy(t,s); + } + return t ; +} + +/*--------------------------------------------------------------------------- + Function codes + ---------------------------------------------------------------------------*/ +/*-------------------------------------------------------------------------*/ +/** + @brief Compute the hash key for a string. + @param key Character string to use for key. + @return 1 unsigned int on at least 32 bits. + + This hash function has been taken from an Article in Dr Dobbs Journal. + This is normally a collision-free function, distributing keys evenly. + The key is stored anyway in the struct so that collision can be avoided + by comparing the key itself in last resort. + */ +/*--------------------------------------------------------------------------*/ +unsigned dictionary_hash(char * key) +{ + int len ; + unsigned hash ; + int i ; + + len = strlen(key); + for (hash=0, i=0 ; i>6) ; + } + hash += (hash <<3); + hash ^= (hash >>11); + hash += (hash <<15); + return hash ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Create a new dictionary object. + @param size Optional initial size of the dictionary. + @return 1 newly allocated dictionary objet. + + This function allocates a new dictionary object of given size and returns + it. If you do not know in advance (roughly) the number of entries in the + dictionary, give size=0. + */ +/*--------------------------------------------------------------------------*/ +dictionary * dictionary_new(int size) +{ + dictionary * d ; + + /* If no size was specified, allocate space for DICTMINSZ */ + if (sizesize = size ; + d->val = (char **)calloc(size, sizeof(char*)); + d->key = (char **)calloc(size, sizeof(char*)); + d->hash = (unsigned int *)calloc(size, sizeof(unsigned)); + return d ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Delete a dictionary object + @param d dictionary object to deallocate. + @return void + + Deallocate a dictionary object and all memory associated to it. + */ +/*--------------------------------------------------------------------------*/ +void dictionary_del(dictionary * d) +{ + int i ; + + if (d==NULL) return ; + for (i=0 ; isize ; i++) { + if (d->key[i]!=NULL) + free(d->key[i]); + if (d->val[i]!=NULL) + free(d->val[i]); + } + free(d->val); + free(d->key); + free(d->hash); + free(d); + return ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Get a value from a dictionary. + @param d dictionary object to search. + @param key Key to look for in the dictionary. + @param def Default value to return if key not found. + @return 1 pointer to internally allocated character string. + + This function locates a key in a dictionary and returns a pointer to its + value, or the passed 'def' pointer if no such key can be found in + dictionary. The returned character pointer points to data internal to the + dictionary object, you should not try to free it or modify it. + */ +/*--------------------------------------------------------------------------*/ +char * dictionary_get(dictionary * d, char * key, char * def) +{ + unsigned hash ; + int i ; + + hash = dictionary_hash(key); + for (i=0 ; isize ; i++) { + if (d->key[i]==NULL) + continue ; + /* Compare hash */ + if (hash==d->hash[i]) { + /* Compare string, to avoid hash collisions */ + if (!strcmp(key, d->key[i])) { + return d->val[i] ; + } + } + } + return def ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Set a value in a dictionary. + @param d dictionary object to modify. + @param key Key to modify or add. + @param val Value to add. + @return int 0 if Ok, anything else otherwise + + If the given key is found in the dictionary, the associated value is + replaced by the provided one. If the key cannot be found in the + dictionary, it is added to it. + + It is Ok to provide a NULL value for val, but NULL values for the dictionary + or the key are considered as errors: the function will return immediately + in such a case. + + Notice that if you dictionary_set a variable to NULL, a call to + dictionary_get will return a NULL value: the variable will be found, and + its value (NULL) is returned. In other words, setting the variable + content to NULL is equivalent to deleting the variable from the + dictionary. It is not possible (in this implementation) to have a key in + the dictionary without value. + + This function returns non-zero in case of failure. + */ +/*--------------------------------------------------------------------------*/ +int dictionary_set(dictionary * d, char * key, char * val) +{ + int i ; + unsigned hash ; + + if (d==NULL || key==NULL) return -1 ; + + /* Compute hash for this key */ + hash = dictionary_hash(key) ; + /* Find if value is already in dictionary */ + if (d->n>0) { + for (i=0 ; isize ; i++) { + if (d->key[i]==NULL) + continue ; + if (hash==d->hash[i]) { /* Same hash value */ + if (!strcmp(key, d->key[i])) { /* Same key */ + /* Found a value: modify and return */ + if (d->val[i]!=NULL) + free(d->val[i]); + d->val[i] = val ? xstrdup(val) : NULL ; + /* Value has been modified: return */ + return 0 ; + } + } + } + } + /* Add a new value */ + /* See if dictionary needs to grow */ + if (d->n==d->size) { + + /* Reached maximum size: reallocate dictionary */ + d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ; + d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ; + d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ; + if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) { + /* Cannot grow dictionary */ + return -1 ; + } + /* Double size */ + d->size *= 2 ; + } + + /* Insert key in the first empty slot */ + for (i=0 ; isize ; i++) { + if (d->key[i]==NULL) { + /* Add key here */ + break ; + } + } + /* Copy key */ + d->key[i] = xstrdup(key); + d->val[i] = val ? xstrdup(val) : NULL ; + d->hash[i] = hash; + d->n ++ ; + return 0 ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Delete a key in a dictionary + @param d dictionary object to modify. + @param key Key to remove. + @return void + + This function deletes a key in a dictionary. Nothing is done if the + key cannot be found. + */ +/*--------------------------------------------------------------------------*/ +void dictionary_unset(dictionary * d, char * key) +{ + unsigned hash ; + int i ; + + if (key == NULL) { + return; + } + + hash = dictionary_hash(key); + for (i=0 ; isize ; i++) { + if (d->key[i]==NULL) + continue ; + /* Compare hash */ + if (hash==d->hash[i]) { + /* Compare string, to avoid hash collisions */ + if (!strcmp(key, d->key[i])) { + /* Found key */ + break ; + } + } + } + if (i>=d->size) + /* Key not found */ + return ; + + free(d->key[i]); + d->key[i] = NULL ; + if (d->val[i]!=NULL) { + free(d->val[i]); + d->val[i] = NULL ; + } + d->hash[i] = 0 ; + d->n -- ; + return ; +} + +/*-------------------------------------------------------------------------*/ +/** + @brief Dump a dictionary to an opened file pointer. + @param d Dictionary to dump + @param f Opened file pointer. + @return void + + Dumps a dictionary onto an opened file pointer. Key pairs are printed out + as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as + output file pointers. + */ +/*--------------------------------------------------------------------------*/ +void dictionary_dump(dictionary * d, FILE * out) +{ + int i ; + + if (d==NULL || out==NULL) return ; + if (d->n<1) { + fprintf(out, "empty dictionary\n"); + return ; + } + for (i=0 ; isize ; i++) { + if (d->key[i]) { + fprintf(out, "%20s\t[%s]\n", + d->key[i], + d->val[i] ? d->val[i] : "UNDEF"); + } + } + return ; +} + + +/* Test code */ +#ifdef TESTDIC +#define NVALS 20000 +int main(int argc, char *argv[]) +{ + dictionary * d ; + char * val ; + int i ; + char cval[90] ; + + /* Allocate dictionary */ + printf("allocating...\n"); + d = dictionary_new(0); + + /* Set values in dictionary */ + printf("setting %d values...\n", NVALS); + for (i=0 ; in != 0) { + printf("error deleting values\n"); + } + printf("deallocating...\n"); + dictionary_del(d); + return 0 ; +} +#endif +/* vim: set ts=4 et sw=4 tw=75 */ -- cgit v1.2.3