From e54b645fc6b8422562327443bda575c65d931fbd Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 28 Mar 2021 20:02:21 -0700 Subject: [PATCH] xalloc: new function xpalloc, from dfa MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Move xpalloc from dfa.c to xmalloc.c and change it from static to extern. The function is useful in other contexts; I’m about to use it in coreutils. * lib/dfa.c: Include idx.h, instead of rolling our own idx_t and IDX_MAX. Do not include intprops.h; no longer needed. (xpalloc): Move from here ... * lib/xmalloc.c (xpalloc): ... to here, and make it extern. Include intprops.h and minmax.h, needed by xpalloc. * lib/xalloc.h: Include idx.h, for idx_t. * modules/dfa (Depends-on): Add idx; remove intprops. * modules/xalloc (Depends-on): Add idx, intprops, minmax. --- ChangeLog | 15 +++++++++++ lib/dfa.c | 68 +------------------------------------------------- lib/xalloc.h | 3 +++ lib/xmalloc.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++ modules/dfa | 2 +- modules/xalloc | 3 +++ 6 files changed, 86 insertions(+), 68 deletions(-) diff --git a/ChangeLog b/ChangeLog index 9f010fd4ec..78bf3a5a74 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +2021-03-28 Paul Eggert + + xalloc: new function xpalloc, from dfa + Move xpalloc from dfa.c to xmalloc.c and change it from static to + extern. The function is useful in other contexts; I’m about to + use it in coreutils. + * lib/dfa.c: Include idx.h, instead of rolling our own idx_t and + IDX_MAX. Do not include intprops.h; no longer needed. + (xpalloc): Move from here ... + * lib/xmalloc.c (xpalloc): ... to here, and make it extern. + Include intprops.h and minmax.h, needed by xpalloc. + * lib/xalloc.h: Include idx.h, for idx_t. + * modules/dfa (Depends-on): Add idx; remove intprops. + * modules/xalloc (Depends-on): Add idx, intprops, minmax. + 2021-03-28 Bruno Haible linked-list tests: Add another test for SIGNAL_SAFE_LIST. diff --git a/lib/dfa.c b/lib/dfa.c index 4929e4c348..33de2fb82e 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -25,6 +25,7 @@ #include "dfa.h" #include "flexmember.h" +#include "idx.h" #include #include @@ -34,12 +35,6 @@ #include #include -/* Another name for ptrdiff_t, for sizes of objects and nonnegative - indexes into objects. It is signed to help catch integer overflow. - It has its own name because it is for nonnegative values only. */ -typedef ptrdiff_t idx_t; -static idx_t const IDX_MAX = PTRDIFF_MAX; - static bool streq (char const *a, char const *b) { @@ -57,7 +52,6 @@ isasciidigit (char c) #include -#include "intprops.h" #include "xalloc.h" #include "localeinfo.h" @@ -791,66 +785,6 @@ emptyset (charclass const *s) return w == 0; } -/* 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. - - 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 - infinity. - - If PA is null, then allocate a new array instead of reallocating - the old one. - - Thus, to grow an array A without saving its old contents, do - { free (A); A = xpalloc (NULL, &AITEMS, ...); }. */ - -static void * -xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min, - ptrdiff_t nitems_max, idx_t item_size) -{ - idx_t n0 = *nitems; - - /* The approximate size to use for initial small allocation - requests. This is the largest "small" request for the GNU C - library malloc. */ - enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 }; - - /* 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. */ - - idx_t n, nbytes; - if (INT_ADD_WRAPV (n0, n0 >> 1, &n)) - n = IDX_MAX; - if (0 <= nitems_max && nitems_max < n) - n = nitems_max; - - idx_t adjusted_nbytes - = ((INT_MULTIPLY_WRAPV (n, item_size, &nbytes) || SIZE_MAX < nbytes) - ? MIN (IDX_MAX, SIZE_MAX) - : nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0); - if (adjusted_nbytes) - { - n = adjusted_nbytes / item_size; - nbytes = adjusted_nbytes - adjusted_nbytes % item_size; - } - - if (! pa) - *nitems = 0; - if (n - n0 < nitems_incr_min - && (INT_ADD_WRAPV (n0, nitems_incr_min, &n) - || (0 <= nitems_max && nitems_max < n) - || INT_MULTIPLY_WRAPV (n, item_size, &nbytes))) - xalloc_die (); - pa = xrealloc (pa, nbytes); - *nitems = n; - return pa; -} - /* Ensure that the array addressed by PA holds at least I + 1 items. Either return PA, or reallocate the array and return its new address. Although PA may be null, the returned value is never null. diff --git a/lib/xalloc.h b/lib/xalloc.h index 7ab68f4e6c..76d83c63c1 100644 --- a/lib/xalloc.h +++ b/lib/xalloc.h @@ -21,6 +21,7 @@ #include #include +#include "idx.h" #include "xalloc-oversized.h" #ifndef _GL_INLINE_HEADER_BEGIN @@ -59,6 +60,8 @@ void *xcalloc (size_t n, size_t s) void *xrealloc (void *p, size_t s) _GL_ATTRIBUTE_ALLOC_SIZE ((2)); 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)); char *xstrdup (char const *str) diff --git a/lib/xmalloc.c b/lib/xmalloc.c index 4203f19ce5..faeccacc9b 100644 --- a/lib/xmalloc.c +++ b/lib/xmalloc.c @@ -21,6 +21,9 @@ #include "xalloc.h" +#include "intprops.h" +#include "minmax.h" + #include #include @@ -87,6 +90,66 @@ x2realloc (void *p, size_t *pn) return x2nrealloc (p, pn, 1); } +/* 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. + + 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 + infinity. + + If PA is null, then allocate a new array instead of reallocating + the old one. + + Thus, to grow an array A without saving its old contents, do + { free (A); A = xpalloc (NULL, &AITEMS, ...); }. */ + +void * +xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min, + ptrdiff_t nitems_max, idx_t item_size) +{ + idx_t n0 = *nitems; + + /* The approximate size to use for initial small allocation + requests. This is the largest "small" request for the GNU C + library malloc. */ + enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 }; + + /* 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. */ + + idx_t n, nbytes; + if (INT_ADD_WRAPV (n0, n0 >> 1, &n)) + n = IDX_MAX; + if (0 <= nitems_max && nitems_max < n) + n = nitems_max; + + idx_t adjusted_nbytes + = ((INT_MULTIPLY_WRAPV (n, item_size, &nbytes) || SIZE_MAX < nbytes) + ? MIN (IDX_MAX, SIZE_MAX) + : nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0); + if (adjusted_nbytes) + { + n = adjusted_nbytes / item_size; + nbytes = adjusted_nbytes - adjusted_nbytes % item_size; + } + + if (! pa) + *nitems = 0; + if (n - n0 < nitems_incr_min + && (INT_ADD_WRAPV (n0, nitems_incr_min, &n) + || (0 <= nitems_max && nitems_max < n) + || INT_MULTIPLY_WRAPV (n, item_size, &nbytes))) + xalloc_die (); + pa = xrealloc (pa, nbytes); + *nitems = n; + return pa; +} + /* Allocate N 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). */ diff --git a/modules/dfa b/modules/dfa index 303957fa50..4b78ef4870 100644 --- a/modules/dfa +++ b/modules/dfa @@ -12,7 +12,7 @@ assert c99 ctype flexmember -intprops +idx locale regex stdbool diff --git a/modules/xalloc b/modules/xalloc index 65007561b5..5fa386a5d9 100644 --- a/modules/xalloc +++ b/modules/xalloc @@ -9,6 +9,9 @@ m4/xalloc.m4 Depends-on: c99 extern-inline +idx +intprops +minmax stdint xalloc-die xalloc-oversized -- 2.39.5