1 /* PSPP - computes sample statistics.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
28 /* Fast, low-overhead memory block suballocator. */
31 struct pool *parent; /* Pool of which this pool is a subpool. */
32 struct pool_block *blocks; /* Blocks owned by the pool. */
33 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
39 struct pool_block *prev;
40 struct pool_block *next;
50 POOL_GIZMO_REGISTERED,
53 /* Pool routines can maintain objects (`gizmos') as well as doing
55 This structure is used to keep track of them. */
59 struct pool_gizmo *prev;
60 struct pool_gizmo *next;
62 long serial; /* Serial number. */
63 int type; /* Type of this gizmo. */
65 /* Type-dependent info. */
68 FILE *file; /* POOL_GIZMO_FILE. */
69 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
71 /* POOL_GIZMO_REGISTERED. */
74 void (*free) (void *p);
82 /* Rounds X up to the next multiple of Y. */
84 #define ROUND_UP(X, Y) \
85 (((X) + ((Y) - 1)) / (Y) * (Y))
88 /* Types that provide typically useful alignment sizes. */
97 /* This should be the alignment size used by malloc(). The size of
98 the union above is correct, if not optimal, in all known cases. */
99 #define ALIGN_SIZE sizeof (union align)
101 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
102 suballocation of blocks. This is useful under memory
103 debuggers like Checker or valgrind because it allows the
104 source location of bugs to be more accurately pinpointed.
106 On the other hand, if we're testing the library, then we want to
107 test the library's real functionality, not its crippled, slow,
108 simplified functionality. */
109 /*#define DISCRETE_BLOCKS 1*/
111 /* Size of each block allocated in the pool, in bytes.
112 Should be at least 1k. */
114 #define BLOCK_SIZE 1024
118 /* Sizes of some structures with alignment padding included. */
119 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
120 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
121 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
123 /* Serial number used to keep track of gizmos for mark/release. */
124 static long serial = 0;
127 static void add_gizmo (struct pool *, struct pool_gizmo *);
128 static void free_gizmo (struct pool_gizmo *);
129 static void free_all_gizmos (struct pool *pool);
130 static void delete_gizmo (struct pool *, struct pool_gizmo *);
131 static void check_gizmo (struct pool *, struct pool_gizmo *);
133 /* General routines. */
135 /* Creates and returns a new memory pool, which allows malloc()'d
136 blocks to be suballocated in a time- and space-efficient manner.
137 The entire contents of the memory pool are freed at once.
139 In addition, other objects can be associated with a memory pool.
140 These are released when the pool is destroyed. */
144 struct pool_block *block;
147 block = xmalloc (BLOCK_SIZE);
148 block->prev = block->next = block;
149 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
151 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
153 pool->blocks = block;
159 /* Creates a pool, allocates a block STRUCT_SIZE bytes in
160 length from it, stores the pool's address at offset
161 POOL_MEMBER_OFFSET within the block, and returns the allocated
164 Meant for use indirectly via pool_create_container(). */
166 pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
171 assert (struct_size >= sizeof pool);
172 assert (pool_member_offset <= struct_size - sizeof pool);
174 pool = pool_create ();
175 struct_ = pool_alloc (pool, struct_size);
176 *(struct pool **) (struct_ + pool_member_offset) = pool;
180 /* Destroy the specified pool, including all subpools. */
182 pool_destroy (struct pool *pool)
187 /* Remove this pool from its parent's list of gizmos. */
189 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
191 free_all_gizmos (pool);
193 /* Free all the memory. */
195 struct pool_block *cur, *next;
197 pool->blocks->prev->next = NULL;
198 for (cur = pool->blocks; cur; cur = next)
206 /* Release all the memory and gizmos in POOL.
207 Blocks are not given back with free() but kept for later
208 allocations. To give back memory, use a subpool instead. */
210 pool_clear (struct pool *pool)
212 free_all_gizmos (pool);
214 /* Zero out block sizes. */
216 struct pool_block *cur;
221 cur->ofs = POOL_BLOCK_SIZE;
222 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
224 cur->ofs += POOL_SIZE;
225 if (pool->parent != NULL)
226 cur->ofs += POOL_GIZMO_SIZE;
230 while (cur != pool->blocks);
234 /* Suballocation routines. */
236 /* Allocates a memory region AMT bytes in size from POOL and returns a
237 pointer to the region's start.
238 The region is properly aligned for storing any object. */
240 pool_alloc (struct pool *pool, size_t amt)
242 assert (pool != NULL);
247 #ifndef DISCRETE_BLOCKS
248 if (amt <= MAX_SUBALLOC)
250 /* If there is space in this block, take it. */
251 struct pool_block *b = pool->blocks;
252 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
253 if (b->ofs + amt <= BLOCK_SIZE)
255 void *const p = ((char *) b) + b->ofs;
260 /* No space in this block, so we must make other
262 if (b->next->ofs == 0)
264 /* The next block is empty. Use it. */
266 b->ofs = POOL_BLOCK_SIZE;
267 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
272 /* Create a new block at the start of the list. */
273 b = xmalloc (BLOCK_SIZE);
274 b->next = pool->blocks;
275 b->prev = pool->blocks->prev;
276 b->ofs = POOL_BLOCK_SIZE;
277 pool->blocks->prev->next = b;
278 pool->blocks->prev = b;
282 /* Allocate space from B. */
284 return ((char *) b) + b->ofs - amt;
288 return pool_malloc (pool, amt);
291 /* Allocates a memory region AMT bytes in size from POOL and
292 returns a pointer to the region's start. The region is not
293 necessarily aligned, so it is most suitable for storing
296 pool_alloc_unaligned (struct pool *pool, size_t amt)
298 assert (pool != NULL);
300 #ifndef DISCRETE_BLOCKS
301 /* Strings need not be aligned on any boundary, but some
302 operations may be more efficient when they are. However,
303 that's only going to help with reasonably long strings. */
304 if (amt < ALIGN_SIZE)
310 struct pool_block *const b = pool->blocks;
312 if (b->ofs + amt <= BLOCK_SIZE)
314 void *p = ((char *) b) + b->ofs;
322 return pool_alloc (pool, amt);
325 /* Allocates a memory region N * S bytes in size from POOL and
326 returns a pointer to the region's start.
327 N must be nonnegative, S must be positive.
328 Terminates the program if the memory cannot be obtained,
329 including the case where N * S overflows the range of size_t. */
331 pool_nalloc (struct pool *pool, size_t n, size_t s)
333 if (xalloc_oversized (n, s))
335 return pool_alloc (pool, n * s);
338 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
339 returns the new copy. */
341 pool_clone (struct pool *pool, const void *buffer, size_t size)
343 void *block = pool_alloc (pool, size);
344 memcpy (block, buffer, size);
348 /* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
349 into it, and returns the new copy. */
351 pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
353 void *block = pool_alloc_unaligned (pool, size);
354 memcpy (block, buffer, size);
358 /* Duplicates null-terminated STRING, within POOL, and returns a
359 pointer to the duplicate. For use only with strings, because
360 the returned pointere may not be aligned properly for other
363 pool_strdup (struct pool *pool, const char *string)
365 return pool_clone_unaligned (pool, string, strlen (string) + 1);
368 /* Standard allocation routines. */
370 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
371 returns a pointer to the beginning of the block.
372 If POOL is a null pointer, then allocates a normal memory block
375 pool_malloc (struct pool *pool, size_t amt)
381 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
382 g->type = POOL_GIZMO_MALLOC;
385 return ((char *) g) + POOL_GIZMO_SIZE;
391 return xmalloc (amt);
394 /* Allocates and returns N elements of S bytes each, to be
396 If POOL is a null pointer, then allocates a normal memory block
398 N must be nonnegative, S must be positive.
399 Terminates the program if the memory cannot be obtained,
400 including the case where N * S overflows the range of size_t. */
402 pool_nmalloc (struct pool *pool, size_t n, size_t s)
404 if (xalloc_oversized (n, s))
406 return pool_malloc (pool, n * s);
409 /* Changes the allocation size of the specified memory block P managed
410 by POOL to AMT bytes and returns a pointer to the beginning of the
412 If POOL is a null pointer, then the block is reallocated in the
413 usual way with realloc(). */
415 pool_realloc (struct pool *pool, void *p, size_t amt)
423 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
424 check_gizmo (pool, g);
426 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
433 check_gizmo (pool, g);
435 return ((char *) g) + POOL_GIZMO_SIZE;
444 return pool_malloc (pool, amt);
447 return xrealloc (p, amt);
450 /* Changes the allocation size of the specified memory block P
451 managed by POOL to N * S bytes and returns a pointer to the
452 beginning of the block.
453 N must be nonnegative, S must be positive.
454 If POOL is a null pointer, then the block is reallocated in
455 the usual way with xrealloc().
456 Terminates the program if the memory cannot be obtained,
457 including the case where N * S overflows the range of size_t. */
459 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
461 if (xalloc_oversized (n, s))
463 return pool_realloc (pool, p, n * s);
466 /* If P is null, allocate a block of at least *PN such objects;
467 otherwise, reallocate P so that it contains more than *PN
468 objects each of S bytes. *PN must be nonzero unless P is
469 null, and S must be nonzero. Set *PN to the new number of
470 objects, and return the pointer to the new block. *PN is
471 never set to zero, and the returned pointer is never null.
473 The block returned is managed by POOL. If POOL is a null
474 pointer, then the block is reallocated in the usual way with
477 Terminates the program if the memory cannot be obtained,
478 including the case where the memory required overflows the
481 Repeated reallocations are guaranteed to make progress, either by
482 allocating an initial block with a nonzero size, or by allocating a
485 In the following implementation, nonzero sizes are doubled so that
486 repeated reallocations have O(N log N) overall cost rather than
487 O(N**2) cost, but the specification for this function does not
488 guarantee that sizes are doubled.
490 Here is an example of use:
495 size_t allocated = 0;
498 append_int (int value)
500 if (used == allocated)
501 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
505 This causes x2nrealloc to allocate a block of some nonzero size the
506 first time it is called.
508 To have finer-grained control over the initial size, set *PN to a
509 nonzero value before calling this function with P == NULL. For
515 size_t allocated = 0;
516 size_t allocated1 = 1000;
519 append_int (int value)
521 if (used == allocated)
523 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
524 allocated = allocated1;
529 This function implementation is from gnulib. */
531 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
539 /* The approximate size to use for initial small allocation
540 requests, when the invoking code specifies an old size of
541 zero. 64 bytes is the largest "small" request for the
542 GNU C library malloc. */
543 enum { DEFAULT_MXFAST = 64 };
545 n = DEFAULT_MXFAST / s;
551 if (SIZE_MAX / 2 / s < n)
557 return pool_realloc (pool, p, n * s);
560 /* Frees block P managed by POOL.
561 If POOL is a null pointer, then the block is freed as usual with
564 pool_free (struct pool *pool, void *p)
566 if (pool != NULL && p != NULL)
568 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
569 check_gizmo (pool, g);
570 delete_gizmo (pool, g);
577 /* Gizmo allocations. */
579 /* Creates and returns a pool as a subpool of POOL.
580 The subpool will be destroyed automatically when POOL is destroyed.
581 It may also be destroyed explicitly in advance. */
583 pool_create_subpool (struct pool *pool)
585 struct pool *subpool;
586 struct pool_gizmo *g;
588 assert (pool != NULL);
589 subpool = pool_create ();
590 subpool->parent = pool;
592 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
593 subpool->blocks->ofs += POOL_GIZMO_SIZE;
595 g->type = POOL_GIZMO_SUBPOOL;
596 g->p.subpool = subpool;
603 /* Makes SUBPOOL a subpool of POOL.
604 SUBPOOL must not already have a parent pool.
605 The subpool will be destroyed automatically when POOL is destroyed.
606 It may also be destroyed explicitly in advance. */
608 pool_add_subpool (struct pool *pool, struct pool *subpool)
610 struct pool_gizmo *g;
612 assert (pool != NULL);
613 assert (subpool != NULL);
614 assert (subpool->parent == NULL);
616 g = pool_alloc (subpool, sizeof *g);
617 g->type = POOL_GIZMO_SUBPOOL;
618 g->p.subpool = subpool;
621 subpool->parent = pool;
624 /* Opens file FILENAME with mode MODE and returns a handle to it
625 if successful or a null pointer if not.
626 The file will be closed automatically when POOL is destroyed, or it
627 may be closed explicitly in advance using pool_fclose(), or
628 detached from the pool with pool_detach_file(). */
630 pool_fopen (struct pool *pool, const char *filename, const char *mode)
634 assert (pool && filename && mode);
635 f = fopen (filename, mode);
642 /* Closes file FILE managed by POOL.
643 Returns 0 if successful, EOF if an I/O error occurred. */
645 pool_fclose (struct pool *pool, FILE *file)
647 assert (pool && file);
648 pool_detach_file (pool, file);
649 return fclose (file);
652 /* Creates a temporary file with tmpfile() and returns a handle to it
653 if successful or a null pointer if not.
654 The file will be closed automatically when POOL is destroyed, or it
655 may be closed explicitly in advance using pool_fclose(), or
656 detached from the pool with pool_detach_file(). */
658 pool_tmpfile (struct pool *pool)
660 FILE *file = tmpfile ();
662 pool_attach_file (pool, file);
666 /* Attaches FILE to POOL.
667 The file will be closed automatically when POOL is destroyed, or it
668 may be closed explicitly in advance using pool_fclose(), or
669 detached from the pool with pool_detach_file(). */
671 pool_attach_file (struct pool *pool, FILE *file)
673 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
674 g->type = POOL_GIZMO_FILE;
679 /* Detaches FILE from POOL. */
681 pool_detach_file (struct pool *pool, FILE *file)
683 struct pool_gizmo *g;
685 for (g = pool->gizmos; g; g = g->next)
686 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
688 delete_gizmo (pool, g);
693 /* Registers FREE to be called with argument P.
694 P should be unique among those registered in POOL so that it can be
695 uniquely identified by pool_unregister().
696 If not unregistered, FREE will be called with argument P when POOL
699 pool_register (struct pool *pool, void (*free) (void *), void *p)
701 assert (pool && free && p);
704 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
705 g->type = POOL_GIZMO_REGISTERED;
706 g->p.registered.free = free;
707 g->p.registered.p = p;
712 /* Unregisters previously registered P from POOL.
713 Returns nonzero only if P was found to be registered in POOL. */
715 pool_unregister (struct pool *pool, void *p)
720 struct pool_gizmo *g;
722 for (g = pool->gizmos; g; g = g->next)
723 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
725 delete_gizmo (pool, g);
733 /* Partial freeing. */
735 /* Notes the state of POOL into MARK so that it may be restored
736 by a call to pool_release(). */
738 pool_mark (struct pool *pool, struct pool_mark *mark)
740 assert (pool && mark);
742 mark->block = pool->blocks;
743 mark->ofs = pool->blocks->ofs;
745 mark->serial = serial;
748 /* Restores to POOL the state recorded in MARK.
749 Emptied blocks are not given back with free() but kept for
750 later allocations. To get that behavior, use a subpool
753 pool_release (struct pool *pool, const struct pool_mark *mark)
755 assert (pool && mark);
758 struct pool_gizmo *cur, *next;
760 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
776 struct pool_block *cur;
778 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
780 cur->ofs = POOL_BLOCK_SIZE;
781 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
783 cur->ofs += POOL_SIZE;
784 if (pool->parent != NULL)
785 cur->ofs += POOL_GIZMO_SIZE;
788 pool->blocks = mark->block;
789 pool->blocks->ofs = mark->ofs;
793 /* Private functions. */
795 /* Adds GIZMO at the beginning of POOL's gizmo list. */
797 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
799 assert (pool && gizmo);
802 gizmo->next = pool->gizmos;
805 pool->gizmos->prev = gizmo;
806 pool->gizmos = gizmo;
808 gizmo->serial = serial++;
810 check_gizmo (pool, gizmo);
813 /* Removes GIZMO from POOL's gizmo list. */
815 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
817 assert (pool && gizmo);
819 check_gizmo (pool, gizmo);
822 gizmo->prev->next = gizmo->next;
824 pool->gizmos = gizmo->next;
826 gizmo->next->prev = gizmo->prev;
829 /* Frees any of GIZMO's internal state.
830 GIZMO's data must not be referenced after calling this function. */
832 free_gizmo (struct pool_gizmo *gizmo)
834 assert (gizmo != NULL);
838 case POOL_GIZMO_MALLOC:
841 case POOL_GIZMO_FILE:
842 fclose (gizmo->p.file); /* Ignore errors. */
844 case POOL_GIZMO_SUBPOOL:
845 gizmo->p.subpool->parent = NULL;
846 pool_destroy (gizmo->p.subpool);
848 case POOL_GIZMO_REGISTERED:
849 gizmo->p.registered.free (gizmo->p.registered.p);
856 /* Free all the gizmos in POOL. */
858 free_all_gizmos (struct pool *pool)
860 struct pool_gizmo *cur, *next;
862 for (cur = pool->gizmos; cur; cur = next)
871 check_gizmo (struct pool *p, struct pool_gizmo *g)
873 assert (g->pool == p);
874 assert (g->next == NULL || g->next->prev == g);
875 assert ((g->prev != NULL && g->prev->next == g)
876 || (g->prev == NULL && p->gizmos == g));