From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Mfc9X-00065X-OY for qemu-devel@nongnu.org; Mon, 24 Aug 2009 12:12:15 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Mfc9S-0005wq-DZ for qemu-devel@nongnu.org; Mon, 24 Aug 2009 12:12:14 -0400 Received: from [199.232.76.173] (port=46993 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mfc9S-0005wF-1X for qemu-devel@nongnu.org; Mon, 24 Aug 2009 12:12:10 -0400 Received: from mx1.redhat.com ([209.132.183.28]:45214) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1Mfc9R-0004xC-Ch for qemu-devel@nongnu.org; Mon, 24 Aug 2009 12:12:09 -0400 Date: Mon, 24 Aug 2009 13:11:58 -0300 From: Luiz Capitulino Subject: Re: [Qemu-devel] [PATCH 04/29] Introduce QDict Message-ID: <20090824131158.414fe394@doriath> In-Reply-To: <877hwtjk3n.fsf@pike.pond.sub.org> References: <1250723280-3509-1-git-send-email-lcapitulino@redhat.com> <1250723280-3509-5-git-send-email-lcapitulino@redhat.com> <877hwtjk3n.fsf@pike.pond.sub.org> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Markus Armbruster Cc: aliguori@us.ibm.com, qemu-devel@nongnu.org, avi@redhat.com On Mon, 24 Aug 2009 17:40:44 +0200 Markus Armbruster wrote: > Luiz Capitulino writes: > > > 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 | 311 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > > qdict.h | 40 ++++++++ > > qobject.h | 1 + > > 4 files changed, 353 insertions(+), 1 deletions(-) > > create mode 100644 qdict.c > > create mode 100644 qdict.h > > > > diff --git a/Makefile b/Makefile > [...] > > diff --git a/qdict.c b/qdict.c > > new file mode 100644 > > index 0000000..3901c48 > > --- /dev/null > > +++ b/qdict.c > > @@ -0,0 +1,311 @@ > > +/* > > + * 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 const 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(qdict, &qdict_type); > > + > > + return qdict; > > +} > > + > > +/** > > + * qobject_to_qdict(): Convert a QObject into a QDict > > + */ > > +QDict *qobject_to_qdict(const QObject *obj) > > +{ > > + if (qobject_type(obj) != QTYPE_QDICT) > > + return NULL; > > + > > + return container_of(obj, QDict, base); > > +} > > + > > +/** > > + * 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) > > So this steals unless KEY already exists. Callers who need to know > whether they still own VALUE afterwards have to check whether KEY exists > before. Hmm. What about returning whether the reference was stolen? > > Or just steal unconditionally. Avi has suggested having a qdict_put() with that semantics, I'm already working on this. > Same for the qdict_add_FOO(). > > Is it okay to add a null value? No, although this is not enforced at insertion time. I'll fix in new qdict_put(). Note that supporting this is just a matter of checking if a certain struct member if null at destroy time, but I don't see uses for it as we have agreed the dict will only store QObjects. > > +{ > > + 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; > > +} > > Duplicates the loop from qdict_find(). > > What about > > return qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE) != NULL > > Doesn't work if qdict can contain (key, value) pairs with null values. > Not a problem if qdict_find() returned e (of type QDictEntry *) instead > of e->value (of type void *). This code is somewhat different now and the duplication is already gone, as I have ported QDict to use list functions from "sys-queue.h".