[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH 04/29] Introduce QDict
From: |
Luiz Capitulino |
Subject: |
Re: [Qemu-devel] [PATCH 04/29] Introduce QDict |
Date: |
Mon, 24 Aug 2009 13:11:58 -0300 |
On Mon, 24 Aug 2009 17:40:44 +0200
Markus Armbruster <address@hidden> wrote:
> Luiz Capitulino <address@hidden> 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 <address@hidden>
> > ---
> > 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 <address@hidden>
> > + *
> > + * 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".
- [Qemu-devel] Re: [PATCH 03/29] Introduce QString, (continued)
[Qemu-devel] Re: [PATCH 04/29] Introduce QDict, Paolo Bonzini, 2009/08/20
Re: [Qemu-devel] [PATCH 04/29] Introduce QDict, Markus Armbruster, 2009/08/24
- Re: [Qemu-devel] [PATCH 04/29] Introduce QDict,
Luiz Capitulino <=
[Qemu-devel] [PATCH 05/29] Add wrappers to functions used by the Monitor, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 06/29] monitor: New format for handlers argument types, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 07/29] monitor: Setup a QDict with arguments to handlers, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 08/29] monitor: Export QDict header, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 09/29] monitor: Port handler_0 to use QDict, Luiz Capitulino, 2009/08/19