diff mbox series

[2/3] dynarray: Implement remove function

Message ID 1518008967-8310-2-git-send-email-adhemerval.zanella@linaro.org
State New
Headers show
Series [1/3] Refactor Linux ARCH_FORK implementation | expand

Commit Message

Adhemerval Zanella Feb. 7, 2018, 1:09 p.m. UTC 
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(-)

Comments

Alexander Monakov Feb. 7, 2018, 2:48 p.m. UTC | #1 
On Wed, 7 Feb 2018, Adhemerval Zanella wrote:

> 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.

If preserving order is not required, then removing an element is as
cheap as moving only the last element to the position of the removed.

If order preservation, is, in fact, part of the intended interface,
then shouldn't the new function be named like '..._ordered_remove'
to reflect that?

Alexander
Adhemerval Zanella Feb. 7, 2018, 4:06 p.m. UTC | #2 
On 07/02/2018 12:48, Alexander Monakov wrote:
> On Wed, 7 Feb 2018, Adhemerval Zanella wrote:
> 
>> 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.
> 
> If preserving order is not required, then removing an element is as
> cheap as moving only the last element to the position of the removed.
> 
> If order preservation, is, in fact, part of the intended interface,
> then shouldn't the new function be named like '..._ordered_remove'
> to reflect that?
> 
> Alexander
> 

I see dynarray works similar to c++ vector container and the remove
usage on subsequent patch expects order preservation.  So I would
prefer to use the other way around your suggestion: to add a
unordered_remove if the case.
diff mbox series

Patch

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);
                     }
                 }