Parameter estimate matched with appropriate variable during estimation
[pspp] / src / pool.c
index 336671e2bcd6b84c868f380e95608dbc76ad47b8..0f6b11e05caa7c3a090660cbddb86a6ed5161bec 100644 (file)
 
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
-   02111-1307, USA. */
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA. */
 
-#if HAVE_CONFIG_H
 #include <config.h>
-#endif
 #include "pool.h"
-#include <assert.h>
 #include <stdlib.h>
 #include "alloc.h"
+#include "command.h"
+#include "error.h"
+#include "size_max.h"
 #include "str.h"
 
 /* Fast, low-overhead memory block suballocator. */
@@ -56,6 +56,7 @@ enum
    This structure is used to keep track of them. */
 struct pool_gizmo
   {
+    struct pool *pool;
     struct pool_gizmo *prev;
     struct pool_gizmo *next;
 
@@ -112,10 +113,6 @@ union align
    simplified functionality. */
 /*#define DISCRETE_BLOCKS 1*/
 
-/* Enable debug code if appropriate. */
-#if SELF_TEST
-#endif
-
 /* Size of each block allocated in the pool, in bytes.
    Should be at least 1k. */
 #ifndef BLOCK_SIZE
@@ -142,11 +139,7 @@ static void add_gizmo (struct pool *, struct pool_gizmo *);
 static void free_gizmo (struct pool_gizmo *);
 static void free_all_gizmos (struct pool *pool);
 static void delete_gizmo (struct pool *, struct pool_gizmo *);
-
-#if !PSPP
-static void *xmalloc (size_t);
-static void *xrealloc (void *, size_t);
-#endif
+static void check_gizmo (struct pool *, struct pool_gizmo *);
 \f
 /* General routines. */
 
@@ -183,9 +176,8 @@ pool_destroy (struct pool *pool)
 
   /* Remove this pool from its parent's list of gizmos. */
   if (pool->parent) 
-    delete_gizmo (pool->parent,
-                 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
-
+    delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
+  
   free_all_gizmos (pool);
 
   /* Free all the memory. */
@@ -217,8 +209,12 @@ pool_clear (struct pool *pool)
     do
       {
         cur->ofs = POOL_BLOCK_SIZE;
-        if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
-          cur->ofs += POOL_SIZE;
+        if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) 
+          {
+            cur->ofs += POOL_SIZE;
+            if (pool->parent != NULL)
+              cur->ofs += POOL_GIZMO_SIZE; 
+          }
         cur = cur->next;
       }
     while (cur != pool->blocks);
@@ -278,6 +274,29 @@ pool_alloc (struct pool *pool, size_t amt)
     return pool_malloc (pool, amt);
 }
 
+/* Allocates a memory region N * S bytes in size from POOL and
+   returns a pointer to the region's start.
+   N must be nonnegative, S must be positive.
+   Terminates the program if the memory cannot be obtained,
+   including the case where N * S overflows the range of size_t. */
+void *
+pool_nalloc (struct pool *pool, size_t n, size_t s) 
+{
+  if (xalloc_oversized (n, s))
+    xalloc_die ();
+  return pool_alloc (pool, n * s);
+}
+
+/* Allocates SIZE bytes in POOL, copies BUFFER into it, and
+   returns the new copy. */
+void *
+pool_clone (struct pool *pool, const void *buffer, size_t size)
+{
+  void *block = pool_alloc (pool, size);
+  memcpy (block, buffer, size);
+  return block;
+}
+
 /* Duplicates STRING, which has LENGTH characters, within POOL,
    and returns a pointer to the duplicate.  LENGTH should not
    include the null terminator, which is always added to the
@@ -302,6 +321,8 @@ pool_strndup (struct pool *pool, const char *string, size_t length)
         copy = ((char *) b) + b->ofs;
         b->ofs += size;
       }
+    else
+      copy = pool_alloc (pool, size);
   }
 #else
   copy = pool_alloc (pool, size);
@@ -327,7 +348,7 @@ pool_strdup (struct pool *pool, const char *string)
 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
    returns a pointer to the beginning of the block.
    If POOL is a null pointer, then allocates a normal memory block
-   with malloc().  */
+   with xmalloc().  */
 void *
 pool_malloc (struct pool *pool, size_t amt)
 {
@@ -348,6 +369,21 @@ pool_malloc (struct pool *pool, size_t amt)
     return xmalloc (amt);
 }
 
