diff options
author | Thomas Haller <thaller@redhat.com> | 2017-06-26 17:46:43 +0200 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2017-07-05 18:37:38 +0200 |
commit | bb009630a1ebf6de2b82e8afb986c90be3806318 (patch) | |
tree | e9075176287a0bdd07da65f0fed7e3c4000b6d70 | |
parent | 35502807b5cef64e562e41b40bc213aea3cbb35b (diff) | |
download | NetworkManager-bb009630a1ebf6de2b82e8afb986c90be3806318.tar.gz |
core: remove NMMultiIndex
It's unused now.
-rw-r--r-- | Makefile.am | 2 | ||||
-rw-r--r-- | src/nm-multi-index.c | 473 | ||||
-rw-r--r-- | src/nm-multi-index.h | 105 | ||||
-rw-r--r-- | src/tests/test-general-with-expect.c | 358 |
4 files changed, 0 insertions, 938 deletions
diff --git a/Makefile.am b/Makefile.am index 98b717021e..7e88e3f328 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1279,8 +1279,6 @@ src_libNetworkManagerBase_la_SOURCES = \ src/nm-logging.c \ src/nm-logging.h \ \ - src/nm-multi-index.c \ - src/nm-multi-index.h \ src/NetworkManagerUtils.c \ src/NetworkManagerUtils.h \ \ diff --git a/src/nm-multi-index.c b/src/nm-multi-index.c deleted file mode 100644 index 6ae4c21fab..0000000000 --- a/src/nm-multi-index.c +++ /dev/null @@ -1,473 +0,0 @@ -/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */ -/* NetworkManager -- Network link manager - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Copyright (C) 2015 Red Hat, Inc. - */ - -#include "nm-default.h" - -#include "nm-multi-index.h" - -#include <string.h> - -struct NMMultiIndex { - NMMultiIndexFuncEqual equal_fcn; - NMMultiIndexFuncClone clone_fcn; - GHashTable *hash; -}; - -typedef struct { - /* when storing the first item for a multi-index id, we don't yet create - * the hashtable @index. Instead we store it inplace to @value0. Note that - * &values_data->value0 is a NULL terminated array with one item that is - * suitable to be returned directly from nm_multi_index_lookup(). */ - union { - gpointer value0; - gpointer *values; - }; - GHashTable *index; -} ValuesData; - -/*****************************************************************************/ - -static void -_values_data_destroy (ValuesData *values_data) -{ - if (values_data->index) { - g_free (values_data->values); - g_hash_table_unref (values_data->index); - } - g_slice_free (ValuesData, values_data); -} - -static gboolean -_values_data_contains (ValuesData *values_data, gconstpointer value) -{ - return values_data->index - ? g_hash_table_contains (values_data->index, value) - : value == values_data->value0; -} - -static void -_values_data_get_data (ValuesData *values_data, - void *const**out_data, - guint *out_len) -{ - guint i, len; - gpointer *values; - GHashTableIter iter; - - nm_assert (values_data); - - if (!values_data->index) { - NM_SET_OUT (out_data, &values_data->value0); - NM_SET_OUT (out_len, 1); - return; - } - - nm_assert (values_data->index && g_hash_table_size (values_data->index) > 0); - - if (!values_data->values) { - len = g_hash_table_size (values_data->index); - values = g_new (gpointer, len + 1); - - g_hash_table_iter_init (&iter, values_data->index); - for (i = 0; g_hash_table_iter_next (&iter, &values[i], NULL); i++) - nm_assert (i < len); - nm_assert (i == len); - values[i] = NULL; - - values_data->values = values; - NM_SET_OUT (out_len, len); - } else if (out_len) - NM_SET_OUT (out_len, g_hash_table_size (values_data->index)); - - NM_SET_OUT (out_data, values_data->values); -} - -/*****************************************************************************/ - -/** - * nm_multi_index_lookup(): - * @index: - * @id: - * @out_len: (allow-none): output the number of values - * that are returned. - * - * Returns: (transfer none): %NULL if there are no values - * or a %NULL terminated array of pointers. - */ -void *const* -nm_multi_index_lookup (const NMMultiIndex *index, - const NMMultiIndexId *id, - guint *out_len) -{ - ValuesData *values_data; - void *const*values; - - g_return_val_if_fail (index, NULL); - g_return_val_if_fail (id, NULL); - - values_data = g_hash_table_lookup (index->hash, id); - if (!values_data) { - if (out_len) - *out_len = 0; - return NULL; - } - _values_data_get_data (values_data, &values, out_len); - return values; -} - -gboolean -nm_multi_index_contains (const NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value) -{ - ValuesData *values_data; - - g_return_val_if_fail (index, FALSE); - g_return_val_if_fail (id, FALSE); - g_return_val_if_fail (value, FALSE); - - values_data = g_hash_table_lookup (index->hash, id); - return values_data && _values_data_contains (values_data, value); -} - -const NMMultiIndexId * -nm_multi_index_lookup_first_by_value (const NMMultiIndex *index, - gconstpointer value) -{ - GHashTableIter iter; - const NMMultiIndexId *id; - ValuesData *values_data; - - g_return_val_if_fail (index, NULL); - g_return_val_if_fail (value, NULL); - - /* reverse-lookup needs to iterate over all hash tables. It should - * still be fairly quick, if the number of hash tables is small. - * There is no O(1) reverse lookup implemented, because this access - * pattern is not what NMMultiIndex is here for. - * You are supposed to use NMMultiIndex by always knowing which @id - * a @value has. - */ - - g_hash_table_iter_init (&iter, index->hash); - while (g_hash_table_iter_next (&iter, (gpointer *) &id, (gpointer *) &values_data)) { - if (_values_data_contains (values_data, value)) - return id; - } - return NULL; -} - -void -nm_multi_index_foreach (const NMMultiIndex *index, - gconstpointer value, - NMMultiIndexFuncForeach foreach_func, - gpointer user_data) -{ - GHashTableIter iter; - const NMMultiIndexId *id; - ValuesData *values_data; - guint len; - void *const*values; - - g_return_if_fail (index); - g_return_if_fail (foreach_func); - - g_hash_table_iter_init (&iter, index->hash); - while (g_hash_table_iter_next (&iter, (gpointer *) &id, (gpointer *) &values_data)) { - if (value && !_values_data_contains (values_data, value)) - continue; - - _values_data_get_data (values_data, &values, &len); - if (!foreach_func (id, values, len, user_data)) - return; - } -} - -void -nm_multi_index_iter_init (NMMultiIndexIter *iter, - const NMMultiIndex *index, - gconstpointer value) -{ - g_return_if_fail (index); - g_return_if_fail (iter); - - g_hash_table_iter_init (&iter->_iter, index->hash); - iter->_index = index; - iter->_value = value; -} - -gboolean -nm_multi_index_iter_next (NMMultiIndexIter *iter, - const NMMultiIndexId **out_id, - void *const**out_values, - guint *out_len) -{ - const NMMultiIndexId *id; - ValuesData *values_data; - - g_return_val_if_fail (iter, FALSE); - - while (g_hash_table_iter_next (&iter->_iter, (gpointer *) &id, (gpointer *) &values_data)) { - if ( !iter->_value - || _values_data_contains (values_data, iter->_value)) { - if (out_values || out_len) - _values_data_get_data (values_data, out_values, out_len); - if (out_id) - *out_id = id; - return TRUE; - } - } - return FALSE; -} - -/*****************************************************************************/ - -void -nm_multi_index_id_iter_init (NMMultiIndexIdIter *iter, - const NMMultiIndex *index, - const NMMultiIndexId *id) -{ - ValuesData *values_data; - - g_return_if_fail (index); - g_return_if_fail (iter); - g_return_if_fail (id); - - values_data = g_hash_table_lookup (index->hash, id); - if (!values_data) - iter->_state = 2; - else if (values_data->index) { - iter->_state = 1; - g_hash_table_iter_init (&iter->_iter, values_data->index); - } else { - iter->_state = 0; - iter->_value = values_data->value0; - } -} - -gboolean -nm_multi_index_id_iter_next (NMMultiIndexIdIter *iter, - void **out_value) -{ - g_return_val_if_fail (iter, FALSE); - - switch (iter->_state) { - case 0: - iter->_state = 2; - NM_SET_OUT (out_value, iter->_value); - return TRUE; - case 1: - return g_hash_table_iter_next (&iter->_iter, out_value, NULL); - case 2: - iter->_state = 3; - return FALSE; - default: - g_return_val_if_reached (FALSE); - } -} - -/*****************************************************************************/ - -static gboolean -_do_add (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value) -{ - ValuesData *values_data; - - values_data = g_hash_table_lookup (index->hash, id); - if (!values_data) { - NMMultiIndexId *id_new; - - /* Contrary to GHashTable, we don't take ownership of the @id that was - * provided to nm_multi_index_add(). Instead we clone it via @clone_fcn - * when needed. - * - * The reason is, that we expect in most cases that there exists - * already a @id so that we don't need ownership of it (or clone it). - * By doing this, the caller can pass a stack allocated @id or - * reuse the @id for other insertions. - */ - id_new = index->clone_fcn (id); - if (!id_new) - g_return_val_if_reached (FALSE); - - values_data = g_slice_new0 (ValuesData); - values_data->value0 = (gpointer) value; - - g_hash_table_insert (index->hash, id_new, values_data); - } else { - if (!values_data->index) { - if (values_data->value0 == value) - return FALSE; - values_data->index = g_hash_table_new (NULL, NULL); - g_hash_table_replace (values_data->index, (gpointer) value, (gpointer) value); - g_hash_table_replace (values_data->index, values_data->value0, values_data->value0); - values_data->values = NULL; - } else { - if (!nm_g_hash_table_replace (values_data->index, (gpointer) value, (gpointer) value)) - return FALSE; - g_clear_pointer (&values_data->values, g_free); - } - } - return TRUE; -} - -static gboolean -_do_remove (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value) -{ - ValuesData *values_data; - - values_data = g_hash_table_lookup (index->hash, id); - if (!values_data) - return FALSE; - - if (values_data->index) { - if (!g_hash_table_remove (values_data->index, value)) - return FALSE; - if (g_hash_table_size (values_data->index) == 0) - g_hash_table_remove (index->hash, id); - else - g_clear_pointer (&values_data->values, g_free); - } else { - if (values_data->value0 != value) - return FALSE; - g_hash_table_remove (index->hash, id); - } - - return TRUE; -} - -gboolean -nm_multi_index_add (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value) -{ - g_return_val_if_fail (index, FALSE); - g_return_val_if_fail (id, FALSE); - g_return_val_if_fail (value, FALSE); - - return _do_add (index, id, value); -} - -gboolean -nm_multi_index_remove (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value) -{ - g_return_val_if_fail (index, FALSE); - g_return_val_if_fail (value, FALSE); - - if (!id) - g_return_val_if_reached (FALSE); - return _do_remove (index, id, value); -} - -/** - * nm_multi_index_move: - * @index: - * @id_old: (allow-none): remove @value at @id_old - * @id_new: (allow-none): add @value under @id_new - * @value: the value to add - * - * Similar to a remove(), followed by an add(). The difference - * is, that we allow %NULL for both @id_old and @id_new. - * And the return value indicates whether @value was successfully - * removed *and* added. - * - * Returns: %TRUE, if the value was removed from @id_old and added - * as %id_new. %FALSE could mean, that @value was not added to @id_old - * before, or that that @value was already part of @id_new. */ -gboolean -nm_multi_index_move (NMMultiIndex *index, - const NMMultiIndexId *id_old, - const NMMultiIndexId *id_new, - gconstpointer value) -{ - g_return_val_if_fail (index, FALSE); - g_return_val_if_fail (value, FALSE); - - if (!id_old && !id_new) { - /* nothing to do, @value was and is not in @index. */ - return TRUE; - } if (!id_old) { - /* add @value to @index with @id_new */ - return _do_add (index, id_new, value); - } else if (!id_new) { - /* remove @value from @index with @id_old */ - return _do_remove (index, id_old, value); - } else if (index->equal_fcn (id_old, id_new)) { - if (_do_add (index, id_new, value)) { - /* we would expect, that @value is already in @index, - * Return %FALSE, if it wasn't. */ - return FALSE; - } - return TRUE; - } else { - gboolean did_remove; - - did_remove = _do_remove (index, id_old, value); - return _do_add (index, id_new, value) && did_remove; - } -} - -/*****************************************************************************/ - -guint -nm_multi_index_get_num_groups (const NMMultiIndex *index) -{ - g_return_val_if_fail (index, 0); - return g_hash_table_size (index->hash); -} - -NMMultiIndex * -nm_multi_index_new (NMMultiIndexFuncHash hash_fcn, - NMMultiIndexFuncEqual equal_fcn, - NMMultiIndexFuncClone clone_fcn, - NMMultiIndexFuncDestroy destroy_fcn) -{ - NMMultiIndex *index; - - g_return_val_if_fail (hash_fcn, NULL); - g_return_val_if_fail (equal_fcn, NULL); - g_return_val_if_fail (clone_fcn, NULL); - g_return_val_if_fail (destroy_fcn, NULL); - - index = g_new (NMMultiIndex, 1); - index->equal_fcn = equal_fcn; - index->clone_fcn = clone_fcn; - - index->hash = g_hash_table_new_full ((GHashFunc) hash_fcn, - (GEqualFunc) equal_fcn, - (GDestroyNotify) destroy_fcn, - (GDestroyNotify) _values_data_destroy); - return index; -} - -void -nm_multi_index_free (NMMultiIndex *index) -{ - g_return_if_fail (index); - g_hash_table_unref (index->hash); - g_free (index); -} - diff --git a/src/nm-multi-index.h b/src/nm-multi-index.h deleted file mode 100644 index fb102574a1..0000000000 --- a/src/nm-multi-index.h +++ /dev/null @@ -1,105 +0,0 @@ -/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */ -/* NetworkManager -- Network link manager - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Copyright (C) 2015 Red Hat, Inc. - */ - -#ifndef __NM_MULTI_INDEX__ -#define __NM_MULTI_INDEX__ - -typedef struct { - char _dummy; -} NMMultiIndexId; - -typedef struct NMMultiIndex NMMultiIndex; - -typedef struct { - GHashTableIter _iter; - const NMMultiIndex *_index; - gconstpointer _value; -} NMMultiIndexIter; - -typedef struct { - union { - GHashTableIter _iter; - gpointer _value; - }; - guint _state; -} NMMultiIndexIdIter; - -typedef gboolean (*NMMultiIndexFuncEqual) (const NMMultiIndexId *id_a, const NMMultiIndexId *id_b); -typedef guint (*NMMultiIndexFuncHash) (const NMMultiIndexId *id); -typedef NMMultiIndexId *(*NMMultiIndexFuncClone) (const NMMultiIndexId *id); -typedef void (*NMMultiIndexFuncDestroy) (NMMultiIndexId *id); - -typedef gboolean (*NMMultiIndexFuncForeach) (const NMMultiIndexId *id, void *const* values, guint len, gpointer user_data); - - -NMMultiIndex *nm_multi_index_new (NMMultiIndexFuncHash hash_fcn, - NMMultiIndexFuncEqual equal_fcn, - NMMultiIndexFuncClone clone_fcn, - NMMultiIndexFuncDestroy destroy_fcn); - -void nm_multi_index_free (NMMultiIndex *index); - -gboolean nm_multi_index_add (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value); - -gboolean nm_multi_index_remove (NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value); - -gboolean nm_multi_index_move (NMMultiIndex *index, - const NMMultiIndexId *id_old, - const NMMultiIndexId *id_new, - gconstpointer value); - -guint nm_multi_index_get_num_groups (const NMMultiIndex *index); - -void *const*nm_multi_index_lookup (const NMMultiIndex *index, - const NMMultiIndexId *id, - guint *out_len); - -gboolean nm_multi_index_contains (const NMMultiIndex *index, - const NMMultiIndexId *id, - gconstpointer value); - -const NMMultiIndexId *nm_multi_index_lookup_first_by_value (const NMMultiIndex *index, - gconstpointer value); - -void nm_multi_index_foreach (const NMMultiIndex *index, - gconstpointer value, - NMMultiIndexFuncForeach foreach_func, - gpointer user_data); - -void nm_multi_index_iter_init (NMMultiIndexIter *iter, - const NMMultiIndex *index, - gconstpointer value); -gboolean nm_multi_index_iter_next (NMMultiIndexIter *iter, - const NMMultiIndexId **out_id, - void *const**out_values, - guint *out_len); - -void nm_multi_index_id_iter_init (NMMultiIndexIdIter *iter, - const NMMultiIndex *index, - const NMMultiIndexId *id); -gboolean nm_multi_index_id_iter_next (NMMultiIndexIdIter *iter, - void **out_value); - -#endif /* __NM_MULTI_INDEX__ */ - diff --git a/src/tests/test-general-with-expect.c b/src/tests/test-general-with-expect.c index 492e1b1f60..c5d26163fe 100644 --- a/src/tests/test-general-with-expect.c +++ b/src/tests/test-general-with-expect.c @@ -29,7 +29,6 @@ #include <fcntl.h> #include "NetworkManagerUtils.h" -#include "nm-multi-index.h" #include "nm-test-utils-core.h" @@ -499,362 +498,6 @@ test_nm_ethernet_address_is_valid (void) /*****************************************************************************/ -typedef struct { - union { - NMMultiIndexId id_base; - guint bucket; - }; -} NMMultiIndexIdTest; - -typedef struct { - guint64 buckets; - gpointer ptr_value; -} NMMultiIndexTestValue; - -static gboolean -_mi_value_bucket_has (const NMMultiIndexTestValue *value, guint bucket) -{ - g_assert (value); - g_assert (bucket < 64); - - return (value->buckets & (((guint64) 0x01) << bucket)) != 0; -} - -static gboolean -_mi_value_bucket_set (NMMultiIndexTestValue *value, guint bucket) -{ - g_assert (value); - g_assert (bucket < 64); - - if (_mi_value_bucket_has (value, bucket)) - return FALSE; - - value->buckets |= (((guint64) 0x01) << bucket); - return TRUE; -} - -static gboolean -_mi_value_bucket_unset (NMMultiIndexTestValue *value, guint bucket) -{ - g_assert (value); - g_assert (bucket < 64); - - if (!_mi_value_bucket_has (value, bucket)) - return FALSE; - - value->buckets &= ~(((guint64) 0x01) << bucket); - return TRUE; -} - -static guint -_mi_idx_hash (const NMMultiIndexIdTest *id) -{ - g_assert (id && id->bucket < 64); - return id->bucket; -} - -static gboolean -_mi_idx_equal (const NMMultiIndexIdTest *a, const NMMultiIndexIdTest *b) -{ - g_assert (a && a->bucket < 64); - g_assert (b && b->bucket < 64); - - return a->bucket == b->bucket; -} - -static NMMultiIndexIdTest * -_mi_idx_clone (const NMMultiIndexIdTest *id) -{ - NMMultiIndexIdTest *n; - - g_assert (id && id->bucket < 64); - - n = g_new0 (NMMultiIndexIdTest, 1); - n->bucket = id->bucket; - return n; -} - -static void -_mi_idx_destroy (NMMultiIndexIdTest *id) -{ - g_assert (id && id->bucket < 64); - g_free (id); -} - -static NMMultiIndexTestValue * -_mi_create_array (guint num_values) -{ - NMMultiIndexTestValue *array = g_new0 (NMMultiIndexTestValue, num_values); - guint i; - - g_assert (num_values > 0); - - for (i = 0; i < num_values; i++) { - array[i].buckets = 0; - array[i].ptr_value = GUINT_TO_POINTER (i + 1); - } - return array; -} - -typedef struct { - guint num_values; - guint num_buckets; - NMMultiIndexTestValue *array; - int test_idx; -} NMMultiIndexAssertData; - -static gboolean -_mi_assert_index_equals_array_cb (const NMMultiIndexIdTest *id, void *const* values, guint len, NMMultiIndexAssertData *data) -{ - guint i; - gboolean has_test_idx = FALSE; - - g_assert (id && id->bucket < 64); - g_assert (data); - g_assert (values); - g_assert (len > 0); - g_assert (values[len] == NULL); - g_assert (data->test_idx >= -1 || data->test_idx < data->num_buckets); - - g_assert (id->bucket < data->num_buckets); - - for (i = 0; i < data->num_values; i++) - g_assert (!_mi_value_bucket_has (&data->array[i], id->bucket)); - - for (i = 0; i < len; i++) { - guint vi = GPOINTER_TO_UINT (values[i]); - - g_assert (vi >= 1); - g_assert (vi <= data->num_values); - vi--; - if (data->test_idx == vi) - has_test_idx = TRUE; - g_assert (data->array[vi].ptr_value == values[i]); - if (!_mi_value_bucket_set (&data->array[vi], id->bucket)) - g_assert_not_reached (); - } - g_assert ((data->test_idx == -1 && !has_test_idx) || has_test_idx); - return TRUE; -} - -static void -_mi_assert_index_equals_array (guint num_values, guint num_buckets, int test_idx, const NMMultiIndexTestValue *array, const NMMultiIndex *index) -{ - NMMultiIndexAssertData data = { - .num_values = num_values, - .num_buckets = num_buckets, - .test_idx = test_idx, - }; - NMMultiIndexIter iter; - const NMMultiIndexIdTest *id; - void *const* values; - guint len; - NMMultiIndexTestValue *v; - - data.array = _mi_create_array (num_values); - v = test_idx >= 0 ? data.array[test_idx].ptr_value : NULL; - nm_multi_index_foreach (index, v, (NMMultiIndexFuncForeach) _mi_assert_index_equals_array_cb, &data); - if (test_idx >= 0) - g_assert (memcmp (&data.array[test_idx], &array[test_idx], sizeof (NMMultiIndexTestValue)) == 0); - else - g_assert (memcmp (data.array, array, sizeof (NMMultiIndexTestValue) * num_values) == 0); - g_free (data.array); - - - data.array = _mi_create_array (num_values); - v = test_idx >= 0 ? data.array[test_idx].ptr_value : NULL; - nm_multi_index_iter_init (&iter, index, v); - while (nm_multi_index_iter_next (&iter, (gpointer) &id, &values, &len)) - _mi_assert_index_equals_array_cb (id, values, len, &data); - if (test_idx >= 0) - g_assert (memcmp (&data.array[test_idx], &array[test_idx], sizeof (NMMultiIndexTestValue)) == 0); - else - g_assert (memcmp (data.array, array, sizeof (NMMultiIndexTestValue) * num_values) == 0); - g_free (data.array); -} - -typedef enum { - MI_OP_ADD, - MI_OP_REMOVE, - MI_OP_MOVE, -} NMMultiIndexOperation; - -static void -_mi_rebucket (GRand *rand, guint num_values, guint num_buckets, NMMultiIndexOperation op, guint bucket, guint bucket_old, guint array_idx, NMMultiIndexTestValue *array, NMMultiIndex *index) -{ - NMMultiIndexTestValue *v; - NMMultiIndexIdTest id, id_old; - const NMMultiIndexIdTest *id_reverse; - guint64 buckets_old; - guint i; - gboolean had_bucket, had_bucket_old; - - g_assert (array_idx < num_values); - g_assert (bucket < (int) num_buckets); - - v = &array[array_idx]; - - buckets_old = v->buckets; - if (op == MI_OP_MOVE) - had_bucket_old = _mi_value_bucket_has (v, bucket_old); - else - had_bucket_old = FALSE; - had_bucket = _mi_value_bucket_has (v, bucket); - - switch (op) { - - case MI_OP_ADD: - _mi_value_bucket_set (v, bucket); - id.bucket = bucket; - if (nm_multi_index_add (index, &id.id_base, v->ptr_value)) - g_assert (!had_bucket); - else - g_assert (had_bucket); - break; - - case MI_OP_REMOVE: - _mi_value_bucket_unset (v, bucket); - id.bucket = bucket; - if (nm_multi_index_remove (index, &id.id_base, v->ptr_value)) - g_assert (had_bucket); - else - g_assert (!had_bucket); - break; - - case MI_OP_MOVE: - - _mi_value_bucket_unset (v, bucket_old); - _mi_value_bucket_set (v, bucket); - - id.bucket = bucket; - id_old.bucket = bucket_old; - - if (nm_multi_index_move (index, &id_old.id_base, &id.id_base, v->ptr_value)) { - if (bucket == bucket_old) - g_assert (had_bucket_old && had_bucket); - else - g_assert (had_bucket_old && !had_bucket); - } else { - if (bucket == bucket_old) - g_assert (!had_bucket_old && !had_bucket); - else - g_assert (!had_bucket_old || had_bucket); - } - break; - - default: - g_assert_not_reached (); - } - -#if 0 - g_print (">>> rebucket: idx=%3u, op=%3s, bucket=%3i%c -> %3i%c, buckets=%08llx -> %08llx %s\n", array_idx, - op == MI_OP_ADD ? "ADD" : (op == MI_OP_REMOVE ? "REM" : "MOV"), - bucket_old, had_bucket_old ? '*' : ' ', - bucket, had_bucket ? '*' : ' ', - (unsigned long long) buckets_old, (unsigned long long) v->buckets, - buckets_old != v->buckets ? "(changed)" : "(unchanged)"); -#endif - - id_reverse = (const NMMultiIndexIdTest *) nm_multi_index_lookup_first_by_value (index, v->ptr_value); - if (id_reverse) - g_assert (_mi_value_bucket_has (v, id_reverse->bucket)); - else - g_assert (v->buckets == 0); - - for (i = 0; i < 64; i++) { - id.bucket = i; - if (nm_multi_index_contains (index, &id.id_base, v->ptr_value)) - g_assert (_mi_value_bucket_has (v, i)); - else - g_assert (!_mi_value_bucket_has (v, i)); - } - - _mi_assert_index_equals_array (num_values, num_buckets, -1, array, index); - _mi_assert_index_equals_array (num_values, num_buckets, array_idx, array, index); - _mi_assert_index_equals_array (num_values, num_buckets, g_rand_int_range (rand, 0, num_values), array, index); -} - -static void -_mi_test_run (guint num_values, guint num_buckets) -{ - NMMultiIndex *index = nm_multi_index_new ((NMMultiIndexFuncHash) _mi_idx_hash, - (NMMultiIndexFuncEqual) _mi_idx_equal, - (NMMultiIndexFuncClone) _mi_idx_clone, - (NMMultiIndexFuncDestroy) _mi_idx_destroy); - gs_free NMMultiIndexTestValue *array = _mi_create_array (num_values); - GRand *rand = nmtst_get_rand (); - guint i, i_rd, i_idx, i_bucket; - guint num_buckets_all = num_values * num_buckets; - - g_assert (array[0].ptr_value == GUINT_TO_POINTER (1)); - - _mi_assert_index_equals_array (num_values, num_buckets, -1, array, index); - - _mi_rebucket (rand, num_values, num_buckets, MI_OP_ADD, 0, 0, 0, array, index); - _mi_rebucket (rand, num_values, num_buckets, MI_OP_REMOVE, 0, 0, 0, array, index); - - if (num_buckets >= 3) { - _mi_rebucket (rand, num_values, num_buckets, MI_OP_ADD, 0, 0, 0, array, index); - _mi_rebucket (rand, num_values, num_buckets, MI_OP_MOVE, 2, 0, 0, array, index); - _mi_rebucket (rand, num_values, num_buckets, MI_OP_REMOVE, 2, 0, 0, array, index); - } - - g_assert (nm_multi_index_get_num_groups (index) == 0); - - /* randomly change the bucket of entries. */ - for (i = 0; i < 5 * num_values; i++) { - guint array_idx = g_rand_int_range (rand, 0, num_values); - guint bucket = g_rand_int_range (rand, 0, num_buckets); - NMMultiIndexOperation op = g_rand_int_range (rand, 0, MI_OP_MOVE + 1); - guint bucket_old = 0; - - if (op == MI_OP_MOVE) { - if ((g_rand_int (rand) % 2) && array[array_idx].buckets != 0) { - guint64 b; - - /* choose the highest (existing) bucket. */ - bucket_old = 0; - for (b = array[array_idx].buckets; b; b >>= 1) - bucket_old++; - } else { - /* choose a random bucket (even if the item is currently not in that bucket). */ - bucket_old = g_rand_int_range (rand, 0, num_buckets); - } - } - - _mi_rebucket (rand, num_values, num_buckets, op, bucket, bucket_old, array_idx, array, index); - } - - /* remove all elements from all buckets */ - i_rd = g_rand_int (rand); - for (i = 0; i < num_buckets_all; i++) { - i_rd = (i_rd + 101) % num_buckets_all; - i_idx = i_rd / num_buckets; - i_bucket = i_rd % num_buckets; - - if (_mi_value_bucket_has (&array[i_idx], i_bucket)) - _mi_rebucket (rand, num_values, num_buckets, MI_OP_REMOVE, i_bucket, 0, i_idx, array, index); - } - - g_assert (nm_multi_index_get_num_groups (index) == 0); - nm_multi_index_free (index); -} - -static void -test_nm_multi_index (void) -{ - guint i, j; - - for (i = 1; i < 7; i++) { - for (j = 1; j < 6; j++) - _mi_test_run (i, j); - } - _mi_test_run (50, 3); - _mi_test_run (50, 18); -} - -/*****************************************************************************/ - static void test_nm_utils_new_vlan_name (void) { @@ -909,7 +552,6 @@ main (int argc, char **argv) g_test_add_func ("/general/nm_utils_kill_child", test_nm_utils_kill_child); g_test_add_func ("/general/nm_utils_array_remove_at_indexes", test_nm_utils_array_remove_at_indexes); g_test_add_func ("/general/nm_ethernet_address_is_valid", test_nm_ethernet_address_is_valid); - g_test_add_func ("/general/nm_multi_index", test_nm_multi_index); g_test_add_func ("/general/nm_utils_new_vlan_name", test_nm_utils_new_vlan_name); return g_test_run (); |