gprofng/src/HashMap.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 // java.util.HashMap
  22
  23 #ifndef _DBE_HASHMAP_H
  24 #define _DBE_HASHMAP_H
  25
  26 #include "vec.h"
  27 #include "util.h"
  28 #include "StringBuilder.h"
  29 #include "Histable.h"
  30 #include "MemObject.h"
  31
  32 template <typename Key_t> inline int get_hash_code (Key_t a);
  33 template <typename Key_t> inline bool is_equals (Key_t a, Key_t b);
  34 template <typename Key_t> inline Key_t copy_key (Key_t a);
  35 template <typename Key_t> inline void delete_key (Key_t a);
  36
  37 // Specialization for char*
  38 template<> inline int
  39 get_hash_code (char *a)
  40 {
  41   return (int) (crc64 (a, strlen (a)) & 0x7fffffff);
  42 }
  43
  44 template<> inline bool
  45 is_equals (char *a, char *b)
  46 {
  47   return dbe_strcmp (a, b) == 0;
  48 }
  49
  50 template<> inline char *
  51 copy_key (char *a)
  52 {
  53   return dbe_strdup (a);
  54 }
  55
  56 template<> inline void
  57 delete_key (char *a)
  58 {
  59   return free (a);
  60 }
  61
  62 template<> inline int
  63 get_hash_code (uint64_t a)
  64 {
  65   return (int) (a & 0x7fffffff);
  66 }
  67
  68 template<> inline bool
  69 is_equals (uint64_t a, uint64_t b)
  70 {
  71   return a == b;
  72 }
  73
  74 template<> inline uint64_t
  75 copy_key (uint64_t a)
  76 {
  77   return a;
  78 }
  79
  80 template<> inline void
  81 delete_key (uint64_t a)
  82 {
  83   a = a;
  84 }
  85
  86 template<> inline int
  87 get_hash_code (Histable* a)
  88 {
  89   return (int) (a->id & 0x7fffffff);
  90 }
  91
  92 template<> inline bool
  93 is_equals (Histable* a, Histable* b)
  94 {
  95   return a == b;
  96 }
  97
  98 template<> inline Histable*
  99 copy_key (Histable* a)
 100 {
 101   return a;
 102 }
 103
 104 template<> inline void
 105 delete_key (Histable* a)
 106 {
 107   a->id = a->id;
 108 }
 109
 110 template<> inline int
 111 get_hash_code (MemObj* a)
 112 {
 113   return (int) (a->id & 0x7fffffff);
 114 }
 115
 116 template<> inline bool
 117 is_equals (MemObj* a, MemObj* b)
 118 {
 119   return a == b;
 120 }
 121
 122 template<> inline MemObj*
 123 copy_key (MemObj* a)
 124 {
 125   return a;
 126 }
 127
 128 template<> inline void
 129 delete_key (MemObj* a)
 130 {
 131   a->id = a->id;
 132 }
 133
 134 template <typename Key_t, typename Value_t>
 135 class HashMap
 136 {
 137 public:
 138   HashMap (int initialCapacity = 0);
 139
 140   ~HashMap ()
 141   {
 142     clear ();
 143     delete vals;
 144     delete[] hashTable;
 145   }
 146
 147   Value_t put (Key_t key, Value_t val);
 148   Value_t get (Key_t key);
 149   Value_t get (Key_t key, Value_t val); // Create a new map if key is not here
 150   void clear ();
 151   Value_t remove (Key_t);
 152   Vector<Value_t> *values (Key_t key);  // Return a list of values for 'key'
 153
 154   bool
 155   containsKey (Key_t key)
 156   {
 157     Value_t p = get (key);
 158     return p != NULL;
 159   };
 160
 161   Vector<Value_t> *
 162   values ()
 163   {
 164     return vals;
 165   }
 166
 167   void
 168   reset ()
 169   {
 170     clear ();
 171   }
 172
 173   int
 174   get_phaseIdx ()
 175   {
 176     return phaseIdx;
 177   }
 178
 179   void
 180   set_phaseIdx (int phase)
 181   {
 182     if (phase == 0) clear ();
 183     phaseIdx = phase;
 184   }
 185   char *dump ();
 186
 187 private:
 188
 189   enum
 190   {
 191     HASH_SIZE       = 511,
 192     MAX_HASH_SIZE   = 1048575
 193   };
 194
 195   typedef struct Hash
 196   {
 197     Key_t key;
 198     Value_t val;
 199     struct Hash *next;
 200   } Hash_t;
 201
 202   void resize ();
 203
 204   int
 205   hashCode (Key_t key)
 206   {
 207     return get_hash_code (key) % hash_sz;
 208   }
 209
 210   bool
 211   equals (Key_t a, Key_t b)
 212   {
 213     return is_equals (a, b);
 214   }
 215
 216   Key_t
 217   copy (Key_t key)
 218   {
 219     return copy_key (key);
 220   }
 221
 222   Hash_t **hashTable;
 223   Vector<Value_t> *vals;
 224   int phaseIdx;
 225   int hash_sz;
 226   int nelem;
 227 };
 228
 229 template <typename Key_t, typename Value_t>
 230 HashMap<Key_t, Value_t>
 231 ::HashMap (int initialCapacity)
 232 {
 233   if (initialCapacity > 0)
 234     vals = new Vector<Value_t>(initialCapacity);
 235   else
 236     vals = new Vector<Value_t>();
 237   phaseIdx = 0;
 238   nelem = 0;
 239   hash_sz = HASH_SIZE;
 240   hashTable = new Hash_t*[hash_sz];
 241   for (int i = 0; i < hash_sz; i++)
 242     hashTable[i] = NULL;
 243 }
 244
 245 template <typename Key_t, typename Value_t>
 246 void
 247 HashMap<Key_t, Value_t>::clear ()
 248 {
 249   vals->reset ();
 250   phaseIdx = 0;
 251   nelem = 0;
 252   for (int i = 0; i < hash_sz; i++)
 253     {
 254       Hash_t *next;
 255       for (Hash_t *p = hashTable[i]; p; p = next)
 256         {
 257           next = p->next;
 258           delete_key (p->key);
 259           delete p;
 260         }
 261       hashTable[i] = NULL;
 262     }
 263 }
 264
 265 template <typename Key_t, typename Value_t>
 266 void
 267 HashMap<Key_t, Value_t>::resize ()
 268 {
 269   int old_hash_sz = hash_sz;
 270   hash_sz = old_hash_sz * 2 + 1;
 271   Hash_t **old_hash_table = hashTable;
 272   hashTable = new Hash_t*[hash_sz];
 273   for (int i = 0; i < hash_sz; i++)
 274     hashTable[i] = NULL;
 275   nelem = 0;
 276   for (int i = 0; i < old_hash_sz; i++)
 277     {
 278       if (old_hash_table[i] != NULL)
 279         {
 280           Hash_t *old_p;
 281           Hash_t *p = old_hash_table[i];
 282           while (p != NULL)
 283             {
 284               put (p->key, p->val);
 285               old_p = p;
 286               p = p->next;
 287               delete old_p;
 288             }
 289         }
 290     }
 291   delete[] old_hash_table;
 292 }
 293
 294 template <typename Key_t, typename Value_t>
 295 Value_t
 296 HashMap<Key_t, Value_t>::get (Key_t key)
 297 {
 298   int hash_code = hashCode (key);
 299   for (Hash_t *p = hashTable[hash_code]; p; p = p->next)
 300     if (equals (key, p->key))
 301       return p->val;
 302   return NULL;
 303 }
 304
 305 template <typename Key_t, typename Value_t>
 306 Vector<Value_t> *
 307 HashMap<Key_t, Value_t>::values (Key_t key)
 308 {
 309   Vector<Value_t> *list = new Vector<Value_t>();
 310   int hash_code = hashCode (key);
 311   for (Hash_t *p = hashTable[hash_code]; p; p = p->next)
 312     {
 313       if (equals (key, p->key))
 314         list->append (p->val);
 315     }
 316   return list;
 317 }
 318
 319 template <typename Key_t, typename Value_t>
 320 Value_t
 321 HashMap<Key_t, Value_t>::get (const Key_t key, Value_t val)
 322 {
 323   int hash_code = hashCode (key);
 324   Hash_t *p, *first = NULL;
 325   for (p = hashTable[hash_code]; p; p = p->next)
 326     {
 327       if (equals (key, p->key))
 328         {
 329           if (first == NULL)
 330             first = p;
 331           if (val == p->val)
 332             return first->val; // Always return the first value
 333         }
 334     }
 335   vals->append (val);
 336   p = new Hash_t ();
 337   p->val = val;
 338   p->key = copy (key);
 339   if (first)
 340     {
 341       p->next = first->next;
 342       first->next = p;
 343       return first->val; // Always return the first value
 344     }
 345   else
 346     {
 347       p->next = hashTable[hash_code];
 348       hashTable[hash_code] = p;
 349       return val;
 350     }
 351 }
 352
 353 template <typename Key_t, typename Value_t>
 354 Value_t
 355 HashMap<Key_t, Value_t>::remove (Key_t key)
 356 {
 357   int hash_code = hashCode (key);
 358   Value_t val = NULL;
 359   for (Hash_t *prev = NULL, *p = hashTable[hash_code]; p != NULL;)
 360     {
 361       if (equals (key, p->key))
 362         {
 363           if (prev == NULL)
 364             hashTable[hash_code] = p->next;
 365           else
 366             prev->next = p->next;
 367           if (val == NULL)
 368             val = p->val;
 369           delete_key (p->key);
 370           delete p;
 371         }
 372       else
 373         {
 374           prev = p;
 375           p = p->next;
 376         }
 377     }
 378   return val;
 379 }
 380
 381 template <typename Key_t, typename Value_t>
 382 Value_t
 383 HashMap<Key_t, Value_t>::put (Key_t key, Value_t val)
 384 {
 385   int hash_code = hashCode (key);
 386   vals->append (val);
 387   for (Hash_t *p = hashTable[hash_code]; p != NULL; p = p->next)
 388     {
 389       if (equals (key, p->key))
 390         {
 391           Value_t v = p->val;
 392           p->val = val;
 393           return v;
 394         }
 395     }
 396   Hash_t *p = new Hash_t ();
 397   p->val = val;
 398   p->key = copy (key);
 399   p->next = hashTable[hash_code];
 400   hashTable[hash_code] = p;
 401   nelem++;
 402   if (nelem == hash_sz)
 403     resize ();
 404   return val;
 405 }
 406
 407 template <typename Key_t, typename Value_t>
 408 char *
 409 HashMap<Key_t, Value_t>::dump ()
 410 {
 411   StringBuilder sb;
 412   char buf[128];
 413   snprintf (buf, sizeof (buf), "HashMap: size=%d ##########\n", vals->size ());
 414   sb.append (buf);
 415   for (int i = 0; i < hash_sz; i++)
 416     {
 417       if (hashTable[i] == NULL)
 418         continue;
 419       snprintf (buf, sizeof (buf), "%3d:", i);
 420       sb.append (buf);
 421       char *s = NTXT (" ");
 422       for (Hash_t *p = hashTable[i]; p; p = p->next)
 423         {
 424           sb.append (s);
 425           s = NTXT ("     ");
 426           sb.append (p->key);
 427           snprintf (buf, sizeof (buf), " --> 0x%p '%s'\n",
 428                     p->val, p->val->get_name ());
 429           sb.append (buf);
 430         }
 431     }
 432   return sb.toString ();
 433 }
 434
 435 #endif // _DBE_HASHMAP_H