[icmpmonitor] / iniparser / dictionary.c

/*-------------------------------------------------------------------------*/
/**
   @file    dictionary.c
   @author  N. Devillard
   @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).
*/
/*--------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------
                                Includes
 ---------------------------------------------------------------------------*/
#include "dictionary.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/** 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
 ---------------------------------------------------------------------------*/

/*-------------------------------------------------------------------------*/
/**
  @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(const char * s)
{
    char * t ;
    size_t len ;
    if (!s)
        return NULL ;

    len = strlen(s) + 1 ;
    t = (char*) malloc(len) ;
    if (t) {
        memcpy(t, s, len) ;
    }
    return t ;
}

/*-------------------------------------------------------------------------*/
/**
  @brief    Double the size of the dictionary
  @param    d Dictionary to grow
  @return   This function returns non-zero in case of failure
 */
/*--------------------------------------------------------------------------*/
static int dictionary_grow(dictionary * d)
{
    char        ** new_val ;
    char        ** new_key ;
    unsigned     * new_hash ;

    new_val  = (char**) calloc(d->size * 2, sizeof *d->val);
    new_key  = (char**) calloc(d->size * 2, sizeof *d->key);
    new_hash = (unsigned*) calloc(d->size * 2, sizeof *d->hash);
    if (!new_val || !new_key || !new_hash) {
        /* An allocation failed, leave the dictionary unchanged */
        if (new_val)
            free(new_val);
        if (new_key)
            free(new_key);
        if (new_hash)
            free(new_hash);
        return -1 ;
    }
    /* Initialize the newly allocated space */
    memcpy(new_val, d->val, d->size * sizeof(char *));
    memcpy(new_key, d->key, d->size * sizeof(char *));
    memcpy(new_hash, d->hash, d->size * sizeof(unsigned));
    /* Delete previous data */
    free(d->val);
    free(d->key);
    free(d->hash);
    /* Actually update the dictionary */
    d->size *= 2 ;
    d->val = new_val;
    d->key = new_key;
    d->hash = new_hash;
    return 0 ;
}

/*---------------------------------------------------------------------------
                            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(const char * key)
{
    size_t      len ;
    unsigned    hash ;
    size_t      i ;

    if (!key)
        return 0 ;

    len = strlen(key);
    for (hash=0, i=0 ; i<len ; i++) {
        hash += (unsigned)key[i] ;
        hash += (hash<<10);
        hash ^= (hash>>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(size_t size)
{
    dictionary  *   d ;

    /* If no size was specified, allocate space for DICTMINSZ */
    if (size<DICTMINSZ) size=DICTMINSZ ;

    d = (dictionary*) calloc(1, sizeof *d) ;

    if (d) {
        d->size = size ;
        d->val  = (char**) calloc(size, sizeof *d->val);
        d->key  = (char**) calloc(size, sizeof *d->key);
        d->hash = (unsigned*) calloc(size, sizeof *d->hash);
    }
    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)
{
    ssize_t  i ;

    if (d==NULL) return ;
    for (i=0 ; i<d->size ; 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.
 */
/*--------------------------------------------------------------------------*/
const char * dictionary_get(const dictionary * d, const char * key, const char * def)
{
    unsigned    hash ;
    ssize_t      i ;

    hash = dictionary_hash(key);
    for (i=0 ; i<d->size ; 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, const char * key, const char * val)
{
    ssize_t         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 ; i<d->size ; 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 */
        if (dictionary_grow(d) != 0)
            return -1;
    }

    /* Insert key in the first empty slot. Start at d->n and wrap at
       d->size. Because d->n < d->size this will necessarily
       terminate. */
    for (i=d->n ; d->key[i] ; ) {
        if(++i == d->size) i = 0;
    }
    /* 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, const char * key)
{
    unsigned    hash ;
    ssize_t      i ;

    if (key == NULL || d == NULL) {
        return;
    }

    hash = dictionary_hash(key);
    for (i=0 ; i<d->size ; 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(const dictionary * d, FILE * out)
{
    ssize_t  i ;

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