From patchwork Thu Aug 13 13:50:03 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luiz Capitulino X-Patchwork-Id: 31303 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 3E5F0B6F2B for ; Thu, 13 Aug 2009 23:59:34 +1000 (EST) Received: from localhost ([127.0.0.1]:57949 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mbaq2-00046E-4Z for incoming@patchwork.ozlabs.org; Thu, 13 Aug 2009 09:59:30 -0400 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Mbai4-0000Ly-Qr for qemu-devel@nongnu.org; Thu, 13 Aug 2009 09:51:16 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Mbahy-0000Bv-Dv for qemu-devel@nongnu.org; Thu, 13 Aug 2009 09:51:15 -0400 Received: from [199.232.76.173] (port=33489 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mbahy-0000BI-0g for qemu-devel@nongnu.org; Thu, 13 Aug 2009 09:51:10 -0400 Received: from mx2.redhat.com ([66.187.237.31]:45065) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1Mbahw-0003DH-TK for qemu-devel@nongnu.org; Thu, 13 Aug 2009 09:51:09 -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 n7DDp8kX023171; Thu, 13 Aug 2009 09:51:08 -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 n7DDp7MM027235; Thu, 13 Aug 2009 09:51:07 -0400 Received: from localhost (vpn-10-83.bos.redhat.com [10.16.10.83]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n7DDp5Io012104; Thu, 13 Aug 2009 09:51:06 -0400 From: Luiz Capitulino To: qemu-devel@nongnu.org Date: Thu, 13 Aug 2009 10:50:03 -0300 Message-Id: <1250171428-29308-5-git-send-email-lcapitulino@redhat.com> In-Reply-To: <1250171428-29308-1-git-send-email-lcapitulino@redhat.com> References: <1250171428-29308-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: aliguori@us.ibm.com, avi@redhat.com Subject: [Qemu-devel] [PATCH 04/29] Introduce QDict 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 QDict is a high-level dictionary data type that can be used to store a collection of QObjects. A unique key is associated with only one QObject. The following functions are available: - qdict_new() Create a new dictionary - qdict_add() Add a new 'key:object' pair - qdict_get() Get the QObject of a given key - qdict_del() Delete a 'key:object' pair - qdict_size() Return the size of the dictionary - qdict_exists() Check if a given 'key' exists Some high-level helpers to operate on QStrings and QInts objects are also provided. Signed-off-by: Luiz Capitulino --- Makefile | 2 +- qdict.c | 300 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ qdict.h | 47 ++++++++++ qobject.h | 1 + 4 files changed, 349 insertions(+), 1 deletions(-) create mode 100644 qdict.c create mode 100644 qdict.h diff --git a/Makefile b/Makefile index 47cc532..2310a31 100644 --- a/Makefile +++ b/Makefile @@ -90,7 +90,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 += qint.o qstring.o +obj-y += qint.o qstring.o qdict.o obj-$(CONFIG_BRLAPI) += baum.o obj-$(CONFIG_WIN32) += tap-win32.o diff --git a/qdict.c b/qdict.c new file mode 100644 index 0000000..9a75e3c --- /dev/null +++ b/qdict.c @@ -0,0 +1,300 @@ +/* + * QDict 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 "qobject.h" +#include "qemu-common.h" + +static QType qdict_type; + +/** + * qdict_new(): Create a new dictionary data-type + * + * Return new reference. + */ +QDict *qdict_new(void) +{ + QDict *qdict; + + qdict = qemu_mallocz(sizeof(*qdict)); + qobject_init(QOBJECT(qdict), &qdict_type); + + return 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); +} + +/** + * alloc_entry(): allocate a new QDictEntry + */ +static QDictEntry *alloc_entry(const char *key, QObject *value, + QDictEntry *next) +{ + QDictEntry *entry; + + entry = qemu_malloc(sizeof(*entry)); + entry->key = qemu_strdup(key); + entry->value = value; + entry->next = next; + + return entry; +} + +/** + * 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_add(): Add a new object into the dictionary + * + * Add the pair 'key:value' into qdict. Does nothing if 'key' already + * exist. + * + * NOTE: this function 'steals' a reference to 'value' + */ +void qdict_add(QDict *qdict, const char *key, QObject *value) +{ + unsigned int hash; + QDictEntry *entry; + + 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, qdict->table[hash]); + qdict->table[hash] = entry; + qdict->size++; +} + +/** + * qdict_add_qint(): Add a new QInt into the dictionary + * + * Add the pair 'key:qint' into qdict. Does nothing if 'key' already + * exist. + * + * NOTE: this function 'steals' a reference to 'qi' + */ +void qdict_add_qint(QDict *qdict, const char *key, QInt *qi) +{ + qdict_add(qdict, key, QOBJECT(qi)); +} + +/** + * qdict_add_qstring(): Add a new QString into the dictionary + * + * Add the pair 'key:qstring' into qdict. Does nothing if 'key' already + * exist. + * + * NOTE: this function 'steals' a reference to 'qs' + */ +void qdict_add_qstring(QDict *qdict, const char *key, QString *qs) +{ + qdict_add(qdict, key, QOBJECT(qs)); +} + +/** + * qdict_get(): Lookup for a given 'key' + * + * Return borrowed reference to QObject if 'key' exists, + * NULL otherwise. + */ +QObject *qdict_get(const QDict *qdict, const char *key) +{ + return qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE); +} + +/** + * qdict_size(): Return the size of the dictionary + */ +size_t qdict_size(const QDict *qdict) +{ + return qdict->size; +} + +/** + * qdict_get_obj(): Get a QObject of a specific type. + */ +static QObject *qdict_get_obj(const QDict *qdict, const char *key, + qtype_code type) +{ + QObject *obj; + + obj = qdict_get(qdict, key); + assert(obj != NULL); + assert(qobject_type(obj) == type); + + return obj; +} + +/** + * qdict_get_int(): Get an int value mapped by 'key' + * + * This function assumes that 'key' exists and it stores a + * QInt object. + */ +int qdict_get_int(const QDict *qdict, const char *key) +{ + QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT); + return qint_to_int(qobject_to_qint(obj)); +} + +/** + * qdict_get_uint32(): Get an uint32_t value mapped by 'key' + * + * This function assumes that 'key' exists and it stores a + * QInt object. + */ +uint32_t qdict_get_uint32(const QDict *qdict, const char *key) +{ + QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT); + return qint_to_uint32(qobject_to_qint(obj)); +} + +/** + * qdict_get_uint64(): Get an uint64_t value mapped by 'key' + * + * This function assumes that 'key' exists and it stores a + * QInt object. + */ +uint64_t qdict_get_uint64(const QDict *qdict, const char *key) +{ + QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT); + return qint_to_uint64(qobject_to_qint(obj)); +} + +/** + * qdict_get_str(): Get a pointer to the stored string mapped + * by 'key' + * + * return the string pointer on success, NULL if 'key' doesn't + * exist. + */ +const char *qdict_get_str(const QDict *qdict, const char *key) +{ + QObject *obj; + + obj = qdict_get(qdict, key); + if (!obj) + return NULL; + + assert(qobject_type(obj) == QTYPE_QSTRING); + return qstring_get_str(qobject_to_qstring(obj)); +} + +/** + * 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; + + for (e = qdict->table[tdb_hash(key) % QDICT_HASH_SIZE]; e; e = e->next) + if (!strcmp(e->key, key)) + return 1; + return 0; +} + +/** + * qentry_destroy(): Free all the memory allocated by a QDictEntry + */ +static void qentry_destroy(QDictEntry *e) +{ + assert(e != NULL); + assert(e->key != NULL); + assert(e->value != NULL); + + qobject_decref(e->value); + qemu_free(e->key); + qemu_free(e); +} + +/** + * qdict_del(): Delete a 'key:value' pair from the dictionary + * + * This will destroy all data allocated by this entry. + */ +void qdict_del(QDict *qdict, const char *key) +{ + unsigned int hash; + QDictEntry *e, *prev; + + prev = NULL; + hash = tdb_hash(key) % QDICT_HASH_SIZE; + for (e = qdict->table[hash]; e; e = e->next) { + if (!strcmp(e->key, key)) { + if (!prev) + qdict->table[hash] = e->next; + else + prev->next = e->next; + qentry_destroy(e); + qdict->size--; + return; + } + prev = e; + } +} + +/** + * qdict_destroy_obj(): Free all the memory allocated by a QDict + */ +static void qdict_destroy_obj(QObject *obj) +{ + int i; + QDict *qdict; + + assert(obj != NULL); + qdict = qobject_to_qdict(obj); + + for (i = 0; i < QDICT_HASH_SIZE; i++) { + QDictEntry *e = qdict->table[i]; + while (e) { + QDictEntry *tmp = e->next; + qentry_destroy(e); + e = tmp; + } + } + + qemu_free(qdict); +} + +static QType qdict_type = { + .code = QTYPE_QDICT, + .destroy = qdict_destroy_obj, +}; diff --git a/qdict.h b/qdict.h new file mode 100644 index 0000000..1500b8c --- /dev/null +++ b/qdict.h @@ -0,0 +1,47 @@ +#ifndef QDICT_H +#define QDICT_H + +#include "qint.h" +#include "qstring.h" +#include "qobject.h" +#include + +#define QDICT_HASH_SIZE 512 + +typedef struct QDictEntry { + char *key; + QObject *value; + struct QDictEntry *next; +} QDictEntry; + +typedef struct QDict { + QObject base; + size_t size; + QDictEntry *table[QDICT_HASH_SIZE]; +} QDict; + +/* Object API */ +QDict *qdict_new(void); +size_t qdict_size(const QDict *qdict); +void qdict_add(QDict *qdict, const char *key, QObject *value); +void qdict_del(QDict *qdict, const char *key); +int qdict_exists(const QDict *qdict, const char *key); +QObject *qdict_get(const QDict *qdict, const char *key); + +/* High level helpers */ +int qdict_get_int(const QDict *qdict, const char *key); +uint32_t qdict_get_uint32(const QDict *qdict, const char *key); +uint64_t qdict_get_uint64(const QDict *qdict, const char *key); +const char *qdict_get_str(const QDict *qdict, const char *key); +void qdict_add_qint(QDict *qdict, const char *key, QInt *qi); +void qdict_add_qstring(QDict *qdict, const char *key, QString *qs); + +/** + * qobject_to_qdict(): Convert a QObject into a QDict + */ +static inline QDict *qobject_to_qdict(const QObject *obj) +{ + return container_of(obj, QDict, base); +} + +#endif /* QDICT_H */ diff --git a/qobject.h b/qobject.h index c1bdae7..52df5ff 100644 --- a/qobject.h +++ b/qobject.h @@ -42,6 +42,7 @@ typedef enum { QTYPE_NONE, QTYPE_QINT, QTYPE_QSTRING, + QTYPE_QDICT, } qtype_code; struct QObject;