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