core: add NMMultiIndex class

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

The values are opaque pointers (void*). These values can be
associated with keys. The keys are an opaque type NMMultiIndexId
with arbitrary hash/equal functions.

Think of the keys being a set of buckets. A value can be associated with multiple
keys, just like with a regular GHashTable (i.e. it can be in multiple buckets).
But one key can also be associated with multiple values (i.e. one bucket can contain
multiple values). Hence the name "multi".
One bucket can only either contain a value or not. It cannot contain the same
value multiple times.

This is implemented as a hash of hashes with the outer keys being
NMMultiIndexId. The inner hashes are the "buckets".

This class will be used as an efficient lookup index to find all values
that belong to a certain key (bucket). Later we will ask for example
"Which IP4-Addresses are associated with a certain ifindex" and
efficiently retrieve the cached result list.

4 files changed, 912 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 4abd92a53b..388c6b3b66 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -331,6 +331,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 \
@@ -498,6 +500,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..34695add7e
--- /dev/null
+++ b/src/nm-multi-index.c
@@ -0,0 +1,441 @@
+/* -*- 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 <string.h>
+
+#include "nm-glib-compat.h"
+#include "nm-macros-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;
+}
+
+/******************************************************************************************/
+
+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 = 1;
+	else {
+		iter->_state = 0;
+		g_hash_table_iter_init (&iter->_iter, values_data->index);
+	}
+}
+
+gboolean
+nm_multi_index_id_iter_next (NMMultiIndexIdIter *iter,
+                             void **out_value)
+{
+	g_return_val_if_fail (iter, FALSE);
+	g_return_val_if_fail (iter->_state <= 1, FALSE);
+
+	if (iter->_state == 0)
+		return g_hash_table_iter_next (&iter->_iter, out_value, NULL);
+	else {
+		iter->_state = 2;
+		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 (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
new file mode 100644
index 0000000000..e41ef54e7c
--- /dev/null
+++ b/src/nm-multi-index.h
@@ -0,0 +1,109 @@
+/* -*- 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 struct {
+	GHashTableIter _iter;
+	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);
+
+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 300ed2145d..e7a1453942 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 (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 ? '*' : ' ',
+	         (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 ();
 }