pintos-os.org Git - openvswitch/blob - lib/ovsdb-data.c

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