home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 541b.lha / OakLisp / src.lzh / weak.c < prev    next >
C/C++ Source or Header  |  1991-06-15  |  4KB  |  216 lines
  1. /*  Copyright (C) 1987, 1988 Barak Pearlmutter and Kevin Lang    */
  2.  
  3. /* This file has weak pointers in it. */
  4.  
  5. #include <stdio.h>
  6. #include "emulator.h"
  7. #include "gc.h"
  8.  
  9.  
  10. #ifdef PROTOTYPES
  11. extern void        init_wp(void);        
  12. extern void        enter_wp(ref r, ref wp);        
  13. extern void        rebuild_wp_hashtable(void);        
  14. extern ref        ref_to_wp(ref r);        
  15. extern void        wp_hashtable_distribution(void);        
  16. extern unsigned long    post_gc_wp(void);        
  17. #endif
  18.  
  19.  
  20. /*
  21.  * Weak pointers are done with a simple table that goes from weak
  22.  * pointers to objects, and a hash table that goes from objects to
  23.  * their weak pointers.
  24.  
  25.  * In the future, this will be modified to keep separate hash tables
  26.  * for the different areas, so that objects in spatic space need not
  27.  * be rehashed.
  28.  
  29.  * Plus another one for immediates and fixnums, which don't live in
  30.  * any space at all.
  31.  
  32.  */
  33.  
  34. #define WP_TABLE_SIZE 10000L
  35.  
  36. #ifdef MALLOC_WP_TABLE
  37. ref *wp_table;
  38. #else
  39. ref wp_table[WP_TABLE_SIZE+1];
  40. #endif
  41.  
  42. long wp_index = 0;
  43.  
  44.  
  45. /* A hash table from references to their weak pointers.  This hash
  46.  * table is not saved in dumped worlds, and is rebuilt from scratch
  47.  * after each GC and upon booting a new world.
  48.  
  49.  * Structure of this hash table:
  50.  
  51.  * Keys are references themselves, smashed about and xored if deemed
  52.  * necessary.
  53.  
  54.  * Sequential rehash, single probe.
  55.  */
  56.  
  57. #define WP_HASHTABLE_SIZE 10007L    /* Good idea for this to be prime. */
  58.  
  59. typedef struct
  60. {
  61.   ref obj, wp;
  62. } wp_hashtable_entry;
  63.  
  64. #ifdef MALLOC_WP_TABLE
  65. wp_hashtable_entry *wp_hashtable;
  66. #else
  67. wp_hashtable_entry wp_hashtable[WP_HASHTABLE_SIZE];
  68. #endif
  69.  
  70.  
  71. /* The following magic number is floor( 2^32 * (sqrt(5)-1)/2 ). */
  72. #define wp_key(r) ((unsigned long) 0x9E3779BB*(r)) /* >>10, == 2654435771L */
  73.  
  74. void init_wp()
  75. {
  76. #ifdef MALLOC_WP_TABLE
  77.   wp_table = (ref *)my_malloc((long)(sizeof(ref) * WP_TABLE_SIZE));
  78.   wp_hashtable = (wp_hashtable_entry *)
  79.     my_malloc((long)(sizeof(wp_hashtable_entry) * WP_HASHTABLE_SIZE));
  80. #endif
  81. }
  82.  
  83.  
  84. /* Register r as having weak pointer wp. */
  85. void enter_wp(r, wp)
  86.      ref r, wp;
  87. {
  88.   unsigned long i = wp_key(r) % WP_HASHTABLE_SIZE;
  89.  
  90.   while (TRUE)
  91.     if (wp_hashtable[i].obj == e_nil)
  92.       {
  93.     wp_hashtable[i].obj = r;
  94.     wp_hashtable[i].wp = wp;
  95.     return;
  96.       }
  97.     else if (++i == WP_HASHTABLE_SIZE)
  98.       i = 0;
  99. }
  100.  
  101.  
  102.  
  103.  
  104. /* Rebuild the weak pointer hash table from the information in the table
  105.    that takes weak pointers to objects. */
  106. void rebuild_wp_hashtable()
  107. {
  108.   unsigned long i;
  109.   
  110.   for (i=0; i<WP_HASHTABLE_SIZE; i++)
  111.     wp_hashtable[i].obj = e_nil;
  112.  
  113.   for (i = 0; i<wp_index; i++)
  114.     if (wp_table[1+i] != e_nil)
  115.       enter_wp(wp_table[1+i], INT_TO_REF(i));
  116. }
  117.  
  118.  
  119.  
  120.  
  121.  
  122. /* Return weak pointer associated with obj, making a new one if necessary. */
  123.  
  124. ref ref_to_wp(r)
  125.      ref r;
  126. {
  127.   unsigned long i = wp_key(r) % WP_HASHTABLE_SIZE;
  128.  
  129.   if (r == e_nil) return INT_TO_REF(-1);
  130.  
  131.   while (TRUE)
  132.     {
  133.       if (wp_hashtable[i].obj == r)
  134.     return wp_hashtable[i].wp;
  135.       else if (wp_hashtable[i].obj == e_nil)
  136.     {
  137.       /* Make a new weak pointer, installing it in both tables: */
  138.       wp_hashtable[i].obj = wp_table[1+wp_index] = r;
  139.       return wp_hashtable[i].wp = INT_TO_REF(wp_index++);
  140.     }
  141.       else if (++i == WP_HASHTABLE_SIZE)
  142.     i = 0;
  143.     }
  144. }
  145.  
  146.  
  147.  
  148. void wp_hashtable_distribution()
  149. {
  150.   unsigned long i;
  151.  
  152.   for (i=0; i<WP_HASHTABLE_SIZE; i++)
  153.     {
  154.       ref r = wp_hashtable[i].obj;
  155.       
  156.       if (r == e_nil)
  157.     (void)putchar('.');
  158.       else 
  159.     {
  160.       unsigned long j = wp_key(r) % WP_HASHTABLE_SIZE;
  161.       long dist = i-j;
  162.  
  163.       if (dist < 0) dist += WP_HASHTABLE_SIZE;
  164.  
  165.       if (dist < 1+'9'-'0')
  166.         (void)putchar((char)('0'+dist));
  167.       else if (dist < 1+'Z'-'A' + 1+'9'-'0')
  168.         (void)putchar((char)('A' + dist - (1+'9'-'0')));
  169.       else
  170.         (void)putchar('*');
  171.     }
  172.  
  173.       fflush_stdout();
  174.     }
  175. }
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182. unsigned long post_gc_wp()
  183. {
  184.   /* Scan the weak pointer table.  When a reference to old space is found,
  185.      check if the location has a forwarding pointer.  If not, discard the
  186.      reference; if so, update it. */
  187.   long i;
  188.   unsigned long discard_count = 0;
  189.  
  190.   for (i=0; i<wp_index; i++)
  191.     {
  192.       ref r = wp_table[1+i], *p;
  193.  
  194.       if ( (r&PTR_MASK) && (p = ANY_TO_PTR(r), OLD_PTR(p)) )
  195.     {
  196.       ref r1 = *p;
  197.  
  198.       if (TAG_IS(r1,LOC_TAG) && NEW_PTR(LOC_TO_PTR(r1)))
  199.         {
  200.           wp_table[1+i] = TAG_IS(r,LOC_TAG) ? r1 : r1|PTR_TAG;
  201.         }
  202.       else
  203.         {
  204.           wp_table[1+i] = e_nil;
  205.           discard_count += 1;
  206.         }
  207.     }
  208.     }
  209.  
  210.   rebuild_wp_hashtable();
  211.  
  212.   return discard_count;
  213. }
  214.  
  215.  
  216.