home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / g / gs252src.zip / GS252 / IALLOC.C < prev    next >
C/C++ Source or Header  |  1992-06-11  |  12KB  |  378 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* ialloc.c */
  21. /* Memory allocator for Ghostscript interpreter */
  22. #include "gs.h"
  23. #include "gdebug.h"
  24. #include "memory_.h"
  25. #include "alloc.h"
  26. #include "astate.h"
  27.  
  28. /* Forward references */
  29. private int alloc_add_chunk(P2(alloc_state_ptr, uint));
  30. private char *alloc_large(P3(alloc_state_ptr, uint, const char *));
  31. private void alloc_free_large(P3(char *, uint, const char *));
  32.  
  33. /* The only allocator instance (for now). */
  34. private alloc_state as_current;
  35. alloc_state_ptr alloc_state_current = &as_current;
  36.  
  37. /* Debugging printout */
  38. #ifdef DEBUG
  39. #  define alloc_print_block(rtag, tag, blk, sz)\
  40.     fprintf(gs_debug_out, "[a:%c:%c:%s] %lx(%u)\n", rtag, tag,\
  41.         client_name, (ulong)blk, sz)
  42. #  define alloc_print(rtag, tag, blk, sz)\
  43.     if ( gs_debug['A'] || (gs_debug['a'] && align_round(sz) > max_chain_size) )\
  44.       alloc_print_block(rtag, tag, blk, sz)
  45. #  define alloc_print_large(rtag, tag, blk, sz)\
  46.     if ( gs_debug['A'] | gs_debug['a'] )\
  47.       alloc_print_block(rtag, tag, blk, sz)
  48. #else
  49. #  define alloc_print(rtag, tag, blk, sz)
  50. #  define alloc_print_large(rtag, tag, blk, sz)
  51. #endif
  52.  
  53. /* ------ Initialize/status ------ */
  54.  
  55. /* Initialize the allocator */
  56. void
  57. alloc_init(proc_alloc_t palloc, proc_free_t pfree, uint chunk_size)
  58. {    register alloc_state_ptr ap = alloc_state_current;
  59.     memset(ap, 0, sizeof(alloc_state));    /* do it all at once */
  60.     ap->chunk_size = chunk_size;
  61.     ap->big_size = chunk_size / 4;
  62.     ap->palloc = palloc;
  63.     ap->pfree = pfree;
  64.     ap->last_freed = 0;
  65.        {    extern void alloc_save_init(P0());
  66.         alloc_save_init();
  67.        }
  68. }
  69.  
  70. /* Return the status of the allocator: space used, total space. */
  71. void
  72. alloc_status(long *pused, long *ptotal)
  73. {    register alloc_state_ptr ap = alloc_state_current;
  74.     *pused = (ap->cbot - ap->cbase) + (ap->climit - ap->ctop) + ap->used;
  75.     *ptotal = ap->total;
  76. }
  77.  
  78. /* ------ Allocation and freeing ------ */
  79.  
  80. /* Allocate an object.  Return 0 if not enough room. */
  81. char *
  82. alloc(uint num_elts, uint elt_size, const char *client_name)
  83. {    register alloc_state_ptr ap = alloc_state_current;
  84.     uint size = num_elts * elt_size;
  85.     uint block_size;
  86.     uint left;
  87.     if ( size >= ap->big_size )
  88.        {    /* Large object, do a separate malloc. */
  89.         char *block = alloc_large(ap, size, client_name);
  90.         if ( block != NULL ) return block;
  91.         if ( size > ap->chunk_size )
  92.             return 0;    /* can't alloc */
  93.        }
  94.     block_size = align_round(size);
  95.     if ( block_size <= max_chain_size )
  96.        {    /* See if we can use a freed block. */
  97.         char **fptr = &ap->free[block_size >> log2_align_mod];
  98.         char *block = *fptr;
  99.         if ( block != 0 )
  100.            {    *fptr = *(char **)block;
  101.             alloc_print('+', '#', block, size);
  102.             return block;
  103.            }
  104.        }
  105.     left = ap->ctop - ap->cbot;
  106.     if ( block_size > left )
  107.        {    uint csize = ap->chunk_size;
  108.         while ( !alloc_add_chunk(ap, csize) )
  109.            {    alloc_print('+', '?', (ulong)0, size);
  110.             /* Things are desperate, but perhaps not hopeless. */
  111.             if ( (csize >>= 1) < block_size )
  112.                 return 0;    /* no hope */
  113.            }
  114.        }
  115.     if ( elt_size == 1 )
  116.        {    /* Unaligned block */
  117.         ap->ctop -= size;
  118.         alloc_print('+', '>', ap->ctop, size);
  119.         return (char *)ap->ctop;
  120.        }
  121.     else
  122.        {    /* Aligned block */
  123.         char *block = (char *)ap->cbot;
  124.         ap->cbot += block_size;
  125.         alloc_print('+', '<', block, size);
  126.         return block;
  127.        }
  128. }
  129.  
  130. /* Free an object, if possible. */
  131. /* Note that if a save is in effect, objects in chunks older than */
  132. /* the save, and objects allocated with malloc before the save, */
  133. /* must not be freed. */
  134. void
  135. alloc_free(char *cobj, uint num_elts, uint elt_size, const char *client_name)
  136. {    register alloc_state_ptr ap = alloc_state_current;
  137.     uint size = num_elts * elt_size;
  138.     uint block_size;
  139.     if ( size >= ap->big_size )
  140.        {    /* Object was allocated with malloc. */
  141.         alloc_free_large(cobj, size, client_name);
  142.         return;
  143.        }
  144. #define obj ((byte *)cobj)
  145.     if ( obj == ap->ctop )
  146.        {    /* Don't free the object if we're in a save and */
  147.         /* this object wasn't allocated since the save. */
  148.         if ( ap->current.save_level == ap->save_level ||
  149.              /* We know the current chunk is the same as */
  150.              /* the one in as->saved->state */
  151.              obj < ap->saved_ctop
  152.            )
  153.             ap->ctop += size;
  154.         alloc_print('-', '>', obj, size);
  155.         return;
  156.        }
  157.     else if ( obj + (block_size = align_round(size)) == ap->cbot )
  158.        {    /* Freeing an aligned object.  Same check. */
  159.         if ( ap->current.save_level == ap->save_level ||
  160.              obj >= ap->saved_cbot
  161.            )
  162.             ap->cbot = obj;
  163.         alloc_print('-', '<', obj, size);
  164.         return;
  165.        }
  166.     else if ( !ptr_is_in_chunk(obj, &ap->current) )
  167.        {    /* In another chunk, check its save level. */
  168.         /* We rely on the chunk list being ordered */
  169.         /* by decreasing save level. */
  170.         int level = ap->save_level;
  171.         alloc_chunk *cp = ap->last_freed;
  172.         if ( cp != 0 && ptr_is_in_chunk(obj, cp) )  /* cache hit */
  173.          { if ptr_lt(obj, cp->bot) goto pxf;
  174.            else goto pnf;
  175.          }
  176.         for ( cp = ap->current.next; cp != 0; cp = cp->next )
  177.          { if ( cp->save_level == level )
  178.              { if ( ptr_is_in_chunk(obj, cp) )
  179.              { if ( ptr_lt(obj, cp->bot) ) goto pbf;
  180.                /* Unaligned, not freeable. */
  181.                alloc_print('-', '~', obj, size);
  182.                goto pnf;
  183.              }
  184.              }
  185.            else
  186.              { /* This is the chunk that straddles the save. */
  187.                /* Check whether the object being freed */
  188.                /* was allocated since the save. */
  189.                if ( ptr_between(obj, ap->saved_cbot, cp->bot) )
  190.              goto pxf;
  191.                goto pnf;
  192.              }
  193.          }
  194. pnf:        /* Older save level, not freeable. */
  195.         alloc_print('-', '\\', obj, size);
  196.         return;
  197. pbf:        /* If we get here, OK to put the block on a free list. */
  198.         ap->last_freed = cp;
  199. pxf:        ;
  200.        }
  201.     else if ( obj >= ap->cbot )    /* not aligned object, punt */
  202.        {    alloc_print('-', '~', obj, size);
  203.         return;
  204.        }
  205.     else if ( ap->current.save_level < ap->save_level &&
  206.           obj < ap->saved_cbot
  207.         )
  208.     {    /* Current chunk straddles the current save, and */
  209.         /* object is older than the current save. */
  210.         /* (Same check as above.) */
  211.         alloc_print('-', '!', obj, size);
  212.         return;
  213.     }
  214.     /* Put on a free list if small enough */
  215.     alloc_print('-', '#', obj, size);
  216.     if ( block_size <= max_chain_size && block_size >= sizeof(char **) )
  217.        {    char **fptr = &ap->free[block_size >> log2_align_mod];
  218.         *(char **)cobj = *fptr;
  219.         *fptr = cobj;
  220.        }
  221. #undef obj
  222. }
  223.  
  224. /* Grow an object.  This may require allocating a new copy. */
  225. /* Return 0 if not enough room. */
  226. /****** Note: the object must have been allocated at
  227.  ****** the current save level. */
  228. byte *
  229. alloc_grow(byte *obj, uint old_num, uint new_num, uint elt_size,
  230.   const char *client_name)
  231. {    register alloc_state_ptr ap = alloc_state_current;
  232.     uint old_size = old_num * elt_size;
  233.     uint new_size = new_num * elt_size;
  234.     byte *nobj;
  235.     if ( new_size == old_size ) return obj;
  236.     if ( new_size < ap->big_size ) /* try to grow in place */
  237.       { uint old_block_size;
  238.         uint new_block_size;
  239.         if ( obj == ap->ctop )
  240.           { /* Might be able to grow in place */
  241.         uint diff = new_size - old_size;
  242.         if ( diff <= ap->ctop - ap->cbot )
  243.           { alloc_print('>', '>', obj, new_size);
  244.             ap->ctop -= diff;
  245.             memcpy(ap->ctop, obj, old_size);
  246.             return ap->ctop;
  247.           }
  248.           }
  249.         old_block_size = align_round(old_size);
  250.         new_block_size = align_round(new_size);
  251.         if ( obj + old_block_size == ap->cbot )
  252.           { /* Might be able to grow in place */
  253.         uint diff = new_block_size - old_block_size;
  254.         if ( diff <= ap->ctop - ap->cbot )
  255.           { alloc_print('>', '<', obj, new_size);
  256.             ap->cbot += diff;
  257.             return obj;
  258.           }
  259.           }
  260.       }
  261.     /* Can't grow in place.  Allocate a new object and copy. */
  262.     nobj = (byte *)alloc(new_num, elt_size, client_name);
  263.     if ( nobj == 0 )
  264.         return 0;
  265.     memcpy(nobj, obj, old_size);
  266.     alloc_free((char *)obj, old_num, elt_size, client_name);
  267.     alloc_print('>', '&', obj, new_size);
  268.     return nobj;
  269. }
  270.  
  271. /* Shrink an object. */
  272. /****** Note: the object must have been allocated at
  273.  ****** the current save level. */
  274. byte *
  275. alloc_shrink(byte *obj, uint old_num, uint new_num, uint elt_size,
  276.   const char *client_name)
  277. {    register alloc_state_ptr ap = alloc_state_current;
  278.     uint old_size = old_num * elt_size;
  279.     uint new_size = new_num * elt_size;
  280.     if ( new_size == old_size ) return obj;
  281.     if ( old_size >= ap->big_size )
  282.       { /* Allocate a new block. */
  283.         byte *nobj = (byte *)alloc(new_num, elt_size, client_name);
  284.         if ( nobj == 0 ) return obj; /* can't shrink, leave as is */
  285.         memcpy(nobj, obj, new_size);
  286.         alloc_free((char *)obj, old_num, elt_size, client_name);
  287.         alloc_print('<', '&', obj, new_size);
  288.         return nobj;
  289.       }
  290.     else if ( obj == ap->ctop )
  291.       { /* Move the object up in place. */
  292.         /* memcpy doesn't do this properly. */
  293.         register byte *from = obj + new_size;
  294.         register byte *to = obj + old_size;
  295.         while ( from > obj ) *--to = *--from;
  296.         obj = ap->ctop = to;
  297.       }
  298.     else
  299.       { uint new_block_size = align_round(new_size);
  300.         alloc_free((char *)(obj + new_block_size),
  301.                1, align_round(old_size) - new_block_size,
  302.                "alloc_shrink");
  303.       }
  304.     alloc_print('<', ' ', obj, new_size);
  305.     return obj;
  306. }
  307.  
  308. /* ------ Private routines ------ */
  309.  
  310. /* Allocate (with malloc) an object too large to be put in a chunk. */
  311. /* Return NULL on failure. */
  312. private char *
  313. alloc_large(alloc_state_ptr ap, uint size, const char *client_name)
  314. {    alloc_block *mblock = (alloc_block *)
  315.         (*ap->palloc)(1, alloc_block_size + size, client_name);
  316.     char *block;
  317.     if ( mblock == NULL ) return NULL;
  318.     block = (char *)mblock + alloc_block_size;
  319.        alloc_print_large('+', '*', block, size);
  320.     mblock->next = ap->malloc_chain;
  321.     mblock->size = size;
  322.     mblock->save_level = ap->save_level;
  323.     mblock->cap = ap;
  324.     ap->malloc_chain = mblock;
  325.     ap->used += size;
  326.     ap->total += size;
  327.     return block;
  328. }
  329.  
  330. /* Allocate a new chunk.  Return true if successful. */
  331. #define chunk_head_size align_round(sizeof(alloc_chunk))
  332. private int
  333. alloc_add_chunk(register alloc_state_ptr ap, uint csize)
  334. {    char *space =
  335.         (*ap->palloc)(1, chunk_head_size + csize, "alloc chunk");
  336.     long discard;
  337.     if ( space == NULL )
  338.         return 0;
  339.     ap->num_chunks++;
  340.     /* Accumulate statistics */
  341.     ap->total += csize;
  342.     alloc_status(&ap->used, &discard);
  343.     /* Stash the state of the old chunk */
  344.     if ( ap->current_ptr != 0 )    /* check for very first chunk */
  345.         *ap->current_ptr = ap->current;
  346.     /* Initialize the new chunk */
  347.     ap->cbase = ap->cbot = (byte *)space + chunk_head_size;
  348.     ap->climit = ap->ctop = ap->cbot + csize;
  349.     ap->current.next = ap->current_ptr;
  350.     ap->current.save_level = ap->save_level;
  351.     ap->current_ptr = (alloc_chunk *)space;
  352.     return 1;
  353. }
  354. #undef chunk_head_size
  355.  
  356. /* Free a large object (allocated with malloc). */
  357. private void
  358. alloc_free_large(char *cobj, uint size, const char *client_name)
  359. {    alloc_block **prev;
  360.     alloc_block *mblock = (alloc_block *)(cobj - alloc_block_size);
  361.     alloc_state_ptr ap = mblock->cap;
  362.     if ( mblock->save_level == ap->save_level )
  363.      for ( prev = &ap->malloc_chain; *prev != 0; prev = &mblock->next )
  364.        {    mblock = *prev;
  365.         if ( (char *)mblock + alloc_block_size == cobj )
  366.            {    *prev = mblock->next;
  367.             ap->used -= size;
  368.             ap->total -= size;
  369.             (*ap->pfree)((char *)mblock,
  370.                     1, size + alloc_block_size,
  371.                     "large object");
  372.             alloc_print_large('-', '*', cobj, size);
  373.             return;
  374.            }
  375.        }
  376.     alloc_print('-', '?', cobj, size);
  377. }
  378.