qobject/qdict.c

   1 /*
   2  * QDict Module
   3  *
   4  * Copyright (C) 2009 Red Hat Inc.
   5  *
   6  * Authors:
   7  *  Luiz Capitulino <lcapitulino@redhat.com>
   8  *
   9  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
  10  * See the COPYING.LIB file in the top-level directory.
  11  */
  12
  13 #include "qapi/qmp/qint.h"
  14 #include "qapi/qmp/qfloat.h"
  15 #include "qapi/qmp/qdict.h"
  16 #include "qapi/qmp/qbool.h"
  17 #include "qapi/qmp/qstring.h"
  18 #include "qapi/qmp/qobject.h"
  19 #include "qemu/queue.h"
  20 #include "qemu-common.h"
  21
  22 static void qdict_destroy_obj(QObject *obj);
  23
  24 static const QType qdict_type = {
  25     .code = QTYPE_QDICT,
  26     .destroy = qdict_destroy_obj,
  27 };
  28
  29 /**
  30  * qdict_new(): Create a new QDict
  31  *
  32  * Return strong reference.
  33  */
  34 QDict *qdict_new(void)
  35 {
  36     QDict *qdict;
  37
  38     qdict = g_malloc0(sizeof(*qdict));
  39     QOBJECT_INIT(qdict, &qdict_type);
  40
  41     return qdict;
  42 }
  43
  44 /**
  45  * qobject_to_qdict(): Convert a QObject into a QDict
  46  */
  47 QDict *qobject_to_qdict(const QObject *obj)
  48 {
  49     if (qobject_type(obj) != QTYPE_QDICT)
  50         return NULL;
  51
  52     return container_of(obj, QDict, base);
  53 }
  54
  55 /**
  56  * tdb_hash(): based on the hash agorithm from gdbm, via tdb
  57  * (from module-init-tools)
  58  */
  59 static unsigned int tdb_hash(const char *name)
  60 {
  61     unsigned value;     /* Used to compute the hash value.  */
  62     unsigned   i;       /* Used to cycle through random values. */
  63
  64     /* Set the initial value from the key size. */
  65     for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
  66         value = (value + (((const unsigned char *)name)[i] << (i*5 % 24)));
  67
  68     return (1103515243 * value + 12345);
  69 }
  70
  71 /**
  72  * alloc_entry(): allocate a new QDictEntry
  73  */
  74 static QDictEntry *alloc_entry(const char *key, QObject *value)
  75 {
  76     QDictEntry *entry;
  77
  78     entry = g_malloc0(sizeof(*entry));
  79     entry->key = g_strdup(key);
  80     entry->value = value;
  81
  82     return entry;
  83 }
  84
  85 /**
  86  * qdict_entry_value(): Return qdict entry value
  87  *
  88  * Return weak reference.
  89  */
  90 QObject *qdict_entry_value(const QDictEntry *entry)
  91 {
  92     return entry->value;
  93 }
  94
  95 /**
  96  * qdict_entry_key(): Return qdict entry key
  97  *
  98  * Return a *pointer* to the string, it has to be duplicated before being
  99  * stored.
 100  */
 101 const char *qdict_entry_key(const QDictEntry *entry)
 102 {
 103     return entry->key;
 104 }
 105
 106 /**
 107  * qdict_find(): List lookup function
 108  */
 109 static QDictEntry *qdict_find(const QDict *qdict,
 110                               const char *key, unsigned int bucket)
 111 {
 112     QDictEntry *entry;
 113
 114     QLIST_FOREACH(entry, &qdict->table[bucket], next)
 115         if (!strcmp(entry->key, key))
 116             return entry;
 117
 118     return NULL;
 119 }
 120
 121 /**
 122  * qdict_put_obj(): Put a new QObject into the dictionary
 123  *
 124  * Insert the pair 'key:value' into 'qdict', if 'key' already exists
 125  * its 'value' will be replaced.
 126  *
 127  * This is done by freeing the reference to the stored QObject and
 128  * storing the new one in the same entry.
 129  *
 130  * NOTE: ownership of 'value' is transferred to the QDict
 131  */
 132 void qdict_put_obj(QDict *qdict, const char *key, QObject *value)
 133 {
 134     unsigned int bucket;
 135     QDictEntry *entry;
 136
 137     bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
 138     entry = qdict_find(qdict, key, bucket);
 139     if (entry) {
 140         /* replace key's value */
 141         qobject_decref(entry->value);
 142         entry->value = value;
 143     } else {
 144         /* allocate a new entry */
 145         entry = alloc_entry(key, value);
 146         QLIST_INSERT_HEAD(&qdict->table[bucket], entry, next);
 147         qdict->size++;
 148     }
 149 }
 150
 151 /**
 152  * qdict_get(): Lookup for a given 'key'
 153  *
 154  * Return a weak reference to the QObject associated with 'key' if
 155  * 'key' is present in the dictionary, NULL otherwise.
 156  */
 157 QObject *qdict_get(const QDict *qdict, const char *key)
 158 {
 159     QDictEntry *entry;
 160
 161     entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
 162     return (entry == NULL ? NULL : entry->value);
 163 }
 164
 165 /**
 166  * qdict_haskey(): Check if 'key' exists
 167  *
 168  * Return 1 if 'key' exists in the dict, 0 otherwise
 169  */
 170 int qdict_haskey(const QDict *qdict, const char *key)
 171 {
 172     unsigned int bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
 173     return (qdict_find(qdict, key, bucket) == NULL ? 0 : 1);
 174 }
 175
 176 /**
 177  * qdict_size(): Return the size of the dictionary
 178  */
 179 size_t qdict_size(const QDict *qdict)
 180 {
 181     return qdict->size;
 182 }
 183
 184 /**
 185  * qdict_get_obj(): Get a QObject of a specific type
 186  */
 187 static QObject *qdict_get_obj(const QDict *qdict, const char *key,
 188                               qtype_code type)
 189 {
 190     QObject *obj;
 191
 192     obj = qdict_get(qdict, key);
 193     assert(obj != NULL);
 194     assert(qobject_type(obj) == type);
 195
 196     return obj;
 197 }
 198
 199 /**
 200  * qdict_get_double(): Get an number mapped by 'key'
 201  *
 202  * This function assumes that 'key' exists and it stores a
 203  * QFloat or QInt object.
 204  *
 205  * Return number mapped by 'key'.
 206  */
 207 double qdict_get_double(const QDict *qdict, const char *key)
 208 {
 209     QObject *obj = qdict_get(qdict, key);
 210
 211     assert(obj);
 212     switch (qobject_type(obj)) {
 213     case QTYPE_QFLOAT:
 214         return qfloat_get_double(qobject_to_qfloat(obj));
 215     case QTYPE_QINT:
 216         return qint_get_int(qobject_to_qint(obj));
 217     default:
 218         abort();
 219     }
 220 }
 221
 222 /**
 223  * qdict_get_int(): Get an integer mapped by 'key'
 224  *
 225  * This function assumes that 'key' exists and it stores a
 226  * QInt object.
 227  *
 228  * Return integer mapped by 'key'.
 229  */
 230 int64_t qdict_get_int(const QDict *qdict, const char *key)
 231 {
 232     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT);
 233     return qint_get_int(qobject_to_qint(obj));
 234 }
 235
 236 /**
 237  * qdict_get_bool(): Get a bool mapped by 'key'
 238  *
 239  * This function assumes that 'key' exists and it stores a
 240  * QBool object.
 241  *
 242  * Return bool mapped by 'key'.
 243  */
 244 int qdict_get_bool(const QDict *qdict, const char *key)
 245 {
 246     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QBOOL);
 247     return qbool_get_int(qobject_to_qbool(obj));
 248 }
 249
 250 /**
 251  * qdict_get_qlist(): Get the QList mapped by 'key'
 252  *
 253  * This function assumes that 'key' exists and it stores a
 254  * QList object.
 255  *
 256  * Return QList mapped by 'key'.
 257  */
 258 QList *qdict_get_qlist(const QDict *qdict, const char *key)
 259 {
 260     return qobject_to_qlist(qdict_get_obj(qdict, key, QTYPE_QLIST));
 261 }
 262
 263 /**
 264  * qdict_get_qdict(): Get the QDict mapped by 'key'
 265  *
 266  * This function assumes that 'key' exists and it stores a
 267  * QDict object.
 268  *
 269  * Return QDict mapped by 'key'.
 270  */
 271 QDict *qdict_get_qdict(const QDict *qdict, const char *key)
 272 {
 273     return qobject_to_qdict(qdict_get_obj(qdict, key, QTYPE_QDICT));
 274 }
 275
 276 /**
 277  * qdict_get_str(): Get a pointer to the stored string mapped
 278  * by 'key'
 279  *
 280  * This function assumes that 'key' exists and it stores a
 281  * QString object.
 282  *
 283  * Return pointer to the string mapped by 'key'.
 284  */
 285 const char *qdict_get_str(const QDict *qdict, const char *key)
 286 {
 287     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QSTRING);
 288     return qstring_get_str(qobject_to_qstring(obj));
 289 }
 290
 291 /**
 292  * qdict_get_try_int(): Try to get integer mapped by 'key'
 293  *
 294  * Return integer mapped by 'key', if it is not present in
 295  * the dictionary or if the stored object is not of QInt type
 296  * 'def_value' will be returned.
 297  */
 298 int64_t qdict_get_try_int(const QDict *qdict, const char *key,
 299                           int64_t def_value)
 300 {
 301     QObject *obj;
 302
 303     obj = qdict_get(qdict, key);
 304     if (!obj || qobject_type(obj) != QTYPE_QINT)
 305         return def_value;
 306
 307     return qint_get_int(qobject_to_qint(obj));
 308 }
 309
 310 /**
 311  * qdict_get_try_bool(): Try to get a bool mapped by 'key'
 312  *
 313  * Return bool mapped by 'key', if it is not present in the
 314  * dictionary or if the stored object is not of QBool type
 315  * 'def_value' will be returned.
 316  */
 317 int qdict_get_try_bool(const QDict *qdict, const char *key, int def_value)
 318 {
 319     QObject *obj;
 320
 321     obj = qdict_get(qdict, key);
 322     if (!obj || qobject_type(obj) != QTYPE_QBOOL)
 323         return def_value;
 324
 325     return qbool_get_int(qobject_to_qbool(obj));
 326 }
 327
 328 /**
 329  * qdict_get_try_str(): Try to get a pointer to the stored string
 330  * mapped by 'key'
 331  *
 332  * Return a pointer to the string mapped by 'key', if it is not present
 333  * in the dictionary or if the stored object is not of QString type
 334  * NULL will be returned.
 335  */
 336 const char *qdict_get_try_str(const QDict *qdict, const char *key)
 337 {
 338     QObject *obj;
 339
 340     obj = qdict_get(qdict, key);
 341     if (!obj || qobject_type(obj) != QTYPE_QSTRING)
 342         return NULL;
 343
 344     return qstring_get_str(qobject_to_qstring(obj));
 345 }
 346
 347 /**
 348  * qdict_iter(): Iterate over all the dictionary's stored values.
 349  *
 350  * This function allows the user to provide an iterator, which will be
 351  * called for each stored value in the dictionary.
 352  */
 353 void qdict_iter(const QDict *qdict,
 354                 void (*iter)(const char *key, QObject *obj, void *opaque),
 355                 void *opaque)
 356 {
 357     int i;
 358     QDictEntry *entry;
 359
 360     for (i = 0; i < QDICT_BUCKET_MAX; i++) {
 361         QLIST_FOREACH(entry, &qdict->table[i], next)
 362             iter(entry->key, entry->value, opaque);
 363     }
 364 }
 365
 366 static QDictEntry *qdict_next_entry(const QDict *qdict, int first_bucket)
 367 {
 368     int i;
 369
 370     for (i = first_bucket; i < QDICT_BUCKET_MAX; i++) {
 371         if (!QLIST_EMPTY(&qdict->table[i])) {
 372             return QLIST_FIRST(&qdict->table[i]);
 373         }
 374     }
 375
 376     return NULL;
 377 }
 378
 379 /**
 380  * qdict_first(): Return first qdict entry for iteration.
 381  */
 382 const QDictEntry *qdict_first(const QDict *qdict)
 383 {
 384     return qdict_next_entry(qdict, 0);
 385 }
 386
 387 /**
 388  * qdict_next(): Return next qdict entry in an iteration.
 389  */
 390 const QDictEntry *qdict_next(const QDict *qdict, const QDictEntry *entry)
 391 {
 392     QDictEntry *ret;
 393
 394     ret = QLIST_NEXT(entry, next);
 395     if (!ret) {
 396         unsigned int bucket = tdb_hash(entry->key) % QDICT_BUCKET_MAX;
 397         ret = qdict_next_entry(qdict, bucket + 1);
 398     }
 399
 400     return ret;
 401 }
 402
 403 /**
 404  * qdict_clone_shallow(): Clones a given QDict. Its entries are not copied, but
 405  * another reference is added.
 406  */
 407 QDict *qdict_clone_shallow(const QDict *src)
 408 {
 409     QDict *dest;
 410     QDictEntry *entry;
 411     int i;
 412
 413     dest = qdict_new();
 414
 415     for (i = 0; i < QDICT_BUCKET_MAX; i++) {
 416         QLIST_FOREACH(entry, &src->table[i], next) {
 417             qobject_incref(entry->value);
 418             qdict_put_obj(dest, entry->key, entry->value);
 419         }
 420     }
 421
 422     return dest;
 423 }
 424
 425 /**
 426  * qentry_destroy(): Free all the memory allocated by a QDictEntry
 427  */
 428 static void qentry_destroy(QDictEntry *e)
 429 {
 430     assert(e != NULL);
 431     assert(e->key != NULL);
 432     assert(e->value != NULL);
 433
 434     qobject_decref(e->value);
 435     g_free(e->key);
 436     g_free(e);
 437 }
 438
 439 /**
 440  * qdict_del(): Delete a 'key:value' pair from the dictionary
 441  *
 442  * This will destroy all data allocated by this entry.
 443  */
 444 void qdict_del(QDict *qdict, const char *key)
 445 {
 446     QDictEntry *entry;
 447
 448     entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
 449     if (entry) {
 450         QLIST_REMOVE(entry, next);
 451         qentry_destroy(entry);
 452         qdict->size--;
 453     }
 454 }
 455
 456 /**
 457  * qdict_destroy_obj(): Free all the memory allocated by a QDict
 458  */
 459 static void qdict_destroy_obj(QObject *obj)
 460 {
 461     int i;
 462     QDict *qdict;
 463
 464     assert(obj != NULL);
 465     qdict = qobject_to_qdict(obj);
 466
 467     for (i = 0; i < QDICT_BUCKET_MAX; i++) {
 468         QDictEntry *entry = QLIST_FIRST(&qdict->table[i]);
 469         while (entry) {
 470             QDictEntry *tmp = QLIST_NEXT(entry, next);
 471             QLIST_REMOVE(entry, next);
 472             qentry_destroy(entry);
 473             entry = tmp;
 474         }
 475     }
 476
 477     g_free(qdict);
 478 }
 479
 480 static void qdict_flatten_qdict(QDict *qdict, QDict *target,
 481                                 const char *prefix);
 482
 483 static void qdict_flatten_qlist(QList *qlist, QDict *target, const char *prefix)
 484 {
 485     QObject *value;
 486     const QListEntry *entry;
 487     char *new_key;
 488     int i;
 489
 490     /* This function is never called with prefix == NULL, i.e., it is always
 491      * called from within qdict_flatten_q(list|dict)(). Therefore, it does not
 492      * need to remove list entries during the iteration (the whole list will be
 493      * deleted eventually anyway from qdict_flatten_qdict()). */
 494     assert(prefix);
 495
 496     entry = qlist_first(qlist);
 497
 498     for (i = 0; entry; entry = qlist_next(entry), i++) {
 499         value = qlist_entry_obj(entry);
 500         new_key = g_strdup_printf("%s.%i", prefix, i);
 501
 502         if (qobject_type(value) == QTYPE_QDICT) {
 503             qdict_flatten_qdict(qobject_to_qdict(value), target, new_key);
 504         } else if (qobject_type(value) == QTYPE_QLIST) {
 505             qdict_flatten_qlist(qobject_to_qlist(value), target, new_key);
 506         } else {
 507             /* All other types are moved to the target unchanged. */
 508             qobject_incref(value);
 509             qdict_put_obj(target, new_key, value);
 510         }
 511
 512         g_free(new_key);
 513     }
 514 }
 515
 516 static void qdict_flatten_qdict(QDict *qdict, QDict *target, const char *prefix)
 517 {
 518     QObject *value;
 519     const QDictEntry *entry, *next;
 520     char *new_key;
 521     bool delete;
 522
 523     entry = qdict_first(qdict);
 524
 525     while (entry != NULL) {
 526
 527         next = qdict_next(qdict, entry);
 528         value = qdict_entry_value(entry);
 529         new_key = NULL;
 530         delete = false;
 531
 532         if (prefix) {
 533             new_key = g_strdup_printf("%s.%s", prefix, entry->key);
 534         }
 535
 536         if (qobject_type(value) == QTYPE_QDICT) {
 537             /* Entries of QDicts are processed recursively, the QDict object
 538              * itself disappears. */
 539             qdict_flatten_qdict(qobject_to_qdict(value), target,
 540                                 new_key ? new_key : entry->key);
 541             delete = true;
 542         } else if (qobject_type(value) == QTYPE_QLIST) {
 543             qdict_flatten_qlist(qobject_to_qlist(value), target,
 544                                 new_key ? new_key : entry->key);
 545             delete = true;
 546         } else if (prefix) {
 547             /* All other objects are moved to the target unchanged. */
 548             qobject_incref(value);
 549             qdict_put_obj(target, new_key, value);
 550             delete = true;
 551         }
 552
 553         g_free(new_key);
 554
 555         if (delete) {
 556             qdict_del(qdict, entry->key);
 557
 558             /* Restart loop after modifying the iterated QDict */
 559             entry = qdict_first(qdict);
 560             continue;
 561         }
 562
 563         entry = next;
 564     }
 565 }
 566
 567 /**
 568  * qdict_flatten(): For each nested QDict with key x, all fields with key y
 569  * are moved to this QDict and their key is renamed to "x.y". For each nested
 570  * QList with key x, the field at index y is moved to this QDict with the key
 571  * "x.y" (i.e., the reverse of what qdict_array_split() does).
 572  * This operation is applied recursively for nested QDicts and QLists.
 573  */
 574 void qdict_flatten(QDict *qdict)
 575 {
 576     qdict_flatten_qdict(qdict, qdict, NULL);
 577 }
 578
 579 /* extract all the src QDict entries starting by start into dst */
 580 void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start)
 581
 582 {
 583     const QDictEntry *entry, *next;
 584     const char *p;
 585
 586     *dst = qdict_new();
 587     entry = qdict_first(src);
 588
 589     while (entry != NULL) {
 590         next = qdict_next(src, entry);
 591         if (strstart(entry->key, start, &p)) {
 592             qobject_incref(entry->value);
 593             qdict_put_obj(*dst, p, entry->value);
 594             qdict_del(src, entry->key);
 595         }
 596         entry = next;
 597     }
 598 }
 599
 600 static bool qdict_has_prefixed_entries(const QDict *src, const char *start)
 601 {
 602     const QDictEntry *entry;
 603
 604     for (entry = qdict_first(src); entry; entry = qdict_next(src, entry)) {
 605         if (strstart(entry->key, start, NULL)) {
 606             return true;
 607         }
 608     }
 609
 610     return false;
 611 }
 612
 613 /**
 614  * qdict_array_split(): This function moves array-like elements of a QDict into
 615  * a new QList. Every entry in the original QDict with a key "%u" or one
 616  * prefixed "%u.", where %u designates an unsigned integer starting at 0 and
 617  * incrementally counting up, will be moved to a new QDict at index %u in the
 618  * output QList with the key prefix removed, if that prefix is "%u.". If the
 619  * whole key is just "%u", the whole QObject will be moved unchanged without
 620  * creating a new QDict. The function terminates when there is no entry in the
 621  * QDict with a prefix directly (incrementally) following the last one; it also
 622  * returns if there are both entries with "%u" and "%u." for the same index %u.
 623  * Example: {"0.a": 42, "0.b": 23, "1.x": 0, "4.y": 1, "o.o": 7, "2": 66}
 624  *      (or {"1.x": 0, "4.y": 1, "0.a": 42, "o.o": 7, "0.b": 23, "2": 66})
 625  *       => [{"a": 42, "b": 23}, {"x": 0}, 66]
 626  *      and {"4.y": 1, "o.o": 7} (remainder of the old QDict)
 627  */
 628 void qdict_array_split(QDict *src, QList **dst)
 629 {
 630     unsigned i;
 631
 632     *dst = qlist_new();
 633
 634     for (i = 0; i < UINT_MAX; i++) {
 635         QObject *subqobj;
 636         bool is_subqdict;
 637         QDict *subqdict;
 638         char indexstr[32], prefix[32];
 639         size_t snprintf_ret;
 640
 641         snprintf_ret = snprintf(indexstr, 32, "%u", i);
 642         assert(snprintf_ret < 32);
 643
 644         subqobj = qdict_get(src, indexstr);
 645
 646         snprintf_ret = snprintf(prefix, 32, "%u.", i);
 647         assert(snprintf_ret < 32);
 648
 649         is_subqdict = qdict_has_prefixed_entries(src, prefix);
 650
 651         // There may be either a single subordinate object (named "%u") or
 652         // multiple objects (each with a key prefixed "%u."), but not both.
 653         if (!subqobj == !is_subqdict) {
 654             break;
 655         }
 656
 657         if (is_subqdict) {
 658             qdict_extract_subqdict(src, &subqdict, prefix);
 659             assert(qdict_size(subqdict) > 0);
 660         } else {
 661             qobject_incref(subqobj);
 662             qdict_del(src, indexstr);
 663         }
 664
 665         qlist_append_obj(*dst, subqobj ?: QOBJECT(subqdict));
 666     }
 667 }
 668
 669 /**
 670  * qdict_join(): Absorb the src QDict into the dest QDict, that is, move all
 671  * elements from src to dest.
 672  *
 673  * If an element from src has a key already present in dest, it will not be
 674  * moved unless overwrite is true.
 675  *
 676  * If overwrite is true, the conflicting values in dest will be discarded and
 677  * replaced by the corresponding values from src.
 678  *
 679  * Therefore, with overwrite being true, the src QDict will always be empty when
 680  * this function returns. If overwrite is false, the src QDict will be empty
 681  * iff there were no conflicts.
 682  */
 683 void qdict_join(QDict *dest, QDict *src, bool overwrite)
 684 {
 685     const QDictEntry *entry, *next;
 686
 687     entry = qdict_first(src);
 688     while (entry) {
 689         next = qdict_next(src, entry);
 690
 691         if (overwrite || !qdict_haskey(dest, entry->key)) {
 692             qobject_incref(entry->value);
 693             qdict_put_obj(dest, entry->key, entry->value);
 694             qdict_del(src, entry->key);
 695         }
 696
 697         entry = next;
 698     }
 699 }