/Users/maurits/Documents/studie/afstuderen/biosphere/common/dict.c

Go to the documentation of this file.

/*
 * Author: MA Hartman
 * Date: feb 13, 2007
 * 
 * Function:
 * A general purpose dictionary implementation with
 * almost constant time get operations.
 * 
 * License information:
 * 
 * Copyright (c) 2006 Maurits Hartman
 *
 * 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 "dict.h"
#include "str.h"

#include <apr_strings.h>
#include <assert.h>


bs_dict *new_dict(apr_pool_t *mp)
{
        apr_status_t rv;
        apr_pool_t *pool;
        bs_dict *dict = NULL;
        
        /* Create a subpool for this dict and its data: */
        rv = apr_pool_create(&pool, mp);
        if (rv != APR_SUCCESS) return NULL;
        
        /* Initialize data members (note that bucket does not have
         * to be malloced: */
    dict                        = apr_pcalloc(pool, sizeof(bs_dict));
    dict->size      = 0;
    dict->pool          = pool;
    
    return dict;        
}


void delete_dict(bs_dict *dict)
{
    if (dict != NULL) {
        apr_pool_destroy(dict->pool);
    }   
}


void *dict_get(const bs_dict *dict, const char *key)
{
        unsigned char c;
        assert(dict && key);
        
        c = key[0];
        if (dict->bucket[c]) {
                unsigned i;
                bs_list *tmp = dict->bucket[c];
                for (i = 0; i < list_size(tmp); i++) {
                        bs_dict_item *item = (bs_dict_item *) list_index(tmp, i);
                        if (streq(key, item->key)) return item->data;
                }
        }
        return NULL;
}


bs_bool dict_add(bs_dict *dict, const char *key, void *data)
{
        unsigned char c;
        unsigned i;
        bs_dict_item *item;
        assert(dict && key);
        
        /* See if the key is not already taken: */
        c = key[0];
        if (!dict->bucket[c]) dict->bucket[c] = new_list(dict->pool);
        for (i = 0; i < list_size(dict->bucket[c]); i++) {
                item = (bs_dict_item *) list_index(dict->bucket[c], i);
                if (streq(key, item->key)) return FALSE;
        }
        
        /* Insert: */
        item = apr_palloc(dict->pool, sizeof(bs_dict_item));
        item->key = apr_pstrdup(dict->pool, key);
        item->data = data;
        dict->size++;
        return TRUE;
}


void dict_remove(bs_dict *dict, const char *key)
{
        unsigned char c;
        assert(dict);
        
        c = key[0];
        if (dict->bucket[c]) {
                unsigned i;
                for (i = 0; i < list_size(dict->bucket[c]); i++) {
                        bs_dict_item *item;
                        item = (bs_dict_item *) list_index(dict->bucket[c], i);
                        if (streq(key, item->key)) {
                                list_remove(dict->bucket[c], i);
                                dict->size--;
                                return; 
                        }
                }
        }
}


inline unsigned dict_size(const bs_dict *dict)
{
        assert(dict);
        return dict->size;      
}

---