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