From 2f47998baea215b996af0be4d1653032005e3ac4 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 25 Jan 2010 10:08:57 -0800 Subject: [PATCH] ovsdb-data: Add some more functions for dealing with "struct ovsdb_datum". This commit refactors the functions for working with "struct ovsdb_datum", adding and exposing some more operations for ovs-vsctl to use in an upcoming commit. --- lib/ovsdb-data.c | 157 ++++++++++++++++++++++++++++++++++------------- lib/ovsdb-data.h | 53 ++++++++++++---- ovsdb/mutation.c | 4 +- 3 files changed, 160 insertions(+), 54 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 65fd43e69..6d9edb414 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -371,6 +371,14 @@ alloc_default_atoms(enum ovsdb_atomic_type type, size_t n) } } +void +ovsdb_datum_init_empty(struct ovsdb_datum *datum) +{ + datum->n = 0; + datum->keys = NULL; + datum->values = NULL; +} + void ovsdb_datum_init_default(struct ovsdb_datum *datum, const struct ovsdb_type *type) @@ -661,9 +669,9 @@ ovsdb_datum_hash(const struct ovsdb_datum *datum, static int atom_arrays_compare_3way(const union ovsdb_atom *a, - const union ovsdb_atom *b, - enum ovsdb_atomic_type type, - size_t n) + const union ovsdb_atom *b, + enum ovsdb_atomic_type type, + size_t n) { unsigned int i; @@ -706,6 +714,52 @@ ovsdb_datum_compare_3way(const struct ovsdb_datum *a, a->n)); } +/* If 'key' is one of the keys in 'datum', returns its index within 'datum', + * otherwise UINT_MAX. 'key_type' must be the type of the atoms stored in the + * 'keys' array in 'datum'. + */ +unsigned int +ovsdb_datum_find_key(const struct ovsdb_datum *datum, + const union ovsdb_atom *key, + enum ovsdb_atomic_type key_type) +{ + unsigned int low = 0; + unsigned int high = datum->n; + while (low < high) { + unsigned int idx = (low + high) / 2; + int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type); + if (cmp < 0) { + high = idx; + } else if (cmp > 0) { + low = idx + 1; + } else { + return idx; + } + } + return UINT_MAX; +} + +/* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its + * index within 'datum', otherwise UINT_MAX. 'key_type' must be the type of + * the atoms stored in the 'keys' array in 'datum'. 'value_type' may be the + * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys. + */ +unsigned int +ovsdb_datum_find_key_value(const struct ovsdb_datum *datum, + const union ovsdb_atom *key, + enum ovsdb_atomic_type key_type, + const union ovsdb_atom *value, + enum ovsdb_atomic_type value_type) +{ + unsigned int idx = ovsdb_datum_find_key(datum, key, key_type); + if (idx != UINT_MAX + && value_type != OVSDB_TYPE_VOID + && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) { + idx = UINT_MAX; + } + return idx; +} + /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise * UINT_MAX. 'type' must be the type of 'a' and 'b', except that * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not @@ -715,24 +769,10 @@ ovsdb_datum_find(const struct ovsdb_datum *a, int i, const struct ovsdb_datum *b, const struct ovsdb_type *type) { - int low = 0; - int high = b->n; - while (low < high) { - int j = (low + high) / 2; - int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j], - type->key_type); - if (cmp < 0) { - high = j; - } else if (cmp > 0) { - low = j + 1; - } else { - bool eq_value = (type->value_type == OVSDB_TYPE_VOID - || ovsdb_atom_equals(&a->values[i], &b->values[j], - type->value_type)); - return eq_value ? j : UINT_MAX; - } - } - return UINT_MAX; + return ovsdb_datum_find_key_value(b, + &a->keys[i], type->key_type, + a->values ? &a->values[i] : NULL, + type->value_type); } /* Returns true if every element in 'a' is also in 'b', false otherwise. */ @@ -777,41 +817,76 @@ ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type, } } -static void -ovsdb_datum_remove(struct ovsdb_datum *a, size_t i, - const struct ovsdb_type *type) +/* Removes the element with index 'idx' from 'datum', which has type 'type'. + * If 'idx' is not the last element in 'datum', then the removed element is + * replaced by the (former) last element. + * + * This function does not maintain ovsdb_datum invariants. Use + * ovsdb_datum_sort() to check and restore these invariants. */ +void +ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx, + const struct ovsdb_type *type) { - ovsdb_atom_destroy(&a->keys[i], type->key_type); - a->keys[i] = a->keys[a->n - 1]; + ovsdb_atom_destroy(&datum->keys[idx], type->key_type); + datum->keys[idx] = datum->keys[datum->n - 1]; if (type->value_type != OVSDB_TYPE_VOID) { - ovsdb_atom_destroy(&a->values[i], type->value_type); - a->values[i] = a->values[a->n - 1]; + ovsdb_atom_destroy(&datum->values[idx], type->value_type); + datum->values[idx] = datum->values[datum->n - 1]; + } + datum->n--; +} + +/* Adds the element with the given 'key' and 'value' to 'datum', which must + * have the specified 'type'. + * + * This function always allocates memory, so it is not an efficient way to add + * a number of elements to a datum. + * + * This function does not maintain ovsdb_datum invariants. Use + * ovsdb_datum_sort() to check and restore these invariants. (But a datum with + * 0 or 1 elements cannot violate the invariants anyhow.) */ +void +ovsdb_datum_add_unsafe(struct ovsdb_datum *datum, + const union ovsdb_atom *key, + const union ovsdb_atom *value, + const struct ovsdb_type *type) +{ + size_t idx = datum->n++; + datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys); + ovsdb_atom_clone(&datum->keys[idx], key, type->key_type); + if (type->value_type != OVSDB_TYPE_VOID) { + datum->values = xrealloc(datum->values, + datum->n * sizeof *datum->values); + ovsdb_atom_clone(&datum->values[idx], value, type->value_type); } - a->n--; } void -ovsdb_datum_union(struct ovsdb_datum *a, - const struct ovsdb_datum *b, const struct ovsdb_type *type) +ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b, + const struct ovsdb_type *type, bool replace) { - struct ovsdb_type type_without_value; unsigned int n; - size_t i; + size_t bi; - type_without_value = *type; - type_without_value.value_type = OVSDB_TYPE_VOID; n = a->n; - for (i = 0; i < b->n; i++) { - if (ovsdb_datum_find(b, i, a, &type_without_value) == UINT_MAX) { + for (bi = 0; bi < b->n; bi++) { + unsigned int ai; + + ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key_type); + if (ai == UINT_MAX) { if (n == a->n) { - ovsdb_datum_reallocate(a, type, a->n + (b->n - i)); + ovsdb_datum_reallocate(a, type, a->n + (b->n - bi)); } - ovsdb_atom_clone(&a->keys[n], &b->keys[i], type->key_type); + ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key_type); if (type->value_type != OVSDB_TYPE_VOID) { - ovsdb_atom_clone(&a->values[n], &b->values[i], + ovsdb_atom_clone(&a->values[n], &b->values[bi], type->value_type); } n++; + } else if (replace && type->value_type != OVSDB_TYPE_VOID) { + ovsdb_atom_destroy(&a->values[ai], type->value_type); + ovsdb_atom_clone(&a->values[ai], &b->values[bi], + type->value_type); } } if (n != a->n) { @@ -839,7 +914,7 @@ ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type, unsigned int idx = ovsdb_datum_find(a, i, b, b_type); if (idx != UINT_MAX) { changed = true; - ovsdb_datum_remove(a, i, a_type); + ovsdb_datum_remove_unsafe(a, i, a_type); } else { i++; } diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index 6ee5f9ac0..9cada2f40 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -75,18 +75,23 @@ struct json *ovsdb_atom_to_json(const union ovsdb_atom *, /* An instance of an OVSDB type (given by struct ovsdb_type). * - * 'n' is constrained by the ovsdb_type's 'n_min' and 'n_max'. + * - The 'keys' must be unique and in sorted order. Most functions that modify + * an ovsdb_datum maintain these invariants. Functions that don't maintain + * the invariants have names that end in "_unsafe". Use ovsdb_datum_sort() + * to check and restore these invariants. * - * If 'n' is nonzero, then 'keys' points to an array of 'n' atoms of the type - * specified by the ovsdb_type's 'key_type'. (Otherwise, 'keys' should be - * null.) + * - 'n' is constrained by the ovsdb_type's 'n_min' and 'n_max'. * - * If 'n' is nonzero and the ovsdb_type's 'value_type' is not OVSDB_TYPE_VOID, - * then 'values' points to an array of 'n' atoms of the type specified by the - * 'value_type'. (Otherwise, 'values' should be null.) + * If 'n' is nonzero, then 'keys' points to an array of 'n' atoms of the type + * specified by the ovsdb_type's 'key_type'. (Otherwise, 'keys' should be + * null.) * - * Thus, for 'n' > 0, 'keys' will always be nonnull and 'values' will be - * nonnull only for "map" types. + * If 'n' is nonzero and the ovsdb_type's 'value_type' is not + * OVSDB_TYPE_VOID, then 'values' points to an array of 'n' atoms of the type + * specified by the 'value_type'. (Otherwise, 'values' should be null.) + * + * Thus, for 'n' > 0, 'keys' will always be nonnull and 'values' will be + * nonnull only for "map" types. */ struct ovsdb_datum { unsigned int n; /* Number of 'keys' and 'values'. */ @@ -94,6 +99,8 @@ struct ovsdb_datum { union ovsdb_atom *values; /* Each of the ovsdb_type's 'value_type'. */ }; +/* Basics. */ +void ovsdb_datum_init_empty(struct ovsdb_datum *); void ovsdb_datum_init_default(struct ovsdb_datum *, const struct ovsdb_type *); bool ovsdb_datum_is_default(const struct ovsdb_datum *, const struct ovsdb_type *); @@ -101,9 +108,12 @@ void ovsdb_datum_clone(struct ovsdb_datum *, const struct ovsdb_datum *, const struct ovsdb_type *); void ovsdb_datum_destroy(struct ovsdb_datum *, const struct ovsdb_type *); void ovsdb_datum_swap(struct ovsdb_datum *, struct ovsdb_datum *); + +/* Checking and maintaining invariants. */ struct ovsdb_error *ovsdb_datum_sort(struct ovsdb_datum *, const struct ovsdb_type *); +/* Type conversion. */ struct ovsdb_error *ovsdb_datum_from_json(struct ovsdb_datum *, const struct ovsdb_type *, const struct json *, @@ -120,21 +130,42 @@ int ovsdb_datum_compare_3way(const struct ovsdb_datum *, bool ovsdb_datum_equals(const struct ovsdb_datum *, const struct ovsdb_datum *, const struct ovsdb_type *); + +/* Search. */ +unsigned int ovsdb_datum_find_key(const struct ovsdb_datum *, + const union ovsdb_atom *key, + enum ovsdb_atomic_type key_type); +unsigned int ovsdb_datum_find_key_value(const struct ovsdb_datum *, + const union ovsdb_atom *key, + enum ovsdb_atomic_type key_type, + const union ovsdb_atom *value, + enum ovsdb_atomic_type value_type); + +/* Set operations. */ bool ovsdb_datum_includes_all(const struct ovsdb_datum *, const struct ovsdb_datum *, const struct ovsdb_type *); bool ovsdb_datum_excludes_all(const struct ovsdb_datum *, const struct ovsdb_datum *, const struct ovsdb_type *); - void ovsdb_datum_union(struct ovsdb_datum *, const struct ovsdb_datum *, - const struct ovsdb_type *); + const struct ovsdb_type *, + bool replace); void ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type, const struct ovsdb_datum *b, const struct ovsdb_type *b_type); +/* Raw operations that may not maintain the invariants. */ +void ovsdb_datum_remove_unsafe(struct ovsdb_datum *, size_t idx, + const struct ovsdb_type *); +void ovsdb_datum_add_unsafe(struct ovsdb_datum *, + const union ovsdb_atom *key, + const union ovsdb_atom *value, + const struct ovsdb_type *); + +/* Type checking. */ static inline bool ovsdb_datum_conforms_to_type(const struct ovsdb_datum *datum, const struct ovsdb_type *type) diff --git a/ovsdb/mutation.c b/ovsdb/mutation.c index ba56827c4..53e46f930 100644 --- a/ovsdb/mutation.c +++ b/ovsdb/mutation.c @@ -1,4 +1,4 @@ -/* Copyright (c) 2009 Nicira Networks +/* Copyright (c) 2009, 2010 Nicira Networks * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -416,7 +416,7 @@ ovsdb_mutation_set_execute(struct ovsdb_row *row, break; case OVSDB_M_INSERT: - ovsdb_datum_union(dst, arg, dst_type); + ovsdb_datum_union(dst, arg, dst_type, false); error = ovsdb_datum_conforms_to_type(dst, dst_type) ? 0 : ME_COUNT; break; -- 2.43.0