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 X-Patchwork-Id: 77018 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EBFD73875462 for ; Tue, 3 Oct 2023 12:23:57 +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-Google-Smtp-Source: AGHT+IHtreGKeWdpKM+6B66G/X6BhaImTYHltO9GmnUwrYfqWtE3ZAg7PoodExQNANO46j+eTMEmfQ== 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+patchwork=sourceware.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; } }