[PATCH] generic lookup dictionary (hash) - extends gwlib/dict.[ch]

### Eclipse Workspace Patch 1.0
#P gateway-cvs-head
Index: gwlib/gw-dict.h
===================================================================
RCS file: gwlib/gw-dict.h
diff -N gwlib/gw-dict.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gwlib/gw-dict.h	1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,199 @@
+/* ==================================================================== 
+ * The Kannel Software License, Version 1.0 
+ * 
+ * Copyright (c) 2001-2007 Kannel Group  
+ * Copyright (c) 1998-2001 WapIT Ltd.   
+ * All rights reserved. 
+ * 
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions 
+ * are met: 
+ * 
+ * 1. Redistributions of source code must retain the above copyright 
+ *    notice, this list of conditions and the following disclaimer. 
+ * 
+ * 2. Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in 
+ *    the documentation and/or other materials provided with the 
+ *    distribution. 
+ * 
+ * 3. The end-user documentation included with the redistribution, 
+ *    if any, must include the following acknowledgment: 
+ *       "This product includes software developed by the 
+ *        Kannel Group (http://www.kannel.org/)." 
+ *    Alternately, this acknowledgment may appear in the software itself, 
+ *    if and wherever such third-party acknowledgments normally appear. 
+ * 
+ * 4. The names "Kannel" and "Kannel Group" must not be used to 
+ *    endorse or promote products derived from this software without 
+ *    prior written permission. For written permission, please  
+ *    contact [email protected]. 
+ * 
+ * 5. Products derived from this software may not be called "Kannel", 
+ *    nor may "Kannel" appear in their name, without prior written 
+ *    permission of the Kannel Group. 
+ * 
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+ * DISCLAIMED.  IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS 
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,  
+ * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR  
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE  
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ * ==================================================================== 
+ * 
+ * This software consists of voluntary contributions made by many 
+ * individuals on behalf of the Kannel Group.  For more information on  
+ * the Kannel Group, please see <http://www.kannel.org/>. 
+ * 
+ * Portions of this software are based upon software originally written at  
+ * WapIT Ltd., Helsinki, Finland for the Kannel project.  
+ */ 
+
+/*
+ * gw-dict.h - hash lookup data structure using generic struct as key
+ *
+ * This data structure manages a hash table for void* objects and it's 
+ * associated key type is independant from this implemenation. We pass
+ * also void* for the key type and within typedef struct gw_dict_ops_t we
+ * define the three functions that deal with the key type explicitely.
+ * 
+ * Stipe Tolj
+ * Based on Lars Wirzenius's gwlib/dict.[ch] 
+ * Based on code by Tuomas Luttinen
+ */
+
+#ifndef GW_DICT_H
+#define GW_DICT_H
+
+typedef struct gw_dict gw_dict_t;
+
+
+/*
+ * To achive the void* key type independance, ie. against a static way to
+ * implement the key as unsigned long or Ocstr we use the following typedef
+ * gw_dict_ops_t that defines the three functions that deal with the type
+ * implementation of the stored void* item and the void* key.
+ * 
+ *   .destroy - function applied to all void* item in the hash when 
+ *              the dict is beeing destroyed
+ *   .key_to_index - function mapping a given void* key to a unsigned long
+ *                   that is used to calculate the hash table position
+ *   .item_has_key - function used for gwlist_search() as compare function
+ *                   to give a result if the given key matches the stored item
+ * 
+ * So how is this used in the user code? We give here two examples for the 
+ * void *key handling functions:
+ * 
+ * Key is a Octstr*:
+ * 
+ *   static unsigned long key_to_index(void *key)
+ *   {
+ *      return octstr_hash_key((Octstr*) key);
+ *   }
+ *
+ *   static int item_has_key(void *item, void *key)
+ *   {
+ *      return octstr_compare((Octstr*) item, (Octstr*) key) == 0;
+ *   }
+ * 
+ * Key is a unisgned long:
+ * 
+ *   static unsigned long key_to_index(void *key)
+ *   {
+ *      unsigned long *k = (unsigned long*) key;
+ *      return *k;
+ *   }
+ * 
+ *   static int item_has_key(void *item, void *key)
+ *   {
+ *      unsigned long *i = (unsigned long*) item;
+ *      unsigned long *k = (unsigned long*) key;
+ *      return *i == *k;
+ *   }
+ */
+typedef struct gw_dict_ops gw_dict_ops_t;
+
+struct gw_dict_ops {
+    void (*destroy) (void *item);
+    unsigned long (*key_to_index) (void *key);
+    int (*item_has_key) (void *item, void *key);
+};
+
+
+/*
+ * Create a gw_dict_t. `size_hint' gives an indication of how many different
+ * keys will be in the gw_dict_t at the same time, at most. This is used for
+ * performance optimization; things will work fine, though somewhat
+ * slower, even if it the number is exceeded. `ops' is a pointer to a strcut
+ * defining the above type handling functions. If `ops.destroy' is NULL, then 
+ * values are not destroyed by the gw_dict_t, they are just discarded.
+ * 
+ * Example, where we handle Octstr* as items:
+ * 
+ *   static gw_dict_ops_t ops = {
+ *      .destroy = (void (*)(void *))octstr_destroy,
+ *      .key_to_index = key_to_index,
+ *      .item_has_key = item_has_key
+ *   };
+ * 
+ *   ...
+ *   gw_dict_t *dict = gw_dict_create(100, &ops);
+ *   ...
+ */
+gw_dict_t *gw_dict_create(long size_hint, gw_dict_ops_t *ops);
+
+
+/*
+ * Destroy a gw_dict_ and all values in it.
+ */
+void gw_dict_destroy(gw_dict_t *dict);
+
+
+/*
+ * Put a new value into a gw_dict_t. If the same key existed already, the
+ * old value is destroyed. If `value' is NULL, the old value is destroyed
+ * and the key is removed from the gw_dict_t.
+ */
+void gw_dict_put(gw_dict_t *dict, void *key, void *value);
+
+
+/*
+ * Put a new value into a gw_dict_t. Return error, if the same key existed all-
+ * ready.
+ */
+int gw_dict_put_once(gw_dict_t *dict, void *key, void *value);
+
+
+/*
+ * Look up a value in a gw_dict_t. If there is no value corresponding to a 
+ * key, return NULL, otherwise return the value. The value will not
+ * be removed from the gw_dict_t.
+ */
+void *gw_dict_get(gw_dict_t *dict, void *key);
+
+
+/*
+ * Remove a value from a gw_dict_t without destroying it.
+ */
+void *gw_dict_remove(gw_dict_t *dict, void *key);
+
+
+/*
+ * Return the number of keys which currently exist in the gw_dict_t.
+ */
+long gw_dict_key_count(gw_dict_t *dict);
+
+
+/*
+ * Return a list of all the currently defined keys in the gw_dict_t. The
+ * caller must destroy the list.
+ */
+List *gw_dict_keys(gw_dict_t *dict);
+
+
+#endif
Index: test/test_gw_dict.c
===================================================================
RCS file: test/test_gw_dict.c
diff -N test/test_gw_dict.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ test/test_gw_dict.c	1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,136 @@
+/* ==================================================================== 
+ * The Kannel Software License, Version 1.0 
+ * 
+ * Copyright (c) 2001-2007 Kannel Group  
+ * Copyright (c) 1998-2001 WapIT Ltd.   
+ * All rights reserved. 
+ * 
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions 
+ * are met: 
+ * 
+ * 1. Redistributions of source code must retain the above copyright 
+ *    notice, this list of conditions and the following disclaimer. 
+ * 
+ * 2. Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in 
+ *    the documentation and/or other materials provided with the 
+ *    distribution. 
+ * 
+ * 3. The end-user documentation included with the redistribution, 
+ *    if any, must include the following acknowledgment: 
+ *       "This product includes software developed by the 
+ *        Kannel Group (http://www.kannel.org/)." 
+ *    Alternately, this acknowledgment may appear in the software itself, 
+ *    if and wherever such third-party acknowledgments normally appear. 
+ * 
+ * 4. The names "Kannel" and "Kannel Group" must not be used to 
+ *    endorse or promote products derived from this software without 
+ *    prior written permission. For written permission, please  
+ *    contact [email protected]. 
+ * 
+ * 5. Products derived from this software may not be called "Kannel", 
+ *    nor may "Kannel" appear in their name, without prior written 
+ *    permission of the Kannel Group. 
+ * 
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+ * DISCLAIMED.  IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS 
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,  
+ * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR  
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE  
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ * ==================================================================== 
+ * 
+ * This software consists of voluntary contributions made by many 
+ * individuals on behalf of the Kannel Group.  For more information on  
+ * the Kannel Group, please see <http://www.kannel.org/>. 
+ * 
+ * Portions of this software are based upon software originally written at  
+ * WapIT Ltd., Helsinki, Finland for the Kannel project.  
+ */ 
+
+/*
+ * test_dict.c - test Dict objects
+ *
+ * Lars Wirzenius
+ */
+
+
+#include "gwlib/gwlib.h"
+#include "gwlib/gw-dict.h"
+
+#define HUGE_SIZE 200000
+
+
+/*
+ * gw_dict operations for key type Octstr*
+ */
+
+static unsigned long key_to_index(void *key)
+{
+    return octstr_hash_key((Octstr*) key);
+}
+
+static int item_has_key(void *item, void *key)
+{
+    return octstr_compare((Octstr*) item, (Octstr*) key) == 0;
+}
+
+static gw_dict_ops_t ops = {
+    .destroy = (void (*)(void *))octstr_destroy,
+    .key_to_index = key_to_index,
+    .item_has_key = item_has_key
+};
+
+
+
+int main(void)
+{
+    gw_dict_t *dict;
+    Octstr *foo, *bar;
+    unsigned long i;
+     
+    gwlib_init();
+    
+    foo = octstr_imm("foo");
+    bar = octstr_imm("bar");
+    
+    debug("",0,"gw_dict simple test.");
+    dict = gw_dict_create(10, &ops);
+    gw_dict_put(dict, foo, bar);
+    info(0, "foo gives %s", octstr_get_cstr(gw_dict_get(dict, foo)));
+    if (gw_dict_key_count(dict) == 1)
+        info(0, "there is but one foo.");
+    else
+        error(0, "key count is %ld, should be 1.", gw_dict_key_count(dict));
+    gw_dict_destroy(dict);
+
+    debug("",0,"Dict extended/huge test.");
+    dict = gw_dict_create(HUGE_SIZE, &ops);
+    for (i = 1; i <= HUGE_SIZE; i++) {
+        unsigned long val;
+        Octstr *okey, *oval;
+        uuid_t id;
+        char key[UUID_STR_LEN + 1];
+        uuid_generate(id);
+        uuid_unparse(id, key);
+        val = gw_rand();
+        okey = octstr_create(key);
+        oval = octstr_format("%ld", val);
+        gw_dict_put(dict, okey, oval);
+    }
+    gwthread_sleep(5); 
+    if (gw_dict_key_count(dict) == HUGE_SIZE)
+        info(0, "ok, got %d entries in the dictionary.", HUGE_SIZE);
+    else
+        error(0, "key count is %ld, should be %d.", gw_dict_key_count(dict), HUGE_SIZE);
+    gw_dict_destroy(dict);
+
+    gwlib_shutdown();
+    return 0;
+}
Index: gwlib/gw-dict.c
===================================================================
RCS file: gwlib/gw-dict.c
diff -N gwlib/gw-dict.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gwlib/gw-dict.c	1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,378 @@
+/* ==================================================================== 
+ * The Kannel Software License, Version 1.0 
+ * 
+ * Copyright (c) 2001-2007 Kannel Group  
+ * Copyright (c) 1998-2001 WapIT Ltd.   
+ * All rights reserved. 
+ * 
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions 
+ * are met: 
+ * 
+ * 1. Redistributions of source code must retain the above copyright 
+ *    notice, this list of conditions and the following disclaimer. 
+ * 
+ * 2. Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in 
+ *    the documentation and/or other materials provided with the 
+ *    distribution. 
+ * 
+ * 3. The end-user documentation included with the redistribution, 
+ *    if any, must include the following acknowledgment: 
+ *       "This product includes software developed by the 
+ *        Kannel Group (http://www.kannel.org/)." 
+ *    Alternately, this acknowledgment may appear in the software itself, 
+ *    if and wherever such third-party acknowledgments normally appear. 
+ * 
+ * 4. The names "Kannel" and "Kannel Group" must not be used to 
+ *    endorse or promote products derived from this software without 
+ *    prior written permission. For written permission, please  
+ *    contact [email protected]. 
+ * 
+ * 5. Products derived from this software may not be called "Kannel", 
+ *    nor may "Kannel" appear in their name, without prior written 
+ *    permission of the Kannel Group. 
+ * 
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+ * DISCLAIMED.  IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS 
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,  
+ * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR  
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE  
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ * ==================================================================== 
+ * 
+ * This software consists of voluntary contributions made by many 
+ * individuals on behalf of the Kannel Group.  For more information on  
+ * the Kannel Group, please see <http://www.kannel.org/>. 
+ * 
+ * Portions of this software are based upon software originally written at  
+ * WapIT Ltd., Helsinki, Finland for the Kannel project.  
+ */ 
+
+/*
+ * gw-dict.c - hash lookup data structure using generic struct as key
+ *
+ * This data structure manages a hash table for void* objects and it's 
+ * associated key type is independant from this implemenation. We pass
+ * also void* for the key type and within typedef struct gw_dict_ops_t we
+ * define the three functions that deal with the key type explicitely.
+ * 
+ * Stipe Tolj
+ * Based on Lars Wirzenius's gwlib/dict.[ch] 
+ * Based on code by Tuomas Luttinen
+ */
+
+#include "gwlib.h"
+#include "gw-dict.h"
+
+
+/*
+ * The hash table stores key/value -pairs in a List.
+ */
+typedef struct Item Item;
+
+struct Item {
+    void *key;
+    void *value;
+    void *dict;
+};
+
+
+static Item *item_create(void *key, void *value, void *dict)
+{
+    Item *item;
+    
+    item = gw_malloc(sizeof(*item));
+    item->key = key;
+    item->value = value;
+    item->dict = dict;
+    return item;
+}
+
+
+static void item_destroy(void *item)
+{
+    Item *p;
+    
+    p = item;
+    gw_free(p);
+}
+
+
+/*
+ * The dictionary itself is a very simple hash table.
+ * `tab' is an array of Lists of Items, in which empty Lists may be
+ * represented as NULL.  `size' is the number of elements allocated
+ * for the array, and `key_count' is the number of Items currently
+ * in the table.  `key_count' is kept up to date by the put and remove
+ * functions, and is used to make gw_dict_key_count() faster.
+ */
+struct gw_dict {
+    List **tab;
+    long size;
+    long key_count;
+    gw_dict_ops_t *ops;
+    Mutex *lock;
+};
+
+
+static void lock(gw_dict_t *dict)
+{
+    mutex_lock(dict->lock);
+}
+
+
+static void unlock(gw_dict_t *dict)
+{
+    mutex_unlock(dict->lock);
+}
+
+
+/*
+ * A wrapper arround the given .item_has_key in the gw_dict_ops_t
+ * struct. Needed to ensure Item struct has not to be in public
+ * scope defined.
+ */
+static int item_has_key(void *item, void *key)
+{
+    Item *i = item;
+    gw_dict_t *d = i->dict;
+    return d->ops->item_has_key((void*)i->key, key);
+}
+
+
+static int handle_null_value(gw_dict_t *dict, void *key, void *value)
+{
+    if (value == NULL) {
+        value = gw_dict_remove(dict, key);
+	if (dict->ops->destroy != NULL)
+	    dict->ops->destroy(value);
+        return 1;
+    }
+
+    return 0;
+}
+
+
+static int dict_put_true(gw_dict_t *dict, void *key, void *value)
+{
+    Item *p;
+    long i;
+    int item_unique;
+
+    item_unique = 0;
+    lock(dict);
+    i = dict->ops->key_to_index(key) % dict->size;
+
+    if (dict->tab[i] == NULL) {
+        dict->tab[i] = gwlist_create();
+        p = NULL;
+    } else {
+        p = gwlist_search(dict->tab[i], key, item_has_key);
+    }
+
+    if (p == NULL) {
+    	p = item_create(key, value, dict);
+        gwlist_append(dict->tab[i], p);
+        dict->key_count++;
+        item_unique = 1;
+    } else {
+    	if (dict->ops->destroy != NULL)
+    	    dict->ops->destroy(value);
+        item_unique = 0;
+    }
+
+    unlock(dict);
+
+    return item_unique;
+}
+
+
+/********************************************************************
+ * Public functions
+ */
+
+gw_dict_t *gw_dict_create(long size_hint, gw_dict_ops_t *ops)
+{
+    gw_dict_t *dict;
+    long i;
+    
+    dict = gw_malloc(sizeof(*dict));
+
+    /*
+     * Hash tables tend to work well until they are fill to about 50%.
+     * So we pre-allocate the double space in order to have enough room.
+     */
+    dict->size = size_hint * 2;
+
+    dict->tab = gw_malloc(sizeof(dict->tab[0]) * dict->size);
+    for (i = 0; i < dict->size; ++i)
+    	dict->tab[i] = NULL;
+    dict->lock = mutex_create();
+    dict->ops = ops;
+    dict->key_count = 0;
+    
+    return dict;
+}
+
+
+void gw_dict_destroy(gw_dict_t *dict)
+{
+    long i;
+    Item *p;
+    
+    if (dict == NULL)
+        return;
+
+    for (i = 0; i < dict->size; ++i) {
+        if (dict->tab[i] == NULL)
+            continue;
+
+        while ((p = gwlist_extract_first(dict->tab[i])) != NULL) {
+            if (dict->ops->destroy != NULL)
+                dict->ops->destroy(p->value);
+            item_destroy(p);
+        }
+        gwlist_destroy(dict->tab[i], NULL);
+    }
+    mutex_destroy(dict->lock);
+    gw_free(dict->tab);
+    gw_free(dict);
+}
+
+
+void gw_dict_put(gw_dict_t *dict, void *key, void *value)
+{
+    long i;
+    Item *p;
+
+    if (value == NULL) {
+        value = gw_dict_remove(dict, key);
+        if (dict->ops->destroy != NULL)
+            dict->ops->destroy(value);
+        return;
+    }
+
+    lock(dict);
+    i = dict->ops->key_to_index(key) % dict->size;
+    if (dict->tab[i] == NULL) {
+        dict->tab[i] = gwlist_create();
+        p = NULL;
+    } else
+        p = gwlist_search(dict->tab[i], key, item_has_key);
+    if (p == NULL) {
+    	p = item_create(key, value, dict);
+        gwlist_append(dict->tab[i], p);
+        dict->key_count++;
+    } else {
+        if (dict->ops->destroy != NULL)
+            dict->ops->destroy(p->value);
+        p->value = value;
+    }
+    unlock(dict);
+}
+
+
+int gw_dict_put_once(gw_dict_t *dict, void *key, void *value)
+{
+    int ret;
+
+    ret = 1;
+    if (handle_null_value(dict, key, value))
+        return 1;
+    if (dict_put_true(dict, key, value)) {
+        ret = 1;
+    } else {
+        ret = 0;
+    }
+    return ret;
+}
+
+
+void *gw_dict_get(gw_dict_t *dict, void *key)
+{
+    long i;
+    Item *p;
+    void *value;
+
+    lock(dict);
+    i = dict->ops->key_to_index(key) % dict->size;
+    if (dict->tab[i] == NULL)
+        p = NULL;
+    else
+        p = gwlist_search(dict->tab[i], key, item_has_key);
+    if (p == NULL)
+    	value = NULL;
+    else
+    	value = p->value;
+    unlock(dict);
+    return value;
+}
+
+
+void *gw_dict_remove(gw_dict_t *dict, void *key)
+{
+    long i;
+    Item *p;
+    void *value;
+    List *list;
+
+    lock(dict);
+    i = dict->ops->key_to_index(key) % dict->size;
+    if (dict->tab[i] == NULL)
+        list = NULL;
+    else
+        list = gwlist_extract_matching(dict->tab[i], key, item_has_key);
+    gw_assert(list == NULL || gwlist_len(list) == 1);
+    if (list == NULL)
+    	value = NULL;
+    else {
+        p = gwlist_get(list, 0);
+        gwlist_destroy(list, NULL);
+        value = p->value;
+        item_destroy(p);
+        dict->key_count--;
+    }
+    unlock(dict);
+    return value;
+}
+
+
+long gw_dict_key_count(gw_dict_t *dict)
+{
+    long result;
+
+    lock(dict);
+    result = dict->key_count;
+    unlock(dict);
+
+    return result;
+}
+
+
+List *gw_dict_keys(gw_dict_t *dict)
+{
+    List *list;
+    Item *item;
+    long i, j;
+    
+    list = gwlist_create();
+
+    lock(dict);
+    for (i = 0; i < dict->size; ++i) {
+        if (dict->tab[i] == NULL)
+            continue;
+        for (j = 0; j < gwlist_len(dict->tab[i]); ++j) {
+            item = gwlist_get(dict->tab[i], j);
+            gwlist_append(list, octstr_duplicate(item->key));
+        }
+    }
+    unlock(dict);
+    
+    return list;
+}