HashTab.cpp

/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#include "infra/HashTab.hpp"

#include <stdio.h>
#include "compile/Compilation.hpp"
#include "infra/Bit.hpp"

#ifdef DEBUG
void TRHashTab_testit()
   {
   TR::Compilation * comp = TR::comp();
   int32_t i;
   TR_HashTabInt x(comp->trMemory());
   TR_HashId id;
   printf("testing hashtable....\n");
   TR_ASSERT(false == x.locate(12,id),"should be false\n");
   x.add(12,id,(void *)12);
   TR_ASSERT(true == x.locate(12,id),"should be false\n");
   printf("starting\n");
   for (i =13;i < 1000;++i)
      {
      bool rc = x.locate(i,id);
      TR_ASSERT(rc == false,"should not be there\n");
      x.add(i,id,(void *)long(i));
      }
   for (i =12;i < 1000;++i)
      {
      bool rc = x.locate(i,id);
      TR_ASSERT(rc ,"should be there\n");
      long  data = (long)x.getData(id);
      TR_ASSERT((long)data == i,"%d != %d\n",(int32_t)i,(int32_t)data);
      }
   printf("done\n");
   }

#endif


void * TR_HashTab::getData(TR_HashId id)
   {
   TR_HashTableEntry * entry = _table[id];
   TR_ASSERT(id < _tableSize,"%d >= %d\n",id,_tableSize);
   TR_ASSERT(entry,"entry is null for id %d\n",id);
   return entry->_data;
   }


// will allocate table on demand
void TR_HashTab::init(uint32_t newSize, bool growth)
   {
   uint32_t openAreaSize;

   _allowGrowth = growth;

   _closedAreaSize = ceilingPowerOfTwo(newSize);
   _closedAreaSize = _closedAreaSize < kMinimumSize?kMinimumSize:_closedAreaSize;
   _mask = _closedAreaSize -1;
   _nextFree = _closedAreaSize +1;
   openAreaSize = _closedAreaSize /4;
   _tableSize = _closedAreaSize + openAreaSize;
   _table = (TR_HashTableEntry **)trMemory()->allocateMemory(_tableSize * sizeof(TR_HashTableEntry *), _allocType,  TR_Memory::HashTableEntry);
   memset(_table,0,sizeof(TR_HashTableEntry*) * _tableSize);
   }

/**
 * find and set hashIndex for the key.  Return true if element
 * exists in table.  modified hashIndex used when adding an element
 */
bool TR_HashTab::locate(const void* key,TR_HashId &hashIndex)
   {
   TR_HashId hashValue;
   hashValue = calculateHash(key);

   hashIndex = (hashValue & _mask) + 1;

   TR_ASSERT(hashIndex,"hash value is 0\n");

   if (NULL == _table) return false;
   if (NULL == _table[hashIndex]) return false;

   uint32_t collisions=0;
   while ( !isEqual(key,_table[hashIndex]->_key))
      {
      TR_HashId nextId = _table[hashIndex]->_chain;
      ++collisions;
      if (0 == nextId) return false;
      hashIndex = nextId;
      }
   return true;
   }


/**
 * have added too many entries--time to grow the table and rehash it
 */
void TR_HashTab::growAndRehash(uint32_t newSize)
   {
   TR_ASSERT(_allowGrowth,"Hash collision table is full %d\n",_tableSize);
   TR_HashTableEntry **oldTable = _table;
   uint32_t oldSize = _tableSize;

   if (_trace) printf("Regrowing to %d\n",newSize);
   init(newSize);

   TR_HashId  newId=0;
   for (TR_HashId i=0;i < oldSize;++i)
      {
      TR_HashTableEntry *oldEntry =oldTable[i];
      if (oldEntry)
         {
         addElement(oldEntry->_key,newId,oldEntry);
         }
      }
   if ((_allocType == persistentAlloc) &&
       (oldTable != NULL))
      {
      jitPersistentFree(oldTable);
      }
   }

bool TR_HashTab::growTo(uint32_t newSize)
   {
   if (NULL == _table)
      {
      init(newSize);
      }
   else
      {
      growAndRehash(newSize);
      }
   return true;
   }

/**
   * return true if element added, false if already in table.  hashIndex set to
   * element.
   */
bool TR_HashTab::addElement(void * key,TR_HashId &hashIndex,TR_HashTableEntry *entry)
   {
   if (_nextFree == _tableSize-1)
      {
      growAndRehash(uint32_t(_closedAreaSize *1.25)); // grow by 25%
      }

   if (locate(key,hashIndex)) return false;

   TR_ASSERT(hashIndex < _tableSize,"index too big %d >=%d\n",hashIndex,_tableSize);

   entry->_chain = 0;
   if (NULL == _table[hashIndex])
      {
      _table[hashIndex] = entry;
      return true;
      }

   TR_HashId nextIndex = hashIndex;
   do
      {
      hashIndex = nextIndex;
      nextIndex = _table[hashIndex]->_chain;

      if (0 == nextIndex)
         {
         nextIndex = _nextFree++;
         TR_ASSERT(_nextFree < _tableSize,"out of free space: index %d (%d)\n",nextIndex,_tableSize);

         _table[hashIndex]->_chain = nextIndex;
         _table[nextIndex] = entry;
         hashIndex = nextIndex;
         return true;
         }
      } while(!isEqual(key,_table[hashIndex]->_key));

   return false;
   }


void *TR_HashTabIterator::getCurrent ()
   {
   for(;_curHashIndex < _baseHashTab->_tableSize;++_curHashIndex)
      {
      if(_baseHashTab->_table[_curHashIndex])
         return _baseHashTab->getData(_curHashIndex);
      }
   return NULL;
   }

bool TR_HashTabIterator::atEnd() { return _curHashIndex >= _baseHashTab->_tableSize; }