From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS22989 209.51.188.0/24 X-Spam-Status: No, score=-3.8 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 543FA1F5AE for ; Sat, 12 Jun 2021 00:27:17 +0000 (UTC) Received: from localhost ([::1]:60516 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lrrUa-0001jI-B2 for normalperson@yhbt.net; Fri, 11 Jun 2021 20:27:16 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:54182) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lrrTi-0000AX-KC for bug-gnulib@gnu.org; Fri, 11 Jun 2021 20:26:22 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:39096) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lrrTc-0003oX-No for bug-gnulib@gnu.org; Fri, 11 Jun 2021 20:26:22 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 426E4160129 for ; Fri, 11 Jun 2021 17:26:11 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id HiN25mh61zMv; Fri, 11 Jun 2021 17:26:09 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 1C1C516011F; Fri, 11 Jun 2021 17:26:09 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id 1X9SaYtCbenc; Fri, 11 Jun 2021 17:26:08 -0700 (PDT) Received: from day.example.com (cpe-172-91-119-151.socal.res.rr.com [172.91.119.151]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id CCA22160095; Fri, 11 Jun 2021 17:26:08 -0700 (PDT) From: Paul Eggert To: bug-gnulib@gnu.org Subject: [PATCH 02/13] xalloc: new idx_t-based allocators Date: Fri, 11 Jun 2021 17:25:42 -0700 Message-Id: <20210612002553.1105537-2-eggert@cs.ucla.edu> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210612002553.1105537-1-eggert@cs.ucla.edu> References: <20210612002553.1105537-1-eggert@cs.ucla.edu> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass client-ip=131.179.128.68; envelope-from=eggert@cs.ucla.edu; helo=zimbra.cs.ucla.edu X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Paul Eggert Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" This is for code that prefers to use idx_t for sizes. * lib/xalloc.h (ximalloc, xizalloc, xicalloc, xirealloc) (xireallocarray, ximemdup, ximemdup0) [GNULIB_XALLOC]: New decls. (x2nrealloc): Now just a decl, as the body is moved into xmalloc.c. * lib/xmalloc.c: Include ialloc.h. Rename some local parameters to be consistent with the .h files. (nonnull): New static function. (xmalloc, xcalloc): Simplify by using nonnull. (ximalloc, xirealloc, xireallocarray, xizalloc, xicalloc) (ximemdup, ximemdup0): New functions. (x2nrealloc): Moved here from xalloc.h. * modules/xalloc (Depends-on): Add ialloc. --- ChangeLog | 15 ++++ lib/xalloc.h | 114 ++++--------------------- lib/xmalloc.c | 224 +++++++++++++++++++++++++++++++++++++++---------- modules/xalloc | 1 + 4 files changed, 212 insertions(+), 142 deletions(-) diff --git a/ChangeLog b/ChangeLog index dd9aa5015..42d748a38 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,20 @@ 2021-06-11 Paul Eggert =20 + xalloc: new idx_t-based allocators + This is for code that prefers to use idx_t for sizes. + * lib/xalloc.h (ximalloc, xizalloc, xicalloc, xirealloc) + (xireallocarray, ximemdup, ximemdup0) [GNULIB_XALLOC]: + New decls. + (x2nrealloc): Now just a decl, as the body is moved into xmalloc.c. + * lib/xmalloc.c: Include ialloc.h. + Rename some local parameters to be consistent with the .h files. + (nonnull): New static function. + (xmalloc, xcalloc): Simplify by using nonnull. + (ximalloc, xirealloc, xireallocarray, xizalloc, xicalloc) + (ximemdup, ximemdup0): New functions. + (x2nrealloc): Moved here from xalloc.h. + * modules/xalloc (Depends-on): Add ialloc. + ialloc: new module * lib/ialloc.c, lib/ialloc.h, modules/ialloc: New files. =20 diff --git a/lib/xalloc.h b/lib/xalloc.h index 6cd7a680c..70ef0971f 100644 --- a/lib/xalloc.h +++ b/lib/xalloc.h @@ -53,21 +53,26 @@ extern "C" { =20 #if GNULIB_XALLOC =20 -void *xmalloc (size_t s) - _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE ((1)); -void *xzalloc (size_t s) - _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE ((1)); +void *xmalloc (size_t s) _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE (= (1)); +void *ximalloc (idx_t s) _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE (= (1)); +void *xzalloc (size_t s) _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE (= (1)); +void *xizalloc (idx_t s) _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE (= (1)); void *xcalloc (size_t n, size_t s) - _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE ((1, 2)); -void *xrealloc (void *p, size_t s) - _GL_ATTRIBUTE_ALLOC_SIZE ((2)); + _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE ((1, 2)); +void *xicalloc (idx_t n, idx_t s) + _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_ALLOC_SIZE ((1, 2)); +void *xrealloc (void *p, size_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2)); +void *xirealloc (void *p, idx_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2)); void *xreallocarray (void *p, size_t n, size_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2, 3)); -void *x2realloc (void *p, size_t *pn); -void *xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min, - ptrdiff_t nitems_max, idx_t item_size); -void *xmemdup (void const *p, size_t s) - _GL_ATTRIBUTE_ALLOC_SIZE ((2)); +void *xireallocarray (void *p, idx_t n, idx_t s) + _GL_ATTRIBUTE_ALLOC_SIZE ((2, 3)); +void *x2realloc (void *p, size_t *ps); /* superseded by xpalloc */ +void *x2nrealloc (void *p, size_t *pn, size_t s); /* superseded by xpall= oc */ +void *xpalloc (void *pa, idx_t *pn, idx_t n_incr_min, ptrdiff_t n_max, i= dx_t s); +void *xmemdup (void const *p, size_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2)); +void *ximemdup (void const *p, idx_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2)); +char *ximemdup0 (void const *p, idx_t s) _GL_ATTRIBUTE_MALLOC; char *xstrdup (char const *str) _GL_ATTRIBUTE_MALLOC; =20 @@ -120,91 +125,6 @@ xnrealloc (void *p, size_t n, size_t s) return xreallocarray (p, n, s); } =20 -/* If P is null, allocate a block of at least *PN such objects; - otherwise, reallocate P so that it contains more than *PN objects - each of S bytes. S must be nonzero. Set *PN to the new number of - objects, and return the pointer to the new block. *PN is never set - to zero, and the returned pointer is never null. - - Repeated reallocations are guaranteed to make progress, either by - allocating an initial block with a nonzero size, or by allocating a - larger block. - - In the following implementation, nonzero sizes are increased by a - factor of approximately 1.5 so that repeated reallocations have - O(N) overall cost rather than O(N**2) cost, but the - specification for this function does not guarantee that rate. - - Here is an example of use: - - int *p =3D NULL; - size_t used =3D 0; - size_t allocated =3D 0; - - void - append_int (int value) - { - if (used =3D=3D allocated) - p =3D x2nrealloc (p, &allocated, sizeof *p); - p[used++] =3D value; - } - - This causes x2nrealloc to allocate a block of some nonzero size the - first time it is called. - - To have finer-grained control over the initial size, set *PN to a - nonzero value before calling this function with P =3D=3D NULL. For - example: - - int *p =3D NULL; - size_t used =3D 0; - size_t allocated =3D 0; - size_t allocated1 =3D 1000; - - void - append_int (int value) - { - if (used =3D=3D allocated) - { - p =3D x2nrealloc (p, &allocated1, sizeof *p); - allocated =3D allocated1; - } - p[used++] =3D value; - } - - */ - -XALLOC_INLINE void * -x2nrealloc (void *p, size_t *pn, size_t s) -{ - size_t n =3D *pn; - - if (! p) - { - if (! n) - { - /* The approximate size to use for initial small allocation - requests, when the invoking code specifies an old size of - zero. This is the largest "small" request for the GNU C - library malloc. */ - enum { DEFAULT_MXFAST =3D 64 * sizeof (size_t) / 4 }; - - n =3D DEFAULT_MXFAST / s; - n +=3D !n; - } - } - else - { - /* Set N =3D floor (1.5 * N) + 1 to make progress even if N =3D=3D= 0. */ - if (INT_ADD_WRAPV (n, (n >> 1) + 1, &n)) - xalloc_die (); - } - - p =3D xreallocarray (p, n, s); - *pn =3D n; - return p; -} - /* Return a pointer to a new buffer of N bytes. This is like xmalloc, except it returns char *. */ =20 diff --git a/lib/xmalloc.c b/lib/xmalloc.c index 88698fade..413ee1b3c 100644 --- a/lib/xmalloc.c +++ b/lib/xmalloc.c @@ -21,35 +21,53 @@ =20 #include "xalloc.h" =20 +#include "ialloc.h" #include "intprops.h" #include "minmax.h" =20 #include #include =20 -/* Allocate N bytes of memory dynamically, with error checking. */ - -void * -xmalloc (size_t n) +static void * +nonnull (void *p) { - void *p =3D malloc (n); if (!p) xalloc_die (); return p; } =20 -/* Change the size of an allocated block of memory P to N bytes, +/* Allocate S bytes of memory dynamically, with error checking. */ + +void * +xmalloc (size_t s) +{ + return nonnull (malloc (s)); +} + +void * +ximalloc (idx_t s) +{ + return nonnull (imalloc (s)); +} + +/* Change the size of an allocated block of memory P to S bytes, with error checking. */ =20 void * -xrealloc (void *p, size_t n) +xrealloc (void *p, size_t s) { - void *r =3D realloc (p, n); - if (!r && (!p || n)) + void *r =3D realloc (p, s); + if (!r && (!p || s)) xalloc_die (); return r; } =20 +void * +xirealloc (void *p, idx_t s) +{ + return nonnull (irealloc (p, s)); +} + /* Change the size of an allocated block of memory P to an array of N objects each of S bytes, with error checking. */ =20 @@ -62,26 +80,117 @@ xreallocarray (void *p, size_t n, size_t s) return r; } =20 -/* If P is null, allocate a block of at least *PN bytes; otherwise, - reallocate P so that it contains more than *PN bytes. *PN must be - nonzero unless P is null. Set *PN to the new block's size, and - return the pointer to the new block. *PN is never set to zero, and +void * +xireallocarray (void *p, idx_t n, idx_t s) +{ + return nonnull (ireallocarray (p, n, s)); +} + +/* If P is null, allocate a block of at least *PS bytes; otherwise, + reallocate P so that it contains more than *PS bytes. *PS must be + nonzero unless P is null. Set *PS to the new block's size, and + return the pointer to the new block. *PS is never set to zero, and the returned pointer is never null. */ =20 void * -x2realloc (void *p, size_t *pn) +x2realloc (void *p, size_t *ps) { - return x2nrealloc (p, pn, 1); + return x2nrealloc (p, ps, 1); } =20 -/* Grow PA, which points to an array of *NITEMS items, and return the - location of the reallocated array, updating *NITEMS to reflect its - new size. The new array will contain at least NITEMS_INCR_MIN more - items, but will not contain more than NITEMS_MAX items total. - ITEM_SIZE is the size of each item, in bytes. +/* If P is null, allocate a block of at least *PN such objects; + otherwise, reallocate P so that it contains more than *PN objects + each of S bytes. S must be nonzero. Set *PN to the new number of + objects, and return the pointer to the new block. *PN is never set + to zero, and the returned pointer is never null. + + Repeated reallocations are guaranteed to make progress, either by + allocating an initial block with a nonzero size, or by allocating a + larger block. + + In the following implementation, nonzero sizes are increased by a + factor of approximately 1.5 so that repeated reallocations have + O(N) overall cost rather than O(N**2) cost, but the + specification for this function does not guarantee that rate. + + Here is an example of use: + + int *p =3D NULL; + size_t used =3D 0; + size_t allocated =3D 0; + + void + append_int (int value) + { + if (used =3D=3D allocated) + p =3D x2nrealloc (p, &allocated, sizeof *p); + p[used++] =3D value; + } + + This causes x2nrealloc to allocate a block of some nonzero size the + first time it is called. + + To have finer-grained control over the initial size, set *PN to a + nonzero value before calling this function with P =3D=3D NULL. For + example: + + int *p =3D NULL; + size_t used =3D 0; + size_t allocated =3D 0; + size_t allocated1 =3D 1000; + + void + append_int (int value) + { + if (used =3D=3D allocated) + { + p =3D x2nrealloc (p, &allocated1, sizeof *p); + allocated =3D allocated1; + } + p[used++] =3D value; + } + + */ =20 - ITEM_SIZE and NITEMS_INCR_MIN must be positive. *NITEMS must be - nonnegative. If NITEMS_MAX is -1, it is treated as if it were +void * +x2nrealloc (void *p, size_t *pn, size_t s) +{ + size_t n =3D *pn; + + if (! p) + { + if (! n) + { + /* The approximate size to use for initial small allocation + requests, when the invoking code specifies an old size of + zero. This is the largest "small" request for the GNU C + library malloc. */ + enum { DEFAULT_MXFAST =3D 64 * sizeof (size_t) / 4 }; + + n =3D DEFAULT_MXFAST / s; + n +=3D !n; + } + } + else + { + /* Set N =3D floor (1.5 * N) + 1 to make progress even if N =3D=3D= 0. */ + if (INT_ADD_WRAPV (n, (n >> 1) + 1, &n)) + xalloc_die (); + } + + p =3D xreallocarray (p, n, s); + *pn =3D n; + return p; +} + +/* Grow PA, which points to an array of *PN items, and return the + location of the reallocated array, updating *PN to reflect its + new size. The new array will contain at least N_INCR_MIN more + items, but will not contain more than N_MAX items total. + S is the size of each item, in bytes. + + S and N_INCR_MIN must be positive. *PN must be + nonnegative. If N_MAX is -1, it is treated as if it were infinity. =20 If PA is null, then allocate a new array instead of reallocating @@ -91,10 +200,9 @@ x2realloc (void *p, size_t *pn) { free (A); A =3D xpalloc (NULL, &AITEMS, ...); }. */ =20 void * -xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min, - ptrdiff_t nitems_max, idx_t item_size) +xpalloc (void *pa, idx_t *pn, idx_t n_incr_min, ptrdiff_t n_max, idx_t s= ) { - idx_t n0 =3D *nitems; + idx_t n0 =3D *pn; =20 /* The approximate size to use for initial small allocation requests. This is the largest "small" request for the GNU C @@ -103,14 +211,14 @@ xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr= _min, =20 /* If the array is tiny, grow it to about (but no greater than) DEFAULT_MXFAST bytes. Otherwise, grow it by about 50%. - Adjust the growth according to three constraints: NITEMS_INCR_MIN, - NITEMS_MAX, and what the C language can represent safely. */ + Adjust the growth according to three constraints: N_INCR_MIN, + N_MAX, and what the C language can represent safely. */ =20 idx_t n; if (INT_ADD_WRAPV (n0, n0 >> 1, &n)) n =3D IDX_MAX; - if (0 <=3D nitems_max && nitems_max < n) - n =3D nitems_max; + if (0 <=3D n_max && n_max < n) + n =3D n_max; =20 /* NBYTES is of a type suitable for holding the count of bytes in an o= bject. This is typically idx_t, but it should be size_t on (theoretical?) @@ -122,35 +230,41 @@ xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr= _min, size_t nbytes; #endif idx_t adjusted_nbytes - =3D (INT_MULTIPLY_WRAPV (n, item_size, &nbytes) + =3D (INT_MULTIPLY_WRAPV (n, s, &nbytes) ? MIN (IDX_MAX, SIZE_MAX) : nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0); if (adjusted_nbytes) { - n =3D adjusted_nbytes / item_size; - nbytes =3D adjusted_nbytes - adjusted_nbytes % item_size; + n =3D adjusted_nbytes / s; + nbytes =3D adjusted_nbytes - adjusted_nbytes % s; } =20 if (! pa) - *nitems =3D 0; - if (n - n0 < nitems_incr_min - && (INT_ADD_WRAPV (n0, nitems_incr_min, &n) - || (0 <=3D nitems_max && nitems_max < n) - || INT_MULTIPLY_WRAPV (n, item_size, &nbytes))) + *pn =3D 0; + if (n - n0 < n_incr_min + && (INT_ADD_WRAPV (n0, n_incr_min, &n) + || (0 <=3D n_max && n_max < n) + || INT_MULTIPLY_WRAPV (n, s, &nbytes))) xalloc_die (); pa =3D xrealloc (pa, nbytes); - *nitems =3D n; + *pn =3D n; return pa; } =20 -/* Allocate N bytes of zeroed memory dynamically, with error checking. +/* Allocate S bytes of zeroed memory dynamically, with error checking. There's no need for xnzalloc (N, S), since it would be equivalent to xcalloc (N, S). */ =20 void * -xzalloc (size_t n) +xzalloc (size_t s) { - return xcalloc (n, 1); + return xcalloc (s, 1); +} + +void * +xizalloc (idx_t s) +{ + return xicalloc (s, 1); } =20 /* Allocate zeroed memory for N elements of S bytes, with error @@ -159,10 +273,13 @@ xzalloc (size_t n) void * xcalloc (size_t n, size_t s) { - void *p =3D calloc (n, s); - if (!p) - xalloc_die (); - return p; + return nonnull (calloc (n, s)); +} + +void * +xicalloc (idx_t n, idx_t s) +{ + return nonnull (icalloc (n, s)); } =20 /* Clone an object P of size S, with error checking. There's no need @@ -175,6 +292,23 @@ xmemdup (void const *p, size_t s) return memcpy (xmalloc (s), p, s); } =20 +void * +ximemdup (void const *p, idx_t s) +{ + return memcpy (ximalloc (s), p, s); +} + +/* Clone an object P of size S, with error checking. Append + a terminating NUL byte. */ + +char * +ximemdup0 (void const *p, idx_t s) +{ + char *result =3D ximalloc (s + 1); + result[s] =3D 0; + return memcpy (result, p, s); +} + /* Clone STRING. */ =20 char * diff --git a/modules/xalloc b/modules/xalloc index 0dbae1c86..0fc3836c2 100644 --- a/modules/xalloc +++ b/modules/xalloc @@ -10,6 +10,7 @@ Depends-on: c99 calloc-gnu extern-inline +ialloc idx intprops malloc-gnu --=20 2.30.2