From patchwork Mon Aug 3 16:56:58 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luiz Capitulino X-Patchwork-Id: 30654 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [199.232.76.165]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by bilbo.ozlabs.org (Postfix) with ESMTPS id 56CBEB6F1F for ; Tue, 4 Aug 2009 05:22:30 +1000 (EST) Received: from localhost ([127.0.0.1]:57882 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MY374-00070M-Uv for incoming@patchwork.ozlabs.org; Mon, 03 Aug 2009 15:22:26 -0400 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MY0rb-0005x9-Ps for qemu-devel@nongnu.org; Mon, 03 Aug 2009 12:58:19 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MY0rX-0005uw-Pr for qemu-devel@nongnu.org; Mon, 03 Aug 2009 12:58:19 -0400 Received: from [199.232.76.173] (port=55270 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MY0rX-0005up-Er for qemu-devel@nongnu.org; Mon, 03 Aug 2009 12:58:15 -0400 Received: from mx2.redhat.com ([66.187.237.31]:56277) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1MY0rW-00037q-Pr for qemu-devel@nongnu.org; Mon, 03 Aug 2009 12:58:15 -0400 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n73GwEIX026219; Mon, 3 Aug 2009 12:58:14 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n73GwDD6015295; Mon, 3 Aug 2009 12:58:13 -0400 Received: from localhost (vpn-10-1.bos.redhat.com [10.16.10.1]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n73GwBLl030058; Mon, 3 Aug 2009 12:58:12 -0400 From: Luiz Capitulino To: qemu-devel@nongnu.org Date: Mon, 3 Aug 2009 13:56:58 -0300 Message-Id: <1249318642-19324-2-git-send-email-lcapitulino@redhat.com> In-Reply-To: <1249318642-19324-1-git-send-email-lcapitulino@redhat.com> References: <1249318642-19324-1-git-send-email-lcapitulino@redhat.com> X-Scanned-By: MIMEDefang 2.58 on 172.16.27.26 X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Cc: jan.kiszka@siemens.com, aliguori@us.ibm.com, avi@redhat.com Subject: [Qemu-devel] [PATCH 01/25] Introduce QEMU dictionary data type X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org 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 qdict module, which implements a dictionary for QEMU and exports the following functions: - qdict_new() Create a new dictionary - qdict_add() Add a new 'key:value' pair - qdict_get() Get the 'value' of a given 'key' - qdict_exists() Check if a given 'key' exists - qdict_del() Delete a 'key:value' pair - qdict_destroy() Destroy the dictionary - qdict_size() Return the size of the dictionary qdict module uses a chained hash table, whose hash function comes from module-init-tools program. Signed-off-by: Luiz Capitulino --- Makefile | 1 + qdict.c | 183 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ qdict.h | 34 ++++++++++++ 3 files changed, 218 insertions(+), 0 deletions(-) create mode 100644 qdict.c create mode 100644 qdict.h diff --git a/Makefile b/Makefile index d3f999e..41c669f 100644 --- a/Makefile +++ b/Makefile @@ -104,6 +104,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 += qdict.o obj-$(CONFIG_BRLAPI) += baum.o diff --git a/qdict.c b/qdict.c new file mode 100644 index 0000000..8f911b3 --- /dev/null +++ b/qdict.c @@ -0,0 +1,183 @@ +/* + * 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 "qdict.h" +#include "qemu-common.h" + +/** + * qdict_new(): Create a new dictionary data-type + */ +QDict *qdict_new(void) +{ + return qemu_mallocz(sizeof(QDict)); +} + +/** + * 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); +} + +/** + * qdict_find(): Low-level lookup function + */ +static void *qdict_find(const QDict *qdict, + const char *key, unsigned int hash) +{ + QDictEntry *e; + + for (e = qdict->table[hash]; e; e = e->next) + if (!strcmp(e->key, key)) + return e->value; + return NULL; +} + +/** + * qdict_get(): Lookup for a given 'key' + * + * return corresponding 'value' or NULL if 'key' doesn't exist. + */ +void *qdict_get(const QDict *qdict, const char *key) +{ + assert(qdict != NULL); + assert(key != NULL); + return qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE); +} + +/** + * qdict_exists(): Check if 'key' exists + * + * return 1 if 'key' exists in the dict, 0 otherwise + */ +int qdict_exists(const QDict *qdict, const char *key) +{ + QDictEntry *e; + + assert(qdict != NULL); + assert(key != NULL); + + for (e = qdict->table[tdb_hash(key) % QDICT_HASH_SIZE]; e; e = e->next) + if (!strcmp(e->key, key)) + return 1; + return 0; +} + +/** + * alloc_entry(): allocate a new QDictEntry + */ +static QDictEntry *alloc_entry(const char *key, void *value) +{ + QDictEntry *entry; + + entry = qemu_malloc(sizeof(*entry)); + entry->key = qemu_strdup(key); + entry->value = value; + entry->next = NULL; + + return entry; +} + +/** + * qdict_add(): Add a new value into the dictionary + * + * Add the pair 'key:value' into qdict. Does nothing if 'key' already + * exist. + */ +void qdict_add(QDict *qdict, const char *key, void *value) +{ + unsigned int hash; + QDictEntry *entry; + + assert(qdict != NULL); + assert(key != NULL); + + hash = tdb_hash(key) % QDICT_HASH_SIZE; + if (qdict_find(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++; +} + +/** + * qdict_del(): Delete a given 'key' from the dictionary + * + * This will destroy all data allocated by 'key', except 'value' + * which is returned. + */ +void *qdict_del(QDict *qdict, const char *key) +{ + unsigned int hash; + QDictEntry *e, *prev; + + assert(qdict != NULL); + assert(key != NULL); + + prev = NULL; + hash = tdb_hash(key) % QDICT_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; +} + +/** + * qdict_destroy(): Destroy given 'qdict' + * + * This will destroy all data allocated by 'qdict', but added + * values must be freed by the caller. + */ +void qdict_destroy(QDict *qdict) +{ + int i; + + assert(qdict != NULL); + + for (i = 0; i < QDICT_HASH_SIZE; i++) { + QDictEntry *e = qdict->table[i]; + while (e) { + QDictEntry *tmp = e->next; + qemu_free(e->key); + qemu_free(e); + e = tmp; + } + } + + qemu_free(qdict); +} diff --git a/qdict.h b/qdict.h new file mode 100644 index 0000000..89401ed --- /dev/null +++ b/qdict.h @@ -0,0 +1,34 @@ +#ifndef QDICT_H +#define QDICT_H + +#include + +#define QDICT_HASH_SIZE 512 + +typedef struct QDictEntry { + struct QDictEntry *next; + char *key; + void *value; +} QDictEntry; + +typedef struct QDict { + size_t size; + QDictEntry *table[QDICT_HASH_SIZE]; +} QDict; + +/** + * qdict_size(): return the size of the dictionary + */ +static inline size_t qdict_size(const QDict *qdict) +{ + return qdict->size; +} + +QDict *qdict_new(void); +void qdict_add(QDict *qdict, const char *key, void *value); +void *qdict_get(const QDict *qdict, const char *key); +int qdict_exists(const QDict *qdict, const char *key); +void *qdict_del(QDict *qdict, const char *key); +void qdict_destroy(QDict *qdict); + +#endif /* QDICT_H */