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 void
 376 ovsdb_atom_from_string(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 377                        const char *s)
 378 {
 379     switch (type) {
 380     case OVSDB_TYPE_VOID:
 381         NOT_REACHED();
 382
 383     case OVSDB_TYPE_INTEGER: {
 384         long long int integer;
 385         if (!str_to_llong(s, 10, &integer)) {
 386             ovs_fatal(0, "%s is not a valid integer", s);
 387         }
 388         atom->integer = integer;
 389     }
 390         break;
 391
 392     case OVSDB_TYPE_REAL:
 393         if (!str_to_double(s, &atom->real)) {
 394             ovs_fatal(0, "%s is not a valid real number", s);
 395         }
 396         break;
 397
 398     case OVSDB_TYPE_BOOLEAN:
 399         if (!strcmp(s, "true") || !strcmp(s, "yes") || !strcmp(s, "on")
 400             || !strcmp(s, "1")) {
 401             atom->boolean = true;
 402         } else if (!strcmp(s, "false") || !strcmp(s, "no") || !strcmp(s, "off")
 403                    || !strcmp(s, "0")) {
 404             atom->boolean = false;
 405         } else {
 406             ovs_fatal(0, "%s is not a valid boolean "
 407                       "(use \"true\" or \"false\")", s);
 408         }
 409         break;
 410
 411     case OVSDB_TYPE_STRING:
 412         if (*s == '\0') {
 413             ovs_fatal(0, "use \"\" to represent the empty string");
 414         } else if (*s == '"') {
 415             size_t s_len = strlen(s);
 416
 417             if (s_len < 2 || s[s_len - 1] != '"') {
 418                 ovs_fatal(0, "%s: missing quote at end of quoted string", s);
 419             } else if (!json_string_unescape(s + 1, s_len - 2,
 420                                              &atom->string)) {
 421                 ovs_fatal(0, "%s: %s", s, atom->string);
 422             }
 423         } else {
 424             atom->string = xstrdup(s);
 425         }
 426         break;
 427
 428     case OVSDB_TYPE_UUID:
 429         if (!uuid_from_string(&atom->uuid, s)) {
 430             ovs_fatal(0, "%s is not a valid UUID", s);
 431         }
 432         break;
 433
 434     case OVSDB_N_TYPES:
 435     default:
 436         NOT_REACHED();
 437     }
 438 }
 439
 440 static bool
 441 string_needs_quotes(const char *s)
 442 {
 443     const char *p = s;
 444     unsigned char c;
 445
 446     c = *p++;
 447     if (!isalpha(c) && c != '_') {
 448         return true;
 449     }
 450
 451     while ((c = *p++) != '\0') {
 452         if (!isalpha(c) && c != '_' && c != '-' && c != '.') {
 453             return true;
 454         }
 455     }
 456
 457     if (!strcmp(s, "true") || !strcmp(s, "false")) {
 458         return true;
 459     }
 460
 461     return false;
 462 }
 463
 464 /* Appends 'atom' (which has the given 'type') to 'out', in a format acceptable
 465  * to ovsdb_atom_from_string().  */
 466 void
 467 ovsdb_atom_to_string(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 468                      struct ds *out)
 469 {
 470     switch (type) {
 471     case OVSDB_TYPE_VOID:
 472         NOT_REACHED();
 473
 474     case OVSDB_TYPE_INTEGER:
 475         ds_put_format(out, "%"PRId64, atom->integer);
 476         break;
 477
 478     case OVSDB_TYPE_REAL:
 479         ds_put_format(out, "%.*g", DBL_DIG, atom->real);
 480         break;
 481
 482     case OVSDB_TYPE_BOOLEAN:
 483         ds_put_cstr(out, atom->boolean ? "true" : "false");
 484         break;
 485
 486     case OVSDB_TYPE_STRING:
 487         if (string_needs_quotes(atom->string)) {
 488             struct json json;
 489
 490             json.type = JSON_STRING;
 491             json.u.string = atom->string;
 492             json_to_ds(&json, 0, out);
 493         } else {
 494             ds_put_cstr(out, atom->string);
 495         }
 496         break;
 497
 498     case OVSDB_TYPE_UUID:
 499         ds_put_format(out, UUID_FMT, UUID_ARGS(&atom->uuid));
 500         break;
 501
 502     case OVSDB_N_TYPES:
 503     default:
 504         NOT_REACHED();
 505     }
 506 }
 507 \f
 508 static union ovsdb_atom *
 509 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
 510 {
 511     if (type != OVSDB_TYPE_VOID && n) {
 512         union ovsdb_atom *atoms;
 513         unsigned int i;
 514
 515         atoms = xmalloc(n * sizeof *atoms);
 516         for (i = 0; i < n; i++) {
 517             ovsdb_atom_init_default(&atoms[i], type);
 518         }
 519         return atoms;
 520     } else {
 521         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 522          * treated as xmalloc(1). */
 523         return NULL;
 524     }
 525 }
 526
 527 void
 528 ovsdb_datum_init_empty(struct ovsdb_datum *datum)
 529 {
 530     datum->n = 0;
 531     datum->keys = NULL;
 532     datum->values = NULL;
 533 }
 534
 535 void
 536 ovsdb_datum_init_default(struct ovsdb_datum *datum,
 537                          const struct ovsdb_type *type)
 538 {
 539     datum->n = type->n_min;
 540     datum->keys = alloc_default_atoms(type->key_type, datum->n);
 541     datum->values = alloc_default_atoms(type->value_type, datum->n);
 542 }
 543
 544 bool
 545 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
 546                        const struct ovsdb_type *type)
 547 {
 548     size_t i;
 549
 550     if (datum->n != type->n_min) {
 551         return false;
 552     }
 553     for (i = 0; i < datum->n; i++) {
 554         if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
 555             return false;
 556         }
 557         if (type->value_type != OVSDB_TYPE_VOID
 558             && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
 559             return false;
 560         }
 561     }
 562
 563     return true;
 564 }
 565
 566 static union ovsdb_atom *
 567 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 568 {
 569     if (type != OVSDB_TYPE_VOID && n) {
 570         union ovsdb_atom *new;
 571         unsigned int i;
 572
 573         new = xmalloc(n * sizeof *new);
 574         for (i = 0; i < n; i++) {
 575             ovsdb_atom_clone(&new[i], &old[i], type);
 576         }
 577         return new;
 578     } else {
 579         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 580          * treated as xmalloc(1). */
 581         return NULL;
 582     }
 583 }
 584
 585 void
 586 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
 587                   const struct ovsdb_type *type)
 588 {
 589     unsigned int n = old->n;
 590     new->n = n;
 591     new->keys = clone_atoms(old->keys, type->key_type, n);
 592     new->values = clone_atoms(old->values, type->value_type, n);
 593 }
 594
 595 static void
 596 free_data(enum ovsdb_atomic_type type,
 597           union ovsdb_atom *atoms, size_t n_atoms)
 598 {
 599     if (ovsdb_atom_needs_destruction(type)) {
 600         unsigned int i;
 601         for (i = 0; i < n_atoms; i++) {
 602             ovsdb_atom_destroy(&atoms[i], type);
 603         }
 604     }
 605     free(atoms);
 606 }
 607
 608 void
 609 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 610 {
 611     free_data(type->key_type, datum->keys, datum->n);
 612     free_data(type->value_type, datum->values, datum->n);
 613 }
 614
 615 void
 616 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
 617 {
 618     struct ovsdb_datum tmp = *a;
 619     *a = *b;
 620     *b = tmp;
 621 }
 622
 623 struct ovsdb_datum_sort_cbdata {
 624     const struct ovsdb_type *type;
 625     struct ovsdb_datum *datum;
 626 };
 627
 628 static int
 629 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
 630 {
 631     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 632
 633     return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
 634                                    &cbdata->datum->keys[b],
 635                                    cbdata->type->key_type);
 636 }
 637
 638 static void
 639 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
 640 {
 641     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 642
 643     ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
 644     if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
 645         ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
 646     }
 647 }
 648
 649 struct ovsdb_error *
 650 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 651 {
 652     if (datum->n < 2) {
 653         return NULL;
 654     } else {
 655         struct ovsdb_datum_sort_cbdata cbdata;
 656         size_t i;
 657
 658         cbdata.type = type;
 659         cbdata.datum = datum;
 660         sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
 661              &cbdata);
 662
 663         for (i = 0; i < datum->n - 1; i++) {
 664             if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
 665                                   type->key_type)) {
 666                 if (ovsdb_type_is_map(type)) {
 667                     return ovsdb_error(NULL, "map contains duplicate key");
 668                 } else {
 669                     return ovsdb_error(NULL, "set contains duplicate");
 670                 }
 671             }
 672         }
 673
 674         return NULL;
 675     }
 676 }
 677
 678 struct ovsdb_error *
 679 ovsdb_datum_from_json(struct ovsdb_datum *datum,
 680                       const struct ovsdb_type *type,
 681                       const struct json *json,
 682                       const struct ovsdb_symbol_table *symtab)
 683 {
 684     struct ovsdb_error *error;
 685
 686     if (ovsdb_type_is_scalar(type)) {
 687         datum->n = 1;
 688         datum->keys = xmalloc(sizeof *datum->keys);
 689         datum->values = NULL;
 690
 691         error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
 692                                      json, symtab);
 693         if (error) {
 694             free(datum->keys);
 695         }
 696         return error;
 697     } else {
 698         bool is_map = ovsdb_type_is_map(type);
 699         const char *class = is_map ? "map" : "set";
 700         const struct json *inner;
 701         unsigned int i;
 702         size_t n;
 703
 704         assert(is_map || ovsdb_type_is_set(type));
 705
 706         error = unwrap_json(json, class, JSON_ARRAY, &inner);
 707         if (error) {
 708             return error;
 709         }
 710
 711         n = inner->u.array.n;
 712         if (n < type->n_min || n > type->n_max) {
 713             return ovsdb_syntax_error(json, NULL, "%s must have %u to "
 714                                       "%u members but %zu are present",
 715                                       class, type->n_min, type->n_max, n);
 716         }
 717
 718         datum->n = 0;
 719         datum->keys = xmalloc(n * sizeof *datum->keys);
 720         datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
 721         for (i = 0; i < n; i++) {
 722             const struct json *element = inner->u.array.elems[i];
 723             const struct json *key = NULL;
 724             const struct json *value = NULL;
 725
 726             if (!is_map) {
 727                 key = element;
 728             } else {
 729                 error = parse_json_pair(element, &key, &value);
 730                 if (error) {
 731                     goto error;
 732                 }
 733             }
 734
 735             error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
 736                                          key, symtab);
 737             if (error) {
 738                 goto error;
 739             }
 740
 741             if (is_map) {
 742                 error = ovsdb_atom_from_json(&datum->values[i],
 743                                              type->value_type, value, symtab);
 744                 if (error) {
 745                     ovsdb_atom_destroy(&datum->keys[i], type->key_type);
 746                     goto error;
 747                 }
 748             }
 749
 750             datum->n++;
 751         }
 752
 753         error = ovsdb_datum_sort(datum, type);
 754         if (error) {
 755             goto error;
 756         }
 757
 758         return NULL;
 759
 760     error:
 761         ovsdb_datum_destroy(datum, type);
 762         return error;
 763     }
 764 }
 765
 766 struct json *
 767 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
 768                     const struct ovsdb_type *type)
 769 {
 770     /* These tests somewhat tolerate a 'datum' that does not exactly match
 771      * 'type', in particular a datum with 'n' not in the allowed range. */
 772     if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
 773         return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
 774     } else if (type->value_type == OVSDB_TYPE_VOID) {
 775         struct json **elems;
 776         size_t i;
 777
 778         elems = xmalloc(datum->n * sizeof *elems);
 779         for (i = 0; i < datum->n; i++) {
 780             elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
 781         }
 782
 783         return wrap_json("set", json_array_create(elems, datum->n));
 784     } else {
 785         struct json **elems;
 786         size_t i;
 787
 788         elems = xmalloc(datum->n * sizeof *elems);
 789         for (i = 0; i < datum->n; i++) {
 790             elems[i] = json_array_create_2(
 791                 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
 792                 ovsdb_atom_to_json(&datum->values[i], type->value_type));
 793         }
 794
 795         return wrap_json("map", json_array_create(elems, datum->n));
 796     }
 797 }
 798
 799 static const char *
 800 skip_spaces(const char *p)
 801 {
 802     return p + strspn(p, " ");
 803 }
 804
 805 static const char *
 806 parse_key_value(const char *s, const struct ovsdb_type *type,
 807                 union ovsdb_atom *key, union ovsdb_atom *value)
 808 {
 809     char *key_string;
 810     const char *p;
 811
 812     /* Parse key. */
 813     p = ovsdb_token_parse(s, &key_string);
 814     ovsdb_atom_from_string(key, type->key_type, key_string);
 815     free(key_string);
 816
 817     /* Parse value. */
 818     if (type->value_type != OVSDB_TYPE_VOID) {
 819         char *value_string;
 820
 821         if (*p != '=') {
 822             ovs_fatal(0, "%s: syntax error at \"%c\" expecting \"=\"",
 823                       s, *p);
 824         }
 825         p = ovsdb_token_parse(p + 1, &value_string);
 826         ovsdb_atom_from_string(value, type->value_type, value_string);
 827         free(value_string);
 828     }
 829     return p;
 830 }
 831
 832 static void
 833 free_key_value(const struct ovsdb_type *type,
 834                union ovsdb_atom *key, union ovsdb_atom *value)
 835 {
 836     ovsdb_atom_destroy(key, type->key_type);
 837     if (type->value_type != OVSDB_TYPE_VOID) {
 838         ovsdb_atom_destroy(value, type->value_type);
 839     }
 840 }
 841
 842 /* Initializes 'datum' as a datum of the given 'type', parsing its contents
 843  * from 's'.  The format of 's' is a series of space or comma separated atoms
 844  * or, for a map, '='-delimited pairs of atoms.  Each atom must in a format
 845  * acceptable to ovsdb_atom_from_string().  Optionally, a set may be enclosed
 846  * in "[]" or a map in "{}"; for an empty set or map these punctuators are
 847  * required. */
 848 void
 849 ovsdb_datum_from_string(struct ovsdb_datum *datum,
 850                         const struct ovsdb_type *type, const char *s)
 851 {
 852     bool is_map = ovsdb_type_is_map(type);
 853     const char *p;
 854     int end_delim;
 855
 856     ovsdb_datum_init_empty(datum);
 857
 858     /* Swallow a leading delimiter if there is one. */
 859     p = skip_spaces(s);
 860     if (*p == (is_map ? '{' : '[')) {
 861         end_delim = is_map ? '}' : ']';
 862         p = skip_spaces(p + 1);
 863     } else if (!*p) {
 864         if (is_map) {
 865             ovs_fatal(0, "use \"{}\" to specify the empty map");
 866         } else {
 867             ovs_fatal(0, "use \"[]\" to specify the empty set");
 868         }
 869     } else {
 870         end_delim = 0;
 871     }
 872
 873     while (*p && *p != end_delim) {
 874         union ovsdb_atom key, value;
 875
 876         if (ovsdb_token_is_delim(*p)) {
 877             ovs_fatal(0, "%s: unexpected \"%c\" parsing %s",
 878                       s, *p, ovsdb_type_to_english(type));
 879         }
 880
 881         /* Add to datum. */
 882         p = parse_key_value(p, type, &key, &value);
 883         ovsdb_datum_add_unsafe(datum, &key, &value, type);
 884         free_key_value(type, &key, &value);
 885
 886         /* Skip optional white space and comma. */
 887         p = skip_spaces(p);
 888         if (*p == ',') {
 889             p = skip_spaces(p + 1);
 890         }
 891     }
 892
 893     if (*p != end_delim) {
 894         ovs_fatal(0, "%s: missing \"%c\" at end of data", s, end_delim);
 895     }
 896     if (end_delim) {
 897         p = skip_spaces(p + 1);
 898         if (*p) {
 899             ovs_fatal(0, "%s: trailing garbage after \"%c\"", s, end_delim);
 900         }
 901     }
 902
 903     if (datum->n < type->n_min) {
 904         ovs_fatal(0, "%s: %u %s were specified but at least %u are required",
 905                   s, datum->n,
 906                   type->value_type == OVSDB_TYPE_VOID ? "values" : "pairs",
 907                   type->n_min);
 908     } else if (datum->n > type->n_max) {
 909         ovs_fatal(0, "%s: %u %s were specified but at most %u are allowed",
 910                   s, datum->n,
 911                   type->value_type == OVSDB_TYPE_VOID ? "values" : "pairs",
 912                   type->n_max);
 913     }
 914
 915     if (ovsdb_datum_sort(datum, type)) {
 916         if (ovsdb_type_is_map(type)) {
 917             ovs_fatal(0, "%s: map contains duplicate key", s);
 918         } else {
 919             ovs_fatal(0, "%s: set contains duplicate value", s);
 920         }
 921     }
 922 }
 923
 924 /* Appends to 'out' the 'datum' (with the given 'type') in a format acceptable
 925  * to ovsdb_datum_from_string(). */
 926 void
 927 ovsdb_datum_to_string(const struct ovsdb_datum *datum,
 928                       const struct ovsdb_type *type, struct ds *out)
 929 {
 930     bool is_map = ovsdb_type_is_map(type);
 931     size_t i;
 932
 933     if (type->n_max > 1 || !datum->n) {
 934         ds_put_char(out, is_map ? '{' : '[');
 935     }
 936     for (i = 0; i < datum->n; i++) {
 937         if (i > 0) {
 938             ds_put_cstr(out, ", ");
 939         }
 940
 941         ovsdb_atom_to_string(&datum->keys[i], type->key_type, out);
 942         if (is_map) {
 943             ds_put_char(out, '=');
 944             ovsdb_atom_to_string(&datum->values[i], type->value_type, out);
 945         }
 946     }
 947     if (type->n_max > 1 || !datum->n) {
 948         ds_put_char(out, is_map ? '}' : ']');
 949     }
 950 }
 951
 952 static uint32_t
 953 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
 954            unsigned int n, uint32_t basis)
 955 {
 956     if (type != OVSDB_TYPE_VOID) {
 957         unsigned int i;
 958
 959         for (i = 0; i < n; i++) {
 960             basis = ovsdb_atom_hash(&atoms[i], type, basis);
 961         }
 962     }
 963     return basis;
 964 }
 965
 966 uint32_t
 967 ovsdb_datum_hash(const struct ovsdb_datum *datum,
 968                  const struct ovsdb_type *type, uint32_t basis)
 969 {
 970     basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
 971     basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
 972     basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
 973     return basis;
 974 }
 975
 976 static int
 977 atom_arrays_compare_3way(const union ovsdb_atom *a,
 978                          const union ovsdb_atom *b,
 979                          enum ovsdb_atomic_type type,
 980                          size_t n)
 981 {
 982     unsigned int i;
 983
 984     for (i = 0; i < n; i++) {
 985         int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
 986         if (cmp) {
 987             return cmp;
 988         }
 989     }
 990
 991     return 0;
 992 }
 993
 994 bool
 995 ovsdb_datum_equals(const struct ovsdb_datum *a,
 996                    const struct ovsdb_datum *b,
 997                    const struct ovsdb_type *type)
 998 {
 999     return !ovsdb_datum_compare_3way(a, b, type);
1000 }
1001
1002 int
1003 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
1004                          const struct ovsdb_datum *b,
1005                          const struct ovsdb_type *type)
1006 {
1007     int cmp;
1008
1009     if (a->n != b->n) {
1010         return a->n < b->n ? -1 : 1;
1011     }
1012
1013     cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
1014     if (cmp) {
1015         return cmp;
1016     }
1017
1018     return (type->value_type == OVSDB_TYPE_VOID ? 0
1019             : atom_arrays_compare_3way(a->values, b->values, type->value_type,
1020                                        a->n));
1021 }
1022
1023 /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
1024  * otherwise UINT_MAX.  'key_type' must be the type of the atoms stored in the
1025  * 'keys' array in 'datum'.
1026  */
1027 unsigned int
1028 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
1029                      const union ovsdb_atom *key,
1030                      enum ovsdb_atomic_type key_type)
1031 {
1032     unsigned int low = 0;
1033     unsigned int high = datum->n;
1034     while (low < high) {
1035         unsigned int idx = (low + high) / 2;
1036         int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
1037         if (cmp < 0) {
1038             high = idx;
1039         } else if (cmp > 0) {
1040             low = idx + 1;
1041         } else {
1042             return idx;
1043         }
1044     }
1045     return UINT_MAX;
1046 }
1047
1048 /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
1049  * index within 'datum', otherwise UINT_MAX.  'key_type' must be the type of
1050  * the atoms stored in the 'keys' array in 'datum'.  'value_type' may be the
1051  * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
1052  */
1053 unsigned int
1054 ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
1055                            const union ovsdb_atom *key,
1056                            enum ovsdb_atomic_type key_type,
1057                            const union ovsdb_atom *value,
1058                            enum ovsdb_atomic_type value_type)
1059 {
1060     unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
1061     if (idx != UINT_MAX
1062         && value_type != OVSDB_TYPE_VOID
1063         && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
1064         idx = UINT_MAX;
1065     }
1066     return idx;
1067 }
1068
1069 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
1070  * UINT_MAX.  'type' must be the type of 'a' and 'b', except that
1071  * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
1072  * values. */
1073 static unsigned int
1074 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
1075                  const struct ovsdb_datum *b,
1076                  const struct ovsdb_type *type)
1077 {
1078     return ovsdb_datum_find_key_value(b,
1079                                       &a->keys[i], type->key_type,
1080                                       a->values ? &a->values[i] : NULL,
1081                                       type->value_type);
1082 }
1083
1084 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
1085 bool
1086 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
1087                          const struct ovsdb_datum *b,
1088                          const struct ovsdb_type *type)
1089 {
1090     size_t i;
1091
1092     for (i = 0; i < a->n; i++) {
1093         if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
1094             return false;
1095         }
1096     }
1097     return true;
1098 }
1099
1100 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
1101 bool
1102 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
1103                          const struct ovsdb_datum *b,
1104                          const struct ovsdb_type *type)
1105 {
1106     size_t i;
1107
1108     for (i = 0; i < a->n; i++) {
1109         if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
1110             return false;
1111         }
1112     }
1113     return true;
1114 }
1115
1116 static void
1117 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
1118                        unsigned int capacity)
1119 {
1120     a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
1121     if (type->value_type != OVSDB_TYPE_VOID) {
1122         a->values = xrealloc(a->values, capacity * sizeof *a->values);
1123     }
1124 }
1125
1126 /* Removes the element with index 'idx' from 'datum', which has type 'type'.
1127  * If 'idx' is not the last element in 'datum', then the removed element is
1128  * replaced by the (former) last element.
1129  *
1130  * This function does not maintain ovsdb_datum invariants.  Use
1131  * ovsdb_datum_sort() to check and restore these invariants. */
1132 void
1133 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
1134                           const struct ovsdb_type *type)
1135 {
1136     ovsdb_atom_destroy(&datum->keys[idx], type->key_type);
1137     datum->keys[idx] = datum->keys[datum->n - 1];
1138     if (type->value_type != OVSDB_TYPE_VOID) {
1139         ovsdb_atom_destroy(&datum->values[idx], type->value_type);
1140         datum->values[idx] = datum->values[datum->n - 1];
1141     }
1142     datum->n--;
1143 }
1144
1145 /* Adds the element with the given 'key' and 'value' to 'datum', which must
1146  * have the specified 'type'.
1147  *
1148  * This function always allocates memory, so it is not an efficient way to add
1149  * a number of elements to a datum.
1150  *
1151  * This function does not maintain ovsdb_datum invariants.  Use
1152  * ovsdb_datum_sort() to check and restore these invariants.  (But a datum with
1153  * 0 or 1 elements cannot violate the invariants anyhow.) */
1154 void
1155 ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
1156                        const union ovsdb_atom *key,
1157                        const union ovsdb_atom *value,
1158                        const struct ovsdb_type *type)
1159 {
1160     size_t idx = datum->n++;
1161     datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
1162     ovsdb_atom_clone(&datum->keys[idx], key, type->key_type);
1163     if (type->value_type != OVSDB_TYPE_VOID) {
1164         datum->values = xrealloc(datum->values,
1165                                  datum->n * sizeof *datum->values);
1166         ovsdb_atom_clone(&datum->values[idx], value, type->value_type);
1167     }
1168 }
1169
1170 void
1171 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
1172                   const struct ovsdb_type *type, bool replace)
1173 {
1174     unsigned int n;
1175     size_t bi;
1176
1177     n = a->n;
1178     for (bi = 0; bi < b->n; bi++) {
1179         unsigned int ai;
1180
1181         ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type);
1182         if (ai == UINT_MAX) {
1183             if (n == a->n) {
1184                 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
1185             }
1186             ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type);
1187             if (type->value_type != OVSDB_TYPE_VOID) {
1188                 ovsdb_atom_clone(&a->values[n], &b->values[bi],
1189                                  type->value_type);
1190             }
1191             n++;
1192         } else if (replace && type->value_type != OVSDB_TYPE_VOID) {
1193             ovsdb_atom_destroy(&a->values[ai], type->value_type);
1194             ovsdb_atom_clone(&a->values[ai], &b->values[bi],
1195                              type->value_type);
1196         }
1197     }
1198     if (n != a->n) {
1199         struct ovsdb_error *error;
1200         a->n = n;
1201         error = ovsdb_datum_sort(a, type);
1202         assert(!error);
1203     }
1204 }
1205
1206 void
1207 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
1208                      const struct ovsdb_datum *b,
1209                      const struct ovsdb_type *b_type)
1210 {
1211     bool changed = false;
1212     size_t i;
1213
1214     assert(a_type->key_type == b_type->key_type);
1215     assert(a_type->value_type == b_type->value_type
1216            || b_type->value_type == OVSDB_TYPE_VOID);
1217
1218     /* XXX The big-O of this could easily be improved. */
1219     for (i = 0; i < a->n; ) {
1220         unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
1221         if (idx != UINT_MAX) {
1222             changed = true;
1223             ovsdb_datum_remove_unsafe(a, i, a_type);
1224         } else {
1225             i++;
1226         }
1227     }
1228     if (changed) {
1229         struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
1230         assert(!error);
1231     }
1232 }
1233 \f
1234 struct ovsdb_symbol_table {
1235     struct shash sh;
1236 };
1237
1238 struct ovsdb_symbol_table *
1239 ovsdb_symbol_table_create(void)
1240 {
1241     struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
1242     shash_init(&symtab->sh);
1243     return symtab;
1244 }
1245
1246 void
1247 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
1248 {
1249     if (symtab) {
1250         struct shash_node *node, *next;
1251
1252         SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
1253             struct ovsdb_symbol *symbol = node->data;
1254             free(symbol);
1255             shash_delete(&symtab->sh, node);
1256         }
1257         shash_destroy(&symtab->sh);
1258         free(symtab);
1259     }
1260 }
1261
1262 struct ovsdb_symbol *
1263 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
1264                        const char *name)
1265 {
1266     return shash_find_data(&symtab->sh, name);
1267 }
1268
1269 void
1270 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
1271                        const struct uuid *uuid, bool used)
1272 {
1273     struct ovsdb_symbol *symbol;
1274
1275     assert(!ovsdb_symbol_table_get(symtab, name));
1276     symbol = xmalloc(sizeof *symbol);
1277     symbol->uuid = *uuid;
1278     symbol->used = used;
1279     shash_add(&symtab->sh, name, symbol);
1280 }
1281 \f
1282 /* Extracts a token from the beginning of 's' and returns a pointer just after
1283  * the token.  Stores the token itself into '*outp', which the caller is
1284  * responsible for freeing (with free()).
1285  *
1286  * If 's[0]' is a delimiter, the returned token is the empty string.
1287  *
1288  * A token extends from 's' to the first delimiter, as defined by
1289  * ovsdb_token_is_delim(), or until the end of the string.  A delimiter can be
1290  * escaped with a backslash, in which case the backslash does not appear in the
1291  * output.  Double quotes also cause delimiters to be ignored, but the double
1292  * quotes are retained in the output.  (Backslashes inside double quotes are
1293  * not removed, either.)
1294  */
1295 const char *
1296 ovsdb_token_parse(const char *s, char **outp)
1297 {
1298     const char *p;
1299     struct ds out;
1300     bool in_quotes;
1301
1302     ds_init(&out);
1303     in_quotes = false;
1304     for (p = s; *p != '\0'; ) {
1305         int c = *p++;
1306         if (c == '\\') {
1307             if (in_quotes) {
1308                 ds_put_char(&out, '\\');
1309             }
1310             if (!*p) {
1311                 ovs_fatal(0, "%s: backslash at end of argument", s);
1312             }
1313             ds_put_char(&out, *p++);
1314         } else if (!in_quotes && ovsdb_token_is_delim(c)) {
1315             p--;
1316             break;
1317         } else {
1318             ds_put_char(&out, c);
1319             if (c == '"') {
1320                 in_quotes = !in_quotes;
1321             }
1322         }
1323     }
1324     if (in_quotes) {
1325         ovs_fatal(0, "%s: quoted string extends past end of argument", s);
1326     }
1327     *outp = ds_cstr(&out);
1328     return p;
1329 }
1330
1331 /* Returns true if 'c' delimits tokens, or if 'c' is 0, and false otherwise. */
1332 bool
1333 ovsdb_token_is_delim(unsigned char c)
1334 {
1335     return strchr(":=, []{}", c) != NULL;
1336 }