gprofng/src/DefaultMap.h

   1 /* Copyright (C) 2021 Free Software Foundation, Inc.
   2    Contributed by Oracle.
   3
   4    This file is part of GNU Binutils.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, 51 Franklin Street - Fifth Floor, Boston,
  19    MA 02110-1301, USA.  */
  20
  21 #ifndef _DBE_DEFAULTMAP_H
  22 #define _DBE_DEFAULTMAP_H
  23
  24 #include <assert.h>
  25 #include <vec.h>
  26 #include <Map.h>
  27
  28 template <typename Key_t, typename Value_t>
  29 class DefaultMap : public Map<Key_t, Value_t>
  30 {
  31 public:
  32
  33   DefaultMap ();
  34   ~DefaultMap ();
  35   void clear ();
  36   void put (Key_t key, Value_t val);
  37   Value_t get (Key_t key);
  38   Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
  39   Value_t remove (Key_t);
  40   Vector<Key_t> *keySet ();
  41   Vector<Value_t> *values ();
  42
  43 private:
  44
  45   struct Entry
  46   {
  47     Key_t key;
  48     Value_t val;
  49   };
  50
  51   static const int CHUNK_SIZE;
  52   static const int HTABLE_SIZE;
  53
  54   int entries;
  55   int nchunks;
  56   Entry **chunks;
  57   Vector<Entry*> *index;
  58   Entry **hashTable;
  59 };
  60
  61
  62 template <typename Key_t, typename Value_t>
  63 const int DefaultMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
  64 template <typename Key_t, typename Value_t>
  65 const int DefaultMap<Key_t, Value_t>::HTABLE_SIZE = 1024;
  66
  67 template <typename Key_t, typename Value_t>
  68 DefaultMap<Key_t, Value_t>::DefaultMap ()
  69 {
  70   entries = 0;
  71   nchunks = 0;
  72   chunks = NULL;
  73   index = new Vector<Entry*>;
  74   hashTable = new Entry*[HTABLE_SIZE];
  75   for (int i = 0; i < HTABLE_SIZE; i++)
  76     hashTable[i] = NULL;
  77 }
  78
  79 template <typename Key_t, typename Value_t>
  80 DefaultMap<Key_t, Value_t>::~DefaultMap ()
  81 {
  82   for (int i = 0; i < nchunks; i++)
  83     delete[] chunks[i];
  84   delete[] chunks;
  85   delete index;
  86   delete[] hashTable;
  87 }
  88
  89 template <typename Key_t, typename Value_t>
  90 void
  91 DefaultMap<Key_t, Value_t>::clear ()
  92 {
  93   entries = 0;
  94   index->reset ();
  95   for (int i = 0; i < HTABLE_SIZE; i++)
  96     hashTable[i] = NULL;
  97 }
  98
  99 template <typename Key_t>
 100 inline unsigned
 101 hash (Key_t key)
 102 {
 103   unsigned h = (unsigned) ((unsigned long) key);
 104   h ^= (h >> 20) ^ (h >> 12);
 105   return (h ^ (h >> 7) ^ (h >> 4));
 106 }
 107
 108 template <typename Key_t, typename Value_t>
 109 void
 110 DefaultMap<Key_t, Value_t>::put (Key_t key, Value_t val)
 111 {
 112   unsigned idx = hash (key) % HTABLE_SIZE;
 113   Entry *entry = hashTable[idx];
 114   if (entry && entry->key == key)
 115     {
 116       entry->val = val;
 117       return;
 118     }
 119   int lo = 0;
 120   int hi = entries - 1;
 121   while (lo <= hi)
 122     {
 123       int md = (lo + hi) / 2;
 124       entry = index->fetch (md);
 125       int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
 126       if (cmp < 0)
 127         lo = md + 1;
 128       else if (cmp > 0)
 129         hi = md - 1;
 130       else
 131         {
 132           entry->val = val;
 133           return;
 134         }
 135     }
 136   if (entries >= nchunks * CHUNK_SIZE)
 137     {
 138       nchunks++;
 139       // Reallocate Entry chunk array
 140       Entry **new_chunks = new Entry*[nchunks];
 141       for (int i = 0; i < nchunks - 1; i++)
 142         new_chunks[i] = chunks[i];
 143       delete[] chunks;
 144       chunks = new_chunks;
 145
 146       // Allocate new chunk for entries.
 147       chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
 148     }
 149   entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
 150   entry->key = key;
 151   entry->val = val;
 152   index->insert (lo, entry);
 153   hashTable[idx] = entry;
 154   entries++;
 155 }
 156
 157 template <typename Key_t, typename Value_t>
 158 Value_t
 159 DefaultMap<Key_t, Value_t>::get (Key_t key)
 160 {
 161   unsigned idx = hash (key) % HTABLE_SIZE;
 162   Entry *entry = hashTable[idx];
 163   if (entry && entry->key == key)
 164     return entry->val;
 165
 166   int lo = 0;
 167   int hi = entries - 1;
 168   while (lo <= hi)
 169     {
 170       int md = (lo + hi) / 2;
 171       entry = index->fetch (md);
 172       int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
 173       if (cmp < 0)
 174         lo = md + 1;
 175       else if (cmp > 0)
 176         hi = md - 1;
 177       else
 178         {
 179           hashTable[idx] = entry;
 180           return entry->val;
 181         }
 182     }
 183   return (Value_t) 0;
 184 }
 185
 186 template <typename Key_t, typename Value_t>
 187 Value_t
 188 DefaultMap<Key_t, Value_t>::get (Key_t key,
 189                                  typename Map<Key_t, Value_t>::Relation rel)
 190 {
 191   if (rel != Map<Key_t, Value_t>::REL_EQ)
 192     return (Value_t) 0;
 193   return get (key);
 194 }
 195
 196 template <typename Key_t, typename Value_t>
 197 Value_t
 198 DefaultMap<Key_t, Value_t>::remove (Key_t)
 199 {
 200   // Not implemented
 201   if (1)
 202     assert (0);
 203   return (Value_t) 0;
 204 }
 205
 206 template <typename Key_t, typename Value_t>
 207 Vector<Value_t> *
 208 DefaultMap<Key_t, Value_t>::values ()
 209 {
 210   Vector<Value_t> *vals = new Vector<Value_t>(entries);
 211   for (int i = 0; i < entries; ++i)
 212     {
 213       Entry *entry = index->fetch (i);
 214       vals->append (entry->val);
 215     }
 216   return vals;
 217 }
 218
 219 template <typename Key_t, typename Value_t>
 220 Vector<Key_t> *
 221 DefaultMap<Key_t, Value_t>::keySet ()
 222 {
 223   Vector<Key_t> *keys = new Vector<Key_t>(entries);
 224   for (int i = 0; i < entries; ++i)
 225     {
 226       Entry *entry = index->fetch (i);
 227       keys->append (entry->key);
 228     }
 229   return keys;
 230 }
 231
 232 #endif