From 603476c25c4d588a557ec2139352028f3157cba4 Mon Sep 17 00:00:00 2001 From: "Daniel P. Berrange" Date: Fri, 30 Sep 2016 15:45:25 +0100 Subject: qdict: implement a qdict_crumple method for un-flattening a dict MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The qdict_flatten() method will take a dict whose elements are further nested dicts/lists and flatten them by concatenating keys. The qdict_crumple() method aims to do the reverse, taking a flat qdict, and turning it into a set of nested dicts/lists. It will apply nesting based on the key name, with a '.' indicating a new level in the hierarchy. If the keys in the nested structure are all numeric, it will create a list, otherwise it will create a dict. If the keys are a mixture of numeric and non-numeric, or the numeric keys are not in strictly ascending order, an error will be reported. As an example, a flat dict containing { 'foo.0.bar': 'one', 'foo.0.wizz': '1', 'foo.1.bar': 'two', 'foo.1.wizz': '2' } will get turned into a dict with one element 'foo' whose value is a list. The list elements will each in turn be dicts. { 'foo': [ { 'bar': 'one', 'wizz': '1' }, { 'bar': 'two', 'wizz': '2' } ], } If the key is intended to contain a literal '.', then it must be escaped as '..'. ie a flat dict { 'foo..bar': 'wizz', 'bar.foo..bar': 'eek', 'bar.hello': 'world' } Will end up as { 'foo.bar': 'wizz', 'bar': { 'foo.bar': 'eek', 'hello': 'world' } } The intent of this function is that it allows a set of QemuOpts to be turned into a nested data structure that mirrors the nesting used when the same object is defined over QMP. Reviewed-by: Eric Blake Reviewed-by: Kevin Wolf Reviewed-by: Marc-André Lureau Signed-off-by: Daniel P. Berrange Message-Id: <1475246744-29302-3-git-send-email-berrange@redhat.com> Reviewed-by: Markus Armbruster [Parameter recursive dropped along with its tests; whitespace style touched up] Signed-off-by: Markus Armbruster --- qobject/qdict.c | 277 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 277 insertions(+) (limited to 'qobject') diff --git a/qobject/qdict.c b/qobject/qdict.c index 60f158c3b7..197b0fbd47 100644 --- a/qobject/qdict.c +++ b/qobject/qdict.c @@ -17,6 +17,7 @@ #include "qapi/qmp/qbool.h" #include "qapi/qmp/qstring.h" #include "qapi/qmp/qobject.h" +#include "qapi/error.h" #include "qemu/queue.h" #include "qemu-common.h" #include "qemu/cutils.h" @@ -683,6 +684,282 @@ void qdict_array_split(QDict *src, QList **dst) } } +/** + * qdict_split_flat_key: + * @key: the key string to split + * @prefix: non-NULL pointer to hold extracted prefix + * @suffix: non-NULL pointer to remaining suffix + * + * Given a flattened key such as 'foo.0.bar', split it into two parts + * at the first '.' separator. Allows double dot ('..') to escape the + * normal separator. + * + * e.g. + * 'foo.0.bar' -> prefix='foo' and suffix='0.bar' + * 'foo..0.bar' -> prefix='foo.0' and suffix='bar' + * + * The '..' sequence will be unescaped in the returned 'prefix' + * string. The 'suffix' string will be left in escaped format, so it + * can be fed back into the qdict_split_flat_key() key as the input + * later. + * + * The caller is responsible for freeing the string returned in @prefix + * using g_free(). + */ +static void qdict_split_flat_key(const char *key, char **prefix, + const char **suffix) +{ + const char *separator; + size_t i, j; + + /* Find first '.' separator, but if there is a pair '..' + * that acts as an escape, so skip over '..' */ + separator = NULL; + do { + if (separator) { + separator += 2; + } else { + separator = key; + } + separator = strchr(separator, '.'); + } while (separator && separator[1] == '.'); + + if (separator) { + *prefix = g_strndup(key, separator - key); + *suffix = separator + 1; + } else { + *prefix = g_strdup(key); + *suffix = NULL; + } + + /* Unescape the '..' sequence into '.' */ + for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) { + if ((*prefix)[i] == '.') { + assert((*prefix)[i + 1] == '.'); + i++; + } + (*prefix)[j] = (*prefix)[i]; + } + (*prefix)[j] = '\0'; +} + +/** + * qdict_is_list: + * @maybe_list: dict to check if keys represent list elements. + * + * Determine whether all keys in @maybe_list are valid list elements. + * If @maybe_list is non-zero in length and all the keys look like + * valid list indexes, this will return 1. If @maybe_list is zero + * length or all keys are non-numeric then it will return 0 to indicate + * it is a normal qdict. If there is a mix of numeric and non-numeric + * keys, or the list indexes are non-contiguous, an error is reported. + * + * Returns: 1 if a valid list, 0 if a dict, -1 on error + */ +static int qdict_is_list(QDict *maybe_list, Error **errp) +{ + const QDictEntry *ent; + ssize_t len = 0; + ssize_t max = -1; + int is_list = -1; + int64_t val; + + for (ent = qdict_first(maybe_list); ent != NULL; + ent = qdict_next(maybe_list, ent)) { + + if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) { + if (is_list == -1) { + is_list = 1; + } else if (!is_list) { + error_setg(errp, + "Cannot mix list and non-list keys"); + return -1; + } + len++; + if (val > max) { + max = val; + } + } else { + if (is_list == -1) { + is_list = 0; + } else if (is_list) { + error_setg(errp, + "Cannot mix list and non-list keys"); + return -1; + } + } + } + + if (is_list == -1) { + assert(!qdict_size(maybe_list)); + is_list = 0; + } + + /* NB this isn't a perfect check - e.g. it won't catch + * a list containing '1', '+1', '01', '3', but that + * does not matter - we've still proved that the + * input is a list. It is up the caller to do a + * stricter check if desired */ + if (len != (max + 1)) { + error_setg(errp, "List indices are not contiguous, " + "saw %zd elements but %zd largest index", + len, max); + return -1; + } + + return is_list; +} + +/** + * qdict_crumple: + * @src: the original flat dictionary (only scalar values) to crumple + * + * Takes a flat dictionary whose keys use '.' separator to indicate + * nesting, and values are scalars, and crumples it into a nested + * structure. + * + * To include a literal '.' in a key name, it must be escaped as '..' + * + * For example, an input of: + * + * { 'foo.0.bar': 'one', 'foo.0.wizz': '1', + * 'foo.1.bar': 'two', 'foo.1.wizz': '2' } + * + * will result in an output of: + * + * { + * 'foo': [ + * { 'bar': 'one', 'wizz': '1' }, + * { 'bar': 'two', 'wizz': '2' } + * ], + * } + * + * The following scenarios in the input dict will result in an + * error being returned: + * + * - Any values in @src are non-scalar types + * - If keys in @src imply that a particular level is both a + * list and a dict. e.g., "foo.0.bar" and "foo.eek.bar". + * - If keys in @src imply that a particular level is a list, + * but the indices are non-contiguous. e.g. "foo.0.bar" and + * "foo.2.bar" without any "foo.1.bar" present. + * - If keys in @src represent list indexes, but are not in + * the "%zu" format. e.g. "foo.+0.bar" + * + * Returns: either a QDict or QList for the nested data structure, or NULL + * on error + */ +QObject *qdict_crumple(const QDict *src, Error **errp) +{ + const QDictEntry *ent; + QDict *two_level, *multi_level = NULL; + QObject *dst = NULL, *child; + size_t i; + char *prefix = NULL; + const char *suffix = NULL; + int is_list; + + two_level = qdict_new(); + + /* Step 1: split our totally flat dict into a two level dict */ + for (ent = qdict_first(src); ent != NULL; ent = qdict_next(src, ent)) { + if (qobject_type(ent->value) == QTYPE_QDICT || + qobject_type(ent->value) == QTYPE_QLIST) { + error_setg(errp, "Value %s is not a scalar", + ent->key); + goto error; + } + + qdict_split_flat_key(ent->key, &prefix, &suffix); + + child = qdict_get(two_level, prefix); + if (suffix) { + if (child) { + if (qobject_type(child) != QTYPE_QDICT) { + error_setg(errp, "Key %s prefix is already set as a scalar", + prefix); + goto error; + } + } else { + child = QOBJECT(qdict_new()); + qdict_put_obj(two_level, prefix, child); + } + qobject_incref(ent->value); + qdict_put_obj(qobject_to_qdict(child), suffix, ent->value); + } else { + if (child) { + error_setg(errp, "Key %s prefix is already set as a dict", + prefix); + goto error; + } + qobject_incref(ent->value); + qdict_put_obj(two_level, prefix, ent->value); + } + + g_free(prefix); + prefix = NULL; + } + + /* Step 2: optionally process the two level dict recursively + * into a multi-level dict */ + multi_level = qdict_new(); + for (ent = qdict_first(two_level); ent != NULL; + ent = qdict_next(two_level, ent)) { + + if (qobject_type(ent->value) == QTYPE_QDICT) { + child = qdict_crumple(qobject_to_qdict(ent->value), errp); + if (!child) { + goto error; + } + + qdict_put_obj(multi_level, ent->key, child); + } else { + qobject_incref(ent->value); + qdict_put_obj(multi_level, ent->key, ent->value); + } + } + QDECREF(two_level); + two_level = NULL; + + /* Step 3: detect if we need to turn our dict into list */ + is_list = qdict_is_list(multi_level, errp); + if (is_list < 0) { + goto error; + } + + if (is_list) { + dst = QOBJECT(qlist_new()); + + for (i = 0; i < qdict_size(multi_level); i++) { + char *key = g_strdup_printf("%zu", i); + + child = qdict_get(multi_level, key); + g_free(key); + + if (!child) { + error_setg(errp, "Missing list index %zu", i); + goto error; + } + + qobject_incref(child); + qlist_append_obj(qobject_to_qlist(dst), child); + } + QDECREF(multi_level); + multi_level = NULL; + } else { + dst = QOBJECT(multi_level); + } + + return dst; + + error: + g_free(prefix); + QDECREF(multi_level); + QDECREF(two_level); + qobject_decref(dst); + return NULL; +} + /** * qdict_array_entries(): Returns the number of direct array entries if the * sub-QDict of src specified by the prefix in subqdict (or src itself for -- cgit v1.2.1