From patchwork Tue Oct 3 12:22:48 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 728730 Delivered-To: patch@linaro.org Received: by 2002:a5d:60c8:0:b0:31d:da82:a3b4 with SMTP id x8csp2112768wrt; Tue, 3 Oct 2023 05:23:52 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEAnsjNdJd3hNyVMsAM2T04htLSkOrgEMO7O6Qu/pIpIcAfudffc5l+0Ba3AgHfwX+nvTds X-Received: by 2002:a17:907:b1a:b0:9ae:699d:8a31 with SMTP id h26-20020a1709070b1a00b009ae699d8a31mr2092876ejl.33.1696335832086; Tue, 03 Oct 2023 05:23:52 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1696335832; cv=none; d=google.com; s=arc-20160816; b=fucUk9gzqPBPdgYgxdduUQfzMcAMLAgNGx1kC3kutzGoFFjjsB93WXnbvWKx8cxQqb 2woIfUI1qXkBwbST9vmPW8BNiGtRYyhJf5sKQeVKhf84GZPvymjL2dYQlO5Pfc6sTrx+ VQUeJVwSlkYFB4uXZdEIa6WUqslFrv1eoXFTlIRQs4NzDTBkyL7E8rwo+xLP0O0g1xxZ WEQgFQf4Q4T21ycc4YO5sO9ot50DHQ4DE9S7p+KujbC/kPt8wEP8Lr8Xk4Stsyf3if2I vIgcYmct7fVu+6xnVcBFMn6wuSy1q1UNDDeJnVlD9GMJ1IbWIHzSF9VD/JU5b2b5oKFa IFmA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:to:from :dkim-signature:dmarc-filter:delivered-to; bh=lalwyLl0SNT9fXfI43KwDyeZlEexF65og/8SxMtD+Sk=; fh=ubzLPtaquqORyAJ/TX35zypB35/iXKzZJOEWlgP8mu4=; b=ePM/QKM40iHDmw/Xaem5UNrrdVJRFqpRXJihpjGHudkg9axDexUUPPK2CkEIOSON5T YRK8ZelNur8ASqAmVFMAkxlmPr0Of7wz47BHqwEams+fMwLGfR3ZBUELBw+TLzvMa3Ip FWOwYgTEDY2bCO8kh0SY/GJwtlKdp8AtbtcVEAvqyrQFuskE9Z3wqXJ7rkEfKIM9P60K I7jb4mkz3IPn68+1APU9hrT6Y0oR3UAlM5E8LDXLes5+JLQLe/NHhXDGJ++1Z3tlzUus kvCeYFszetV5/YrLL6kYiECoMwg00HzE9iARiJJyeX0rJwCRZK9CAcIUlRllcT5TSQmY YOZQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b="kdI0ucU/"; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id k7-20020a170906578700b0099bd58fb8c5si625040ejq.751.2023.10.03.05.23.51 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 Oct 2023 05:23:52 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b="kdI0ucU/"; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1BD0B3861901 for ; Tue, 3 Oct 2023 12:23:51 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x62b.google.com (mail-pl1-x62b.google.com [IPv6:2607:f8b0:4864:20::62b]) by sourceware.org (Postfix) with ESMTPS id 087093857342 for ; Tue, 3 Oct 2023 12:23:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 087093857342 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-pl1-x62b.google.com with SMTP id d9443c01a7336-1c60a514f3aso6446685ad.3 for ; Tue, 03 Oct 2023 05:23:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1696335784; x=1696940584; darn=sourceware.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=lalwyLl0SNT9fXfI43KwDyeZlEexF65og/8SxMtD+Sk=; b=kdI0ucU/S2UiaIsGdKAZAb09BUru01CQ7r7DP+daGpyVAIMnkin9Jnv1d0HCQ1id8V jNj3Lo8Kq1nIYcYspKvRy46L2cZbnybAebhQphhROjEo1YpTJrXO4MKFVXzcA8soVFVf 7qGD7flySseeVMpRM6KA6ZC1TMNml1NUQQQzvkssVPUuki0iKaFSx6H7fa0EJz27MKil N3xJ0dZa0GLRHtT1kkh45BiMAj7gZyx/nsjxpNoYQ3Wagl4qTu64SwGK5Y05VAyG+fLH 6cetc54zTI2KtV+c1TdqOpZiQw0Y+mQjSK4j3UIVUiXxFde8iw0K+mZadi7sYKpwJUPv gVyg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696335784; x=1696940584; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=lalwyLl0SNT9fXfI43KwDyeZlEexF65og/8SxMtD+Sk=; b=Dl2H+YHB+lg8Ba3HJRHvn6tTb629KW2Cielo7gKn7yH+xHZm5AKaNEd2BmtwQ69OBT fldzKkTbgf16l2xuQJK4kzTozXTIb0bUBs1GvqBb/Rg1yBQGAgXvzCPKug8DjLn/kfzV 4Fs8cBCzLDL60yN6ffyHOQR0Z8gNskurSdTcvFw1VpidDtgiGsFlCDrl/iqNRQWjX0KM hXF7jipmLKDoTOq4MxS1ab9ODqjfdsqQfViTnMSxAGwcqwtYE07APVVUZwRSPog+3Fee 3SUF6aJtZ/GnlXRr1qQjk/qVOlUuC9kSZezwPCcO1riVWezbM74pIsn6ih5mCj3GcU5t nP8w== X-Gm-Message-State: AOJu0Yz0KCJWKZyaDnoEgiQd/+znI864aL7vko/2AhKMgUynxqz3140Y 4/iBdGNWKEDSuSDCgU3LCVYAktkdfj1e/fDriIC23g== X-Received: by 2002:a17:902:ecce:b0:1c7:1fbc:b9e7 with SMTP id a14-20020a170902ecce00b001c71fbcb9e7mr16325402plh.43.1696335784339; Tue, 03 Oct 2023 05:23:04 -0700 (PDT) Received: from mandiga.. ([2804:1b3:a7c1:feaf:31ef:b40c:b4e5:77c]) by smtp.gmail.com with ESMTPSA id b1-20020a170902d30100b001c5de2f1686sm1403881plc.99.2023.10.03.05.23.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 Oct 2023 05:23:03 -0700 (PDT) From: Adhemerval Zanella To: libc-alpha@sourceware.org, Noah Goldstein , Paul Eggert , Florian Weimer Subject: [PATCH v8 4/7] stdlib: qsort: Move some macros to inline function Date: Tue, 3 Oct 2023 09:22:48 -0300 Message-Id: <20231003122251.3325435-5-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20231003122251.3325435-1-adhemerval.zanella@linaro.org> References: <20231003122251.3325435-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-12.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+patch=linaro.org@sourceware.org --- stdlib/qsort.c | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-) Reviewed-by: Noah Goldstein diff --git a/stdlib/qsort.c b/stdlib/qsort.c index 5691249a9b..80706b3357 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -100,15 +100,28 @@ typedef struct char *hi; } stack_node; -/* The next 4 #defines implement a very fast in-line stack abstraction. */ /* The stack needs log (total_elements) entries (we could even subtract log(MAX_THRESH)). Since total_elements has type size_t, we get as upper bound for log (total_elements): bits per byte (CHAR_BIT) * sizeof(size_t). */ -#define STACK_SIZE (CHAR_BIT * sizeof (size_t)) -#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) -#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) -#define STACK_NOT_EMPTY (stack < top) +enum { STACK_SIZE = CHAR_BIT * sizeof (size_t) }; + +static inline stack_node * +push (stack_node *top, char *lo, char *hi) +{ + top->lo = lo; + top->hi = hi; + return ++top; +} + +static inline stack_node * +pop (stack_node *top, char **lo, char **hi) +{ + --top; + *lo = top->lo; + *hi = top->hi; + return top; +} static inline void @@ -212,11 +225,9 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, char *lo = base_ptr; char *hi = &lo[size * (total_elems - 1)]; stack_node stack[STACK_SIZE]; - stack_node *top = stack; - - PUSH (NULL, NULL); + stack_node *top = stack + 1; - while (STACK_NOT_EMPTY) + while (stack < top) { char *left_ptr; char *right_ptr; @@ -281,7 +292,7 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, { if ((size_t) (hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ - POP (lo, hi); + top = pop (top, &lo, &hi); else /* Ignore small left partition. */ lo = left_ptr; @@ -292,13 +303,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, else if ((right_ptr - lo) > (hi - left_ptr)) { /* Push larger left partition indices. */ - PUSH (lo, right_ptr); + top = push (top, lo, right_ptr); lo = left_ptr; } else { /* Push larger right partition indices. */ - PUSH (left_ptr, hi); + top = push (top, left_ptr, hi); hi = right_ptr; } }