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 <assert.h>
+#include "pool.h"
#include <stdlib.h>
#include "alloc.h"
-#include "pool.h"
+#include "command.h"
+#include "error.h"
+#include "size_max.h"
+#include "str.h"
/* Fast, low-overhead memory block suballocator. */
struct pool
This structure is used to keep track of them. */
struct pool_gizmo
{
+ struct pool *pool;
struct pool_gizmo *prev;
struct pool_gizmo *next;
/* This should be the alignment size used by malloc(). The size of
the union above is correct, if not optimal, in all known cases. */
-#if defined (i386) || defined (__i386__)
-#define ALIGN_SIZE 4 /* Save some extra memory. */
-#else
#define ALIGN_SIZE sizeof (union align)
-#endif
-/* DISCRETE_BLOCKS may be declared as nonzero to prevent suballocation
- of blocks. This is useful under memory debuggers like Checker
- because it allows the source location of bugs to be more accurately
- pinpointed.
+/* DISCRETE_BLOCKS may be declared as nonzero to prevent
+ suballocation of blocks. This is useful under memory
+ debuggers like Checker or valgrind because it allows the
+ source location of bugs to be more accurately pinpointed.
On the other hand, if we're testing the library, then we want to
test the library's real functionality, not its crippled, slow,
simplified functionality. */
-#if __CHECKER__ && !SELF_TEST
-#define DISCRETE_BLOCKS 1
-#endif
-
-/* Enable debug code if appropriate. */
-#undef DEBUGGING
-#if SELF_TEST
-#define DEBUGGING 1
-#endif
+/*#define DISCRETE_BLOCKS 1*/
/* Size of each block allocated in the pool, in bytes.
Should be at least 1k. */
/* Prototypes. */
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. */
return pool;
}
+/* Creates a pool, allocates a block STRUCT_SIZE bytes in
+ length from it, stores the pool's address at offset
+ POOL_MEMBER_OFFSET within the block, and returns the allocated
+ block.
+
+ Meant for use indirectly via pool_create_container(). */
+void *
+pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
+{
+ struct pool *pool;
+ char *struct_;
+
+ assert (struct_size >= sizeof pool);
+ assert (pool_member_offset <= struct_size - sizeof pool);
+
+ pool = pool_create ();
+ struct_ = pool_alloc (pool, struct_size);
+ *(struct pool **) (struct_ + pool_member_offset) = pool;
+ return struct_;
+}
+
/* Destroy the specified pool, including all subpools. */
void
pool_destroy (struct pool *pool)
if (pool == NULL)
return;
+ /* Remove this pool from its parent's list of gizmos. */
if (pool->parent)
- delete_gizmo (pool,
- (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
-
- {
- struct pool_gizmo *cur, *next;
-
- for (cur = pool->gizmos; cur; cur = next)
- {
- next = cur->next;
- free_gizmo (cur);
- }
- }
+ delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
+ free_all_gizmos (pool);
+
+ /* Free all the memory. */
{
struct pool_block *cur, *next;
}
}
}
+
+/* Release all the memory and gizmos in POOL.
+ Blocks are not given back with free() but kept for later
+ allocations. To give back memory, use a subpool instead. */
+void
+pool_clear (struct pool *pool)
+{
+ free_all_gizmos (pool);
+
+ /* Zero out block sizes. */
+ {
+ struct pool_block *cur;
+
+ cur = pool->blocks;
+ do
+ {
+ cur->ofs = POOL_BLOCK_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);
+ }
+}
\f
/* Suballocation routines. */
/* Allocates a memory region AMT bytes in size from POOL and returns a
- pointer to the region's start. */
+ pointer to the region's start.
+ The region is properly aligned for storing any object. */
void *
pool_alloc (struct pool *pool, size_t amt)
{
assert (pool != NULL);
+
+ if (amt == 0)
+ return NULL;
-#if !DISCRETE_BLOCKS /* Help identify source of bugs for Checker users. */
+#ifndef DISCRETE_BLOCKS
if (amt <= MAX_SUBALLOC)
{
+ /* If there is space in this block, take it. */
struct pool_block *b = pool->blocks;
b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
if (b->ofs + amt <= BLOCK_SIZE)
return p;
}
- b = xmalloc (BLOCK_SIZE);
- b->next = pool->blocks;
- b->prev = pool->blocks->prev;
- b->ofs = POOL_BLOCK_SIZE + amt;
-
- pool->blocks->prev->next = b;
- pool->blocks = pool->blocks->prev = b;
-
- return ((char *) b) + POOL_BLOCK_SIZE;
+ /* No space in this block, so we must make other
+ arrangements. */
+ if (b->next->ofs == 0)
+ {
+ /* The next block is empty. Use it. */
+ b = b->next;
+ b->ofs = POOL_BLOCK_SIZE;
+ if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
+ b->ofs += POOL_SIZE;
+ }
+ else
+ {
+ /* Create a new block at the start of the list. */
+ b = xmalloc (BLOCK_SIZE);
+ b->next = pool->blocks;
+ b->prev = pool->blocks->prev;
+ b->ofs = POOL_BLOCK_SIZE;
+ pool->blocks->prev->next = b;
+ pool->blocks->prev = b;
+ }
+ pool->blocks = b;
+
+ /* Allocate space from B. */
+ b->ofs += amt;
+ return ((char *) b) + b->ofs - amt;
}
else
-#endif /* !DISCRETE_BLOCKS */
+#endif
return pool_malloc (pool, amt);
}
-/* Duplicates STRING within POOL and returns a pointer to the
- duplicate. */
-char *
-pool_strdup (struct pool *pool, const char *string)
+/* Allocates a memory region AMT bytes in size from POOL and
+ returns a pointer to the region's start. The region is not
+ necessarily aligned, so it is most suitable for storing
+ strings. */
+void *
+pool_alloc_unaligned (struct pool *pool, size_t amt)
{
- size_t amt;
- void *p;
+ assert (pool != NULL);
- assert (pool && string);
- amt = strlen (string) + 1;
+#ifndef DISCRETE_BLOCKS
+ /* Strings need not be aligned on any boundary, but some
+ operations may be more efficient when they are. However,
+ that's only going to help with reasonably long strings. */
+ if (amt < ALIGN_SIZE)
+ {
+ if (amt == 0)
+ return NULL;
+ else
+ {
+ struct pool_block *const b = pool->blocks;
+
+ if (b->ofs + amt <= BLOCK_SIZE)
+ {
+ void *p = ((char *) b) + b->ofs;
+ b->ofs += amt;
+ return p;
+ }
+ }
+ }
+#endif
- /* Note that strings need not be aligned on any boundary. */
- {
-#if !DISCRETE_BLOCKS
- struct pool_block *const b = pool->blocks;
+ return pool_alloc (pool, amt);
+}
- if (b->ofs + amt <= BLOCK_SIZE)
- {
- p = ((char *) b) + b->ofs;
- b->ofs += amt;
- }
- else
-#endif
- p = pool_alloc (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);
+}
- memcpy (p, string, amt);
- return p;
+/* 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;
+}
+
+/* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
+ into it, and returns the new copy. */
+void *
+pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
+{
+ void *block = pool_alloc_unaligned (pool, size);
+ memcpy (block, buffer, size);
+ return block;
+}
+
+/* Duplicates null-terminated STRING, within POOL, and returns a
+ pointer to the duplicate. For use only with strings, because
+ the returned pointere may not be aligned properly for other
+ types. */
+char *
+pool_strdup (struct pool *pool, const char *string)
+{
+ return pool_clone_unaligned (pool, string, strlen (string) + 1);
}
\f
/* Standard allocation routines. */
/* 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)
{
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.
{
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;
}
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(). */
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);
}
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;
return subpool;
}
+/* Makes SUBPOOL a subpool of POOL.
+ SUBPOOL must not already have a parent pool.
+ The subpool will be destroyed automatically when POOL is destroyed.
+ It may also be destroyed explicitly in advance. */
+void
+pool_add_subpool (struct pool *pool, struct pool *subpool)
+{
+ struct pool_gizmo *g;
+
+ assert (pool != NULL);
+ assert (subpool != NULL);
+ assert (subpool->parent == NULL);
+
+ g = pool_alloc (subpool, sizeof *g);
+ g->type = POOL_GIZMO_SUBPOOL;
+ g->p.subpool = subpool;
+ add_gizmo (pool, g);
+
+ subpool->parent = pool;
+}
+
/* Opens file FILENAME with mode MODE and returns a handle to it
if successful or a null pointer if not.
The file will be closed automatically when POOL is destroyed, or it
mark->serial = serial;
}
-/* Restores to POOL the state recorded in MARK. */
+/* Restores to POOL the state recorded in MARK.
+ Emptied blocks are not given back with free() but kept for
+ later allocations. To get that behavior, use a subpool
+ instead. */
void
pool_release (struct pool *pool, const struct pool_mark *mark)
{
}
{
- struct pool_block *cur, *next, *last;
+ struct pool_block *cur;
- last = pool->blocks->prev;
- for (cur = pool->blocks; cur != mark->block; cur = next)
+ for (cur = pool->blocks; cur != mark->block; cur = cur->next)
{
- next = cur->next;
- assert (next != cur);
-
- free (cur);
+ cur->ofs = POOL_BLOCK_SIZE;
+ if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
+ {
+ cur->ofs += POOL_SIZE;
+ if (pool->parent != NULL)
+ cur->ofs += POOL_GIZMO_SIZE;
+ }
}
-
- cur->prev = last;
- last->next = pool->blocks = cur;
-
- cur->ofs = mark->ofs;
+ pool->blocks = mark->block;
+ pool->blocks->ofs = mark->ofs;
}
}
\f
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)
pool->gizmos = gizmo;
gizmo->serial = serial++;
+
+ check_gizmo (pool, gizmo);
}
/* Removes GIZMO from POOL's gizmo list. */
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
free_gizmo (struct pool_gizmo *gizmo)
{
assert (gizmo != NULL);
-
+
switch (gizmo->type)
{
case POOL_GIZMO_MALLOC:
assert (0);
}
}
-\f
-/* Memory allocation. */
-#if !PSPP
-/* Allocates SIZE bytes of space using malloc(). Aborts if out of
- memory. */
-static void *
-xmalloc (size_t size)
+/* Free all the gizmos in POOL. */
+static void
+free_all_gizmos (struct pool *pool)
{
- void *vp;
- if (size == 0)
- return NULL;
- vp = malloc (size);
- assert (vp != NULL);
- if (vp == NULL)
- abort ();
- return vp;
-}
+ struct pool_gizmo *cur, *next;
-/* 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)
+ for (cur = pool->gizmos; cur; cur = next)
{
- free (p);
- return NULL;
+ next = cur->next;
+ free_gizmo (cur);
}
- p = realloc (p, size);
- if (p == NULL)
- abort ();
- return p;
+ pool->gizmos = NULL;
+}
+
+static void
+check_gizmo (struct pool *p, struct pool_gizmo *g)
+{
+ 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));
+
}
-#endif /* !PSPP */
\f
/* Self-test routine. */
-#if SELF_TEST
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
/* 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 (;;)
{
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:
-*/
projects / pspp-builds.git / blobdiff