gprofng/src/CacheMap.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 /*
  22  *  Cache Map implementation.
  23  *
  24  *  Cache Map makes the following assumptions:
  25  *    - Cache Map is used for very fast but not guaranteed mapping;
  26  *    - only REL_EQ Relation can be used;
  27  *    - all objects used as keys or values has to be managed
  28  *      outside CacheMap (f.e. deletion);
  29  *    - (Key_t)0 is invalid key;
  30  *    - (Value_t)0 is invalid value;
  31  *    - <TBC>
  32  */
  33
  34 #ifndef _DBE_CACHEMAP_H
  35 #define _DBE_CACHEMAP_H
  36
  37 #include <assert.h>
  38 #include <vec.h>
  39 #include <Map.h>
  40
  41 template <typename Key_t, typename Value_t>
  42 class CacheMap : public Map<Key_t, Value_t>
  43 {
  44 public:
  45
  46   CacheMap ();
  47   ~CacheMap ();
  48   void put (Key_t key, Value_t val);
  49   Value_t get (Key_t key);
  50   Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
  51   Value_t
  52   remove (Key_t key);
  53
  54 private:
  55
  56   struct Entry
  57   {
  58     Key_t key;
  59     Value_t val;
  60
  61     Entry ()
  62     {
  63       key = (Key_t) 0;
  64     }
  65   };
  66
  67   static const int INIT_SIZE;
  68   static const int MAX_SIZE;
  69
  70   static unsigned hash (Key_t key);
  71   Entry *getEntry (Key_t key);
  72
  73   int cursize;
  74   int nputs;
  75   int nchunks;
  76   Entry **chunks;
  77 };
  78
  79 template <typename Key_t, typename Value_t>
  80 const int CacheMap<Key_t, Value_t>::INIT_SIZE = 1 << 14;
  81 template <typename Key_t, typename Value_t>
  82 const int CacheMap<Key_t, Value_t>::MAX_SIZE = 1 << 20;
  83
  84 template <typename Key_t, typename Value_t>CacheMap<Key_t, Value_t>
  85 ::CacheMap ()
  86 {
  87   cursize = INIT_SIZE;
  88   chunks = new Entry*[32];
  89   nchunks = 0;
  90   chunks[nchunks++] = new Entry[cursize];
  91   nputs = 0;
  92 }
  93
  94 template <typename Key_t, typename Value_t>
  95 CacheMap<Key_t, Value_t>::~CacheMap ()
  96 {
  97   for (int i = 0; i < nchunks; i++)
  98     delete[] chunks[i];
  99   delete[] chunks;
 100 }
 101
 102 template <typename Key_t, typename Value_t>
 103 unsigned
 104 CacheMap<Key_t, Value_t>::hash (Key_t key)
 105 {
 106   unsigned h = (unsigned) key ^ (unsigned) (key >> 32);
 107   h ^= (h >> 20) ^ (h >> 12);
 108   return h ^ (h >> 7) ^ (h >> 4);
 109 }
 110
 111 template <typename Key_t, typename Value_t>
 112 void
 113 CacheMap<Key_t, Value_t>::put (Key_t key, Value_t val)
 114 {
 115   if (nputs >= cursize && cursize < MAX_SIZE)
 116     {
 117       // Allocate new chunk for entries.
 118       chunks[nchunks++] = new Entry[cursize];
 119       cursize *= 2;
 120
 121       // Copy all old entries to the newly allocated chunk
 122       Entry *newchunk = chunks[nchunks - 1];
 123       int prevsz = 0;
 124       int nextsz = INIT_SIZE;
 125       for (int i = 0; i < nchunks - 1; i++)
 126         {
 127           Entry *oldchunk = chunks[i];
 128           for (int j = prevsz; j < nextsz; j++)
 129             newchunk[j] = oldchunk[j - prevsz];
 130           prevsz = nextsz;
 131           nextsz *= 2;
 132         }
 133     }
 134   Entry *entry = getEntry (key);
 135   entry->key = key;
 136   entry->val = val;
 137   nputs++;
 138 }
 139
 140 template <typename Key_t, typename Value_t>
 141 typename CacheMap<Key_t, Value_t>::Entry *
 142 CacheMap<Key_t, Value_t>::getEntry (Key_t key)
 143 {
 144   unsigned idx = hash (key);
 145   int i = nchunks - 1;
 146   int j = cursize / 2;
 147   for (; i > 0; i -= 1, j /= 2)
 148     if (idx & j)
 149       break;
 150   if (i == 0)
 151     j *= 2;
 152   return &chunks[i][idx & (j - 1)];
 153 }
 154
 155 template <typename Key_t, typename Value_t>
 156 Value_t
 157 CacheMap<Key_t, Value_t>::get (Key_t key)
 158 {
 159   Entry *entry = getEntry (key);
 160   return entry->key == key ? entry->val : (Value_t) 0;
 161 }
 162
 163 template <typename Key_t, typename Value_t>
 164 Value_t
 165 CacheMap<Key_t, Value_t>::get (Key_t key, typename Map<Key_t, Value_t>::Relation rel)
 166 {
 167   if (rel != Map<Key_t, Value_t>::REL_EQ)
 168     return (Value_t) 0;
 169   return get (key);
 170 }
 171
 172 template <typename Key_t, typename Value_t>
 173 Value_t
 174 CacheMap<Key_t, Value_t>::remove (Key_t key)
 175 {
 176   Entry *entry = getEntry (key);
 177   Value_t res = (Value_t) 0;
 178   if (entry->key == key)
 179     {
 180       res = entry->val;
 181       entry->val = (Value_t) 0;
 182     }
 183   return res;
 184 }
 185
 186 #endif