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

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

[Luiz Capitulino]

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 <lcapitulino@redhat.com>
---
 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 <lcapitulino@redhat.com>
+ *
+ * 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 <stddef.h>
+
+#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;
-- 
1.6.4.67.gea5b1

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

[Luiz Capitulino]

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 <lcapitulino@redhat.com>
---
 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
index 6100b35..40fe1b7 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..3901c48
--- /dev/null
+++ b/qdict.c
@@ -0,0 +1,311 @@
+/*
+ * QDict data type.
+ *
+ * Copyright (C) 2009 Red Hat Inc.
+ *
+ * Authors:
+ *  Luiz Capitulino <lcapitulino@redhat.com>
+ *
+ * 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)
+{
+    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 const QType qdict_type = {
+    .code = QTYPE_QDICT,
+    .destroy = qdict_destroy_obj,
+};
diff --git a/qdict.h b/qdict.h
new file mode 100644
index 0000000..911117f
--- /dev/null
+++ b/qdict.h
@@ -0,0 +1,40 @@
+#ifndef QDICT_H
+#define QDICT_H
+
+#include "qint.h"
+#include "qstring.h"
+#include "qobject.h"
+#include <stddef.h>
+
+#define QDICT_HASH_SIZE 512
+
+typedef struct QDictEntry {
+    char *key;
+    QObject *value;
+    struct QDictEntry *next;
+} QDictEntry;
+
+typedef struct QDict {
+    QType_HEAD
+    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);
+QDict *qobject_to_qdict(const QObject *obj);
+
+/* 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);
+
+#endif /* QDICT_H */
diff --git a/qobject.h b/qobject.h
index 61cd4a3..0835a28 100644
--- a/qobject.h
+++ b/qobject.h
@@ -43,6 +43,7 @@ typedef enum {
     QTYPE_NONE,
     QTYPE_QINT,
     QTYPE_QSTRING,
+    QTYPE_QDICT,
 } qtype_code;
 
 struct QObject;
-- 
1.6.4.67.gea5b1

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

[Markus Armbruster]

Luiz Capitulino <lcapitulino@redhat.com> 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 <lcapitulino@redhat.com>
> ---
>  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 <lcapitulino@redhat.com>
> + *
> + * 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
[...]

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

[Luiz Capitulino]

On Mon, 24 Aug 2009 17:40:44 +0200
Markus Armbruster <armbru@redhat.com> wrote:

> Luiz Capitulino <lcapitulino@redhat.com> 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 <lcapitulino@redhat.com>
> > ---
> >  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 <lcapitulino@redhat.com>
> > + *
> > + * 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] [PATCH 04/29] Introduce QDict

[Luiz Capitulino]

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 QDict
- qdict_put()    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_haskey() 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 <lcapitulino@redhat.com>
---
 Makefile  |    2 +-
 qdict.c   |  297 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 qdict.h   |   42 +++++++++
 qobject.h |    1 +
 4 files changed, 341 insertions(+), 1 deletions(-)
 create mode 100644 qdict.c
 create mode 100644 qdict.h

