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_empty(struct ovsdb_datum *datum)
 376 {
 377     datum->n = 0;
 378     datum->keys = NULL;
 379     datum->values = NULL;
 380 }
 381
 382 void
 383 ovsdb_datum_init_default(struct ovsdb_datum *datum,
 384                          const struct ovsdb_type *type)
 385 {
 386     datum->n = type->n_min;
 387     datum->keys = alloc_default_atoms(type->key_type, datum->n);
 388     datum->values = alloc_default_atoms(type->value_type, datum->n);
 389 }
 390
 391 bool
 392 ovsdb_datum_is_default(const struct ovsdb_datum *datum,
 393                        const struct ovsdb_type *type)
 394 {
 395     size_t i;
 396
 397     if (datum->n != type->n_min) {
 398         return false;
 399     }
 400     for (i = 0; i < datum->n; i++) {
 401         if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
 402             return false;
 403         }
 404         if (type->value_type != OVSDB_TYPE_VOID
 405             && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
 406             return false;
 407         }
 408     }
 409
 410     return true;
 411 }
 412
 413 static union ovsdb_atom *
 414 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 415 {
 416     if (type != OVSDB_TYPE_VOID && n) {
 417         union ovsdb_atom *new;
 418         unsigned int i;
 419
 420         new = xmalloc(n * sizeof *new);
 421         for (i = 0; i < n; i++) {
 422             ovsdb_atom_clone(&new[i], &old[i], type);
 423         }
 424         return new;
 425     } else {
 426         /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
 427          * treated as xmalloc(1). */
 428         return NULL;
 429     }
 430 }
 431
 432 void
 433 ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
 434                   const struct ovsdb_type *type)
 435 {
 436     unsigned int n = old->n;
 437     new->n = n;
 438     new->keys = clone_atoms(old->keys, type->key_type, n);
 439     new->values = clone_atoms(old->values, type->value_type, n);
 440 }
 441
 442 static void
 443 free_data(enum ovsdb_atomic_type type,
 444           union ovsdb_atom *atoms, size_t n_atoms)
 445 {
 446     if (ovsdb_atom_needs_destruction(type)) {
 447         unsigned int i;
 448         for (i = 0; i < n_atoms; i++) {
 449             ovsdb_atom_destroy(&atoms[i], type);
 450         }
 451     }
 452     free(atoms);
 453 }
 454
 455 void
 456 ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 457 {
 458     free_data(type->key_type, datum->keys, datum->n);
 459     free_data(type->value_type, datum->values, datum->n);
 460 }
 461
 462 void
 463 ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
 464 {
 465     struct ovsdb_datum tmp = *a;
 466     *a = *b;
 467     *b = tmp;
 468 }
 469
 470 struct ovsdb_datum_sort_cbdata {
 471     const struct ovsdb_type *type;
 472     struct ovsdb_datum *datum;
 473 };
 474
 475 static int
 476 ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
 477 {
 478     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 479
 480     return ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
 481                                    &cbdata->datum->keys[b],
 482                                    cbdata->type->key_type);
 483 }
 484
 485 static void
 486 ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
 487 {
 488     struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
 489
 490     ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
 491     if (cbdata->type->value_type != OVSDB_TYPE_VOID) {
 492         ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
 493     }
 494 }
 495
 496 struct ovsdb_error *
 497 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 498 {
 499     if (datum->n < 2) {
 500         return NULL;
 501     } else {
 502         struct ovsdb_datum_sort_cbdata cbdata;
 503         size_t i;
 504
 505         cbdata.type = type;
 506         cbdata.datum = datum;
 507         sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
 508              &cbdata);
 509
 510         for (i = 0; i < datum->n - 1; i++) {
 511             if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
 512                                   type->key_type)) {
 513                 if (ovsdb_type_is_map(type)) {
 514                     return ovsdb_error(NULL, "map contains duplicate key");
 515                 } else {
 516                     return ovsdb_error(NULL, "set contains duplicate");
 517                 }
 518             }
 519         }
 520
 521         return NULL;
 522     }
 523 }
 524
 525 struct ovsdb_error *
 526 ovsdb_datum_from_json(struct ovsdb_datum *datum,
 527                       const struct ovsdb_type *type,
 528                       const struct json *json,
 529                       const struct ovsdb_symbol_table *symtab)
 530 {
 531     struct ovsdb_error *error;
 532
 533     if (ovsdb_type_is_scalar(type)) {
 534         datum->n = 1;
 535         datum->keys = xmalloc(sizeof *datum->keys);
 536         datum->values = NULL;
 537
 538         error = ovsdb_atom_from_json(&datum->keys[0], type->key_type,
 539                                      json, symtab);
 540         if (error) {
 541             free(datum->keys);
 542         }
 543         return error;
 544     } else {
 545         bool is_map = ovsdb_type_is_map(type);
 546         const char *class = is_map ? "map" : "set";
 547         const struct json *inner;
 548         unsigned int i;
 549         size_t n;
 550
 551         assert(is_map || ovsdb_type_is_set(type));
 552
 553         error = unwrap_json(json, class, JSON_ARRAY, &inner);
 554         if (error) {
 555             return error;
 556         }
 557
 558         n = inner->u.array.n;
 559         if (n < type->n_min || n > type->n_max) {
 560             return ovsdb_syntax_error(json, NULL, "%s must have %u to "
 561                                       "%u members but %zu are present",
 562                                       class, type->n_min, type->n_max, n);
 563         }
 564
 565         datum->n = 0;
 566         datum->keys = xmalloc(n * sizeof *datum->keys);
 567         datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
 568         for (i = 0; i < n; i++) {
 569             const struct json *element = inner->u.array.elems[i];
 570             const struct json *key = NULL;
 571             const struct json *value = NULL;
 572
 573             if (!is_map) {
 574                 key = element;
 575             } else {
 576                 error = parse_json_pair(element, &key, &value);
 577                 if (error) {
 578                     goto error;
 579                 }
 580             }
 581
 582             error = ovsdb_atom_from_json(&datum->keys[i], type->key_type,
 583                                          key, symtab);
 584             if (error) {
 585                 goto error;
 586             }
 587
 588             if (is_map) {
 589                 error = ovsdb_atom_from_json(&datum->values[i],
 590                                              type->value_type, value, symtab);
 591                 if (error) {
 592                     ovsdb_atom_destroy(&datum->keys[i], type->key_type);
 593                     goto error;
 594                 }
 595             }
 596
 597             datum->n++;
 598         }
 599
 600         error = ovsdb_datum_sort(datum, type);
 601         if (error) {
 602             goto error;
 603         }
 604
 605         return NULL;
 606
 607     error:
 608         ovsdb_datum_destroy(datum, type);
 609         return error;
 610     }
 611 }
 612
 613 struct json *
 614 ovsdb_datum_to_json(const struct ovsdb_datum *datum,
 615                     const struct ovsdb_type *type)
 616 {
 617     /* These tests somewhat tolerate a 'datum' that does not exactly match
 618      * 'type', in particular a datum with 'n' not in the allowed range. */
 619     if (datum->n == 1 && ovsdb_type_is_scalar(type)) {
 620         return ovsdb_atom_to_json(&datum->keys[0], type->key_type);
 621     } else if (type->value_type == OVSDB_TYPE_VOID) {
 622         struct json **elems;
 623         size_t i;
 624
 625         elems = xmalloc(datum->n * sizeof *elems);
 626         for (i = 0; i < datum->n; i++) {
 627             elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key_type);
 628         }
 629
 630         return wrap_json("set", json_array_create(elems, datum->n));
 631     } else {
 632         struct json **elems;
 633         size_t i;
 634
 635         elems = xmalloc(datum->n * sizeof *elems);
 636         for (i = 0; i < datum->n; i++) {
 637             elems[i] = json_array_create_2(
 638                 ovsdb_atom_to_json(&datum->keys[i], type->key_type),
 639                 ovsdb_atom_to_json(&datum->values[i], type->value_type));
 640         }
 641
 642         return wrap_json("map", json_array_create(elems, datum->n));
 643     }
 644 }
 645
 646 static uint32_t
 647 hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
 648            unsigned int n, uint32_t basis)
 649 {
 650     if (type != OVSDB_TYPE_VOID) {
 651         unsigned int i;
 652
 653         for (i = 0; i < n; i++) {
 654             basis = ovsdb_atom_hash(&atoms[i], type, basis);
 655         }
 656     }
 657     return basis;
 658 }
 659
 660 uint32_t
 661 ovsdb_datum_hash(const struct ovsdb_datum *datum,
 662                  const struct ovsdb_type *type, uint32_t basis)
 663 {
 664     basis = hash_atoms(type->key_type, datum->keys, datum->n, basis);
 665     basis ^= (type->key_type << 24) | (type->value_type << 16) | datum->n;
 666     basis = hash_atoms(type->value_type, datum->values, datum->n, basis);
 667     return basis;
 668 }
 669
 670 static int
 671 atom_arrays_compare_3way(const union ovsdb_atom *a,
 672                          const union ovsdb_atom *b,
 673                          enum ovsdb_atomic_type type,
 674                          size_t n)
 675 {
 676     unsigned int i;
 677
 678     for (i = 0; i < n; i++) {
 679         int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
 680         if (cmp) {
 681             return cmp;
 682         }
 683     }
 684
 685     return 0;
 686 }
 687
 688 bool
 689 ovsdb_datum_equals(const struct ovsdb_datum *a,
 690                    const struct ovsdb_datum *b,
 691                    const struct ovsdb_type *type)
 692 {
 693     return !ovsdb_datum_compare_3way(a, b, type);
 694 }
 695
 696 int
 697 ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
 698                          const struct ovsdb_datum *b,
 699                          const struct ovsdb_type *type)
 700 {
 701     int cmp;
 702
 703     if (a->n != b->n) {
 704         return a->n < b->n ? -1 : 1;
 705     }
 706
 707     cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key_type, a->n);
 708     if (cmp) {
 709         return cmp;
 710     }
 711
 712     return (type->value_type == OVSDB_TYPE_VOID ? 0
 713             : atom_arrays_compare_3way(a->values, b->values, type->value_type,
 714                                        a->n));
 715 }
 716
 717 /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
 718  * otherwise UINT_MAX.  'key_type' must be the type of the atoms stored in the
 719  * 'keys' array in 'datum'.
 720  */
 721 unsigned int
 722 ovsdb_datum_find_key(const struct ovsdb_datum *datum,
 723                      const union ovsdb_atom *key,
 724                      enum ovsdb_atomic_type key_type)
 725 {
 726     unsigned int low = 0;
 727     unsigned int high = datum->n;
 728     while (low < high) {
 729         unsigned int idx = (low + high) / 2;
 730         int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
 731         if (cmp < 0) {
 732             high = idx;
 733         } else if (cmp > 0) {
 734             low = idx + 1;
 735         } else {
 736             return idx;
 737         }
 738     }
 739     return UINT_MAX;
 740 }
 741
 742 /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
 743  * index within 'datum', otherwise UINT_MAX.  'key_type' must be the type of
 744  * the atoms stored in the 'keys' array in 'datum'.  'value_type' may be the
 745  * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
 746  */
 747 unsigned int
 748 ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
 749                            const union ovsdb_atom *key,
 750                            enum ovsdb_atomic_type key_type,
 751                            const union ovsdb_atom *value,
 752                            enum ovsdb_atomic_type value_type)
 753 {
 754     unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
 755     if (idx != UINT_MAX
 756         && value_type != OVSDB_TYPE_VOID
 757         && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
 758         idx = UINT_MAX;
 759     }
 760     return idx;
 761 }
 762
 763 /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
 764  * UINT_MAX.  'type' must be the type of 'a' and 'b', except that
 765  * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
 766  * values. */
 767 static unsigned int
 768 ovsdb_datum_find(const struct ovsdb_datum *a, int i,
 769                  const struct ovsdb_datum *b,
 770                  const struct ovsdb_type *type)
 771 {
 772     return ovsdb_datum_find_key_value(b,
 773                                       &a->keys[i], type->key_type,
 774                                       a->values ? &a->values[i] : NULL,
 775                                       type->value_type);
 776 }
 777
 778 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
 779 bool
 780 ovsdb_datum_includes_all(const struct ovsdb_datum *a,
 781                          const struct ovsdb_datum *b,
 782                          const struct ovsdb_type *type)
 783 {
 784     size_t i;
 785
 786     for (i = 0; i < a->n; i++) {
 787         if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
 788             return false;
 789         }
 790     }
 791     return true;
 792 }
 793
 794 /* Returns true if no element in 'a' is also in 'b', false otherwise. */
 795 bool
 796 ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
 797                          const struct ovsdb_datum *b,
 798                          const struct ovsdb_type *type)
 799 {
 800     size_t i;
 801
 802     for (i = 0; i < a->n; i++) {
 803         if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
 804             return false;
 805         }
 806     }
 807     return true;
 808 }
 809
 810 static void
 811 ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
 812                        unsigned int capacity)
 813 {
 814     a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
 815     if (type->value_type != OVSDB_TYPE_VOID) {
 816         a->values = xrealloc(a->values, capacity * sizeof *a->values);
 817     }
 818 }
 819
 820 /* Removes the element with index 'idx' from 'datum', which has type 'type'.
 821  * If 'idx' is not the last element in 'datum', then the removed element is
 822  * replaced by the (former) last element.
 823  *
 824  * This function does not maintain ovsdb_datum invariants.  Use
 825  * ovsdb_datum_sort() to check and restore these invariants. */
 826 void
 827 ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
 828                           const struct ovsdb_type *type)
 829 {
 830     ovsdb_atom_destroy(&datum->keys[idx], type->key_type);
 831     datum->keys[idx] = datum->keys[datum->n - 1];
 832     if (type->value_type != OVSDB_TYPE_VOID) {
 833         ovsdb_atom_destroy(&datum->values[idx], type->value_type);
 834         datum->values[idx] = datum->values[datum->n - 1];
 835     }
 836     datum->n--;
 837 }
 838
 839 /* Adds the element with the given 'key' and 'value' to 'datum', which must
 840  * have the specified 'type'.
 841  *
 842  * This function always allocates memory, so it is not an efficient way to add
 843  * a number of elements to a datum.
 844  *
 845  * This function does not maintain ovsdb_datum invariants.  Use
 846  * ovsdb_datum_sort() to check and restore these invariants.  (But a datum with
 847  * 0 or 1 elements cannot violate the invariants anyhow.) */
 848 void
 849 ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
 850                        const union ovsdb_atom *key,
 851                        const union ovsdb_atom *value,
 852                        const struct ovsdb_type *type)
 853 {
 854     size_t idx = datum->n++;
 855     datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
 856     ovsdb_atom_clone(&datum->keys[idx], key, type->key_type);
 857     if (type->value_type != OVSDB_TYPE_VOID) {
 858         datum->values = xrealloc(datum->values,
 859                                  datum->n * sizeof *datum->values);
 860         ovsdb_atom_clone(&datum->values[idx], value, type->value_type);
 861     }
 862 }
 863
 864 void
 865 ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
 866                   const struct ovsdb_type *type, bool replace)
 867 {
 868     unsigned int n;
 869     size_t bi;
 870
 871     n = a->n;
 872     for (bi = 0; bi < b->n; bi++) {
 873         unsigned int ai;
 874
 875         ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type);
 876         if (ai == UINT_MAX) {
 877             if (n == a->n) {
 878                 ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
 879             }
 880             ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type);
 881             if (type->value_type != OVSDB_TYPE_VOID) {
 882                 ovsdb_atom_clone(&a->values[n], &b->values[bi],
 883                                  type->value_type);
 884             }
 885             n++;
 886         } else if (replace && type->value_type != OVSDB_TYPE_VOID) {
 887             ovsdb_atom_destroy(&a->values[ai], type->value_type);
 888             ovsdb_atom_clone(&a->values[ai], &b->values[bi],
 889                              type->value_type);
 890         }
 891     }
 892     if (n != a->n) {
 893         struct ovsdb_error *error;
 894         a->n = n;
 895         error = ovsdb_datum_sort(a, type);
 896         assert(!error);
 897     }
 898 }
 899
 900 void
 901 ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
 902                      const struct ovsdb_datum *b,
 903                      const struct ovsdb_type *b_type)
 904 {
 905     bool changed = false;
 906     size_t i;
 907
 908     assert(a_type->key_type == b_type->key_type);
 909     assert(a_type->value_type == b_type->value_type
 910            || b_type->value_type == OVSDB_TYPE_VOID);
 911
 912     /* XXX The big-O of this could easily be improved. */
 913     for (i = 0; i < a->n; ) {
 914         unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
 915         if (idx != UINT_MAX) {
 916             changed = true;
 917             ovsdb_datum_remove_unsafe(a, i, a_type);
 918         } else {
 919             i++;
 920         }
 921     }
 922     if (changed) {
 923         struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
 924         assert(!error);
 925     }
 926 }
 927 \f
 928 struct ovsdb_symbol_table {
 929     struct shash sh;
 930 };
 931
 932 struct ovsdb_symbol_table *
 933 ovsdb_symbol_table_create(void)
 934 {
 935     struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
 936     shash_init(&symtab->sh);
 937     return symtab;
 938 }
 939
 940 void
 941 ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
 942 {
 943     if (symtab) {
 944         struct shash_node *node, *next;
 945
 946         SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
 947             struct ovsdb_symbol *symbol = node->data;
 948             free(symbol);
 949             shash_delete(&symtab->sh, node);
 950         }
 951         shash_destroy(&symtab->sh);
 952         free(symtab);
 953     }
 954 }
 955
 956 struct ovsdb_symbol *
 957 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
 958                        const char *name)
 959 {
 960     return shash_find_data(&symtab->sh, name);
 961 }
 962
 963 void
 964 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
 965                        const struct uuid *uuid, bool used)
 966 {
 967     struct ovsdb_symbol *symbol;
 968
 969     assert(!ovsdb_symbol_table_get(symtab, name));
 970     symbol = xmalloc(sizeof *symbol);
 971     symbol->uuid = *uuid;
 972     symbol->used = used;
 973     shash_add(&symtab->sh, name, symbol);
 974 }