contrib/gnu-sort/lib/xmalloc.c

   1 /* xmalloc.c -- malloc with out of memory checking
   2
   3    Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  19
  20 #if HAVE_CONFIG_H
  21 # include <config.h>
  22 #endif
  23
  24 #include "xalloc.h"
  25
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 #ifndef SIZE_MAX
  30 # define SIZE_MAX ((size_t) -1)
  31 #endif
  32
  33 /* Allocate an array of N objects, each with S bytes of memory,
  34    dynamically, with error checking.  S must be nonzero.  */
  35
  36 static inline void *
  37 xnmalloc_inline (size_t n, size_t s)
  38 {
  39   void *p;
  40   if (xalloc_oversized (n, s) || (! (p = malloc (n * s)) && n != 0))
  41     xalloc_die ();
  42   return p;
  43 }
  44
  45 void *
  46 xnmalloc (size_t n, size_t s)
  47 {
  48   return xnmalloc_inline (n, s);
  49 }
  50
  51 /* Allocate N bytes of memory dynamically, with error checking.  */
  52
  53 void *
  54 xmalloc (size_t n)
  55 {
  56   return xnmalloc_inline (n, 1);
  57 }
  58
  59 /* Change the size of an allocated block of memory P to an array of N
  60    objects each of S bytes, with error checking.  S must be nonzero.  */
  61
  62 static inline void *
  63 xnrealloc_inline (void *p, size_t n, size_t s)
  64 {
  65   if (xalloc_oversized (n, s) || (! (p = realloc (p, n * s)) && n != 0))
  66     xalloc_die ();
  67   return p;
  68 }
  69
  70 void *
  71 xnrealloc (void *p, size_t n, size_t s)
  72 {
  73   return xnrealloc_inline (p, n, s);
  74 }
  75
  76 /* Change the size of an allocated block of memory P to N bytes,
  77    with error checking.  */
  78
  79 void *
  80 xrealloc (void *p, size_t n)
  81 {
  82   return xnrealloc_inline (p, n, 1);
  83 }
  84
  85
  86 /* If P is null, allocate a block of at least *PN such objects;
  87    otherwise, reallocate P so that it contains more than *PN objects
  88    each of S bytes.  *PN must be nonzero unless P is null, and S must
  89    be nonzero.  Set *PN to the new number of objects, and return the
  90    pointer to the new block.  *PN is never set to zero, and the
  91    returned pointer is never null.
  92
  93    Repeated reallocations are guaranteed to make progress, either by
  94    allocating an initial block with a nonzero size, or by allocating a
  95    larger block.
  96
  97    In the following implementation, nonzero sizes are doubled so that
  98    repeated reallocations have O(N log N) overall cost rather than
  99    O(N**2) cost, but the specification for this function does not
 100    guarantee that sizes are doubled.
 101
 102    Here is an example of use:
 103
 104      int *p = NULL;
 105      size_t used = 0;
 106      size_t allocated = 0;
 107
 108      void
 109      append_int (int value)
 110        {
 111          if (used == allocated)
 112            p = x2nrealloc (p, &allocated, sizeof *p);
 113          p[used++] = value;
 114        }
 115
 116    This causes x2nrealloc to allocate a block of some nonzero size the
 117    first time it is called.
 118
 119    To have finer-grained control over the initial size, set *PN to a
 120    nonzero value before calling this function with P == NULL.  For
 121    example:
 122
 123      int *p = NULL;
 124      size_t used = 0;
 125      size_t allocated = 0;
 126      size_t allocated1 = 1000;
 127
 128      void
 129      append_int (int value)
 130        {
 131          if (used == allocated)
 132            {
 133              p = x2nrealloc (p, &allocated1, sizeof *p);
 134              allocated = allocated1;
 135            }
 136          p[used++] = value;
 137        }
 138
 139    */
 140
 141 static inline void *
 142 x2nrealloc_inline (void *p, size_t *pn, size_t s)
 143 {
 144   size_t n = *pn;
 145
 146   if (! p)
 147     {
 148       if (! n)
 149         {
 150           /* The approximate size to use for initial small allocation
 151              requests, when the invoking code specifies an old size of
 152              zero.  64 bytes is the largest "small" request for the
 153              GNU C library malloc.  */
 154           enum { DEFAULT_MXFAST = 64 };
 155
 156           n = DEFAULT_MXFAST / s;
 157           n += !n;
 158         }
 159     }
 160   else
 161     {
 162       if (SIZE_MAX / 2 / s < n)
 163         xalloc_die ();
 164       n *= 2;
 165     }
 166
 167   *pn = n;
 168   return xrealloc (p, n * s);
 169 }
 170
 171 void *
 172 x2nrealloc (void *p, size_t *pn, size_t s)
 173 {
 174   return x2nrealloc_inline (p, pn, s);
 175 }
 176
 177 /* If P is null, allocate a block of at least *PN bytes; otherwise,
 178    reallocate P so that it contains more than *PN bytes.  *PN must be
 179    nonzero unless P is null.  Set *PN to the new block's size, and
 180    return the pointer to the new block.  *PN is never set to zero, and
 181    the returned pointer is never null.  */
 182
 183 void *
 184 x2realloc (void *p, size_t *pn)
 185 {
 186   return x2nrealloc_inline (p, pn, 1);
 187 }
 188
 189 /* Allocate S bytes of zeroed memory dynamically, with error checking.
 190    There's no need for xnzalloc (N, S), since it would be equivalent
 191    to xcalloc (N, S).  */
 192
 193 void *
 194 xzalloc (size_t s)
 195 {
 196   return memset (xmalloc (s), 0, s);
 197 }
 198
 199 /* Allocate zeroed memory for N elements of S bytes, with error
 200    checking.  S must be nonzero.  */
 201
 202 void *
 203 xcalloc (size_t n, size_t s)
 204 {
 205   void *p;
 206   /* Test for overflow, since some calloc implementations don't have
 207      proper overflow checks.  */
 208   if (xalloc_oversized (n, s) || (! (p = calloc (n, s)) && n != 0))
 209     xalloc_die ();
 210   return p;
 211 }
 212
 213 /* Clone an object P of size S, with error checking.  There's no need
 214    for xnclone (P, N, S), since xclone (P, N * S) works without any
 215    need for an arithmetic overflow check.  */
 216
 217 void *
 218 xclone (void const *p, size_t s)
 219 {
 220   return memcpy (xmalloc (s), p, s);
 221 }