From patchwork Wed Feb 7 13:09:26 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 25855 Received: (qmail 11993 invoked by alias); 7 Feb 2018 13:09:49 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 11844 invoked by uid 89); 7 Feb 2018 13:09:48 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qk0-f195.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=Gtgx6DdVXOT8P5YuWoMXUXW48rQ0DFCN+cRkZ/iYOhg=; b=gobuhXQ0rrmxZ871z0X7Bz5I6avDAcPBq/5+dYGm2tcVh1KxBKabcc7atk8+/9X5mb qLLIjhE1JmVefJx+E52P8nI43bfw2yLy0rG0jM7NJqANqJ54jPxPX89Rg8L6ZtmBJO1D ec9fs3hWDk7s4DHwS/t0Bzd/PGoyjQ9KZHcnWB6lDT1EQ0yROJ63WJED12mhIaGY6UV6 Q4boJiXQJM1wq6V/zPlgb9r/l3vTblvR6MVUD8PLO+F/NAkk+pnKvV3qklDj5RyXrvwo DwCFn6XQMHyUyPG6cXgEWJbWhU/vhJY3DyXtj4eFqZUsopBDkNRNZNxddPx8FYJopg5k uTuw== X-Gm-Message-State: APf1xPDkym7sWLPpRljz9bJ8GPj/hW5vwZEWCN3jDgrDVDf3nRVEsVxp cEp3AqfkytXICoMdPSNYS1mjO/CYxmM= X-Google-Smtp-Source: AH8x224jnU+eCnzd0+Fu5cD3CXj92dxLS/qbFtrB9jpLhzAGHZ9my2rd2j7ky6K6trJsCXDsgM/gMw== X-Received: by 10.55.20.232 with SMTP id 101mr5110171qku.264.1518008979146; Wed, 07 Feb 2018 05:09:39 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 2/3] dynarray: Implement remove function Date: Wed, 7 Feb 2018 11:09:26 -0200 Message-Id: <1518008967-8310-2-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1518008967-8310-1-git-send-email-adhemerval.zanella@linaro.org> 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); } }