| Message ID | 1250723280-3509-5-git-send-email-lcapitulino@redhat.com |
|---|---|
| State | Superseded |
| Headers | show |
On 08/20/2009 02:07 AM, Luiz Capitulino wrote: > 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_put() is both symmetrical with qdict_get(), and also conveys the fact that you can replace an existing key/value. > + > +/** > + * 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)); > +} > I think these wrappers are superfluous, they don't really add much value. > + > +/** > + * 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)); > +} > This assumption does not hold if the dict came from a user.
> + > +/** > + * 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))); This is a _bad_ hash function, especially because 5 is exactly the bit that is flipped between lowercase and uppercase. So "aa" would collide with "Ab". Besides, since the function is additive, you can initialize the value to 0 and add "0x238F13AF * i" at the end (but this is just showing off...). Here is a very simple but good hash function: uintptr_t hashVal = 1497032417; /* arbitrary value */ while (len--) { hashVal += *str++; hashVal += (hashVal << 10); hashVal ^= (hashVal >> 6); } return 1103515243 * value; > +/** > + * 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' Using my proposed nomenclature, "ownership of value is transferred to the QDict". > +void qdict_add_qint(QDict *qdict, const char *key, QInt *qi) I agree with Avi that these do not add much. If anything, make wrappers that accept C datatypes. > +/** > + * qdict_get(): Lookup for a given 'key' > + * > + * Return borrowed reference to QObject if 'key' exists, > + * NULL otherwise. Return a weak reference to the QObject associated with 'key' if the key is present in the dictionary, NULL otherwise. > +/** > + * qdict_del(): Delete a 'key:value' pair from the dictionary > + * > + * This will destroy all data allocated by this entry. ... decrementing the reference count of the QObject associated to 'key'. Paolo
On Thu, 20 Aug 2009 10:57:54 +0300 Avi Kivity <avi@redhat.com> wrote: > On 08/20/2009 02:07 AM, Luiz Capitulino wrote: > > 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_put() is both symmetrical with qdict_get(), and also conveys the > fact that you can replace an existing key/value. Would it be useful in the current Monitor code? If so, how? > > +/** > > + * 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)); > > +} > > > > I think these wrappers are superfluous, they don't really add much value. They exist to avoid always typing QOBJECT(), but a better way would be: #define qdict_add_qtype(qdict, key, qtype) \ qdict_add(qdict, key, QOBJECT(qtype)) I'll do the change. > > +/** > > + * 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)); > > +} > > > > This assumption does not hold if the dict came from a user. Then the user has to know what he or she is doing. :) The problem with high-level functions that receive a QObject but return a plain int is: what do you return if QObject is not an QInt? With QString is possible to return NULL, as you are returning a pointer. But with ints the only solution I found was to not accept this. Note that there is no problem when you are converting between high-level types, like QObject to Qint.
On 08/20/2009 04:57 PM, Luiz Capitulino wrote: > On Thu, 20 Aug 2009 10:57:54 +0300 > Avi Kivity<avi@redhat.com> wrote: > > >> On 08/20/2009 02:07 AM, Luiz Capitulino wrote: >> >>> 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_put() is both symmetrical with qdict_get(), and also conveys the >> fact that you can replace an existing key/value. >> > Would it be useful in the current Monitor code? If so, how? > The current code, no, but once we read qdicts from the monitor, you need to be able to handle { a: 1, a: 2 }. >>> + */ >>> +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)); >>> +} >>> >>> >> This assumption does not hold if the dict came from a user. >> > Then the user has to know what he or she is doing. :) > They don't, as a rule. > The problem with high-level functions that receive a QObject > but return a plain int is: what do you return if QObject is > not an QInt? > Pass a default value to return.
On Thu, 20 Aug 2009 11:00:46 +0200 Paolo Bonzini <bonzini@gnu.org> wrote: > > + > > +/** > > + * 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))); > > This is a _bad_ hash function, especially because 5 is exactly the bit > that is flipped between lowercase and uppercase. So "aa" would collide > with "Ab". > > Besides, since the function is additive, you can initialize the value to > 0 and add "0x238F13AF * i" at the end (but this is just showing off...). > > Here is a very simple but good hash function: > > uintptr_t hashVal = 1497032417; /* arbitrary value */ > > while (len--) > { > hashVal += *str++; > hashVal += (hashVal << 10); > hashVal ^= (hashVal >> 6); > } > > return 1103515243 * value; [ I have to say that I was 100% sure that someone would come with a 'better' hash function, I'm actually impressed it took three submissions to happen. :) ] Well, to be honest I'm not a hash expert and took the first hash function I knew that was used by a widely used program. That said, I would not agree changing the hash function for this series, as we have no code in tree that can be used to really measure this and confirm what is good and what is not. Also, current monitor code will push a maximum of five objects into the dict, looks a minor issue to me.
On Thu, 20 Aug 2009 17:07:25 +0300 Avi Kivity <avi@redhat.com> wrote: > On 08/20/2009 04:57 PM, Luiz Capitulino wrote: > > On Thu, 20 Aug 2009 10:57:54 +0300 > > Avi Kivity<avi@redhat.com> wrote: > > > > > >> On 08/20/2009 02:07 AM, Luiz Capitulino wrote: > >> > >>> 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_put() is both symmetrical with qdict_get(), and also conveys the > >> fact that you can replace an existing key/value. > >> > > Would it be useful in the current Monitor code? If so, how? > > > > The current code, no, but once we read qdicts from the monitor, you need > to be able to handle { a: 1, a: 2 }. qdict_add() will refuse to add an existing key, but I can change it to replace instead. Would this be enough? > >>> + */ > >>> +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)); > >>> +} > >>> > >>> > >> This assumption does not hold if the dict came from a user. > >> > > Then the user has to know what he or she is doing. :) > > > > They don't, as a rule. That's why there's an assert() there. :) > > The problem with high-level functions that receive a QObject > > but return a plain int is: what do you return if QObject is > > not an QInt? > > > > Pass a default value to return. Looks a good solution, although I think both cases are useful. For most handlers, for example, the monitor code _must_ push the key specified in qemu-monitor.hx into the dictionary. Not doing this is a bug. But we also support optional keys, which may or may not be pushed into the dictionary. We need two functions then and this also applies to QString.
On 08/20/2009 06:08 PM, Luiz Capitulino wrote: >> The current code, no, but once we read qdicts from the monitor, you need >> to be able to handle { a: 1, a: 2 }. >> > qdict_add() will refuse to add an existing key, but I can change > it to replace instead. > > Would this be enough? > Yes, that's the standard behaviour. Rename it qdict_put() though. >>>> This assumption does not hold if the dict came from a user. >>>> >>>> >>> Then the user has to know what he or she is doing. :) >>> >>> >> They don't, as a rule. >> > That's why there's an assert() there. :) > You don't want user input triggering asserts (I'm talking user in the sense of something external to the program, not in the sense of code in qemu using this function).
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 [...]
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".
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;
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