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