]>
Commit | Line | Data |
---|---|---|
c532bf9d | 1 | /* Copyright (c) 2009, 2010 Nicira Networks |
f85f8ebb BP |
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> | |
e9f8f936 | 21 | #include <limits.h> |
f85f8ebb BP |
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 | ||
c532bf9d BP |
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 | ||
f85f8ebb BP |
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); | |
2d2d6d4a | 252 | const struct ovsdb_symbol *symbol; |
f85f8ebb BP |
253 | |
254 | ovsdb_error_destroy(error0); | |
255 | ||
2d2d6d4a BP |
256 | symbol = ovsdb_symbol_table_get(symtab, name); |
257 | if (symbol) { | |
258 | *uuid = symbol->uuid; | |
f85f8ebb BP |
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 | ||
2f47998b BP |
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 | ||
f85f8ebb BP |
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 | ||
c532bf9d BP |
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 | ||
f85f8ebb BP |
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 | ||
e9f8f936 | 496 | struct ovsdb_error * |
f85f8ebb BP |
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, | |
2f47998b BP |
672 | const union ovsdb_atom *b, |
673 | enum ovsdb_atomic_type type, | |
674 | size_t n) | |
f85f8ebb BP |
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 | ||
2f47998b BP |
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 | ||
e9f8f936 BP |
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) | |
f85f8ebb | 771 | { |
2f47998b BP |
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); | |
f85f8ebb BP |
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++) { | |
e9f8f936 | 787 | if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) { |
f85f8ebb BP |
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++) { | |
e9f8f936 | 803 | if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) { |
f85f8ebb BP |
804 | return false; |
805 | } | |
806 | } | |
807 | return true; | |
808 | } | |
e9f8f936 BP |
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 | ||
2f47998b BP |
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) | |
e9f8f936 | 829 | { |
2f47998b BP |
830 | ovsdb_atom_destroy(&datum->keys[idx], type->key_type); |
831 | datum->keys[idx] = datum->keys[datum->n - 1]; | |
e9f8f936 | 832 | if (type->value_type != OVSDB_TYPE_VOID) { |
2f47998b BP |
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); | |
e9f8f936 | 861 | } |
e9f8f936 BP |
862 | } |
863 | ||
864 | void | |
2f47998b BP |
865 | ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b, |
866 | const struct ovsdb_type *type, bool replace) | |
e9f8f936 | 867 | { |
e9f8f936 | 868 | unsigned int n; |
2f47998b | 869 | size_t bi; |
e9f8f936 | 870 | |
e9f8f936 | 871 | n = a->n; |
2f47998b BP |
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) { | |
e9f8f936 | 877 | if (n == a->n) { |
2f47998b | 878 | ovsdb_datum_reallocate(a, type, a->n + (b->n - bi)); |
e9f8f936 | 879 | } |
2f47998b | 880 | ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type); |
e9f8f936 | 881 | if (type->value_type != OVSDB_TYPE_VOID) { |
2f47998b | 882 | ovsdb_atom_clone(&a->values[n], &b->values[bi], |
e9f8f936 BP |
883 | type->value_type); |
884 | } | |
885 | n++; | |
2f47998b BP |
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); | |
e9f8f936 BP |
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; | |
2f47998b | 917 | ovsdb_datum_remove_unsafe(a, i, a_type); |
e9f8f936 BP |
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 | } | |
f85f8ebb BP |
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) { | |
2d2d6d4a BP |
947 | struct ovsdb_symbol *symbol = node->data; |
948 | free(symbol); | |
f85f8ebb BP |
949 | shash_delete(&symtab->sh, node); |
950 | } | |
951 | shash_destroy(&symtab->sh); | |
952 | free(symtab); | |
953 | } | |
954 | } | |
955 | ||
2d2d6d4a | 956 | struct ovsdb_symbol * |
f85f8ebb BP |
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, | |
2d2d6d4a | 965 | const struct uuid *uuid, bool used) |
f85f8ebb | 966 | { |
2d2d6d4a BP |
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); | |
f85f8ebb | 974 | } |