lib/ovsdb-data.c

   1 /* Copyright (c) 2009, 2010, 2011 Nicira Networks
   2  *
   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:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   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.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "ovsdb-data.h"
  19
  20 #include <assert.h>
  21 #include <ctype.h>
  22 #include <float.h>
  23 #include <inttypes.h>
  24 #include <limits.h>
  25
  26 #include "dynamic-string.h"
  27 #include "hash.h"
  28 #include "ovsdb-error.h"
  29 #include "json.h"
  30 #include "shash.h"
  31 #include "sort.h"
  32 #include "unicode.h"
  33
  34 static struct json *
  35 wrap_json(const char *name, struct json *wrapped)
  36 {
  37     return json_array_create_2(json_string_create(name), wrapped);
  38 }
  39
  40 /* Initializes 'atom' with the default value of the given 'type'.
  41  *
  42  * The default value for an atom is as defined in ovsdb/SPECS:
  43  *
  44  *      - "integer" or "real": 0
  45  *
  46  *      - "boolean": false
  47  *
  48  *      - "string": "" (the empty string)
  49  *
  50  *      - "uuid": 00000000-0000-0000-0000-000000000000
  51  *
  52  * The caller must eventually arrange for 'atom' to be destroyed (with
  53  * ovsdb_atom_destroy()). */
  54 void
  55 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
  56 {
  57     switch (type) {
  58     case OVSDB_TYPE_VOID:
  59         NOT_REACHED();
  60
  61     case OVSDB_TYPE_INTEGER:
  62         atom->integer = 0;
  63         break;
  64
  65     case OVSDB_TYPE_REAL:
  66         atom->real = 0.0;
  67         break;
  68
  69     case OVSDB_TYPE_BOOLEAN:
  70         atom->boolean = false;
  71         break;
  72
  73     case OVSDB_TYPE_STRING:
  74         atom->string = xmemdup("", 1);
  75         break;
  76
  77     case OVSDB_TYPE_UUID:
  78         uuid_zero(&atom->uuid);
  79         break;
  80
  81     case OVSDB_N_TYPES:
  82     default:
  83         NOT_REACHED();
  84     }
  85 }
  86
  87 /* Returns a read-only atom of the given 'type' that has the default value for
  88  * 'type'.  The caller must not modify or free the returned atom.
  89  *
  90  * See ovsdb_atom_init_default() for an explanation of the default value of an
  91  * atom. */
  92 const union ovsdb_atom *
  93 ovsdb_atom_default(enum ovsdb_atomic_type type)
  94 {
  95     static union ovsdb_atom default_atoms[OVSDB_N_TYPES];
  96     static bool inited;
  97
  98     if (!inited) {
  99         int i;
 100
 101         for (i = 0; i < OVSDB_N_TYPES; i++) {
 102             if (i != OVSDB_TYPE_VOID) {
 103                 ovsdb_atom_init_default(&default_atoms[i], i);
 104             }
 105         }
 106         inited = true;
 107     }
 108
 109     assert(ovsdb_atomic_type_is_valid(type));
 110     return &default_atoms[type];
 111 }
 112
 113 /* Returns true if 'atom', which must have the given 'type', has the default
 114  * value for that type.
 115  *
 116  * See ovsdb_atom_init_default() for an explanation of the default value of an
 117  * atom. */
 118 bool
 119 ovsdb_atom_is_default(const union ovsdb_atom *atom,
 120                       enum ovsdb_atomic_type type)
 121 {
 122     switch (type) {
 123     case OVSDB_TYPE_VOID:
 124         NOT_REACHED();
 125
 126     case OVSDB_TYPE_INTEGER:
 127         return atom->integer == 0;
 128
 129     case OVSDB_TYPE_REAL:
 130         return atom->real == 0.0;
 131
 132     case OVSDB_TYPE_BOOLEAN:
 133         return atom->boolean == false;
 134
 135     case OVSDB_TYPE_STRING:
 136         return atom->string[0] == '\0';
 137
 138     case OVSDB_TYPE_UUID:
 139         return uuid_is_zero(&atom->uuid);
 140
 141     case OVSDB_N_TYPES:
 142     default:
 143         NOT_REACHED();
 144     }
 145 }
 146
 147 /* Initializes 'new' as a copy of 'old', with the given 'type'.
 148  *
 149  * The caller must eventually arrange for 'new' to be destroyed (with
 150  * ovsdb_atom_destroy()). */
 151 void
 152 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
 153                  enum ovsdb_atomic_type type)
 154 {
 155     switch (type) {
 156     case OVSDB_TYPE_VOID:
 157         NOT_REACHED();
 158
 159     case OVSDB_TYPE_INTEGER:
 160         new->integer = old->integer;
 161         break;
 162
 163     case OVSDB_TYPE_REAL:
 164         new->real = old->real;
 165         break;
 166
 167     case OVSDB_TYPE_BOOLEAN:
 168         new->boolean = old->boolean;
 169         break;
 170
 171     case OVSDB_TYPE_STRING:
 172         new->string = xstrdup(old->string);
 173         break;
 174
 175     case OVSDB_TYPE_UUID:
 176         new->uuid = old->uuid;
 177         break;
 178
 179     case OVSDB_N_TYPES:
 180     default:
 181         NOT_REACHED();
 182     }
 183 }
 184
 185 /* Swaps the contents of 'a' and 'b', which need not have the same type. */
 186 void
 187 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
 188 {
 189     union ovsdb_atom tmp = *a;
 190     *a = *b;
 191     *b = tmp;
 192 }
 193
 194 /* Returns a hash value for 'atom', which has the specified 'type', folding
 195  * 'basis' into the calculation. */
 196 uint32_t
 197 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 198                 uint32_t basis)
 199 {
 200     switch (type) {
 201     case OVSDB_TYPE_VOID:
 202         NOT_REACHED();
 203
 204     case OVSDB_TYPE_INTEGER:
 205         return hash_int(atom->integer, basis);
 206
 207     case OVSDB_TYPE_REAL:
 208         return hash_double(atom->real, basis);
 209
 210     case OVSDB_TYPE_BOOLEAN:
 211         return hash_boolean(atom->boolean, basis);
 212
 213     case OVSDB_TYPE_STRING:
 214         return hash_string(atom->string, basis);
 215
 216     case OVSDB_TYPE_UUID:
 217         return hash_int(uuid_hash(&atom->uuid), basis);
 218
 219     case OVSDB_N_TYPES:
 220     default:
 221         NOT_REACHED();
 222     }
 223 }
 224
 225 /* Compares 'a' and 'b', which both have type 'type', and returns a
 226  * strcmp()-like result. */
 227 int
 228 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
 229                         const union ovsdb_atom *b,
 230                         enum ovsdb_atomic_type type)
 231 {
 232     switch (type) {
 233     case OVSDB_TYPE_VOID:
 234         NOT_REACHED();
 235
 236     case OVSDB_TYPE_INTEGER:
 237         return a->integer < b->integer ? -1 : a->integer > b->integer;
 238
 239     case OVSDB_TYPE_REAL:
 240         return a->real < b->real ? -1 : a->real > b->real;
 241
 242     case OVSDB_TYPE_BOOLEAN:
 243         return a->boolean - b->boolean;
 244
 245     case OVSDB_TYPE_STRING:
 246         return strcmp(a->string, b->string);
 247
 248     case OVSDB_TYPE_UUID:
 249         return uuid_compare_3way(&a->uuid, &b->uuid);
 250
 251     case OVSDB_N_TYPES:
 252     default:
 253         NOT_REACHED();
 254     }
 255 }
 256
 257 static struct ovsdb_error *
 258 unwrap_json(const struct json *json, const char *name,
 259             enum json_type value_type, const struct json **value)
 260 {
 261     if (json->type != JSON_ARRAY
 262         || json->u.array.n != 2
 263         || json->u.array.elems[0]->type != JSON_STRING
 264         || (name && strcmp(json->u.array.elems[0]->u.string, name))
 265         || json->u.array.elems[1]->type != value_type)
 266     {
 267         *value = NULL;
 268         return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
 269                                   json_type_to_string(value_type));
 270     }
 271     *value = json->u.array.elems[1];
 272     return NULL;
 273 }
 274
 275 static struct ovsdb_error *
 276 parse_json_pair(const struct json *json,
 277                 const struct json **elem0, const struct json **elem1)
 278 {
 279     if (json->type != JSON_ARRAY || json->u.array.n != 2) {
 280         return ovsdb_syntax_error(json, NULL, "expected 2-element array");
 281     }
 282     *elem0 = json->u.array.elems[0];
 283     *elem1 = json->u.array.elems[1];
 284     return NULL;
 285 }
 286
 287 static struct ovsdb_error * WARN_UNUSED_RESULT
 288 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
 289                       struct ovsdb_symbol_table *symtab)
 290 {
 291     struct ovsdb_error *error0;
 292     const struct json *value;
 293
 294     error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
 295     if (!error0) {
 296         const char *uuid_string = json_string(value);
 297         if (!uuid_from_string(uuid, uuid_string)) {
 298             return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
 299                                       uuid_string);
 300         }
 301     } else if (symtab) {
 302         struct ovsdb_error *error1;
 303
 304         error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
 305         if (!error1) {
 306             const char *name = json_string(value);
 307
 308             ovsdb_error_destroy(error0);
 309             *uuid = ovsdb_symbol_table_insert(symtab, name)->uuid;
 310             return NULL;
 311         }
 312         ovsdb_error_destroy(error1);
 313     }
 314
 315     return error0;
 316 }
 317
 318 static struct ovsdb_error * WARN_UNUSED_RESULT
 319 ovsdb_atom_from_json__(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 320                        const struct json *json,
 321                        struct ovsdb_symbol_table *symtab)
 322 {
 323     switch (type) {
 324     case OVSDB_TYPE_VOID:
 325         NOT_REACHED();
 326
 327     case OVSDB_TYPE_INTEGER:
 328         if (json->type == JSON_INTEGER) {
 329             atom->integer = json->u.integer;
 330             return NULL;
 331         }
 332         break;
 333
 334     case OVSDB_TYPE_REAL:
 335         if (json->type == JSON_INTEGER) {
 336             atom->real = json->u.integer;
 337             return NULL;
 338         } else if (json->type == JSON_REAL) {
 339             atom->real = json->u.real;
 340             return NULL;
 341         }
 342         break;
 343
 344     case OVSDB_TYPE_BOOLEAN:
 345         if (json->type == JSON_TRUE) {
 346             atom->boolean = true;
 347             return NULL;
 348         } else if (json->type == JSON_FALSE) {
 349             atom->boolean = false;
 350             return NULL;
 351         }
 352         break;
 353
 354     case OVSDB_TYPE_STRING:
 355         if (json->type == JSON_STRING) {
 356             atom->string = xstrdup(json->u.string);
 357             return NULL;
 358         }
 359         break;
 360
 361     case OVSDB_TYPE_UUID:
 362         return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
 363
 364     case OVSDB_N_TYPES:
 365     default:
 366         NOT_REACHED();
 367     }
 368
 369     return ovsdb_syntax_error(json, NULL, "expected %s",
 370                               ovsdb_atomic_type_to_string(type));
 371 }
 372
 373 /* Parses 'json' as an atom of the type described by 'base'.  If successful,
 374  * returns NULL and initializes 'atom' with the parsed atom.  On failure,
 375  * returns an error and the contents of 'atom' are indeterminate.  The caller
 376  * is responsible for freeing the error or the atom that is returned.
 377  *
 378  * Violations of constraints expressed by 'base' are treated as errors.
 379  *
 380  * If 'symtab' is nonnull, then named UUIDs in 'symtab' are accepted.  Refer to
 381  * ovsdb/SPECS for information about this, and for the syntax that this
 382  * function accepts. */
 383 struct ovsdb_error *
 384 ovsdb_atom_from_json(union ovsdb_atom *atom,
 385                      const struct ovsdb_base_type *base,
 386                      const struct json *json,
 387                      struct ovsdb_symbol_table *symtab)
 388 {
 389     struct ovsdb_error *error;
 390
 391     error = ovsdb_atom_from_json__(atom, base->type, json, symtab);
 392     if (error) {
 393         return error;
 394     }
 395
 396     error = ovsdb_atom_check_constraints(atom, base);
 397     if (error) {
 398         ovsdb_atom_destroy(atom, base->type);
 399     }
 400     return error;
 401 }
 402
 403 /* Converts 'atom', of the specified 'type', to JSON format, and returns the
 404  * JSON.  The caller is responsible for freeing the returned JSON.
 405  *
 406  * Refer to ovsdb/SPECS for the format of the JSON that this function
 407  * produces. */
 408 struct json *
 409 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
 410 {
 411     switch (type) {
 412     case OVSDB_TYPE_VOID:
 413         NOT_REACHED();
 414
 415     case OVSDB_TYPE_INTEGER:
 416         return json_integer_create(atom->integer);
 417
 418     case OVSDB_TYPE_REAL:
 419         return json_real_create(atom->real);
 420
 421     case OVSDB_TYPE_BOOLEAN:
 422         return json_boolean_create(atom->boolean);
 423
 424     case OVSDB_TYPE_STRING:
 425         return json_string_create(atom->string);
 426
 427     case OVSDB_TYPE_UUID:
 428         return wrap_json("uuid", json_string_create_nocopy(
 429                              xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
 430
 431     case OVSDB_N_TYPES:
 432     default:
 433         NOT_REACHED();
 434     }
 435 }
 436
 437 static char *
 438 ovsdb_atom_from_string__(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 439                          const char *s, struct ovsdb_symbol_table *symtab)
 440 {
 441     switch (type) {
 442     case OVSDB_TYPE_VOID:
 443         NOT_REACHED();
 444
 445     case OVSDB_TYPE_INTEGER: {
 446         long long int integer;
 447         if (!str_to_llong(s, 10, &integer)) {
 448             return xasprintf("\"%s\" is not a valid integer", s);
 449         }
 450         atom->integer = integer;
 451     }
 452         break;
 453
 454     case OVSDB_TYPE_REAL:
 455         if (!str_to_double(s, &atom->real)) {
 456             return xasprintf("\"%s\" is not a valid real number", s);
 457         }
 458         /* Our JSON input routines map negative zero to zero, so do that here
 459          * too for consistency. */
 460         if (atom->real == 0.0) {
 461             atom->real = 0.0;
 462         }
 463         break;
 464
 465     case OVSDB_TYPE_BOOLEAN:
 466         if (!strcmp(s, "true") || !strcmp(s, "yes") || !strcmp(s, "on")
 467             || !strcmp(s, "1")) {
 468             atom->boolean = true;
 469         } else if (!strcmp(s, "false") || !strcmp(s, "no") || !strcmp(s, "off")
 470                    || !strcmp(s, "0")) {
 471             atom->boolean = false;
 472         } else {
 473             return xasprintf("\"%s\" is not a valid boolean "
 474                              "(use \"true\" or \"false\")", s);
 475         }
 476         break;
 477
 478     case OVSDB_TYPE_STRING:
 479         if (*s == '\0') {
 480             return xstrdup("An empty string is not valid as input; "
 481                            "use \"\" to represent the empty string");
 482         } else if (*s == '"') {
 483             size_t s_len = strlen(s);
 484
 485             if (s_len < 2 || s[s_len - 1] != '"') {
 486                 return xasprintf("%s: missing quote at end of "
 487                                  "quoted string", s);
 488             } else if (!json_string_unescape(s + 1, s_len - 2,
 489                                              &atom->string)) {
 490                 char *error = xasprintf("%s: %s", s, atom->string);
 491                 free(atom->string);
 492                 return error;
 493             }
 494         } else {
 495             atom->string = xstrdup(s);
 496         }
 497         break;
 498
 499     case OVSDB_TYPE_UUID:
 500         if (*s == '@') {
 501             atom->uuid = ovsdb_symbol_table_insert(symtab, s)->uuid;
 502         } else if (!uuid_from_string(&atom->uuid, s)) {
 503             return xasprintf("\"%s\" is not a valid UUID", s);
 504         }
 505         break;
 506
 507     case OVSDB_N_TYPES:
 508     default:
 509         NOT_REACHED();
 510     }
 511
 512     return NULL;
 513 }
 514
 515 /* Initializes 'atom' to a value of type 'base' parsed from 's', which takes
 516  * one of the following forms:
 517  *
 518  *      - OVSDB_TYPE_INTEGER: A decimal integer optionally preceded by a sign.
 519  *
 520  *      - OVSDB_TYPE_REAL: A floating-point number in the format accepted by
 521  *        strtod().
 522  *
 523  *      - OVSDB_TYPE_BOOLEAN: "true", "yes", "on", "1" for true, or "false",
 524  *        "no", "off", or "0" for false.
 525  *
 526  *      - OVSDB_TYPE_STRING: A JSON string if it begins with a quote, otherwise
 527  *        an arbitrary string.
 528  *
 529  *      - OVSDB_TYPE_UUID: A UUID in RFC 4122 format.  If 'symtab' is nonnull,
 530  *        then an identifier beginning with '@' is also acceptable.  If the
 531  *        named identifier is already in 'symtab', then the associated UUID is
 532  *        used; otherwise, a new, random UUID is used and added to the symbol
 533  *        table.
 534  *
 535  * Returns a null pointer if successful, otherwise an error message describing
 536  * the problem.  On failure, the contents of 'atom' are indeterminate.  The
 537  * caller is responsible for freeing the atom or the error.
 538  */
 539 char *
 540 ovsdb_atom_from_string(union ovsdb_atom *atom,
 541                        const struct ovsdb_base_type *base, const char *s,
 542                        struct ovsdb_symbol_table *symtab)
 543 {
 544     struct ovsdb_error *error;
 545     char *msg;
 546
 547     msg = ovsdb_atom_from_string__(atom, base->type, s, symtab);
 548     if (msg) {
 549         return msg;
 550     }
 551
 552     error = ovsdb_atom_check_constraints(atom, base);
 553     if (error) {
 554         msg = ovsdb_error_to_string(error);
 555         ovsdb_error_destroy(error);
 556     }
 557     return msg;
 558 }
 559
 560 static bool
 561 string_needs_quotes(const char *s)
 562 {
 563     const char *p = s;
 564     unsigned char c;
 565
 566     c = *p++;
 567     if (!isalpha(c) && c != '_') {
 568         return true;
 569     }
 570
 571     while ((c = *p++) != '\0') {
 572         if (!isalpha(c) && c != '_' && c != '-' && c != '.') {
 573             return true;
 574         }
 575     }
 576
 577     if (!strcmp(s, "true") || !strcmp(s, "false")) {
 578         return true;
 579     }
 580
 581     return false;
 582 }
 583
 584 /* Appends 'atom' (which has the given 'type') to 'out', in a format acceptable
 585  * to ovsdb_atom_from_string().  */
 586 void
 587 ovsdb_atom_to_string(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 588                      struct ds *out)
 589 {
 590     switch (type) {
 591     case OVSDB_TYPE_VOID:
 592         NOT_REACHED();
 593
 594     case OVSDB_TYPE_INTEGER:
 595         ds_put_format(out, "%"PRId64, atom->integer);
 596         break;
 597
 598     case OVSDB_TYPE_REAL:
 599         ds_put_format(out, "%.*g", DBL_DIG, atom->real);
 600         break;
 601
 602     case OVSDB_TYPE_BOOLEAN:
 603         ds_put_cstr(out, atom->boolean ? "true" : "false");
 604         break;
 605
 606     case OVSDB_TYPE_STRING:
 607         if (string_needs_quotes(atom->string)) {
 608             struct json json;
 609
 610             json.type = JSON_STRING;
 611             json.u.string = atom->string;
 612             json_to_ds(&json, 0, out);
 613         } else {
 614             ds_put_cstr(out, atom->string);
 615         }
 616         break;
 617
 618     case OVSDB_TYPE_UUID:
 619         ds_put_format(out, UUID_FMT, UUID_ARGS(&atom->uuid));
 620         break;
 621
 622     case OVSDB_N_TYPES:
 623     default:
 624         NOT_REACHED();
 625     }
 626 }
 627
 628 /* Appends 'atom' (which has the given 'type') to 'out', in a bare string
 629  * format that cannot be parsed uniformly back into a datum but is easier for
 630  * shell scripts, etc., to deal with. */
 631 void
 632 ovsdb_atom_to_bare(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 633                    struct ds *out)
 634 {
 635     if (type == OVSDB_TYPE_STRING) {
 636         ds_put_cstr(out, atom->string);
 637     } else {
 638         ovsdb_atom_to_string(atom, type, out);
 639     }
 640 }
 641
 642 static struct ovsdb_error *
 643 check_string_constraints(const char *s,
 644                          const struct ovsdb_string_constraints *c)
 645 {
 646     size_t n_chars;
 647     char *msg;
 648
 649     msg = utf8_validate(s, &n_chars);
 650     if (msg) {
 651         struct ovsdb_error *error;
 652
 653         error = ovsdb_error("constraint violation",
 654                             "\"%s\" is not a valid UTF-8 string: %s",
 655                             s, msg);
 656         free(msg);
 657         return error;
 658     }
 659
 660     if (n_chars < c->minLen) {
 661         return ovsdb_error(
 662             "constraint violation",
 663             "\"%s\" length %zu is less than minimum allowed "
 664             "length %u", s, n_chars, c->minLen);
 665     } else if (n_chars > c->maxLen) {
 666         return ovsdb_error(
 667             "constraint violation",
 668             "\"%s\" length %zu is greater than maximum allowed "
 669             "length %u", s, n_chars, c->maxLen);
 670     }
 671
 672     return NULL;
 673 }
 674
 675 /* Checks whether 'atom' meets the constraints (if any) defined in 'base'.
 676  * (base->type must specify 'atom''s type.)  Returns a null pointer if the
 677  * constraints are met, otherwise an error that explains the violation.
 678  *
 679  * Checking UUID constraints is deferred to transaction commit time, so this
 680  * function does nothing for UUID constraints. */
 681 struct ovsdb_error *
 682 ovsdb_atom_check_constraints(const union ovsdb_atom *atom,
 683                              const struct ovsdb_base_type *base)
 684 {
 685     if (base->enum_
 686         && ovsdb_datum_find_key(base->enum_, atom, base->type) == UINT_MAX) {
 687         struct ovsdb_error *error;
 688         struct ds actual = DS_EMPTY_INITIALIZER;
 689         struct ds valid = DS_EMPTY_INITIALIZER;
 690
 691         ovsdb_atom_to_string(atom, base->type, &actual);
 692         ovsdb_datum_to_string(base->enum_,
 693                               ovsdb_base_type_get_enum_type(base->type),
 694                               &valid);
 695         error = ovsdb_error("constraint violation",
 696                             "%s is not one of the allowed values (%s)",
 697                             ds_cstr(&actual), ds_cstr(&valid));
 698         ds_destroy(&actual);
 699         ds_destroy(&valid);
 700
 701         return error;
 702     }
 703
 704     switch (base->type) {
 705     case OVSDB_TYPE_VOID:
 706         NOT_REACHED();
 707
 708     case OVSDB_TYPE_INTEGER:
 709         if (atom->integer >= base->u.integer.min
 710             && atom->integer <= base->u.integer.max) {
 711             return NULL;
 712         } else if (base->u.integer.min != INT64_MIN) {
 713             if (base->u.integer.max != INT64_MAX) {
 714                 return ovsdb_error("constraint violation",
 715                                    "%"PRId64" is not in the valid range "
 716                                    "%"PRId64" to %"PRId64" (inclusive)",
 717                                    atom->integer,
 718                                    base->u.integer.min, base->u.integer.max);
 719             } else {
 720                 return ovsdb_error("constraint violation",
 721                                    "%"PRId64" is less than minimum allowed "
 722                                    "value %"PRId64,
 723                                    atom->integer, base->u.integer.min);
 724             }
 725         } else {
 726             return ovsdb_error("constraint violation",
 727                                "%"PRId64" is greater than maximum allowed "
 728                                "value %"PRId64,
 729                                atom->integer, base->u.integer.max);
 730         }
 731         NOT_REACHED();
 732
 733     case OVSDB_TYPE_REAL:
 734         if (atom->real >= base->u.real.min && atom->real <= base->u.real.max) {
 735             return NULL;
 736         } else if (base->u.real.min != -DBL_MAX) {
 737             if (base->u.real.max != DBL_MAX) {
 738                 return ovsdb_error("constraint violation",
 739                                    "%.*g is not in the valid range "
 740                                    "%.*g to %.*g (inclusive)",
 741                                    DBL_DIG, atom->real,
 742                                    DBL_DIG, base->u.real.min,
 743                                    DBL_DIG, base->u.real.max);
 744             } else {
 745                 return ovsdb_error("constraint violation",
 746                                    "%.*g is less than minimum allowed "
 747                                    "value %.*g",
 748                                    DBL_DIG, atom->real,
 749                                    DBL_DIG, base->u.real.min);
 750             }
 751         } else {
 752             return ovsdb_error("constraint violation",
 753                                "%.*g is greater than maximum allowed "
 754                                "value %.*g",
 755                                DBL_DIG, atom->real,
 756                                DBL_DIG, base->u.real.max);
 757         }
 758         NOT_REACHED();
 759
 760     case OVSDB_TYPE_BOOLEAN:
 761         return NULL;
 762
 763     case OVSDB_TYPE_STRING:
 764         return check_string_constraints(atom->string, &base->u.string);
 765
 766     case OVSDB_TYPE_UUID:
 767         return NULL;
 768
 769     case OVSDB_N_TYPES:
 770     default:
 771         NOT_REACHED();
 772     }
 773 }
 774 \f
 775 static union ovsdb_atom *
 776 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
 777 {
 778     if (type != OVSDB_TYPE_VOID && n) {
 779         union ovsdb_atom *atoms;
 780         unsigned int i;
 781
 782         atoms = xmalloc(n * sizeof *atoms);
 783         for (i = 0; i < n; i++) {
 784             ovsdb_atom_init_default(&atoms[i], type);
 785         }
 786         return atoms;
 787     } else {
 788         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 789          * treated as xmalloc(1). */
 790         return NULL;
 791     }
 792 }
 793
 794 /* Initializes 'datum' as an empty datum.  (An empty datum can be treated as
 795  * any type.) */
 796 void
 797 ovsdb_datum_init_empty(struct ovsdb_datum *datum)
 798 {
 799     datum->n = 0;
 800     datum->keys = NULL;
 801     datum->values = NULL;
 802 }
 803
 804 /* Initializes 'datum' as a datum that has the default value for 'type'.
 805  *
 806  * The default value for a particular type is as defined in ovsdb/SPECS:
 807  *
 808  *    - If n_min is 0, then the default value is the empty set (or map).
 809  *
 810  *    - If n_min is 1, the default value is a single value or a single
 811  *      key-value pair, whose key and value are the defaults for their
 812  *      atomic types.  (See ovsdb_atom_init_default() for details.)
 813  *
 814  *    - n_min > 1 is invalid.  See ovsdb_type_is_valid().
 815  */
 816 void
 817 ovsdb_datum_init_default(struct ovsdb_datum *datum,
 818                          const struct ovsdb_type *type)
 819 {
 820     datum->n = type->n_min;
 821     datum->keys = alloc_default_atoms(type->key.type, datum->n);
 822     datum->values = alloc_default_atoms(type->value.type, datum->n);
 823 }
 824
 825 /* Returns a read-only datum of the given 'type' that has the default value for
 826  * 'type'.  The caller must not modify or free the returned datum.
 827  *
 828  * See ovsdb_datum_init_default() for an explanation of the default value of a
 829  * datum. */
 830 const struct ovsdb_datum *
 831 ovsdb_datum_default(const struct ovsdb_type *type)
 832 {
 833     if (type->n_min == 0) {
 834         static const struct ovsdb_datum empty;
 835         return &empty;
 836     } else if (type->n_min == 1) {
 837         static struct ovsdb_datum default_data[OVSDB_N_TYPES][OVSDB_N_TYPES];
 838         struct ovsdb_datum *d;
 839         int kt = type->key.type;
 840         int vt = type->value.type;
 841
 842         assert(ovsdb_type_is_valid(type));
 843
 844         d = &default_data[kt][vt];
 845         if (!d->n) {
 846             d->n = 1;
 847             d->keys = (union ovsdb_atom *) ovsdb_atom_default(kt);
 848             if (vt != OVSDB_TYPE_VOID) {
 849                 d->values = (union ovsdb_atom *) ovsdb_atom_default(vt);
 850             }
 851         }
 852         return d;
 853     } else {
 854         NOT_REACHED();
 855     }
 856 }
 857
 858 /* Returns true if 'datum', which must have the given 'type', has the default
 859  * value for that type.
 860  *
 861  * See ovsdb_datum_init_default() for an explanation of the default value of a
 862  * datum. */
 863 bool
 864 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
 865                        const struct ovsdb_type *type)
 866 {
 867     size_t i;
 868
 869     if (datum->n != type->n_min) {
 870         return false;
 871     }
 872     for (i = 0; i < datum->n; i++) {
 873         if (!ovsdb_atom_is_default(&datum->keys[i], type->key.type)) {
 874             return false;
 875         }
 876         if (type->value.type != OVSDB_TYPE_VOID
 877             && !ovsdb_atom_is_default(&datum->values[i], type->value.type)) {
 878             return false;
 879         }
 880     }
 881
 882     return true;
 883 }
 884
 885 static union ovsdb_atom *
 886 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 887 {
 888     if (type != OVSDB_TYPE_VOID && n) {
 889         union ovsdb_atom *new;
 890         unsigned int i;
 891
 892         new = xmalloc(n * sizeof *new);
 893         for (i = 0; i < n; i++) {
 894             ovsdb_atom_clone(&new[i], &old[i], type);
 895         }
 896         return new;
 897     } else {
 898         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 899          * treated as xmalloc(1). */
 900         return NULL;
 901     }
 902 }
 903
 904 /* Initializes 'new' as a copy of 'old', with the given 'type'.
 905  *
 906  * The caller must eventually arrange for 'new' to be destroyed (with
 907  * ovsdb_datum_destroy()). */
 908 void
 909 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
 910                   const struct ovsdb_type *type)
 911 {
 912     unsigned int n = old->n;
 913     new->n = n;
 914     new->keys = clone_atoms(old->keys, type->key.type, n);
 915     new->values = clone_atoms(old->values, type->value.type, n);
 916 }
 917
 918 static void
 919 free_data(enum ovsdb_atomic_type type,
 920           union ovsdb_atom *atoms, size_t n_atoms)
 921 {
 922     if (ovsdb_atom_needs_destruction(type)) {
 923         unsigned int i;
 924         for (i = 0; i < n_atoms; i++) {
 925             ovsdb_atom_destroy(&atoms[i], type);
 926         }
 927     }
 928     free(atoms);
 929 }
 930
 931 /* Frees the data owned by 'datum', which must have the given 'type'.
 932  *
 933  * This does not actually call free(datum).  If necessary, the caller must be
 934  * responsible for that. */
 935 void
 936 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 937 {
 938     free_data(type->key.type, datum->keys, datum->n);
 939     free_data(type->value.type, datum->values, datum->n);
 940 }
 941
 942 /* Swaps the contents of 'a' and 'b', which need not have the same type. */
 943 void
 944 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
 945 {
 946     struct ovsdb_datum tmp = *a;
 947     *a = *b;
 948     *b = tmp;
 949 }
 950
 951 struct ovsdb_datum_sort_cbdata {
 952     enum ovsdb_atomic_type key_type;
 953     enum ovsdb_atomic_type value_type;
 954     struct ovsdb_datum *datum;
 955 };
 956
 957 static int
 958 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
 959 {
 960     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 961     int retval;
 962
 963     retval = ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
 964                                      &cbdata->datum->keys[b],
 965                                      cbdata->key_type);
 966     if (retval || cbdata->value_type == OVSDB_TYPE_VOID) {
 967         return retval;
 968     }
 969
 970     return ovsdb_atom_compare_3way(&cbdata->datum->values[a],
 971                                    &cbdata->datum->values[b],
 972                                    cbdata->value_type);
 973 }
 974
 975 static void
 976 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
 977 {
 978     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 979
 980     ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
 981     if (cbdata->datum->values) {
 982         ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
 983     }
 984 }
 985
 986 static void
 987 ovsdb_datum_sort__(struct ovsdb_datum *datum, enum ovsdb_atomic_type key_type,
 988                    enum ovsdb_atomic_type value_type)
 989 {
 990     struct ovsdb_datum_sort_cbdata cbdata;
 991
 992     cbdata.key_type = key_type;
 993     cbdata.value_type = value_type;
 994     cbdata.datum = datum;
 995     sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
 996          &cbdata);
 997 }
 998
 999 /* The keys in an ovsdb_datum must be unique and in sorted order.  Most
1000  * functions that modify an ovsdb_datum maintain these invariants.  For those
1001  * that don't, this function checks and restores these invariants for 'datum',
1002  * whose keys are of type 'key_type'.
1003  *
1004  * This function returns NULL if successful, otherwise an error message.  The
1005  * caller must free the returned error when it is no longer needed.  On error,
1006  * 'datum' is sorted but not unique. */
1007 struct ovsdb_error *
1008 ovsdb_datum_sort(struct ovsdb_datum *datum, enum ovsdb_atomic_type key_type)
1009 {
1010     size_t i;
1011
1012     if (datum->n < 2) {
1013         return NULL;
1014     }
1015
1016     ovsdb_datum_sort__(datum, key_type, OVSDB_TYPE_VOID);
1017
1018     for (i = 0; i < datum->n - 1; i++) {
1019         if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
1020                               key_type)) {
1021             if (datum->values) {
1022                 return ovsdb_error(NULL, "map contains duplicate key");
1023             } else {
1024                 return ovsdb_error(NULL, "set contains duplicate");
1025             }
1026         }
1027     }
1028     return NULL;
1029 }
1030
1031 /* This function is the same as ovsdb_datum_sort(), except that the caller
1032  * knows that 'datum' is unique.  The operation therefore "cannot fail", so
1033  * this function assert-fails if it actually does. */
1034 void
1035 ovsdb_datum_sort_assert(struct ovsdb_datum *datum,
1036                         enum ovsdb_atomic_type key_type)
1037 {
1038     struct ovsdb_error *error = ovsdb_datum_sort(datum, key_type);
1039     if (error) {
1040         NOT_REACHED();
1041     }
1042 }
1043
1044 /* This is similar to ovsdb_datum_sort(), except that it drops duplicate keys
1045  * instead of reporting an error.  In a map type, the smallest value among a
1046  * group of duplicate pairs is retained and the others are dropped.
1047  *
1048  * Returns the number of keys (or pairs) that were dropped. */
1049 size_t
1050 ovsdb_datum_sort_unique(struct ovsdb_datum *datum,
1051                         enum ovsdb_atomic_type key_type,
1052                         enum ovsdb_atomic_type value_type)
1053 {
1054     size_t src, dst;
1055
1056     if (datum->n < 2) {
1057         return 0;
1058     }
1059
1060     ovsdb_datum_sort__(datum, key_type, value_type);
1061
1062     dst = 1;
1063     for (src = 1; src < datum->n; src++) {
1064         if (ovsdb_atom_equals(&datum->keys[src], &datum->keys[dst - 1],
1065                               key_type)) {
1066             ovsdb_atom_destroy(&datum->keys[src], key_type);
1067             if (value_type != OVSDB_TYPE_VOID) {
1068                 ovsdb_atom_destroy(&datum->values[src], value_type);
1069             }
1070         } else {
1071             if (src != dst) {
1072                 datum->keys[dst] = datum->keys[src];
1073                 if (value_type != OVSDB_TYPE_VOID) {
1074                     datum->values[dst] = datum->values[src];
1075                 }
1076             }
1077             dst++;
1078         }
1079     }
1080     datum->n = dst;
1081     return datum->n - src;
1082 }
1083
1084 /* Checks that each of the atoms in 'datum' conforms to the constraints
1085  * specified by its 'type'.  Returns an error if a constraint is violated,
1086  * otherwise a null pointer.
1087  *
1088  * This function is not commonly useful because the most ordinary way to obtain
1089  * a datum is ultimately via ovsdb_atom_from_string() or
1090  * ovsdb_atom_from_json(), which check constraints themselves. */
1091 struct ovsdb_error *
1092 ovsdb_datum_check_constraints(const struct ovsdb_datum *datum,
1093                               const struct ovsdb_type *type)
1094 {
1095     struct ovsdb_error *error;
1096     unsigned int i;
1097
1098     for (i = 0; i < datum->n; i++) {
1099         error = ovsdb_atom_check_constraints(&datum->keys[i], &type->key);
1100         if (error) {
1101             return error;
1102         }
1103     }
1104
1105     if (type->value.type != OVSDB_TYPE_VOID) {
1106         for (i = 0; i < datum->n; i++) {
1107             error = ovsdb_atom_check_constraints(&datum->values[i],
1108                                                  &type->value);
1109             if (error) {
1110                 return error;
1111             }
1112         }
1113     }
1114
1115     return NULL;
1116 }
1117
1118 static struct ovsdb_error *
1119 ovsdb_datum_from_json__(struct ovsdb_datum *datum,
1120                         const struct ovsdb_type *type,
1121                         const struct json *json,
1122                         struct ovsdb_symbol_table *symtab)
1123 {
1124     struct ovsdb_error *error;
1125
1126     if (ovsdb_type_is_map(type)
1127         || (json->type == JSON_ARRAY
1128             && json->u.array.n > 0
1129             && json->u.array.elems[0]->type == JSON_STRING
1130             && !strcmp(json->u.array.elems[0]->u.string, "set"))) {
1131         bool is_map = ovsdb_type_is_map(type);
1132         const char *class = is_map ? "map" : "set";
1133         const struct json *inner;
1134         unsigned int i;
1135         size_t n;
1136
1137         error = unwrap_json(json, class, JSON_ARRAY, &inner);
1138         if (error) {
1139             return error;
1140         }
1141
1142         n = inner->u.array.n;
1143         if (n < type->n_min || n > type->n_max) {
1144             return ovsdb_syntax_error(json, NULL, "%s must have %u to "
1145                                       "%u members but %zu are present",
1146                                       class, type->n_min, type->n_max, n);
1147         }
1148
1149         datum->n = 0;
1150         datum->keys = xmalloc(n * sizeof *datum->keys);
1151         datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
1152         for (i = 0; i < n; i++) {
1153             const struct json *element = inner->u.array.elems[i];
1154             const struct json *key = NULL;
1155             const struct json *value = NULL;
1156
1157             if (!is_map) {
1158                 key = element;
1159             } else {
1160                 error = parse_json_pair(element, &key, &value);
1161                 if (error) {
1162                     goto error;
1163                 }
1164             }
1165
1166             error = ovsdb_atom_from_json(&datum->keys[i], &type->key,
1167                                          key, symtab);
1168             if (error) {
1169                 goto error;
1170             }
1171
1172             if (is_map) {
1173                 error = ovsdb_atom_from_json(&datum->values[i],
1174                                              &type->value, value, symtab);
1175                 if (error) {
1176                     ovsdb_atom_destroy(&datum->keys[i], type->key.type);
1177                     goto error;
1178                 }
1179             }
1180
1181             datum->n++;
1182         }
1183         return NULL;
1184
1185     error:
1186         ovsdb_datum_destroy(datum, type);
1187         return error;
1188     } else {
1189         datum->n = 1;
1190         datum->keys = xmalloc(sizeof *datum->keys);
1191         datum->values = NULL;
1192
1193         error = ovsdb_atom_from_json(&datum->keys[0], &type->key,
1194                                      json, symtab);
1195         if (error) {
1196             free(datum->keys);
1197         }
1198         return error;
1199     }
1200 }
1201
1202 /* Parses 'json' as a datum of the type described by 'type'.  If successful,
1203  * returns NULL and initializes 'datum' with the parsed datum.  On failure,
1204  * returns an error and the contents of 'datum' are indeterminate.  The caller
1205  * is responsible for freeing the error or the datum that is returned.
1206  *
1207  * Violations of constraints expressed by 'type' are treated as errors.
1208  *
1209  * If 'symtab' is nonnull, then named UUIDs in 'symtab' are accepted.  Refer to
1210  * ovsdb/SPECS for information about this, and for the syntax that this
1211  * function accepts. */
1212 struct ovsdb_error *
1213 ovsdb_datum_from_json(struct ovsdb_datum *datum,
1214                       const struct ovsdb_type *type,
1215                       const struct json *json,
1216                       struct ovsdb_symbol_table *symtab)
1217 {
1218     struct ovsdb_error *error;
1219
1220     error = ovsdb_datum_from_json__(datum, type, json, symtab);
1221     if (error) {
1222         return error;
1223     }
1224
1225     error = ovsdb_datum_sort(datum, type->key.type);
1226     if (error) {
1227         ovsdb_datum_destroy(datum, type);
1228     }
1229     return error;
1230 }
1231
1232 /* Converts 'datum', of the specified 'type', to JSON format, and returns the
1233  * JSON.  The caller is responsible for freeing the returned JSON.
1234  *
1235  * 'type' constraints on datum->n are ignored.
1236  *
1237  * Refer to ovsdb/SPECS for the format of the JSON that this function
1238  * produces. */
1239 struct json *
1240 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
1241                     const struct ovsdb_type *type)
1242 {
1243     if (datum->n == 1 && !ovsdb_type_is_map(type)) {
1244         return ovsdb_atom_to_json(&datum->keys[0], type->key.type);
1245     } else if (type->value.type == OVSDB_TYPE_VOID) {
1246         struct json **elems;
1247         size_t i;
1248
1249         elems = xmalloc(datum->n * sizeof *elems);
1250         for (i = 0; i < datum->n; i++) {
1251             elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key.type);
1252         }
1253
1254         return wrap_json("set", json_array_create(elems, datum->n));
1255     } else {
1256         struct json **elems;
1257         size_t i;
1258
1259         elems = xmalloc(datum->n * sizeof *elems);
1260         for (i = 0; i < datum->n; i++) {
1261             elems[i] = json_array_create_2(
1262                 ovsdb_atom_to_json(&datum->keys[i], type->key.type),
1263                 ovsdb_atom_to_json(&datum->values[i], type->value.type));
1264         }
1265
1266         return wrap_json("map", json_array_create(elems, datum->n));
1267     }
1268 }
1269
1270 static const char *
1271 skip_spaces(const char *p)
1272 {
1273     while (isspace((unsigned char) *p)) {
1274         p++;
1275     }
1276     return p;
1277 }
1278
1279 static char *
1280 parse_atom_token(const char **s, const struct ovsdb_base_type *base,
1281                  union ovsdb_atom *atom, struct ovsdb_symbol_table *symtab)
1282 {
1283     char *token, *error;
1284
1285     error = ovsdb_token_parse(s, &token);
1286     if (!error) {
1287         error = ovsdb_atom_from_string(atom, base, token, symtab);
1288         free(token);
1289     }
1290     return error;
1291 }
1292
1293 static char *
1294 parse_key_value(const char **s, const struct ovsdb_type *type,
1295                 union ovsdb_atom *key, union ovsdb_atom *value,
1296                 struct ovsdb_symbol_table *symtab)
1297 {
1298     const char *start = *s;
1299     char *error;
1300
1301     error = parse_atom_token(s, &type->key, key, symtab);
1302     if (!error && type->value.type != OVSDB_TYPE_VOID) {
1303         *s = skip_spaces(*s);
1304         if (**s == '=') {
1305             (*s)++;
1306             *s = skip_spaces(*s);
1307             error = parse_atom_token(s, &type->value, value, symtab);
1308         } else {
1309             error = xasprintf("%s: syntax error at \"%c\" expecting \"=\"",
1310                               start, **s);
1311         }
1312         if (error) {
1313             ovsdb_atom_destroy(key, type->key.type);
1314         }
1315     }
1316     return error;
1317 }
1318
1319 static void
1320 free_key_value(const struct ovsdb_type *type,
1321                union ovsdb_atom *key, union ovsdb_atom *value)
1322 {
1323     ovsdb_atom_destroy(key, type->key.type);
1324     if (type->value.type != OVSDB_TYPE_VOID) {
1325         ovsdb_atom_destroy(value, type->value.type);
1326     }
1327 }
1328
1329 /* Initializes 'datum' as a datum of the given 'type', parsing its contents
1330  * from 's'.  The format of 's' is a series of space or comma separated atoms
1331  * or, for a map, '='-delimited pairs of atoms.  Each atom must in a format
1332  * acceptable to ovsdb_atom_from_string().  Optionally, a set may be enclosed
1333  * in "[]" or a map in "{}"; for an empty set or map these punctuators are
1334  * required.
1335  *
1336  * Optionally, a symbol table may be supplied as 'symtab'.  It is passed to
1337  * ovsdb_atom_to_string(). */
1338 char *
1339 ovsdb_datum_from_string(struct ovsdb_datum *datum,
1340                         const struct ovsdb_type *type, const char *s,
1341                         struct ovsdb_symbol_table *symtab)
1342 {
1343     bool is_map = ovsdb_type_is_map(type);
1344     struct ovsdb_error *dberror;
1345     const char *p;
1346     int end_delim;
1347     char *error;
1348
1349     ovsdb_datum_init_empty(datum);
1350
1351     /* Swallow a leading delimiter if there is one. */
1352     p = skip_spaces(s);
1353     if (*p == (is_map ? '{' : '[')) {
1354         end_delim = is_map ? '}' : ']';
1355         p = skip_spaces(p + 1);
1356     } else if (!*p) {
1357         if (is_map) {
1358             return xstrdup("use \"{}\" to specify the empty map");
1359         } else {
1360             return xstrdup("use \"[]\" to specify the empty set");
1361         }
1362     } else {
1363         end_delim = 0;
1364     }
1365
1366     while (*p && *p != end_delim) {
1367         union ovsdb_atom key, value;
1368
1369         if (ovsdb_token_is_delim(*p)) {
1370             error = xasprintf("%s: unexpected \"%c\" parsing %s",
1371                               s, *p, ovsdb_type_to_english(type));
1372             goto error;
1373         }
1374
1375         /* Add to datum. */
1376         error = parse_key_value(&p, type, &key, &value, symtab);
1377         if (error) {
1378             goto error;
1379         }
1380         ovsdb_datum_add_unsafe(datum, &key, &value, type);
1381         free_key_value(type, &key, &value);
1382
1383         /* Skip optional white space and comma. */
1384         p = skip_spaces(p);
1385         if (*p == ',') {
1386             p = skip_spaces(p + 1);
1387         }
1388     }
1389
1390     if (*p != end_delim) {
1391         error = xasprintf("%s: missing \"%c\" at end of data", s, end_delim);
1392         goto error;
1393     }
1394     if (end_delim) {
1395         p = skip_spaces(p + 1);
1396         if (*p) {
1397             error = xasprintf("%s: trailing garbage after \"%c\"",
1398                               s, end_delim);
1399             goto error;
1400         }
1401     }
1402
1403     if (datum->n < type->n_min) {
1404         error = xasprintf("%s: %u %s specified but the minimum number is %u",
1405                           s, datum->n, is_map ? "pair(s)" : "value(s)",
1406                           type->n_min);
1407         goto error;
1408     } else if (datum->n > type->n_max) {
1409         error = xasprintf("%s: %u %s specified but the maximum number is %u",
1410                           s, datum->n, is_map ? "pair(s)" : "value(s)",
1411             type->n_max);
1412         goto error;
1413     }
1414
1415     dberror = ovsdb_datum_sort(datum, type->key.type);
1416     if (dberror) {
1417         ovsdb_error_destroy(dberror);
1418         if (ovsdb_type_is_map(type)) {
1419             error = xasprintf("%s: map contains duplicate key", s);
1420         } else {
1421             error = xasprintf("%s: set contains duplicate value", s);
1422         }
1423         goto error;
1424     }
1425
1426     return NULL;
1427
1428 error:
1429     ovsdb_datum_destroy(datum, type);
1430     ovsdb_datum_init_empty(datum);
1431     return error;
1432 }
1433
1434 /* Appends to 'out' the 'datum' (with the given 'type') in a format acceptable
1435  * to ovsdb_datum_from_string(). */
1436 void
1437 ovsdb_datum_to_string(const struct ovsdb_datum *datum,
1438                       const struct ovsdb_type *type, struct ds *out)
1439 {
1440     bool is_map = ovsdb_type_is_map(type);
1441     size_t i;
1442
1443     if (type->n_max > 1 || !datum->n) {
1444         ds_put_char(out, is_map ? '{' : '[');
1445     }
1446     for (i = 0; i < datum->n; i++) {
1447         if (i > 0) {
1448             ds_put_cstr(out, ", ");
1449         }
1450
1451         ovsdb_atom_to_string(&datum->keys[i], type->key.type, out);
1452         if (is_map) {
1453             ds_put_char(out, '=');
1454             ovsdb_atom_to_string(&datum->values[i], type->value.type, out);
1455         }
1456     }
1457     if (type->n_max > 1 || !datum->n) {
1458         ds_put_char(out, is_map ? '}' : ']');
1459     }
1460 }
1461
1462 /* Appends to 'out' the 'datum' (with the given 'type') in a bare string format
1463  * that cannot be parsed uniformly back into a datum but is easier for shell
1464  * scripts, etc., to deal with. */
1465 void
1466 ovsdb_datum_to_bare(const struct ovsdb_datum *datum,
1467                     const struct ovsdb_type *type, struct ds *out)
1468 {
1469     bool is_map = ovsdb_type_is_map(type);
1470     size_t i;
1471
1472     for (i = 0; i < datum->n; i++) {
1473         if (i > 0) {
1474             ds_put_cstr(out, " ");
1475         }
1476
1477         ovsdb_atom_to_bare(&datum->keys[i], type->key.type, out);
1478         if (is_map) {
1479             ds_put_char(out, '=');
1480             ovsdb_atom_to_bare(&datum->values[i], type->value.type, out);
1481         }
1482     }
1483 }
1484
1485 /* Initializes 'datum' as a string-to-string map whose contents are taken from
1486  * 'sh'.  Destroys 'sh'. */
1487 void
1488 ovsdb_datum_from_shash(struct ovsdb_datum *datum, struct shash *sh)
1489 {
1490     struct shash_node *node, *next;
1491     size_t i;
1492
1493     datum->n = shash_count(sh);
1494     datum->keys = xmalloc(datum->n * sizeof *datum->keys);
1495     datum->values = xmalloc(datum->n * sizeof *datum->values);
1496
1497     i = 0;
1498     SHASH_FOR_EACH_SAFE (node, next, sh) {
1499         datum->keys[i].string = node->name;
1500         datum->values[i].string = node->data;
1501         shash_steal(sh, node);
1502         i++;
1503     }
1504     assert(i == datum->n);
1505
1506     shash_destroy(sh);
1507     ovsdb_datum_sort_unique(datum, OVSDB_TYPE_STRING, OVSDB_TYPE_STRING);
1508 }
1509
1510 static uint32_t
1511 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
1512            unsigned int n, uint32_t basis)
1513 {
1514     if (type != OVSDB_TYPE_VOID) {
1515         unsigned int i;
1516
1517         for (i = 0; i < n; i++) {
1518             basis = ovsdb_atom_hash(&atoms[i], type, basis);
1519         }
1520     }
1521     return basis;
1522 }
1523
1524 uint32_t
1525 ovsdb_datum_hash(const struct ovsdb_datum *datum,
1526                  const struct ovsdb_type *type, uint32_t basis)
1527 {
1528     basis = hash_atoms(type->key.type, datum->keys, datum->n, basis);
1529     basis ^= (type->key.type << 24) | (type->value.type << 16) | datum->n;
1530     basis = hash_atoms(type->value.type, datum->values, datum->n, basis);
1531     return basis;
1532 }
1533
1534 static int
1535 atom_arrays_compare_3way(const union ovsdb_atom *a,
1536                          const union ovsdb_atom *b,
1537                          enum ovsdb_atomic_type type,
1538                          size_t n)
1539 {
1540     unsigned int i;
1541
1542     for (i = 0; i < n; i++) {
1543         int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
1544         if (cmp) {
1545             return cmp;
1546         }
1547     }
1548
1549     return 0;
1550 }
1551
1552 bool
1553 ovsdb_datum_equals(const struct ovsdb_datum *a,
1554                    const struct ovsdb_datum *b,
1555                    const struct ovsdb_type *type)
1556 {
1557     return !ovsdb_datum_compare_3way(a, b, type);
1558 }
1559
1560 int
1561 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
1562                          const struct ovsdb_datum *b,
1563                          const struct ovsdb_type *type)
1564 {
1565     int cmp;
1566
1567     if (a->n != b->n) {
1568         return a->n < b->n ? -1 : 1;
1569     }
1570
1571     cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key.type, a->n);
1572     if (cmp) {
1573         return cmp;
1574     }
1575
1576     return (type->value.type == OVSDB_TYPE_VOID ? 0
1577             : atom_arrays_compare_3way(a->values, b->values, type->value.type,
1578                                        a->n));
1579 }
1580
1581 /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
1582  * otherwise UINT_MAX.  'key.type' must be the type of the atoms stored in the
1583  * 'keys' array in 'datum'.
1584  */
1585 unsigned int
1586 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
1587                      const union ovsdb_atom *key,
1588                      enum ovsdb_atomic_type key_type)
1589 {
1590     unsigned int low = 0;
1591     unsigned int high = datum->n;
1592     while (low < high) {
1593         unsigned int idx = (low + high) / 2;
1594         int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
1595         if (cmp < 0) {
1596             high = idx;
1597         } else if (cmp > 0) {
1598             low = idx + 1;
1599         } else {
1600             return idx;
1601         }
1602     }
1603     return UINT_MAX;
1604 }
1605
1606 /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
1607  * index within 'datum', otherwise UINT_MAX.  'key.type' must be the type of
1608  * the atoms stored in the 'keys' array in 'datum'.  'value_type' may be the
1609  * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
1610  */
1611 unsigned int
1612 ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
1613                            const union ovsdb_atom *key,
1614                            enum ovsdb_atomic_type key_type,
1615                            const union ovsdb_atom *value,
1616                            enum ovsdb_atomic_type value_type)
1617 {
1618     unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
1619     if (idx != UINT_MAX
1620         && value_type != OVSDB_TYPE_VOID
1621         && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
1622         idx = UINT_MAX;
1623     }
1624     return idx;
1625 }
1626
1627 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
1628  * UINT_MAX.  'type' must be the type of 'a' and 'b', except that
1629  * type->value.type may be set to OVSDB_TYPE_VOID to compare keys but not
1630  * values. */
1631 static unsigned int
1632 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
1633                  const struct ovsdb_datum *b,
1634                  const struct ovsdb_type *type)
1635 {
1636     return ovsdb_datum_find_key_value(b,
1637                                       &a->keys[i], type->key.type,
1638                                       a->values ? &a->values[i] : NULL,
1639                                       type->value.type);
1640 }
1641
1642 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
1643 bool
1644 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
1645                          const struct ovsdb_datum *b,
1646                          const struct ovsdb_type *type)
1647 {
1648     size_t i;
1649
1650     for (i = 0; i < a->n; i++) {
1651         if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
1652             return false;
1653         }
1654     }
1655     return true;
1656 }
1657
1658 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
1659 bool
1660 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
1661                          const struct ovsdb_datum *b,
1662                          const struct ovsdb_type *type)
1663 {
1664     size_t i;
1665
1666     for (i = 0; i < a->n; i++) {
1667         if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
1668             return false;
1669         }
1670     }
1671     return true;
1672 }
1673
1674 static void
1675 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
1676                        unsigned int capacity)
1677 {
1678     a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
1679     if (type->value.type != OVSDB_TYPE_VOID) {
1680         a->values = xrealloc(a->values, capacity * sizeof *a->values);
1681     }
1682 }
1683
1684 /* Removes the element with index 'idx' from 'datum', which has type 'type'.
1685  * If 'idx' is not the last element in 'datum', then the removed element is
1686  * replaced by the (former) last element.
1687  *
1688  * This function does not maintain ovsdb_datum invariants.  Use
1689  * ovsdb_datum_sort() to check and restore these invariants. */
1690 void
1691 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
1692                           const struct ovsdb_type *type)
1693 {
1694     ovsdb_atom_destroy(&datum->keys[idx], type->key.type);
1695     datum->keys[idx] = datum->keys[datum->n - 1];
1696     if (type->value.type != OVSDB_TYPE_VOID) {
1697         ovsdb_atom_destroy(&datum->values[idx], type->value.type);
1698         datum->values[idx] = datum->values[datum->n - 1];
1699     }
1700     datum->n--;
1701 }
1702
1703 /* Adds the element with the given 'key' and 'value' to 'datum', which must
1704  * have the specified 'type'.
1705  *
1706  * This function always allocates memory, so it is not an efficient way to add
1707  * a number of elements to a datum.
1708  *
1709  * This function does not maintain ovsdb_datum invariants.  Use
1710  * ovsdb_datum_sort() to check and restore these invariants.  (But a datum with
1711  * 0 or 1 elements cannot violate the invariants anyhow.) */
1712 void
1713 ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
1714                        const union ovsdb_atom *key,
1715                        const union ovsdb_atom *value,
1716                        const struct ovsdb_type *type)
1717 {
1718     size_t idx = datum->n++;
1719     datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
1720     ovsdb_atom_clone(&datum->keys[idx], key, type->key.type);
1721     if (type->value.type != OVSDB_TYPE_VOID) {
1722         datum->values = xrealloc(datum->values,
1723                                  datum->n * sizeof *datum->values);
1724         ovsdb_atom_clone(&datum->values[idx], value, type->value.type);
1725     }
1726 }
1727
1728 void
1729 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
1730                   const struct ovsdb_type *type, bool replace)
1731 {
1732     unsigned int n;
1733     size_t bi;
1734
1735     n = a->n;
1736     for (bi = 0; bi < b->n; bi++) {
1737         unsigned int ai;
1738
1739         ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key.type);
1740         if (ai == UINT_MAX) {
1741             if (n == a->n) {
1742                 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
1743             }
1744             ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key.type);
1745             if (type->value.type != OVSDB_TYPE_VOID) {
1746                 ovsdb_atom_clone(&a->values[n], &b->values[bi],
1747                                  type->value.type);
1748             }
1749             n++;
1750         } else if (replace && type->value.type != OVSDB_TYPE_VOID) {
1751             ovsdb_atom_destroy(&a->values[ai], type->value.type);
1752             ovsdb_atom_clone(&a->values[ai], &b->values[bi],
1753                              type->value.type);
1754         }
1755     }
1756     if (n != a->n) {
1757         struct ovsdb_error *error;
1758         a->n = n;
1759         error = ovsdb_datum_sort(a, type->key.type);
1760         assert(!error);
1761     }
1762 }
1763
1764 void
1765 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
1766                      const struct ovsdb_datum *b,
1767                      const struct ovsdb_type *b_type)
1768 {
1769     bool changed = false;
1770     size_t i;
1771
1772     assert(a_type->key.type == b_type->key.type);
1773     assert(a_type->value.type == b_type->value.type
1774            || b_type->value.type == OVSDB_TYPE_VOID);
1775
1776     /* XXX The big-O of this could easily be improved. */
1777     for (i = 0; i < a->n; ) {
1778         unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
1779         if (idx != UINT_MAX) {
1780             changed = true;
1781             ovsdb_datum_remove_unsafe(a, i, a_type);
1782         } else {
1783             i++;
1784         }
1785     }
1786     if (changed) {
1787         ovsdb_datum_sort_assert(a, a_type->key.type);
1788     }
1789 }
1790 \f
1791 struct ovsdb_symbol_table {
1792     struct shash sh;
1793 };
1794
1795 struct ovsdb_symbol_table *
1796 ovsdb_symbol_table_create(void)
1797 {
1798     struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
1799     shash_init(&symtab->sh);
1800     return symtab;
1801 }
1802
1803 void
1804 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
1805 {
1806     if (symtab) {
1807         shash_destroy_free_data(&symtab->sh);
1808         free(symtab);
1809     }
1810 }
1811
1812 struct ovsdb_symbol *
1813 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
1814                        const char *name)
1815 {
1816     return shash_find_data(&symtab->sh, name);
1817 }
1818
1819 struct ovsdb_symbol *
1820 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
1821                        const struct uuid *uuid, bool used)
1822 {
1823     struct ovsdb_symbol *symbol;
1824
1825     assert(!ovsdb_symbol_table_get(symtab, name));
1826     symbol = xmalloc(sizeof *symbol);
1827     symbol->uuid = *uuid;
1828     symbol->used = used;
1829     shash_add(&symtab->sh, name, symbol);
1830     return symbol;
1831 }
1832
1833 struct ovsdb_symbol *
1834 ovsdb_symbol_table_insert(struct ovsdb_symbol_table *symtab,
1835                           const char *name)
1836 {
1837     struct ovsdb_symbol *symbol;
1838
1839     symbol = ovsdb_symbol_table_get(symtab, name);
1840     if (!symbol) {
1841         struct uuid uuid;
1842
1843         uuid_generate(&uuid);
1844         symbol = ovsdb_symbol_table_put(symtab, name, &uuid, false);
1845     }
1846     return symbol;
1847 }
1848
1849 const char *
1850 ovsdb_symbol_table_find_unused(const struct ovsdb_symbol_table *symtab)
1851 {
1852     struct shash_node *node;
1853
1854     SHASH_FOR_EACH (node, &symtab->sh) {
1855         struct ovsdb_symbol *symbol = node->data;
1856         if (!symbol->used) {
1857             return node->name;
1858         }
1859     }
1860
1861     return NULL;
1862 }
1863 \f
1864 /* Extracts a token from the beginning of 's' and returns a pointer just after
1865  * the token.  Stores the token itself into '*outp', which the caller is
1866  * responsible for freeing (with free()).
1867  *
1868  * If 's[0]' is a delimiter, the returned token is the empty string.
1869  *
1870  * A token extends from 's' to the first delimiter, as defined by
1871  * ovsdb_token_is_delim(), or until the end of the string.  A delimiter can be
1872  * escaped with a backslash, in which case the backslash does not appear in the
1873  * output.  Double quotes also cause delimiters to be ignored, but the double
1874  * quotes are retained in the output.  (Backslashes inside double quotes are
1875  * not removed, either.)
1876  */
1877 char *
1878 ovsdb_token_parse(const char **s, char **outp)
1879 {
1880     const char *p;
1881     struct ds out;
1882     bool in_quotes;
1883     char *error;
1884
1885     ds_init(&out);
1886     in_quotes = false;
1887     for (p = *s; *p != '\0'; ) {
1888         int c = *p++;
1889         if (c == '\\') {
1890             if (in_quotes) {
1891                 ds_put_char(&out, '\\');
1892             }
1893             if (!*p) {
1894                 error = xasprintf("%s: backslash at end of argument", *s);
1895                 goto error;
1896             }
1897             ds_put_char(&out, *p++);
1898         } else if (!in_quotes && ovsdb_token_is_delim(c)) {
1899             p--;
1900             break;
1901         } else {
1902             ds_put_char(&out, c);
1903             if (c == '"') {
1904                 in_quotes = !in_quotes;
1905             }
1906         }
1907     }
1908     if (in_quotes) {
1909         error = xasprintf("%s: quoted string extends past end of argument",
1910                           *s);
1911         goto error;
1912     }
1913     *outp = ds_cstr(&out);
1914     *s = p;
1915     return NULL;
1916
1917 error:
1918     ds_destroy(&out);
1919     *outp = NULL;
1920     return error;
1921 }
1922
1923 /* Returns true if 'c' delimits tokens, or if 'c' is 0, and false otherwise. */
1924 bool
1925 ovsdb_token_is_delim(unsigned char c)
1926 {
1927     return strchr(":=, []{}!<>", c) != NULL;
1928 }