Re: [Qemu-devel] [PATCH 04/29] Introduce QDict

[Markus Armbruster]

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.

Same for the qdict_add_FOO().

Is it okay to add a null 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;
> +}

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 *).

> +
> +/**
> + * 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;
> +    }
> +}

Duplicates the loop from qdict_find().  I figure it could quse
qdict_find() if it returned e instead of e->value.

> +
> +/**
> + * 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 const QType qdict_type = {
> +    .code = QTYPE_QDICT,
> +    .destroy = qdict_destroy_obj,
> +};
> diff --git a/qdict.h b/qdict.h
[...]
> diff --git a/qobject.h b/qobject.h
[...]