Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / pool.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
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.
9
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.
14
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
18    02111-1307, USA. */
19
20 #if HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23 #include "pool.h"
24 #include "error.h"
25 #include <stdlib.h>
26 #include "alloc.h"
27 #include "str.h"
28
29 /* Fast, low-overhead memory block suballocator. */
30 struct pool
31   {
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. */
35   };
36
37 /* Pool block. */
38 struct pool_block 
39   {
40     struct pool_block *prev;
41     struct pool_block *next;
42     size_t ofs;
43   };
44
45 /* Gizmo types. */
46 enum
47   {
48     POOL_GIZMO_MALLOC,
49     POOL_GIZMO_FILE,
50     POOL_GIZMO_SUBPOOL,
51     POOL_GIZMO_REGISTERED,
52   };
53
54 /* Pool routines can maintain objects (`gizmos') as well as doing
55    suballocation.  
56    This structure is used to keep track of them. */
57 struct pool_gizmo
58   {
59     struct pool_gizmo *prev;
60     struct pool_gizmo *next;
61
62     long serial;                /* Serial number. */
63     int type;                   /* Type of this gizmo. */
64
65     /* Type-dependent info. */
66     union
67       {
68         FILE *file;             /* POOL_GIZMO_FILE. */
69         struct pool *subpool;   /* POOL_GIZMO_SUBPOOL. */
70
71         /* POOL_GIZMO_REGISTERED. */
72         struct
73           {
74             void (*free) (void *p);
75             void *p;
76           }
77         registered;
78       }
79     p;
80   };
81
82 /* Rounds X up to the next multiple of Y. */
83 #ifndef ROUND_UP
84 #define ROUND_UP(X, Y)                          \
85         (((X) + ((Y) - 1)) / (Y) * (Y))
86 #endif
87
88 /* Types that provide typically useful alignment sizes. */
89 union align
90   {
91     void *op;
92     void (*fp) (void);
93     long l;
94     double d;
95   };
96
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. */
101 #else
102 #define ALIGN_SIZE sizeof (union align)
103 #endif
104
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.
109
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*/
114
115 /* Enable debug code if appropriate. */
116 #if SELF_TEST
117 #endif
118
119 /* Size of each block allocated in the pool, in bytes.
120    Should be at least 1k. */
121 #ifndef BLOCK_SIZE
122 #define BLOCK_SIZE 1024
123 #endif
124
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. */
128 #ifndef MAX_SUBALLOC
129 #define MAX_SUBALLOC 64
130 #endif
131
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)
136
137 /* Serial number used to keep track of gizmos for mark/release. */
138 static long serial = 0;
139
140 /* Prototypes. */
141 static void add_gizmo (struct pool *, struct pool_gizmo *);
142 static void free_gizmo (struct pool_gizmo *);
143 static void free_all_gizmos (struct pool *pool);
144 static void delete_gizmo (struct pool *, struct pool_gizmo *);
145
146 #if !PSPP
147 static void *xmalloc (size_t);
148 static void *xrealloc (void *, size_t);
149 #endif
150 \f
151 /* General routines. */
152
153 /* Creates and returns a new memory pool, which allows malloc()'d
154    blocks to be suballocated in a time- and space-efficient manner.
155    The entire contents of the memory pool are freed at once.
156
157    In addition, other objects can be associated with a memory pool.
158    These are released when the pool is destroyed. */
159 struct pool *
160 pool_create (void)
161 {
162   struct pool_block *block;
163   struct pool *pool;
164
165   block = xmalloc (BLOCK_SIZE);
166   block->prev = block->next = block;
167   block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
168   
169   pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
170   pool->parent = NULL;
171   pool->blocks = block;
172   pool->gizmos = NULL;
173
174   return pool;
175 }
176
177 /* Destroy the specified pool, including all subpools. */
178 void
179 pool_destroy (struct pool *pool)
180 {
181   if (pool == NULL)
182     return;
183
184   /* Remove this pool from its parent's list of gizmos. */
185   if (pool->parent) 
186     delete_gizmo (pool->parent,
187                   (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
188
189   free_all_gizmos (pool);
190
191   /* Free all the memory. */
192   {
193     struct pool_block *cur, *next;
194
195     pool->blocks->prev->next = NULL;
196     for (cur = pool->blocks; cur; cur = next)
197       {
198         next = cur->next;
199         free (cur);
200       }
201   }
202 }
203
204 /* Release all the memory and gizmos in POOL.
205    Blocks are not given back with free() but kept for later
206    allocations.  To give back memory, use a subpool instead. */ 
207 void
208 pool_clear (struct pool *pool) 
209 {
210   free_all_gizmos (pool);
211
212   /* Zero out block sizes. */
213   {
214     struct pool_block *cur;
215     
216     cur = pool->blocks;
217     do
218       {
219         cur->ofs = POOL_BLOCK_SIZE;
220         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
221           cur->ofs += POOL_SIZE;
222         cur = cur->next;
223       }
224     while (cur != pool->blocks);
225   }
226 }
227 \f
228 /* Suballocation routines. */
229
230 /* Allocates a memory region AMT bytes in size from POOL and returns a
231    pointer to the region's start. */
232 void *
233 pool_alloc (struct pool *pool, size_t amt)
234 {
235   assert (pool != NULL);
236   
237 #ifndef DISCRETE_BLOCKS
238   if (amt <= MAX_SUBALLOC)
239     {
240       /* If there is space in this block, take it. */
241       struct pool_block *b = pool->blocks;
242       b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
243       if (b->ofs + amt <= BLOCK_SIZE)
244         {
245           void *const p = ((char *) b) + b->ofs;
246           b->ofs += amt;
247           return p;
248         }
249
250       /* No space in this block, so we must make other
251          arrangements. */
252       if (b->next->ofs == 0) 
253         {
254           /* The next block is empty.  Use it. */
255           b = b->next;
256           b->ofs = POOL_BLOCK_SIZE;
257           if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
258             b->ofs += POOL_SIZE;
259         }
260       else 
261         {
262           /* Create a new block at the start of the list. */
263           b = xmalloc (BLOCK_SIZE);
264           b->next = pool->blocks;
265           b->prev = pool->blocks->prev;
266           b->ofs = POOL_BLOCK_SIZE;
267           pool->blocks->prev->next = b;
268           pool->blocks->prev = b;
269         }
270       pool->blocks = b;
271
272       /* Allocate space from B. */
273       b->ofs += amt;
274       return ((char *) b) + b->ofs - amt;
275     }
276   else
277 #endif
278     return pool_malloc (pool, amt);
279 }
280
281 /* Duplicates STRING, which has LENGTH characters, within POOL,
282    and returns a pointer to the duplicate.  LENGTH should not
283    include the null terminator, which is always added to the
284    duplicate.  For use only with strings, because the returned
285    pointere may not be aligned properly for other types. */
286 char *
287 pool_strndup (struct pool *pool, const char *string, size_t length)
288 {
289   size_t size;
290   char *copy;
291
292   assert (pool && string);
293   size = length + 1;
294
295   /* Note that strings need not be aligned on any boundary. */
296 #ifndef DISCRETE_BLOCKS
297   {
298     struct pool_block *const b = pool->blocks;
299
300     if (b->ofs + size <= BLOCK_SIZE)
301       {
302         copy = ((char *) b) + b->ofs;
303         b->ofs += size;
304       }
305     else
306       copy = pool_alloc (pool, size);
307   }
308 #else
309   copy = pool_alloc (pool, size);
310 #endif
311
312   memcpy (copy, string, length);
313   copy[length] = '\0';
314   return copy;
315 }
316
317 /* Duplicates null-terminated STRING, within POOL, and returns a
318    pointer to the duplicate.  For use only with strings, because
319    the returned pointere may not be aligned properly for other
320    types. */
321 char *
322 pool_strdup (struct pool *pool, const char *string) 
323 {
324   return pool_strndup (pool, string, strlen (string));
325 }
326 \f
327 /* Standard allocation routines. */
328
329 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
330    returns a pointer to the beginning of the block.
331    If POOL is a null pointer, then allocates a normal memory block
332    with malloc().  */
333 void *
334 pool_malloc (struct pool *pool, size_t amt)
335 {
336   if (pool != NULL)
337     {
338       if (amt != 0)
339         {
340           struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
341           g->type = POOL_GIZMO_MALLOC;
342           add_gizmo (pool, g);
343
344           return ((char *) g) + POOL_GIZMO_SIZE;
345         }
346       else
347         return NULL;
348     }
349   else
350     return xmalloc (amt);
351 }
352
353 /* Changes the allocation size of the specified memory block P managed
354    by POOL to AMT bytes and returns a pointer to the beginning of the
355    block.
356    If POOL is a null pointer, then the block is reallocated in the
357    usual way with realloc(). */
358 void *
359 pool_realloc (struct pool *pool, void *p, size_t amt)
360 {
361   if (pool != NULL)
362     {
363       if (p != NULL)
364         {
365           if (amt != 0)
366             {
367               struct pool_gizmo *g;
368
369               g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
370                             amt + POOL_GIZMO_SIZE);
371               if (g->next)
372                 g->next->prev = g;
373               if (g->prev)
374                 g->prev->next = g;
375               else
376                 pool->gizmos = g;
377
378               return ((char *) g) + POOL_GIZMO_SIZE;
379             }
380           else
381             {
382               pool_free (pool, p);
383               return NULL;
384             }
385         }
386       else
387         return pool_malloc (pool, amt);
388     }
389   else
390     return xrealloc (p, amt);
391 }
392
393 /* Frees block P managed by POOL.
394    If POOL is a null pointer, then the block is freed as usual with
395    free(). */
396 void
397 pool_free (struct pool *pool, void *p)
398 {
399   if (pool != NULL && p != NULL)
400     {
401       struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
402       delete_gizmo (pool, g);
403       free (g);
404     }
405   else
406     free (p);
407 }
408 \f
409 /* Gizmo allocations. */
410
411 /* Creates and returns a pool as a subpool of POOL.
412    The subpool will be destroyed automatically when POOL is destroyed.
413    It may also be destroyed explicitly in advance. */
414 struct pool *
415 pool_create_subpool (struct pool *pool)
416 {
417   struct pool *subpool;
418   struct pool_gizmo *g;
419
420   assert (pool != NULL);
421   subpool = pool_create ();
422   subpool->parent = pool;
423
424   g = (void *) (((char *) subpool) + subpool->blocks->ofs);
425   subpool->blocks->ofs += POOL_GIZMO_SIZE;
426   
427   g->type = POOL_GIZMO_SUBPOOL;
428   g->p.subpool = subpool;
429
430   add_gizmo (pool, g);
431
432   return subpool;
433 }
434
435 /* Opens file FILENAME with mode MODE and returns a handle to it
436    if successful or a null pointer if not.
437    The file will be closed automatically when POOL is destroyed, or it
438    may be closed explicitly in advance using pool_fclose. */
439 FILE *
440 pool_fopen (struct pool *pool, const char *filename, const char *mode)
441 {
442   FILE *f;
443
444   assert (pool && filename && mode);
445   f = fopen (filename, mode);
446   if (f == NULL)
447     return NULL;
448
449   {
450     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
451     g->type = POOL_GIZMO_FILE;
452     g->p.file = f;
453     add_gizmo (pool, g);
454   }
455
456   return f;
457 }
458
459 /* Closes file FILE managed by POOL. */
460 int
461 pool_fclose (struct pool *pool, FILE *file)
462 {
463   assert (pool && file);
464   if (fclose (file) == EOF)
465     return EOF;
466   
467   {
468     struct pool_gizmo *g;
469
470     for (g = pool->gizmos; g; g = g->next)
471       if (g->type == POOL_GIZMO_FILE && g->p.file == file)
472         {
473           delete_gizmo (pool, g);
474           break;
475         }
476   }
477   
478   return 0;
479 }
480 \f
481 /* Registers FREE to be called with argument P.
482    P should be unique among those registered in POOL so that it can be
483    uniquely identified by pool_unregister().
484    If not unregistered, FREE will be called with argument P when POOL
485    is destroyed. */
486 void
487 pool_register (struct pool *pool, void (*free) (void *), void *p)
488 {
489   assert (pool && free && p);
490
491   {
492     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
493     g->type = POOL_GIZMO_REGISTERED;
494     g->p.registered.free = free;
495     g->p.registered.p = p;
496     add_gizmo (pool, g);
497   }
498 }
499
500 /* Unregisters previously registered P from POOL.
501    Returns nonzero only if P was found to be registered in POOL. */
502 int
503 pool_unregister (struct pool *pool, void *p)
504 {
505   assert (pool && p);
506   
507   {
508     struct pool_gizmo *g;
509
510     for (g = pool->gizmos; g; g = g->next)
511       if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
512         {
513           delete_gizmo (pool, g);
514           return 1;
515         }
516   }
517   
518   return 0;
519 }
520 \f
521 /* Partial freeing. */
522
523 /* Notes the state of POOL into MARK so that it may be restored
524    by a call to pool_release(). */
525 void
526 pool_mark (struct pool *pool, struct pool_mark *mark)
527 {
528   assert (pool && mark);
529
530   mark->block = pool->blocks;
531   mark->ofs = pool->blocks->ofs;
532
533   mark->serial = serial;
534 }
535
536 /* Restores to POOL the state recorded in MARK.
537    Emptied blocks are not given back with free() but kept for
538    later allocations.  To get that behavior, use a subpool
539    instead. */ 
540 void
541 pool_release (struct pool *pool, const struct pool_mark *mark)
542 {
543   assert (pool && mark);
544   
545   {
546     struct pool_gizmo *cur, *next;
547
548     for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
549       {
550         next = cur->next;
551         free_gizmo (cur);
552       }
553
554     if (cur != NULL)
555       {
556         cur->prev = NULL;
557         pool->gizmos = cur;
558       }
559     else
560       pool->gizmos = NULL;
561   }
562   
563   {
564     struct pool_block *cur;
565
566     for (cur = pool->blocks; cur != mark->block; cur = cur->next) 
567       {
568         cur->ofs = POOL_BLOCK_SIZE;
569         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
570           cur->ofs += POOL_SIZE; 
571       }
572     pool->blocks = mark->block;
573     pool->blocks->ofs = mark->ofs;
574   }
575 }
576 \f
577 /* Private functions. */
578
579 /* Adds GIZMO at the beginning of POOL's gizmo list. */
580 static void
581 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
582 {
583   assert (pool && gizmo);
584   
585   gizmo->next = pool->gizmos;
586   gizmo->prev = NULL;
587   if (pool->gizmos)
588     pool->gizmos->prev = gizmo;
589   pool->gizmos = gizmo;
590
591   gizmo->serial = serial++;
592 }
593  
594 /* Removes GIZMO from POOL's gizmo list. */
595 static void
596 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
597 {
598   assert (pool && gizmo);
599   
600   if (gizmo->prev)
601     gizmo->prev->next = gizmo->next;
602   else
603     pool->gizmos = gizmo->next;
604   if (gizmo->next)
605     gizmo->next->prev = gizmo->prev;
606 }
607
608 /* Frees any of GIZMO's internal state.
609    GIZMO's data must not be referenced after calling this function. */
610 static void
611 free_gizmo (struct pool_gizmo *gizmo)
612 {
613   assert (gizmo != NULL);
614   
615   switch (gizmo->type)
616     {
617     case POOL_GIZMO_MALLOC:
618       free (gizmo);
619       break;
620     case POOL_GIZMO_FILE:
621       fclose (gizmo->p.file);   /* Ignore errors. */
622       break;
623     case POOL_GIZMO_SUBPOOL:
624       gizmo->p.subpool->parent = NULL;
625       pool_destroy (gizmo->p.subpool);
626       break;
627     case POOL_GIZMO_REGISTERED:
628       gizmo->p.registered.free (gizmo->p.registered.p);
629       break;
630     default:
631       assert (0);
632     }
633 }
634
635 /* Free all the gizmos in POOL. */
636 static void
637 free_all_gizmos (struct pool *pool) 
638 {
639   struct pool_gizmo *cur, *next;
640
641   for (cur = pool->gizmos; cur; cur = next)
642     {
643       next = cur->next;
644       free_gizmo (cur);
645     }
646   pool->gizmos=NULL;
647 }
648 \f
649 /* Memory allocation. */
650
651 #if !PSPP
652 /* Allocates SIZE bytes of space using malloc().  Aborts if out of
653    memory. */
654 static void *
655 xmalloc (size_t size)
656 {
657   void *vp;
658   if (size == 0)
659     return NULL;
660   vp = malloc (size);
661   assert (vp != NULL);
662   if (vp == NULL)
663     abort ();
664   return vp;
665 }
666
667 /* Reallocates P to be SIZE bytes long using realloc().  Aborts if out
668    of memory. */
669 static void *
670 xrealloc (void *p, size_t size)
671 {
672   if (p == NULL)
673     return xmalloc (size);
674   if (size == 0)
675     {
676       free (p);
677       return NULL;
678     }
679   p = realloc (p, size);
680   if (p == NULL)
681     abort ();
682   return p;
683 }
684 #endif /* !PSPP */
685 \f
686 /* Self-test routine. */
687
688 #if SELF_TEST
689 #include <errno.h>
690 #include <stdio.h>
691 #include <stdlib.h>
692 #include <string.h>
693 #include <time.h>
694
695 #define N_ITERATIONS 8192
696 #define N_FILES 16
697
698 /* Self-test routine.
699    This is not exhaustive, but it can be useful. */
700 int
701 main (int argc, char **argv)
702 {
703   int seed;
704   
705   if (argc == 2)
706     seed = atoi (argv[1]);
707   else
708     seed = time (0) * 257 % 32768;
709
710   for (;;)
711     {
712       struct pool *pool;
713       struct pool_mark m1, m2;
714       FILE *files[N_FILES];
715       int cur_file;
716       long i;
717
718       printf ("Random number seed: %d\n", seed);
719       srand (seed++);
720
721       printf ("Creating pool...\n");
722       pool = pool_create ();
723
724       printf ("Marking pool state...\n");
725       pool_mark (pool, &m1);
726
727       printf ("    Populating pool with random-sized small objects...\n");
728       for (i = 0; i < N_ITERATIONS; i++)
729         {
730           size_t size = rand () % MAX_SUBALLOC;
731           void *p = pool_alloc (pool, size);
732           memset (p, 0, size);
733         }
734
735       printf ("    Marking pool state...\n");
736       pool_mark (pool, &m2);
737       
738       printf ("       Populating pool with random-sized small "
739               "and large objects...\n");
740       for (i = 0; i < N_ITERATIONS; i++)
741         {
742           size_t size = rand () % (2 * MAX_SUBALLOC);
743           void *p = pool_alloc (pool, size);
744           memset (p, 0, size);
745         }
746
747       printf ("    Releasing pool state...\n");
748       pool_release (pool, &m2);
749
750       printf ("    Populating pool with random objects and gizmos...\n");
751       for (i = 0; i < N_FILES; i++)
752         files[i] = NULL;
753       cur_file = 0;
754       for (i = 0; i < N_ITERATIONS; i++)
755         {
756           int type = rand () % 32;
757
758           if (type == 0)
759             {
760               if (files[cur_file] != NULL
761                   && EOF == pool_fclose (pool, files[cur_file]))
762                 printf ("error on fclose: %s\n", strerror (errno));
763
764               files[cur_file] = pool_fopen (pool, "/dev/null", "r");
765
766               if (++cur_file >= N_FILES)
767                 cur_file = 0;
768             }
769           else if (type == 1)
770             pool_create_subpool (pool);
771           else 
772             {
773               size_t size = rand () % (2 * MAX_SUBALLOC);
774               void *p = pool_alloc (pool, size);
775               memset (p, 0, size);
776             }
777         }
778       
779       printf ("Releasing pool state...\n");
780       pool_release (pool, &m1);
781
782       printf ("Destroying pool...\n");
783       pool_destroy (pool);
784
785       putchar ('\n');
786     }
787 }
788
789 #endif /* SELF_TEST */
790
791 /* 
792    Local variables:
793    compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"
794    End:
795 */