util: add nm_utils_array_remove_at_indexes() function

3 files changed, 175 insertions, 0 deletions

diff --git a/src/NetworkManagerUtils.c b/src/NetworkManagerUtils.c
index ba2319af5f..2a88c946a4 100644
--- a/src/NetworkManagerUtils.c
+++ b/src/NetworkManagerUtils.c
@@ -150,6 +150,80 @@ nm_utils_ip6_address_clear_host_address (struct in6_addr *dst, const struct in6_
 	return dst;
 }
 
+void
+nm_utils_array_remove_at_indexes (GArray *array, const guint *indexes_to_delete, gsize len)
+{
+	gsize elt_size;
+	guint index_to_delete;
+	guint i_src;
+	guint mm_src, mm_dst, mm_len;
+	gsize i_itd;
+	guint res_length;
+
+	g_return_if_fail (array);
+	if (!len)
+		return;
+	g_return_if_fail (indexes_to_delete);
+
+	elt_size = g_array_get_element_size (array);
+
+	i_itd = 0;
+	index_to_delete = indexes_to_delete[0];
+	if (index_to_delete >= array->len)
+		g_return_if_reached ();
+
+	res_length = array->len - 1;
+
+	mm_dst = index_to_delete;
+	mm_src = index_to_delete;
+	mm_len = 0;
+
+	for (i_src = index_to_delete; i_src < array->len; i_src++) {
+		if (i_src < index_to_delete)
+			mm_len++;
+		else {
+			/* we require indexes_to_delete to contain non-repeated, ascending
+			 * indexes. Otherwise we would need to presort the indexes. */
+			while (TRUE) {
+				guint dd;
+
+				if (i_itd + 1 >= len) {
+					index_to_delete = G_MAXUINT;
+					break;
+				}
+
+				dd = indexes_to_delete[++i_itd];
+				if (dd > index_to_delete) {
+					if (dd >= array->len)
+						g_warn_if_reached ();
+					else {
+						g_assert (res_length > 0);
+						res_length--;
+					}
+					index_to_delete = dd;
+					break;
+				}
+				g_warn_if_reached ();
+			}
+
+			if (mm_len) {
+				memmove (&array->data[mm_dst * elt_size],
+				         &array->data[mm_src * elt_size],
+				         mm_len * elt_size);
+				mm_dst += mm_len;
+				mm_src += mm_len + 1;
+				mm_len = 0;
+			} else
+				mm_src++;
+		}
+	}
+	if (mm_len) {
+		memmove (&array->data[mm_dst * elt_size],
+		         &array->data[mm_src * elt_size],
+		         mm_len * elt_size);
+	}
+	g_array_set_size (array, res_length);
+}
 
 int
 nm_spawn_process (const char *args, GError **error)
diff --git a/src/NetworkManagerUtils.h b/src/NetworkManagerUtils.h
index 5633d4b2f7..99de3b66b9 100644
--- a/src/NetworkManagerUtils.h
+++ b/src/NetworkManagerUtils.h
@@ -183,6 +183,8 @@ void nm_utils_ipv6_interface_identfier_get_from_addr (NMUtilsIPv6IfaceId *iid,
 GVariant   *nm_utils_connection_hash_to_dict (GHashTable *hash);
 GHashTable *nm_utils_connection_dict_to_hash (GVariant *dict);
 
+void nm_utils_array_remove_at_indexes (GArray *array, const guint *indexes_to_delete, gsize len);
+
 void nm_utils_setpgid (gpointer unused);
 
 #endif /* __NETWORKMANAGER_UTILS_H__ */
diff --git a/src/tests/test-general-with-expect.c b/src/tests/test-general-with-expect.c
index e341ca7988..274cbc854e 100644
--- a/src/tests/test-general-with-expect.c
+++ b/src/tests/test-general-with-expect.c
@@ -330,6 +330,104 @@ 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);
+					}
+				}
+			}
+		}
+	}
+}
 
 /*******************************************/
 
@@ -341,6 +439,7 @@ main (int argc, char **argv)
 	nmtst_init_assert_logging (&argc, &argv, "DEBUG", "DEFAULT");
 
 	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);
 
 	return g_test_run ();
 }