gprofng: a new GNU profiler

top-level
	* Makefile.def: Add gprofng module.
	* configure.ac: Add --enable-gprofng option.
	* src-release.sh: Add gprofng.
	* Makefile.in: Regenerate.
	* configure: Regenerate.
	* gprofng: New directory.

binutils
	* MAINTAINERS: Add gprofng maintainer.
	* README-how-to-make-a-release: Add gprofng.

include.
	* collectorAPI.h: New file.
	* libcollector.h: New file.
	* libfcollector.h: New file.

1 files changed, 238 insertions, 0 deletions

diff --git a/gprofng/src/StringMap.h b/gprofng/src/StringMap.h
new file mode 100644
index 0000000..31898f4
--- /dev/null
+++ b/gprofng/src/StringMap.h
@@ -0,0 +1,238 @@
+/* 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.  */
+
+/*
+ *	String Map implementation.
+ */
+
+#ifndef _DBE_STRINGMAP_H
+#define _DBE_STRINGMAP_H
+
+#include <assert.h>
+#include <vec.h>
+#include <Map.h>
+#include <util.h>
+
+template <typename Value_t>
+class StringMap : public Map<const char*, Value_t>
+{
+public:
+
+  StringMap (int htable_size = 1024, int chunk_size = 16384);
+  ~StringMap ();
+  void clear ();
+  void put (const char *key, Value_t val);
+  Value_t get (const char *key);
+  Value_t get (const char *key, typename Map<const char*, Value_t>::Relation rel);
+  Value_t remove (const char*);
+  Vector<const char*> *keySet ();
+  Vector<Value_t> *values ();
+
+private:
+
+  static unsigned
+  hash (const char *key)
+  {
+    return (unsigned) crc64 (key, strlen (key));
+  }
+
+  struct Entry
+  {
+    char *key;
+    Value_t val;
+  };
+
+  int CHUNK_SIZE, HTABLE_SIZE;
+  int entries;
+  int nchunks;
+  Entry **chunks;
+  Vector<Entry*> *index;
+  Entry **hashTable;
+};
+
+template <typename Value_t>
+StringMap<Value_t>::StringMap (int htable_size, int chunk_size)
+{
+  HTABLE_SIZE = htable_size;
+  CHUNK_SIZE = chunk_size;
+  entries = 0;
+  nchunks = 0;
+  chunks = NULL;
+  index = new Vector<Entry*>;
+  hashTable = new Entry*[HTABLE_SIZE];
+  for (int i = 0; i < HTABLE_SIZE; i++)
+    hashTable[i] = NULL;
+}
+
+template <typename Value_t>
+StringMap<Value_t>::~StringMap ()
+{
+  for (int i = 0; i < entries; ++i)
+    {
+      Entry *entry = index->fetch (i);
+      free (entry->key);
+    }
+  for (int i = 0; i < nchunks; i++)
+    delete[] chunks[i];
+  delete[] chunks;
+  delete index;
+  delete[] hashTable;
+}
+
+template <typename Value_t>
+void
+StringMap<Value_t>::clear ()
+{
+  for (int i = 0; i < entries; ++i)
+    {
+      Entry *entry = index->fetch (i);
+      free (entry->key);
+    }
+  entries = 0;
+  index->reset ();
+  for (int i = 0; i < HTABLE_SIZE; i++)
+    hashTable[i] = NULL;
+}
+
+template <typename Value_t>
+void
+StringMap<Value_t>::put (const char *key, Value_t val)
+{
+  unsigned idx = hash (key) % HTABLE_SIZE;
+  Entry *entry = hashTable[idx];
+  if (entry && strcmp (entry->key, key) == 0)
+    {
+      entry->val = val;
+      return;
+    }
+  int lo = 0;
+  int hi = entries - 1;
+  while (lo <= hi)
+    {
+      int md = (lo + hi) / 2;
+      entry = index->fetch (md);
+      int cmp = strcmp (entry->key, key);
+      if (cmp < 0)
+	lo = md + 1;
+      else if (cmp > 0)
+	hi = md - 1;
+      else
+	{
+	  entry->val = val;
+	  return;
+	}
+    }
+  if (entries >= nchunks * CHUNK_SIZE)
+    {
+      nchunks++;
+
+      // Reallocate Entry chunk array
+      Entry **new_chunks = new Entry*[nchunks];
+      for (int i = 0; i < nchunks - 1; i++)
+	new_chunks[i] = chunks[i];
+      delete[] chunks;
+      chunks = new_chunks;
+
+      // Allocate new chunk for entries.
+      chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
+    }
+  entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
+  entry->key = strdup (key);
+  entry->val = val;
+  index->insert (lo, entry);
+  hashTable[idx] = entry;
+  entries++;
+}
+
+template <typename Value_t>
+Value_t
+StringMap<Value_t>::get (const char *key)
+{
+  unsigned idx = hash (key) % HTABLE_SIZE;
+  Entry *entry = hashTable[idx];
+  if (entry && strcmp (entry->key, key) == 0)
+    return entry->val;
+  int lo = 0;
+  int hi = entries - 1;
+  while (lo <= hi)
+    {
+      int md = (lo + hi) / 2;
+      entry = index->fetch (md);
+      int cmp = strcmp (entry->key, key);
+      if (cmp < 0)
+	lo = md + 1;
+      else if (cmp > 0)
+	hi = md - 1;
+      else
+	{
+	  hashTable[idx] = entry;
+	  return entry->val;
+	}
+    }
+  return (Value_t) 0;
+}
+
+template <typename Value_t>
+Value_t
+StringMap<Value_t>::get (const char *key, typename Map<const char*,
+			 Value_t>::Relation rel)
+{
+  if (rel != Map<const char*, Value_t>::REL_EQ)
+    return (Value_t) 0;
+  return get (key);
+}
+
+template <typename Value_t>
+Value_t
+StringMap<Value_t>::remove (const char*)
+{
+  // Not implemented
+  if (1)
+    assert (0);
+  return (Value_t) 0;
+}
+
+template <typename Value_t>
+Vector<Value_t> *
+StringMap<Value_t>::values ()
+{
+  Vector<Value_t> *vals = new Vector<Value_t>(entries);
+  for (int i = 0; i < entries; ++i)
+    {
+      Entry *entry = index->fetch (i);
+      vals->append (entry->val);
+    }
+  return vals;
+}
+
+template <typename Value_t>
+Vector<const char*> *
+StringMap<Value_t>::keySet ()
+{
+  Vector<const char*> *keys = new Vector<const char*>(entries);
+  for (int i = 0; i < entries; ++i)
+    {
+      Entry *entry = index->fetch (i);
+      keys->append (entry->key);
+    }
+  return keys;
+}
+
+#endif