1 /* Copyright (c) 2009, 2010 Nicira Networks
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
18 #include "ovsdb-data.h"
24 #include "ovsdb-error.h"
30 wrap_json(const char *name, struct json *wrapped)
32 return json_array_create_2(json_string_create(name), wrapped);
36 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
42 case OVSDB_TYPE_INTEGER:
50 case OVSDB_TYPE_BOOLEAN:
51 atom->boolean = false;
54 case OVSDB_TYPE_STRING:
55 atom->string = xmemdup("", 1);
59 uuid_zero(&atom->uuid);
69 ovsdb_atom_is_default(const union ovsdb_atom *atom,
70 enum ovsdb_atomic_type type)
76 case OVSDB_TYPE_INTEGER:
77 return atom->integer == 0;
80 return atom->real == 0.0;
82 case OVSDB_TYPE_BOOLEAN:
83 return atom->boolean == false;
85 case OVSDB_TYPE_STRING:
86 return atom->string[0] == '\0';
89 return uuid_is_zero(&atom->uuid);
98 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
99 enum ovsdb_atomic_type type)
102 case OVSDB_TYPE_VOID:
105 case OVSDB_TYPE_INTEGER:
106 new->integer = old->integer;
109 case OVSDB_TYPE_REAL:
110 new->real = old->real;
113 case OVSDB_TYPE_BOOLEAN:
114 new->boolean = old->boolean;
117 case OVSDB_TYPE_STRING:
118 new->string = xstrdup(old->string);
121 case OVSDB_TYPE_UUID:
122 new->uuid = old->uuid;
132 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
134 union ovsdb_atom tmp = *a;
140 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
144 case OVSDB_TYPE_VOID:
147 case OVSDB_TYPE_INTEGER:
148 return hash_int(atom->integer, basis);
150 case OVSDB_TYPE_REAL:
151 return hash_double(atom->real, basis);
153 case OVSDB_TYPE_BOOLEAN:
154 return hash_boolean(atom->boolean, basis);
156 case OVSDB_TYPE_STRING:
157 return hash_string(atom->string, basis);
159 case OVSDB_TYPE_UUID:
160 return hash_int(uuid_hash(&atom->uuid), basis);
169 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
170 const union ovsdb_atom *b,
171 enum ovsdb_atomic_type type)
174 case OVSDB_TYPE_VOID:
177 case OVSDB_TYPE_INTEGER:
178 return a->integer < b->integer ? -1 : a->integer > b->integer;
180 case OVSDB_TYPE_REAL:
181 return a->real < b->real ? -1 : a->real > b->real;
183 case OVSDB_TYPE_BOOLEAN:
184 return a->boolean - b->boolean;
186 case OVSDB_TYPE_STRING:
187 return strcmp(a->string, b->string);
189 case OVSDB_TYPE_UUID:
190 return uuid_compare_3way(&a->uuid, &b->uuid);
198 static struct ovsdb_error *
199 unwrap_json(const struct json *json, const char *name,
200 enum json_type value_type, const struct json **value)
202 if (json->type != JSON_ARRAY
203 || json->u.array.n != 2
204 || json->u.array.elems[0]->type != JSON_STRING
205 || (name && strcmp(json->u.array.elems[0]->u.string, name))
206 || json->u.array.elems[1]->type != value_type)
208 return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
209 json_type_to_string(value_type));
211 *value = json->u.array.elems[1];
215 static struct ovsdb_error *
216 parse_json_pair(const struct json *json,
217 const struct json **elem0, const struct json **elem1)
219 if (json->type != JSON_ARRAY || json->u.array.n != 2) {
220 return ovsdb_syntax_error(json, NULL, "expected 2-element array");
222 *elem0 = json->u.array.elems[0];
223 *elem1 = json->u.array.elems[1];
227 static struct ovsdb_error *
228 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
229 const struct ovsdb_symbol_table *symtab)
232 static struct ovsdb_error *
233 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
234 const struct ovsdb_symbol_table *symtab)
236 struct ovsdb_error *error0;
237 const struct json *value;
239 error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
241 const char *uuid_string = json_string(value);
242 if (!uuid_from_string(uuid, uuid_string)) {
243 return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
247 struct ovsdb_error *error1;
249 error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
251 const char *name = json_string(value);
252 const struct ovsdb_symbol *symbol;
254 ovsdb_error_destroy(error0);
256 symbol = ovsdb_symbol_table_get(symtab, name);
258 *uuid = symbol->uuid;
261 return ovsdb_syntax_error(json, NULL,
262 "unknown named-uuid \"%s\"", name);
265 ovsdb_error_destroy(error1);
272 ovsdb_atom_from_json(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
273 const struct json *json,
274 const struct ovsdb_symbol_table *symtab)
277 case OVSDB_TYPE_VOID:
280 case OVSDB_TYPE_INTEGER:
281 if (json->type == JSON_INTEGER) {
282 atom->integer = json->u.integer;
287 case OVSDB_TYPE_REAL:
288 if (json->type == JSON_INTEGER) {
289 atom->real = json->u.integer;
291 } else if (json->type == JSON_REAL) {
292 atom->real = json->u.real;
297 case OVSDB_TYPE_BOOLEAN:
298 if (json->type == JSON_TRUE) {
299 atom->boolean = true;
301 } else if (json->type == JSON_FALSE) {
302 atom->boolean = false;
307 case OVSDB_TYPE_STRING:
308 if (json->type == JSON_STRING) {
309 atom->string = xstrdup(json->u.string);
314 case OVSDB_TYPE_UUID:
315 return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
322 return ovsdb_syntax_error(json, NULL, "expected %s",
323 ovsdb_atomic_type_to_string(type));
327 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
330 case OVSDB_TYPE_VOID:
333 case OVSDB_TYPE_INTEGER:
334 return json_integer_create(atom->integer);
336 case OVSDB_TYPE_REAL:
337 return json_real_create(atom->real);
339 case OVSDB_TYPE_BOOLEAN:
340 return json_boolean_create(atom->boolean);
342 case OVSDB_TYPE_STRING:
343 return json_string_create(atom->string);
345 case OVSDB_TYPE_UUID:
346 return wrap_json("uuid", json_string_create_nocopy(
347 xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
355 static union ovsdb_atom *
356 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
358 if (type != OVSDB_TYPE_VOID && n) {
359 union ovsdb_atom *atoms;
362 atoms = xmalloc(n * sizeof *atoms);
363 for (i = 0; i < n; i++) {
364 ovsdb_atom_init_default(&atoms[i], type);
368 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
369 * treated as xmalloc(1). */
375 ovsdb_datum_init_empty(struct ovsdb_datum *datum)
379 datum->values = NULL;
383 ovsdb_datum_init_default(struct ovsdb_datum *datum,
384 const struct ovsdb_type *type)
386 datum->n = type->n_min;
387 datum->keys = alloc_default_atoms(type->key_type, datum->n);
388 datum->values = alloc_default_atoms(type->value_type, datum->n);
392 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
393 const struct ovsdb_type *type)
397 if (datum->n != type->n_min) {
400 for (i = 0; i < datum->n; i++) {
401 if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
404 if (type->value_type != OVSDB_TYPE_VOID
405 && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
413 static union ovsdb_atom *
414 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
416 if (type != OVSDB_TYPE_VOID && n) {
417 union ovsdb_atom *new;
420 new = xmalloc(n * sizeof *new);
421 for (i = 0; i < n; i++) {
422 ovsdb_atom_clone(&new[i], &old[i], type);
426 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
427 * treated as xmalloc(1). */
433 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
434 const struct ovsdb_type *type)
436 unsigned int n = old->n;
438 new->keys = clone_atoms(old->keys, type->key_type, n);
439 new->values = clone_atoms(old->values, type->value_type, n);
443 free_data(enum ovsdb_atomic_type type,
444 union ovsdb_atom *atoms, size_t n_atoms)
446 if (ovsdb_atom_needs_destruction(type)) {
448 for (i = 0; i < n_atoms; i++) {
449 ovsdb_atom_destroy(&atoms[i], type);
456 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
458 free_data(type->key_type, datum->keys, datum->n);
459 free_data(type->value_type, datum->values, datum->n);
463 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
465 struct ovsdb_datum tmp = *a;
470 struct ovsdb_datum_sort_cbdata {
471 const struct ovsdb_type *type;
472 struct ovsdb_datum *datum;
476 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
478 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
480 return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
481 &cbdata->datum->keys[b],
482 cbdata->type->key_type);
486 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
488 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
490 ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
491 if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
492 ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
497 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
502 struct ovsdb_datum_sort_cbdata cbdata;
506 cbdata.datum = datum;
507 sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
510 for (i = 0; i < datum->n - 1; i++) {
511 if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
513 if (ovsdb_type_is_map(type)) {
514 return ovsdb_error(NULL, "map contains duplicate key");
516 return ovsdb_error(NULL, "set contains duplicate");
526 ovsdb_datum_from_json(struct ovsdb_datum *datum,
527 const struct ovsdb_type *type,
528 const struct json *json,
529 const struct ovsdb_symbol_table *symtab)
531 struct ovsdb_error *error;
533 if (ovsdb_type_is_scalar(type)) {
535 datum->keys = xmalloc(sizeof *datum->keys);
536 datum->values = NULL;
538 error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
545 bool is_map = ovsdb_type_is_map(type);
546 const char *class = is_map ? "map" : "set";
547 const struct json *inner;
551 assert(is_map || ovsdb_type_is_set(type));
553 error = unwrap_json(json, class, JSON_ARRAY, &inner);
558 n = inner->u.array.n;
559 if (n < type->n_min || n > type->n_max) {
560 return ovsdb_syntax_error(json, NULL, "%s must have %u to "
561 "%u members but %zu are present",
562 class, type->n_min, type->n_max, n);
566 datum->keys = xmalloc(n * sizeof *datum->keys);
567 datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
568 for (i = 0; i < n; i++) {
569 const struct json *element = inner->u.array.elems[i];
570 const struct json *key = NULL;
571 const struct json *value = NULL;
576 error = parse_json_pair(element, &key, &value);
582 error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
589 error = ovsdb_atom_from_json(&datum->values[i],
590 type->value_type, value, symtab);
592 ovsdb_atom_destroy(&datum->keys[i], type->key_type);
600 error = ovsdb_datum_sort(datum, type);
608 ovsdb_datum_destroy(datum, type);
614 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
615 const struct ovsdb_type *type)
617 /* These tests somewhat tolerate a 'datum' that does not exactly match
618 * 'type', in particular a datum with 'n' not in the allowed range. */
619 if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
620 return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
621 } else if (type->value_type == OVSDB_TYPE_VOID) {
625 elems = xmalloc(datum->n * sizeof *elems);
626 for (i = 0; i < datum->n; i++) {
627 elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
630 return wrap_json("set", json_array_create(elems, datum->n));
635 elems = xmalloc(datum->n * sizeof *elems);
636 for (i = 0; i < datum->n; i++) {
637 elems[i] = json_array_create_2(
638 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
639 ovsdb_atom_to_json(&datum->values[i], type->value_type));
642 return wrap_json("map", json_array_create(elems, datum->n));
647 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
648 unsigned int n, uint32_t basis)
650 if (type != OVSDB_TYPE_VOID) {
653 for (i = 0; i < n; i++) {
654 basis = ovsdb_atom_hash(&atoms[i], type, basis);
661 ovsdb_datum_hash(const struct ovsdb_datum *datum,
662 const struct ovsdb_type *type, uint32_t basis)
664 basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
665 basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
666 basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
671 atom_arrays_compare_3way(const union ovsdb_atom *a,
672 const union ovsdb_atom *b,
673 enum ovsdb_atomic_type type,
678 for (i = 0; i < n; i++) {
679 int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
689 ovsdb_datum_equals(const struct ovsdb_datum *a,
690 const struct ovsdb_datum *b,
691 const struct ovsdb_type *type)
693 return !ovsdb_datum_compare_3way(a, b, type);
697 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
698 const struct ovsdb_datum *b,
699 const struct ovsdb_type *type)
704 return a->n < b->n ? -1 : 1;
707 cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
712 return (type->value_type == OVSDB_TYPE_VOID ? 0
713 : atom_arrays_compare_3way(a->values, b->values, type->value_type,
717 /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
718 * otherwise UINT_MAX. 'key_type' must be the type of the atoms stored in the
719 * 'keys' array in 'datum'.
722 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
723 const union ovsdb_atom *key,
724 enum ovsdb_atomic_type key_type)
726 unsigned int low = 0;
727 unsigned int high = datum->n;
729 unsigned int idx = (low + high) / 2;
730 int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
733 } else if (cmp > 0) {
742 /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
743 * index within 'datum', otherwise UINT_MAX. 'key_type' must be the type of
744 * the atoms stored in the 'keys' array in 'datum'. 'value_type' may be the
745 * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
748 ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
749 const union ovsdb_atom *key,
750 enum ovsdb_atomic_type key_type,
751 const union ovsdb_atom *value,
752 enum ovsdb_atomic_type value_type)
754 unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
756 && value_type != OVSDB_TYPE_VOID
757 && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
763 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
764 * UINT_MAX. 'type' must be the type of 'a' and 'b', except that
765 * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
768 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
769 const struct ovsdb_datum *b,
770 const struct ovsdb_type *type)
772 return ovsdb_datum_find_key_value(b,
773 &a->keys[i], type->key_type,
774 a->values ? &a->values[i] : NULL,
778 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
780 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
781 const struct ovsdb_datum *b,
782 const struct ovsdb_type *type)
786 for (i = 0; i < a->n; i++) {
787 if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
794 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
796 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
797 const struct ovsdb_datum *b,
798 const struct ovsdb_type *type)
802 for (i = 0; i < a->n; i++) {
803 if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
811 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
812 unsigned int capacity)
814 a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
815 if (type->value_type != OVSDB_TYPE_VOID) {
816 a->values = xrealloc(a->values, capacity * sizeof *a->values);
820 /* Removes the element with index 'idx' from 'datum', which has type 'type'.
821 * If 'idx' is not the last element in 'datum', then the removed element is
822 * replaced by the (former) last element.
824 * This function does not maintain ovsdb_datum invariants. Use
825 * ovsdb_datum_sort() to check and restore these invariants. */
827 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
828 const struct ovsdb_type *type)
830 ovsdb_atom_destroy(&datum->keys[idx], type->key_type);
831 datum->keys[idx] = datum->keys[datum->n - 1];
832 if (type->value_type != OVSDB_TYPE_VOID) {
833 ovsdb_atom_destroy(&datum->values[idx], type->value_type);
834 datum->values[idx] = datum->values[datum->n - 1];
839 /* Adds the element with the given 'key' and 'value' to 'datum', which must
840 * have the specified 'type'.
842 * This function always allocates memory, so it is not an efficient way to add
843 * a number of elements to a datum.
845 * This function does not maintain ovsdb_datum invariants. Use
846 * ovsdb_datum_sort() to check and restore these invariants. (But a datum with
847 * 0 or 1 elements cannot violate the invariants anyhow.) */
849 ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
850 const union ovsdb_atom *key,
851 const union ovsdb_atom *value,
852 const struct ovsdb_type *type)
854 size_t idx = datum->n++;
855 datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
856 ovsdb_atom_clone(&datum->keys[idx], key, type->key_type);
857 if (type->value_type != OVSDB_TYPE_VOID) {
858 datum->values = xrealloc(datum->values,
859 datum->n * sizeof *datum->values);
860 ovsdb_atom_clone(&datum->values[idx], value, type->value_type);
865 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
866 const struct ovsdb_type *type, bool replace)
872 for (bi = 0; bi < b->n; bi++) {
875 ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type);
876 if (ai == UINT_MAX) {
878 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
880 ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type);
881 if (type->value_type != OVSDB_TYPE_VOID) {
882 ovsdb_atom_clone(&a->values[n], &b->values[bi],
886 } else if (replace && type->value_type != OVSDB_TYPE_VOID) {
887 ovsdb_atom_destroy(&a->values[ai], type->value_type);
888 ovsdb_atom_clone(&a->values[ai], &b->values[bi],
893 struct ovsdb_error *error;
895 error = ovsdb_datum_sort(a, type);
901 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
902 const struct ovsdb_datum *b,
903 const struct ovsdb_type *b_type)
905 bool changed = false;
908 assert(a_type->key_type == b_type->key_type);
909 assert(a_type->value_type == b_type->value_type
910 || b_type->value_type == OVSDB_TYPE_VOID);
912 /* XXX The big-O of this could easily be improved. */
913 for (i = 0; i < a->n; ) {
914 unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
915 if (idx != UINT_MAX) {
917 ovsdb_datum_remove_unsafe(a, i, a_type);
923 struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
928 struct ovsdb_symbol_table {
932 struct ovsdb_symbol_table *
933 ovsdb_symbol_table_create(void)
935 struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
936 shash_init(&symtab->sh);
941 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
944 struct shash_node *node, *next;
946 SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
947 struct ovsdb_symbol *symbol = node->data;
949 shash_delete(&symtab->sh, node);
951 shash_destroy(&symtab->sh);
956 struct ovsdb_symbol *
957 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
960 return shash_find_data(&symtab->sh, name);
964 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
965 const struct uuid *uuid, bool used)
967 struct ovsdb_symbol *symbol;
969 assert(!ovsdb_symbol_table_get(symtab, name));
970 symbol = xmalloc(sizeof *symbol);
971 symbol->uuid = *uuid;
973 shash_add(&symtab->sh, name, symbol);