home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / pgmutl / val_link.arc / DICTARY.C < prev    next >
Text File  |  1989-02-18  |  12KB  |  277 lines
  1. /*                                 DICTARY.C                               */
  2.  
  3. /*
  4. There are several dictionaries which the linker maintains.  These
  5. dictionaries are used as:
  6.  
  7.     1)  A dictionary of public (internal and external) symbols.
  8.     2)  A dictionary of segments.
  9.     3)  A dictionary of group names.
  10.     4)  A dictionary of "LNAMES" and other names encountered in
  11.         an object module.
  12.  
  13. All the dictionaries have a similar data structure.
  14.  
  15. Since the dictionary uses a hashing scheme, two linked list are used
  16. as the principle dictionary data structure.  One linked list (based
  17. on the "next" field) is used to link elements together in the classical
  18. manner.  The other (based on the "next_congruent" field) is used to
  19. link congruent elements together.  (The hashing scheme divides the
  20. symbol table into partitions.  Elements which are in the same partition
  21. are said to be congruent with each other.)  The dictionary of "LNAMES"
  22. does not have the "next" link.
  23.  
  24. The second linked list forms a list of all symbols which are congruent
  25. modulo the hash table size.  In other words, all the symbols having the
  26. same remainder when you divide the sum of the characters forming the symbol
  27. by the hash table size are in the same list.  Graphically, here is what
  28. it looks like:
  29.  
  30.    hash_table
  31.    +--------+[0]
  32.    |        |
  33.    +--------+[1]
  34.    |        |
  35.    +--------+
  36.    ~        ~                       next next_congruent rest of entry
  37.    +--------+[i]                   +----+--------------+-----//------+
  38.    |   *----+--------------------->|    |      *       |             |
  39.    +--------+                      +----+------+-------+-----//------+
  40.    ~        ~                                  |
  41.    +--------+[HASH_TABLE_SIZE-1]               V
  42.    |        |                      +----+--------------+-----//------+
  43.    +--------+                      |    |      *       |             |
  44.                                    +----+------+-------+-----//------+
  45.                                                |
  46. Note:  The "next" field in the                 ~
  47.        list is the classical                   |
  48.        linking.  It is not                     V
  49.        mapped out here.            +----+--------------+-----//------+
  50.                                    |    |      *       |             |
  51.                                    +----+------+-------+-----//------+
  52.                                                |
  53.                                              -----
  54.                                               ---
  55.                                                -
  56.  
  57. In addition to using a standard hash table for improving symbol table
  58. lookup performance, a additional heuristic algorithm is added.  When a
  59. lookup is performed for a symbol, that symbol is moved to the beginning
  60. of the list of symbols in that congruency.  In this manner, symbols used
  61. frequently will remain close to the beginning of the list and thereby
  62. reduce searching time. */
  63.  
  64. /*+-------------------------------------------------------------------------+
  65.   |                                                                         |
  66.   |                              lookup_group                               |
  67.   |                                                                         |
  68.   +-------------------------------------------------------------------------+*/
  69. group_entry_ptr lookup_group(lname_entry_ptr  group_lname)
  70. BeginDeclarations
  71. #define Group_lname                    (*group_lname)
  72. bit_16                                 hash_val;
  73. group_entry_ptr                        group_entry;
  74. #define Group_entry                    (*group_entry)
  75. group_entry_ptr                        prior;
  76. #define Prior                          (*prior)
  77. EndDeclarations
  78. BeginCode
  79.  hash_val    = Group_lname.lname_checksum Mod group_table_hash_size.val;
  80.  group_entry = group_hash_table[hash_val];
  81.  prior       = Null;
  82.  While group_entry IsNotNull
  83.   BeginWhile
  84.    If group_lname Is Group_entry.group_name
  85.     Then
  86.      If prior IsNotNull
  87.       Then  /* Move group to beginning of list */
  88.        Prior.next_congruent       = Group_entry.next_congruent;
  89.        Group_entry.next_congruent = group_hash_table[hash_val];
  90.        group_hash_table[hash_val] = group_entry;
  91.       EndIf;
  92.      return(group_entry);
  93.     EndIf;
  94.    prior       = group_entry;
  95.    group_entry = Group_entry.next_congruent;
  96.   EndWhile;
  97.  group_entry = (group_entry_ptr)
  98.                 allocate_memory(Addr(static_pool),
  99.                                 Bit_32(sizeof(group_entry_type)));
  100.  Insert group_entry AtEnd InList group_list EndInsert;
  101.  Group_entry.group_name     = group_lname;
  102.  Group_entry.next_congruent = group_hash_table[hash_val];
  103.  group_hash_table[hash_val] = group_entry;
  104.  Group_entry.first_segment  = Null;
  105.  return(group_entry);
  106. EndCode
  107. #undef Group_lname
  108. #undef Group_entry
  109. #undef Prior
  110.  
  111. /*+-------------------------------------------------------------------------+
  112.   |                                                                         |
  113.   |                              lookup_lname                               |
  114.   |                                                                         |
  115.   +-------------------------------------------------------------------------+*/
  116. lname_entry_ptr lookup_lname(bit_16 len, byte *sym)
  117. BeginDeclarations
  118. bit_16                                 charsum;
  119. bit_16                                 hash_val;
  120. lname_entry_ptr                        lname_entry;
  121. #define Lname_entry                    (*lname_entry)
  122. lname_entry_ptr                        prior;
  123. #define Prior                          (*prior)
  124. EndDeclarations
  125. BeginCode
  126.  charsum     = checksum(len, sym);
  127.  hash_val    = charsum Mod lname_table_hash_size.val;
  128.  lname_entry = lname_hash_table[hash_val];
  129.  prior       = Null;
  130.  While lname_entry IsNotNull
  131.   BeginWhile
  132.    If len Is Lname_entry.length
  133.     Then
  134.      If far_compare(sym, Lname_entry.symbol, len) IsZero
  135.       Then
  136.        If prior IsNotNull
  137.         Then  /* Move lname to beginning of list */
  138.          Prior.next_congruent       = Lname_entry.next_congruent;
  139.          Lname_entry.next_congruent = lname_hash_table[hash_val];
  140.          lname_hash_table[hash_val] = lname_entry;
  141.         EndIf;
  142.        return(lname_entry);
  143.       EndIf;
  144.     EndIf;
  145.    prior       = lname_entry;
  146.    lname_entry = Lname_entry.next_congruent;
  147.   EndWhile;
  148.  lname_entry = (lname_entry_ptr)
  149.                 allocate_memory(Addr(static_pool),
  150.                                 Bit_32(sizeof(lname_entry_type))+Bit_32(len));
  151.  Lname_entry.lname_checksum = charsum;
  152.  Lname_entry.length         = len;
  153.  far_move(Lname_entry.symbol, sym, len);
  154.  Lname_entry.symbol[len]    = '\000';
  155.  Lname_entry.next_congruent = lname_hash_table[hash_val];
  156.  lname_hash_table[hash_val] = lname_entry;
  157.  return(lname_entry);
  158. EndCode
  159. #undef Lname_entry
  160. #undef Prior
  161.  
  162. /*+-------------------------------------------------------------------------+
  163.   |                                                                         |
  164.   |                             lookup_public                               |
  165.   |                                                                         |
  166.   +-------------------------------------------------------------------------+*/
  167. public_entry_ptr lookup_public(bit_16 len, byte *sym, bit_16 module)
  168. BeginDeclarations
  169. bit_16                                 hash_val;
  170. public_entry_ptr                       pub_entry;
  171. #define Pub_entry                      (*pub_entry)
  172. public_entry_ptr                       prior;
  173. #define Prior                          (*prior)
  174. EndDeclarations
  175. BeginCode
  176.  hash_val  = checksum(len, sym) Mod public_table_hash_size.val;
  177.  pub_entry = public_hash_table[hash_val];
  178.  prior     = Null;
  179.  While pub_entry IsNotNull
  180.   BeginWhile
  181.    If len Is Pub_entry.length
  182.     Then
  183.      If (far_compare(sym, Pub_entry.symbol, len) IsZero) AndIf
  184.         (module Is Pub_entry.module)
  185.       Then
  186.        If prior IsNotNull
  187.         Then  /* Move public to beginning of list */
  188.          Prior.next_congruent        = Pub_entry.next_congruent;
  189.          Pub_entry.next_congruent    = public_hash_table[hash_val];
  190.          public_hash_table[hash_val] = pub_entry;
  191.         EndIf;
  192.        return(pub_entry);
  193.       EndIf;
  194.     EndIf;
  195.    prior     = pub_entry;
  196.    pub_entry = Pub_entry.next_congruent;
  197.   EndWhile;
  198.  pub_entry = (public_entry_ptr)
  199.               allocate_memory(Addr(static_pool),
  200.                               Bit_32(sizeof(public_entry_type))+Bit_32(len));
  201.  Pub_entry.type_entry        = unused;
  202.  Pub_entry.module            = module;
  203.  Pub_entry.length            = len;
  204.  far_move(Pub_entry.symbol, sym, len);
  205.  Pub_entry.symbol[len]       = '\000';
  206.  Pub_entry.next_congruent    = public_hash_table[hash_val];
  207.  public_hash_table[hash_val] = pub_entry;
  208.  return(pub_entry);
  209. EndCode
  210. #undef Pub_entry
  211. #undef Prior
  212.  
  213. /*+-------------------------------------------------------------------------+
  214.   |                                                                         |
  215.   |                              lookup_segment                               |
  216.   |                                                                         |
  217.   +-------------------------------------------------------------------------+*/
  218. segment_entry_ptr lookup_segment(lname_entry_ptr  segment_lname,
  219.                                  lname_entry_ptr  class_lname,
  220.                                  combine_type     combine)
  221. BeginDeclarations
  222. #define Segment_lname                  (*segment_lname)
  223. #define Class_lname                    (*class_lname)
  224. bit_16                                 hash_val;
  225. segment_entry_ptr                      segment_entry;
  226. #define Segment_entry                  (*segment_entry)
  227. segment_entry_ptr                      prior;
  228. #define Prior                          (*prior)
  229. EndDeclarations
  230. BeginCode
  231.  hash_val      = (Segment_lname.lname_checksum +
  232.                   Class_lname.lname_checksum)
  233.                  Mod segment_table_hash_size.val;
  234.  segment_entry = segment_hash_table[hash_val];
  235.  If (combine IsNotZero) AndIf (combine IsNot blank_common_combine)
  236.   Then  /* All non-zero combine types except blank common will be combined. */
  237.    prior         = Null;
  238.    While segment_entry IsNotNull
  239.     BeginWhile
  240.      If (segment_lname       Is Segment_entry.segment_name) AndIf
  241.         (class_lname         Is Segment_entry.class_name)   AndIf
  242.         (combine             Is Segment_entry.combine)
  243.       Then
  244.        If prior IsNotNull
  245.         Then  /* Move segment to beginning of list */
  246.          Prior.next_congruent         = Segment_entry.next_congruent;
  247.          Segment_entry.next_congruent = segment_hash_table[hash_val];
  248.          segment_hash_table[hash_val] = segment_entry;
  249.         EndIf;
  250.        return(segment_entry);
  251.       EndIf;
  252.      prior       = segment_entry;
  253.      segment_entry = Segment_entry.next_congruent;
  254.     EndWhile;
  255.   EndIf;
  256.  segment_entry = (segment_entry_ptr)
  257.                 allocate_memory(Addr(static_pool),
  258.                                 Bit_32(sizeof(segment_entry_type)));
  259.  Insert segment_entry AtEnd InList segment_list EndInsert;
  260.  Segment_entry.segment_name   = segment_lname;
  261.  Segment_entry.class_name     = class_lname;
  262.  Segment_entry.combine        = Bit_8(combine);
  263.  Segment_entry.owning_group   = Null;
  264.  Segment_entry.lsegs.first    =
  265.  Segment_entry.lsegs.last     = Null;
  266.  Segment_entry.address        =
  267.  Segment_entry.length         = 0L;
  268.  Segment_entry.next_congruent = segment_hash_table[hash_val];
  269.  segment_hash_table[hash_val] = segment_entry;
  270.  return(segment_entry);
  271. EndCode
  272. #undef Segment_lname
  273. #undef Segment_class_lname
  274. #undef Segment_entry
  275. #undef Prior
  276.  
  277.