This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
[PATCH 2/3] dynarray: Implement remove function
- From: Adhemerval Zanella <adhemerval dot zanella at linaro dot org>
- To: libc-alpha at sourceware dot org
- Date: Wed, 7 Feb 2018 11:09:26 -0200
- Subject: [PATCH 2/3] dynarray: Implement remove function
- Authentication-results: sourceware.org; auth=none
- References: <1518008967-8310-1-git-send-email-adhemerval.zanella@linaro.org>
This patch implements the remove item function for dynarray array.
It is a costly operation, since it requires a memory move operation
possible as large as the array size less one element.
Checked on x86_64-linux-gnu.
* malloc/dynarray-skeleton.c: List remove as defined function.
((DYNARRAY_PREFIX##remove): New function.
* malloc/tst-dynarray.c (test_int): Add tests for remove function.
(check_int, check_int_array): New functions.
---
ChangeLog | 5 ++++
malloc/dynarray-skeleton.c | 23 +++++++++++++++++
malloc/tst-dynarray.c | 64 ++++++++++++++++++++++++++++++++++++++--------
3 files changed, 81 insertions(+), 11 deletions(-)
diff --git a/malloc/dynarray-skeleton.c b/malloc/dynarray-skeleton.c
index 5ab4a19..619a750 100644
--- a/malloc/dynarray-skeleton.c
+++ b/malloc/dynarray-skeleton.c
@@ -72,6 +72,7 @@
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *);
bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t);
void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *);
+ void DYNARRAY_PREFIX##remove (struct DYNARRAY_STRUCT *, size_t);
void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *);
The following functions are provided are provided if the
@@ -428,6 +429,28 @@ DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
}
}
+/* Remove the element of index IDX of LIST if it is present. */
+__attribute__ ((unused, nonnull (1)))
+static void
+DYNARRAY_NAME (remove) (struct DYNARRAY_STRUCT *list, size_t idx)
+{
+ size_t last_pos = list->dynarray_header.used;
+ if (idx + 1 == last_pos)
+ {
+ DYNARRAY_NAME (remove_last) (list);
+ return;
+ }
+ DYNARRAY_ELEMENT *elem = DYNARRAY_NAME (at) (list, idx);
+ DYNARRAY_ELEMENT *last = &list->dynarray_header.array[last_pos];
+
+ ptrdiff_t size_to_move = (uintptr_t)last - (uintptr_t)elem;
+#ifdef DYNARRAY_ELEMENT_FREE
+ DYNARRAY_ELEMENT_FREE (elem);
+#endif
+ memmove (elem, elem + 1, size_to_move);
+ list->dynarray_header.used--;
+}
+
/* Remove all elements from the list. The elements are freed, but the
list itself is not. */
__attribute__ ((unused, nonnull (1)))
diff --git a/malloc/tst-dynarray.c b/malloc/tst-dynarray.c
index 0a5716b..c31b73d 100644
--- a/malloc/tst-dynarray.c
+++ b/malloc/tst-dynarray.c
@@ -55,6 +55,40 @@ struct long_array
enum { max_count = 20 };
+static void
+check_int (int do_remove, struct dynarray_int *dyn, unsigned int base,
+ unsigned int final_count, unsigned int to_remove)
+{
+ if (do_remove == 1)
+ for (unsigned int i = 0; i < final_count; ++i)
+ TEST_VERIFY_EXIT (*dynarray_int_at (dyn, i) == base + i);
+ else if (do_remove == 2)
+ {
+ unsigned int i;
+ for (i = 0; i < to_remove; ++i)
+ TEST_VERIFY_EXIT (*dynarray_int_at (dyn, i) == base + i);
+ for (i = to_remove; i < final_count; ++i)
+ TEST_VERIFY_EXIT (*dynarray_int_at (dyn, i) == base + i + 1);
+ }
+}
+
+static void
+check_int_array (int do_remove, struct int_array *result, unsigned int base,
+ unsigned int final_count, unsigned int to_remove)
+{
+ if (do_remove == 1)
+ for (unsigned int i = 0; i < final_count; ++i)
+ TEST_VERIFY_EXIT (result->array[i] == base + i);
+ else if (do_remove == 2)
+ {
+ unsigned int i;
+ for (i = 0; i < to_remove; ++i)
+ TEST_VERIFY_EXIT (result->array[i] == base + i);
+ for (i = to_remove; i < final_count; ++i)
+ TEST_VERIFY_EXIT (result->array[i] == base + i + 1);
+ }
+}
+
/* Test dynamic arrays with int elements (no automatic deallocation
for elements). */
static void
@@ -84,15 +118,15 @@ test_int (void)
do_add: Switch between emplace (false) and add (true).
do_finalize: Perform finalize call at the end.
do_clear: Perform clear call at the end.
- do_remove_last: Perform remove_last call after adding elements.
+ do_remove: Perform remove_last or remove call after adding elements.
count: Number of elements added to the array. */
for (int do_add = 0; do_add < 2; ++do_add)
- for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+ for (int do_finalize = 1; do_finalize < 2; ++do_finalize)
for (int do_clear = 0; do_clear < 2; ++do_clear)
- for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
- for (unsigned int count = 0; count < max_count; ++count)
+ for (int do_remove = 1; do_remove < 3; ++do_remove)
+ for (unsigned int count = 2; count < max_count; ++count)
{
- if (do_remove_last && count == 0)
+ if (do_remove && count == 0)
continue;
unsigned int base = count * count;
struct dynarray_int dyn;
@@ -123,7 +157,8 @@ test_int (void)
}
unsigned final_count;
bool heap_array = dyn.dynarray_header.array != dyn.scratch;
- if (do_remove_last)
+ size_t to_remove = dynarray_int_size (&dyn) / 2;
+ if (do_remove == 1)
{
dynarray_int_remove_last (&dyn);
if (count == 0)
@@ -131,7 +166,15 @@ test_int (void)
else
final_count = count - 1;
}
- else
+ else if (do_remove == 2)
+ {
+ dynarray_int_remove (&dyn, to_remove);
+ if (count == 0)
+ final_count = 0;
+ else
+ final_count = count - 1;
+ }
+ else
final_count = count;
if (final_count > 0)
{
@@ -151,8 +194,7 @@ test_int (void)
TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == final_count);
TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
if (!do_clear)
- for (unsigned int i = 0; i < final_count; ++i)
- TEST_VERIFY_EXIT (*dynarray_int_at (&dyn, i) == base + i);
+ check_int (do_remove, &dyn, base, final_count, to_remove);
if (do_finalize)
{
struct int_array result = { (int *) (uintptr_t) -1, -1 };
@@ -168,8 +210,8 @@ test_int (void)
TEST_VERIFY_EXIT
(malloc_usable_size (result.array)
>= final_count * sizeof (result.array[0]));
- for (unsigned int i = 0; i < final_count; ++i)
- TEST_VERIFY_EXIT (result.array[i] == base + i);
+ check_int_array (do_remove, &result, base, final_count,
+ to_remove);
free (result.array);
}
}
--
2.7.4