lib/ovsdb-data.c

   1 /* Copyright (c) 2009, 2010 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
  33 static struct json *
  34 wrap_json(const char *name, struct json *wrapped)
  35 {
  36     return json_array_create_2(json_string_create(name), wrapped);
  37 }
  38
  39 void
  40 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
  41 {
  42     switch (type) {
  43     case OVSDB_TYPE_VOID:
  44         NOT_REACHED();
  45
  46     case OVSDB_TYPE_INTEGER:
  47         atom->integer = 0;
  48         break;
  49
  50     case OVSDB_TYPE_REAL:
  51         atom->real = 0.0;
  52         break;
  53
  54     case OVSDB_TYPE_BOOLEAN:
  55         atom->boolean = false;
  56         break;
  57
  58     case OVSDB_TYPE_STRING:
  59         atom->string = xmemdup("", 1);
  60         break;
  61
  62     case OVSDB_TYPE_UUID:
  63         uuid_zero(&atom->uuid);
  64         break;
  65
  66     case OVSDB_N_TYPES:
  67     default:
  68         NOT_REACHED();
  69     }
  70 }
  71
  72 bool
  73 ovsdb_atom_is_default(const union ovsdb_atom *atom,
  74                       enum ovsdb_atomic_type type)
  75 {
  76     switch (type) {
  77     case OVSDB_TYPE_VOID:
  78         NOT_REACHED();
  79
  80     case OVSDB_TYPE_INTEGER:
  81         return atom->integer == 0;
  82
  83     case OVSDB_TYPE_REAL:
  84         return atom->real == 0.0;
  85
  86     case OVSDB_TYPE_BOOLEAN:
  87         return atom->boolean == false;
  88
  89     case OVSDB_TYPE_STRING:
  90         return atom->string[0] == '\0';
  91
  92     case OVSDB_TYPE_UUID:
  93         return uuid_is_zero(&atom->uuid);
  94
  95     case OVSDB_N_TYPES:
  96     default:
  97         NOT_REACHED();
  98     }
  99 }
 100
 101 void
 102 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
 103                  enum ovsdb_atomic_type type)
 104 {
 105     switch (type) {
 106     case OVSDB_TYPE_VOID:
 107         NOT_REACHED();
 108
 109     case OVSDB_TYPE_INTEGER:
 110         new->integer = old->integer;
 111         break;
 112
 113     case OVSDB_TYPE_REAL:
 114         new->real = old->real;
 115         break;
 116
 117     case OVSDB_TYPE_BOOLEAN:
 118         new->boolean = old->boolean;
 119         break;
 120
 121     case OVSDB_TYPE_STRING:
 122         new->string = xstrdup(old->string);
 123         break;
 124
 125     case OVSDB_TYPE_UUID:
 126         new->uuid = old->uuid;
 127         break;
 128
 129     case OVSDB_N_TYPES:
 130     default:
 131         NOT_REACHED();
 132     }
 133 }
 134
 135 void
 136 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
 137 {
 138     union ovsdb_atom tmp = *a;
 139     *a = *b;
 140     *b = tmp;
 141 }
 142
 143 uint32_t
 144 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 145                 uint32_t basis)
 146 {
 147     switch (type) {
 148     case OVSDB_TYPE_VOID:
 149         NOT_REACHED();
 150
 151     case OVSDB_TYPE_INTEGER:
 152         return hash_int(atom->integer, basis);
 153
 154     case OVSDB_TYPE_REAL:
 155         return hash_double(atom->real, basis);
 156
 157     case OVSDB_TYPE_BOOLEAN:
 158         return hash_boolean(atom->boolean, basis);
 159
 160     case OVSDB_TYPE_STRING:
 161         return hash_string(atom->string, basis);
 162
 163     case OVSDB_TYPE_UUID:
 164         return hash_int(uuid_hash(&atom->uuid), basis);
 165
 166     case OVSDB_N_TYPES:
 167     default:
 168         NOT_REACHED();
 169     }
 170 }
 171
 172 int
 173 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
 174                         const union ovsdb_atom *b,
 175                         enum ovsdb_atomic_type type)
 176 {
 177     switch (type) {
 178     case OVSDB_TYPE_VOID:
 179         NOT_REACHED();
 180
 181     case OVSDB_TYPE_INTEGER:
 182         return a->integer < b->integer ? -1 : a->integer > b->integer;
 183
 184     case OVSDB_TYPE_REAL:
 185         return a->real < b->real ? -1 : a->real > b->real;
 186
 187     case OVSDB_TYPE_BOOLEAN:
 188         return a->boolean - b->boolean;
 189
 190     case OVSDB_TYPE_STRING:
 191         return strcmp(a->string, b->string);
 192
 193     case OVSDB_TYPE_UUID:
 194         return uuid_compare_3way(&a->uuid, &b->uuid);
 195
 196     case OVSDB_N_TYPES:
 197     default:
 198         NOT_REACHED();
 199     }
 200 }
 201
 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)
 205 {
 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)
 211     {
 212         return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
 213                                   json_type_to_string(value_type));
 214     }
 215     *value = json->u.array.elems[1];
 216     return NULL;
 217 }
 218
 219 static struct ovsdb_error *
 220 parse_json_pair(const struct json *json,
 221                 const struct json **elem0, const struct json **elem1)
 222 {
 223     if (json->type != JSON_ARRAY || json->u.array.n != 2) {
 224         return ovsdb_syntax_error(json, NULL, "expected 2-element array");
 225     }
 226     *elem0 = json->u.array.elems[0];
 227     *elem1 = json->u.array.elems[1];
 228     return NULL;
 229 }
 230
 231 static struct ovsdb_error *
 232 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
 233                       const struct ovsdb_symbol_table *symtab)
 234     WARN_UNUSED_RESULT;
 235
 236 static struct ovsdb_error *
 237 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
 238                       const struct ovsdb_symbol_table *symtab)
 239 {
 240     struct ovsdb_error *error0;
 241     const struct json *value;
 242
 243     error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
 244     if (!error0) {
 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",
 248                                       uuid_string);
 249         }
 250     } else if (symtab) {
 251         struct ovsdb_error *error1;
 252
 253         error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
 254         if (!error1) {
 255             const char *name = json_string(value);
 256             const struct ovsdb_symbol *symbol;
 257
 258             ovsdb_error_destroy(error0);
 259
 260             symbol = ovsdb_symbol_table_get(symtab, name);
 261             if (symbol) {
 262                 *uuid = symbol->uuid;
 263                 return NULL;
 264             } else {
 265                 return ovsdb_syntax_error(json, NULL,
 266                                           "unknown named-uuid \"%s\"", name);
 267             }
 268         }
 269         ovsdb_error_destroy(error1);
 270     }
 271
 272     return error0;
 273 }
 274
 275 struct ovsdb_error *
 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)
 279 {
 280     switch (type) {
 281     case OVSDB_TYPE_VOID:
 282         NOT_REACHED();
 283
 284     case OVSDB_TYPE_INTEGER:
 285         if (json->type == JSON_INTEGER) {
 286             atom->integer = json->u.integer;
 287             return NULL;
 288         }
 289         break;
 290
 291     case OVSDB_TYPE_REAL:
 292         if (json->type == JSON_INTEGER) {
 293             atom->real = json->u.integer;
 294             return NULL;
 295         } else if (json->type == JSON_REAL) {
 296             atom->real = json->u.real;
 297             return NULL;
 298         }
 299         break;
 300
 301     case OVSDB_TYPE_BOOLEAN:
 302         if (json->type == JSON_TRUE) {
 303             atom->boolean = true;
 304             return NULL;
 305         } else if (json->type == JSON_FALSE) {
 306             atom->boolean = false;
 307             return NULL;
 308         }
 309         break;
 310
 311     case OVSDB_TYPE_STRING:
 312         if (json->type == JSON_STRING) {
 313             atom->string = xstrdup(json->u.string);
 314             return NULL;
 315         }
 316         break;
 317
 318     case OVSDB_TYPE_UUID:
 319         return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
 320
 321     case OVSDB_N_TYPES:
 322     default:
 323         NOT_REACHED();
 324     }
 325
 326     return ovsdb_syntax_error(json, NULL, "expected %s",
 327                               ovsdb_atomic_type_to_string(type));
 328 }
 329
 330 struct json *
 331 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
 332 {
 333     switch (type) {
 334     case OVSDB_TYPE_VOID:
 335         NOT_REACHED();
 336
 337     case OVSDB_TYPE_INTEGER:
 338         return json_integer_create(atom->integer);
 339
 340     case OVSDB_TYPE_REAL:
 341         return json_real_create(atom->real);
 342
 343     case OVSDB_TYPE_BOOLEAN:
 344         return json_boolean_create(atom->boolean);
 345
 346     case OVSDB_TYPE_STRING:
 347         return json_string_create(atom->string);
 348
 349     case OVSDB_TYPE_UUID:
 350         return wrap_json("uuid", json_string_create_nocopy(
 351                              xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
 352
 353     case OVSDB_N_TYPES:
 354     default:
 355         NOT_REACHED();
 356     }
 357 }
 358
 359 /* Initializes 'atom' to a value of the given 'type' parsed from 's', which
 360  * takes one of the following forms:
 361  *
 362  *      - OVSDB_TYPE_INTEGER: A decimal integer optionally preceded by a sign.
 363  *
 364  *      - OVSDB_TYPE_REAL: A floating-point number in the format accepted by
 365  *        strtod().
 366  *
 367  *      - OVSDB_TYPE_BOOLEAN: "true", "yes", "on", "1" for true, or "false",
 368  *        "no", "off", or "0" for false.
 369  *
 370  *      - OVSDB_TYPE_STRING: A JSON string if it begins with a quote, otherwise
 371  *        an arbitrary string.
 372  *
 373  *      - OVSDB_TYPE_UUID: A UUID in RFC 4122 format.
 374  *
 375  * Returns a null pointer if successful, otherwise an error message describing
 376  * the problem.  The caller is responsible for freeing the error.
 377  */
 378 char *
 379 ovsdb_atom_from_string(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 380                        const char *s)
 381 {
 382     switch (type) {
 383     case OVSDB_TYPE_VOID:
 384         NOT_REACHED();
 385
 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);
 390         }
 391         atom->integer = integer;
 392     }
 393         break;
 394
 395     case OVSDB_TYPE_REAL:
 396         if (!str_to_double(s, &atom->real)) {
 397             return xasprintf("\"%s\" is not a valid real number", s);
 398         }
 399         break;
 400
 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;
 408         } else {
 409             return xasprintf("\"%s\" is not a valid boolean "
 410                              "(use \"true\" or \"false\")", s);
 411         }
 412         break;
 413
 414     case OVSDB_TYPE_STRING:
 415         if (*s == '\0') {
 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);
 420
 421             if (s_len < 2 || s[s_len - 1] != '"') {
 422                 return xasprintf("%s: missing quote at end of "
 423                                  "quoted string", s);
 424             } else if (!json_string_unescape(s + 1, s_len - 2,
 425                                              &atom->string)) {
 426                 char *error = xasprintf("%s: %s", s, atom->string);
 427                 free(atom->string);
 428                 return error;
 429             }
 430         } else {
 431             atom->string = xstrdup(s);
 432         }
 433         break;
 434
 435     case OVSDB_TYPE_UUID:
 436         if (!uuid_from_string(&atom->uuid, s)) {
 437             return xasprintf("\"%s\" is not a valid UUID", s);
 438         }
 439         break;
 440
 441     case OVSDB_N_TYPES:
 442     default:
 443         NOT_REACHED();
 444     }
 445
 446     return NULL;
 447 }
 448
 449 static bool
 450 string_needs_quotes(const char *s)
 451 {
 452     const char *p = s;
 453     unsigned char c;
 454
 455     c = *p++;
 456     if (!isalpha(c) && c != '_') {
 457         return true;
 458     }
 459
 460     while ((c = *p++) != '\0') {
 461         if (!isalpha(c) && c != '_' && c != '-' && c != '.') {
 462             return true;
 463         }
 464     }
 465
 466     if (!strcmp(s, "true") || !strcmp(s, "false")) {
 467         return true;
 468     }
 469
 470     return false;
 471 }
 472
 473 /* Appends 'atom' (which has the given 'type') to 'out', in a format acceptable
 474  * to ovsdb_atom_from_string().  */
 475 void
 476 ovsdb_atom_to_string(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 477                      struct ds *out)
 478 {
 479     switch (type) {
 480     case OVSDB_TYPE_VOID:
 481         NOT_REACHED();
 482
 483     case OVSDB_TYPE_INTEGER:
 484         ds_put_format(out, "%"PRId64, atom->integer);
 485         break;
 486
 487     case OVSDB_TYPE_REAL:
 488         ds_put_format(out, "%.*g", DBL_DIG, atom->real);
 489         break;
 490
 491     case OVSDB_TYPE_BOOLEAN:
 492         ds_put_cstr(out, atom->boolean ? "true" : "false");
 493         break;
 494
 495     case OVSDB_TYPE_STRING:
 496         if (string_needs_quotes(atom->string)) {
 497             struct json json;
 498
 499             json.type = JSON_STRING;
 500             json.u.string = atom->string;
 501             json_to_ds(&json, 0, out);
 502         } else {
 503             ds_put_cstr(out, atom->string);
 504         }
 505         break;
 506
 507     case OVSDB_TYPE_UUID:
 508         ds_put_format(out, UUID_FMT, UUID_ARGS(&atom->uuid));
 509         break;
 510
 511     case OVSDB_N_TYPES:
 512     default:
 513         NOT_REACHED();
 514     }
 515 }
 516 \f
 517 static union ovsdb_atom *
 518 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
 519 {
 520     if (type != OVSDB_TYPE_VOID && n) {
 521         union ovsdb_atom *atoms;
 522         unsigned int i;
 523
 524         atoms = xmalloc(n * sizeof *atoms);
 525         for (i = 0; i < n; i++) {
 526             ovsdb_atom_init_default(&atoms[i], type);
 527         }
 528         return atoms;
 529     } else {
 530         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 531          * treated as xmalloc(1). */
 532         return NULL;
 533     }
 534 }
 535
 536 void
 537 ovsdb_datum_init_empty(struct ovsdb_datum *datum)
 538 {
 539     datum->n = 0;
 540     datum->keys = NULL;
 541     datum->values = NULL;
 542 }
 543
 544 void
 545 ovsdb_datum_init_default(struct ovsdb_datum *datum,
 546                          const struct ovsdb_type *type)
 547 {
 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);
 551 }
 552
 553 bool
 554 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
 555                        const struct ovsdb_type *type)
 556 {
 557     size_t i;
 558
 559     if (datum->n != type->n_min) {
 560         return false;
 561     }
 562     for (i = 0; i < datum->n; i++) {
 563         if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
 564             return false;
 565         }
 566         if (type->value_type != OVSDB_TYPE_VOID
 567             && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
 568             return false;
 569         }
 570     }
 571
 572     return true;
 573 }
 574
 575 static union ovsdb_atom *
 576 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 577 {
 578     if (type != OVSDB_TYPE_VOID && n) {
 579         union ovsdb_atom *new;
 580         unsigned int i;
 581
 582         new = xmalloc(n * sizeof *new);
 583         for (i = 0; i < n; i++) {
 584             ovsdb_atom_clone(&new[i], &old[i], type);
 585         }
 586         return new;
 587     } else {
 588         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 589          * treated as xmalloc(1). */
 590         return NULL;
 591     }
 592 }
 593
 594 void
 595 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
 596                   const struct ovsdb_type *type)
 597 {
 598     unsigned int n = old->n;
 599     new->n = n;
 600     new->keys = clone_atoms(old->keys, type->key_type, n);
 601     new->values = clone_atoms(old->values, type->value_type, n);
 602 }
 603
 604 static void
 605 free_data(enum ovsdb_atomic_type type,
 606           union ovsdb_atom *atoms, size_t n_atoms)
 607 {
 608     if (ovsdb_atom_needs_destruction(type)) {
 609         unsigned int i;
 610         for (i = 0; i < n_atoms; i++) {
 611             ovsdb_atom_destroy(&atoms[i], type);
 612         }
 613     }
 614     free(atoms);
 615 }
 616
 617 void
 618 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 619 {
 620     free_data(type->key_type, datum->keys, datum->n);
 621     free_data(type->value_type, datum->values, datum->n);
 622 }
 623
 624 void
 625 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
 626 {
 627     struct ovsdb_datum tmp = *a;
 628     *a = *b;
 629     *b = tmp;
 630 }
 631
 632 struct ovsdb_datum_sort_cbdata {
 633     const struct ovsdb_type *type;
 634     struct ovsdb_datum *datum;
 635 };
 636
 637 static int
 638 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
 639 {
 640     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 641
 642     return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
 643                                    &cbdata->datum->keys[b],
 644                                    cbdata->type->key_type);
 645 }
 646
 647 static void
 648 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
 649 {
 650     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 651
 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]);
 655     }
 656 }
 657
 658 struct ovsdb_error *
 659 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 660 {
 661     if (datum->n < 2) {
 662         return NULL;
 663     } else {
 664         struct ovsdb_datum_sort_cbdata cbdata;
 665         size_t i;
 666
 667         cbdata.type = type;
 668         cbdata.datum = datum;
 669         sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
 670              &cbdata);
 671
 672         for (i = 0; i < datum->n - 1; i++) {
 673             if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
 674                                   type->key_type)) {
 675                 if (ovsdb_type_is_map(type)) {
 676                     return ovsdb_error(NULL, "map contains duplicate key");
 677                 } else {
 678                     return ovsdb_error(NULL, "set contains duplicate");
 679                 }
 680             }
 681         }
 682
 683         return NULL;
 684     }
 685 }
 686
 687 struct ovsdb_error *
 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)
 692 {
 693     struct ovsdb_error *error;
 694
 695     if (ovsdb_type_is_scalar(type)) {
 696         datum->n = 1;
 697         datum->keys = xmalloc(sizeof *datum->keys);
 698         datum->values = NULL;
 699
 700         error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
 701                                      json, symtab);
 702         if (error) {
 703             free(datum->keys);
 704         }
 705         return error;
 706     } else {
 707         bool is_map = ovsdb_type_is_map(type);
 708         const char *class = is_map ? "map" : "set";
 709         const struct json *inner;
 710         unsigned int i;
 711         size_t n;
 712
 713         assert(is_map || ovsdb_type_is_set(type));
 714
 715         error = unwrap_json(json, class, JSON_ARRAY, &inner);
 716         if (error) {
 717             return error;
 718         }
 719
 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);
 725         }
 726
 727         datum->n = 0;
 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;
 734
 735             if (!is_map) {
 736                 key = element;
 737             } else {
 738                 error = parse_json_pair(element, &key, &value);
 739                 if (error) {
 740                     goto error;
 741                 }
 742             }
 743
 744             error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
 745                                          key, symtab);
 746             if (error) {
 747                 goto error;
 748             }
 749
 750             if (is_map) {
 751                 error = ovsdb_atom_from_json(&datum->values[i],
 752                                              type->value_type, value, symtab);
 753                 if (error) {
 754                     ovsdb_atom_destroy(&datum->keys[i], type->key_type);
 755                     goto error;
 756                 }
 757             }
 758
 759             datum->n++;
 760         }
 761
 762         error = ovsdb_datum_sort(datum, type);
 763         if (error) {
 764             goto error;
 765         }
 766
 767         return NULL;
 768
 769     error:
 770         ovsdb_datum_destroy(datum, type);
 771         return error;
 772     }
 773 }
 774
 775 struct json *
 776 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
 777                     const struct ovsdb_type *type)
 778 {
 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) {
 784         struct json **elems;
 785         size_t i;
 786
 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);
 790         }
 791
 792         return wrap_json("set", json_array_create(elems, datum->n));
 793     } else {
 794         struct json **elems;
 795         size_t i;
 796
 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));
 802         }
 803
 804         return wrap_json("map", json_array_create(elems, datum->n));
 805     }
 806 }
 807
 808 static const char *
 809 skip_spaces(const char *p)
 810 {
 811     return p + strspn(p, " ");
 812 }
 813
 814 static char *
 815 parse_atom_token(const char **s, enum ovsdb_atomic_type type,
 816                  union ovsdb_atom *atom)
 817 {
 818     char *token, *error;
 819
 820     error = ovsdb_token_parse(s, &token);
 821     if (!error) {
 822         error = ovsdb_atom_from_string(atom, type, token);
 823         free(token);
 824     }
 825     return error;
 826 }
 827
 828
 829 static char *
 830 parse_key_value(const char **s, const struct ovsdb_type *type,
 831                 union ovsdb_atom *key, union ovsdb_atom *value)
 832 {
 833     const char *start = *s;
 834     char *error;
 835
 836     error = parse_atom_token(s, type->key_type, key);
 837     if (!error && type->value_type != OVSDB_TYPE_VOID) {
 838         if (**s == '=') {
 839             (*s)++;
 840             error = parse_atom_token(s, type->value_type, value);
 841         } else {
 842             error = xasprintf("%s: syntax error at \"%c\" expecting \"=\"",
 843                               start, **s);
 844         }
 845         if (error) {
 846             ovsdb_atom_destroy(key, type->key_type);
 847         }
 848     }
 849     return error;
 850 }
 851
 852 static void
 853 free_key_value(const struct ovsdb_type *type,
 854                union ovsdb_atom *key, union ovsdb_atom *value)
 855 {
 856     ovsdb_atom_destroy(key, type->key_type);
 857     if (type->value_type != OVSDB_TYPE_VOID) {
 858         ovsdb_atom_destroy(value, type->value_type);
 859     }
 860 }
 861
 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
 867  * required. */
 868 char *
 869 ovsdb_datum_from_string(struct ovsdb_datum *datum,
 870                         const struct ovsdb_type *type, const char *s)
 871 {
 872     bool is_map = ovsdb_type_is_map(type);
 873     struct ovsdb_error *dberror;
 874     const char *p;
 875     int end_delim;
 876     char *error;
 877
 878     ovsdb_datum_init_empty(datum);
 879
 880     /* Swallow a leading delimiter if there is one. */
 881     p = skip_spaces(s);
 882     if (*p == (is_map ? '{' : '[')) {
 883         end_delim = is_map ? '}' : ']';
 884         p = skip_spaces(p + 1);
 885     } else if (!*p) {
 886         if (is_map) {
 887             return xstrdup("use \"{}\" to specify the empty map");
 888         } else {
 889             return xstrdup("use \"[]\" to specify the empty set");
 890         }
 891     } else {
 892         end_delim = 0;
 893     }
 894
 895     while (*p && *p != end_delim) {
 896         union ovsdb_atom key, value;
 897
 898         if (ovsdb_token_is_delim(*p)) {
 899             error = xasprintf("%s: unexpected \"%c\" parsing %s",
 900                               s, *p, ovsdb_type_to_english(type));
 901             goto error;
 902         }
 903
 904         /* Add to datum. */
 905         error = parse_key_value(&p, type, &key, &value);
 906         if (error) {
 907             goto error;
 908         }
 909         ovsdb_datum_add_unsafe(datum, &key, &value, type);
 910         free_key_value(type, &key, &value);
 911
 912         /* Skip optional white space and comma. */
 913         p = skip_spaces(p);
 914         if (*p == ',') {
 915             p = skip_spaces(p + 1);
 916         }
 917     }
 918
 919     if (*p != end_delim) {
 920         error = xasprintf("%s: missing \"%c\" at end of data", s, end_delim);
 921         goto error;
 922     }
 923     if (end_delim) {
 924         p = skip_spaces(p + 1);
 925         if (*p) {
 926             error = xasprintf("%s: trailing garbage after \"%c\"",
 927                               s, end_delim);
 928             goto error;
 929         }
 930     }
 931
 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)",
 935                           type->n_min);
 936         goto error;
 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)",
 940             type->n_max);
 941         goto error;
 942     }
 943
 944     dberror = ovsdb_datum_sort(datum, type);
 945     if (dberror) {
 946         ovsdb_error_destroy(dberror);
 947         if (ovsdb_type_is_map(type)) {
 948             error = xasprintf("%s: map contains duplicate key", s);
 949         } else {
 950             error = xasprintf("%s: set contains duplicate value", s);
 951         }
 952         goto error;
 953     }
 954
 955     return NULL;
 956
 957 error:
 958     ovsdb_datum_destroy(datum, type);
 959     ovsdb_datum_init_empty(datum);
 960     return error;
 961 }
 962
 963 /* Appends to 'out' the 'datum' (with the given 'type') in a format acceptable
 964  * to ovsdb_datum_from_string(). */
 965 void
 966 ovsdb_datum_to_string(const struct ovsdb_datum *datum,
 967                       const struct ovsdb_type *type, struct ds *out)
 968 {
 969     bool is_map = ovsdb_type_is_map(type);
 970     size_t i;
 971
 972     if (type->n_max > 1 || !datum->n) {
 973         ds_put_char(out, is_map ? '{' : '[');
 974     }
 975     for (i = 0; i < datum->n; i++) {
 976         if (i > 0) {
 977             ds_put_cstr(out, ", ");
 978         }
 979
 980         ovsdb_atom_to_string(&datum->keys[i], type->key_type, out);
 981         if (is_map) {
 982             ds_put_char(out, '=');
 983             ovsdb_atom_to_string(&datum->values[i], type->value_type, out);
 984         }
 985     }
 986     if (type->n_max > 1 || !datum->n) {
 987         ds_put_char(out, is_map ? '}' : ']');
 988     }
 989 }
 990
 991 static uint32_t
 992 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
 993            unsigned int n, uint32_t basis)
 994 {
 995     if (type != OVSDB_TYPE_VOID) {
 996         unsigned int i;
 997
 998         for (i = 0; i < n; i++) {
 999             basis = ovsdb_atom_hash(&atoms[i], type, basis);
1000         }
1001     }
1002     return basis;
1003 }
1004
1005 uint32_t
1006 ovsdb_datum_hash(const struct ovsdb_datum *datum,
1007                  const struct ovsdb_type *type, uint32_t basis)
1008 {
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);
1012     return basis;
1013 }
1014
1015 static int
1016 atom_arrays_compare_3way(const union ovsdb_atom *a,
1017                          const union ovsdb_atom *b,
1018                          enum ovsdb_atomic_type type,
1019                          size_t n)
1020 {
1021     unsigned int i;
1022
1023     for (i = 0; i < n; i++) {
1024         int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
1025         if (cmp) {
1026             return cmp;
1027         }
1028     }
1029
1030     return 0;
1031 }
1032
1033 bool
1034 ovsdb_datum_equals(const struct ovsdb_datum *a,
1035                    const struct ovsdb_datum *b,
1036                    const struct ovsdb_type *type)
1037 {
1038     return !ovsdb_datum_compare_3way(a, b, type);
1039 }
1040
1041 int
1042 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
1043                          const struct ovsdb_datum *b,
1044                          const struct ovsdb_type *type)
1045 {
1046     int cmp;
1047
1048     if (a->n != b->n) {
1049         return a->n < b->n ? -1 : 1;
1050     }
1051
1052     cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
1053     if (cmp) {
1054         return cmp;
1055     }
1056
1057     return (type->value_type == OVSDB_TYPE_VOID ? 0
1058             : atom_arrays_compare_3way(a->values, b->values, type->value_type,
1059                                        a->n));
1060 }
1061
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'.
1065  */
1066 unsigned int
1067 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
1068                      const union ovsdb_atom *key,
1069                      enum ovsdb_atomic_type key_type)
1070 {
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);
1076         if (cmp < 0) {
1077             high = idx;
1078         } else if (cmp > 0) {
1079             low = idx + 1;
1080         } else {
1081             return idx;
1082         }
1083     }
1084     return UINT_MAX;
1085 }
1086
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.
1091  */
1092 unsigned int
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)
1098 {
1099     unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
1100     if (idx != UINT_MAX
1101         && value_type != OVSDB_TYPE_VOID
1102         && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
1103         idx = UINT_MAX;
1104     }
1105     return idx;
1106 }
1107
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
1111  * values. */
1112 static unsigned int
1113 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
1114                  const struct ovsdb_datum *b,
1115                  const struct ovsdb_type *type)
1116 {
1117     return ovsdb_datum_find_key_value(b,
1118                                       &a->keys[i], type->key_type,
1119                                       a->values ? &a->values[i] : NULL,
1120                                       type->value_type);
1121 }
1122
1123 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
1124 bool
1125 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
1126                          const struct ovsdb_datum *b,
1127                          const struct ovsdb_type *type)
1128 {
1129     size_t i;
1130
1131     for (i = 0; i < a->n; i++) {
1132         if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
1133             return false;
1134         }
1135     }
1136     return true;
1137 }
1138
1139 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
1140 bool
1141 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
1142                          const struct ovsdb_datum *b,
1143                          const struct ovsdb_type *type)
1144 {
1145     size_t i;
1146
1147     for (i = 0; i < a->n; i++) {
1148         if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
1149             return false;
1150         }
1151     }
1152     return true;
1153 }
1154
1155 static void
1156 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
1157                        unsigned int capacity)
1158 {
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);
1162     }
1163 }
1164
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.
1168  *
1169  * This function does not maintain ovsdb_datum invariants.  Use
1170  * ovsdb_datum_sort() to check and restore these invariants. */
1171 void
1172 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
1173                           const struct ovsdb_type *type)
1174 {
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];
1180     }
1181     datum->n--;
1182 }
1183
1184 /* Adds the element with the given 'key' and 'value' to 'datum', which must
1185  * have the specified 'type'.
1186  *
1187  * This function always allocates memory, so it is not an efficient way to add
1188  * a number of elements to a datum.
1189  *
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.) */
1193 void
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)
1198 {
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);
1206     }
1207 }
1208
1209 void
1210 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
1211                   const struct ovsdb_type *type, bool replace)
1212 {
1213     unsigned int n;
1214     size_t bi;
1215
1216     n = a->n;
1217     for (bi = 0; bi < b->n; bi++) {
1218         unsigned int ai;
1219
1220         ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type);
1221         if (ai == UINT_MAX) {
1222             if (n == a->n) {
1223                 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
1224             }
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],
1228                                  type->value_type);
1229             }
1230             n++;
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],
1234                              type->value_type);
1235         }
1236     }
1237     if (n != a->n) {
1238         struct ovsdb_error *error;
1239         a->n = n;
1240         error = ovsdb_datum_sort(a, type);
1241         assert(!error);
1242     }
1243 }
1244
1245 void
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)
1249 {
1250     bool changed = false;
1251     size_t i;
1252
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);
1256
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) {
1261             changed = true;
1262             ovsdb_datum_remove_unsafe(a, i, a_type);
1263         } else {
1264             i++;
1265         }
1266     }
1267     if (changed) {
1268         struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
1269         assert(!error);
1270     }
1271 }
1272 \f
1273 struct ovsdb_symbol_table {
1274     struct shash sh;
1275 };
1276
1277 struct ovsdb_symbol_table *
1278 ovsdb_symbol_table_create(void)
1279 {
1280     struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
1281     shash_init(&symtab->sh);
1282     return symtab;
1283 }
1284
1285 void
1286 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
1287 {
1288     if (symtab) {
1289         struct shash_node *node, *next;
1290
1291         SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
1292             struct ovsdb_symbol *symbol = node->data;
1293             free(symbol);
1294             shash_delete(&symtab->sh, node);
1295         }
1296         shash_destroy(&symtab->sh);
1297         free(symtab);
1298     }
1299 }
1300
1301 struct ovsdb_symbol *
1302 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
1303                        const char *name)
1304 {
1305     return shash_find_data(&symtab->sh, name);
1306 }
1307
1308 void
1309 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
1310                        const struct uuid *uuid, bool used)
1311 {
1312     struct ovsdb_symbol *symbol;
1313
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);
1319 }
1320 \f
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()).
1324  *
1325  * If 's[0]' is a delimiter, the returned token is the empty string.
1326  *
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.)
1333  */
1334 char *
1335 ovsdb_token_parse(const char **s, char **outp)
1336 {
1337     const char *p;
1338     struct ds out;
1339     bool in_quotes;
1340     char *error;
1341
1342     ds_init(&out);
1343     in_quotes = false;
1344     for (p = *s; *p != '\0'; ) {
1345         int c = *p++;
1346         if (c == '\\') {
1347             if (in_quotes) {
1348                 ds_put_char(&out, '\\');
1349             }
1350             if (!*p) {
1351                 error = xasprintf("%s: backslash at end of argument", *s);
1352                 goto error;
1353             }
1354             ds_put_char(&out, *p++);
1355         } else if (!in_quotes && ovsdb_token_is_delim(c)) {
1356             p--;
1357             break;
1358         } else {
1359             ds_put_char(&out, c);
1360             if (c == '"') {
1361                 in_quotes = !in_quotes;
1362             }
1363         }
1364     }
1365     if (in_quotes) {
1366         error = xasprintf("%s: quoted string extends past end of argument",
1367                           *s);
1368         goto error;
1369     }
1370     *outp = ds_cstr(&out);
1371     *s = p;
1372     return NULL;
1373
1374 error:
1375     ds_destroy(&out);
1376     *outp = NULL;
1377     return error;
1378 }
1379
1380 /* Returns true if 'c' delimits tokens, or if 'c' is 0, and false otherwise. */
1381 bool
1382 ovsdb_token_is_delim(unsigned char c)
1383 {
1384     return strchr(":=, []{}", c) != NULL;
1385 }