diff --git a/Makefile b/Makefile
index 6307278..bdb6b39 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..cffd23d
--- /dev/null
+++ b/qdict.c
@@ -0,0 +1,297 @@
+/*
+ * QDict data type.
+ *
+ * Copyright (C) 2009 Red Hat Inc.
+ *
+ * Authors:
+ *  Luiz Capitulino <lcapitulino@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+
+#include "qint.h"
+#include "qdict.h"
+#include "qstring.h"
+#include "qobject.h"
+#include "sys-queue.h"
+#include "qemu-common.h"
+
+static const QType qdict_type;
+
+/**
+ * qdict_new(): Create a new QDict
+ *
+ * Return strong 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 *entry;
+
+    entry = qemu_mallocz(sizeof(*entry));
+    entry->key = qemu_strdup(key);
+    entry->value = value;
+
+    return entry;
+}
+
+/**
+ * qdict_find(): List lookup function
+ */
+static QDictEntry *qdict_find(const QDict *qdict,
+                              const char *key, unsigned int hash)
+{
+    QDictEntry *entry;
+
+    LIST_FOREACH(entry, &qdict->table[hash], next)
+        if (!strcmp(entry->key, key))
+            return entry;
+
+    return NULL;
+}
+
+/**
+ * qdict_put_obj(): Put a new QObject into the dictionary
+ *
+ * Insert the pair 'key:value' into 'qdict', if 'key' already exists
+ * its 'value' will be replaced.
+ *
+ * This is done by freeing the reference to the stored QObject and
+ * storing the new one in the same entry.
+ *
+ * NOTE: ownership of 'value' is transferred to the QDict
+ */
+void qdict_put_obj(QDict *qdict, const char *key, QObject *value)
+{
+    unsigned int hash;
+    QDictEntry *entry;
+
+    hash = tdb_hash(key) % QDICT_HASH_SIZE;
+    entry = qdict_find(qdict, key, hash);
+    if (entry) {
+        /* replace key's value */
+        qobject_decref(entry->value);
+        entry->value = value;
+    } else {
+        /* allocate a new entry */
+        entry = alloc_entry(key, value);
+        LIST_INSERT_HEAD(&qdict->table[hash], entry, next);
+    }
+
+    qdict->size++;
+}
+
+/**
+ * qdict_get(): Lookup for a given 'key'
+ *
+ * Return a weak reference to the QObject associated with 'key' if
+ * 'key' is present in the dictionary, NULL otherwise.
+ */
+QObject *qdict_get(const QDict *qdict, const char *key)
+{
+    QDictEntry *entry;
+
+    entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE);
+    return (entry == NULL ? NULL : entry->value);
+}
+
+/**
+ * qdict_haskey(): Check if 'key' exists
+ *
+ * Return 1 if 'key' exists in the dict, 0 otherwise
+ */
+int qdict_haskey(const QDict *qdict, const char *key)
+{
+    unsigned int hash = tdb_hash(key) % QDICT_HASH_SIZE;
+    return (qdict_find(qdict, key, hash) == NULL ? 0 : 1);
+}
+
+/**
+ * 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 integer mapped by 'key'
+ *
+ * This function assumes that 'key' exists and it stores a
+ * QInt object.
+ *
+ * Return integer mapped by 'key'.
+ */
+int64_t qdict_get_int(const QDict *qdict, const char *key)
+{
+    QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT);
+    return qint_get_int(qobject_to_qint(obj));
+}
+
+/**
+ * qdict_get_str(): Get a pointer to the stored string mapped
+ * by 'key'
+ *
+ * This function assumes that 'key' exists and it stores a
+ * QString object.
+ *
+ * Return pointer to the string mapped by 'key'.
+ */
+const char *qdict_get_str(const QDict *qdict, const char *key)
+{
+    QObject *obj = qdict_get_obj(qdict, key, QTYPE_QSTRING);
+    return qstring_get_str(qobject_to_qstring(obj));
+}
+
+/**
+ * qdict_get_try_int(): Try to get integer mapped by 'key'
+ *
+ * Return integer mapped by 'key', if it is not present in
+ * the dictionary or if the stored object is not of QInt type
+ * 'err_value' will be returned.
+ */
+int64_t qdict_get_try_int(const QDict *qdict, const char *key,
+                          int64_t err_value)
+{
+    QObject *obj;
+
+    obj = qdict_get(qdict, key);
+    if (!obj || qobject_type(obj) != QTYPE_QINT)
+        return err_value;
+
+    return qint_get_int(qobject_to_qint(obj));
+}
+
+/**
+ * qdict_get_try_str(): Try to get a pointer to the stored string
+ * mapped by 'key'
+ *
+ * Return a pointer to the string mapped by 'key', if it is not present
+ * in the dictionary or if the stored object is not of QString type
+ * NULL will be returned.
+ */
+const char *qdict_get_try_str(const QDict *qdict, const char *key)
+{
+    QObject *obj;
+
+    obj = qdict_get(qdict, key);
+    if (!obj || qobject_type(obj) != QTYPE_QSTRING)
+        return NULL;
+
+    return qstring_get_str(qobject_to_qstring(obj));
+}
+
+/**
+ * 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)
+{
+    QDictEntry *entry;
+
+    entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE);
+    if (entry) {
+        LIST_REMOVE(entry, next);
+        qentry_destroy(entry);
+        qdict->size--;
+    }
+}
+
+/**
+ * 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 *entry = LIST_FIRST(&qdict->table[i]);
+        while (entry) {
+            QDictEntry *tmp = LIST_NEXT(entry, next);
+            LIST_REMOVE(entry, next);
+            qentry_destroy(entry);
+            entry = tmp;
+        }
+    }
+
+    qemu_free(qdict);
+}
+
+static const QType qdict_type = {
+    .code = QTYPE_QDICT,
+    .destroy = qdict_destroy_obj,
+};
diff --git a/qdict.h b/qdict.h
new file mode 100644
index 0000000..613d163
--- /dev/null
+++ b/qdict.h
@@ -0,0 +1,42 @@
+#ifndef QDICT_H
+#define QDICT_H
+
+#include "qobject.h"
+#include "sys-queue.h"
+#include <stdint.h>
+
+#define QDICT_HASH_SIZE 512
+
+typedef struct QDictEntry {
+    char *key;
+    QObject *value;
+    LIST_ENTRY(QDictEntry) next;
+} QDictEntry;
+
+typedef struct QDict {
+    QObject_HEAD;
+    size_t size;
+    LIST_HEAD(,QDictEntry) table[QDICT_HASH_SIZE];
+} QDict;
+
+/* Object API */
+QDict *qdict_new(void);
+size_t qdict_size(const QDict *qdict);
+void qdict_put_obj(QDict *qdict, const char *key, QObject *value);
+void qdict_del(QDict *qdict, const char *key);
+int qdict_haskey(const QDict *qdict, const char *key);
+QObject *qdict_get(const QDict *qdict, const char *key);
+QDict *qobject_to_qdict(const QObject *obj);
+
+/* Helper to qdict_put_obj(), accepts any object */
+#define qdict_put(qdict, key, obj) \
+        qdict_put_obj(qdict, key, QOBJECT(obj))
+
+/* High level helpers */
+int64_t qdict_get_int(const QDict *qdict, const char *key);
+const char *qdict_get_str(const QDict *qdict, const char *key);
+int64_t qdict_get_try_int(const QDict *qdict, const char *key,
+                          int64_t err_value);
+const char *qdict_get_try_str(const QDict *qdict, const char *key);
+
+#endif /* QDICT_H */
diff --git a/qobject.h b/qobject.h
index 4f84cec..f17397e 100644
--- a/qobject.h
+++ b/qobject.h
@@ -41,6 +41,7 @@ typedef enum {
     QTYPE_NONE,
     QTYPE_QINT,
     QTYPE_QSTRING,
+    QTYPE_QDICT,
 } qtype_code;
 
 struct QObject;
