gprofng/src/StringMap.h

   1 /* Copyright (C) 2021-2024 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  *      String Map implementation.
  23  */
  24
  25 #ifndef _DBE_STRINGMAP_H
  26 #define _DBE_STRINGMAP_H
  27
  28 #include <assert.h>
  29 #include <vec.h>
  30 #include <Map.h>
  31 #include <util.h>
  32
  33 template <typename Value_t>
  34 class StringMap : public Map<const char*, Value_t>
  35 {
  36 public:
  37
  38   StringMap (int htable_size = 1024, int chunk_size = 16384);
  39   ~StringMap ();
  40   void clear ();
  41   void put (const char *key, Value_t val);
  42   Value_t get (const char *key);
  43   Value_t get (const char *key, typename Map<const char*, Value_t>::Relation rel);
  44   Value_t remove (const char*);
  45   Vector<const char*> *keySet ();
  46   Vector<Value_t> *values ();
  47
  48 private:
  49
  50   static unsigned
  51   hash (const char *key)
  52   {
  53     return (unsigned) crc64 (key, strlen (key));
  54   }
  55
  56   struct Entry
  57   {
  58     char *key;
  59     Value_t val;
  60   };
  61
  62   int CHUNK_SIZE, HTABLE_SIZE;
  63   int entries;
  64   int nchunks;
  65   Entry **chunks;
  66   Vector<Entry*> *index;
  67   Entry **hashTable;
  68 };
  69
  70 template <typename Value_t>
  71 StringMap<Value_t>::StringMap (int htable_size, int chunk_size)
  72 {
  73   HTABLE_SIZE = htable_size;
  74   CHUNK_SIZE = chunk_size;
  75   entries = 0;
  76   nchunks = 0;
  77   chunks = NULL;
  78   index = new Vector<Entry*>;
  79   hashTable = new Entry*[HTABLE_SIZE];
  80   for (int i = 0; i < HTABLE_SIZE; i++)
  81     hashTable[i] = NULL;
  82 }
  83
  84 template <typename Value_t>
  85 StringMap<Value_t>::~StringMap ()
  86 {
  87   for (int i = 0; i < entries; ++i)
  88     {
  89       Entry *entry = index->fetch (i);
  90       free (entry->key);
  91     }
  92   for (int i = 0; i < nchunks; i++)
  93     delete[] chunks[i];
  94   delete[] chunks;
  95   delete index;
  96   delete[] hashTable;
  97 }
  98
  99 template <typename Value_t>
 100 void
 101 StringMap<Value_t>::clear ()
 102 {
 103   for (int i = 0; i < entries; ++i)
 104     {
 105       Entry *entry = index->fetch (i);
 106       free (entry->key);
 107     }
 108   entries = 0;
 109   index->reset ();
 110   for (int i = 0; i < HTABLE_SIZE; i++)
 111     hashTable[i] = NULL;
 112 }
 113
 114 template <typename Value_t>
 115 void
 116 StringMap<Value_t>::put (const char *key, Value_t val)
 117 {
 118   unsigned idx = hash (key) % HTABLE_SIZE;
 119   Entry *entry = hashTable[idx];
 120   if (entry && strcmp (entry->key, key) == 0)
 121     {
 122       entry->val = val;
 123       return;
 124     }
 125   int lo = 0;
 126   int hi = entries - 1;
 127   while (lo <= hi)
 128     {
 129       int md = (lo + hi) / 2;
 130       entry = index->fetch (md);
 131       int cmp = strcmp (entry->key, key);
 132       if (cmp < 0)
 133         lo = md + 1;
 134       else if (cmp > 0)
 135         hi = md - 1;
 136       else
 137         {
 138           entry->val = val;
 139           return;
 140         }
 141     }
 142   if (entries >= nchunks * CHUNK_SIZE)
 143     {
 144       nchunks++;
 145
 146       // Reallocate Entry chunk array
 147       Entry **new_chunks = new Entry*[nchunks];
 148       for (int i = 0; i < nchunks - 1; i++)
 149         new_chunks[i] = chunks[i];
 150       delete[] chunks;
 151       chunks = new_chunks;
 152
 153       // Allocate new chunk for entries.
 154       chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
 155     }
 156   entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
 157   entry->key = strdup (key);
 158   entry->val = val;
 159   index->insert (lo, entry);
 160   hashTable[idx] = entry;
 161   entries++;
 162 }
 163
 164 template <typename Value_t>
 165 Value_t
 166 StringMap<Value_t>::get (const char *key)
 167 {
 168   unsigned idx = hash (key) % HTABLE_SIZE;
 169   Entry *entry = hashTable[idx];
 170   if (entry && strcmp (entry->key, key) == 0)
 171     return entry->val;
 172   int lo = 0;
 173   int hi = entries - 1;
 174   while (lo <= hi)
 175     {
 176       int md = (lo + hi) / 2;
 177       entry = index->fetch (md);
 178       int cmp = strcmp (entry->key, key);
 179       if (cmp < 0)
 180         lo = md + 1;
 181       else if (cmp > 0)
 182         hi = md - 1;
 183       else
 184         {
 185           hashTable[idx] = entry;
 186           return entry->val;
 187         }
 188     }
 189   return (Value_t) 0;
 190 }
 191
 192 template <typename Value_t>
 193 Value_t
 194 StringMap<Value_t>::get (const char *key, typename Map<const char*,
 195                          Value_t>::Relation rel)
 196 {
 197   if (rel != Map<const char*, Value_t>::REL_EQ)
 198     return (Value_t) 0;
 199   return get (key);
 200 }
 201
 202 template <typename Value_t>
 203 Value_t
 204 StringMap<Value_t>::remove (const char*)
 205 {
 206   // Not implemented
 207   if (1)
 208     assert (0);
 209   return (Value_t) 0;
 210 }
 211
 212 template <typename Value_t>
 213 Vector<Value_t> *
 214 StringMap<Value_t>::values ()
 215 {
 216   Vector<Value_t> *vals = new Vector<Value_t>(entries);
 217   for (int i = 0; i < entries; ++i)
 218     {
 219       Entry *entry = index->fetch (i);
 220       vals->append (entry->val);
 221     }
 222   return vals;
 223 }
 224
 225 template <typename Value_t>
 226 Vector<const char*> *
 227 StringMap<Value_t>::keySet ()
 228 {
 229   Vector<const char*> *keys = new Vector<const char*>(entries);
 230   for (int i = 0; i < entries; ++i)
 231     {
 232       Entry *entry = index->fetch (i);
 233       keys->append (entry->key);
 234     }
 235   return keys;
 236 }
 237
 238 #endif