dictionary.c

Go to the documentation of this file.

/* Copyright (c) 2000-2007 by Nicolas Devillard.
 * Copyright (x) 2009 by Tim Post <tinkertim@gmail.com>
 * MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

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

#define MAXVALSZ        1024

#define DICTMINSZ       128

#define DICT_INVALID_KEY        ((char*)-1)

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;
}
 
/* The remaining exposed functions are documented in dictionary.h */
 
unsigned dictionary_hash(const char* key)
{
        int len;
        unsigned hash;
        int i;
 
        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;
}
 
dictionary* dictionary_new(int size)
{
        dictionary* d;
 
        /* If no size was specified, allocate space for DICTMINSZ */
        if (size < DICTMINSZ)
                size = DICTMINSZ;
 
        if (!(d = (dictionary*)calloc(1, sizeof(dictionary))))
                return NULL;
        d->size = 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;
}
 
void dictionary_del(dictionary* d)
{
        int 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;
}
 
const char* dictionary_get(dictionary* d, const char* key, const char* def)
{
        unsigned hash;
        int 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;
}
 
int dictionary_set(dictionary* d, const char* key, const 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; i < d->size; i++) {
                        if (d->key[i] == NULL)
                                continue;
                        /* Same hash value */
                        if (hash == d->hash[i]) {
                                /* Same key */
                                if (!strcmp(key, d->key[i])) {
                                        /* Found a value: modify and return */
                                        if (d->val[i] != NULL)
                                                free(d->val[i]);
                                        d->val[i] = val ? strdup(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; i < d->size; i++) {
                if (d->key[i] == NULL)
                        /* Add key here */
                        break;
        }
        /* Copy key */
        d->key[i] = strdup(key);
        d->val[i] = val ? strdup(val) : NULL;
        d->hash[i] = hash;
        d->n++;
        return 0;
}
 
void dictionary_unset(dictionary* d, const char* key)
{
        unsigned hash;
        int i;
 
        if (key == 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;
}
 
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; 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;
}