+/* Allocates and returns N elements of S bytes each, to be
+   managed by POOL.
+   If POOL is a null pointer, then allocates a normal memory block
+   with malloc().
+   N must be nonnegative, S must be positive.
+   Terminates the program if the memory cannot be obtained,
+   including the case where N * S overflows the range of size_t. */
+void *
+pool_nmalloc (struct pool *pool, size_t n, size_t s) 
+{
+  if (xalloc_oversized (n, s))
+    xalloc_die ();
+  return pool_malloc (pool, n * s);
+}
+
 /* Changes the allocation size of the specified memory block P managed
    by POOL to AMT bytes and returns a pointer to the beginning of the
    block.
@@ -362,16 +398,17 @@ pool_realloc (struct pool *pool, void *p, size_t amt)
        {
          if (amt != 0)
            {
-             struct pool_gizmo *g;
+             struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
+              check_gizmo (pool, g);
 
-             g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
-                           amt + POOL_GIZMO_SIZE);
+             g = xrealloc (g, amt + POOL_GIZMO_SIZE);
              if (g->next)
                g->next->prev = g;
              if (g->prev)
                g->prev->next = g;
              else
                pool->gizmos = g;
+              check_gizmo (pool, g);
 
              return ((char *) g) + POOL_GIZMO_SIZE;
            }
@@ -388,6 +425,116 @@ pool_realloc (struct pool *pool, void *p, size_t amt)
     return xrealloc (p, amt);
 }
 
+/* Changes the allocation size of the specified memory block P
+   managed by POOL to N * S bytes and returns a pointer to the
+   beginning of the block.
+   N must be nonnegative, S must be positive.
+   If POOL is a null pointer, then the block is reallocated in
+   the usual way with xrealloc().
+   Terminates the program if the memory cannot be obtained,
+   including the case where N * S overflows the range of size_t. */
+void *
+pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
+{
+  if (xalloc_oversized (n, s))
+    xalloc_die ();
+  return pool_realloc (pool, p, n * s);
+}
+
+/* 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.  *PN must be nonzero unless P is
+   null, and 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.
+
+   The block returned is managed by POOL.  If POOL is a null
+   pointer, then the block is reallocated in the usual way with
+   x2nrealloc().
+
+   Terminates the program if the memory cannot be obtained,
+   including the case where the memory required overflows the
+   range of size_t.
+
+   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 doubled so that
+   repeated reallocations have O(N log N) overall cost rather than
+   O(N**2) cost, but the specification for this function does not
+   guarantee that sizes are doubled.
+
+   Here is an example of use:
+
+     int *p = NULL;
+     struct pool *pool;
+     size_t used = 0;
+     size_t allocated = 0;
+
+     void
+     append_int (int value)
+       {
+        if (used == allocated)
+          p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
+        p[used++] = 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 == NULL.  For
+   example:
+
+     int *p = NULL;
+     struct pool *pool;
+     size_t used = 0;
+     size_t allocated = 0;
+     size_t allocated1 = 1000;
+
+     void
+     append_int (int value)
+       {
+        if (used == allocated)
+          {
+            p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
+            allocated = allocated1;
+          }
+        p[used++] = value;
+       }
+
+   This function implementation is from gnulib. */
+void *
+pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
+{
+  size_t n = *pn;
+
+  if (p == NULL)
+    {
+      if (n == 0)
+       {
+         /* The approximate size to use for initial small allocation
+            requests, when the invoking code specifies an old size of
+            zero.  64 bytes is the largest "small" request for the
+            GNU C library malloc.  */
+         enum { DEFAULT_MXFAST = 64 };
+
+         n = DEFAULT_MXFAST / s;
+         n += !n;
+       }
+    }
+  else
+    {
+      if (SIZE_MAX / 2 / s < n)
+       xalloc_die ();
+      n *= 2;
+    }
+
+  *pn = n;
+  return pool_realloc (pool, p, n * s);
+}
+
 /* Frees block P managed by POOL.
    If POOL is a null pointer, then the block is freed as usual with
    free(). */
