core: add NMMultiIndex

A class to do efficient lookup for values based on a key.

One value can be referenced by multiple keys, and one
key can contain multiple values. Hence the name.

4 files changed, 863 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 1534ce153d..d74135916c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -326,6 +326,8 @@ nm_sources = \
 	nm-auth-utils.h \
 	nm-manager.c \
 	nm-manager.h \
+	nm-multi-index.c \
+	nm-multi-index.h \
 	nm-policy.c \
 	nm-policy.h \
 	nm-properties-changed-signal.c \
@@ -487,6 +489,8 @@ libnm_iface_helper_la_SOURCES = \
 	nm-enum-types.h \
 	nm-logging.c \
 	nm-logging.h \
+	nm-multi-index.c \
+	nm-multi-index.h \
 	NetworkManagerUtils.c \
 	NetworkManagerUtils.h
 
diff --git a/src/nm-multi-index.c b/src/nm-multi-index.c
new file mode 100644
index 0000000000..379fceb8ff
--- /dev/null
+++ b/src/nm-multi-index.c
@@ -0,0 +1,403 @@
+/* -*- 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 "config.h"
+
+#include "nm-multi-index.h"
+
+#include "nm-glib-compat.h"
+#include "nm-utils-internal.h"
+
+
+struct NMMultiIndex {
+	NMMultiIndexFuncEqual equal_fcn;
+	NMMultiIndexFuncClone clone_fcn;
+	GHashTable *hash;
+};
+
+typedef struct {
+	GHashTable *index;
+	gpointer *values;
+} ValuesData;
+
+/******************************************************************************************/
+
+static ValuesData *
+_values_data_create ()
+{
+	ValuesData *values_data;
+
+	values_data = g_slice_new (ValuesData);
+	values_data->index = g_hash_table_new (NULL, NULL);
+	values_data->values = NULL;
+	return values_data;
+}
+
+static void
+_values_data_destroy (ValuesData *values_data)
+{
+	if (values_data) {
+		g_free (values_data->values);
+		g_hash_table_unref (values_data->index);
+		g_slice_free (ValuesData, values_data);
+	}
+}
+
+static void
+_values_data_populate_array (ValuesData *values_data)
+{
+	guint i, len;
+	gpointer *values;
+	GHashTableIter iter;
+
+	nm_assert (values_data);
+	nm_assert (values_data->index && g_hash_table_size (values_data->index) > 0);
+
+	if (values_data->values)
+		return;
+
+	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_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;
+
+	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_populate_array (values_data);
+	if (out_len)
+		*out_len = g_hash_table_size (values_data->index);
+	return values_data->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
+	       && g_hash_table_contains (values_data->index, 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 (g_hash_table_contains (values_data->index, 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;
+
+	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
+		    && !g_hash_table_contains (values_data->index, value))
+			continue;
+
+		_values_data_populate_array (values_data);
+		if (!foreach_func (id, values_data->values, g_hash_table_size (values_data->index), 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
+		    || g_hash_table_contains (values_data->index, iter->_value)) {
+			_values_data_populate_array (values_data);
+			if (out_id)
+				*out_id = id;
+			if (out_values)
+				*out_values = values_data->values;
+			if (out_len)
+				*out_len = g_hash_table_size (values_data->index);
+			return TRUE;
+		}
+	}
+	return 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 = _values_data_create ();
+		g_hash_table_replace (values_data->index, (gpointer) value, (gpointer) value);
+
+		g_hash_table_insert (index->hash, id_new, values_data);
+	} 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 (!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);
+	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 (value, FALSE);
+
+	if (!id)
+		g_return_val_if_reached (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 undicates 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 as @id_old
+ *   or 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
new file mode 100644
index 0000000000..7586c4848c
--- /dev/null
+++ b/src/nm-multi-index.h
@@ -0,0 +1,98 @@
+/* -*- 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__
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+
+typedef struct {
+	char _dummy;
+} NMMultiIndexId;
+
+typedef struct NMMultiIndex NMMultiIndex;
+
+typedef struct {
+	GHashTableIter _iter;
+	const NMMultiIndex *_index;
+	gconstpointer _value;
+} NMMultiIndexIter;
+
+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);
+
+G_END_DECLS
+
+#endif /* __NM_MULTI_INDEX__ */
+
diff --git a/src/tests/test-general-with-expect.c b/src/tests/test-general-with-expect.c
index 8f52af3775..09f8306273 100644
--- a/src/tests/test-general-with-expect.c
+++ b/src/tests/test-general-with-expect.c
@@ -29,6 +29,7 @@
 
 #include "NetworkManagerUtils.h"
 #include "nm-logging.h"
+#include "nm-multi-index.h"
 
 #include "nm-test-utils.h"
 
@@ -545,6 +546,362 @@ test_nm_ethernet_address_is_valid ()
 
 /*******************************************/
 
+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 ? '*' : ' ',
+	         (long long unsigned) buckets_old, (long long unsigned) 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);
+}
+
+/*******************************************/
+
 NMTST_DEFINE ();
 
 int
@@ -557,6 +914,7 @@ 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);
 
 	return g_test_run ();
 }