HashTab.hpp

/*******************************************************************************
 * 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
 *******************************************************************************/

#ifndef HASHTAB_INCL
#define HASHTAB_INCL

#include <stdint.h>
#include <string.h>
#include "env/TRMemory.hpp"
#include "env/jittypes.h"
#include "infra/Assert.hpp"

#include "infra/Bit.hpp"

class TR_HashTab;
namespace TR { class Compilation; }

/**
 * general purpose hash table that assume a key which fits in 8 bytes
 * and stores a 'void *'.  Less space efficient than a template,
 * but templates have their own headaches.
 * User can overwrite two routines, and they must be explicitly
 * cast when being used. See HashTab.cpp for examples
 *
 *     uint32_t calculateHash(const void *key) const;
 */


// assume sizeof(long) >= sizeof(uint32_t)
typedef unsigned long TR_HashId;

class TR_HashTabIterator
   {
   public:
   TR_ALLOC(TR_Memory::HashTab)
   TR_HashTabIterator() : _curHashIndex(0) {}
   TR_HashTabIterator(TR_HashTab *h) : _baseHashTab(h),_curHashIndex(0){}
   void *getCurrent ();

   void *getFirst() { _curHashIndex = 0; return getCurrent(); }
   void *getNext() { ++_curHashIndex; return getCurrent(); }
   void reset() { _curHashIndex = 0; }
   bool atEnd();

   private:
   TR_HashId   _curHashIndex;
   TR_HashTab *_baseHashTab;
    };
// hash table with chaining.  Chained buckets are in a separate area
class TR_HashTab
   {

   protected:
   enum  { kMinimumSize=16,
           kDefaultSize=64};

   public:

   TR_ALLOC(TR_Memory::HashTab)

   // inherit and then overwrite these two methods as appropriate
   // assume a pointer
   virtual TR_HashId calculateHash(const void *key) const { return  (TR_HashId((uintptr_t)key) >> 2) %_closedAreaSize;}
   virtual bool isEqual(const void * key1, const void *key2) const { return key1 == key2; }

   TR_HashTab(TR_Memory *mem,
              TR_AllocationKind a=heapAlloc,
              uint32_t initialSize=kDefaultSize,
              bool g=true):
      _tableSize(0), _allocType(a),_table(NULL),_closedAreaSize(0),_allowGrowth(g),_trMemory(mem)
      {
      init(initialSize);
      _trace=false;
      }

   TR_Memory *               trMemory()                    { return _trMemory; }
   TR_StackMemory            trStackMemory()               { return _trMemory; }
   TR_HeapMemory             trHeapMemory()                { return _trMemory; }

   void init(uint32_t size, bool allowGrowth=true);

   bool locate(const void* key,TR_HashId &hashIndex);

   bool growTo(uint32_t newSize);

   void reset()
      {
      _tableSize=0;
      if ((_allocType == persistentAlloc) &&
          (_table != NULL))
         {
         for (TR_HashId i=0; i < _tableSize ;++i)
            jitPersistentFree(_table[i]);
         jitPersistentFree(_table);
         }
      _table = NULL; // TODO if heap, notify vm that it's free
      }

   void clear() { memset(_table,0,sizeof(TR_HashTableEntry*) * _tableSize); }

   void * getData(TR_HashId id);
   void updateData(TR_HashId id, void *data)
      {
      _table[id]->_data = data;
      return;
      }
   void setKey(TR_HashId id, void* key) { _table[id]->_key = key;return; } ;

 /**
   * return true if successfully added
   * search table for matching record.  If
   * a collision, chain in a new entry.
   * if we run out of free space, die--in future grow and rehash
   */
   bool add(void *key,TR_HashId hashIndex,void * data)
      {
      TR_HashTableEntry *entry = new (trMemory(), _allocType) TR_HashTableEntry(key,data,0);
      return addElement(key,hashIndex,entry);
      }

   void replace(void *key, TR_HashId hashIndex, void *data)
      {
      TR_HashTableEntry *entry = new (trMemory(), _allocType) TR_HashTableEntry(key,data,0);
      TR_ASSERT(_table && _table[hashIndex], "entry in hashIndex is NULL\n");
      entry->_chain = _table[hashIndex]->_chain;
      _table[hashIndex] = entry;
      }

   private:

   void growAndRehash(uint32_t);

   class TR_HashTableEntry
      {
      public:

      TR_ALLOC(TR_Memory::HashTableEntry)
      TR_HashTableEntry():
         _chain(0),
         _data(NULL){}

      TR_HashTableEntry(void *key,void * data,uint32_t chain)
         {
         _key = key;
         _chain = chain;
         _data = data;
         }

      TR_HashTableEntry(const TR_HashTableEntry & entry):
         _key(entry._key),
         _chain(entry._chain),
         _data(entry._data){}

      void *       _key;
      void *       _data;
      uint32_t     _chain;

      };

   private:
   bool addElement(void * key,TR_HashId &hashIndex,TR_HashTableEntry *entry);

   uint32_t          _tableSize; // total table size (closed + open)
   TR::Compilation *  _comp;
   TR_Memory *       _trMemory;
   TR_AllocationKind _allocType;
   TR_HashId         _nextFree;  // next free slot in open area
   uint32_t          _mask;
   TR_HashTableEntry  **_table;
   bool              _allowGrowth;
   bool              _trace;
   protected:
   uint32_t          _closedAreaSize; // range of hashes
   friend bool TR_HashTabIterator::atEnd();
   friend void *TR_HashTabIterator::getCurrent();
   };

