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