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"
26 #include "dynamic-string.h"
28 #include "ovsdb-error.h"
34 wrap_json(const char *name, struct json *wrapped)
36 return json_array_create_2(json_string_create(name), wrapped);
40 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
46 case OVSDB_TYPE_INTEGER:
54 case OVSDB_TYPE_BOOLEAN:
55 atom->boolean = false;
58 case OVSDB_TYPE_STRING:
59 atom->string = xmemdup("", 1);
63 uuid_zero(&atom->uuid);
73 ovsdb_atom_is_default(const union ovsdb_atom *atom,
74 enum ovsdb_atomic_type type)
80 case OVSDB_TYPE_INTEGER:
81 return atom->integer == 0;
84 return atom->real == 0.0;
86 case OVSDB_TYPE_BOOLEAN:
87 return atom->boolean == false;
89 case OVSDB_TYPE_STRING:
90 return atom->string[0] == '\0';
93 return uuid_is_zero(&atom->uuid);
102 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
103 enum ovsdb_atomic_type type)
106 case OVSDB_TYPE_VOID:
109 case OVSDB_TYPE_INTEGER:
110 new->integer = old->integer;
113 case OVSDB_TYPE_REAL:
114 new->real = old->real;
117 case OVSDB_TYPE_BOOLEAN:
118 new->boolean = old->boolean;
121 case OVSDB_TYPE_STRING:
122 new->string = xstrdup(old->string);
125 case OVSDB_TYPE_UUID:
126 new->uuid = old->uuid;
136 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
138 union ovsdb_atom tmp = *a;
144 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
148 case OVSDB_TYPE_VOID:
151 case OVSDB_TYPE_INTEGER:
152 return hash_int(atom->integer, basis);
154 case OVSDB_TYPE_REAL:
155 return hash_double(atom->real, basis);
157 case OVSDB_TYPE_BOOLEAN:
158 return hash_boolean(atom->boolean, basis);
160 case OVSDB_TYPE_STRING:
161 return hash_string(atom->string, basis);
163 case OVSDB_TYPE_UUID:
164 return hash_int(uuid_hash(&atom->uuid), basis);
173 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
174 const union ovsdb_atom *b,
175 enum ovsdb_atomic_type type)
178 case OVSDB_TYPE_VOID:
181 case OVSDB_TYPE_INTEGER:
182 return a->integer < b->integer ? -1 : a->integer > b->integer;
184 case OVSDB_TYPE_REAL:
185 return a->real < b->real ? -1 : a->real > b->real;
187 case OVSDB_TYPE_BOOLEAN:
188 return a->boolean - b->boolean;
190 case OVSDB_TYPE_STRING:
191 return strcmp(a->string, b->string);
193 case OVSDB_TYPE_UUID:
194 return uuid_compare_3way(&a->uuid, &b->uuid);
202 static struct ovsdb_error *
203 unwrap_json(const struct json *json, const char *name,
204 enum json_type value_type, const struct json **value)
206 if (json->type != JSON_ARRAY
207 || json->u.array.n != 2
208 || json->u.array.elems[0]->type != JSON_STRING
209 || (name && strcmp(json->u.array.elems[0]->u.string, name))
210 || json->u.array.elems[1]->type != value_type)
212 return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
213 json_type_to_string(value_type));
215 *value = json->u.array.elems[1];
219 static struct ovsdb_error *
220 parse_json_pair(const struct json *json,
221 const struct json **elem0, const struct json **elem1)
223 if (json->type != JSON_ARRAY || json->u.array.n != 2) {
224 return ovsdb_syntax_error(json, NULL, "expected 2-element array");
226 *elem0 = json->u.array.elems[0];
227 *elem1 = json->u.array.elems[1];
231 static struct ovsdb_error *
232 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
233 const struct ovsdb_symbol_table *symtab)
236 static struct ovsdb_error *
237 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
238 const struct ovsdb_symbol_table *symtab)
240 struct ovsdb_error *error0;
241 const struct json *value;
243 error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
245 const char *uuid_string = json_string(value);
246 if (!uuid_from_string(uuid, uuid_string)) {
247 return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
251 struct ovsdb_error *error1;
253 error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
255 const char *name = json_string(value);
256 const struct ovsdb_symbol *symbol;
258 ovsdb_error_destroy(error0);
260 symbol = ovsdb_symbol_table_get(symtab, name);
262 *uuid = symbol->uuid;
265 return ovsdb_syntax_error(json, NULL,
266 "unknown named-uuid \"%s\"", name);
269 ovsdb_error_destroy(error1);
276 ovsdb_atom_from_json(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
277 const struct json *json,
278 const struct ovsdb_symbol_table *symtab)
281 case OVSDB_TYPE_VOID:
284 case OVSDB_TYPE_INTEGER:
285 if (json->type == JSON_INTEGER) {
286 atom->integer = json->u.integer;
291 case OVSDB_TYPE_REAL:
292 if (json->type == JSON_INTEGER) {
293 atom->real = json->u.integer;
295 } else if (json->type == JSON_REAL) {
296 atom->real = json->u.real;
301 case OVSDB_TYPE_BOOLEAN:
302 if (json->type == JSON_TRUE) {
303 atom->boolean = true;
305 } else if (json->type == JSON_FALSE) {
306 atom->boolean = false;
311 case OVSDB_TYPE_STRING:
312 if (json->type == JSON_STRING) {
313 atom->string = xstrdup(json->u.string);
318 case OVSDB_TYPE_UUID:
319 return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
326 return ovsdb_syntax_error(json, NULL, "expected %s",
327 ovsdb_atomic_type_to_string(type));
331 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
334 case OVSDB_TYPE_VOID:
337 case OVSDB_TYPE_INTEGER:
338 return json_integer_create(atom->integer);
340 case OVSDB_TYPE_REAL:
341 return json_real_create(atom->real);
343 case OVSDB_TYPE_BOOLEAN:
344 return json_boolean_create(atom->boolean);
346 case OVSDB_TYPE_STRING:
347 return json_string_create(atom->string);
349 case OVSDB_TYPE_UUID:
350 return wrap_json("uuid", json_string_create_nocopy(
351 xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
359 /* Initializes 'atom' to a value of the given 'type' parsed from 's', which
360 * takes one of the following forms:
362 * - OVSDB_TYPE_INTEGER: A decimal integer optionally preceded by a sign.
364 * - OVSDB_TYPE_REAL: A floating-point number in the format accepted by
367 * - OVSDB_TYPE_BOOLEAN: "true", "yes", "on", "1" for true, or "false",
368 * "no", "off", or "0" for false.
370 * - OVSDB_TYPE_STRING: A JSON string if it begins with a quote, otherwise
371 * an arbitrary string.
373 * - OVSDB_TYPE_UUID: A UUID in RFC 4122 format.
375 * Returns a null pointer if successful, otherwise an error message describing
376 * the problem. The caller is responsible for freeing the error.
379 ovsdb_atom_from_string(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
383 case OVSDB_TYPE_VOID:
386 case OVSDB_TYPE_INTEGER: {
387 long long int integer;
388 if (!str_to_llong(s, 10, &integer)) {
389 return xasprintf("\"%s\" is not a valid integer", s);
391 atom->integer = integer;
395 case OVSDB_TYPE_REAL:
396 if (!str_to_double(s, &atom->real)) {
397 return xasprintf("\"%s\" is not a valid real number", s);
401 case OVSDB_TYPE_BOOLEAN:
402 if (!strcmp(s, "true") || !strcmp(s, "yes") || !strcmp(s, "on")
403 || !strcmp(s, "1")) {
404 atom->boolean = true;
405 } else if (!strcmp(s, "false") || !strcmp(s, "no") || !strcmp(s, "off")
406 || !strcmp(s, "0")) {
407 atom->boolean = false;
409 return xasprintf("\"%s\" is not a valid boolean "
410 "(use \"true\" or \"false\")", s);
414 case OVSDB_TYPE_STRING:
416 return xstrdup("An empty string is not valid as input; "
417 "use \"\" to represent the empty string");
418 } else if (*s == '"') {
419 size_t s_len = strlen(s);
421 if (s_len < 2 || s[s_len - 1] != '"') {
422 return xasprintf("%s: missing quote at end of "
424 } else if (!json_string_unescape(s + 1, s_len - 2,
426 char *error = xasprintf("%s: %s", s, atom->string);
431 atom->string = xstrdup(s);
435 case OVSDB_TYPE_UUID:
436 if (!uuid_from_string(&atom->uuid, s)) {
437 return xasprintf("\"%s\" is not a valid UUID", s);
450 string_needs_quotes(const char *s)
456 if (!isalpha(c) && c != '_') {
460 while ((c = *p++) != '\0') {
461 if (!isalpha(c) && c != '_' && c != '-' && c != '.') {
466 if (!strcmp(s, "true") || !strcmp(s, "false")) {
473 /* Appends 'atom' (which has the given 'type') to 'out', in a format acceptable
474 * to ovsdb_atom_from_string(). */
476 ovsdb_atom_to_string(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
480 case OVSDB_TYPE_VOID:
483 case OVSDB_TYPE_INTEGER:
484 ds_put_format(out, "%"PRId64, atom->integer);
487 case OVSDB_TYPE_REAL:
488 ds_put_format(out, "%.*g", DBL_DIG, atom->real);
491 case OVSDB_TYPE_BOOLEAN:
492 ds_put_cstr(out, atom->boolean ? "true" : "false");
495 case OVSDB_TYPE_STRING:
496 if (string_needs_quotes(atom->string)) {
499 json.type = JSON_STRING;
500 json.u.string = atom->string;
501 json_to_ds(&json, 0, out);
503 ds_put_cstr(out, atom->string);
507 case OVSDB_TYPE_UUID:
508 ds_put_format(out, UUID_FMT, UUID_ARGS(&atom->uuid));
517 static union ovsdb_atom *
518 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
520 if (type != OVSDB_TYPE_VOID && n) {
521 union ovsdb_atom *atoms;
524 atoms = xmalloc(n * sizeof *atoms);
525 for (i = 0; i < n; i++) {
526 ovsdb_atom_init_default(&atoms[i], type);
530 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
531 * treated as xmalloc(1). */
537 ovsdb_datum_init_empty(struct ovsdb_datum *datum)
541 datum->values = NULL;
545 ovsdb_datum_init_default(struct ovsdb_datum *datum,
546 const struct ovsdb_type *type)
548 datum->n = type->n_min;
549 datum->keys = alloc_default_atoms(type->key_type, datum->n);
550 datum->values = alloc_default_atoms(type->value_type, datum->n);
554 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
555 const struct ovsdb_type *type)
559 if (datum->n != type->n_min) {
562 for (i = 0; i < datum->n; i++) {
563 if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
566 if (type->value_type != OVSDB_TYPE_VOID
567 && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
575 static union ovsdb_atom *
576 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
578 if (type != OVSDB_TYPE_VOID && n) {
579 union ovsdb_atom *new;
582 new = xmalloc(n * sizeof *new);
583 for (i = 0; i < n; i++) {
584 ovsdb_atom_clone(&new[i], &old[i], type);
588 /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
589 * treated as xmalloc(1). */
595 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
596 const struct ovsdb_type *type)
598 unsigned int n = old->n;
600 new->keys = clone_atoms(old->keys, type->key_type, n);
601 new->values = clone_atoms(old->values, type->value_type, n);
605 free_data(enum ovsdb_atomic_type type,
606 union ovsdb_atom *atoms, size_t n_atoms)
608 if (ovsdb_atom_needs_destruction(type)) {
610 for (i = 0; i < n_atoms; i++) {
611 ovsdb_atom_destroy(&atoms[i], type);
618 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
620 free_data(type->key_type, datum->keys, datum->n);
621 free_data(type->value_type, datum->values, datum->n);
625 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
627 struct ovsdb_datum tmp = *a;
632 struct ovsdb_datum_sort_cbdata {
633 const struct ovsdb_type *type;
634 struct ovsdb_datum *datum;
638 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
640 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
642 return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
643 &cbdata->datum->keys[b],
644 cbdata->type->key_type);
648 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
650 struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
652 ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
653 if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
654 ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
659 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
664 struct ovsdb_datum_sort_cbdata cbdata;
668 cbdata.datum = datum;
669 sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
672 for (i = 0; i < datum->n - 1; i++) {
673 if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
675 if (ovsdb_type_is_map(type)) {
676 return ovsdb_error(NULL, "map contains duplicate key");
678 return ovsdb_error(NULL, "set contains duplicate");
688 ovsdb_datum_from_json(struct ovsdb_datum *datum,
689 const struct ovsdb_type *type,
690 const struct json *json,
691 const struct ovsdb_symbol_table *symtab)
693 struct ovsdb_error *error;
695 if (ovsdb_type_is_scalar(type)) {
697 datum->keys = xmalloc(sizeof *datum->keys);
698 datum->values = NULL;
700 error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
707 bool is_map = ovsdb_type_is_map(type);
708 const char *class = is_map ? "map" : "set";
709 const struct json *inner;
713 assert(is_map || ovsdb_type_is_set(type));
715 error = unwrap_json(json, class, JSON_ARRAY, &inner);
720 n = inner->u.array.n;
721 if (n < type->n_min || n > type->n_max) {
722 return ovsdb_syntax_error(json, NULL, "%s must have %u to "
723 "%u members but %zu are present",
724 class, type->n_min, type->n_max, n);
728 datum->keys = xmalloc(n * sizeof *datum->keys);
729 datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
730 for (i = 0; i < n; i++) {
731 const struct json *element = inner->u.array.elems[i];
732 const struct json *key = NULL;
733 const struct json *value = NULL;
738 error = parse_json_pair(element, &key, &value);
744 error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
751 error = ovsdb_atom_from_json(&datum->values[i],
752 type->value_type, value, symtab);
754 ovsdb_atom_destroy(&datum->keys[i], type->key_type);
762 error = ovsdb_datum_sort(datum, type);
770 ovsdb_datum_destroy(datum, type);
776 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
777 const struct ovsdb_type *type)
779 /* These tests somewhat tolerate a 'datum' that does not exactly match
780 * 'type', in particular a datum with 'n' not in the allowed range. */
781 if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
782 return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
783 } else if (type->value_type == OVSDB_TYPE_VOID) {
787 elems = xmalloc(datum->n * sizeof *elems);
788 for (i = 0; i < datum->n; i++) {
789 elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
792 return wrap_json("set", json_array_create(elems, datum->n));
797 elems = xmalloc(datum->n * sizeof *elems);
798 for (i = 0; i < datum->n; i++) {
799 elems[i] = json_array_create_2(
800 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
801 ovsdb_atom_to_json(&datum->values[i], type->value_type));
804 return wrap_json("map", json_array_create(elems, datum->n));
809 skip_spaces(const char *p)
811 return p + strspn(p, " ");
815 parse_atom_token(const char **s, enum ovsdb_atomic_type type,
816 union ovsdb_atom *atom)
820 error = ovsdb_token_parse(s, &token);
822 error = ovsdb_atom_from_string(atom, type, token);
830 parse_key_value(const char **s, const struct ovsdb_type *type,
831 union ovsdb_atom *key, union ovsdb_atom *value)
833 const char *start = *s;
836 error = parse_atom_token(s, type->key_type, key);
837 if (!error && type->value_type != OVSDB_TYPE_VOID) {
840 error = parse_atom_token(s, type->value_type, value);
842 error = xasprintf("%s: syntax error at \"%c\" expecting \"=\"",
846 ovsdb_atom_destroy(key, type->key_type);
853 free_key_value(const struct ovsdb_type *type,
854 union ovsdb_atom *key, union ovsdb_atom *value)
856 ovsdb_atom_destroy(key, type->key_type);
857 if (type->value_type != OVSDB_TYPE_VOID) {
858 ovsdb_atom_destroy(value, type->value_type);
862 /* Initializes 'datum' as a datum of the given 'type', parsing its contents
863 * from 's'. The format of 's' is a series of space or comma separated atoms
864 * or, for a map, '='-delimited pairs of atoms. Each atom must in a format
865 * acceptable to ovsdb_atom_from_string(). Optionally, a set may be enclosed
866 * in "[]" or a map in "{}"; for an empty set or map these punctuators are
869 ovsdb_datum_from_string(struct ovsdb_datum *datum,
870 const struct ovsdb_type *type, const char *s)
872 bool is_map = ovsdb_type_is_map(type);
873 struct ovsdb_error *dberror;
878 ovsdb_datum_init_empty(datum);
880 /* Swallow a leading delimiter if there is one. */
882 if (*p == (is_map ? '{' : '[')) {
883 end_delim = is_map ? '}' : ']';
884 p = skip_spaces(p + 1);
887 return xstrdup("use \"{}\" to specify the empty map");
889 return xstrdup("use \"[]\" to specify the empty set");
895 while (*p && *p != end_delim) {
896 union ovsdb_atom key, value;
898 if (ovsdb_token_is_delim(*p)) {
899 error = xasprintf("%s: unexpected \"%c\" parsing %s",
900 s, *p, ovsdb_type_to_english(type));
905 error = parse_key_value(&p, type, &key, &value);
909 ovsdb_datum_add_unsafe(datum, &key, &value, type);
910 free_key_value(type, &key, &value);
912 /* Skip optional white space and comma. */
915 p = skip_spaces(p + 1);
919 if (*p != end_delim) {
920 error = xasprintf("%s: missing \"%c\" at end of data", s, end_delim);
924 p = skip_spaces(p + 1);
926 error = xasprintf("%s: trailing garbage after \"%c\"",
932 if (datum->n < type->n_min) {
933 error = xasprintf("%s: %u %s specified but the minimum number is %u",
934 s, datum->n, is_map ? "pair(s)" : "value(s)",
937 } else if (datum->n > type->n_max) {
938 error = xasprintf("%s: %u %s specified but the maximum number is %u",
939 s, datum->n, is_map ? "pair(s)" : "value(s)",
944 dberror = ovsdb_datum_sort(datum, type);
946 ovsdb_error_destroy(dberror);
947 if (ovsdb_type_is_map(type)) {
948 error = xasprintf("%s: map contains duplicate key", s);
950 error = xasprintf("%s: set contains duplicate value", s);
958 ovsdb_datum_destroy(datum, type);
959 ovsdb_datum_init_empty(datum);
963 /* Appends to 'out' the 'datum' (with the given 'type') in a format acceptable
964 * to ovsdb_datum_from_string(). */
966 ovsdb_datum_to_string(const struct ovsdb_datum *datum,
967 const struct ovsdb_type *type, struct ds *out)
969 bool is_map = ovsdb_type_is_map(type);
972 if (type->n_max > 1 || !datum->n) {
973 ds_put_char(out, is_map ? '{' : '[');
975 for (i = 0; i < datum->n; i++) {
977 ds_put_cstr(out, ", ");
980 ovsdb_atom_to_string(&datum->keys[i], type->key_type, out);
982 ds_put_char(out, '=');
983 ovsdb_atom_to_string(&datum->values[i], type->value_type, out);
986 if (type->n_max > 1 || !datum->n) {
987 ds_put_char(out, is_map ? '}' : ']');
992 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
993 unsigned int n, uint32_t basis)
995 if (type != OVSDB_TYPE_VOID) {
998 for (i = 0; i < n; i++) {
999 basis = ovsdb_atom_hash(&atoms[i], type, basis);
1006 ovsdb_datum_hash(const struct ovsdb_datum *datum,
1007 const struct ovsdb_type *type, uint32_t basis)
1009 basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
1010 basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
1011 basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
1016 atom_arrays_compare_3way(const union ovsdb_atom *a,
1017 const union ovsdb_atom *b,
1018 enum ovsdb_atomic_type type,
1023 for (i = 0; i < n; i++) {
1024 int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
1034 ovsdb_datum_equals(const struct ovsdb_datum *a,
1035 const struct ovsdb_datum *b,
1036 const struct ovsdb_type *type)
1038 return !ovsdb_datum_compare_3way(a, b, type);
1042 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
1043 const struct ovsdb_datum *b,
1044 const struct ovsdb_type *type)
1049 return a->n < b->n ? -1 : 1;
1052 cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
1057 return (type->value_type == OVSDB_TYPE_VOID ? 0
1058 : atom_arrays_compare_3way(a->values, b->values, type->value_type,
1062 /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
1063 * otherwise UINT_MAX. 'key_type' must be the type of the atoms stored in the
1064 * 'keys' array in 'datum'.
1067 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
1068 const union ovsdb_atom *key,
1069 enum ovsdb_atomic_type key_type)
1071 unsigned int low = 0;
1072 unsigned int high = datum->n;
1073 while (low < high) {
1074 unsigned int idx = (low + high) / 2;
1075 int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
1078 } else if (cmp > 0) {
1087 /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
1088 * index within 'datum', otherwise UINT_MAX. 'key_type' must be the type of
1089 * the atoms stored in the 'keys' array in 'datum'. 'value_type' may be the
1090 * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
1093 ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
1094 const union ovsdb_atom *key,
1095 enum ovsdb_atomic_type key_type,
1096 const union ovsdb_atom *value,
1097 enum ovsdb_atomic_type value_type)
1099 unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
1101 && value_type != OVSDB_TYPE_VOID
1102 && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
1108 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
1109 * UINT_MAX. 'type' must be the type of 'a' and 'b', except that
1110 * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
1113 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
1114 const struct ovsdb_datum *b,
1115 const struct ovsdb_type *type)
1117 return ovsdb_datum_find_key_value(b,
1118 &a->keys[i], type->key_type,
1119 a->values ? &a->values[i] : NULL,
1123 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
1125 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
1126 const struct ovsdb_datum *b,
1127 const struct ovsdb_type *type)
1131 for (i = 0; i < a->n; i++) {
1132 if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
1139 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
1141 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
1142 const struct ovsdb_datum *b,
1143 const struct ovsdb_type *type)
1147 for (i = 0; i < a->n; i++) {
1148 if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
1156 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
1157 unsigned int capacity)
1159 a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
1160 if (type->value_type != OVSDB_TYPE_VOID) {
1161 a->values = xrealloc(a->values, capacity * sizeof *a->values);
1165 /* Removes the element with index 'idx' from 'datum', which has type 'type'.
1166 * If 'idx' is not the last element in 'datum', then the removed element is
1167 * replaced by the (former) last element.
1169 * This function does not maintain ovsdb_datum invariants. Use
1170 * ovsdb_datum_sort() to check and restore these invariants. */
1172 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
1173 const struct ovsdb_type *type)
1175 ovsdb_atom_destroy(&datum->keys[idx], type->key_type);
1176 datum->keys[idx] = datum->keys[datum->n - 1];
1177 if (type->value_type != OVSDB_TYPE_VOID) {
1178 ovsdb_atom_destroy(&datum->values[idx], type->value_type);
1179 datum->values[idx] = datum->values[datum->n - 1];
1184 /* Adds the element with the given 'key' and 'value' to 'datum', which must
1185 * have the specified 'type'.
1187 * This function always allocates memory, so it is not an efficient way to add
1188 * a number of elements to a datum.
1190 * This function does not maintain ovsdb_datum invariants. Use
1191 * ovsdb_datum_sort() to check and restore these invariants. (But a datum with
1192 * 0 or 1 elements cannot violate the invariants anyhow.) */
1194 ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
1195 const union ovsdb_atom *key,
1196 const union ovsdb_atom *value,
1197 const struct ovsdb_type *type)
1199 size_t idx = datum->n++;
1200 datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
1201 ovsdb_atom_clone(&datum->keys[idx], key, type->key_type);
1202 if (type->value_type != OVSDB_TYPE_VOID) {
1203 datum->values = xrealloc(datum->values,
1204 datum->n * sizeof *datum->values);
1205 ovsdb_atom_clone(&datum->values[idx], value, type->value_type);
1210 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
1211 const struct ovsdb_type *type, bool replace)
1217 for (bi = 0; bi < b->n; bi++) {
1220 ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type);
1221 if (ai == UINT_MAX) {
1223 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
1225 ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type);
1226 if (type->value_type != OVSDB_TYPE_VOID) {
1227 ovsdb_atom_clone(&a->values[n], &b->values[bi],
1231 } else if (replace && type->value_type != OVSDB_TYPE_VOID) {
1232 ovsdb_atom_destroy(&a->values[ai], type->value_type);
1233 ovsdb_atom_clone(&a->values[ai], &b->values[bi],
1238 struct ovsdb_error *error;
1240 error = ovsdb_datum_sort(a, type);
1246 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
1247 const struct ovsdb_datum *b,
1248 const struct ovsdb_type *b_type)
1250 bool changed = false;
1253 assert(a_type->key_type == b_type->key_type);
1254 assert(a_type->value_type == b_type->value_type
1255 || b_type->value_type == OVSDB_TYPE_VOID);
1257 /* XXX The big-O of this could easily be improved. */
1258 for (i = 0; i < a->n; ) {
1259 unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
1260 if (idx != UINT_MAX) {
1262 ovsdb_datum_remove_unsafe(a, i, a_type);
1268 struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
1273 struct ovsdb_symbol_table {
1277 struct ovsdb_symbol_table *
1278 ovsdb_symbol_table_create(void)
1280 struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
1281 shash_init(&symtab->sh);
1286 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
1289 struct shash_node *node, *next;
1291 SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
1292 struct ovsdb_symbol *symbol = node->data;
1294 shash_delete(&symtab->sh, node);
1296 shash_destroy(&symtab->sh);
1301 struct ovsdb_symbol *
1302 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
1305 return shash_find_data(&symtab->sh, name);
1309 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
1310 const struct uuid *uuid, bool used)
1312 struct ovsdb_symbol *symbol;
1314 assert(!ovsdb_symbol_table_get(symtab, name));
1315 symbol = xmalloc(sizeof *symbol);
1316 symbol->uuid = *uuid;
1317 symbol->used = used;
1318 shash_add(&symtab->sh, name, symbol);
1321 /* Extracts a token from the beginning of 's' and returns a pointer just after
1322 * the token. Stores the token itself into '*outp', which the caller is
1323 * responsible for freeing (with free()).
1325 * If 's[0]' is a delimiter, the returned token is the empty string.
1327 * A token extends from 's' to the first delimiter, as defined by
1328 * ovsdb_token_is_delim(), or until the end of the string. A delimiter can be
1329 * escaped with a backslash, in which case the backslash does not appear in the
1330 * output. Double quotes also cause delimiters to be ignored, but the double
1331 * quotes are retained in the output. (Backslashes inside double quotes are
1332 * not removed, either.)
1335 ovsdb_token_parse(const char **s, char **outp)
1344 for (p = *s; *p != '\0'; ) {
1348 ds_put_char(&out, '\\');
1351 error = xasprintf("%s: backslash at end of argument", *s);
1354 ds_put_char(&out, *p++);
1355 } else if (!in_quotes && ovsdb_token_is_delim(c)) {
1359 ds_put_char(&out, c);
1361 in_quotes = !in_quotes;
1366 error = xasprintf("%s: quoted string extends past end of argument",
1370 *outp = ds_cstr(&out);
1380 /* Returns true if 'c' delimits tokens, or if 'c' is 0, and false otherwise. */
1382 ovsdb_token_is_delim(unsigned char c)
1384 return strchr(":=, []{}", c) != NULL;