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. */
121 /* Size of each block allocated in the pool, in bytes.
122 Should be at least 1k. */
124 #define BLOCK_SIZE 1024
127 /* Maximum size of a suballocated block. Larger blocks are allocated
128 directly with malloc() to avoid memory wastage at the end of a
129 suballocation block. */
131 #define MAX_SUBALLOC 64
134 /* Sizes of some structures with alignment padding included. */
135 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
136 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
137 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
139 /* Serial number used to keep track of gizmos for mark/release. */
140 static long serial = 0;
143 static void add_gizmo (struct pool *, struct pool_gizmo *);
144 static void free_gizmo (struct pool_gizmo *);
145 static void delete_gizmo (struct pool *, struct pool_gizmo *);
148 static void *xmalloc (size_t);
149 static void *xrealloc (void *, size_t);
152 /* General routines. */
154 /* Creates and returns a new memory pool, which allows malloc()'d
155 blocks to be suballocated in a time- and space-efficient manner.
156 The entire contents of the memory pool are freed at once.
158 In addition, other objects can be associated with a memory pool.
159 These are released when the pool is destroyed. */
163 struct pool_block *block;
166 block = xmalloc (BLOCK_SIZE);
167 block->prev = block->next = block;
168 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
170 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
172 pool->blocks = block;
178 /* Destroy the specified pool, including all subpools. */
180 pool_destroy (struct pool *pool)
187 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
190 struct pool_gizmo *cur, *next;
192 for (cur = pool->gizmos; cur; cur = next)
200 struct pool_block *cur, *next;
202 pool->blocks->prev->next = NULL;
203 for (cur = pool->blocks; cur; cur = next)
211 /* Suballocation routines. */
213 /* Allocates a memory region AMT bytes in size from POOL and returns a
214 pointer to the region's start. */
216 pool_alloc (struct pool *pool, size_t amt)
218 assert (pool != NULL);
221 if (amt <= MAX_SUBALLOC)
223 struct pool_block *b = pool->blocks;
224 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
225 if (b->ofs + amt <= BLOCK_SIZE)
227 void *const p = ((char *) b) + b->ofs;
232 b = xmalloc (BLOCK_SIZE);
233 b->next = pool->blocks;
234 b->prev = pool->blocks->prev;
235 b->ofs = POOL_BLOCK_SIZE + amt;
237 pool->blocks->prev->next = b;
238 pool->blocks = pool->blocks->prev = b;
240 return ((char *) b) + POOL_BLOCK_SIZE;
243 #endif /* !DISCRETE_BLOCKS */
244 return pool_malloc (pool, amt);
247 /* Duplicates STRING, which has LENGTH characters, within POOL,
248 and returns a pointer to the duplicate. LENGTH should not
249 include the null terminator, which is always added to the
250 duplicate. For use only with strings, because the returned
251 pointere may not be aligned properly for other types. */
253 pool_strndup (struct pool *pool, const char *string, size_t length)
258 assert (pool && string);
261 /* Note that strings need not be aligned on any boundary. */
264 struct pool_block *const b = pool->blocks;
266 if (b->ofs + size <= BLOCK_SIZE)
268 copy = ((char *) b) + b->ofs;
273 copy = pool_alloc (pool, size);
276 memcpy (copy, string, length);
281 /* Duplicates null-terminated STRING, within POOL, and returns a
282 pointer to the duplicate. For use only with strings, because
283 the returned pointere may not be aligned properly for other
286 pool_strdup (struct pool *pool, const char *string)
288 return pool_strndup (pool, string, strlen (string));
291 /* Standard allocation routines. */
293 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
294 returns a pointer to the beginning of the block.
295 If POOL is a null pointer, then allocates a normal memory block
298 pool_malloc (struct pool *pool, size_t amt)
304 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
305 g->type = POOL_GIZMO_MALLOC;
308 return ((char *) g) + POOL_GIZMO_SIZE;
314 return xmalloc (amt);
317 /* Changes the allocation size of the specified memory block P managed
318 by POOL to AMT bytes and returns a pointer to the beginning of the
320 If POOL is a null pointer, then the block is reallocated in the
321 usual way with realloc(). */
323 pool_realloc (struct pool *pool, void *p, size_t amt)
331 struct pool_gizmo *g;
333 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
334 amt + POOL_GIZMO_SIZE);
342 return ((char *) g) + POOL_GIZMO_SIZE;
351 return pool_malloc (pool, amt);
354 return xrealloc (p, amt);
357 /* Frees block P managed by POOL.
358 If POOL is a null pointer, then the block is freed as usual with
361 pool_free (struct pool *pool, void *p)
363 if (pool != NULL && p != NULL)
365 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
366 delete_gizmo (pool, g);
373 /* Gizmo allocations. */
375 /* Creates and returns a pool as a subpool of POOL.
376 The subpool will be destroyed automatically when POOL is destroyed.
377 It may also be destroyed explicitly in advance. */
379 pool_create_subpool (struct pool *pool)
381 struct pool *subpool;
382 struct pool_gizmo *g;
384 assert (pool != NULL);
385 subpool = pool_create ();
386 subpool->parent = pool;
388 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
389 subpool->blocks->ofs += POOL_GIZMO_SIZE;
391 g->type = POOL_GIZMO_SUBPOOL;
392 g->p.subpool = subpool;
399 /* Opens file FILENAME with mode MODE and returns a handle to it
400 if successful or a null pointer if not.
401 The file will be closed automatically when POOL is destroyed, or it
402 may be closed explicitly in advance using pool_fclose. */
404 pool_fopen (struct pool *pool, const char *filename, const char *mode)
408 assert (pool && filename && mode);
409 f = fopen (filename, mode);
414 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
415 g->type = POOL_GIZMO_FILE;
423 /* Closes file FILE managed by POOL. */
425 pool_fclose (struct pool *pool, FILE *file)
427 assert (pool && file);
428 if (fclose (file) == EOF)
432 struct pool_gizmo *g;
434 for (g = pool->gizmos; g; g = g->next)
435 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
437 delete_gizmo (pool, g);
445 /* Registers FREE to be called with argument P.
446 P should be unique among those registered in POOL so that it can be
447 uniquely identified by pool_unregister().
448 If not unregistered, FREE will be called with argument P when POOL
451 pool_register (struct pool *pool, void (*free) (void *), void *p)
453 assert (pool && free && p);
456 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
457 g->type = POOL_GIZMO_REGISTERED;
458 g->p.registered.free = free;
459 g->p.registered.p = p;
464 /* Unregisters previously registered P from POOL.
465 Returns nonzero only if P was found to be registered in POOL. */
467 pool_unregister (struct pool *pool, void *p)
472 struct pool_gizmo *g;
474 for (g = pool->gizmos; g; g = g->next)
475 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
477 delete_gizmo (pool, g);
485 /* Partial freeing. */
487 /* Notes the state of POOL into MARK so that it may be restored
488 by a call to pool_release(). */
490 pool_mark (struct pool *pool, struct pool_mark *mark)
492 assert (pool && mark);
494 mark->block = pool->blocks;
495 mark->ofs = pool->blocks->ofs;
497 mark->serial = serial;
500 /* Restores to POOL the state recorded in MARK. */
502 pool_release (struct pool *pool, const struct pool_mark *mark)
504 assert (pool && mark);
507 struct pool_gizmo *cur, *next;
509 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
525 struct pool_block *cur, *next, *last;
527 last = pool->blocks->prev;
528 for (cur = pool->blocks; cur != mark->block; cur = next)
531 assert (next != cur);
537 last->next = pool->blocks = cur;
539 cur->ofs = mark->ofs;
543 /* Private functions. */
545 /* Adds GIZMO at the beginning of POOL's gizmo list. */
547 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
549 assert (pool && gizmo);
551 gizmo->next = pool->gizmos;
554 pool->gizmos->prev = gizmo;
555 pool->gizmos = gizmo;
557 gizmo->serial = serial++;
560 /* Removes GIZMO from POOL's gizmo list. */
562 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
564 assert (pool && gizmo);
567 gizmo->prev->next = gizmo->next;
569 pool->gizmos = gizmo->next;
571 gizmo->next->prev = gizmo->prev;
574 /* Frees any of GIZMO's internal state.
575 GIZMO's data must not be referenced after calling this function. */
577 free_gizmo (struct pool_gizmo *gizmo)
579 assert (gizmo != NULL);
583 case POOL_GIZMO_MALLOC:
586 case POOL_GIZMO_FILE:
587 fclose (gizmo->p.file); /* Ignore errors. */
589 case POOL_GIZMO_SUBPOOL:
590 gizmo->p.subpool->parent = NULL;
591 pool_destroy (gizmo->p.subpool);
593 case POOL_GIZMO_REGISTERED:
594 gizmo->p.registered.free (gizmo->p.registered.p);
601 /* Memory allocation. */
604 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
607 xmalloc (size_t size)
619 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
622 xrealloc (void *p, size_t size)
625 return xmalloc (size);
631 p = realloc (p, size);
638 /* Self-test routine. */
647 #define N_ITERATIONS 8192
650 /* Self-test routine.
651 This is not exhaustive, but it can be useful. */
653 main (int argc, char **argv)
658 seed = atoi (argv[1]);
660 seed = time (0) * 257 % 32768;
665 struct pool_mark m1, m2;
666 FILE *files[N_FILES];
670 printf ("Random number seed: %d\n", seed);
673 printf ("Creating pool...\n");
674 pool = pool_create ();
676 printf ("Marking pool state...\n");
677 pool_mark (pool, &m1);
679 printf (" Populating pool with random-sized small objects...\n");
680 for (i = 0; i < N_ITERATIONS; i++)
682 size_t size = rand () % MAX_SUBALLOC;
683 void *p = pool_alloc (pool, size);
687 printf (" Marking pool state...\n");
688 pool_mark (pool, &m2);
690 printf (" Populating pool with random-sized small "
691 "and large objects...\n");
692 for (i = 0; i < N_ITERATIONS; i++)
694 size_t size = rand () % (2 * MAX_SUBALLOC);
695 void *p = pool_alloc (pool, size);
699 printf (" Releasing pool state...\n");
700 pool_release (pool, &m2);
702 printf (" Populating pool with random objects and gizmos...\n");
703 for (i = 0; i < N_FILES; i++)
706 for (i = 0; i < N_ITERATIONS; i++)
708 int type = rand () % 32;
712 if (files[cur_file] != NULL
713 && EOF == pool_fclose (pool, files[cur_file]))
714 printf ("error on fclose: %s\n", strerror (errno));
716 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
718 if (++cur_file >= N_FILES)
722 pool_create_subpool (pool);
725 size_t size = rand () % (2 * MAX_SUBALLOC);
726 void *p = pool_alloc (pool, size);
731 printf ("Releasing pool state...\n");
732 pool_release (pool, &m1);
734 printf ("Destroying pool...\n");
741 #endif /* SELF_TEST */
745 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"