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_default(struct ovsdb_datum *datum,
376 const struct ovsdb_type *type)
378 datum->n = type->n_min;
379 datum->keys = alloc_default_atoms(type->key_type, datum->n);
380 datum->values = alloc_default_atoms(type->value_type, datum->n);
384 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
385 const struct ovsdb_type *type)
389 if (datum->n != type->n_min) {
392 for (i = 0; i < datum->n; i++) {
393 if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
396 if (type->value_type != OVSDB_TYPE_VOID
397 && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
405 static union ovsdb_atom *
406 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
408 if (type != OVSDB_TYPE_VOID && n) {
409 union ovsdb_atom *new;
412 new = xmalloc(n * sizeof *new);
413 for (i = 0; i < n; i++) {
414 ovsdb_atom_clone(&new[i], &old[i], type);
418 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
419 * treated as xmalloc(1). */
425 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
426 const struct ovsdb_type *type)
428 unsigned int n = old->n;
430 new->keys = clone_atoms(old->keys, type->key_type, n);
431 new->values = clone_atoms(old->values, type->value_type, n);
435 free_data(enum ovsdb_atomic_type type,
436 union ovsdb_atom *atoms, size_t n_atoms)
438 if (ovsdb_atom_needs_destruction(type)) {
440 for (i = 0; i < n_atoms; i++) {
441 ovsdb_atom_destroy(&atoms[i], type);
448 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
450 free_data(type->key_type, datum->keys, datum->n);
451 free_data(type->value_type, datum->values, datum->n);
455 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
457 struct ovsdb_datum tmp = *a;
462 struct ovsdb_datum_sort_cbdata {
463 const struct ovsdb_type *type;
464 struct ovsdb_datum *datum;
468 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
470 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
472 return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
473 &cbdata->datum->keys[b],
474 cbdata->type->key_type);
478 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
480 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
482 ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
483 if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
484 ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
489 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
494 struct ovsdb_datum_sort_cbdata cbdata;
498 cbdata.datum = datum;
499 sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
502 for (i = 0; i < datum->n - 1; i++) {
503 if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
505 if (ovsdb_type_is_map(type)) {
506 return ovsdb_error(NULL, "map contains duplicate key");
508 return ovsdb_error(NULL, "set contains duplicate");
518 ovsdb_datum_from_json(struct ovsdb_datum *datum,
519 const struct ovsdb_type *type,
520 const struct json *json,
521 const struct ovsdb_symbol_table *symtab)
523 struct ovsdb_error *error;
525 if (ovsdb_type_is_scalar(type)) {
527 datum->keys = xmalloc(sizeof *datum->keys);
528 datum->values = NULL;
530 error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
537 bool is_map = ovsdb_type_is_map(type);
538 const char *class = is_map ? "map" : "set";
539 const struct json *inner;
543 assert(is_map || ovsdb_type_is_set(type));
545 error = unwrap_json(json, class, JSON_ARRAY, &inner);
550 n = inner->u.array.n;
551 if (n < type->n_min || n > type->n_max) {
552 return ovsdb_syntax_error(json, NULL, "%s must have %u to "
553 "%u members but %zu are present",
554 class, type->n_min, type->n_max, n);
558 datum->keys = xmalloc(n * sizeof *datum->keys);
559 datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
560 for (i = 0; i < n; i++) {
561 const struct json *element = inner->u.array.elems[i];
562 const struct json *key = NULL;
563 const struct json *value = NULL;
568 error = parse_json_pair(element, &key, &value);
574 error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
581 error = ovsdb_atom_from_json(&datum->values[i],
582 type->value_type, value, symtab);
584 ovsdb_atom_destroy(&datum->keys[i], type->key_type);
592 error = ovsdb_datum_sort(datum, type);
600 ovsdb_datum_destroy(datum, type);
606 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
607 const struct ovsdb_type *type)
609 /* These tests somewhat tolerate a 'datum' that does not exactly match
610 * 'type', in particular a datum with 'n' not in the allowed range. */
611 if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
612 return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
613 } else if (type->value_type == OVSDB_TYPE_VOID) {
617 elems = xmalloc(datum->n * sizeof *elems);
618 for (i = 0; i < datum->n; i++) {
619 elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
622 return wrap_json("set", json_array_create(elems, datum->n));
627 elems = xmalloc(datum->n * sizeof *elems);
628 for (i = 0; i < datum->n; i++) {
629 elems[i] = json_array_create_2(
630 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
631 ovsdb_atom_to_json(&datum->values[i], type->value_type));
634 return wrap_json("map", json_array_create(elems, datum->n));
639 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
640 unsigned int n, uint32_t basis)
642 if (type != OVSDB_TYPE_VOID) {
645 for (i = 0; i < n; i++) {
646 basis = ovsdb_atom_hash(&atoms[i], type, basis);
653 ovsdb_datum_hash(const struct ovsdb_datum *datum,
654 const struct ovsdb_type *type, uint32_t basis)
656 basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
657 basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
658 basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
663 atom_arrays_compare_3way(const union ovsdb_atom *a,
664 const union ovsdb_atom *b,
665 enum ovsdb_atomic_type type,
670 for (i = 0; i < n; i++) {
671 int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
681 ovsdb_datum_equals(const struct ovsdb_datum *a,
682 const struct ovsdb_datum *b,
683 const struct ovsdb_type *type)
685 return !ovsdb_datum_compare_3way(a, b, type);
689 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
690 const struct ovsdb_datum *b,
691 const struct ovsdb_type *type)
696 return a->n < b->n ? -1 : 1;
699 cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
704 return (type->value_type == OVSDB_TYPE_VOID ? 0
705 : atom_arrays_compare_3way(a->values, b->values, type->value_type,
709 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
710 * UINT_MAX. 'type' must be the type of 'a' and 'b', except that
711 * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
714 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
715 const struct ovsdb_datum *b,
716 const struct ovsdb_type *type)
721 int j = (low + high) / 2;
722 int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j],
726 } else if (cmp > 0) {
729 bool eq_value = (type->value_type == OVSDB_TYPE_VOID
730 || ovsdb_atom_equals(&a->values[i], &b->values[j],
732 return eq_value ? j : UINT_MAX;
738 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
740 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
741 const struct ovsdb_datum *b,
742 const struct ovsdb_type *type)
746 for (i = 0; i < a->n; i++) {
747 if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
754 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
756 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
757 const struct ovsdb_datum *b,
758 const struct ovsdb_type *type)
762 for (i = 0; i < a->n; i++) {
763 if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
771 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
772 unsigned int capacity)
774 a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
775 if (type->value_type != OVSDB_TYPE_VOID) {
776 a->values = xrealloc(a->values, capacity * sizeof *a->values);
781 ovsdb_datum_remove(struct ovsdb_datum *a, size_t i,
782 const struct ovsdb_type *type)
784 ovsdb_atom_destroy(&a->keys[i], type->key_type);
785 a->keys[i] = a->keys[a->n - 1];
786 if (type->value_type != OVSDB_TYPE_VOID) {
787 ovsdb_atom_destroy(&a->values[i], type->value_type);
788 a->values[i] = a->values[a->n - 1];
794 ovsdb_datum_union(struct ovsdb_datum *a,
795 const struct ovsdb_datum *b, const struct ovsdb_type *type)
797 struct ovsdb_type type_without_value;
801 type_without_value = *type;
802 type_without_value.value_type = OVSDB_TYPE_VOID;
804 for (i = 0; i < b->n; i++) {
805 if (ovsdb_datum_find(b, i, a, &type_without_value) == UINT_MAX) {
807 ovsdb_datum_reallocate(a, type, a->n + (b->n - i));
809 ovsdb_atom_clone(&a->keys[n], &b->keys[i], type->key_type);
810 if (type->value_type != OVSDB_TYPE_VOID) {
811 ovsdb_atom_clone(&a->values[n], &b->values[i],
818 struct ovsdb_error *error;
820 error = ovsdb_datum_sort(a, type);
826 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
827 const struct ovsdb_datum *b,
828 const struct ovsdb_type *b_type)
830 bool changed = false;
833 assert(a_type->key_type == b_type->key_type);
834 assert(a_type->value_type == b_type->value_type
835 || b_type->value_type == OVSDB_TYPE_VOID);
837 /* XXX The big-O of this could easily be improved. */
838 for (i = 0; i < a->n; ) {
839 unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
840 if (idx != UINT_MAX) {
842 ovsdb_datum_remove(a, i, a_type);
848 struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
853 struct ovsdb_symbol_table {
857 struct ovsdb_symbol_table *
858 ovsdb_symbol_table_create(void)
860 struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
861 shash_init(&symtab->sh);
866 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
869 struct shash_node *node, *next;
871 SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
872 struct ovsdb_symbol *symbol = node->data;
874 shash_delete(&symtab->sh, node);
876 shash_destroy(&symtab->sh);
881 struct ovsdb_symbol *
882 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
885 return shash_find_data(&symtab->sh, name);
889 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
890 const struct uuid *uuid, bool used)
892 struct ovsdb_symbol *symbol;
894 assert(!ovsdb_symbol_table_get(symtab, name));
895 symbol = xmalloc(sizeof *symbol);
896 symbol->uuid = *uuid;
898 shash_add(&symtab->sh, name, symbol);