-- 
1.6.4.1.184.g2e117

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

[Luiz Capitulino]

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 QDict
- qdict_put()    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_haskey() 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 <lcapitulino@redhat.com>
---
 Makefile  |    2 +-
 qdict.c   |  297 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 qdict.h   |   42 +++++++++
 qobject.h |    1 +
 4 files changed, 341 insertions(+), 1 deletions(-)
 create mode 100644 qdict.c
 create mode 100644 qdict.h

diff --git a/Makefile b/Makefile
index d7618ba..983fe39 100644
--- a/Makefile
+++ b/Makefile
@@ -91,7 +91,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..cffd23d
--- /dev/null
+++ b/qdict.c
@@ -0,0 +1,297 @@
+/*
+ * QDict data type.
+ *
+ * Copyright (C) 2009 Red Hat Inc.
+ *
+ * Authors:
+ *  Luiz Capitulino <lcapitulino@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+
+#include "qint.h"
+#include "qdict.h"
+#include "qstring.h"
+#include "qobject.h"
+#include "sys-queue.h"
+#include "qemu-common.h"
+
+static const QType qdict_type;
+
+/**
+ * qdict_new(): Create a new QDict
+ *
+ * Return strong 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 *entry;
+
+    entry = qemu_mallocz(sizeof(*entry));
+    entry->key = qemu_strdup(key);
+    entry->value = value;
+
+    return entry;
+}
+
+/**
+ * qdict_find(): List lookup function
+ */
+static QDictEntry *qdict_find(const QDict *qdict,
+                              const char *key, unsigned int hash)
+{
+    QDictEntry *entry;
+
+    LIST_FOREACH(entry, &qdict->table[hash], next)
+        if (!strcmp(entry->key, key))
+            return entry;
+
+    return NULL;
+}
+
+/**
+ * qdict_put_obj(): Put a new QObject into the dictionary
+ *
+ * Insert the pair 'key:value' into 'qdict', if 'key' already exists
+ * its 'value' will be replaced.
+ *
+ * This is done by freeing the reference to the stored QObject and
+ * storing the new one in the same entry.
+ *
+ * NOTE: ownership of 'value' is transferred to the QDict
+ */
+void qdict_put_obj(QDict *qdict, const char *key, QObject *value)
+{
+    unsigned int hash;
+    QDictEntry *entry;
+
+    hash = tdb_hash(key) % QDICT_HASH_SIZE;
+    entry = qdict_find(qdict, key, hash);
+    if (entry) {
+        /* replace key's value */
+        qobject_decref(entry->value);
+        entry->value = value;
+    } else {
+        /* allocate a new entry */
+        entry = alloc_entry(key, value);
+        LIST_INSERT_HEAD(&qdict->table[hash], entry, next);
+    }
+
+    qdict->size++;
+}
+
+/**
+ * qdict_get(): Lookup for a given 'key'
+ *
+ * Return a weak reference to the QObject associated with 'key' if
+ * 'key' is present in the dictionary, NULL otherwise.
+ */
+QObject *qdict_get(const QDict *qdict, const char *key)
+{
+    QDictEntry *entry;
+
+    entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE);
+    return (entry == NULL ? NULL : entry->value);
+}
+
+/**
+ * qdict_haskey(): Check if 'key' exists
+ *
+ * Return 1 if 'key' exists in the dict, 0 otherwise
+ */
+int qdict_haskey(const QDict *qdict, const char *key)
+{
+    unsigned int hash = tdb_hash(key) % QDICT_HASH_SIZE;
+    return (qdict_find(qdict, key, hash) == NULL ? 0 : 1);
+}
+
+/**
+ * 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 integer mapped by 'key'
+ *
+ * This function assumes that 'key' exists and it stores a
+ * QInt object.
+ *
+ * Return integer mapped by 'key'.
+ */
+int64_t qdict_get_int(const QDict *qdict, const char *key)
+{
+    QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT);
+    return qint_get_int(qobject_to_qint(obj));
+}
+
+/**
+ * qdict_get_str(): Get a pointer to the stored string mapped
+ * by 'key'
+ *
+ * This function assumes that 'key' exists and it stores a
+ * QString object.
+ *
+ * Return pointer to the string mapped by 'key'.
+ */
+const char *qdict_get_str(const QDict *qdict, const char *key)
+{
+    QObject *obj = qdict_get_obj(qdict, key, QTYPE_QSTRING);
+    return qstring_get_str(qobject_to_qstring(obj));
+}
+
+/**
+ * qdict_get_try_int(): Try to get integer mapped by 'key'
+ *
+ * Return integer mapped by 'key', if it is not present in
+ * the dictionary or if the stored object is not of QInt type
+ * 'err_value' will be returned.
+ */
+int64_t qdict_get_try_int(const QDict *qdict, const char *key,
+                          int64_t err_value)
+{
+    QObject *obj;
+
+    obj = qdict_get(qdict, key);
+    if (!obj || qobject_type(obj) != QTYPE_QINT)
+        return err_value;
+
+    return qint_get_int(qobject_to_qint(obj));
+}
+
+/**
+ * qdict_get_try_str(): Try to get a pointer to the stored string
+ * mapped by 'key'
+ *
+ * Return a pointer to the string mapped by 'key', if it is not present
+ * in the dictionary or if the stored object is not of QString type
+ * NULL will be returned.
+ */
+const char *qdict_get_try_str(const QDict *qdict, const char *key)
+{
+    QObject *obj;
+
+    obj = qdict_get(qdict, key);
+    if (!obj || qobject_type(obj) != QTYPE_QSTRING)
+        return NULL;
+
+    return qstring_get_str(qobject_to_qstring(obj));
+}
+
+/**
+ * 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)
+{
+    QDictEntry *entry;
+
+    entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_HASH_SIZE);
+    if (entry) {
+        LIST_REMOVE(entry, next);
+        qentry_destroy(entry);
+        qdict->size--;
+    }
+}
+
+/**
+ * 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 *entry = LIST_FIRST(&qdict->table[i]);
+        while (entry) {
+            QDictEntry *tmp = LIST_NEXT(entry, next);
+            LIST_REMOVE(entry, next);
+            qentry_destroy(entry);
+            entry = tmp;
+        }
+    }
+
+    qemu_free(qdict);
+}
+
+static const QType qdict_type = {
+    .code = QTYPE_QDICT,
+    .destroy = qdict_destroy_obj,
+};
diff --git a/qdict.h b/qdict.h
new file mode 100644
index 0000000..613d163
--- /dev/null
+++ b/qdict.h
@@ -0,0 +1,42 @@
+#ifndef QDICT_H
+#define QDICT_H
+
+#include "qobject.h"
+#include "sys-queue.h"
+#include <stdint.h>
+
+#define QDICT_HASH_SIZE 512
+
+typedef struct QDictEntry {
+    char *key;
+    QObject *value;
+    LIST_ENTRY(QDictEntry) next;
+} QDictEntry;
+
+typedef struct QDict {
+    QObject_HEAD;
+    size_t size;
+    LIST_HEAD(,QDictEntry) table[QDICT_HASH_SIZE];
+} QDict;
+
+/* Object API */
+QDict *qdict_new(void);
+size_t qdict_size(const QDict *qdict);
+void qdict_put_obj(QDict *qdict, const char *key, QObject *value);
+void qdict_del(QDict *qdict, const char *key);
+int qdict_haskey(const QDict *qdict, const char *key);
+QObject *qdict_get(const QDict *qdict, const char *key);
+QDict *qobject_to_qdict(const QObject *obj);
+
+/* Helper to qdict_put_obj(), accepts any object */
+#define qdict_put(qdict, key, obj) \
+        qdict_put_obj(qdict, key, QOBJECT(obj))
+
+/* High level helpers */
+int64_t qdict_get_int(const QDict *qdict, const char *key);
+const char *qdict_get_str(const QDict *qdict, const char *key);
+int64_t qdict_get_try_int(const QDict *qdict, const char *key,
+                          int64_t err_value);
+const char *qdict_get_try_str(const QDict *qdict, const char *key);
+
+#endif /* QDICT_H */
diff --git a/qobject.h b/qobject.h
index d4eeb3f..39b8649 100644
--- a/qobject.h
+++ b/qobject.h
@@ -39,6 +39,7 @@ typedef enum {
     QTYPE_NONE,
     QTYPE_QINT,
     QTYPE_QSTRING,
+    QTYPE_QDICT,
 } qtype_code;
 
 struct QObject;
-- 
1.6.4.1.184.g2e117

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

[Programmingkid]

Could you make a tutorial on how to use the QDict type?

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

[Luiz Capitulino]

On Fri, 11 Sep 2015 20:22:38 -0400
Programmingkid <programmingkidx@gmail.com> wrote:

> Could you make a tutorial on how to use the QDict type?

There are several examples in tests/check-qdict.c.

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

[Programmingkid]

On Sep 12, 2015, at 12:10 AM, Luiz Capitulino wrote:

> On Fri, 11 Sep 2015 20:22:38 -0400
> Programmingkid <programmingkidx@gmail.com> wrote:
> 
>> Could you make a tutorial on how to use the QDict type?
> 
> There are several examples in tests/check-qdict.c.

I was hoping for something with a lot more explanation.