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