aboutsummaryrefslogtreecommitdiff
path: root/gprofng/src/HashMap.h
diff options
context:
space:
mode:
Diffstat (limited to 'gprofng/src/HashMap.h')
-rw-r--r--gprofng/src/HashMap.h435
1 files changed, 435 insertions, 0 deletions
diff --git a/gprofng/src/HashMap.h b/gprofng/src/HashMap.h
new file mode 100644
index 0000000..f66a6fe
--- /dev/null
+++ b/gprofng/src/HashMap.h
@@ -0,0 +1,435 @@
+/* Copyright (C) 2021 Free Software Foundation, Inc.
+ Contributed by Oracle.
+
+ This file is part of GNU Binutils.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, 51 Franklin Street - Fifth Floor, Boston,
+ MA 02110-1301, USA. */
+
+// java.util.HashMap
+
+#ifndef _DBE_HASHMAP_H
+#define _DBE_HASHMAP_H
+
+#include "vec.h"
+#include "util.h"
+#include "StringBuilder.h"
+#include "Histable.h"
+#include "MemObject.h"
+
+template <typename Key_t> inline int get_hash_code (Key_t a);
+template <typename Key_t> inline bool is_equals (Key_t a, Key_t b);
+template <typename Key_t> inline Key_t copy_key (Key_t a);
+template <typename Key_t> inline void delete_key (Key_t a);
+
+// Specialization for char*
+template<> inline int
+get_hash_code (char *a)
+{
+ return (int) (crc64 (a, strlen (a)) & 0x7fffffff);
+}
+
+template<> inline bool
+is_equals (char *a, char *b)
+{
+ return dbe_strcmp (a, b) == 0;
+}
+
+template<> inline char *
+copy_key (char *a)
+{
+ return dbe_strdup (a);
+}
+
+template<> inline void
+delete_key (char *a)
+{
+ return free (a);
+}
+
+template<> inline int
+get_hash_code (uint64_t a)
+{
+ return (int) (a & 0x7fffffff);
+}
+
+template<> inline bool
+is_equals (uint64_t a, uint64_t b)
+{
+ return a == b;
+}
+
+template<> inline uint64_t
+copy_key (uint64_t a)
+{
+ return a;
+}
+
+template<> inline void
+delete_key (uint64_t a)
+{
+ a = a;
+}
+
+template<> inline int
+get_hash_code (Histable* a)
+{
+ return (int) (a->id & 0x7fffffff);
+}
+
+template<> inline bool
+is_equals (Histable* a, Histable* b)
+{
+ return a == b;
+}
+
+template<> inline Histable*
+copy_key (Histable* a)
+{
+ return a;
+}
+
+template<> inline void
+delete_key (Histable* a)
+{
+ a->id = a->id;
+}
+
+template<> inline int
+get_hash_code (MemObj* a)
+{
+ return (int) (a->id & 0x7fffffff);
+}
+
+template<> inline bool
+is_equals (MemObj* a, MemObj* b)
+{
+ return a == b;
+}
+
+template<> inline MemObj*
+copy_key (MemObj* a)
+{
+ return a;
+}
+
+template<> inline void
+delete_key (MemObj* a)
+{
+ a->id = a->id;
+}
+
+template <typename Key_t, typename Value_t>
+class HashMap
+{
+public:
+ HashMap (int initialCapacity = 0);
+
+ ~HashMap ()
+ {
+ clear ();
+ delete vals;
+ delete[] hashTable;
+ }
+
+ Value_t put (Key_t key, Value_t val);
+ Value_t get (Key_t key);
+ Value_t get (Key_t key, Value_t val); // Create a new map if key is not here
+ void clear ();
+ Value_t remove (Key_t);
+ Vector<Value_t> *values (Key_t key); // Return a list of values for 'key'
+
+ bool
+ containsKey (Key_t key)
+ {
+ Value_t p = get (key);
+ return p != NULL;
+ };
+
+ Vector<Value_t> *
+ values ()
+ {
+ return vals;
+ }
+
+ void
+ reset ()
+ {
+ clear ();
+ }
+
+ int
+ get_phaseIdx ()
+ {
+ return phaseIdx;
+ }
+
+ void
+ set_phaseIdx (int phase)
+ {
+ if (phase == 0) clear ();
+ phaseIdx = phase;
+ }
+ char *dump ();
+
+private:
+
+ enum
+ {
+ HASH_SIZE = 511,
+ MAX_HASH_SIZE = 1048575
+ };
+
+ typedef struct Hash
+ {
+ Key_t key;
+ Value_t val;
+ struct Hash *next;
+ } Hash_t;
+
+ void resize ();
+
+ int
+ hashCode (Key_t key)
+ {
+ return get_hash_code (key) % hash_sz;
+ }
+
+ bool
+ equals (Key_t a, Key_t b)
+ {
+ return is_equals (a, b);
+ }
+
+ Key_t
+ copy (Key_t key)
+ {
+ return copy_key (key);
+ }
+
+ Hash_t **hashTable;
+ Vector<Value_t> *vals;
+ int phaseIdx;
+ int hash_sz;
+ int nelem;
+};
+
+template <typename Key_t, typename Value_t>
+HashMap<Key_t, Value_t>
+::HashMap (int initialCapacity)
+{
+ if (initialCapacity > 0)
+ vals = new Vector<Value_t>(initialCapacity);
+ else
+ vals = new Vector<Value_t>();
+ phaseIdx = 0;
+ nelem = 0;
+ hash_sz = HASH_SIZE;
+ hashTable = new Hash_t*[hash_sz];
+ for (int i = 0; i < hash_sz; i++)
+ hashTable[i] = NULL;
+}
+
+template <typename Key_t, typename Value_t>
+void
+HashMap<Key_t, Value_t>::clear ()
+{
+ vals->reset ();
+ phaseIdx = 0;
+ nelem = 0;
+ for (int i = 0; i < hash_sz; i++)
+ {
+ Hash_t *next;
+ for (Hash_t *p = hashTable[i]; p; p = next)
+ {
+ next = p->next;
+ delete_key (p->key);
+ delete p;
+ }
+ hashTable[i] = NULL;
+ }
+}
+
+template <typename Key_t, typename Value_t>
+void
+HashMap<Key_t, Value_t>::resize ()
+{
+ int old_hash_sz = hash_sz;
+ hash_sz = old_hash_sz * 2 + 1;
+ Hash_t **old_hash_table = hashTable;
+ hashTable = new Hash_t*[hash_sz];
+ for (int i = 0; i < hash_sz; i++)
+ hashTable[i] = NULL;
+ nelem = 0;
+ for (int i = 0; i < old_hash_sz; i++)
+ {
+ if (old_hash_table[i] != NULL)
+ {
+ Hash_t *old_p;
+ Hash_t *p = old_hash_table[i];
+ while (p != NULL)
+ {
+ put (p->key, p->val);
+ old_p = p;
+ p = p->next;
+ delete old_p;
+ }
+ }
+ }
+ delete[] old_hash_table;
+}
+
+template <typename Key_t, typename Value_t>
+Value_t
+HashMap<Key_t, Value_t>::get (Key_t key)
+{
+ int hash_code = hashCode (key);
+ for (Hash_t *p = hashTable[hash_code]; p; p = p->next)
+ if (equals (key, p->key))
+ return p->val;
+ return NULL;
+}
+
+template <typename Key_t, typename Value_t>
+Vector<Value_t> *
+HashMap<Key_t, Value_t>::values (Key_t key)
+{
+ Vector<Value_t> *list = new Vector<Value_t>();
+ int hash_code = hashCode (key);
+ for (Hash_t *p = hashTable[hash_code]; p; p = p->next)
+ {
+ if (equals (key, p->key))
+ list->append (p->val);
+ }
+ return list;
+}
+
+template <typename Key_t, typename Value_t>
+Value_t
+HashMap<Key_t, Value_t>::get (const Key_t key, Value_t val)
+{
+ int hash_code = hashCode (key);
+ Hash_t *p, *first = NULL;
+ for (p = hashTable[hash_code]; p; p = p->next)
+ {
+ if (equals (key, p->key))
+ {
+ if (first == NULL)
+ first = p;
+ if (val == p->val)
+ return first->val; // Always return the first value
+ }
+ }
+ vals->append (val);
+ p = new Hash_t ();
+ p->val = val;
+ p->key = copy (key);
+ if (first)
+ {
+ p->next = first->next;
+ first->next = p;
+ return first->val; // Always return the first value
+ }
+ else
+ {
+ p->next = hashTable[hash_code];
+ hashTable[hash_code] = p;
+ return val;
+ }
+}
+
+template <typename Key_t, typename Value_t>
+Value_t
+HashMap<Key_t, Value_t>::remove (Key_t key)
+{
+ int hash_code = hashCode (key);
+ Value_t val = NULL;
+ for (Hash_t *prev = NULL, *p = hashTable[hash_code]; p != NULL;)
+ {
+ if (equals (key, p->key))
+ {
+ if (prev == NULL)
+ hashTable[hash_code] = p->next;
+ else
+ prev->next = p->next;
+ if (val == NULL)
+ val = p->val;
+ delete_key (p->key);
+ delete p;
+ }
+ else
+ {
+ prev = p;
+ p = p->next;
+ }
+ }
+ return val;
+}
+
+template <typename Key_t, typename Value_t>
+Value_t
+HashMap<Key_t, Value_t>::put (Key_t key, Value_t val)
+{
+ int hash_code = hashCode (key);
+ vals->append (val);
+ for (Hash_t *p = hashTable[hash_code]; p != NULL; p = p->next)
+ {
+ if (equals (key, p->key))
+ {
+ Value_t v = p->val;
+ p->val = val;
+ return v;
+ }
+ }
+ Hash_t *p = new Hash_t ();
+ p->val = val;
+ p->key = copy (key);
+ p->next = hashTable[hash_code];
+ hashTable[hash_code] = p;
+ nelem++;
+ if (nelem == hash_sz)
+ resize ();
+ return val;
+}
+
+template <typename Key_t, typename Value_t>
+char *
+HashMap<Key_t, Value_t>::dump ()
+{
+ StringBuilder sb;
+ char buf[128];
+ snprintf (buf, sizeof (buf), "HashMap: size=%d ##########\n", vals->size ());
+ sb.append (buf);
+ for (int i = 0; i < hash_sz; i++)
+ {
+ if (hashTable[i] == NULL)
+ continue;
+ snprintf (buf, sizeof (buf), "%3d:", i);
+ sb.append (buf);
+ char *s = NTXT (" ");
+ for (Hash_t *p = hashTable[i]; p; p = p->next)
+ {
+ sb.append (s);
+ s = NTXT (" ");
+ sb.append (p->key);
+ snprintf (buf, sizeof (buf), " --> 0x%p '%s'\n",
+ p->val, p->val->get_name ());
+ sb.append (buf);
+ }
+ }
+ return sb.toString ();
+}
+
+#endif // _DBE_HASHMAP_H
generated by cgit v1.1 at 2025-03-06 15:16:37 +0000