home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / GC_HDRS.H < prev    next >
C/C++ Source or Header  |  1994-07-14  |  5KB  |  134 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, July 14, 1994 12:49 pm PDT */
  15. # ifndef GC_HEADERS_H
  16. # define GC_HEADERS_H
  17. typedef struct hblkhdr hdr;
  18.  
  19. # if CPP_WORDSZ != 32 && CPP_WORDSZ < 36
  20.     --> Get a real machine.
  21. # endif
  22.  
  23. /*
  24.  * The 2 level tree data structure that is used to find block headers.
  25.  * If there are more than 32 bits in a pointer, the top level is a hash
  26.  * table.
  27.  */
  28.  
  29. # if CPP_WORDSZ > 32
  30. #   define HASH_TL
  31. # endif
  32.  
  33. /* Define appropriate out-degrees for each of the two tree levels    */
  34. # ifdef SMALL_CONFIG
  35. #   define LOG_BOTTOM_SZ 11
  36.     /* Keep top index size reasonable with smaller blocks. */
  37. # else
  38. #   define LOG_BOTTOM_SZ 10
  39. # endif
  40. # ifndef HASH_TL
  41. #   define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
  42. # else
  43. #   define LOG_TOP_SZ 11
  44. # endif
  45. # define TOP_SZ (1 << LOG_TOP_SZ)
  46. # define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
  47.  
  48. typedef struct bi {
  49.     hdr * index[BOTTOM_SZ];
  50.     /*
  51.       * The bottom level index contains one of three kinds of values:
  52.      * 0 means we're not responsible for this block.
  53.      * 1 < (long)X <= MAX_JUMP means the block starts at least
  54.      *        X * HBLKSIZE bytes before the current address.
  55.      * A valid pointer points to a hdr structure. (The above can't be
  56.      * valid pointers due to the GET_MEM return convention.)
  57.      */
  58.     struct bi * asc_link;    /* All indices are linked in    */
  59.                     /* ascending order.        */
  60.     word key;            /* high order address bits.    */
  61. # ifdef HASH_TL
  62.     struct bi * hash_link;    /* Hash chain link.        */
  63. # endif
  64. } bottom_index;
  65.  
  66. /* extern bottom_index GC_all_nils; - really part of GC_arrays */
  67.  
  68. /* extern bottom_index * GC_top_index []; - really part of GC_arrays */
  69.                 /* Each entry points to a bottom_index.    */
  70.                 /* On a 32 bit machine, it points to     */
  71.                 /* the index for a set of high order    */
  72.                 /* bits equal to the index.  For longer    */
  73.                 /* addresses, we hash the high order    */
  74.                 /* bits to compute the index in     */
  75.                 /* GC_top_index, and each entry points    */
  76.                 /* to a hash chain.            */
  77.                 /* The last entry in each chain is    */
  78.                 /* GC_all_nils.                */
  79.  
  80.  
  81. # define MAX_JUMP (HBLKSIZE - 1)
  82.  
  83. # ifndef HASH_TL
  84. #   define BI(p) (GC_top_index \
  85.         [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
  86. #   define HDR_INNER(p) (BI(p)->index \
  87.         [((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
  88. #   ifdef SMALL_CONFIG
  89. #    define HDR(p) GC_find_header((ptr_t)(p))
  90. #   else
  91. #    define HDR(p) HDR_INNER(p)
  92. #   endif
  93. #   define GET_BI(p, bottom_indx) (bottom_indx) = BI(p)
  94. #   define GET_HDR(p, hhdr) (hhdr) = HDR(p)
  95. #   define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr)
  96. #   define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p))
  97. # else /* hash */
  98. /*  Hash function for tree top level */
  99. #   define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
  100. /*  Set bottom_indx to point to the bottom index for address p */
  101. #   define GET_BI(p, bottom_indx) \
  102.     { \
  103.         register word hi = \
  104.             (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
  105.         register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \
  106.         \
  107.         while (_bi -> key != hi && _bi != GC_all_nils) \
  108.             _bi = _bi -> hash_link; \
  109.         (bottom_indx) = _bi; \
  110.     }
  111. #   define GET_HDR_ADDR(p, ha) \
  112.     { \
  113.         register bottom_index * bi; \
  114.         \
  115.         GET_BI(p, bi);    \
  116.         (ha) = &(bi->index[((unsigned long)(p)>>LOG_HBLKSIZE) \
  117.                       & (BOTTOM_SZ - 1)]); \
  118.     }
  119. #   define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
  120.                   (hhdr) = *_ha; }
  121. #   define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
  122.                   *_ha = (hhdr); }
  123. #   define HDR(p) GC_find_header((ptr_t)(p))
  124. # endif
  125.                 
  126. /* Is the result a forwarding address to someplace closer to the    */
  127. /* beginning of the block or NIL?                    */
  128. # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP)
  129.  
  130. /* Get an HBLKSIZE aligned address closer to the beginning of the block */
  131. /* h.  Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr).        */
  132. # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr))
  133. # endif /*  GC_HEADERS_H */
  134.