From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oo1-xc2c.google.com (mail-oo1-xc2c.google.com [IPv6:2607:f8b0:4864:20::c2c]) by sourceware.org (Postfix) with ESMTPS id 46B883858D20 for ; Tue, 11 Jul 2023 23:46:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 46B883858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-oo1-xc2c.google.com with SMTP id 006d021491bc7-5634db21a78so4471476eaf.0 for ; Tue, 11 Jul 2023 16:46:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1689119214; x=1691711214; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=DkAlMSXJju0mUHrXcKwNRhtZuKzKB0LCDSFC3MB4S8E=; b=YCwtXv9LrBMc18aF5Y3/tvqovkYwOFQlyDP2mvW8nc/IrFEsocGywRgDLDtgQ3Jo83 u9zfPeHqLUMu+wFA4KHgfbYUsV17GtYCXjrmvZs120LwnDzcJUPi0XfHo8pj15aTOzF2 7HUZQ0eCSIL2dJ4MGPZvCvoqY5vJGRvI3spyDthMzzwByidOgVZKrrSl2ccKdLpwEyNk SDJtRW0XkUwiUA6VlQYBnaMWetN27gFxUu0jp4HQMMA7rVXhUiBdtWpIyVMRWauRkt5t Wmivu4s0WWuNWfDDyJyTpD4eLkZZcREJ08NbktSiz3KJpJvWa5WC4qA3Rke3qWC1GV9M /Rbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689119214; x=1691711214; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DkAlMSXJju0mUHrXcKwNRhtZuKzKB0LCDSFC3MB4S8E=; b=LwxXOLPqjRfNzQZmgez6BuNNnrDp4PFL/fwa8mmjoyzEqEKGwHc4fWtdllbob/nJbt fYxXarItebT6QDiPW4iqCVSZrKZV5TR0mNNsZ7WUo0JLVO65FcgBuUUV4lHTV9Uul7Wp Lo7jKlm7lVvWBQH1VHYGhIIIo3vS90uGZBp2ILHopsdKhCGawp3LfBGjeZ3wNExNhmOV he8QhQcBdACmRh2HFn49lnR1tb1mFhZ1dSn1JXTFBNIGfWm79zVUYSRwqHdjDn4Zxjgi wkE5mDMvxFRzv+DKp9kh0QwlBluQzmHPhWkiv1+g39DEpOIuDhoic18uf0v2M9+Fie7F OIVw== X-Gm-Message-State: ABy/qLaE8dGVpkRFARRtrAcHvm89sMNPGMxNhJYSR3C6GzpG7HlG8M3k QCRcRWYkh96PkOO9fRrBzcS+qg5p3SIZf+0zm5IMhm4g X-Google-Smtp-Source: APBJJlF86vAxf5jmGH/Z+1aHKH8yTQJqj+c2WDKqw3hQIylZsekTfFM2ypnnsvCo+iKgahhYSxOKi9MugilAf+nKuE0= X-Received: by 2002:a4a:4942:0:b0:566:669d:bed0 with SMTP id z63-20020a4a4942000000b00566669dbed0mr12773511ooa.3.1689119214465; Tue, 11 Jul 2023 16:46:54 -0700 (PDT) MIME-Version: 1.0 References: <20230711190722.4028821-1-adhemerval.zanella@linaro.org> <20230711190722.4028821-3-adhemerval.zanella@linaro.org> In-Reply-To: <20230711190722.4028821-3-adhemerval.zanella@linaro.org> From: Noah Goldstein Date: Tue, 11 Jul 2023 18:46:40 -0500 Message-ID: Subject: Re: [PATCH v4 2/6] stdlib: Move insertion sort out qsort To: Adhemerval Zanella Cc: libc-alpha@sourceware.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-9.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, Jul 11, 2023 at 2:09=E2=80=AFPM Adhemerval Zanella via Libc-alpha wrote: > > --- > stdlib/qsort.c | 100 ++++++++++++++++++++++++++----------------------- > 1 file changed, 53 insertions(+), 47 deletions(-) > > diff --git a/stdlib/qsort.c b/stdlib/qsort.c > index 8a3331fdb4..00637208ab 100644 > --- a/stdlib/qsort.c > +++ b/stdlib/qsort.c > @@ -153,6 +153,58 @@ typedef struct > smaller partition. This *guarantees* no more than log (total_elem= s) > stack size is needed (actually O(1) in this case)! */ > > +static inline void > +insertion_sort (void *const pbase, size_t total_elems, size_t size, Maybe a less generic name would be better. Something like: "insertion_sort_qsort_partions" to indicate this is not just standard insertion sort but a helper for qsort. Just thinking about a reader grepping around in a year or so. > + swap_func_t swap_func, > + __compar_d_fn_t cmp, void *arg) > +{ > + char *base_ptr =3D (char *) pbase; > + char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; > + char *tmp_ptr =3D base_ptr; > +#define min(x, y) ((x) < (y) ? (x) : (y)) > + const size_t max_thresh =3D MAX_THRESH * size; > + char *thresh =3D min(end_ptr, base_ptr + max_thresh); > + char *run_ptr; > + > + /* Find smallest element in first threshold and place it at the > + array's beginning. This is the smallest array element, > + and the operation speeds up insertion sort's inner loop. */ > + > + for (run_ptr =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D siz= e) > + if (cmp (run_ptr, tmp_ptr, arg) < 0) > + tmp_ptr =3D run_ptr; > + > + if (tmp_ptr !=3D base_ptr) > + do_swap (tmp_ptr, base_ptr, size, swap_func); > + > + /* Insertion sort, running from left-hand-side up to right-hand-side. = */ > + > + run_ptr =3D base_ptr + size; > + while ((run_ptr +=3D size) <=3D end_ptr) > + { > + tmp_ptr =3D run_ptr - size; > + while (cmp (run_ptr, tmp_ptr, arg) < 0) > + tmp_ptr -=3D size; > + > + tmp_ptr +=3D size; > + if (tmp_ptr !=3D run_ptr) > + { > + char *trav; > + > + trav =3D run_ptr + size; > + while (--trav >=3D run_ptr) > + { > + char c =3D *trav; > + char *hi, *lo; > + > + for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi = =3D lo) > + *hi =3D *lo; > + *hi =3D c; > + } > + } > + } > +} > + > void > _quicksort (void *const pbase, size_t total_elems, size_t size, > __compar_d_fn_t cmp, void *arg) > @@ -275,51 +327,5 @@ _quicksort (void *const pbase, size_t total_elems, s= ize_t size, > for partitions below MAX_THRESH size. BASE_PTR points to the beginn= ing > of the array to sort, and END_PTR points at the very last element i= n > the array (*not* one beyond it!). */ > - > -#define min(x, y) ((x) < (y) ? (x) : (y)) > - > - { > - char *const end_ptr =3D &base_ptr[size * (total_elems - 1)]; > - char *tmp_ptr =3D base_ptr; > - char *thresh =3D min(end_ptr, base_ptr + max_thresh); > - char *run_ptr; > - > - /* Find smallest element in first threshold and place it at the > - array's beginning. This is the smallest array element, > - and the operation speeds up insertion sort's inner loop. */ > - > - for (run_ptr =3D tmp_ptr + size; run_ptr <=3D thresh; run_ptr +=3D s= ize) > - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) > - tmp_ptr =3D run_ptr; > - > - if (tmp_ptr !=3D base_ptr) > - do_swap (tmp_ptr, base_ptr, size, swap_func); > - > - /* Insertion sort, running from left-hand-side up to right-hand-side= . */ > - > - run_ptr =3D base_ptr + size; > - while ((run_ptr +=3D size) <=3D end_ptr) > - { > - tmp_ptr =3D run_ptr - size; > - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) > - tmp_ptr -=3D size; > - > - tmp_ptr +=3D size; > - if (tmp_ptr !=3D run_ptr) > - { > - char *trav; > - > - trav =3D run_ptr + size; > - while (--trav >=3D run_ptr) > - { > - char c =3D *trav; > - char *hi, *lo; > - > - for (hi =3D lo =3D trav; (lo -=3D size) >=3D tmp_ptr; hi= =3D lo) > - *hi =3D *lo; > - *hi =3D c; > - } > - } > - } > - } > + insertion_sort (pbase, total_elems, size, swap_func, cmp, arg); > } > -- > 2.34.1 >