home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 2 / AACD 2.iso / AACD / Programming / jikes-1.02 / src / set.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-01  |  7.0 KB  |  276 lines
  1. // $Id: set.cpp,v 1.8 1999/09/01 14:58:25 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "set.h"
  11. #include "config.h"
  12.  
  13. int SymbolSet::primes[] = {DEFAULT_HASH_SIZE, 101, 401, MAX_HASH_SIZE};
  14.  
  15. void SymbolSet::Rehash()
  16. {
  17.     hash_size = primes[++prime_index];
  18.  
  19.     delete [] base;
  20.     base = (ShadowSymbol **) memset(new ShadowSymbol *[hash_size], 0, hash_size * sizeof(ShadowSymbol *));
  21.  
  22.     for (int k = 0; k < symbol_pool.Length(); k++)
  23.     {
  24.         ShadowSymbol *shadow = symbol_pool[k];
  25.         int i = shadow -> Identity() -> index % hash_size;
  26.         shadow -> next = base[i];
  27.         base[i] = shadow;
  28.     }
  29.  
  30.     return;
  31. }
  32.  
  33.  
  34. SymbolSet::~SymbolSet()
  35. {
  36.     SetEmpty();
  37.     delete [] base;
  38. }
  39.  
  40.  
  41. bool SymbolSet::operator==(SymbolSet& rhs)
  42. {
  43.     if (this != &rhs)
  44.     {
  45.         if (symbol_pool.Length() != rhs.symbol_pool.Length())
  46.             return false;
  47.  
  48.         for (int i = 0; i < symbol_pool.Length(); i++)
  49.         {
  50.             ShadowSymbol *shadow = symbol_pool[i];
  51.             Symbol *symbol = shadow -> symbol;
  52.             for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  53.             {
  54.                 if (! rhs.IsElement(symbol))
  55.                     return false;
  56.             }
  57.         }
  58.     }
  59.  
  60.     return true;
  61. }
  62.  
  63.  
  64. //
  65. // Union the set in question with the set passed as argument: "set"
  66. //
  67. void SymbolSet::Union(SymbolSet &set)
  68. {
  69.     if (this != &set)
  70.     {
  71.         for (int i = 0; i < set.symbol_pool.Length(); i++)
  72.         {
  73.             ShadowSymbol *shadow = set.symbol_pool[i];
  74.             Symbol *symbol = shadow -> symbol;
  75.             for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  76.                 AddElement(symbol);
  77.         }
  78.     }
  79.  
  80.     return;
  81. }
  82.  
  83.  
  84. //
  85. // Intersect the set in question with the set passed as argument: "set"
  86. //
  87. void SymbolSet::Intersection(SymbolSet &set)
  88. {
  89.     if (this != &set)
  90.     {
  91.         Tuple<Symbol *> old_symbol_pool(this -> symbol_pool.Length());
  92.         for (int i = 0; i < this -> symbol_pool.Length(); i++)
  93.         {
  94.             ShadowSymbol *shadow = this -> symbol_pool[i];
  95.             Symbol *symbol = shadow -> symbol;
  96.             for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  97.                 old_symbol_pool.Next() = symbol;
  98.         }
  99.  
  100.         this -> SetEmpty();
  101.  
  102.         for (int j = 0; j < old_symbol_pool.Length(); j++)
  103.         {
  104.             if (set.IsElement(old_symbol_pool[j]))
  105.                 AddElement(old_symbol_pool[j]);
  106.         }
  107.     }
  108.  
  109.     return;
  110. }
  111.  
  112.  
  113. //
  114. // Return a bolean value indicating whether or not the set in question intersects the set passed as argument: "set"
  115. // i.e., is there at least one element of set that is also an element of "this" set.
  116. //
  117. bool SymbolSet::Intersects(SymbolSet &set)
  118. {
  119.     for (int i = 0; i < set.symbol_pool.Length(); i++)
  120.     {
  121.         ShadowSymbol *shadow = set.symbol_pool[i];
  122.         Symbol *symbol = shadow -> symbol;
  123.         for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  124.             if (IsElement(symbol))
  125.                 return true;
  126.     }
  127.  
  128.     return false;
  129. }
  130.  
  131.  
  132. //
  133. // Remove element from the set
  134. //
  135. void SymbolSet::RemoveElement(Symbol *element)
  136. {
  137.     NameSymbol *name_symbol = element -> Identity();
  138.     int i = name_symbol -> index % hash_size;
  139.     ShadowSymbol *previous = NULL,
  140.                  *shadow;
  141.     for (shadow = base[i]; shadow; previous = shadow, shadow = shadow -> next)
  142.     {
  143.         if (shadow -> Identity() == name_symbol)
  144.         {
  145.             Symbol *symbol = shadow -> symbol;
  146.             int k;
  147.             for (k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  148.             {
  149.                 if (symbol == element)
  150.                     break;
  151.             }
  152.  
  153.             if (symbol)
  154.             {
  155.                 if (shadow -> NumConflicts() == 0)
  156.                     break;
  157.                 shadow -> RemoveConflict(k - 1);
  158.             }
  159.  
  160.             return;
  161.         }
  162.     }
  163.  
  164.     if (shadow) // element is the only object contained in shadow
  165.     {
  166.         if (previous == NULL)
  167.              base[i] = shadow -> next;
  168.         else previous -> next = shadow -> next;
  169.  
  170.         int last_index = symbol_pool.Length() - 1;
  171.         if (shadow -> pool_index != last_index)
  172.         {// move last element to position previously occupied by element being deleted
  173.             symbol_pool[last_index] -> pool_index = shadow -> pool_index;
  174.             symbol_pool[shadow -> pool_index] = symbol_pool[last_index];
  175.         }
  176.  
  177.         symbol_pool.Reset(last_index); // remove last slot in symbol_pool
  178.  
  179.         delete shadow;
  180.     }
  181.  
  182.     return;
  183. }
  184.  
  185.  
  186. int SymbolMap::primes[] = {DEFAULT_HASH_SIZE, 101, 401, MAX_HASH_SIZE};
  187.  
  188. void SymbolMap::Rehash()
  189. {
  190.     hash_size = primes[++prime_index];
  191.  
  192.     delete [] base;
  193.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  194.  
  195.     for (int i = 0; i < symbol_pool.Length(); i++)
  196.     {
  197.         Element *element = symbol_pool[i];
  198.         int k = element -> domain_element -> Identity() -> index % hash_size;
  199.         element -> next = base[k];
  200.         base[k] = element;
  201.     }
  202.  
  203.     return;
  204. }
  205.  
  206.  
  207. void SymbolMap::Map(Symbol *symbol, Symbol *image)
  208. {
  209.     assert(symbol);
  210.  
  211.     Element *element;
  212.     int k = symbol -> Identity() -> index % hash_size;
  213.     for (element = base[k]; element; element = element -> next)
  214.     {
  215.         if (element -> domain_element == symbol)
  216.             break;
  217.     }
  218.  
  219.     //
  220.     // If this is a new element, add it to the map.
  221.     //
  222.     if (! element)
  223.     {
  224.         element = new Element();
  225.         element -> domain_element = symbol;
  226.         element -> next = base[k];
  227.         base[k] = element;
  228.  
  229.         symbol_pool.Next() = element;
  230.  
  231.         //
  232.         // If the number of unique elements in the map exceeds 2 times
  233.         // the size of the base, and we have not yet reached the maximum
  234.         // allowable size for a base, reallocate a larger base and rehash
  235.          // the elements.
  236.         //
  237.         if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  238.             Rehash();
  239.     }
  240.     else
  241.     {
  242.         fprintf(stderr, "WARNING: This should not have happened !!!");
  243.     }
  244.  
  245.     element -> image = image;
  246.  
  247.     return;
  248. }
  249.  
  250.  
  251. SymbolMap::SymbolMap(int hash_size_)
  252. {
  253.     hash_size = (hash_size_ <= 0 ? 1 : hash_size_);
  254.  
  255.     prime_index = -1;
  256.     do
  257.     {
  258.         if (hash_size < primes[prime_index + 1])
  259.             break;
  260.         prime_index++;
  261.     } while (primes[prime_index] < MAX_HASH_SIZE);
  262.  
  263.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  264. }
  265.  
  266.  
  267. SymbolMap::~SymbolMap()
  268. {
  269.     for (int i = 0; i < symbol_pool.Length(); i++)
  270.         delete symbol_pool[i];
  271.  
  272.     delete [] base;
  273.  
  274.     return;
  275. }
  276.