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., 59 Temple Place - Suite 330, Boston, MA
29 /* Fast, low-overhead memory block suballocator. */
32 struct pool *parent; /* Pool of which this pool is a subpool. */
33 struct pool_block *blocks; /* Blocks owned by the pool. */
34 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
40 struct pool_block *prev;
41 struct pool_block *next;
51 POOL_GIZMO_REGISTERED,
54 /* Pool routines can maintain objects (`gizmos') as well as doing
56 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 #if defined (i386) || defined (__i386__)
100 #define ALIGN_SIZE 4 /* Save some extra memory. */
102 #define ALIGN_SIZE sizeof (union align)
105 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
106 suballocation of blocks. This is useful under memory
107 debuggers like Checker or valgrind because it allows the
108 source location of bugs to be more accurately pinpointed.
110 On the other hand, if we're testing the library, then we want to
111 test the library's real functionality, not its crippled, slow,
112 simplified functionality. */
113 /*#define DISCRETE_BLOCKS 1*/
115 /* Enable debug code if appropriate. */
119 /* Size of each block allocated in the pool, in bytes.
120 Should be at least 1k. */
122 #define BLOCK_SIZE 1024
125 /* Maximum size of a suballocated block. Larger blocks are allocated
126 directly with malloc() to avoid memory wastage at the end of a
127 suballocation block. */
129 #define MAX_SUBALLOC 64
132 /* Sizes of some structures with alignment padding included. */
133 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
134 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
135 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
137 /* Serial number used to keep track of gizmos for mark/release. */
138 static long serial = 0;
141 static void add_gizmo (struct pool *, struct pool_gizmo *);
142 static void free_gizmo (struct pool_gizmo *);
143 static void delete_gizmo (struct pool *, struct pool_gizmo *);
146 static void *xmalloc (size_t);
147 static void *xrealloc (void *, size_t);
150 /* General routines. */
152 /* Creates and returns a new memory pool, which allows malloc()'d
153 blocks to be suballocated in a time- and space-efficient manner.
154 The entire contents of the memory pool are freed at once.
156 In addition, other objects can be associated with a memory pool.
157 These are released when the pool is destroyed. */
161 struct pool_block *block;
164 block = xmalloc (BLOCK_SIZE);
165 block->prev = block->next = block;
166 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
168 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
170 pool->blocks = block;
176 /* Destroy the specified pool, including all subpools. */
178 pool_destroy (struct pool *pool)
185 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
188 struct pool_gizmo *cur, *next;
190 for (cur = pool->gizmos; cur; cur = next)
198 struct pool_block *cur, *next;
200 pool->blocks->prev->next = NULL;
201 for (cur = pool->blocks; cur; cur = next)
209 /* Suballocation routines. */
211 /* Allocates a memory region AMT bytes in size from POOL and returns a
212 pointer to the region's start. */
214 pool_alloc (struct pool *pool, size_t amt)
216 assert (pool != NULL);
219 if (amt <= MAX_SUBALLOC)
221 struct pool_block *b = pool->blocks;
222 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
223 if (b->ofs + amt <= BLOCK_SIZE)
225 void *const p = ((char *) b) + b->ofs;
230 b = xmalloc (BLOCK_SIZE);
231 b->next = pool->blocks;
232 b->prev = pool->blocks->prev;
233 b->ofs = POOL_BLOCK_SIZE + amt;
235 pool->blocks->prev->next = b;
236 pool->blocks = pool->blocks->prev = b;
238 return ((char *) b) + POOL_BLOCK_SIZE;
241 #endif /* !DISCRETE_BLOCKS */
242 return pool_malloc (pool, amt);
245 /* Duplicates STRING, which has LENGTH characters, within POOL,
246 and returns a pointer to the duplicate. LENGTH should not
247 include the null terminator, which is always added to the
248 duplicate. For use only with strings, because the returned
249 pointere may not be aligned properly for other types. */
251 pool_strndup (struct pool *pool, const char *string, size_t length)
256 assert (pool && string);
259 /* Note that strings need not be aligned on any boundary. */
262 struct pool_block *const b = pool->blocks;
264 if (b->ofs + size <= BLOCK_SIZE)
266 copy = ((char *) b) + b->ofs;
271 copy = pool_alloc (pool, size);
274 memcpy (copy, string, length);
279 /* Duplicates null-terminated STRING, within POOL, and returns a
280 pointer to the duplicate. For use only with strings, because
281 the returned pointere may not be aligned properly for other
284 pool_strdup (struct pool *pool, const char *string)
286 return pool_strndup (pool, string, strlen (string));
289 /* Standard allocation routines. */
291 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
292 returns a pointer to the beginning of the block.
293 If POOL is a null pointer, then allocates a normal memory block
296 pool_malloc (struct pool *pool, size_t amt)
302 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
303 g->type = POOL_GIZMO_MALLOC;
306 return ((char *) g) + POOL_GIZMO_SIZE;
312 return xmalloc (amt);
315 /* Changes the allocation size of the specified memory block P managed
316 by POOL to AMT bytes and returns a pointer to the beginning of the
318 If POOL is a null pointer, then the block is reallocated in the
319 usual way with realloc(). */
321 pool_realloc (struct pool *pool, void *p, size_t amt)
329 struct pool_gizmo *g;
331 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
332 amt + POOL_GIZMO_SIZE);
340 return ((char *) g) + POOL_GIZMO_SIZE;
349 return pool_malloc (pool, amt);
352 return xrealloc (p, amt);
355 /* Frees block P managed by POOL.
356 If POOL is a null pointer, then the block is freed as usual with
359 pool_free (struct pool *pool, void *p)
361 if (pool != NULL && p != NULL)
363 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
364 delete_gizmo (pool, g);
371 /* Gizmo allocations. */
373 /* Creates and returns a pool as a subpool of POOL.
374 The subpool will be destroyed automatically when POOL is destroyed.
375 It may also be destroyed explicitly in advance. */
377 pool_create_subpool (struct pool *pool)
379 struct pool *subpool;
380 struct pool_gizmo *g;
382 assert (pool != NULL);
383 subpool = pool_create ();
384 subpool->parent = pool;
386 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
387 subpool->blocks->ofs += POOL_GIZMO_SIZE;
389 g->type = POOL_GIZMO_SUBPOOL;
390 g->p.subpool = subpool;
397 /* Opens file FILENAME with mode MODE and returns a handle to it
398 if successful or a null pointer if not.
399 The file will be closed automatically when POOL is destroyed, or it
400 may be closed explicitly in advance using pool_fclose. */
402 pool_fopen (struct pool *pool, const char *filename, const char *mode)
406 assert (pool && filename && mode);
407 f = fopen (filename, mode);
412 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
413 g->type = POOL_GIZMO_FILE;
421 /* Closes file FILE managed by POOL. */
423 pool_fclose (struct pool *pool, FILE *file)
425 assert (pool && file);
426 if (fclose (file) == EOF)
430 struct pool_gizmo *g;
432 for (g = pool->gizmos; g; g = g->next)
433 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
435 delete_gizmo (pool, g);
443 /* Registers FREE to be called with argument P.
444 P should be unique among those registered in POOL so that it can be
445 uniquely identified by pool_unregister().
446 If not unregistered, FREE will be called with argument P when POOL
449 pool_register (struct pool *pool, void (*free) (void *), void *p)
451 assert (pool && free && p);
454 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
455 g->type = POOL_GIZMO_REGISTERED;
456 g->p.registered.free = free;
457 g->p.registered.p = p;
462 /* Unregisters previously registered P from POOL.
463 Returns nonzero only if P was found to be registered in POOL. */
465 pool_unregister (struct pool *pool, void *p)
470 struct pool_gizmo *g;
472 for (g = pool->gizmos; g; g = g->next)
473 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
475 delete_gizmo (pool, g);
483 /* Partial freeing. */
485 /* Notes the state of POOL into MARK so that it may be restored
486 by a call to pool_release(). */
488 pool_mark (struct pool *pool, struct pool_mark *mark)
490 assert (pool && mark);
492 mark->block = pool->blocks;
493 mark->ofs = pool->blocks->ofs;
495 mark->serial = serial;
498 /* Restores to POOL the state recorded in MARK. */
500 pool_release (struct pool *pool, const struct pool_mark *mark)
502 assert (pool && mark);
505 struct pool_gizmo *cur, *next;
507 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
523 struct pool_block *cur, *next, *last;
525 last = pool->blocks->prev;
526 for (cur = pool->blocks; cur != mark->block; cur = next)
529 assert (next != cur);
535 last->next = pool->blocks = cur;
537 cur->ofs = mark->ofs;
541 /* Private functions. */
543 /* Adds GIZMO at the beginning of POOL's gizmo list. */
545 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
547 assert (pool && gizmo);
549 gizmo->next = pool->gizmos;
552 pool->gizmos->prev = gizmo;
553 pool->gizmos = gizmo;
555 gizmo->serial = serial++;
558 /* Removes GIZMO from POOL's gizmo list. */
560 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
562 assert (pool && gizmo);
565 gizmo->prev->next = gizmo->next;
567 pool->gizmos = gizmo->next;
569 gizmo->next->prev = gizmo->prev;
572 /* Frees any of GIZMO's internal state.
573 GIZMO's data must not be referenced after calling this function. */
575 free_gizmo (struct pool_gizmo *gizmo)
577 assert (gizmo != NULL);
581 case POOL_GIZMO_MALLOC:
584 case POOL_GIZMO_FILE:
585 fclose (gizmo->p.file); /* Ignore errors. */
587 case POOL_GIZMO_SUBPOOL:
588 gizmo->p.subpool->parent = NULL;
589 pool_destroy (gizmo->p.subpool);
591 case POOL_GIZMO_REGISTERED:
592 gizmo->p.registered.free (gizmo->p.registered.p);
599 /* Memory allocation. */
602 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
605 xmalloc (size_t size)
617 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
620 xrealloc (void *p, size_t size)
623 return xmalloc (size);
629 p = realloc (p, size);
636 /* Self-test routine. */
645 #define N_ITERATIONS 8192
648 /* Self-test routine.
649 This is not exhaustive, but it can be useful. */
651 main (int argc, char **argv)
656 seed = atoi (argv[1]);
658 seed = time (0) * 257 % 32768;
663 struct pool_mark m1, m2;
664 FILE *files[N_FILES];
668 printf ("Random number seed: %d\n", seed);
671 printf ("Creating pool...\n");
672 pool = pool_create ();
674 printf ("Marking pool state...\n");
675 pool_mark (pool, &m1);
677 printf (" Populating pool with random-sized small objects...\n");
678 for (i = 0; i < N_ITERATIONS; i++)
680 size_t size = rand () % MAX_SUBALLOC;
681 void *p = pool_alloc (pool, size);
685 printf (" Marking pool state...\n");
686 pool_mark (pool, &m2);
688 printf (" Populating pool with random-sized small "
689 "and large objects...\n");
690 for (i = 0; i < N_ITERATIONS; i++)
692 size_t size = rand () % (2 * MAX_SUBALLOC);
693 void *p = pool_alloc (pool, size);
697 printf (" Releasing pool state...\n");
698 pool_release (pool, &m2);
700 printf (" Populating pool with random objects and gizmos...\n");
701 for (i = 0; i < N_FILES; i++)
704 for (i = 0; i < N_ITERATIONS; i++)
706 int type = rand () % 32;
710 if (files[cur_file] != NULL
711 && EOF == pool_fclose (pool, files[cur_file]))
712 printf ("error on fclose: %s\n", strerror (errno));
714 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
716 if (++cur_file >= N_FILES)
720 pool_create_subpool (pool);
723 size_t size = rand () % (2 * MAX_SUBALLOC);
724 void *p = pool_alloc (pool, size);
729 printf ("Releasing pool state...\n");
730 pool_release (pool, &m1);
732 printf ("Destroying pool...\n");
739 #endif /* SELF_TEST */
743 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"