1
2
3
4
5
6
7
8
9
10
11
12
13#include "qemu/osdep.h"
14#include "qapi/qmp/qint.h"
15#include "qapi/qmp/qfloat.h"
16#include "qapi/qmp/qdict.h"
17#include "qapi/qmp/qbool.h"
18#include "qapi/qmp/qstring.h"
19#include "qapi/qmp/qobject.h"
20#include "qapi/error.h"
21#include "qemu/queue.h"
22#include "qemu-common.h"
23#include "qemu/cutils.h"
24
25
26
27
28
29
30QDict *qdict_new(void)
31{
32 QDict *qdict;
33
34 qdict = g_malloc0(sizeof(*qdict));
35 qobject_init(QOBJECT(qdict), QTYPE_QDICT);
36
37 return qdict;
38}
39
40
41
42
43QDict *qobject_to_qdict(const QObject *obj)
44{
45 if (!obj || qobject_type(obj) != QTYPE_QDICT) {
46 return NULL;
47 }
48 return container_of(obj, QDict, base);
49}
50
51
52
53
54
55static unsigned int tdb_hash(const char *name)
56{
57 unsigned value;
58 unsigned i;
59
60
61 for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
62 value = (value + (((const unsigned char *)name)[i] << (i*5 % 24)));
63
64 return (1103515243 * value + 12345);
65}
66
67
68
69
70static QDictEntry *alloc_entry(const char *key, QObject *value)
71{
72 QDictEntry *entry;
73
74 entry = g_malloc0(sizeof(*entry));
75 entry->key = g_strdup(key);
76 entry->value = value;
77
78 return entry;
79}
80
81
82
83
84
85
86QObject *qdict_entry_value(const QDictEntry *entry)
87{
88 return entry->value;
89}
90
91
92
93
94
95
96
97const char *qdict_entry_key(const QDictEntry *entry)
98{
99 return entry->key;
100}
101
102
103
104
105static QDictEntry *qdict_find(const QDict *qdict,
106 const char *key, unsigned int bucket)
107{
108 QDictEntry *entry;
109
110 QLIST_FOREACH(entry, &qdict->table[bucket], next)
111 if (!strcmp(entry->key, key))
112 return entry;
113
114 return NULL;
115}
116
117
118
119
120
121
122
123
124
125
126
127
128void qdict_put_obj(QDict *qdict, const char *key, QObject *value)
129{
130 unsigned int bucket;
131 QDictEntry *entry;
132
133 bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
134 entry = qdict_find(qdict, key, bucket);
135 if (entry) {
136
137 qobject_decref(entry->value);
138 entry->value = value;
139 } else {
140
141 entry = alloc_entry(key, value);
142 QLIST_INSERT_HEAD(&qdict->table[bucket], entry, next);
143 qdict->size++;
144 }
145}
146
147
148
149
150
151
152
153QObject *qdict_get(const QDict *qdict, const char *key)
154{
155 QDictEntry *entry;
156
157 entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
158 return (entry == NULL ? NULL : entry->value);
159}
160
161
162
163
164
165
166int qdict_haskey(const QDict *qdict, const char *key)
167{
168 unsigned int bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
169 return (qdict_find(qdict, key, bucket) == NULL ? 0 : 1);
170}
171
172
173
174
175size_t qdict_size(const QDict *qdict)
176{
177 return qdict->size;
178}
179
180
181
182
183static QObject *qdict_get_obj(const QDict *qdict, const char *key, QType type)
184{
185 QObject *obj;
186
187 obj = qdict_get(qdict, key);
188 assert(obj != NULL);
189 assert(qobject_type(obj) == type);
190
191 return obj;
192}
193
194
195
196
197
198
199
200
201
202double qdict_get_double(const QDict *qdict, const char *key)
203{
204 QObject *obj = qdict_get(qdict, key);
205
206 assert(obj);
207 switch (qobject_type(obj)) {
208 case QTYPE_QFLOAT:
209 return qfloat_get_double(qobject_to_qfloat(obj));
210 case QTYPE_QINT:
211 return qint_get_int(qobject_to_qint(obj));
212 default:
213 abort();
214 }
215}
216
217
218
219
220
221
222
223
224
225int64_t qdict_get_int(const QDict *qdict, const char *key)
226{
227 return qint_get_int(qobject_to_qint(qdict_get(qdict, key)));
228}
229
230
231
232
233
234
235
236
237
238bool qdict_get_bool(const QDict *qdict, const char *key)
239{
240 return qbool_get_bool(qobject_to_qbool(qdict_get(qdict, key)));
241}
242
243
244
245
246
247
248
249
250
251QList *qdict_get_qlist(const QDict *qdict, const char *key)
252{
253 return qobject_to_qlist(qdict_get_obj(qdict, key, QTYPE_QLIST));
254}
255
256
257
258
259
260
261
262
263
264QDict *qdict_get_qdict(const QDict *qdict, const char *key)
265{
266 return qobject_to_qdict(qdict_get(qdict, key));
267}
268
269
270
271
272
273
274
275
276
277
278const char *qdict_get_str(const QDict *qdict, const char *key)
279{
280 return qstring_get_str(qobject_to_qstring(qdict_get(qdict, key)));
281}
282
283
284
285
286
287
288
289
290int64_t qdict_get_try_int(const QDict *qdict, const char *key,
291 int64_t def_value)
292{
293 QInt *qint = qobject_to_qint(qdict_get(qdict, key));
294
295 return qint ? qint_get_int(qint) : def_value;
296}
297
298
299
300
301
302
303
304
305bool qdict_get_try_bool(const QDict *qdict, const char *key, bool def_value)
306{
307 QBool *qbool = qobject_to_qbool(qdict_get(qdict, key));
308
309 return qbool ? qbool_get_bool(qbool) : def_value;
310}
311
312
313
314
315
316
317
318
319
320const char *qdict_get_try_str(const QDict *qdict, const char *key)
321{
322 QString *qstr = qobject_to_qstring(qdict_get(qdict, key));
323
324 return qstr ? qstring_get_str(qstr) : NULL;
325}
326
327
328
329
330
331
332
333void qdict_iter(const QDict *qdict,
334 void (*iter)(const char *key, QObject *obj, void *opaque),
335 void *opaque)
336{
337 int i;
338 QDictEntry *entry;
339
340 for (i = 0; i < QDICT_BUCKET_MAX; i++) {
341 QLIST_FOREACH(entry, &qdict->table[i], next)
342 iter(entry->key, entry->value, opaque);
343 }
344}
345
346static QDictEntry *qdict_next_entry(const QDict *qdict, int first_bucket)
347{
348 int i;
349
350 for (i = first_bucket; i < QDICT_BUCKET_MAX; i++) {
351 if (!QLIST_EMPTY(&qdict->table[i])) {
352 return QLIST_FIRST(&qdict->table[i]);
353 }
354 }
355
356 return NULL;
357}
358
359
360
361
362const QDictEntry *qdict_first(const QDict *qdict)
363{
364 return qdict_next_entry(qdict, 0);
365}
366
367
368
369
370const QDictEntry *qdict_next(const QDict *qdict, const QDictEntry *entry)
371{
372 QDictEntry *ret;
373
374 ret = QLIST_NEXT(entry, next);
375 if (!ret) {
376 unsigned int bucket = tdb_hash(entry->key) % QDICT_BUCKET_MAX;
377 ret = qdict_next_entry(qdict, bucket + 1);
378 }
379
380 return ret;
381}
382
383
384
385
386
387QDict *qdict_clone_shallow(const QDict *src)
388{
389 QDict *dest;
390 QDictEntry *entry;
391 int i;
392
393 dest = qdict_new();
394
395 for (i = 0; i < QDICT_BUCKET_MAX; i++) {
396 QLIST_FOREACH(entry, &src->table[i], next) {
397 qobject_incref(entry->value);
398 qdict_put_obj(dest, entry->key, entry->value);
399 }
400 }
401
402 return dest;
403}
404
405
406
407
408static void qentry_destroy(QDictEntry *e)
409{
410 assert(e != NULL);
411 assert(e->key != NULL);
412 assert(e->value != NULL);
413
414 qobject_decref(e->value);
415 g_free(e->key);
416 g_free(e);
417}
418
419
420
421
422
423
424void qdict_del(QDict *qdict, const char *key)
425{
426 QDictEntry *entry;
427
428 entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
429 if (entry) {
430 QLIST_REMOVE(entry, next);
431 qentry_destroy(entry);
432 qdict->size--;
433 }
434}
435
436
437
438
439void qdict_destroy_obj(QObject *obj)
440{
441 int i;
442 QDict *qdict;
443
444 assert(obj != NULL);
445 qdict = qobject_to_qdict(obj);
446
447 for (i = 0; i < QDICT_BUCKET_MAX; i++) {
448 QDictEntry *entry = QLIST_FIRST(&qdict->table[i]);
449 while (entry) {
450 QDictEntry *tmp = QLIST_NEXT(entry, next);
451 QLIST_REMOVE(entry, next);
452 qentry_destroy(entry);
453 entry = tmp;
454 }
455 }
456
457 g_free(qdict);
458}
459
460
461
462
463
464
465void qdict_copy_default(QDict *dst, QDict *src, const char *key)
466{
467 QObject *val;
468
469 if (qdict_haskey(dst, key)) {
470 return;
471 }
472
473 val = qdict_get(src, key);
474 if (val) {
475 qobject_incref(val);
476 qdict_put_obj(dst, key, val);
477 }
478}
479
480
481
482
483
484void qdict_set_default_str(QDict *dst, const char *key, const char *val)
485{
486 if (qdict_haskey(dst, key)) {
487 return;
488 }
489
490 qdict_put(dst, key, qstring_from_str(val));
491}
492
493static void qdict_flatten_qdict(QDict *qdict, QDict *target,
494 const char *prefix);
495
496static void qdict_flatten_qlist(QList *qlist, QDict *target, const char *prefix)
497{
498 QObject *value;
499 const QListEntry *entry;
500 char *new_key;
501 int i;
502
503
504
505
506
507 assert(prefix);
508
509 entry = qlist_first(qlist);
510
511 for (i = 0; entry; entry = qlist_next(entry), i++) {
512 value = qlist_entry_obj(entry);
513 new_key = g_strdup_printf("%s.%i", prefix, i);
514
515 if (qobject_type(value) == QTYPE_QDICT) {
516 qdict_flatten_qdict(qobject_to_qdict(value), target, new_key);
517 } else if (qobject_type(value) == QTYPE_QLIST) {
518 qdict_flatten_qlist(qobject_to_qlist(value), target, new_key);
519 } else {
520
521 qobject_incref(value);
522 qdict_put_obj(target, new_key, value);
523 }
524
525 g_free(new_key);
526 }
527}
528
529static void qdict_flatten_qdict(QDict *qdict, QDict *target, const char *prefix)
530{
531 QObject *value;
532 const QDictEntry *entry, *next;
533 char *new_key;
534 bool delete;
535
536 entry = qdict_first(qdict);
537
538 while (entry != NULL) {
539
540 next = qdict_next(qdict, entry);
541 value = qdict_entry_value(entry);
542 new_key = NULL;
543 delete = false;
544
545 if (prefix) {
546 new_key = g_strdup_printf("%s.%s", prefix, entry->key);
547 }
548
549 if (qobject_type(value) == QTYPE_QDICT) {
550
551
552 qdict_flatten_qdict(qobject_to_qdict(value), target,
553 new_key ? new_key : entry->key);
554 delete = true;
555 } else if (qobject_type(value) == QTYPE_QLIST) {
556 qdict_flatten_qlist(qobject_to_qlist(value), target,
557 new_key ? new_key : entry->key);
558 delete = true;
559 } else if (prefix) {
560
561 qobject_incref(value);
562 qdict_put_obj(target, new_key, value);
563 delete = true;
564 }
565
566 g_free(new_key);
567
568 if (delete) {
569 qdict_del(qdict, entry->key);
570
571
572 entry = qdict_first(qdict);
573 continue;
574 }
575
576 entry = next;
577 }
578}
579
580
581
582
583
584
585
586
587void qdict_flatten(QDict *qdict)
588{
589 qdict_flatten_qdict(qdict, qdict, NULL);
590}
591
592
593void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start)
594
595{
596 const QDictEntry *entry, *next;
597 const char *p;
598
599 *dst = qdict_new();
600 entry = qdict_first(src);
601
602 while (entry != NULL) {
603 next = qdict_next(src, entry);
604 if (strstart(entry->key, start, &p)) {
605 qobject_incref(entry->value);
606 qdict_put_obj(*dst, p, entry->value);
607 qdict_del(src, entry->key);
608 }
609 entry = next;
610 }
611}
612
613static int qdict_count_prefixed_entries(const QDict *src, const char *start)
614{
615 const QDictEntry *entry;
616 int count = 0;
617
618 for (entry = qdict_first(src); entry; entry = qdict_next(src, entry)) {
619 if (strstart(entry->key, start, NULL)) {
620 if (count == INT_MAX) {
621 return -ERANGE;
622 }
623 count++;
624 }
625 }
626
627 return count;
628}
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645void qdict_array_split(QDict *src, QList **dst)
646{
647 unsigned i;
648
649 *dst = qlist_new();
650
651 for (i = 0; i < UINT_MAX; i++) {
652 QObject *subqobj;
653 bool is_subqdict;
654 QDict *subqdict;
655 char indexstr[32], prefix[32];
656 size_t snprintf_ret;
657
658 snprintf_ret = snprintf(indexstr, 32, "%u", i);
659 assert(snprintf_ret < 32);
660
661 subqobj = qdict_get(src, indexstr);
662
663 snprintf_ret = snprintf(prefix, 32, "%u.", i);
664 assert(snprintf_ret < 32);
665
666
667 is_subqdict = qdict_count_prefixed_entries(src, prefix);
668
669
670
671 if (!subqobj == !is_subqdict) {
672 break;
673 }
674
675 if (is_subqdict) {
676 qdict_extract_subqdict(src, &subqdict, prefix);
677 assert(qdict_size(subqdict) > 0);
678 } else {
679 qobject_incref(subqobj);
680 qdict_del(src, indexstr);
681 }
682
683 qlist_append_obj(*dst, subqobj ?: QOBJECT(subqdict));
684 }
685}
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709static void qdict_split_flat_key(const char *key, char **prefix,
710 const char **suffix)
711{
712 const char *separator;
713 size_t i, j;
714
715
716
717 separator = NULL;
718 do {
719 if (separator) {
720 separator += 2;
721 } else {
722 separator = key;
723 }
724 separator = strchr(separator, '.');
725 } while (separator && separator[1] == '.');
726
727 if (separator) {
728 *prefix = g_strndup(key, separator - key);
729 *suffix = separator + 1;
730 } else {
731 *prefix = g_strdup(key);
732 *suffix = NULL;
733 }
734
735
736 for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) {
737 if ((*prefix)[i] == '.') {
738 assert((*prefix)[i + 1] == '.');
739 i++;
740 }
741 (*prefix)[j] = (*prefix)[i];
742 }
743 (*prefix)[j] = '\0';
744}
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759static int qdict_is_list(QDict *maybe_list, Error **errp)
760{
761 const QDictEntry *ent;
762 ssize_t len = 0;
763 ssize_t max = -1;
764 int is_list = -1;
765 int64_t val;
766
767 for (ent = qdict_first(maybe_list); ent != NULL;
768 ent = qdict_next(maybe_list, ent)) {
769
770 if (qemu_strtoll(ent->key, NULL, 10, &val) == 0) {
771 if (is_list == -1) {
772 is_list = 1;
773 } else if (!is_list) {
774 error_setg(errp,
775 "Cannot mix list and non-list keys");
776 return -1;
777 }
778 len++;
779 if (val > max) {
780 max = val;
781 }
782 } else {
783 if (is_list == -1) {
784 is_list = 0;
785 } else if (is_list) {
786 error_setg(errp,
787 "Cannot mix list and non-list keys");
788 return -1;
789 }
790 }
791 }
792
793 if (is_list == -1) {
794 assert(!qdict_size(maybe_list));
795 is_list = 0;
796 }
797
798
799
800
801
802
803 if (len != (max + 1)) {
804 error_setg(errp, "List indices are not contiguous, "
805 "saw %zd elements but %zd largest index",
806 len, max);
807 return -1;
808 }
809
810 return is_list;
811}
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852QObject *qdict_crumple(const QDict *src, Error **errp)
853{
854 const QDictEntry *ent;
855 QDict *two_level, *multi_level = NULL;
856 QObject *dst = NULL, *child;
857 size_t i;
858 char *prefix = NULL;
859 const char *suffix = NULL;
860 int is_list;
861
862 two_level = qdict_new();
863
864
865 for (ent = qdict_first(src); ent != NULL; ent = qdict_next(src, ent)) {
866 if (qobject_type(ent->value) == QTYPE_QDICT ||
867 qobject_type(ent->value) == QTYPE_QLIST) {
868 error_setg(errp, "Value %s is not a scalar",
869 ent->key);
870 goto error;
871 }
872
873 qdict_split_flat_key(ent->key, &prefix, &suffix);
874
875 child = qdict_get(two_level, prefix);
876 if (suffix) {
877 if (child) {
878 if (qobject_type(child) != QTYPE_QDICT) {
879 error_setg(errp, "Key %s prefix is already set as a scalar",
880 prefix);
881 goto error;
882 }
883 } else {
884 child = QOBJECT(qdict_new());
885 qdict_put_obj(two_level, prefix, child);
886 }
887 qobject_incref(ent->value);
888 qdict_put_obj(qobject_to_qdict(child), suffix, ent->value);
889 } else {
890 if (child) {
891 error_setg(errp, "Key %s prefix is already set as a dict",
892 prefix);
893 goto error;
894 }
895 qobject_incref(ent->value);
896 qdict_put_obj(two_level, prefix, ent->value);
897 }
898
899 g_free(prefix);
900 prefix = NULL;
901 }
902
903
904
905 multi_level = qdict_new();
906 for (ent = qdict_first(two_level); ent != NULL;
907 ent = qdict_next(two_level, ent)) {
908
909 if (qobject_type(ent->value) == QTYPE_QDICT) {
910 child = qdict_crumple(qobject_to_qdict(ent->value), errp);
911 if (!child) {
912 goto error;
913 }
914
915 qdict_put_obj(multi_level, ent->key, child);
916 } else {
917 qobject_incref(ent->value);
918 qdict_put_obj(multi_level, ent->key, ent->value);
919 }
920 }
921 QDECREF(two_level);
922 two_level = NULL;
923
924
925 is_list = qdict_is_list(multi_level, errp);
926 if (is_list < 0) {
927 goto error;
928 }
929
930 if (is_list) {
931 dst = QOBJECT(qlist_new());
932
933 for (i = 0; i < qdict_size(multi_level); i++) {
934 char *key = g_strdup_printf("%zu", i);
935
936 child = qdict_get(multi_level, key);
937 g_free(key);
938
939 if (!child) {
940 error_setg(errp, "Missing list index %zu", i);
941 goto error;
942 }
943
944 qobject_incref(child);
945 qlist_append_obj(qobject_to_qlist(dst), child);
946 }
947 QDECREF(multi_level);
948 multi_level = NULL;
949 } else {
950 dst = QOBJECT(multi_level);
951 }
952
953 return dst;
954
955 error:
956 g_free(prefix);
957 QDECREF(multi_level);
958 QDECREF(two_level);
959 qobject_decref(dst);
960 return NULL;
961}
962
963
964
965
966
967
968
969
970int qdict_array_entries(QDict *src, const char *subqdict)
971{
972 const QDictEntry *entry;
973 unsigned i;
974 unsigned entries = 0;
975 size_t subqdict_len = strlen(subqdict);
976
977 assert(!subqdict_len || subqdict[subqdict_len - 1] == '.');
978
979
980
981
982 for (i = 0; i < INT_MAX; i++) {
983 QObject *subqobj;
984 int subqdict_entries;
985 char *prefix = g_strdup_printf("%s%u.", subqdict, i);
986
987 subqdict_entries = qdict_count_prefixed_entries(src, prefix);
988
989
990 prefix[strlen(prefix) - 1] = 0;
991 subqobj = qdict_get(src, prefix);
992
993 g_free(prefix);
994
995 if (subqdict_entries < 0) {
996 return subqdict_entries;
997 }
998
999
1000
1001 if (subqobj && subqdict_entries) {
1002 return -EINVAL;
1003 } else if (!subqobj && !subqdict_entries) {
1004 break;
1005 }
1006
1007 entries += subqdict_entries ? subqdict_entries : 1;
1008 }
1009
1010
1011 for (entry = qdict_first(src); entry; entry = qdict_next(src, entry)) {
1012 if (!strstart(qdict_entry_key(entry), subqdict, NULL)) {
1013 entries++;
1014 }
1015 }
1016
1017
1018 if (qdict_size(src) != entries) {
1019 return -EINVAL;
1020 }
1021
1022 return i;
1023}
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039void qdict_join(QDict *dest, QDict *src, bool overwrite)
1040{
1041 const QDictEntry *entry, *next;
1042
1043 entry = qdict_first(src);
1044 while (entry) {
1045 next = qdict_next(src, entry);
1046
1047 if (overwrite || !qdict_haskey(dest, entry->key)) {
1048 qobject_incref(entry->value);
1049 qdict_put_obj(dest, entry->key, entry->value);
1050 qdict_del(src, entry->key);
1051 }
1052
1053 entry = next;
1054 }
1055}
1056