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"
23 #include "ovsdb-error.h"
29 wrap_json(const char *name, struct json *wrapped)
31 return json_array_create_2(json_string_create(name), wrapped);
35 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
41 case OVSDB_TYPE_INTEGER:
49 case OVSDB_TYPE_BOOLEAN:
50 atom->boolean = false;
53 case OVSDB_TYPE_STRING:
54 atom->string = xmemdup("", 1);
58 uuid_zero(&atom->uuid);
68 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
69 enum ovsdb_atomic_type type)
75 case OVSDB_TYPE_INTEGER:
76 new->integer = old->integer;
80 new->real = old->real;
83 case OVSDB_TYPE_BOOLEAN:
84 new->boolean = old->boolean;
87 case OVSDB_TYPE_STRING:
88 new->string = xstrdup(old->string);
92 new->uuid = old->uuid;
102 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
104 union ovsdb_atom tmp = *a;
110 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
114 case OVSDB_TYPE_VOID:
117 case OVSDB_TYPE_INTEGER:
118 return hash_int(atom->integer, basis);
120 case OVSDB_TYPE_REAL:
121 return hash_double(atom->real, basis);
123 case OVSDB_TYPE_BOOLEAN:
124 return hash_boolean(atom->boolean, basis);
126 case OVSDB_TYPE_STRING:
127 return hash_string(atom->string, basis);
129 case OVSDB_TYPE_UUID:
130 return hash_int(uuid_hash(&atom->uuid), basis);
139 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
140 const union ovsdb_atom *b,
141 enum ovsdb_atomic_type type)
144 case OVSDB_TYPE_VOID:
147 case OVSDB_TYPE_INTEGER:
148 return a->integer < b->integer ? -1 : a->integer > b->integer;
150 case OVSDB_TYPE_REAL:
151 return a->real < b->real ? -1 : a->real > b->real;
153 case OVSDB_TYPE_BOOLEAN:
154 return a->boolean - b->boolean;
156 case OVSDB_TYPE_STRING:
157 return strcmp(a->string, b->string);
159 case OVSDB_TYPE_UUID:
160 return uuid_compare_3way(&a->uuid, &b->uuid);
168 static struct ovsdb_error *
169 unwrap_json(const struct json *json, const char *name,
170 enum json_type value_type, const struct json **value)
172 if (json->type != JSON_ARRAY
173 || json->u.array.n != 2
174 || json->u.array.elems[0]->type != JSON_STRING
175 || (name && strcmp(json->u.array.elems[0]->u.string, name))
176 || json->u.array.elems[1]->type != value_type)
178 return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
179 json_type_to_string(value_type));
181 *value = json->u.array.elems[1];
185 static struct ovsdb_error *
186 parse_json_pair(const struct json *json,
187 const struct json **elem0, const struct json **elem1)
189 if (json->type != JSON_ARRAY || json->u.array.n != 2) {
190 return ovsdb_syntax_error(json, NULL, "expected 2-element array");
192 *elem0 = json->u.array.elems[0];
193 *elem1 = json->u.array.elems[1];
197 static struct ovsdb_error *
198 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
199 const struct ovsdb_symbol_table *symtab)
202 static struct ovsdb_error *
203 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
204 const struct ovsdb_symbol_table *symtab)
206 struct ovsdb_error *error0;
207 const struct json *value;
209 error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
211 const char *uuid_string = json_string(value);
212 if (!uuid_from_string(uuid, uuid_string)) {
213 return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
217 struct ovsdb_error *error1;
219 error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
221 const char *name = json_string(value);
222 const struct ovsdb_symbol *symbol;
224 ovsdb_error_destroy(error0);
226 symbol = ovsdb_symbol_table_get(symtab, name);
228 *uuid = symbol->uuid;
231 return ovsdb_syntax_error(json, NULL,
232 "unknown named-uuid \"%s\"", name);
235 ovsdb_error_destroy(error1);
242 ovsdb_atom_from_json(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
243 const struct json *json,
244 const struct ovsdb_symbol_table *symtab)
247 case OVSDB_TYPE_VOID:
250 case OVSDB_TYPE_INTEGER:
251 if (json->type == JSON_INTEGER) {
252 atom->integer = json->u.integer;
257 case OVSDB_TYPE_REAL:
258 if (json->type == JSON_INTEGER) {
259 atom->real = json->u.integer;
261 } else if (json->type == JSON_REAL) {
262 atom->real = json->u.real;
267 case OVSDB_TYPE_BOOLEAN:
268 if (json->type == JSON_TRUE) {
269 atom->boolean = true;
271 } else if (json->type == JSON_FALSE) {
272 atom->boolean = false;
277 case OVSDB_TYPE_STRING:
278 if (json->type == JSON_STRING) {
279 atom->string = xstrdup(json->u.string);
284 case OVSDB_TYPE_UUID:
285 return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
292 return ovsdb_syntax_error(json, NULL, "expected %s",
293 ovsdb_atomic_type_to_string(type));
297 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
300 case OVSDB_TYPE_VOID:
303 case OVSDB_TYPE_INTEGER:
304 return json_integer_create(atom->integer);
306 case OVSDB_TYPE_REAL:
307 return json_real_create(atom->real);
309 case OVSDB_TYPE_BOOLEAN:
310 return json_boolean_create(atom->boolean);
312 case OVSDB_TYPE_STRING:
313 return json_string_create(atom->string);
315 case OVSDB_TYPE_UUID:
316 return wrap_json("uuid", json_string_create_nocopy(
317 xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
325 static union ovsdb_atom *
326 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
328 if (type != OVSDB_TYPE_VOID && n) {
329 union ovsdb_atom *atoms;
332 atoms = xmalloc(n * sizeof *atoms);
333 for (i = 0; i < n; i++) {
334 ovsdb_atom_init_default(&atoms[i], type);
338 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
339 * treated as xmalloc(1). */
345 ovsdb_datum_init_default(struct ovsdb_datum *datum,
346 const struct ovsdb_type *type)
348 datum->n = type->n_min;
349 datum->keys = alloc_default_atoms(type->key_type, datum->n);
350 datum->values = alloc_default_atoms(type->value_type, datum->n);
353 static union ovsdb_atom *
354 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
356 if (type != OVSDB_TYPE_VOID && n) {
357 union ovsdb_atom *new;
360 new = xmalloc(n * sizeof *new);
361 for (i = 0; i < n; i++) {
362 ovsdb_atom_clone(&new[i], &old[i], type);
366 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
367 * treated as xmalloc(1). */
373 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
374 const struct ovsdb_type *type)
376 unsigned int n = old->n;
378 new->keys = clone_atoms(old->keys, type->key_type, n);
379 new->values = clone_atoms(old->values, type->value_type, n);
383 free_data(enum ovsdb_atomic_type type,
384 union ovsdb_atom *atoms, size_t n_atoms)
386 if (ovsdb_atom_needs_destruction(type)) {
388 for (i = 0; i < n_atoms; i++) {
389 ovsdb_atom_destroy(&atoms[i], type);
396 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
398 free_data(type->key_type, datum->keys, datum->n);
399 free_data(type->value_type, datum->values, datum->n);
403 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
405 struct ovsdb_datum tmp = *a;
410 struct ovsdb_datum_sort_cbdata {
411 const struct ovsdb_type *type;
412 struct ovsdb_datum *datum;
416 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
418 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
420 return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
421 &cbdata->datum->keys[b],
422 cbdata->type->key_type);
426 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
428 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
430 ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
431 if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
432 ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
436 static struct ovsdb_error *
437 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
442 struct ovsdb_datum_sort_cbdata cbdata;
446 cbdata.datum = datum;
447 sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
450 for (i = 0; i < datum->n - 1; i++) {
451 if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
453 if (ovsdb_type_is_map(type)) {
454 return ovsdb_error(NULL, "map contains duplicate key");
456 return ovsdb_error(NULL, "set contains duplicate");
466 ovsdb_datum_from_json(struct ovsdb_datum *datum,
467 const struct ovsdb_type *type,
468 const struct json *json,
469 const struct ovsdb_symbol_table *symtab)
471 struct ovsdb_error *error;
473 if (ovsdb_type_is_scalar(type)) {
475 datum->keys = xmalloc(sizeof *datum->keys);
476 datum->values = NULL;
478 error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
485 bool is_map = ovsdb_type_is_map(type);
486 const char *class = is_map ? "map" : "set";
487 const struct json *inner;
491 assert(is_map || ovsdb_type_is_set(type));
493 error = unwrap_json(json, class, JSON_ARRAY, &inner);
498 n = inner->u.array.n;
499 if (n < type->n_min || n > type->n_max) {
500 return ovsdb_syntax_error(json, NULL, "%s must have %u to "
501 "%u members but %zu are present",
502 class, type->n_min, type->n_max, n);
506 datum->keys = xmalloc(n * sizeof *datum->keys);
507 datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
508 for (i = 0; i < n; i++) {
509 const struct json *element = inner->u.array.elems[i];
510 const struct json *key = NULL;
511 const struct json *value = NULL;
516 error = parse_json_pair(element, &key, &value);
522 error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
529 error = ovsdb_atom_from_json(&datum->values[i],
530 type->value_type, value, symtab);
532 ovsdb_atom_destroy(&datum->keys[i], type->key_type);
540 error = ovsdb_datum_sort(datum, type);
548 ovsdb_datum_destroy(datum, type);
554 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
555 const struct ovsdb_type *type)
557 /* These tests somewhat tolerate a 'datum' that does not exactly match
558 * 'type', in particular a datum with 'n' not in the allowed range. */
559 if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
560 return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
561 } else if (type->value_type == OVSDB_TYPE_VOID) {
565 elems = xmalloc(datum->n * sizeof *elems);
566 for (i = 0; i < datum->n; i++) {
567 elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
570 return wrap_json("set", json_array_create(elems, datum->n));
575 elems = xmalloc(datum->n * sizeof *elems);
576 for (i = 0; i < datum->n; i++) {
577 elems[i] = json_array_create_2(
578 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
579 ovsdb_atom_to_json(&datum->values[i], type->value_type));
582 return wrap_json("map", json_array_create(elems, datum->n));
587 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
588 unsigned int n, uint32_t basis)
590 if (type != OVSDB_TYPE_VOID) {
593 for (i = 0; i < n; i++) {
594 basis = ovsdb_atom_hash(&atoms[i], type, basis);
601 ovsdb_datum_hash(const struct ovsdb_datum *datum,
602 const struct ovsdb_type *type, uint32_t basis)
604 basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
605 basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
606 basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
611 atom_arrays_compare_3way(const union ovsdb_atom *a,
612 const union ovsdb_atom *b,
613 enum ovsdb_atomic_type type,
618 for (i = 0; i < n; i++) {
619 int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
629 ovsdb_datum_equals(const struct ovsdb_datum *a,
630 const struct ovsdb_datum *b,
631 const struct ovsdb_type *type)
633 return !ovsdb_datum_compare_3way(a, b, type);
637 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
638 const struct ovsdb_datum *b,
639 const struct ovsdb_type *type)
644 return a->n < b->n ? -1 : 1;
647 cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
652 return (type->value_type == OVSDB_TYPE_VOID ? 0
653 : atom_arrays_compare_3way(a->values, b->values, type->value_type,
658 ovsdb_datum_contains(const struct ovsdb_datum *a, int i,
659 const struct ovsdb_datum *b,
660 const struct ovsdb_type *type)
665 int j = (low + high) / 2;
666 int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j], type->key_type);
669 } else if (cmp > 0) {
672 return (type->value_type == OVSDB_TYPE_VOID
673 || ovsdb_atom_equals(&a->values[i], &b->values[j],
680 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
682 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
683 const struct ovsdb_datum *b,
684 const struct ovsdb_type *type)
688 for (i = 0; i < a->n; i++) {
689 if (!ovsdb_datum_contains(a, i, b, type)) {
696 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
698 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
699 const struct ovsdb_datum *b,
700 const struct ovsdb_type *type)
704 for (i = 0; i < a->n; i++) {
705 if (ovsdb_datum_contains(a, i, b, type)) {
712 struct ovsdb_symbol_table {
716 struct ovsdb_symbol_table *
717 ovsdb_symbol_table_create(void)
719 struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
720 shash_init(&symtab->sh);
725 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
728 struct shash_node *node, *next;
730 SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
731 struct ovsdb_symbol *symbol = node->data;
733 shash_delete(&symtab->sh, node);
735 shash_destroy(&symtab->sh);
740 struct ovsdb_symbol *
741 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
744 return shash_find_data(&symtab->sh, name);
748 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
749 const struct uuid *uuid, bool used)
751 struct ovsdb_symbol *symbol;
753 assert(!ovsdb_symbol_table_get(symtab, name));
754 symbol = xmalloc(sizeof *symbol);
755 symbol->uuid = *uuid;
757 shash_add(&symtab->sh, name, symbol);