@@ -397,6 +544,7 @@ pool_free (struct pool *pool, void *p)
   if (pool != NULL && p != NULL)
     {
       struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
+      check_gizmo (pool, g);
       delete_gizmo (pool, g);
       free (g);
     }
@@ -419,7 +567,7 @@ pool_create_subpool (struct pool *pool)
   subpool = pool_create ();
   subpool->parent = pool;
 
-  g = (void *) (((char *) subpool) + subpool->blocks->ofs);
+  g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
   subpool->blocks->ofs += POOL_GIZMO_SIZE;
   
   g->type = POOL_GIZMO_SUBPOOL;
@@ -564,8 +712,12 @@ pool_release (struct pool *pool, const struct pool_mark *mark)
     for (cur = pool->blocks; cur != mark->block; cur = cur->next) 
       {
         cur->ofs = POOL_BLOCK_SIZE;
-        if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
-          cur->ofs += POOL_SIZE; 
+        if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) 
+          {
+            cur->ofs += POOL_SIZE;
+            if (pool->parent != NULL)
+              cur->ofs += POOL_GIZMO_SIZE; 
+          }
       }
     pool->blocks = mark->block;
     pool->blocks->ofs = mark->ofs;
@@ -579,7 +731,8 @@ static void
 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 {
   assert (pool && gizmo);
-  
+
+  gizmo->pool = pool;
   gizmo->next = pool->gizmos;
   gizmo->prev = NULL;
   if (pool->gizmos)
@@ -587,6 +740,8 @@ add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
   pool->gizmos = gizmo;
 
   gizmo->serial = serial++;
+
+  check_gizmo (pool, gizmo);
 }
  
 /* Removes GIZMO from POOL's gizmo list. */
@@ -594,7 +749,9 @@ static void
 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 {
   assert (pool && gizmo);
-  
+
+  check_gizmo (pool, gizmo);
+
   if (gizmo->prev)
     gizmo->prev->next = gizmo->next;
   else
@@ -609,7 +766,7 @@ static void
 free_gizmo (struct pool_gizmo *gizmo)
 {
   assert (gizmo != NULL);
-  
+
   switch (gizmo->type)
     {
     case POOL_GIZMO_MALLOC:
@@ -641,48 +798,21 @@ free_all_gizmos (struct pool *pool)
       next = cur->next;
       free_gizmo (cur);
     }
+  pool->gizmos = NULL;
 }
-\f
-/* Memory allocation. */
 
-#if !PSPP
-/* Allocates SIZE bytes of space using malloc().  Aborts if out of
-   memory. */
-static void *
-xmalloc (size_t size)
+static void
+check_gizmo (struct pool *p, struct pool_gizmo *g) 
 {
-  void *vp;
-  if (size == 0)
-    return NULL;
-  vp = malloc (size);
-  assert (vp != NULL);
-  if (vp == NULL)
-    abort ();
-  return vp;
-}
+  assert (g->pool == p);
+  assert (g->next == NULL || g->next->prev == g);
+  assert ((g->prev != NULL && g->prev->next == g)
+          || (g->prev == NULL && p->gizmos == g));
 
-/* Reallocates P to be SIZE bytes long using realloc().  Aborts if out
-   of memory. */
-static void *
-xrealloc (void *p, size_t size)
-{
-  if (p == NULL)
-    return xmalloc (size);
-  if (size == 0)
-    {
-      free (p);
-      return NULL;
-    }
-  p = realloc (p, size);
-  if (p == NULL)
-    abort ();
-  return p;
 }
-#endif /* !PSPP */
 \f
 /* Self-test routine. */
 
-#if SELF_TEST
 #include <errno.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -695,14 +825,9 @@ xrealloc (void *p, size_t size)
 /* Self-test routine.
    This is not exhaustive, but it can be useful. */
 int
-main (int argc, char **argv)
+cmd_debug_pool (void)
 {
-  int seed;
-  
-  if (argc == 2)
-    seed = atoi (argv[1]);
-  else
-    seed = time (0) * 257 % 32768;
+  int seed = time (0) * 257 % 32768;
 
   for (;;)
     {
@@ -781,12 +906,7 @@ main (int argc, char **argv)
 
       putchar ('\n');
     }
-}
 
-#endif /* SELF_TEST */
+  return CMD_SUCCESS;
+}
 
-/* 
-   Local variables:
-   compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"
-   End:
-*/