1 /* Copyright (c) 2009 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_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
70 enum ovsdb_atomic_type type)
76 case OVSDB_TYPE_INTEGER:
77 new->integer = old->integer;
81 new->real = old->real;
84 case OVSDB_TYPE_BOOLEAN:
85 new->boolean = old->boolean;
88 case OVSDB_TYPE_STRING:
89 new->string = xstrdup(old->string);
93 new->uuid = old->uuid;
103 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
105 union ovsdb_atom tmp = *a;
111 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
115 case OVSDB_TYPE_VOID:
118 case OVSDB_TYPE_INTEGER:
119 return hash_int(atom->integer, basis);
121 case OVSDB_TYPE_REAL:
122 return hash_double(atom->real, basis);
124 case OVSDB_TYPE_BOOLEAN:
125 return hash_boolean(atom->boolean, basis);
127 case OVSDB_TYPE_STRING:
128 return hash_string(atom->string, basis);
130 case OVSDB_TYPE_UUID:
131 return hash_int(uuid_hash(&atom->uuid), basis);
140 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
141 const union ovsdb_atom *b,
142 enum ovsdb_atomic_type type)
145 case OVSDB_TYPE_VOID:
148 case OVSDB_TYPE_INTEGER:
149 return a->integer < b->integer ? -1 : a->integer > b->integer;
151 case OVSDB_TYPE_REAL:
152 return a->real < b->real ? -1 : a->real > b->real;
154 case OVSDB_TYPE_BOOLEAN:
155 return a->boolean - b->boolean;
157 case OVSDB_TYPE_STRING:
158 return strcmp(a->string, b->string);
160 case OVSDB_TYPE_UUID:
161 return uuid_compare_3way(&a->uuid, &b->uuid);
169 static struct ovsdb_error *
170 unwrap_json(const struct json *json, const char *name,
171 enum json_type value_type, const struct json **value)
173 if (json->type != JSON_ARRAY
174 || json->u.array.n != 2
175 || json->u.array.elems[0]->type != JSON_STRING
176 || (name && strcmp(json->u.array.elems[0]->u.string, name))
177 || json->u.array.elems[1]->type != value_type)
179 return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
180 json_type_to_string(value_type));
182 *value = json->u.array.elems[1];
186 static struct ovsdb_error *
187 parse_json_pair(const struct json *json,
188 const struct json **elem0, const struct json **elem1)
190 if (json->type != JSON_ARRAY || json->u.array.n != 2) {
191 return ovsdb_syntax_error(json, NULL, "expected 2-element array");
193 *elem0 = json->u.array.elems[0];
194 *elem1 = json->u.array.elems[1];
198 static struct ovsdb_error *
199 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
200 const struct ovsdb_symbol_table *symtab)
203 static struct ovsdb_error *
204 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
205 const struct ovsdb_symbol_table *symtab)
207 struct ovsdb_error *error0;
208 const struct json *value;
210 error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
212 const char *uuid_string = json_string(value);
213 if (!uuid_from_string(uuid, uuid_string)) {
214 return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
218 struct ovsdb_error *error1;
220 error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
222 const char *name = json_string(value);
223 const struct ovsdb_symbol *symbol;
225 ovsdb_error_destroy(error0);
227 symbol = ovsdb_symbol_table_get(symtab, name);
229 *uuid = symbol->uuid;
232 return ovsdb_syntax_error(json, NULL,
233 "unknown named-uuid \"%s\"", name);
236 ovsdb_error_destroy(error1);
243 ovsdb_atom_from_json(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
244 const struct json *json,
245 const struct ovsdb_symbol_table *symtab)
248 case OVSDB_TYPE_VOID:
251 case OVSDB_TYPE_INTEGER:
252 if (json->type == JSON_INTEGER) {
253 atom->integer = json->u.integer;
258 case OVSDB_TYPE_REAL:
259 if (json->type == JSON_INTEGER) {
260 atom->real = json->u.integer;
262 } else if (json->type == JSON_REAL) {
263 atom->real = json->u.real;
268 case OVSDB_TYPE_BOOLEAN:
269 if (json->type == JSON_TRUE) {
270 atom->boolean = true;
272 } else if (json->type == JSON_FALSE) {
273 atom->boolean = false;
278 case OVSDB_TYPE_STRING:
279 if (json->type == JSON_STRING) {
280 atom->string = xstrdup(json->u.string);
285 case OVSDB_TYPE_UUID:
286 return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
293 return ovsdb_syntax_error(json, NULL, "expected %s",
294 ovsdb_atomic_type_to_string(type));
298 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
301 case OVSDB_TYPE_VOID:
304 case OVSDB_TYPE_INTEGER:
305 return json_integer_create(atom->integer);
307 case OVSDB_TYPE_REAL:
308 return json_real_create(atom->real);
310 case OVSDB_TYPE_BOOLEAN:
311 return json_boolean_create(atom->boolean);
313 case OVSDB_TYPE_STRING:
314 return json_string_create(atom->string);
316 case OVSDB_TYPE_UUID:
317 return wrap_json("uuid", json_string_create_nocopy(
318 xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
326 static union ovsdb_atom *
327 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
329 if (type != OVSDB_TYPE_VOID && n) {
330 union ovsdb_atom *atoms;
333 atoms = xmalloc(n * sizeof *atoms);
334 for (i = 0; i < n; i++) {
335 ovsdb_atom_init_default(&atoms[i], type);
339 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
340 * treated as xmalloc(1). */
346 ovsdb_datum_init_default(struct ovsdb_datum *datum,
347 const struct ovsdb_type *type)
349 datum->n = type->n_min;
350 datum->keys = alloc_default_atoms(type->key_type, datum->n);
351 datum->values = alloc_default_atoms(type->value_type, datum->n);
354 static union ovsdb_atom *
355 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
357 if (type != OVSDB_TYPE_VOID && n) {
358 union ovsdb_atom *new;
361 new = xmalloc(n * sizeof *new);
362 for (i = 0; i < n; i++) {
363 ovsdb_atom_clone(&new[i], &old[i], type);
367 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
368 * treated as xmalloc(1). */
374 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
375 const struct ovsdb_type *type)
377 unsigned int n = old->n;
379 new->keys = clone_atoms(old->keys, type->key_type, n);
380 new->values = clone_atoms(old->values, type->value_type, n);
384 free_data(enum ovsdb_atomic_type type,
385 union ovsdb_atom *atoms, size_t n_atoms)
387 if (ovsdb_atom_needs_destruction(type)) {
389 for (i = 0; i < n_atoms; i++) {
390 ovsdb_atom_destroy(&atoms[i], type);
397 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
399 free_data(type->key_type, datum->keys, datum->n);
400 free_data(type->value_type, datum->values, datum->n);
404 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
406 struct ovsdb_datum tmp = *a;
411 struct ovsdb_datum_sort_cbdata {
412 const struct ovsdb_type *type;
413 struct ovsdb_datum *datum;
417 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
419 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
421 return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
422 &cbdata->datum->keys[b],
423 cbdata->type->key_type);
427 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
429 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
431 ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
432 if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
433 ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
438 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
443 struct ovsdb_datum_sort_cbdata cbdata;
447 cbdata.datum = datum;
448 sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
451 for (i = 0; i < datum->n - 1; i++) {
452 if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
454 if (ovsdb_type_is_map(type)) {
455 return ovsdb_error(NULL, "map contains duplicate key");
457 return ovsdb_error(NULL, "set contains duplicate");
467 ovsdb_datum_from_json(struct ovsdb_datum *datum,
468 const struct ovsdb_type *type,
469 const struct json *json,
470 const struct ovsdb_symbol_table *symtab)
472 struct ovsdb_error *error;
474 if (ovsdb_type_is_scalar(type)) {
476 datum->keys = xmalloc(sizeof *datum->keys);
477 datum->values = NULL;
479 error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
486 bool is_map = ovsdb_type_is_map(type);
487 const char *class = is_map ? "map" : "set";
488 const struct json *inner;
492 assert(is_map || ovsdb_type_is_set(type));
494 error = unwrap_json(json, class, JSON_ARRAY, &inner);
499 n = inner->u.array.n;
500 if (n < type->n_min || n > type->n_max) {
501 return ovsdb_syntax_error(json, NULL, "%s must have %u to "
502 "%u members but %zu are present",
503 class, type->n_min, type->n_max, n);
507 datum->keys = xmalloc(n * sizeof *datum->keys);
508 datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
509 for (i = 0; i < n; i++) {
510 const struct json *element = inner->u.array.elems[i];
511 const struct json *key = NULL;
512 const struct json *value = NULL;
517 error = parse_json_pair(element, &key, &value);
523 error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
530 error = ovsdb_atom_from_json(&datum->values[i],
531 type->value_type, value, symtab);
533 ovsdb_atom_destroy(&datum->keys[i], type->key_type);
541 error = ovsdb_datum_sort(datum, type);
549 ovsdb_datum_destroy(datum, type);
555 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
556 const struct ovsdb_type *type)
558 /* These tests somewhat tolerate a 'datum' that does not exactly match
559 * 'type', in particular a datum with 'n' not in the allowed range. */
560 if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
561 return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
562 } else if (type->value_type == OVSDB_TYPE_VOID) {
566 elems = xmalloc(datum->n * sizeof *elems);
567 for (i = 0; i < datum->n; i++) {
568 elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
571 return wrap_json("set", json_array_create(elems, datum->n));
576 elems = xmalloc(datum->n * sizeof *elems);
577 for (i = 0; i < datum->n; i++) {
578 elems[i] = json_array_create_2(
579 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
580 ovsdb_atom_to_json(&datum->values[i], type->value_type));
583 return wrap_json("map", json_array_create(elems, datum->n));
588 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
589 unsigned int n, uint32_t basis)
591 if (type != OVSDB_TYPE_VOID) {
594 for (i = 0; i < n; i++) {
595 basis = ovsdb_atom_hash(&atoms[i], type, basis);
602 ovsdb_datum_hash(const struct ovsdb_datum *datum,
603 const struct ovsdb_type *type, uint32_t basis)
605 basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
606 basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
607 basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
612 atom_arrays_compare_3way(const union ovsdb_atom *a,
613 const union ovsdb_atom *b,
614 enum ovsdb_atomic_type type,
619 for (i = 0; i < n; i++) {
620 int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
630 ovsdb_datum_equals(const struct ovsdb_datum *a,
631 const struct ovsdb_datum *b,
632 const struct ovsdb_type *type)
634 return !ovsdb_datum_compare_3way(a, b, type);
638 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
639 const struct ovsdb_datum *b,
640 const struct ovsdb_type *type)
645 return a->n < b->n ? -1 : 1;
648 cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
653 return (type->value_type == OVSDB_TYPE_VOID ? 0
654 : atom_arrays_compare_3way(a->values, b->values, type->value_type,
658 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
659 * UINT_MAX. 'type' must be the type of 'a' and 'b', except that
660 * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
663 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
664 const struct ovsdb_datum *b,
665 const struct ovsdb_type *type)
670 int j = (low + high) / 2;
671 int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j],
675 } else if (cmp > 0) {
678 bool eq_value = (type->value_type == OVSDB_TYPE_VOID
679 || ovsdb_atom_equals(&a->values[i], &b->values[j],
681 return eq_value ? j : UINT_MAX;
687 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
689 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
690 const struct ovsdb_datum *b,
691 const struct ovsdb_type *type)
695 for (i = 0; i < a->n; i++) {
696 if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
703 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
705 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
706 const struct ovsdb_datum *b,
707 const struct ovsdb_type *type)
711 for (i = 0; i < a->n; i++) {
712 if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
720 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
721 unsigned int capacity)
723 a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
724 if (type->value_type != OVSDB_TYPE_VOID) {
725 a->values = xrealloc(a->values, capacity * sizeof *a->values);
730 ovsdb_datum_remove(struct ovsdb_datum *a, size_t i,
731 const struct ovsdb_type *type)
733 ovsdb_atom_destroy(&a->keys[i], type->key_type);
734 a->keys[i] = a->keys[a->n - 1];
735 if (type->value_type != OVSDB_TYPE_VOID) {
736 ovsdb_atom_destroy(&a->values[i], type->value_type);
737 a->values[i] = a->values[a->n - 1];
743 ovsdb_datum_union(struct ovsdb_datum *a,
744 const struct ovsdb_datum *b, const struct ovsdb_type *type)
746 struct ovsdb_type type_without_value;
750 type_without_value = *type;
751 type_without_value.value_type = OVSDB_TYPE_VOID;
753 for (i = 0; i < b->n; i++) {
754 if (ovsdb_datum_find(b, i, a, &type_without_value) == UINT_MAX) {
756 ovsdb_datum_reallocate(a, type, a->n + (b->n - i));
758 ovsdb_atom_clone(&a->keys[n], &b->keys[i], type->key_type);
759 if (type->value_type != OVSDB_TYPE_VOID) {
760 ovsdb_atom_clone(&a->values[n], &b->values[i],
767 struct ovsdb_error *error;
769 error = ovsdb_datum_sort(a, type);
775 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
776 const struct ovsdb_datum *b,
777 const struct ovsdb_type *b_type)
779 bool changed = false;
782 assert(a_type->key_type == b_type->key_type);
783 assert(a_type->value_type == b_type->value_type
784 || b_type->value_type == OVSDB_TYPE_VOID);
786 /* XXX The big-O of this could easily be improved. */
787 for (i = 0; i < a->n; ) {
788 unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
789 if (idx != UINT_MAX) {
791 ovsdb_datum_remove(a, i, a_type);
797 struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
802 struct ovsdb_symbol_table {
806 struct ovsdb_symbol_table *
807 ovsdb_symbol_table_create(void)
809 struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
810 shash_init(&symtab->sh);
815 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
818 struct shash_node *node, *next;
820 SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
821 struct ovsdb_symbol *symbol = node->data;
823 shash_delete(&symtab->sh, node);
825 shash_destroy(&symtab->sh);
830 struct ovsdb_symbol *
831 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
834 return shash_find_data(&symtab->sh, name);
838 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
839 const struct uuid *uuid, bool used)
841 struct ovsdb_symbol *symbol;
843 assert(!ovsdb_symbol_table_get(symtab, name));
844 symbol = xmalloc(sizeof *symbol);
845 symbol->uuid = *uuid;
847 shash_add(&symtab->sh, name, symbol);