home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / src / !runtime / freelist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-18  |  7.4 KB  |  236 lines  |  [TEXT/R*ch]
  1. #include "config.h"
  2. #include "debugger.h"
  3. #include "freelist.h"
  4. #include "gc.h"
  5. #include "gc_ctrl.h"
  6. #include "major_gc.h"
  7. #include "misc.h"
  8. #include "mlvalues.h"
  9.  
  10. /* The free-list is kept sorted by increasing addresses.
  11.    This makes the merging of adjacent free blocks possible.
  12.    (See [fl_merge_block].)
  13. */
  14.  
  15. typedef struct {
  16.   char *next_bp;   /* Pointer to the first byte of the next block. */
  17. } block;
  18.  
  19. /* The sentinel can be located anywhere in memory, but it must not be
  20.    adjacent to any heap object. */
  21. static struct {
  22.   value filler1; /* Make sure the sentinel is never adjacent to any block. */
  23.   header_t h;
  24.   value first_bp;
  25.   value filler2; /* Make sure the sentinel is never adjacent to any block. */
  26. } sentinel = {0, Make_header (0, 0, Blue), (value)NULL, 0};
  27.  
  28. #define Fl_head ((char *) (&(sentinel.first_bp)))
  29. static char *fl_prev = Fl_head;  /* Current allocation pointer. */
  30. static char *fl_last = NULL;     /* Last block in the list.  Only valid
  31.                                     just after fl_allocate returned NULL. */
  32. char *fl_merge = Fl_head;        /* Current insertion pointer.  Managed
  33.                                     jointly with [sweep_slice]. */
  34.  
  35. #define Next(b) (((block *) (b))->next_bp)
  36.  
  37. #ifdef DEBUG
  38. void fl_verify ()
  39. {
  40.   char *cur, *prev;
  41.   int prev_found = 0, merge_found = 0;
  42.  
  43.   prev = Fl_head;
  44.   cur = Next (prev);
  45.   while (cur != NULL){
  46.     Assert (Is_in_heap (cur));
  47.     if (cur == fl_prev) prev_found = 1;
  48.     if (cur == fl_merge) merge_found = 1;
  49.     prev = cur;
  50.     cur = Next (prev);
  51.   }
  52.   Assert (prev_found || fl_prev == Fl_head);
  53.   Assert (merge_found || fl_merge == Fl_head);
  54. }
  55. #endif
  56.  
  57. /* [allocate_block] is called by [fl_allocate].  Given a suitable free
  58.    block and the desired size, it allocates a new block from the free
  59.    block.  There are three cases:
  60.    0. The free block has the desired size.  Detach the block from the
  61.       free-list and return it.
  62.    1. The free block is 1 word longer than the desired size.  Detach
  63.       the block from the free list.  The remaining word cannot be linked:
  64.       turn it into an empty block (header only), and return the rest.
  65.    2. The free block is big enough.  Split it in two and return the right
  66.       block.
  67.    In all cases, the allocated block is right-justified in the free block:
  68.    it is located in the high-address words of the free block.  This way,
  69.    the linking of the free-list does not change in case 2.
  70. */
  71. static char *allocate_block (wh_sz, prev, cur)
  72.     mlsize_t wh_sz;
  73.     char *prev, *cur;
  74. {
  75.   header_t h = Hd_bp (cur);
  76.                                              Assert (Whsize_hd (h) >= wh_sz);
  77.   if (Wosize_hd (h) < wh_sz + 1){                        /* Cases 0 and 1. */
  78.     Next (prev) = Next (cur);
  79.                     Assert (Is_in_heap (Next (prev)) || Next (prev) == NULL);
  80.     if (fl_merge == cur) fl_merge = prev;
  81. #ifdef DEBUG
  82.     fl_last = NULL;
  83. #endif
  84.       /* In case 1, the following creates the empty block correctly.
  85.          In case 0, it gives an invalid header to the block.  The function
  86.          calling [fl_allocate] will overwrite it. */
  87.     Hd_op (cur) = Make_header (0, 0, White);
  88.   }else{                                                        /* Case 2. */
  89.     Hd_op (cur) = Make_header (Wosize_hd (h) - wh_sz, 0, Blue);
  90.   }
  91.   fl_prev = prev;
  92.   return cur + Bosize_hd (h) - Bsize_wsize (wh_sz);
  93. }  
  94.  
  95. /* [fl_allocate] does not set the header of the newly allocated block.
  96.    The calling function must do it before any GC function gets called.
  97.    [fl_allocate] returns a head pointer.
  98. */
  99. char *fl_allocate (wo_sz)
  100.      mlsize_t wo_sz;
  101. {
  102.   char *cur, *prev;
  103.                                   Assert (sizeof (char *) == sizeof (value));
  104.                                   Assert (fl_prev != NULL);
  105.                                   Assert (wo_sz >= 1);
  106.     /* Search from [fl_prev] to the end of the list. */
  107.   prev = fl_prev;
  108.   cur = Next (prev);
  109.   while (cur != NULL){                             Assert (Is_in_heap (cur));
  110.     if (Wosize_bp (cur) >= wo_sz){
  111.       return allocate_block (Whsize_wosize (wo_sz), prev, cur);
  112.     }
  113.     prev = cur;
  114.     cur = Next (prev);
  115.   }
  116.   fl_last = prev;
  117.     /* Search from the start of the list to [fl_prev]. */
  118.   prev = Fl_head;
  119.   cur = Next (prev);
  120.   while (prev != fl_prev){
  121.     if (Wosize_bp (cur) >= wo_sz){
  122.       return allocate_block (Whsize_wosize (wo_sz), prev, cur);
  123.     }
  124.     prev = cur;
  125.     cur = Next (prev);
  126.   }
  127.     /* No suitable block was found. */
  128.   return NULL;
  129. }
  130.  
  131. void fl_init_merge ()
  132. {
  133.   fl_merge = Fl_head;
  134. }
  135.  
  136. /* [fl_merge_block] returns the head pointer of the next block after [bp],
  137.    because merging blocks may change the size of [bp]. */
  138. char *fl_merge_block (bp)
  139.     char *bp;
  140. {
  141.   char *prev, *cur, *adj;
  142.   header_t hd = Hd_bp (bp);
  143.   
  144. #ifdef DEBUG
  145.   {
  146.     mlsize_t i;
  147.     for (i = 0; i < Wosize_hd (hd); i++){
  148.       Field (Val_bp (bp), i) = not_random ();
  149.     }
  150.   }
  151. #endif
  152.   prev = fl_merge;
  153.   cur = Next (prev);
  154.     /* The sweep code makes sure that this is the right place to insert
  155.        this block: */
  156.     Assert (prev < bp || prev == Fl_head);
  157.     Assert (cur > bp || cur == NULL);
  158.  
  159.     /* If [bp] and [cur] are adjacent, remove [cur] from the free-list
  160.        and merge them. */
  161.   adj = bp + Bosize_hd (hd);
  162.   if (adj == Hp_bp (cur)){
  163.     char *next_cur = Next (cur);
  164.     long cur_whsz = Whsize_bp (cur);
  165.  
  166.     Next (prev) = next_cur;
  167.     if (fl_prev == cur) fl_prev = prev;
  168.     hd = Make_header (Wosize_hd (hd) + cur_whsz, 0, Blue);
  169.     Hd_bp (bp) = hd;
  170.     adj = bp + Bosize_hd (hd);
  171. #ifdef DEBUG
  172.     fl_last = NULL;
  173.     Next (cur) = (char *) not_random ();
  174.     Hd_bp (cur) = not_random ();
  175. #endif
  176.     cur = next_cur;
  177.   }
  178.     /* If [prev] and [bp] are adjacent merge them, else insert [bp] into
  179.        the free-list if it is big enough. */
  180.   if (prev + Bosize_bp (prev) == Hp_bp (bp)){
  181.     Hd_bp (prev) = Make_header (Wosize_bp (prev) + Whsize_hd (hd), 0, Blue);
  182. #ifdef DEBUG
  183.     Hd_bp (bp) = not_random ();
  184. #endif
  185.     Assert (fl_merge == prev);
  186.   }else if (Wosize_hd (hd) > 0){
  187.     Hd_bp (bp) = Bluehd_hd (hd);
  188.     Next (bp) = cur;
  189.     Next (prev) = bp;
  190.     fl_merge = bp;
  191.   } /* Else leave it in white. */
  192.   return adj;
  193. }
  194.  
  195. /* This is a heap extension.  We have to insert it in the right place
  196.    in the free-list.
  197.    [fl_add_block] can only be called just after a call to [fl_allocate]
  198.    that returned NULL.
  199.    Most of the heap extensions are expected to be at the end of the
  200.    free list.  (This depends on the implementation of [malloc].)
  201. */
  202. void fl_add_block (bp)
  203.      char *bp;
  204. {
  205.                                                    Assert (fl_last != NULL);
  206.                                             Assert (Next (fl_last) == NULL);
  207. #ifdef DEBUG
  208.   {
  209.     mlsize_t i;
  210.     for (i = 0; i < Wosize_bp (bp); i++){
  211.       Field (Val_bp (bp), i) = not_random ();
  212.     }
  213.   }
  214. #endif
  215.   if (bp > fl_last){
  216.     Next (fl_last) = bp;
  217.     Next (bp) = NULL;
  218.   }else{
  219.     char *cur, *prev;
  220.  
  221.     prev = Fl_head;
  222.     cur = Next (prev);
  223.     while (cur != NULL && cur < bp){   Assert (prev < bp || prev == Fl_head);
  224.       prev = cur;
  225.       cur = Next (prev);
  226.     }                                  Assert (prev < bp || prev == Fl_head);
  227.                                             Assert (cur > bp || cur == NULL);
  228.     Next (bp) = cur;
  229.     Next (prev) = bp;
  230.     /* When inserting a block between fl_merge and gc_sweep_hp, we must
  231.        advance fl_merge to the new block, so that fl_merge is always the
  232.        last free-list block before gc_sweep_hp. */
  233.     if (prev == fl_merge && bp <= gc_sweep_hp) fl_merge = bp;
  234.   }
  235. }
  236.