1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 #include <libpspp/assertion.h>
27 /* Fast, low-overhead memory block suballocator. */
30 struct pool *parent; /* Pool of which this pool is a subpool. */
31 struct pool_block *blocks; /* Blocks owned by the pool. */
32 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
38 struct pool_block *prev;
39 struct pool_block *next;
49 POOL_GIZMO_REGISTERED,
52 /* Pool routines can maintain objects (`gizmos') as well as doing
54 This structure is used to keep track of them. */
58 struct pool_gizmo *prev;
59 struct pool_gizmo *next;
61 long serial; /* Serial number. */
62 int type; /* Type of this gizmo. */
64 /* Type-dependent info. */
67 FILE *file; /* POOL_GIZMO_FILE. */
68 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
70 /* POOL_GIZMO_REGISTERED. */
73 void (*free) (void *p);
81 /* Rounds X up to the next multiple of Y. */
83 #define ROUND_UP(X, Y) \
84 (((X) + ((Y) - 1)) / (Y) * (Y))
87 /* Types that provide typically useful alignment sizes. */
96 /* This should be the alignment size used by malloc(). The size of
97 the union above is correct, if not optimal, in all known cases. */
98 #define ALIGN_SIZE sizeof (union align)
100 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
101 suballocation of blocks. This is useful under memory
102 debuggers like valgrind because it allows the source location
103 of bugs to be more accurately pinpointed.
105 On the other hand, if we're testing the library, then we want to
106 test the library's real functionality, not its crippled, slow,
107 simplified functionality. */
108 /*#define DISCRETE_BLOCKS 1*/
110 /* Size of each block allocated in the pool, in bytes.
111 Should be at least 1k. */
113 #define BLOCK_SIZE 1024
117 /* Sizes of some structures with alignment padding included. */
118 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
119 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
120 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
122 /* Serial number used to keep track of gizmos for mark/release. */
123 static long serial = 0;
126 static void add_gizmo (struct pool *, struct pool_gizmo *);
127 static void free_gizmo (struct pool_gizmo *);
128 static void free_all_gizmos (struct pool *pool);
129 static void delete_gizmo (struct pool *, struct pool_gizmo *);
130 static void check_gizmo (struct pool *, struct pool_gizmo *);
132 /* General routines. */
134 /* Creates and returns a new memory pool, which allows malloc()'d
135 blocks to be suballocated in a time- and space-efficient manner.
136 The entire contents of the memory pool are freed at once.
138 In addition, other objects can be associated with a memory pool.
139 These are released when the pool is destroyed. */
143 struct pool_block *block;
146 block = xmalloc (BLOCK_SIZE);
147 block->prev = block->next = block;
148 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
150 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
152 pool->blocks = block;
158 /* Creates a pool, allocates a block STRUCT_SIZE bytes in
159 length from it, stores the pool's address at offset
160 POOL_MEMBER_OFFSET within the block, and returns the allocated
163 Meant for use indirectly via pool_create_container(). */
165 pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
170 assert (struct_size >= sizeof pool);
171 assert (pool_member_offset <= struct_size - sizeof pool);
173 pool = pool_create ();
174 struct_ = pool_alloc (pool, struct_size);
175 *(struct pool **) (struct_ + pool_member_offset) = pool;
179 /* Destroy the specified pool, including all subpools. */
181 pool_destroy (struct pool *pool)
186 /* Remove this pool from its parent's list of gizmos. */
188 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
190 free_all_gizmos (pool);
192 /* Free all the memory. */
194 struct pool_block *cur, *next;
196 pool->blocks->prev->next = NULL;
197 for (cur = pool->blocks; cur; cur = next)
205 /* Release all the memory and gizmos in POOL.
206 Blocks are not given back with free() but kept for later
207 allocations. To give back memory, use a subpool instead. */
209 pool_clear (struct pool *pool)
211 free_all_gizmos (pool);
213 /* Zero out block sizes. */
215 struct pool_block *cur;
220 cur->ofs = POOL_BLOCK_SIZE;
221 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
223 cur->ofs += POOL_SIZE;
224 if (pool->parent != NULL)
225 cur->ofs += POOL_GIZMO_SIZE;
229 while (cur != pool->blocks);
233 /* Suballocation routines. */
235 /* Allocates a memory region AMT bytes in size from POOL and returns a
236 pointer to the region's start.
237 The region is properly aligned for storing any object. */
239 pool_alloc (struct pool *pool, size_t amt)
241 assert (pool != NULL);
246 #ifndef DISCRETE_BLOCKS
247 if (amt <= MAX_SUBALLOC)
249 /* If there is space in this block, take it. */
250 struct pool_block *b = pool->blocks;
251 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
252 if (b->ofs + amt <= BLOCK_SIZE)
254 void *const p = ((char *) b) + b->ofs;
259 /* No space in this block, so we must make other
261 if (b->next->ofs == 0)
263 /* The next block is empty. Use it. */
265 b->ofs = POOL_BLOCK_SIZE;
266 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
271 /* Create a new block at the start of the list. */
272 b = xmalloc (BLOCK_SIZE);
273 b->next = pool->blocks;
274 b->prev = pool->blocks->prev;
275 b->ofs = POOL_BLOCK_SIZE;
276 pool->blocks->prev->next = b;
277 pool->blocks->prev = b;
281 /* Allocate space from B. */
283 return ((char *) b) + b->ofs - amt;
287 return pool_malloc (pool, amt);
290 /* Allocates a memory region AMT bytes in size from POOL and
291 returns a pointer to the region's start. The region is not
292 necessarily aligned, so it is most suitable for storing
295 pool_alloc_unaligned (struct pool *pool, size_t amt)
297 assert (pool != NULL);
299 #ifndef DISCRETE_BLOCKS
300 /* Strings need not be aligned on any boundary, but some
301 operations may be more efficient when they are. However,
302 that's only going to help with reasonably long strings. */
303 if (amt < ALIGN_SIZE)
309 struct pool_block *const b = pool->blocks;
311 if (b->ofs + amt <= BLOCK_SIZE)
313 void *p = ((char *) b) + b->ofs;
321 return pool_alloc (pool, amt);
324 /* Allocates a memory region N * S bytes in size from POOL and
325 returns a pointer to the region's start.
326 N must be nonnegative, S must be positive.
327 Terminates the program if the memory cannot be obtained,
328 including the case where N * S overflows the range of size_t. */
330 pool_nalloc (struct pool *pool, size_t n, size_t s)
332 if (xalloc_oversized (n, s))
334 return pool_alloc (pool, n * s);
337 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
338 returns the new copy. */
340 pool_clone (struct pool *pool, const void *buffer, size_t size)
342 void *block = pool_alloc (pool, size);
343 memcpy (block, buffer, size);
347 /* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
348 into it, and returns the new copy. */
350 pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
352 void *block = pool_alloc_unaligned (pool, size);
353 memcpy (block, buffer, size);
357 /* Duplicates null-terminated STRING, within POOL, and returns a
358 pointer to the duplicate. For use only with strings, because
359 the returned pointere may not be aligned properly for other
362 pool_strdup (struct pool *pool, const char *string)
364 return pool_clone_unaligned (pool, string, strlen (string) + 1);
367 /* Duplicates the SIZE bytes of STRING, plus a trailing 0 byte,
368 and returns a pointer to the duplicate. For use only with
369 strings, because the returned pointere may not be aligned
370 properly for other types. */
372 pool_strdup0 (struct pool *pool, const char *string, size_t size)
374 char *new_string = pool_alloc_unaligned (pool, size + 1);
375 memcpy (new_string, string, size);
376 new_string[size] = '\0';
380 /* Formats FORMAT with the given ARGS in memory allocated from
381 POOL and returns the formatted string. */
383 pool_vasprintf (struct pool *pool, const char *format, va_list args_)
385 struct pool_block *b;
390 va_copy (args, args_);
392 avail = BLOCK_SIZE - b->ofs;
393 s = ((char *) b) + b->ofs;
394 needed = vsnprintf (s, avail, format, args);
401 /* Success. Reserve the space that was actually used. */
402 b->ofs += needed + 1;
406 /* Failure, but now we know how much space is needed.
407 Allocate that much and reformat. */
408 s = pool_alloc (pool, needed + 1);
410 va_copy (args, args_);
411 vsprintf (s, format, args);
417 /* Some old libc's returned -1 when the destination string
418 was too short. This should be uncommon these days and
419 it's a rare case anyhow. Use the easiest solution: punt
420 to dynamic allocation. */
421 va_copy (args, args_);
422 s = xvasprintf (format, args);
425 pool_register (pool, free, s);
431 /* Formats FORMAT in memory allocated from POOL
432 and returns the formatted string. */
434 pool_asprintf (struct pool *pool, const char *format, ...)
439 va_start (args, format);
440 string = pool_vasprintf (pool, format, args);
446 /* Standard allocation routines. */
448 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
449 returns a pointer to the beginning of the block.
450 If POOL is a null pointer, then allocates a normal memory block
453 pool_malloc (struct pool *pool, size_t amt)
459 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
460 g->type = POOL_GIZMO_MALLOC;
463 return ((char *) g) + POOL_GIZMO_SIZE;
469 return xmalloc (amt);
472 /* Allocates and returns N elements of S bytes each, to be
474 If POOL is a null pointer, then allocates a normal memory block
476 N must be nonnegative, S must be positive.
477 Terminates the program if the memory cannot be obtained,
478 including the case where N * S overflows the range of size_t. */
480 pool_nmalloc (struct pool *pool, size_t n, size_t s)
482 if (xalloc_oversized (n, s))
484 return pool_malloc (pool, n * s);
487 /* Allocates AMT bytes using malloc(), to be managed by POOL,
488 zeros the block, and returns a pointer to the beginning of the
490 If POOL is a null pointer, then allocates a normal memory block
493 pool_zalloc (struct pool *pool, size_t amt)
495 void *p = pool_malloc (pool, amt);
500 /* Allocates and returns N elements of S bytes each, to be
501 managed by POOL, and zeros the block.
502 If POOL is a null pointer, then allocates a normal memory block
504 N must be nonnegative, S must be positive.
505 Terminates the program if the memory cannot be obtained,
506 including the case where N * S overflows the range of size_t. */
508 pool_calloc (struct pool *pool, size_t n, size_t s)
510 void *p = pool_nmalloc (pool, n, s);
511 memset (p, 0, n * s);
515 /* Changes the allocation size of the specified memory block P managed
516 by POOL to AMT bytes and returns a pointer to the beginning of the
518 If POOL is a null pointer, then the block is reallocated in the
519 usual way with realloc(). */
521 pool_realloc (struct pool *pool, void *p, size_t amt)
529 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
530 check_gizmo (pool, g);
532 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
539 check_gizmo (pool, g);
541 return ((char *) g) + POOL_GIZMO_SIZE;
550 return pool_malloc (pool, amt);
553 return xrealloc (p, amt);
556 /* Changes the allocation size of the specified memory block P
557 managed by POOL to N * S bytes and returns a pointer to the
558 beginning of the block.
559 N must be nonnegative, S must be positive.
560 If POOL is a null pointer, then the block is reallocated in
561 the usual way with xrealloc().
562 Terminates the program if the memory cannot be obtained,
563 including the case where N * S overflows the range of size_t. */
565 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
567 if (xalloc_oversized (n, s))
569 return pool_realloc (pool, p, n * s);
572 /* If P is null, allocate a block of at least *PN such objects;
573 otherwise, reallocate P so that it contains more than *PN
574 objects each of S bytes. *PN must be nonzero unless P is
575 null, and S must be nonzero. Set *PN to the new number of
576 objects, and return the pointer to the new block. *PN is
577 never set to zero, and the returned pointer is never null.
579 The block returned is managed by POOL. If POOL is a null
580 pointer, then the block is reallocated in the usual way with
583 Terminates the program if the memory cannot be obtained,
584 including the case where the memory required overflows the
587 Repeated reallocations are guaranteed to make progress, either by
588 allocating an initial block with a nonzero size, or by allocating a
591 In the following implementation, nonzero sizes are doubled so that
592 repeated reallocations have O(N log N) overall cost rather than
593 O(N**2) cost, but the specification for this function does not
594 guarantee that sizes are doubled.
596 Here is an example of use:
601 size_t allocated = 0;
604 append_int (int value)
606 if (used == allocated)
607 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
611 This causes x2nrealloc to allocate a block of some nonzero size the
612 first time it is called.
614 To have finer-grained control over the initial size, set *PN to a
615 nonzero value before calling this function with P == NULL. For
621 size_t allocated = 0;
622 size_t allocated1 = 1000;
625 append_int (int value)
627 if (used == allocated)
629 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
630 allocated = allocated1;
635 This function implementation is from gnulib. */
637 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
645 /* The approximate size to use for initial small allocation
646 requests, when the invoking code specifies an old size of
647 zero. 64 bytes is the largest "small" request for the
648 GNU C library malloc. */
649 enum { DEFAULT_MXFAST = 64 };
651 n = DEFAULT_MXFAST / s;
657 if (SIZE_MAX / 2 / s < n)
663 return pool_realloc (pool, p, n * s);
666 /* Frees block P managed by POOL.
667 If POOL is a null pointer, then the block is freed as usual with
670 pool_free (struct pool *pool, void *p)
672 if (pool != NULL && p != NULL)
674 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
675 check_gizmo (pool, g);
676 delete_gizmo (pool, g);
683 /* Gizmo allocations. */
685 /* Creates and returns a pool as a subpool of POOL.
686 The subpool will be destroyed automatically when POOL is destroyed.
687 It may also be destroyed explicitly in advance. */
689 pool_create_subpool (struct pool *pool)
691 struct pool *subpool;
692 struct pool_gizmo *g;
694 assert (pool != NULL);
695 subpool = pool_create ();
696 subpool->parent = pool;
698 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
699 subpool->blocks->ofs += POOL_GIZMO_SIZE;
701 g->type = POOL_GIZMO_SUBPOOL;
702 g->p.subpool = subpool;
709 /* Makes SUBPOOL a subpool of POOL.
710 SUBPOOL must not already have a parent pool.
711 The subpool will be destroyed automatically when POOL is destroyed.
712 It may also be destroyed explicitly in advance. */
714 pool_add_subpool (struct pool *pool, struct pool *subpool)
716 struct pool_gizmo *g;
718 assert (pool != NULL);
719 assert (subpool != NULL);
720 assert (subpool->parent == NULL);
722 g = pool_alloc (subpool, sizeof *g);
723 g->type = POOL_GIZMO_SUBPOOL;
724 g->p.subpool = subpool;
727 subpool->parent = pool;
730 /* Opens file FILE_NAME with mode MODE and returns a handle to it
731 if successful or a null pointer if not.
732 The file will be closed automatically when POOL is destroyed, or it
733 may be closed explicitly in advance using pool_fclose(), or
734 detached from the pool with pool_detach_file(). */
736 pool_fopen (struct pool *pool, const char *file_name, const char *mode)
740 assert (pool && file_name && mode);
741 f = fopen (file_name, mode);
743 pool_attach_file (pool, f);
748 /* Closes file FILE managed by POOL.
749 Returns 0 if successful, EOF if an I/O error occurred. */
751 pool_fclose (struct pool *pool, FILE *file)
753 assert (pool && file);
754 pool_detach_file (pool, file);
755 return fclose (file);
758 /* Creates a temporary file with tmpfile() and returns a handle to it
759 if successful or a null pointer if not.
760 The file will be closed automatically when POOL is destroyed, or it
761 may be closed explicitly in advance using pool_fclose(), or
762 detached from the pool with pool_detach_file(). */
764 pool_tmpfile (struct pool *pool)
766 FILE *file = tmpfile ();
768 pool_attach_file (pool, file);
772 /* Attaches FILE to POOL.
773 The file will be closed automatically when POOL is destroyed, or it
774 may be closed explicitly in advance using pool_fclose(), or
775 detached from the pool with pool_detach_file(). */
777 pool_attach_file (struct pool *pool, FILE *file)
779 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
780 g->type = POOL_GIZMO_FILE;
785 /* Detaches FILE from POOL. */
787 pool_detach_file (struct pool *pool, FILE *file)
789 struct pool_gizmo *g;
791 for (g = pool->gizmos; g; g = g->next)
792 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
794 delete_gizmo (pool, g);
799 /* Registers FREE to be called with argument P.
800 P should be unique among those registered in POOL so that it can be
801 uniquely identified by pool_unregister().
802 If not unregistered, FREE will be called with argument P when POOL
805 pool_register (struct pool *pool, void (*free) (void *), void *p)
807 assert (pool && free && p);
810 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
811 g->type = POOL_GIZMO_REGISTERED;
812 g->p.registered.free = free;
813 g->p.registered.p = p;
818 /* Unregisters previously registered P from POOL.
819 Returns true only if P was found to be registered in POOL. */
821 pool_unregister (struct pool *pool, void *p)
826 struct pool_gizmo *g;
828 for (g = pool->gizmos; g; g = g->next)
829 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
831 delete_gizmo (pool, g);
839 /* Partial freeing. */
841 /* Notes the state of POOL into MARK so that it may be restored
842 by a call to pool_release(). */
844 pool_mark (struct pool *pool, struct pool_mark *mark)
846 assert (pool && mark);
848 mark->block = pool->blocks;
849 mark->ofs = pool->blocks->ofs;
851 mark->serial = serial;
854 /* Restores to POOL the state recorded in MARK.
855 Emptied blocks are not given back with free() but kept for
856 later allocations. To get that behavior, use a subpool
859 pool_release (struct pool *pool, const struct pool_mark *mark)
861 assert (pool && mark);
864 struct pool_gizmo *cur, *next;
866 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
882 struct pool_block *cur;
884 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
886 cur->ofs = POOL_BLOCK_SIZE;
887 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
889 cur->ofs += POOL_SIZE;
890 if (pool->parent != NULL)
891 cur->ofs += POOL_GIZMO_SIZE;
894 pool->blocks = mark->block;
895 pool->blocks->ofs = mark->ofs;
899 /* Private functions. */
901 /* Adds GIZMO at the beginning of POOL's gizmo list. */
903 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
905 assert (pool && gizmo);
908 gizmo->next = pool->gizmos;
911 pool->gizmos->prev = gizmo;
912 pool->gizmos = gizmo;
914 gizmo->serial = serial++;
916 check_gizmo (pool, gizmo);
919 /* Removes GIZMO from POOL's gizmo list. */
921 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
923 assert (pool && gizmo);
925 check_gizmo (pool, gizmo);
928 gizmo->prev->next = gizmo->next;
930 pool->gizmos = gizmo->next;
932 gizmo->next->prev = gizmo->prev;
935 /* Frees any of GIZMO's internal state.
936 GIZMO's data must not be referenced after calling this function. */
938 free_gizmo (struct pool_gizmo *gizmo)
940 assert (gizmo != NULL);
944 case POOL_GIZMO_MALLOC:
947 case POOL_GIZMO_FILE:
948 fclose (gizmo->p.file); /* Ignore errors. */
950 case POOL_GIZMO_SUBPOOL:
951 gizmo->p.subpool->parent = NULL;
952 pool_destroy (gizmo->p.subpool);
954 case POOL_GIZMO_REGISTERED:
955 gizmo->p.registered.free (gizmo->p.registered.p);
962 /* Free all the gizmos in POOL. */
964 free_all_gizmos (struct pool *pool)
966 struct pool_gizmo *cur, *next;
968 for (cur = pool->gizmos; cur; cur = next)
977 check_gizmo (struct pool *p, struct pool_gizmo *g)
979 assert (g->pool == p);
980 assert (g->next == NULL || g->next->prev == g);
981 assert ((g->prev != NULL && g->prev->next == g)
982 || (g->prev == NULL && p->gizmos == g));