home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / users / Harry / Blitz / version-1-0 / BlitzSrc / kpl / mapping.cc < prev    next >
C/C++ Source or Header  |  2006-09-25  |  28KB  |  1,014 lines
  1. // mapping.cc  --  Driver routine for the compiler; basic control routines
  2. //
  3. // KPL Compiler
  4. //
  5. // Copyright 2002-2006, Harry H. Porter III
  6. //
  7. // This file may be freely copied, modified and compiled, on the sole
  8. // condition that if you modify it...
  9. //   (1) Your name and the date of modification is added to this comment
  10. //       under "Modifications by", and
  11. //   (2) Your name and the date of modification is added to the printHelp()
  12. //       routine in file "main.cc" under "Modifications by".
  13. //
  14. // Original Author:
  15. //   07/30/02 - Harry H. Porter III
  16. //
  17. // Modifcations by:
  18. //   03/15/06 - Harry H. Porter III
  19. //
  20. //
  21.  
  22. #include "main.h"
  23.  
  24.  
  25.  
  26.  
  27. // instantiateMappings ()
  28. //
  29. // This routine is never called.  The purpose of it is to force the C++
  30. // compiler to generate code for the various methods that are needed.
  31. //
  32. void instantiateMappings () {
  33.   Mapping <String, Header>      * dummyMap1;
  34.   Mapping <String, String>      * dummyMap2;
  35.   Mapping <String, TypeParm>    * dummyMap3;
  36.   Mapping <TypeParm, Type>      * dummyMap4;
  37.   Mapping <String, MethodProto> * dummyMap5;
  38.   Mapping <String, Method>      * dummyMap6;
  39.   Mapping <String, RecordField> * dummyMap7;
  40.   Mapping <String, ErrorDecl>   * dummyMap8;
  41.   Mapping <Abstract, Abstract>  * dummyMap9;
  42.   Mapping <Offset, String>      * dummyMap10;
  43.   Mapping <String, Offset>      * dummyMap11;
  44.   Mapping <String, AstNode>     * dummyMap12;
  45.  
  46.   dummyMap1 = new Mapping <String, Header> (0, NULL);
  47.   dummyMap1->enter (NULL, NULL);
  48.   dummyMap1->find (NULL);
  49.   dummyMap1->findInTopScope (NULL);
  50.   dummyMap1->alreadyDefined (NULL);
  51.   dummyMap1->print (0);
  52.   dummyMap1->getFirst ();
  53.   dummyMap1->getNext ();
  54.   dummyMap1->getItsKey ();
  55.   delete dummyMap1;
  56.  
  57.   dummyMap2 = new Mapping <String, String> (0, NULL);
  58.   dummyMap2->enter (NULL, NULL);
  59.   dummyMap2->find (NULL);
  60.   dummyMap2->findInTopScope (NULL);
  61.   dummyMap2->alreadyDefined (NULL);
  62.   dummyMap2->print (0);
  63.   dummyMap2->getFirst ();
  64.   dummyMap2->getNext ();
  65.   dummyMap2->getItsKey ();
  66.   delete dummyMap2;
  67.  
  68.   dummyMap3 = new Mapping <String, TypeParm> (0, NULL);
  69.   dummyMap3->enter (NULL, NULL);
  70.   dummyMap3->find (NULL);
  71.   dummyMap3->findInTopScope (NULL);
  72.   dummyMap3->alreadyDefined (NULL);
  73.   dummyMap3->print (0);
  74.   dummyMap3->getFirst ();
  75.   dummyMap3->getNext ();
  76.   dummyMap3->getItsKey ();
  77.   delete dummyMap3;
  78.  
  79.   dummyMap4 = new Mapping <TypeParm, Type> (0, NULL);
  80.   dummyMap4->enter (NULL, NULL);
  81.   dummyMap4->find (NULL);
  82.   dummyMap4->findInTopScope (NULL);
  83.   dummyMap4->alreadyDefined (NULL);
  84.   dummyMap4->print (0);
  85.   dummyMap4->getFirst ();
  86.   dummyMap4->getNext ();
  87.   dummyMap4->getItsKey ();
  88.   delete dummyMap4;
  89.  
  90.   dummyMap5 = new Mapping <String, MethodProto> (0, NULL);
  91.   dummyMap5->enter (NULL, NULL);
  92.   dummyMap5->find (NULL);
  93.   dummyMap5->findInTopScope (NULL);
  94.   dummyMap5->alreadyDefined (NULL);
  95.   dummyMap5->print (0);
  96.   dummyMap5->getFirst ();
  97.   dummyMap5->getNext ();
  98.   dummyMap5->getItsKey ();
  99.   delete dummyMap5;
  100.  
  101.   dummyMap6 = new Mapping <String, Method> (0, NULL);
  102.   dummyMap6->enter (NULL, NULL);
  103.   dummyMap6->find (NULL);
  104.   dummyMap6->findInTopScope (NULL);
  105.   dummyMap6->alreadyDefined (NULL);
  106.   dummyMap6->print (0);
  107.   dummyMap6->getFirst ();
  108.   dummyMap6->getNext ();
  109.   dummyMap6->getItsKey ();
  110.   delete dummyMap6;
  111.  
  112.   dummyMap7 = new Mapping <String, RecordField> (0, NULL);
  113.   dummyMap7->enter (NULL, NULL);
  114.   dummyMap7->find (NULL);
  115.   dummyMap7->findInTopScope (NULL);
  116.   dummyMap7->alreadyDefined (NULL);
  117.   dummyMap7->print (0);
  118.   dummyMap7->getFirst ();
  119.   dummyMap7->getNext ();
  120.   dummyMap7->getItsKey ();
  121.   delete dummyMap7;
  122.  
  123.   dummyMap8 = new Mapping <String, ErrorDecl> (0, NULL);
  124.   dummyMap8->enter (NULL, NULL);
  125.   dummyMap8->find (NULL);
  126.   dummyMap8->findInTopScope (NULL);
  127.   dummyMap8->alreadyDefined (NULL);
  128.   dummyMap8->print (0);
  129.   dummyMap8->getFirst ();
  130.   dummyMap8->getNext ();
  131.   dummyMap8->getItsKey ();
  132.   delete dummyMap8;
  133.  
  134.   dummyMap9 = new Mapping <Abstract, Abstract> (0, NULL);
  135.   dummyMap9->enter (NULL, NULL);
  136.   dummyMap9->find (NULL);
  137.   dummyMap9->findInTopScope (NULL);
  138.   dummyMap9->alreadyDefined (NULL);
  139.   dummyMap9->print (0);
  140.   dummyMap9->getFirst ();
  141.   dummyMap9->getNext ();
  142.   dummyMap9->getItsKey ();
  143.   delete dummyMap9;
  144.  
  145.   dummyMap10 = new Mapping <Offset, String> (0, NULL);
  146.   dummyMap10->enter (NULL, NULL);
  147.   dummyMap10->find (NULL);
  148.   dummyMap10->findInTopScope (NULL);
  149.   dummyMap10->alreadyDefined (NULL);
  150.   dummyMap10->print (0);
  151.   dummyMap10->getFirst ();
  152.   dummyMap10->getNext ();
  153.   dummyMap10->getItsKey ();
  154.   dummyMap10->printOffsetToSelector ("Dummy");
  155.   delete dummyMap10;
  156.  
  157.   dummyMap11 = new Mapping <String, Offset> (0, NULL);
  158.   dummyMap11->enter (NULL, NULL);
  159.   dummyMap11->find (NULL);
  160.   dummyMap11->findInTopScope (NULL);
  161.   dummyMap11->alreadyDefined (NULL);
  162.   dummyMap11->print (0);
  163.   dummyMap11->getFirst ();
  164.   dummyMap11->getNext ();
  165.   dummyMap11->getItsKey ();
  166.   dummyMap11->printSelectorToOffset ();
  167.   delete dummyMap11;
  168.  
  169.   dummyMap12 = new Mapping <String, AstNode> (0, NULL);
  170.   dummyMap12->enter (NULL, NULL);
  171.   dummyMap12->find (NULL);
  172.   dummyMap12->findInTopScope (NULL);
  173.   dummyMap12->alreadyDefined (NULL);
  174.   dummyMap12->print (0);
  175.   dummyMap12->getFirst ();
  176.   dummyMap12->getNext ();
  177.   dummyMap12->getItsKey ();
  178.   dummyMap12->printSelectorToOffset ();
  179.   delete dummyMap12;
  180.  
  181. }
  182.  
  183.  
  184. //----------  Local to this file  ----------
  185.  
  186. void searchFor (String *);
  187. Mapping<String, AstNode> * testMap;
  188.  
  189.  
  190.  
  191. // enter (key, value)
  192. //
  193. // Enter this key-value pair in the top scope.
  194. //
  195. template <class Key, class Value>
  196. void Mapping<Key, Value> :: enter (Key * k, Value * v) {
  197.   Bucket<Key,Value> * newBuck = new Bucket<Key,Value> ();
  198.   int i;
  199.  
  200.   // printf ("Enter  ptr=0x%08x %d    i=%d\n", k, k, arrayIndex (k));
  201.  
  202.   rehashIfNecessary ();
  203.   i = arrayIndex (k);
  204.   newBuck->key = k;
  205.   newBuck->value = v;
  206.   newBuck->next = array[i];
  207.   array[i] = newBuck;
  208.   numberOfElements++;
  209.   if (firstInsertedBucket == NULL) {
  210.     firstInsertedBucket = newBuck;
  211.     lastInsertedBucket = newBuck;
  212.   } else {
  213.     lastInsertedBucket->nextForIterator = newBuck;
  214.     lastInsertedBucket = newBuck;
  215.   }
  216.  
  217.   // printf ("ENTER  0x%08x: ", newBuck);
  218.   // printf ("   KEY=0x%08x", newBuck->key);
  219.   // printf ("   VAL=0x%08x", newBuck->value);
  220.   // printf ("   next=0x%08x", newBuck->next);
  221.   // printf ("   nextForIterator=0x%08x\n", newBuck->nextForIterator);
  222. }
  223.  
  224.  
  225.  
  226. // find (key) --> value
  227. //
  228. // Searches all scopes for the given key.  If found, return the
  229. // corresponding value.  If not found, return NULL.
  230. //
  231. template <class Key, class Value>
  232. Value * Mapping<Key, Value> :: find (Key * k) {
  233.   Bucket<Key,Value> * buck;
  234.   int i = arrayIndex (k);
  235.   buck = array[i];
  236.   while (buck != NULL) {
  237.     if (buck->key == k) return buck->value;
  238.     buck = buck->next;
  239.   }
  240.   if (superMap == NULL) return NULL;
  241.   return superMap->find (k);
  242. }
  243.  
  244.  
  245.  
  246. // alreadyDefined (key) --> bool
  247. //
  248. // Determine if an entry for this key exists.
  249. // Search the top scope only.
  250. //
  251. template <class Key, class Value>
  252. int Mapping<Key, Value> :: alreadyDefined (Key * k) {
  253.   Bucket<Key,Value> * buck;
  254.   int i = arrayIndex (k);
  255.   buck = array[i];
  256.   while (buck != NULL) {
  257.     if (buck->key == k) return 1;
  258.     buck = buck->next;
  259.   }
  260.   return 0;
  261. }
  262.  
  263.  
  264.  
  265. // print (indent)
  266. //
  267. // Print all scopes.
  268. //
  269. template <class Key, class Value>
  270. void Mapping<Key, Value> :: print (int indent) {
  271.   int i;
  272.   Bucket<Key, Value> * p;
  273.   String * str;
  274.   IntConst * val;
  275.   Key * key;
  276.   Value * value;
  277.   ppIndent (indent);
  278.   printf ("==========  Mapping  ==========\n");
  279.  
  280. /***
  281.   printf ("  superMap = 0x%08x\n", superMap);
  282.   printf ("  numberOfElements = %d\n", numberOfElements);
  283.   printf ("  sizeOfArray = %d\n", sizeOfArray);
  284.   printf ("  iteratorLastBucket = 0x%08x\n", iteratorLastBucket);
  285.   printf ("  firstInsertedBucket = 0x%08x\n", firstInsertedBucket);
  286.   printf ("  lastInsertedBucket = 0x%08x\n", lastInsertedBucket);
  287.   for (i=0; i<sizeOfArray; i++) {
  288.     p = array [i];
  289.     printf ("Bucket list %d: 0x%08x:\n", i, p);
  290.     while (p != NULL) {
  291.       printf ("  0x%08x: ", p);
  292.       printf ("  KEY=");
  293.       printString (stdout, (String *) p->key);
  294.       printf ("   VAL=%d", ((IntConst *) p->value)->ivalue);
  295.       printf ("   next=0x%08x    nextForIterator=0x%08x\n", p->next, p->nextForIterator);
  296.       p = p->next;
  297.     }
  298.   }
  299.   printf ("  done.\n");
  300. ***/
  301.  
  302.  
  303. /*****
  304.   // Print each bucket list, giving an order dependent on the hash function...
  305.   for (i=0; i<sizeOfArray; i++) {
  306.     p = array [i];
  307.     while (p != NULL) {
  308.       printKeyValue (p->key, p->value, indent+6);
  309.  
  310.       // str = (String *) p->key;
  311.       // val = (IntConst *) p->value;
  312.       // ppIndent (indent);
  313.       // printf ("   KEY=");
  314.       // printString (stdout, str);
  315.       // printf ("   VAL=%d\n", val->ivalue);
  316.  
  317.       p = p->next;
  318.     }
  319.   }
  320. *****/
  321.  
  322.   // Print using the insertion order...
  323.   for (p = firstInsertedBucket; p; p = p->nextForIterator) {
  324.     printKeyValue (p->key, p->value, indent+6);
  325.   }
  326.  
  327.   if (superMap != NULL) {
  328.     superMap->print (indent+4);
  329.   }
  330.  
  331.   ppIndent (indent);
  332.   printf ("===============================\n");
  333. }
  334.  
  335.  
  336.  
  337. // printKeyValue (key, value, indent)
  338. //
  339. // Print a symbol table entry.
  340. // The value is assumed to be a pointer to a Decl, Class, Function, Method,
  341. // TypeParm, Field, or Parameter.  It prettyPrints it.
  342. //
  343. // It assumes that Key=String and Value=AstNode and WILL CRASH if this is
  344. // not the case.
  345. //
  346. template <class Key, class Value>
  347. void Mapping <Key, Value> :: printKeyValue (Key * k, Value * v, int indent) {
  348.   String * key;
  349.   AstNode * value = (AstNode *) v;
  350.  
  351.   if (((AstNode *) k)->op == TYPE_PARM) {
  352.     key = ((TypeParm *) k) -> id;
  353.   } else {
  354.     key = (String * ) k;
  355.   }
  356.  
  357.   ppIndent (indent);
  358.   printString (stdout, key);
  359.   printf (":\n");
  360.   switch (value->op) {
  361.     case GLOBAL:
  362.     case LOCAL:
  363.     case PARAMETER:
  364.     case CLASS_FIELD:
  365.     case RECORD_FIELD:
  366.       ppIndent (indent+4);
  367.       printf ("%s ", symbolName (value->op));
  368.       value->prettyPrint (indent+8);
  369.       printf ("\n");
  370.       break;
  371.     case ERROR_DECL:
  372.       ppIndent (indent+4);
  373.       printf ("ERROR_DECL ");
  374.       value->prettyPrint (indent+4);
  375.       printf ("\n");
  376.       break;
  377.     case CONST_DECL:
  378.       ppIndent (indent+4);
  379.       printf ("CONST_DECL ");
  380.       value->prettyPrint (indent+4);
  381.       printf ("\n");
  382.       break;
  383.     case FUNCTION_PROTO:
  384.       ppIndent (indent+4);
  385.       printf ("FUNCTION_PROTO ");
  386.       value->prettyPrint (indent+4);
  387.       printf ("\n");
  388.       break;
  389.     case METHOD_PROTO:
  390.       ppIndent (indent+4);
  391.       printf ("METHOD_PROTO ");
  392.       value->prettyPrint (indent+4);
  393.       printf ("\n");
  394.       break;
  395.     case METHOD:
  396.       ppIndent (indent+4);
  397.       printf ("METHOD ");
  398.       value->prettyPrint (indent+4);
  399.       printf ("\n");
  400.       break;
  401.     case TYPE_DEF:
  402.       ppIndent (indent+4);
  403.       printf ("TYPE_DEF ");
  404.       value->prettyPrint (indent+4);
  405.       printf ("\n");
  406.       break;
  407.     case CLASS_DEF:
  408.       ppIndent (indent+4);
  409.       printf ("CLASS_DEF ");
  410.       printString (stdout, ((ClassDef *) value)->id);
  411.       printf ("\n");
  412.       break;
  413.     case INTERFACE:
  414.       ppIndent (indent+4);
  415.       printf ("INTERFACE ");
  416.       printString (stdout, ((ClassDef *) value)->id);
  417.       printf ("\n");
  418.       break;
  419. // NEED TO FIX...  PARAMETER->prettyPrint will print ", " and next...
  420.     case TYPE_PARM:
  421.       ppIndent (indent+4);
  422.       printf ("TYPE_PARM ");
  423.       printString (stdout, ((TypeParm *) value)->id);
  424.       printf ("[%08x]", value);
  425.       printf ("\n");
  426.       break;
  427.     case CHAR_TYPE:
  428.     case INT_TYPE:
  429.     case DOUBLE_TYPE:
  430.     case BOOL_TYPE:
  431.     case VOID_TYPE:
  432.     case TYPE_OF_NULL_TYPE:
  433.     case FUNCTION_TYPE:
  434.     case NAMED_TYPE:
  435.     case ARRAY_TYPE:
  436.     case PTR_TYPE:
  437.       ppIndent (indent+4);
  438.       printf ("%s ", symbolName (value->op));
  439.       ((Type *) value)->prettyPrint (0);
  440.       printf ("\n");
  441.       break;
  442.     case INT_CONST:
  443.       ppIndent (indent+4);
  444.       printf ("INT_CONST ");
  445.       ((IntConst *) value)->prettyPrint (0);
  446.       printf ("\n");
  447.       break;
  448.     case HEADER:
  449.       value->prettyPrint (indent+8);
  450.       break;
  451. /*****
  452.     case FUNCTION:
  453.       ppIndent (indent+4);
  454.       printf ("FUNCTION ");
  455.       printString (stdout, ((Function *) value)->id);
  456.       printf ("\n");
  457.       break;
  458.     case METHOD:
  459.       ppIndent (indent+4);
  460.       printf ("METHOD ");
  461.       printString (stdout, ((Method *) value)->id);
  462.       printf ("\n");
  463.       break;
  464. *****/
  465.     default:
  466.       programLogicError ("Unkown op in printKeyValue");
  467.   }
  468. }
  469.  
  470.  
  471.  
  472. // printOffsetToSelector (title)
  473. //
  474. template <class Key, class Value>
  475. void Mapping<Key, Value> :: printOffsetToSelector (char * title) {
  476.   int i;
  477.   Bucket<Key, Value> * p;
  478.   String * sel;
  479.   Offset * off;
  480.   Key * key;
  481.   Value * value;
  482.   printf ("        %s\n", title);
  483.   // Print using the insertion order...
  484.   for (p=firstInsertedBucket; p; p = p->nextForIterator) {
  485.     off = (Offset *) p->key;
  486.     sel = (String *) p->value;
  487.     printf ("          %d: ", off->ivalue);
  488.     printString (stdout, sel);
  489.     printf ("\n");
  490.   }
  491. /******
  492.   for (i=0; i<sizeOfArray; i++) {
  493.     p = array [i];
  494.     while (p != NULL) {
  495.       off = (Offset *) p->key;
  496.       sel = (String *) p->value;
  497.       printf ("          %d: ", off->ivalue);
  498.       printString (stdout, sel);
  499.       printf ("\n");
  500.       p = p->next;
  501.     }
  502.   }
  503.   printf ("        ===============================\n");
  504. *****/
  505. }
  506.  
  507.  
  508.  
  509. // printSelectorToOffset ()
  510. //
  511. template <class Key, class Value>
  512. void Mapping<Key, Value> :: printSelectorToOffset () {
  513.   int i;
  514.   Bucket<Key, Value> * p;
  515.   String * sel;
  516.   Offset * off;
  517.   Key * key;
  518.   Value * value;
  519.   printf ("        SELECTOR-TO-OFFSET:\n");
  520.   // Print using the insertion order...
  521.   for (p=firstInsertedBucket; p; p = p->nextForIterator) {
  522.     sel = (String *) p->key;
  523.     off = (Offset *) p->value;
  524.     printf ("          ");
  525.     printString (stdout, sel);
  526.     printf (": %d\n", off->ivalue);
  527.   }
  528. /*****
  529.   for (i=0; i<sizeOfArray; i++) {
  530.     p = array [i];
  531.     while (p != NULL) {
  532.       sel = (String *) p->key;
  533.       off = (Offset *) p->value;
  534.       printf ("          ");
  535.       printString (stdout, sel);
  536.       printf (": %d\n", off->ivalue);
  537.       p = p->next;
  538.     }
  539.   }
  540.   printf ("        ===============================\n");
  541. *****/
  542. }
  543.  
  544.  
  545.  
  546. // getFirst () --> Value
  547. //
  548. // This routine and getNext() are used to iterate through all the elements
  549. // in the top scope only.  To use, call getFirst(), then call getNext()
  550. // repeatedly.  When there are no more, these routines will return NULL.
  551. //
  552. template <class Key, class Value>
  553. Value * Mapping <Key, Value> :: getFirst () {
  554.   iteratorLastBucket = firstInsertedBucket;
  555.   if (iteratorLastBucket == NULL) return NULL;
  556.   return iteratorLastBucket->value;                // Possibly NULL
  557. }
  558.  
  559. /*****  old version  *****
  560. template <class Key, class Value>
  561. Value * Mapping <Key, Value> :: getFirst () {
  562.   iteratorLastIndex = 0;
  563.   for (; iteratorLastIndex<sizeOfArray; iteratorLastIndex ++) {
  564.     iteratorLastBucket = array [iteratorLastIndex];
  565.     if (iteratorLastBucket) return iteratorLastBucket->value;
  566.   }
  567.   return NULL;
  568. }
  569. ********************/
  570.  
  571.  
  572.  
  573. // getNext () --> Value
  574. //
  575. // This routine and getFirst() are used to iterate through all the elements
  576. // in the top scope only.  To use, call getFirst(), then call getNext()
  577. // repeatedly.  When there are no more, these routines will return NULL.
  578. //
  579. template <class Key, class Value>
  580. Value * Mapping <Key, Value> :: getNext () {
  581.   if (iteratorLastBucket == NULL) {
  582.     programLogicError ("Mapping getNext called after end of list already reached");
  583.   }
  584.   iteratorLastBucket = iteratorLastBucket->nextForIterator;
  585.   if (iteratorLastBucket == NULL) {
  586.     return NULL;
  587.   }
  588.   return iteratorLastBucket->value;
  589. }
  590.  
  591. /*****  old version  *****
  592. template <class Key, class Value>
  593. Value * Mapping <Key, Value> :: getNext () {
  594.   Bucket<Key, Value> * p;
  595.   iteratorLastBucket = iteratorLastBucket->next;
  596.   if (iteratorLastBucket) return iteratorLastBucket->value; 
  597.   iteratorLastIndex ++;
  598.   for (; iteratorLastIndex < sizeOfArray; iteratorLastIndex ++) {
  599.     iteratorLastBucket = array [iteratorLastIndex];
  600.     if (iteratorLastBucket) return iteratorLastBucket->value;
  601.   }
  602.   return NULL;
  603. }
  604. ********************/
  605.  
  606.  
  607. // getItsKey () --> Key
  608. //
  609. // This routine should only be called after getFirst() or getNext() has
  610. // returned a non-NULL value.  This routine returns its key.
  611. //
  612. template <class Key, class Value>
  613. Key * Mapping <Key, Value> :: getItsKey () {
  614.   if (iteratorLastBucket == NULL) {
  615.     programLogicError ("Mapping getItsKey called but last was NULL");
  616.   }
  617.   return iteratorLastBucket->key;
  618. }
  619.  
  620.  
  621.  
  622. // Constructor (initialSize, superMap)
  623. //
  624. // The initialSize may be zero.  The pointer to a super Mapping may be
  625. // NULL.
  626. //
  627. template <class Key, class Value>
  628. Mapping<Key, Value> :: Mapping (int initSize, Mapping * supMap) {
  629.   int i;
  630.   superMap = supMap;
  631.   numberOfElements = 0;
  632.   sizeOfArray = initSize;
  633.   array = NULL;
  634.   iteratorLastBucket = NULL;
  635.   firstInsertedBucket = NULL;
  636.   lastInsertedBucket = NULL;
  637.   if (initSize < 0) {
  638.     programLogicError ("Trying to create a mapping with negative size");
  639.   }
  640.   if (initSize == 0) return;
  641.   array = (Bucket<Key, Value> * * ) new Bucket<Key, Value> * [initSize];
  642.   for (i=0; i<sizeOfArray; i++) {
  643.     array [i] = NULL;
  644.   }
  645. }
  646.  
  647.  
  648.  
  649. // Destructor ()
  650. //
  651. // Free the array and all the buckets.
  652. //
  653. template <class Key, class Value>
  654. Mapping<Key, Value> :: ~Mapping () {
  655.   int i;
  656.   Bucket<Key, Value> * buck;
  657.   Bucket<Key, Value> * nextBuck;
  658.   
  659.   for (i=0; i<sizeOfArray; i++) {
  660.     buck = array[i];
  661.     while (buck != NULL) {
  662.       nextBuck = buck->next;
  663.       delete buck;
  664.       buck = nextBuck;
  665.     }
  666.   }
  667.   delete array;
  668. }
  669.  
  670.  
  671.  
  672. // nextLargerSize (oldSize) --> int
  673. //
  674. // Returns next larger size.
  675. //
  676. template <class Key, class Value>
  677. int Mapping<Key, Value> :: nextLargerSize (int oldSize) {
  678.   if (oldSize < 0) return 0;
  679.   if (oldSize < 7) return 7;
  680.   if (oldSize < 41) return 41;
  681.   if (oldSize < 211) return 211;
  682.   return 1021;
  683. }
  684.  
  685.  
  686.  
  687. // rehashIfNecessary ()
  688. //
  689. // If the Mapping has reached 50% full (i.e., if the number of Buckets
  690. // is half the size of the hash table), then re allocate a new array
  691. // and move all Buckets into the new array.
  692. //
  693. template <class Key, class Value>
  694. void Mapping<Key, Value> :: rehashIfNecessary () {
  695.   int oldArraySize, i;
  696.   Bucket<Key,Value> * * oldArray;
  697.   Bucket<Key,Value> * p;
  698.   Bucket<Key,Value> * nextP;
  699.  
  700. //  printf ("Rehash called: numberOfElements = %d sizeOfArray = %d\n",
  701. //          numberOfElements, sizeOfArray);
  702.  
  703.   if (numberOfElements < sizeOfArray/2) return;
  704.   if (sizeOfArray == nextLargerSize (sizeOfArray)) return;
  705.  
  706.   // printf ("== Rehashing: nextLargerSize (sizeOfArray) = %d\n",
  707.   //         nextLargerSize (sizeOfArray));
  708.  
  709.   // printf ("Rehashing: Before...\n");
  710.   // this->print (0);
  711.  
  712.   oldArraySize = sizeOfArray;
  713.   oldArray = array;
  714.  
  715.   // Reinitialize this Mapping...
  716.   sizeOfArray = nextLargerSize (oldArraySize);
  717.   array = (Bucket<Key, Value> * * ) new Bucket<Key, Value> * [sizeOfArray];
  718.   for (i=0; i<sizeOfArray; i++) {
  719.     array [i] = NULL;
  720.   }
  721.   //////  numberOfElements = 0;
  722.  
  723.   // Go through the elements and add them back to this mapping.
  724.   for (i=0; i<oldArraySize; i++) {
  725.     p = oldArray [i];
  726.     // printf ("Processing bucket list %d: 0x%08x:\n", i, p);
  727.     while (p != NULL) {
  728.       nextP = p->next;
  729.       // String * str = (String *) p->key;
  730.       // IntConst * val = (IntConst *) p->value;
  731.       // printf ("  Moving   KEY=");
  732.       // printString (stdout, str);
  733.       // printf ("   VAL=%d\n", val->ivalue);
  734.       int i2 = arrayIndex (p->key);
  735.       p->next = array[i2];
  736.       array[i2] = p;
  737.       p = nextP;
  738.     }
  739.   }
  740.   delete oldArray;
  741.   // printf ("Rehashing: After...\n");
  742.   // this->print (0);
  743. }
  744.  
  745.  
  746.  
  747. // findInTopScope (key) --> value
  748. //
  749. // Return NULL if not found.  Look only in the top scope.
  750. //
  751. template <class Key, class Value>
  752. Value * Mapping<Key, Value> :: findInTopScope (Key * k) {
  753.   Bucket<Key,Value> * buck;
  754.   int i = arrayIndex (k);
  755.   buck = array[i];
  756.   while (buck != NULL) {
  757.     if (buck->key == k) return buck->value;
  758.     buck = buck->next;
  759.   }
  760.   return NULL;
  761. }
  762.  
  763.  
  764.  
  765. // arrayIndex (key) --> int
  766. //
  767. // This routine is passed a pointer.  It uses this pointer as a
  768. // hash value and returns an entry into the array.
  769. // It returns an integer between 0 and (arraySize-1).
  770. //
  771. template <class Key, class Value>
  772. int Mapping<Key, Value> :: arrayIndex (Key * k) {
  773.   return (((int) k) >> 2) % sizeOfArray;
  774. }
  775.  
  776.  
  777.  
  778. // testMapping ()
  779. //
  780. // This routine is used in testing the Mapping class.
  781. //
  782. void testMapping () {
  783.   Mapping<String, Offset> * testMap2;
  784.   Mapping<Offset, String> * testMap3;
  785.   int i;
  786.   Offset * off;
  787.  
  788.   String * s1 = lookupAndAdd ("string 1", ID);
  789.   String * s2 = lookupAndAdd ("string 2", ID);
  790.   String * s3 = lookupAndAdd ("string 3", ID);
  791.   String * s4 = lookupAndAdd ("string 4", ID);
  792.   String * s5 = lookupAndAdd ("string 5", ID);
  793.   String * s6 = lookupAndAdd ("string 6", ID);
  794.   String * s7 = lookupAndAdd ("string 7", ID);
  795.   String * s8 = lookupAndAdd ("string 8", ID);
  796.   String * s9 = lookupAndAdd ("string 9", ID);
  797.   String * s10 = lookupAndAdd ("string 10", ID);
  798.   String * s11 = lookupAndAdd ("string 11", ID);
  799.   String * s12 = lookupAndAdd ("string 12", ID);
  800.   String * s13 = lookupAndAdd ("string 13", ID);
  801.   String * s14 = lookupAndAdd ("string 14", ID);
  802.   String * s15 = lookupAndAdd ("string 15", ID);
  803.   String * s16 = lookupAndAdd ("string 16", ID);
  804.   String * s17 = lookupAndAdd ("string 17", ID);
  805.   String * s18 = lookupAndAdd ("string 18", ID);
  806.   String * s19 = lookupAndAdd ("string 19", ID);
  807.   String * s20 = lookupAndAdd ("string 20", ID);
  808.  
  809.   IntConst * v1 = new IntConst (); v1->ivalue = 10001;
  810.   IntConst * v2 = new IntConst (); v2->ivalue = 10002;
  811.   IntConst * v3 = new IntConst (); v3->ivalue = 10003;
  812.   IntConst * v4 = new IntConst (); v4->ivalue = 10004;
  813.   IntConst * v5 = new IntConst (); v5->ivalue = 10005;
  814.   IntConst * v6 = new IntConst (); v6->ivalue = 10006;
  815.   IntConst * v7 = new IntConst (); v7->ivalue = 10007;
  816.   IntConst * v8 = new IntConst (); v8->ivalue = 10008;
  817.   IntConst * v9 = new IntConst (); v9->ivalue = 10009;
  818.   IntConst * v10 = new IntConst (); v10->ivalue = 10010;
  819.   IntConst * v11 = new IntConst (); v11->ivalue = 10011;
  820.   IntConst * v12 = new IntConst (); v12->ivalue = 10012;
  821.   IntConst * v13 = new IntConst (); v13->ivalue = 10013;
  822.   IntConst * v14 = new IntConst (); v14->ivalue = 10014;
  823.   IntConst * v15 = new IntConst (); v15->ivalue = 10015;
  824.   IntConst * v16 = new IntConst (); v16->ivalue = 10016;
  825.   IntConst * v17 = new IntConst (); v17->ivalue = 10017;
  826.   IntConst * v18 = new IntConst (); v18->ivalue = 10018;
  827.   IntConst * v19 = new IntConst (); v19->ivalue = 10019;
  828.   IntConst * v20 = new IntConst (); v20->ivalue = 10020;
  829.  
  830.   testMap = (Mapping<String, AstNode> *)
  831.       new Mapping<String, AstNode> (7, NULL);
  832.   // Test printing for empty mappings...
  833.   testMap->print (0);
  834.  
  835.   printf ("Testing iterator functions for empty mapping...\n");
  836.   for (IntConst * vvv = (IntConst *) testMap->getFirst();
  837.        vvv;
  838.        vvv = (IntConst *) testMap->getNext()) {
  839.     printf ("   KEY=");
  840.     printString (stdout, testMap->getItsKey());
  841.     printf ("   VAL=%d\n", vvv->ivalue);
  842.   }
  843.   printf ("Done testing iterator functions for empty mapping.\n");
  844.  
  845.   testMap->enter (s1,v1);
  846.   testMap->enter (s2,v2);
  847.   testMap->enter (s3,v3);
  848.  
  849.   testMap->print (0);
  850.  
  851.   testMap = (Mapping<String, AstNode> *)
  852.       new Mapping<String, AstNode> (3, testMap);
  853.  
  854.   testMap->print (0);
  855.  
  856.   testMap->enter (s4,v4);
  857.   testMap->enter (s5,v5);
  858.   testMap->enter (s6,v6);
  859.   testMap->enter (s7,v7);
  860.   testMap->enter (s8,v8);
  861.   testMap->enter (s9,v9);
  862.   testMap->enter (s10,v10);
  863.   testMap->enter (s11,v11);
  864.   testMap->enter (s12,v12);
  865.   testMap->enter (s13,v13);
  866.   testMap->enter (s14,v14);
  867.   testMap->enter (s15,v15);
  868.   testMap->enter (s16,v16);
  869.   testMap->enter (s17,v17);
  870.   testMap->enter (s18,v18);
  871.   testMap->enter (s19,v19);
  872.   testMap->enter (s20,v20);
  873.  
  874.   testMap->print (0);
  875.  
  876.   searchFor (s1);
  877.   searchFor (s2);
  878.   searchFor (s3);
  879.   searchFor (s4);
  880.   searchFor (s5);
  881.   searchFor (s6);
  882.   searchFor (s7);
  883.   searchFor (s8);
  884.   searchFor (s9);
  885.  
  886.   printf ("Testing iterator functions...\n");
  887.   for (v1 = (IntConst *) testMap->getFirst(); v1; v1 = (IntConst *) testMap->getNext()) {
  888.     printf ("   KEY=");
  889.     printString (stdout, testMap->getItsKey());
  890.     printf ("   VAL=%d\n", v1->ivalue);
  891.   }
  892.  
  893.   delete testMap;
  894.  
  895.   // Initialize the Dispatch Table offset list...
  896.   if (firstDispatchOffset == NULL) {
  897.     off = new Offset;
  898.     off->ivalue = 4;        // This is the offset of the first message
  899.     off->nextOffset = NULL;
  900.     firstDispatchOffset = off;
  901.   }
  902.  
  903.   testMap2 = (Mapping<String, Offset> *)
  904.       new Mapping<String, Offset> (10, NULL);
  905.   testMap2->printSelectorToOffset ();
  906.   off = firstDispatchOffset;
  907.   testMap2->enter (s1,off);
  908.   off = nextDispatchOffset (off);
  909.   testMap2->enter (s2,off);
  910.   off = nextDispatchOffset (off);
  911.   testMap2->enter (s3,off);
  912.   off = nextDispatchOffset (off);
  913.   testMap2->enter (s4,off);
  914.   off = nextDispatchOffset (off);
  915.   testMap2->enter (s5,off);
  916.   off = nextDispatchOffset (off);
  917.   testMap2->enter (s6,off);
  918.   off = nextDispatchOffset (off);
  919.   testMap2->enter (s7,off);
  920.   off = nextDispatchOffset (off);
  921.   testMap2->enter (s8,off);
  922.   off = nextDispatchOffset (off);
  923.   testMap2->enter (s9,off);
  924.   off = nextDispatchOffset (off);
  925.   testMap2->enter (s10,off);
  926.   off = nextDispatchOffset (off);
  927.   testMap2->enter (s11,off);
  928.   off = nextDispatchOffset (off);
  929.   testMap2->enter (s12,off);
  930.   off = nextDispatchOffset (off);
  931.   testMap2->enter (s13,off);
  932.   off = nextDispatchOffset (off);
  933.   testMap2->enter (s14,off);
  934.   off = nextDispatchOffset (off);
  935.   testMap2->enter (s15,off);
  936.  
  937.   testMap2->printSelectorToOffset ();
  938.   delete testMap2;
  939.  
  940.   testMap3 = (Mapping<Offset, String> *)
  941.       new Mapping<Offset, String> (10, NULL);
  942.   testMap3->printOffsetToSelector ("here is a title");
  943.   off = firstDispatchOffset;
  944.   testMap3->enter (off, s1);
  945.   off = nextDispatchOffset (off);
  946.   testMap3->enter (off, s2);
  947.   off = nextDispatchOffset (off);
  948.   testMap3->enter (off, s3);
  949.   off = nextDispatchOffset (off);
  950.   testMap3->enter (off, s4);
  951.   off = nextDispatchOffset (off);
  952.   testMap3->enter (off, s5);
  953.   off = nextDispatchOffset (off);
  954.   testMap3->enter (off, s6);
  955.   off = nextDispatchOffset (off);
  956.   testMap3->enter (off, s7);
  957.   off = nextDispatchOffset (off);
  958.   testMap3->enter (off, s8);
  959.   off = nextDispatchOffset (off);
  960.   testMap3->enter (off, s9);
  961.   off = nextDispatchOffset (off);
  962.   testMap3->enter (off, s10);
  963.   off = nextDispatchOffset (off);
  964.   testMap3->enter (off, s11);
  965.   off = nextDispatchOffset (off);
  966.   testMap3->enter (off, s12);
  967.   off = nextDispatchOffset (off);
  968.   testMap3->enter (off, s13);
  969.   off = nextDispatchOffset (off);
  970.   testMap3->enter (off, s14);
  971.   off = nextDispatchOffset (off);
  972.   testMap3->enter (off, s15);
  973.  
  974.   testMap3->printOffsetToSelector ("here is a title");
  975.   delete testMap3;
  976.  
  977.   exit (0);
  978. }
  979.  
  980.  
  981.  
  982. // searchFor (str)
  983. //
  984. // This routine is used in testing the Mapping class.  It is passed a
  985. // key and it calls several functions (such as "find" and "alreadyDefined")
  986. // using this key and prints the results.
  987. //
  988. void searchFor (String * str) {
  989.   IntConst * val;
  990.   int i;
  991.   printString (stdout, str);
  992.   printf ("...\n");
  993.   printf ("   find () =              ");
  994.   val = (IntConst *) testMap->find (str);
  995.   if (val == NULL) {
  996.     printf ("   NULL RETURNED\n");
  997.   } else {
  998.     printf ("   KEY=");
  999.     printString (stdout, str);
  1000.     printf ("   VAL=%d\n", val->ivalue);
  1001.   }
  1002.   printf ("   findInTopScope () =    ");
  1003.   val = (IntConst *) testMap->findInTopScope (str);
  1004.   if (val == NULL) {
  1005.     printf ("   NULL RETURNED\n");
  1006.   } else {
  1007.     printf ("   KEY=");
  1008.     printString (stdout, str);
  1009.     printf ("   VAL=%d\n", val->ivalue);
  1010.   }
  1011.   i = testMap->alreadyDefined (str);
  1012.   printf ("   alreadyDefined () = %d\n", i);
  1013. }
  1014.