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 <limits.h>
  22
  23 #include "hash.h"
  24 #include "ovsdb-error.h"
  25 #include "json.h"
  26 #include "shash.h"
  27 #include "sort.h"
  28
  29 static struct json *
  30 wrap_json(const char *name, struct json *wrapped)
  31 {
  32     return json_array_create_2(json_string_create(name), wrapped);
  33 }
  34
  35 void
  36 ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
  37 {
  38     switch (type) {
  39     case OVSDB_TYPE_VOID:
  40         NOT_REACHED();
  41
  42     case OVSDB_TYPE_INTEGER:
  43         atom->integer = 0;
  44         break;
  45
  46     case OVSDB_TYPE_REAL:
  47         atom->real = 0.0;
  48         break;
  49
  50     case OVSDB_TYPE_BOOLEAN:
  51         atom->boolean = false;
  52         break;
  53
  54     case OVSDB_TYPE_STRING:
  55         atom->string = xmemdup("", 1);
  56         break;
  57
  58     case OVSDB_TYPE_UUID:
  59         uuid_zero(&atom->uuid);
  60         break;
  61
  62     case OVSDB_N_TYPES:
  63     default:
  64         NOT_REACHED();
  65     }
  66 }
  67
  68 bool
  69 ovsdb_atom_is_default(const union ovsdb_atom *atom,
  70                       enum ovsdb_atomic_type type)
  71 {
  72     switch (type) {
  73     case OVSDB_TYPE_VOID:
  74         NOT_REACHED();
  75
  76     case OVSDB_TYPE_INTEGER:
  77         return atom->integer == 0;
  78
  79     case OVSDB_TYPE_REAL:
  80         return atom->real == 0.0;
  81
  82     case OVSDB_TYPE_BOOLEAN:
  83         return atom->boolean == false;
  84
  85     case OVSDB_TYPE_STRING:
  86         return atom->string[0] == '\0';
  87
  88     case OVSDB_TYPE_UUID:
  89         return uuid_is_zero(&atom->uuid);
  90
  91     case OVSDB_N_TYPES:
  92     default:
  93         NOT_REACHED();
  94     }
  95 }
  96
  97 void
  98 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
  99                  enum ovsdb_atomic_type type)
 100 {
 101     switch (type) {
 102     case OVSDB_TYPE_VOID:
 103         NOT_REACHED();
 104
 105     case OVSDB_TYPE_INTEGER:
 106         new->integer = old->integer;
 107         break;
 108
 109     case OVSDB_TYPE_REAL:
 110         new->real = old->real;
 111         break;
 112
 113     case OVSDB_TYPE_BOOLEAN:
 114         new->boolean = old->boolean;
 115         break;
 116
 117     case OVSDB_TYPE_STRING:
 118         new->string = xstrdup(old->string);
 119         break;
 120
 121     case OVSDB_TYPE_UUID:
 122         new->uuid = old->uuid;
 123         break;
 124
 125     case OVSDB_N_TYPES:
 126     default:
 127         NOT_REACHED();
 128     }
 129 }
 130
 131 void
 132 ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
 133 {
 134     union ovsdb_atom tmp = *a;
 135     *a = *b;
 136     *b = tmp;
 137 }
 138
 139 uint32_t
 140 ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 141                 uint32_t basis)
 142 {
 143     switch (type) {
 144     case OVSDB_TYPE_VOID:
 145         NOT_REACHED();
 146
 147     case OVSDB_TYPE_INTEGER:
 148         return hash_int(atom->integer, basis);
 149
 150     case OVSDB_TYPE_REAL:
 151         return hash_double(atom->real, basis);
 152
 153     case OVSDB_TYPE_BOOLEAN:
 154         return hash_boolean(atom->boolean, basis);
 155
 156     case OVSDB_TYPE_STRING:
 157         return hash_string(atom->string, basis);
 158
 159     case OVSDB_TYPE_UUID:
 160         return hash_int(uuid_hash(&atom->uuid), basis);
 161
 162     case OVSDB_N_TYPES:
 163     default:
 164         NOT_REACHED();
 165     }
 166 }
 167
 168 int
 169 ovsdb_atom_compare_3way(const union ovsdb_atom *a,
 170                         const union ovsdb_atom *b,
 171                         enum ovsdb_atomic_type type)
 172 {
 173     switch (type) {
 174     case OVSDB_TYPE_VOID:
 175         NOT_REACHED();
 176
 177     case OVSDB_TYPE_INTEGER:
 178         return a->integer < b->integer ? -1 : a->integer > b->integer;
 179
 180     case OVSDB_TYPE_REAL:
 181         return a->real < b->real ? -1 : a->real > b->real;
 182
 183     case OVSDB_TYPE_BOOLEAN:
 184         return a->boolean - b->boolean;
 185
 186     case OVSDB_TYPE_STRING:
 187         return strcmp(a->string, b->string);
 188
 189     case OVSDB_TYPE_UUID:
 190         return uuid_compare_3way(&a->uuid, &b->uuid);
 191
 192     case OVSDB_N_TYPES:
 193     default:
 194         NOT_REACHED();
 195     }
 196 }
 197
 198 static struct ovsdb_error *
 199 unwrap_json(const struct json *json, const char *name,
 200             enum json_type value_type, const struct json **value)
 201 {
 202     if (json->type != JSON_ARRAY
 203         || json->u.array.n != 2
 204         || json->u.array.elems[0]->type != JSON_STRING
 205         || (name && strcmp(json->u.array.elems[0]->u.string, name))
 206         || json->u.array.elems[1]->type != value_type)
 207     {
 208         return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
 209                                   json_type_to_string(value_type));
 210     }
 211     *value = json->u.array.elems[1];
 212     return NULL;
 213 }
 214
 215 static struct ovsdb_error *
 216 parse_json_pair(const struct json *json,
 217                 const struct json **elem0, const struct json **elem1)
 218 {
 219     if (json->type != JSON_ARRAY || json->u.array.n != 2) {
 220         return ovsdb_syntax_error(json, NULL, "expected 2-element array");
 221     }
 222     *elem0 = json->u.array.elems[0];
 223     *elem1 = json->u.array.elems[1];
 224     return NULL;
 225 }
 226
 227 static struct ovsdb_error *
 228 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
 229                       const struct ovsdb_symbol_table *symtab)
 230     WARN_UNUSED_RESULT;
 231
 232 static struct ovsdb_error *
 233 ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
 234                       const 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             const struct ovsdb_symbol *symbol;
 253
 254             ovsdb_error_destroy(error0);
 255
 256             symbol = ovsdb_symbol_table_get(symtab, name);
 257             if (symbol) {
 258                 *uuid = symbol->uuid;
 259                 return NULL;
 260             } else {
 261                 return ovsdb_syntax_error(json, NULL,
 262                                           "unknown named-uuid \"%s\"", name);
 263             }
 264         }
 265         ovsdb_error_destroy(error1);
 266     }
 267
 268     return error0;
 269 }
 270
 271 struct ovsdb_error *
 272 ovsdb_atom_from_json(union ovsdb_atom *atom, enum ovsdb_atomic_type type,
 273                      const struct json *json,
 274                      const struct ovsdb_symbol_table *symtab)
 275 {
 276     switch (type) {
 277     case OVSDB_TYPE_VOID:
 278         NOT_REACHED();
 279
 280     case OVSDB_TYPE_INTEGER:
 281         if (json->type == JSON_INTEGER) {
 282             atom->integer = json->u.integer;
 283             return NULL;
 284         }
 285         break;
 286
 287     case OVSDB_TYPE_REAL:
 288         if (json->type == JSON_INTEGER) {
 289             atom->real = json->u.integer;
 290             return NULL;
 291         } else if (json->type == JSON_REAL) {
 292             atom->real = json->u.real;
 293             return NULL;
 294         }
 295         break;
 296
 297     case OVSDB_TYPE_BOOLEAN:
 298         if (json->type == JSON_TRUE) {
 299             atom->boolean = true;
 300             return NULL;
 301         } else if (json->type == JSON_FALSE) {
 302             atom->boolean = false;
 303             return NULL;
 304         }
 305         break;
 306
 307     case OVSDB_TYPE_STRING:
 308         if (json->type == JSON_STRING) {
 309             atom->string = xstrdup(json->u.string);
 310             return NULL;
 311         }
 312         break;
 313
 314     case OVSDB_TYPE_UUID:
 315         return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab);
 316
 317     case OVSDB_N_TYPES:
 318     default:
 319         NOT_REACHED();
 320     }
 321
 322     return ovsdb_syntax_error(json, NULL, "expected %s",
 323                               ovsdb_atomic_type_to_string(type));
 324 }
 325
 326 struct json *
 327 ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
 328 {
 329     switch (type) {
 330     case OVSDB_TYPE_VOID:
 331         NOT_REACHED();
 332
 333     case OVSDB_TYPE_INTEGER:
 334         return json_integer_create(atom->integer);
 335
 336     case OVSDB_TYPE_REAL:
 337         return json_real_create(atom->real);
 338
 339     case OVSDB_TYPE_BOOLEAN:
 340         return json_boolean_create(atom->boolean);
 341
 342     case OVSDB_TYPE_STRING:
 343         return json_string_create(atom->string);
 344
 345     case OVSDB_TYPE_UUID:
 346         return wrap_json("uuid", json_string_create_nocopy(
 347                              xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
 348
 349     case OVSDB_N_TYPES:
 350     default:
 351         NOT_REACHED();
 352     }
 353 }
 354 \f
 355 static union ovsdb_atom *
 356 alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
 357 {
 358     if (type != OVSDB_TYPE_VOID && n) {
 359         union ovsdb_atom *atoms;
 360         unsigned int i;
 361
 362         atoms = xmalloc(n * sizeof *atoms);
 363         for (i = 0; i < n; i++) {
 364             ovsdb_atom_init_default(&atoms[i], type);
 365         }
 366         return atoms;
 367     } else {
 368         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 369          * treated as xmalloc(1). */
 370         return NULL;
 371     }
 372 }
 373
 374 void
 375 ovsdb_datum_init_default(struct ovsdb_datum *datum,
 376                          const struct ovsdb_type *type)
 377 {
 378     datum->n = type->n_min;
 379     datum->keys = alloc_default_atoms(type->key_type, datum->n);
 380     datum->values = alloc_default_atoms(type->value_type, datum->n);
 381 }
 382
 383 bool
 384 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
 385                        const struct ovsdb_type *type)
 386 {
 387     size_t i;
 388
 389     if (datum->n != type->n_min) {
 390         return false;
 391     }
 392     for (i = 0; i < datum->n; i++) {
 393         if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
 394             return false;
 395         }
 396         if (type->value_type != OVSDB_TYPE_VOID
 397             && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
 398             return false;
 399         }
 400     }
 401
 402     return true;
 403 }
 404
 405 static union ovsdb_atom *
 406 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 407 {
 408     if (type != OVSDB_TYPE_VOID && n) {
 409         union ovsdb_atom *new;
 410         unsigned int i;
 411
 412         new = xmalloc(n * sizeof *new);
 413         for (i = 0; i < n; i++) {
 414             ovsdb_atom_clone(&new[i], &old[i], type);
 415         }
 416         return new;
 417     } else {
 418         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 419          * treated as xmalloc(1). */
 420         return NULL;
 421     }
 422 }
 423
 424 void
 425 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
 426                   const struct ovsdb_type *type)
 427 {
 428     unsigned int n = old->n;
 429     new->n = n;
 430     new->keys = clone_atoms(old->keys, type->key_type, n);
 431     new->values = clone_atoms(old->values, type->value_type, n);
 432 }
 433
 434 static void
 435 free_data(enum ovsdb_atomic_type type,
 436           union ovsdb_atom *atoms, size_t n_atoms)
 437 {
 438     if (ovsdb_atom_needs_destruction(type)) {
 439         unsigned int i;
 440         for (i = 0; i < n_atoms; i++) {
 441             ovsdb_atom_destroy(&atoms[i], type);
 442         }
 443     }
 444     free(atoms);
 445 }
 446
 447 void
 448 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 449 {
 450     free_data(type->key_type, datum->keys, datum->n);
 451     free_data(type->value_type, datum->values, datum->n);
 452 }
 453
 454 void
 455 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
 456 {
 457     struct ovsdb_datum tmp = *a;
 458     *a = *b;
 459     *b = tmp;
 460 }
 461
 462 struct ovsdb_datum_sort_cbdata {
 463     const struct ovsdb_type *type;
 464     struct ovsdb_datum *datum;
 465 };
 466
 467 static int
 468 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
 469 {
 470     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 471
 472     return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
 473                                    &cbdata->datum->keys[b],
 474                                    cbdata->type->key_type);
 475 }
 476
 477 static void
 478 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
 479 {
 480     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 481
 482     ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
 483     if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
 484         ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
 485     }
 486 }
 487
 488 struct ovsdb_error *
 489 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 490 {
 491     if (datum->n < 2) {
 492         return NULL;
 493     } else {
 494         struct ovsdb_datum_sort_cbdata cbdata;
 495         size_t i;
 496
 497         cbdata.type = type;
 498         cbdata.datum = datum;
 499         sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
 500              &cbdata);
 501
 502         for (i = 0; i < datum->n - 1; i++) {
 503             if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
 504                                   type->key_type)) {
 505                 if (ovsdb_type_is_map(type)) {
 506                     return ovsdb_error(NULL, "map contains duplicate key");
 507                 } else {
 508                     return ovsdb_error(NULL, "set contains duplicate");
 509                 }
 510             }
 511         }
 512
 513         return NULL;
 514     }
 515 }
 516
 517 struct ovsdb_error *
 518 ovsdb_datum_from_json(struct ovsdb_datum *datum,
 519                       const struct ovsdb_type *type,
 520                       const struct json *json,
 521                       const struct ovsdb_symbol_table *symtab)
 522 {
 523     struct ovsdb_error *error;
 524
 525     if (ovsdb_type_is_scalar(type)) {
 526         datum->n = 1;
 527         datum->keys = xmalloc(sizeof *datum->keys);
 528         datum->values = NULL;
 529
 530         error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
 531                                      json, symtab);
 532         if (error) {
 533             free(datum->keys);
 534         }
 535         return error;
 536     } else {
 537         bool is_map = ovsdb_type_is_map(type);
 538         const char *class = is_map ? "map" : "set";
 539         const struct json *inner;
 540         unsigned int i;
 541         size_t n;
 542
 543         assert(is_map || ovsdb_type_is_set(type));
 544
 545         error = unwrap_json(json, class, JSON_ARRAY, &inner);
 546         if (error) {
 547             return error;
 548         }
 549
 550         n = inner->u.array.n;
 551         if (n < type->n_min || n > type->n_max) {
 552             return ovsdb_syntax_error(json, NULL, "%s must have %u to "
 553                                       "%u members but %zu are present",
 554                                       class, type->n_min, type->n_max, n);
 555         }
 556
 557         datum->n = 0;
 558         datum->keys = xmalloc(n * sizeof *datum->keys);
 559         datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
 560         for (i = 0; i < n; i++) {
 561             const struct json *element = inner->u.array.elems[i];
 562             const struct json *key = NULL;
 563             const struct json *value = NULL;
 564
 565             if (!is_map) {
 566                 key = element;
 567             } else {
 568                 error = parse_json_pair(element, &key, &value);
 569                 if (error) {
 570                     goto error;
 571                 }
 572             }
 573
 574             error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
 575                                          key, symtab);
 576             if (error) {
 577                 goto error;
 578             }
 579
 580             if (is_map) {
 581                 error = ovsdb_atom_from_json(&datum->values[i],
 582                                              type->value_type, value, symtab);
 583                 if (error) {
 584                     ovsdb_atom_destroy(&datum->keys[i], type->key_type);
 585                     goto error;
 586                 }
 587             }
 588
 589             datum->n++;
 590         }
 591
 592         error = ovsdb_datum_sort(datum, type);
 593         if (error) {
 594             goto error;
 595         }
 596
 597         return NULL;
 598
 599     error:
 600         ovsdb_datum_destroy(datum, type);
 601         return error;
 602     }
 603 }
 604
 605 struct json *
 606 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
 607                     const struct ovsdb_type *type)
 608 {
 609     /* These tests somewhat tolerate a 'datum' that does not exactly match
 610      * 'type', in particular a datum with 'n' not in the allowed range. */
 611     if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
 612         return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
 613     } else if (type->value_type == OVSDB_TYPE_VOID) {
 614         struct json **elems;
 615         size_t i;
 616
 617         elems = xmalloc(datum->n * sizeof *elems);
 618         for (i = 0; i < datum->n; i++) {
 619             elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
 620         }
 621
 622         return wrap_json("set", json_array_create(elems, datum->n));
 623     } else {
 624         struct json **elems;
 625         size_t i;
 626
 627         elems = xmalloc(datum->n * sizeof *elems);
 628         for (i = 0; i < datum->n; i++) {
 629             elems[i] = json_array_create_2(
 630                 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
 631                 ovsdb_atom_to_json(&datum->values[i], type->value_type));
 632         }
 633
 634         return wrap_json("map", json_array_create(elems, datum->n));
 635     }
 636 }
 637
 638 static uint32_t
 639 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
 640            unsigned int n, uint32_t basis)
 641 {
 642     if (type != OVSDB_TYPE_VOID) {
 643         unsigned int i;
 644
 645         for (i = 0; i < n; i++) {
 646             basis = ovsdb_atom_hash(&atoms[i], type, basis);
 647         }
 648     }
 649     return basis;
 650 }
 651
 652 uint32_t
 653 ovsdb_datum_hash(const struct ovsdb_datum *datum,
 654                  const struct ovsdb_type *type, uint32_t basis)
 655 {
 656     basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
 657     basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
 658     basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
 659     return basis;
 660 }
 661
 662 static int
 663 atom_arrays_compare_3way(const union ovsdb_atom *a,
 664                   const union ovsdb_atom *b,
 665                   enum ovsdb_atomic_type type,
 666                   size_t n)
 667 {
 668     unsigned int i;
 669
 670     for (i = 0; i < n; i++) {
 671         int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
 672         if (cmp) {
 673             return cmp;
 674         }
 675     }
 676
 677     return 0;
 678 }
 679
 680 bool
 681 ovsdb_datum_equals(const struct ovsdb_datum *a,
 682                    const struct ovsdb_datum *b,
 683                    const struct ovsdb_type *type)
 684 {
 685     return !ovsdb_datum_compare_3way(a, b, type);
 686 }
 687
 688 int
 689 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
 690                          const struct ovsdb_datum *b,
 691                          const struct ovsdb_type *type)
 692 {
 693     int cmp;
 694
 695     if (a->n != b->n) {
 696         return a->n < b->n ? -1 : 1;
 697     }
 698
 699     cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
 700     if (cmp) {
 701         return cmp;
 702     }
 703
 704     return (type->value_type == OVSDB_TYPE_VOID ? 0
 705             : atom_arrays_compare_3way(a->values, b->values, type->value_type,
 706                                        a->n));
 707 }
 708
 709 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
 710  * UINT_MAX.  'type' must be the type of 'a' and 'b', except that
 711  * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
 712  * values. */
 713 static unsigned int
 714 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
 715                  const struct ovsdb_datum *b,
 716                  const struct ovsdb_type *type)
 717 {
 718     int low = 0;
 719     int high = b->n;
 720     while (low < high) {
 721         int j = (low + high) / 2;
 722         int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j],
 723                                           type->key_type);
 724         if (cmp < 0) {
 725             high = j;
 726         } else if (cmp > 0) {
 727             low = j + 1;
 728         } else {
 729             bool eq_value = (type->value_type == OVSDB_TYPE_VOID
 730                              || ovsdb_atom_equals(&a->values[i], &b->values[j],
 731                                                   type->value_type));
 732             return eq_value ? j : UINT_MAX;
 733         }
 734     }
 735     return UINT_MAX;
 736 }
 737
 738 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
 739 bool
 740 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
 741                          const struct ovsdb_datum *b,
 742                          const struct ovsdb_type *type)
 743 {
 744     size_t i;
 745
 746     for (i = 0; i < a->n; i++) {
 747         if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
 748             return false;
 749         }
 750     }
 751     return true;
 752 }
 753
 754 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
 755 bool
 756 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
 757                          const struct ovsdb_datum *b,
 758                          const struct ovsdb_type *type)
 759 {
 760     size_t i;
 761
 762     for (i = 0; i < a->n; i++) {
 763         if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
 764             return false;
 765         }
 766     }
 767     return true;
 768 }
 769
 770 static void
 771 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
 772                        unsigned int capacity)
 773 {
 774     a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
 775     if (type->value_type != OVSDB_TYPE_VOID) {
 776         a->values = xrealloc(a->values, capacity * sizeof *a->values);
 777     }
 778 }
 779
 780 static void
 781 ovsdb_datum_remove(struct ovsdb_datum *a, size_t i,
 782                    const struct ovsdb_type *type)
 783 {
 784     ovsdb_atom_destroy(&a->keys[i], type->key_type);
 785     a->keys[i] = a->keys[a->n - 1];
 786     if (type->value_type != OVSDB_TYPE_VOID) {
 787         ovsdb_atom_destroy(&a->values[i], type->value_type);
 788         a->values[i] = a->values[a->n - 1];
 789     }
 790     a->n--;
 791 }
 792
 793 void
 794 ovsdb_datum_union(struct ovsdb_datum *a,
 795                   const struct ovsdb_datum *b, const struct ovsdb_type *type)
 796 {
 797     struct ovsdb_type type_without_value;
 798     unsigned int n;
 799     size_t i;
 800
 801     type_without_value = *type;
 802     type_without_value.value_type = OVSDB_TYPE_VOID;
 803     n = a->n;
 804     for (i = 0; i < b->n; i++) {
 805         if (ovsdb_datum_find(b, i, a, &type_without_value) == UINT_MAX) {
 806             if (n == a->n) {
 807                 ovsdb_datum_reallocate(a, type, a->n + (b->n - i));
 808             }
 809             ovsdb_atom_clone(&a->keys[n], &b->keys[i], type->key_type);
 810             if (type->value_type != OVSDB_TYPE_VOID) {
 811                 ovsdb_atom_clone(&a->values[n], &b->values[i],
 812                                  type->value_type);
 813             }
 814             n++;
 815         }
 816     }
 817     if (n != a->n) {
 818         struct ovsdb_error *error;
 819         a->n = n;
 820         error = ovsdb_datum_sort(a, type);
 821         assert(!error);
 822     }
 823 }
 824
 825 void
 826 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
 827                      const struct ovsdb_datum *b,
 828                      const struct ovsdb_type *b_type)
 829 {
 830     bool changed = false;
 831     size_t i;
 832
 833     assert(a_type->key_type == b_type->key_type);
 834     assert(a_type->value_type == b_type->value_type
 835            || b_type->value_type == OVSDB_TYPE_VOID);
 836
 837     /* XXX The big-O of this could easily be improved. */
 838     for (i = 0; i < a->n; ) {
 839         unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
 840         if (idx != UINT_MAX) {
 841             changed = true;
 842             ovsdb_datum_remove(a, i, a_type);
 843         } else {
 844             i++;
 845         }
 846     }
 847     if (changed) {
 848         struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
 849         assert(!error);
 850     }
 851 }
 852 \f
 853 struct ovsdb_symbol_table {
 854     struct shash sh;
 855 };
 856
 857 struct ovsdb_symbol_table *
 858 ovsdb_symbol_table_create(void)
 859 {
 860     struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
 861     shash_init(&symtab->sh);
 862     return symtab;
 863 }
 864
 865 void
 866 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
 867 {
 868     if (symtab) {
 869         struct shash_node *node, *next;
 870
 871         SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
 872             struct ovsdb_symbol *symbol = node->data;
 873             free(symbol);
 874             shash_delete(&symtab->sh, node);
 875         }
 876         shash_destroy(&symtab->sh);
 877         free(symtab);
 878     }
 879 }
 880
 881 struct ovsdb_symbol *
 882 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
 883                        const char *name)
 884 {
 885     return shash_find_data(&symtab->sh, name);
 886 }
 887
 888 void
 889 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
 890                        const struct uuid *uuid, bool used)
 891 {
 892     struct ovsdb_symbol *symbol;
 893
 894     assert(!ovsdb_symbol_table_get(symtab, name));
 895     symbol = xmalloc(sizeof *symbol);
 896     symbol->uuid = *uuid;
 897     symbol->used = used;
 898     shash_add(&symtab->sh, name, symbol);
 899 }