class TR_HashTabInt : public TR_HashTab
   {
   public:
   TR_HashTabInt(TR_Memory *mem, TR_AllocationKind allocType=heapAlloc, uint32_t initialSize=kDefaultSize, bool allowGrowth=true):
      TR_HashTab(mem, allocType, initialSize, allowGrowth) { }

   TR_HashId calculateHash(const void *key) const { return (TR_HashId((intptr_t)key) %_closedAreaSize);}

   bool locate(int32_t key,TR_HashId &hashIndex){ return TR_HashTab::locate((const void*)(uintptr_t)key,hashIndex);}
   bool add(int32_t key,TR_HashId hashIndex,void * data){ return TR_HashTab::add((void *)(uintptr_t)key,hashIndex,data);}
   };

class TR_HashTabString : public TR_HashTab
   {
   public:
   TR_HashTabString(TR_Memory *mem, TR_AllocationKind allocType=heapAlloc, uint32_t initialSize=kDefaultSize, bool allowGrowth=true):
      TR_HashTab(mem, allocType, initialSize, allowGrowth) { }

   TR_HashId calculateHash(const void *key) const // Bernstein's string hash
         {
         uint64_t hash = 5381;
         char * str = (char *) key;
         int32_t c;
         while((c = *str++))
            hash = ((hash <<5) + hash) + c; // hash * 33 + c
         return (TR_HashId(hash) %_closedAreaSize);
         }

   bool isEqual(const void * key1, const void *key2) const { return 0 == strcmp((char*)key1,(char *) key2); }
   bool locate(const char * key,TR_HashId &hashIndex){ return TR_HashTab::locate((const void*)key,hashIndex);}
   bool add(const char * key,TR_HashId hashIndex,void * data){ return TR_HashTab::add((void *)key,hashIndex,data);}
   };
class TR_HashTabDouble : public TR_HashTab
   {
   public:
   TR_HashTabDouble(TR_Memory *mem, TR_AllocationKind allocType=heapAlloc, uint32_t initialSize=kDefaultSize, bool allowGrowth=true):
      TR_HashTab(mem, allocType, initialSize, allowGrowth) { }

   TR_HashId calculateHash(const void *key) const // TODO: research better hash fns for double
         {
         union
            {
            double dbl;
            struct {
            int32_t upperInt;
            int32_t lowerInt;
               }intVal;
            } x;
          x.dbl = *(double *)key;

         int32_t hash = x.intVal.lowerInt | x.intVal.upperInt;

         return (TR_HashId(hash) %_closedAreaSize);
         }

   bool isEqual(const void * key1, const void *key2) const { double a = *(double*)key1; double b = *(double*)key2; return a == b; }
   bool locate(const double * key,TR_HashId &hashIndex){ return TR_HashTab::locate((const void*)key,hashIndex);}
   bool add(double * key,TR_HashId hashIndex,void * data){ return TR_HashTab::add((void *)key,hashIndex,data);}
   };

class TR_HashTabLong : public TR_HashTab
   {
   public:
   TR_HashTabLong(TR_Memory *mem, TR_AllocationKind allocType=heapAlloc, uint32_t initialSize=kDefaultSize, bool allowGrowth=true):
      TR_HashTab(mem, allocType, initialSize, allowGrowth) { }

   TR_HashId calculateHash(const void *key) const // Bernstein's string hash
         {
         union
            {
            int64_t longVal;
            struct {
            int32_t upperInt;
            int32_t lowerInt;
               }intVal;
            } x;
          x.longVal = *(int64_t *)key;

         int32_t hash = x.intVal.lowerInt | x.intVal.upperInt;

         return (TR_HashId(hash) %_closedAreaSize);
         }

   bool isEqual(const void * key1, const void *key2) const { return *(int64_t *)key1 == *(int64_t*)key2; }
   bool locate(const int64_t * key,TR_HashId &hashIndex){ return TR_HashTab::locate((const void*)key,hashIndex);}
   bool add(int64_t * key,TR_HashId hashIndex,void * data){ return TR_HashTab::add((void *)key,hashIndex,data);}
   };

class TR_HashTabFloat : public TR_HashTab
   {
   public:
   TR_HashTabFloat(TR_Memory *mem, TR_AllocationKind allocType=heapAlloc,
                   uint32_t initialSize=kDefaultSize, bool allowGrowth=true):
      TR_HashTab(mem, allocType, initialSize, allowGrowth) { }

   TR_HashId calculateHash(const void *key) const
         {
         union
            {
            float flt;
            int32_t intVal;
            } x;
         x.flt = *(float*)key;

         int32_t hash = x.intVal;

         return (TR_HashId(hash) %_closedAreaSize);
         }

   bool isEqual(const void * key1, const void *key2) const { return *(float*)key1 == *(float*)key2;}
   bool locate(const float *key,TR_HashId &hashIndex){ return TR_HashTab::locate((const void*)key,hashIndex);}
   bool add(float *key,TR_HashId hashIndex,void * data){ return TR_HashTab::add((void *)key,hashIndex,data);}
   };


#endif