Hi list,
attached is an enhanced version of our gwlib/dict.[ch], now called
gwlib/gw-dict.[ch] that can used generic key types.
Generic means void* key actually, and now Octstr* key as current Dict does. Why?
Because under certain conditions it's too expensive to do all the string
mangling stuff via octstr_foobar() routines just to get a unsigned long that is
used internally for the hash table position.
To achive the abstraction of the key type, the gw_dict_t user needs to have a
struct of type gw_dict_ops_t that defines three functions:
.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
See also attched test/test_gw_dict.c which is a copy of test/test_dict.c but
uses of course the new gw_dict_t* instead of Dict*.
I haven't yet reviewed where we can use this new approach of a dictionary in the
gw/ code, but I'm at least sure we'll have some usage for it. I use it for a
enhanced way in dealing with WSP session machines for wapbox et al.
Please review and vote.
Stipe
-------------------------------------------------------------------
Kölner Landstrasse 419
40589 Düsseldorf, NRW, Germany
tolj.org system architecture Kannel Software Foundation (KSF)
http://www.tolj.org/ http://www.kannel.org/
mailto:st_{at}_tolj.org mailto:stolj_{at}_kannel.org
-------------------------------------------------------------------
### 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;
+}
