From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MVuoG-0000BS-EZ for qemu-devel@nongnu.org; Tue, 28 Jul 2009 18:06:12 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MVuoB-0008Qf-FS for qemu-devel@nongnu.org; Tue, 28 Jul 2009 18:06:11 -0400 Received: from [199.232.76.173] (port=49633 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MVuoB-0008QQ-9k for qemu-devel@nongnu.org; Tue, 28 Jul 2009 18:06:07 -0400 Received: from mx2.redhat.com ([66.187.237.31]:37479) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1MVuoA-0000Uu-GB for qemu-devel@nongnu.org; Tue, 28 Jul 2009 18:06:06 -0400 From: Luiz Capitulino Date: Tue, 28 Jul 2009 19:04:49 -0300 Message-Id: <1248818713-11261-2-git-send-email-lcapitulino@redhat.com> In-Reply-To: <1248818713-11261-1-git-send-email-lcapitulino@redhat.com> References: <1248818713-11261-1-git-send-email-lcapitulino@redhat.com> Subject: [Qemu-devel] [PATCH 01/25] Introduce QEMU dictionary data type List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: jan.kiszka@siemens.com, aliguori@us.ibm.com, dlaor@redhat.com, avi@redhat.com, Luiz Capitulino A dictionary is a high-level data type used to store a collection of values, where a unique key is associated with one value. Usually, the notation 'key:value' is used to denote this relationship. This commit adds the qemu-dict module, which implements a dictionary for QEMU and exports the following functions: - qemu_dict_create() Create a new dictionary - qemu_dict_add() Add a new 'key:value' pair - qemu_dict_get() Get the 'value' of a given 'key' - qemu_dict_exists() Check if a given 'key' exists - qemu_dict_del() Delete a 'key:value' pair - qemu_dict_destroy() Destroy the dictionary - qemu_dict_walk() Walk through the dictionary values - qemu_dict_size() Return the size of the dictionary qemu-dict module uses a chained hash table, whose hash function comes from module-init-tools program. Signed-off-by: Luiz Capitulino --- Makefile | 1 + qemu-dict.c | 215 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ qemu-dict.h | 36 ++++++++++ 3 files changed, 252 insertions(+), 0 deletions(-) create mode 100644 qemu-dict.c create mode 100644 qemu-dict.h diff --git a/Makefile b/Makefile index c510ff3..b36786d 100644 --- a/Makefile +++ b/Makefile @@ -97,6 +97,7 @@ obj-y += buffered_file.o migration.o migration-tcp.o net.o qemu-sockets.o obj-y += qemu-char.o aio.o net-checksum.o savevm.o obj-y += msmouse.o ps2.o obj-y += qdev.o qdev-properties.o ssi.o +obj-y += qemu-dict.o obj-$(CONFIG_BRLAPI) += baum.o diff --git a/qemu-dict.c b/qemu-dict.c new file mode 100644 index 0000000..ad2d6d9 --- /dev/null +++ b/qemu-dict.c @@ -0,0 +1,215 @@ +/* + * QEMU dictionary data type. + * + * Copyright (C) 2009 Red Hat Inc. + * + * Authors: + * Luiz Capitulino + * + * This work is licensed under the terms of the GNU GPL, version 2. See + * the COPYING file in the top-level directory. + */ + +#include "qemu-dict.h" +#include "qemu-common.h" + +/** + * qemu_dict_create(): Create a new dictionary data-type + */ +struct qemu_dict *qemu_dict_create(void) +{ + return qemu_mallocz(sizeof(struct qemu_dict)); +} + +/** + * tdb_hash(): based on the hash agorithm from gdbm, via tdb + * (from module-init-tools) + */ +static unsigned int tdb_hash(const char *name) +{ + unsigned value; /* Used to compute the hash value. */ + unsigned i; /* Used to cycle through random values. */ + + /* Set the initial value from the key size. */ + for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++) + value = (value + (((const unsigned char *)name)[i] << (i*5 % 24))); + + return (1103515243 * value + 12345); +} + +/** + * __qemu_dict_get(): Low-level lookup function + */ +static void *__qemu_dict_get(const struct qemu_dict *qdict, + const char *key, unsigned int hash) +{ + struct qemu_dict_entry *e; + + for (e = qdict->table[hash]; e; e = e->next) + if (!strcmp(e->key, key)) + return e->value; + return NULL; +} + +/** + * qemu_dict_get(): Lookup for a given 'key' + * + * return corresponding 'value' or NULL if 'key' doesn't exist. + */ +void *qemu_dict_get(const struct qemu_dict *qdict, const char *key) +{ + assert(qdict != NULL); + assert(key != NULL); + return __qemu_dict_get(qdict, key, tdb_hash(key) % QEMU_DICT_HASH_SIZE); +} + +/** + * qemu_dict_exists(): Check if 'key' exists + * + * return 1 if 'key' exists in the dict, 0 otherwise + */ +int qemu_dict_exists(const struct qemu_dict *qdict, const char *key) +{ + struct qemu_dict_entry *e; + + assert(qdict != NULL); + assert(key != NULL); + + for (e = qdict->table[tdb_hash(key) % QEMU_DICT_HASH_SIZE]; e; e = e->next) + if (!strcmp(e->key, key)) + return 1; + return 0; +} + +/** + * alloc_entry(): allocate a new qemu_dict_entry + */ +static struct qemu_dict_entry *alloc_entry(const char *key, void *value) +{ + struct qemu_dict_entry *entry; + + entry = qemu_malloc(sizeof(*entry)); + entry->key = qemu_strdup(key); + entry->value = value; + entry->next = NULL; + + return entry; +} + +/** + * qemu_dict_add(): Add a new value into the dictionary + * + * Add the pair 'key:value' into qdict. Does nothing if 'key' already + * exist. + */ +void qemu_dict_add(struct qemu_dict *qdict, const char *key, void *value) +{ + unsigned int hash; + struct qemu_dict_entry *entry; + + assert(qdict != NULL); + assert(key != NULL); + + hash = tdb_hash(key) % QEMU_DICT_HASH_SIZE; + if (__qemu_dict_get(qdict, key, hash)) { + /* Don't add again if it's already there */ + return; + } + + entry = alloc_entry(key, value); + entry->next = qdict->table[hash]; + qdict->table[hash] = entry; + qdict->size++; +} + +/** + * qemu_dict_del(): Delete a given 'key' from the dictionary + * + * This will destroy all data allocated by 'key', except 'value' + * which is returned. + */ +void *qemu_dict_del(struct qemu_dict *qdict, const char *key) +{ + unsigned int hash; + struct qemu_dict_entry *e, *prev; + + assert(qdict != NULL); + assert(key != NULL); + + prev = NULL; + hash = tdb_hash(key) % QEMU_DICT_HASH_SIZE; + for (e = qdict->table[hash]; e; e = e->next) { + if (!strcmp(e->key, key)) { + void *value = e->value; + if (!prev) + qdict->table[hash] = e->next; + else + prev->next = e->next; + qemu_free(e->key); + qemu_free(e); + qdict->size--; + return value; + } + + prev = e; + } + + return NULL; +} + +/** + * qemu_dict_destroy(): Destroy given 'qdict' + * + * This will destroy all data allocated by 'qdict', but added + * values must be freed by the caller. + */ +void qemu_dict_destroy(struct qemu_dict *qdict) +{ + int i; + + assert(qdict != NULL); + + for (i = 0; i < QEMU_DICT_HASH_SIZE; i++) { + struct qemu_dict_entry *e = qdict->table[i]; + while (e) { + struct qemu_dict_entry *tmp = e->next; + qemu_free(e->key); + qemu_free(e); + e = tmp; + } + } + + qemu_free(qdict); +} + +/** + * qemu_dict_walk(): Walk through dictionary contents + * + * This function can be used by users to "walk through" + * the data stored in the dictionary. + * + * In order to use this the caller has pass a pointer + * to a function with the following signature: + * + * void walkf(const char *key, void *value); + * + * Then, when qemu_dict_walk() is called, it will + * "walk through" all the dictionary data, passing + * each stored value to walkf(). + */ +void qemu_dict_walk(const struct qemu_dict *qdict, + void (*walkf)(const char *key, void *value)) +{ + int i; + + assert(qdict != NULL); + assert(walkf != NULL); + + for (i = 0; i < QEMU_DICT_HASH_SIZE; i++) { + struct qemu_dict_entry *e = qdict->table[i]; + while (e) { + walkf(e->key, e->value); + e = e->next; + } + } +} diff --git a/qemu-dict.h b/qemu-dict.h new file mode 100644 index 0000000..89324db --- /dev/null +++ b/qemu-dict.h @@ -0,0 +1,36 @@ +#ifndef __QEMU_DICT_H__ +#define __QEMU_DICT_H__ + +#include + +#define QEMU_DICT_HASH_SIZE 512 + +struct qemu_dict_entry { + struct qemu_dict_entry *next; + char *key; + void *value; +}; + +struct qemu_dict { + size_t size; + struct qemu_dict_entry *table[QEMU_DICT_HASH_SIZE]; +}; + +/** + * qemu_dict_size(): return the size of the dictionary + */ +static inline size_t qemu_dict_size(const struct qemu_dict *qdict) +{ + return qdict->size; +} + +struct qemu_dict *qemu_dict_create(void); +void qemu_dict_add(struct qemu_dict *qdict, const char *key, void *value); +void *qemu_dict_get(const struct qemu_dict *qdict, const char *key); +int qemu_dict_exists(const struct qemu_dict *qdict, const char *key); +void *qemu_dict_del(struct qemu_dict *qdict, const char *key); +void qemu_dict_destroy(struct qemu_dict *qdict); +void qemu_dict_walk(const struct qemu_dict *qdict, + void (*walkf)(const char *key, void *value)); + +#endif /* __QEMU_DICT_H__ */ -- 1.6.4.rc3.12.gdf73a