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 Netto X-Patchwork-Id: 127176 Delivered-To: patch@linaro.org Received: by 10.46.124.24 with SMTP id x24csp456146ljc; Wed, 7 Feb 2018 05:10:04 -0800 (PST) X-Google-Smtp-Source: AH8x225kjc5e8zacyqPZxAddbRPIHAtWzp8P/hVeWwbNyprVUXp608CUBwsyO63L5wRziboCPuZ7 X-Received: by 10.98.157.93 with SMTP id i90mr6074322pfd.58.1518009004789; Wed, 07 Feb 2018 05:10:04 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1518009004; cv=none; d=google.com; s=arc-20160816; b=bKfXDELTWJvayCBKBDKLoYTzhHLy6A4j9vJ1AlEzoN4CFay/jT3yj+ljNzGCXA1TfN ASqhg/I/5puXCrogua7ZiTyNoZSvMBGksc6Fey1CPsZCVIMOKGp4vYwiJYhYOGlilnLF Z/OHtoFblDjHmclheZ8xkZpNecerhbUflWJ5NEOIeGretRYjwHWqmRGhb/oTbULTTMhA S1aziGl94BxsM4Roz1OLxRXMMxZbtyGIR5GKjDn1nKbjQKbfekmnCZe7Iu5dHMIuVcVK AI19qhKy5MnKU5GXJNx19t2X69jJKC9zOV7infneLabuUxrltGGl+NrevEMcv26NGR5d 9oOA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=Gtgx6DdVXOT8P5YuWoMXUXW48rQ0DFCN+cRkZ/iYOhg=; b=lp67ybJMTJ25b74Ir69dF3KxSUdQPf9WXprtBVMshgtw+KMnXgVxxfEB48fE1l0NMm EL0r96wVsJX1oAH1GOncyOFx4B5qHmg+V09WX7JYWyAqramDWYMNYEYbWfsJtZDGcern 66pSAxUhSqwhOiVleCaMRQrnZlXl9BzaZL3E+cfvmOFp1pKE0d+SST6SZxeUcKKxbEaM SXWXTXZ4/77fIOGuV4FKeBsdH4dfcUnAVe/Xkh69NS6OPPCdrB0IEsfEESsByB/SjBX1 gyy4t8QxfqcQpPPwQP3EvoIZg3hXZNrPrNPYYZh471KtS2Eos+7RFiGZdoqtLeDJZnUN +HUw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=q0Mw0RTS; spf=pass (google.com: domain of libc-alpha-return-90099-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-90099-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id v8si918614pgc.724.2018.02.07.05.10.04 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 07 Feb 2018 05:10:04 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-90099-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=q0Mw0RTS; spf=pass (google.com: domain of libc-alpha-return-90099-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-90099-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=lK6jl700S7WaPTgA6xmZgyMU1blIyFI +ruCBe5BW9hyhymPqEvMnzABuXZAX1SX9bWLOH/9iBohMSD63kJd7BTeCeAw8sVE pZyoZFV2TIev/ZgUpt9uAD7Q3o4YMyCJeDr1SVfIiVsmJwF/ME2tC25pA1Wf71VL yUiWBNF0Qpac= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=kFXmskt7S9cAJhGoQgUpcIkwn74=; b=q0Mw0 RTSGu91eqPb451zDZAfu5l58holeUmtJ8SL0Xl8eipOBf7brXnDqxb3m75Wcuv3q j9XI47e43/6AynE4+hBzLamS4wsxB00nwCgaDlvCiil8I7Yno9A/DPEuvsaKILOh EAZL8nQ5ZdkE14Cbh2XgmzNwZkZlnQIqZwUcRk= 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-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(-) -- 2.7.4 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); } }