Imported Upstream version 1.0.4 upstream/1.0.4

1 files changed, 458 insertions, 1 deletions

diff --git a/src/tests/test-general-with-expect.c b/src/tests/test-general-with-expect.c
index 4a0627c9..bb52bde2 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"
 
@@ -330,11 +331,109 @@ test_nm_utils_kill_child (void)
 	g_test_assert_expected_messages ();
 }
 
+/*******************************************/
+
+static void
+_remove_at_indexes_init_random_idx (GArray *idx, guint array_len, guint idx_len)
+{
+	GRand *rand = nmtst_get_rand ();
+	gs_free char *mask = NULL;
+	guint i, max_test_idx;
+
+	g_assert (idx);
+	g_assert (array_len > 0);
+	g_assert (idx_len >= 1 && idx_len <= array_len);
+
+	mask = g_new0 (char, array_len);
+
+	max_test_idx = array_len - 1;
+	for (i = 0; i < idx_len; i++) {
+		guint itest;
+
+		/* find a index itest that is not yet taken */
+		if (max_test_idx == 0)
+			itest = 0;
+		else
+			itest = g_rand_int_range (rand, 0, max_test_idx);
+		while (itest < array_len && mask[itest])
+			itest++;
+		g_assert (itest <= max_test_idx);
+		g_assert (!mask[itest]);
+
+		mask[itest] = TRUE;
+		if (itest == max_test_idx) {
+			g_assert (max_test_idx > 0 || i == idx_len - 1);
+
+			if (max_test_idx == 0)
+				g_assert_cmpint (i, ==, idx_len - 1);
+			else {
+				max_test_idx--;
+				while (max_test_idx > 0 && mask[max_test_idx])
+					max_test_idx--;
+				if (mask[max_test_idx])
+					g_assert_cmpint (i, ==, idx_len - 1);
+			}
+		}
+	}
+
+	g_array_set_size (idx, 0);
+	for (i = 0; i < array_len; i++) {
+		if (mask[i])
+			g_array_append_val (idx, i);
+	}
+	g_assert_cmpint (idx->len, ==, idx_len);
+}
+
+static void
+test_nm_utils_array_remove_at_indexes ()
+{
+	gs_unref_array GArray *idx = NULL, *array = NULL;
+	gs_unref_hashtable GHashTable *unique = NULL;
+	guint i_len, i_idx_len, i_rnd, i;
+
+	idx = g_array_new (FALSE, FALSE, sizeof (guint));
+	array = g_array_new (FALSE, FALSE, sizeof (gssize));
+	unique = g_hash_table_new (NULL, NULL);
+	for (i_len = 1; i_len < 20; i_len++) {
+		for (i_idx_len = 1; i_idx_len <= i_len; i_idx_len++) {
+			for (i_rnd = 0; i_rnd < 20; i_rnd++) {
+
+				_remove_at_indexes_init_random_idx (idx, i_len, i_idx_len);
+				g_array_set_size (array, i_len);
+				for (i = 0; i < i_len; i++)
+					g_array_index (array, gssize, i) = i;
+
+				nm_utils_array_remove_at_indexes (array, &g_array_index (idx, guint, 0), i_idx_len);
+
+				g_hash_table_remove_all (unique);
+				/* ensure that all the indexes are still unique */
+				for (i = 0; i < array->len; i++)
+					g_hash_table_add (unique, GUINT_TO_POINTER (g_array_index (array, gssize, i)));
+				g_assert_cmpint (g_hash_table_size (unique), ==, array->len);
+
+				for (i = 0; i < idx->len; i++)
+					g_hash_table_add (unique, GUINT_TO_POINTER (g_array_index (idx, guint, i)));
+				g_assert_cmpint (g_hash_table_size (unique), ==, i_len);
+
+				/* ensure proper sort order in array */
+				for (i = 0; i < array->len; i++) {
+					gssize i1 = g_array_index (array, gssize, i);
+
+					g_assert (i1 >= 0 && i1 < i_len);
+					if (i > 0) {
+						gsize i0 = g_array_index (array, gssize, i - 1);
+						g_assert_cmpint (i0, <, i1);
+					}
+				}
+			}
+		}
+	}
+}
 
 /*******************************************/
 
 static void
-test_nm_ethernet_address_is_valid ()
+test_nm_ethernet_address_is_valid (void)
 {
 	g_assert (!nm_ethernet_address_is_valid (NULL, -1));
 	g_assert (!nm_ethernet_address_is_valid (NULL, ETH_ALEN));
@@ -360,6 +459,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
@@ -369,6 +824,8 @@ 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_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_array_remove_at_indexes", test_nm_utils_array_remove_at_indexes);
 
 	return g_test_run ();
 }