On Wed, Mar 02, 2016 at 05:13:59PM +0100, Max Reitz wrote:
> On 19.02.2016 17:47, Daniel P. Berrange wrote:
> > 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 todo 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 nested
> > used when the same object is defined over QMP.
> >
> > Signed-off-by: Daniel P. Berrange <berra...@redhat.com>
> > ---
> > include/qapi/qmp/qdict.h | 1 +
> > qobject/qdict.c | 180
> > +++++++++++++++++++++++++++++++++++++++++++++++
> > tests/check-qdict.c | 39 ++++++++++
> > 3 files changed, 220 insertions(+)
> >
> > +QObject *qdict_crumple(QDict *src, Error **errp)
> > +{
> > + const QDictEntry *entry, *next;
> > + const char *p = NULL;
> > + QDict *tmp1 = NULL, *tmp2 = NULL;
> > + QObject *dst = NULL, *child;
> > + bool isList = false;
> > + ssize_t listMax = -1;
> > + size_t listLen = 0;
>
> As far as I'm aware we don't have any strict policy on names, but in
> general structs use UpperCamelCase and variables and functions use
> c_style_naming.
Yep, ok
> > + size_t i, j;
> > + int64_t val;
> > + char *key;
> > +
> > + tmp1 = qdict_new();
>
> I guess I'd like clearer variable names.
Sure
>
> > + entry = qdict_first(src);
> > +
> > + /* Step 1: extract everything as nested dicts */
> > + while (entry != NULL) {
> > + next = qdict_next(src, entry);
> > + qobject_incref(entry->value);
> > +
> > + /* Find first '.' separator, but treat '..' as
> > + * an escape sequence */
> > + p = NULL;
>
> How about at least "dot" or "separator"?
Sure.
> > + do {
> > + if (p) {
> > + p += 2;
> > + } else {
> > + p = entry->key;
> > + }
> > + p = strchr(p, '.');
> > + } while (p && *(p + 1) == '.');
> > +
> > + if (p) {
> > + key = g_strndup(entry->key,
> > + p - entry->key);
> > + } else {
> > + key = g_strdup(entry->key);
> > + }
> > +
> > + for (i = 0, j = 0; key[i] != '\0'; i++, j++) {
> > + if (key[i] == '.' &&
> > + key[i + 1] == '.') {
> > + i++;
> > + }
> > + key[j] = key[i];
> > + }
> > + key[j] = '\0';
>
> I general I think it would be nice to put this escaping code into an own
> static function which returns a strdup'd key for the QDict and this
> entry's key in that QDict.
Yep, good idea.
>
> > +
> > + if (p) {
> > + tmp2 = qdict_get_qdict(tmp1, key);
> > + p++;
> > + if (!tmp2) {
> > + tmp2 = qdict_new();
> > + qdict_put(tmp1, key, tmp2);
>
> This...
>
> > + }
> > + qdict_put_obj(tmp2, p, entry->value);
> > + } else {
> > + qdict_put_obj(tmp1, key, entry->value);
>
> ...and this may silently overwrite entries, e.g. when crumpling
>
> { "x": 42, "x.y": 23 }
>
> > + }
>
> key is leaked.
Oh that should result in an error being raised as it is
a contradictory input.
> > +
> > + entry = next;
> > + }
> > +
> > + /* Step 2: crumple the new dicts we just created */
> > + tmp2 = qdict_new();
>
> Please use more variables with clearer names.
>
> > + entry = qdict_first(tmp1);
> > + while (entry != NULL) {
> > + next = qdict_next(tmp1, entry);
> > +
> > + if (qobject_type(entry->value) == QTYPE_QDICT) {
> > + child = qdict_crumple((QDict *)entry->value, errp);
>
> The cast works, but I'd prefer qobject_to_qdict() nonetheless.
Ok
>
> > + if (!child) {
> > + goto error;
> > + }
> > +
> > + qdict_put_obj(tmp2, entry->key, child);
> > + } else {
> > + qobject_incref(entry->value);
> > + qdict_put_obj(tmp2, entry->key, entry->value);
> > + }
> > +
> > + entry = next;
> > + }
> > + QDECREF(tmp1);
> > +
> > + /* Step 3: detect if we need to turn our dict into list */
>
> You could use qdict_array_entries(tmp2, "") > 0 for this.
>
> If you do want to make { "0": 42, "2": 23 } and { "0": 42, "x": 23 }
> errors (my qdict_unflatten() just kept those QDicts), then you'd have to
> check on qdict_array_entries() error whether the QDict contained an
> integer key, but that would still be simpler than the following loop and
> the check in step 4.
If I use qdict_array_entries() then it does 2 O(N) iterations
of the input qdict, and to check the errors, I'll have todo
yet another iteration. My inlined code here does everything
in a single O(N) iteration instead of 3. I think that's
compelling enough to reason to not use that function.
> > + entry = qdict_first(tmp2);
> > + while (entry != NULL) {
> > + next = qdict_next(tmp2, entry);
> > +
> > + errno = 0;
> > + if (qemu_strtoll(entry->key, NULL, 10, &val) == 0) {
> > + if (!dst) {
> > + dst = (QObject *)qlist_new();
> > + isList = true;
> > + } else if (!isList) {
> > + error_setg(errp,
> > + "Key '%s' is for a list, but previous key is "
> > + "for a dict", entry->key);
> > + goto error;
> > + }
> > + listLen++;
> > + if (val > listMax) {
> > + listMax = val;
> > + }
> > + } else {
> > + if (!dst) {
> > + dst = (QObject *)tmp2;
> > + qobject_incref(dst);
> > + isList = false;
> > + } else if (isList) {
> > + error_setg(errp,
> > + "Key '%s' is for a dict, but previous key is "
> > + "for a list", entry->key);
> > + goto error;
> > + }
> > + }
> > +
> > + entry = next;
> > + }
> > +
> > + /* Step 4: Turn the dict into a list */
>
> Why not just use qdict_array_split(tmp2, &dst);?
Again qdict_array_split() is a pretty inefficiently written
function. It does multiple nested iterations over its input
giving it O(n^2) time, compared to O(n) for my code here.
The only user of qdict_array_entries() and qdict_array_split()
is the block quorum driver. From a brief look at that code
I think it could probably be changed to just call this new
qdict_crumple() method, and those 2 inefficient functions
could be deleted, so we don't have duplication of code.
> > + if (isList) {
> > + if (listLen != (listMax + 1)) {
> > + error_setg(errp, "List indexes are not continuous, "
> > + "saw %zu elements but %zu largest index",
> > + listLen, listMax);
> > + goto error;
> > + }
> > +
> > + for (i = 0; i < listLen; i++) {
> > + char *key = g_strdup_printf("%zu", i);
> > +
> > + child = qdict_get(tmp2, key);
> > + g_free(key);
> > + if (!child) {
> > + error_setg(errp, "Unexpected missing list entry %zu", i);
> > + goto error;
> > + }
> > +
> > + qobject_incref(child);
> > + qlist_append_obj((QList *)dst, child);
> > + }
> > + }
> > + QDECREF(tmp2);
> > +
> > + return dst;
> > +
> > + error:
> > + QDECREF(tmp2);
> > + QDECREF(tmp1);
> > + qobject_decref(dst);
> > + return NULL;
> > +}
> > +
> > +
Regards,
Daniel
--
|: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org -o- http://virt-manager.org :|
|: http://autobuild.org -o- http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|
