aboutsummaryrefslogtreecommitdiff
path: root/gprofng/src/vec.h
diff options
context:
space:
mode:
Diffstat (limited to 'gprofng/src/vec.h')
-rw-r--r--gprofng/src/vec.h524
1 files changed, 524 insertions, 0 deletions
diff --git a/gprofng/src/vec.h b/gprofng/src/vec.h
new file mode 100644
index 0000000..28b1800c
--- /dev/null
+++ b/gprofng/src/vec.h
@@ -0,0 +1,524 @@
+/* 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. */
+
+#ifndef _PERFAN_VEC_H
+#define _PERFAN_VEC_H
+
+#include <assert.h>
+#include <inttypes.h>
+#include <string.h>
+#include <stdlib.h>
+
+// This package implements a vector of items.
+
+#define Destroy(x) if (x) { (x)->destroy(); delete (x); (x) = NULL; }
+#define VecSize(x) ((x) ? (x)->size() : 0)
+
+void destroy (void *vec); // Free up the "two-dimension" Vectors
+
+typedef int (*CompareFunc)(const void*, const void*);
+typedef int (*ExtCompareFunc)(const void*, const void*, const void*);
+typedef int (*SearchFunc)(char*, char*);
+
+extern "C"
+{
+ typedef int (*StdCompareFunc)(const void*, const void*);
+}
+
+enum Search_type
+{
+ LINEAR,
+ BINARY,
+ HASH
+};
+
+enum Direction
+{
+ FORWARD,
+ REVERSE
+};
+
+enum VecType
+{
+ VEC_VOID = 0,
+ VEC_INTEGER,
+ VEC_CHAR,
+ VEC_BOOL,
+ VEC_DOUBLE,
+ VEC_LLONG,
+ VEC_VOIDARR,
+ VEC_STRING,
+ VEC_INTARR,
+ VEC_BOOLARR,
+ VEC_LLONGARR,
+ VEC_STRINGARR,
+ VEC_DOUBLEARR
+};
+
+template <class ITEM> void
+qsort (ITEM *, size_t, ExtCompareFunc, void *);
+
+template <typename ITEM> class Vector
+{
+public:
+
+ Vector ()
+ {
+ count = 0;
+ data = NULL;
+ limit = 0;
+ sorted = false;
+ };
+
+ Vector (long sz);
+
+ virtual
+ ~Vector ()
+ {
+ free (data);
+ }
+
+ void append (const ITEM item);
+ void addAll (Vector<ITEM> *vec);
+ Vector<ITEM> *copy (); // Return a copy of "this".
+
+ ITEM
+ fetch (long index)
+ {
+ return data[index];
+ }
+
+ ITEM
+ get (long index)
+ {
+ return data[index];
+ }
+
+ // Return the first index in "this" that equals "item".
+ // Return -1 if "item" is not found.
+ long find (const ITEM item);
+ long find_r (const ITEM item);
+
+ // Insert "item" into "index"'th slot of "this",
+ // moving everything over by 1.
+ void insert (long index, const ITEM item);
+
+ // Insert "item" after locating its appropriate index
+ void incorporate (const ITEM item, CompareFunc func);
+
+ // Remove and return the "index"'th item from "this",
+ // moving everything over by 1.
+ ITEM remove (long index);
+
+ // Swap two items in "this",
+ void swap (long index1, long index2);
+
+ long
+ size ()
+ {
+ return count;
+ }
+
+ // Store "item" into the "index"'th slot of "this".
+ void store (long index, const ITEM item);
+
+ void
+ put (long index, const ITEM item)
+ {
+ store (index, item);
+ }
+
+ // Sort the vector according to compare
+ void
+ sort (CompareFunc compare, void *arg = NULL)
+ {
+ qsort (data, count, (ExtCompareFunc) compare, arg);
+ sorted = true;
+ }
+
+ // Binary search, vector must be sorted
+ long bisearch (long start, long end, void *key, CompareFunc func);
+ void destroy (); // delete all vector elements (must be pointers!)
+
+ void
+ reset ()
+ {
+ count = 0;
+ sorted = false;
+ }
+
+ bool
+ is_sorted ()
+ {
+ return sorted;
+ }
+
+ virtual VecType
+ type ()
+ {
+ return VEC_VOID;
+ }
+
+ virtual void
+ dump (const char * /* msg */)
+ {
+ return;
+ }
+
+private:
+
+ void resize (long index);
+
+ ITEM *data; // Pointer to data vector
+ long count; // Number of items
+ long limit; // Vector length (power of 2)
+ bool sorted;
+};
+
+template<> VecType Vector<int>::type ();
+template<> VecType Vector<unsigned>::type ();
+template<> VecType Vector<char>::type ();
+template<> VecType Vector<bool>::type ();
+template<> VecType Vector<double>::type ();
+template<> VecType Vector<long long>::type ();
+template<> VecType Vector<uint64_t>::type ();
+template<> VecType Vector<void*>::type ();
+template<> VecType Vector<char*>::type ();
+template<> VecType Vector<Vector<int>*>::type ();
+template<> VecType Vector<Vector<char*>*>::type ();
+template<> VecType Vector<Vector<long long>*>::type ();
+template<> void Vector<char *>::destroy ();
+
+#define KILOCHUNK 1024
+#define MEGACHUNK 1024*1024
+#define GIGACHUNK 1024*1024*1024
+
+// A standard looping construct:
+#define Vec_loop(ITEM, vec, index, item) \
+if (vec != NULL) \
+ for (index = 0, item = ((vec)->size() > 0) ? (vec)->fetch(0) : (ITEM)0; \
+ index < (vec)->size(); \
+ item = (++index < (vec)->size()) ? (vec)->fetch(index) : (ITEM)0)
+
+template <typename ITEM>
+Vector<ITEM>::Vector (long sz)
+{
+ count = 0;
+ limit = sz > 0 ? sz : KILOCHUNK; // was 0;
+ data = limit ? (ITEM *) malloc (sizeof (ITEM) * limit) : NULL;
+ sorted = false;
+}
+
+template <typename ITEM> void
+Vector<ITEM>
+::resize (long index)
+{
+ if (index < limit)
+ return;
+ if (limit < 16)
+ limit = 16;
+ while (index >= limit)
+ {
+ if (limit > GIGACHUNK)
+ limit += GIGACHUNK; // Deoptimization for large experiments
+ else
+ limit = limit * 2;
+ }
+ data = (ITEM *) realloc (data, limit * sizeof (ITEM));
+}
+
+template <typename ITEM> void
+Vector<ITEM>::append (const ITEM item)
+{
+ // This routine will append "item" to the end of "this".
+ if (count >= limit)
+ resize (count);
+ data[count++] = item;
+}
+
+template <typename ITEM> void
+Vector<ITEM>::addAll (Vector<ITEM> *vec)
+{
+ if (vec)
+ for (int i = 0, sz = vec->size (); i < sz; i++)
+ append (vec->fetch (i));
+}
+
+template <typename ITEM> Vector<ITEM> *
+Vector<ITEM>::copy ()
+{
+ // This routine will return a copy of "this".
+ Vector<ITEM> *vector;
+ vector = new Vector<ITEM>;
+ vector->count = count;
+ vector->limit = limit;
+ vector->data = (ITEM *) malloc (sizeof (ITEM) * limit);
+ (void) memcpy ((char *) vector->data, (char *) data, sizeof (ITEM) * count);
+ return vector;
+}
+
+template <typename ITEM> long
+Vector<ITEM>::find (const ITEM match_item)
+{
+ for (long i = 0; i < size (); i++)
+ if (match_item == get (i))
+ return i;
+ return -1;
+}
+
+template <typename ITEM> long
+Vector<ITEM>::find_r (const ITEM match_item)
+{
+ for (long i = size () - 1; i >= 0; i--)
+ if (match_item == get (i))
+ return i;
+ return -1;
+}
+
+template <typename ITEM> void
+Vector<ITEM>::insert (long index, const ITEM item)
+{
+ // This routine will insert "item" into the "index"'th slot of "this".
+ // An error occurs if "index" > size().
+ // "index" is allowed to be equal to "count" in the case that
+ // you are inserting past the last element of the vector.
+ // In that case, the bcopy below becomes a no-op.
+ assert (index >= 0);
+ assert (index <= count);
+ append (item);
+ (void) memmove (((char *) (&data[index + 1])), (char *) (&data[index]),
+ (count - index - 1) * sizeof (ITEM));
+ data[index] = item;
+}
+
+template <typename ITEM> ITEM
+Vector<ITEM>::remove (long index)
+{
+ // This routine will remove the "index"'th item from "this" and
+ // return it. An error occurs if "index" >= size();.
+ assert (index >= 0);
+ assert (index < count);
+ ITEM item = data[index];
+ for (long i = index + 1; i < count; i++)
+ data[i - 1] = data[i];
+ count--;
+ // Bad code that works good when ITEM is a pointer type
+ data[count] = item;
+ return data[count];
+}
+
+template <typename ITEM> void
+Vector<ITEM>::swap (long index1, long index2)
+{
+ ITEM item;
+ item = data[index1];
+ data[index1] = data[index2];
+ data[index2] = item;
+}
+
+template <typename ITEM> void
+Vector<ITEM>::store (long index, const ITEM item)
+{
+ if (index >= count)
+ {
+ resize (index);
+ memset (&data[count], 0, (index - count) * sizeof (ITEM));
+ count = index + 1;
+ }
+ data[index] = item;
+}
+
+// This routine performs a binary search across
+// the entire vector, with "start" being the low boundary.
+// It is assumed that the vector is SORTED in
+// ASCENDING ORDER by the same criteria as the
+// compare function.
+// If no match is found, -1 is returned.
+template <typename ITEM> long
+Vector<ITEM>::bisearch (long start, long end, void *key, CompareFunc compare)
+{
+ ITEM *itemp;
+ if (end == -1)
+ end = count;
+ if (start >= end)
+ return -1; // start exceeds limit
+ itemp = (ITEM *) bsearch ((char *) key, (char *) &data[start],
+ end - start, sizeof (ITEM), (StdCompareFunc) compare);
+ if (itemp == (ITEM *) 0)
+ return -1; // not found
+ return (long) (itemp - data);
+}
+
+template <typename ITEM> void
+Vector<ITEM>::incorporate (const ITEM item, CompareFunc compare)
+{
+ long lt = 0;
+ long rt = count - 1;
+ while (lt <= rt)
+ {
+ long md = (lt + rt) / 2;
+ if (compare (data[md], item) < 0)
+ lt = md + 1;
+ else
+ rt = md - 1;
+ }
+ if (lt == count)
+ append (item);
+ else
+ insert (lt, item);
+}
+
+#define QSTHRESH 6
+
+template <typename ITEM> void
+qsort (ITEM *base, size_t nelem, ExtCompareFunc qcmp, void *arg)
+{
+ for (;;)
+ {
+ // For small arrays use insertion sort
+ if (nelem < QSTHRESH)
+ {
+ for (size_t i = 1; i < nelem; i++)
+ {
+ ITEM *p = base + i;
+ ITEM *q = p - 1;
+ if (qcmp (q, p, arg) > 0)
+ {
+ ITEM t = *p;
+ *p = *q;
+ while (q > base && qcmp (q - 1, &t, arg) > 0)
+ {
+ *q = *(q - 1);
+ --q;
+ }
+ *q = t;
+ }
+ }
+ return;
+ }
+
+ ITEM *last = base + nelem - 1;
+ ITEM *mid = base + nelem / 2;
+ // Sort the first, middle, and last elements
+ ITEM *a1 = base, *a2, *a3;
+ if (qcmp (base, mid, arg) > 0)
+ {
+ if (qcmp (mid, last, arg) > 0)
+ { // l-m-b
+ a2 = last;
+ a3 = last;
+ }
+ else if (qcmp (base, last, arg) > 0)
+ { // l-b-m
+ a2 = mid;
+ a3 = last;
+ }
+ else
+ { // m-b-l
+ a2 = mid;
+ a3 = mid;
+ }
+ }
+ else if (qcmp (mid, last, arg) > 0)
+ {
+ a1 = mid;
+ a3 = last;
+ if (qcmp (base, last, arg) > 0) // m-l-b
+ a2 = base;
+ else // b-l-m
+ a2 = a3;
+ }
+ else // b-m-l
+ a3 = a2 = a1;
+ if (a1 != a2)
+ {
+ ITEM t = *a1;
+ *a1 = *a2;
+ if (a2 != a3)
+ *a2 = *a3;
+ *a3 = t;
+ }
+
+ // Partition
+ ITEM *i = base + 1;
+ ITEM *j = last - 1;
+ for (;;)
+ {
+ while (i < mid && qcmp (i, mid, arg) <= 0)
+ i++;
+ while (j > mid && qcmp (mid, j, arg) <= 0)
+ j--;
+ if (i == j)
+ break;
+ ITEM t = *i;
+ *i = *j;
+ *j = t;
+ if (i == mid)
+ {
+ mid = j;
+ i++;
+ }
+ else if (j == mid)
+ {
+ mid = i;
+ j--;
+ }
+ else
+ {
+ i++;
+ j--;
+ }
+ }
+
+ // Compare two partitions. Do the smaller one by recursion
+ // and loop over the larger one.
+ size_t nleft = mid - base;
+ size_t nright = nelem - nleft - 1;
+ if (nleft <= nright)
+ {
+ qsort (base, nleft, qcmp, arg);
+ base = mid + 1;
+ nelem = nright;
+ }
+ else
+ {
+ qsort (mid + 1, nright, qcmp, arg);
+ nelem = nleft;
+ }
+ }
+}
+
+template<> inline void
+Vector<char*>::destroy ()
+{
+ for (long i = 0; i < count; i++)
+ free (data[i]);
+ count = 0;
+}
+
+template <typename ITEM> inline void
+Vector<ITEM>::destroy ()
+{
+ for (long i = 0; i < count; i++)
+ delete data[i];
+ count = 0;
+}
+
+#endif /* _VEC_H */
generated by cgit v1.1 at 2024-09-06 23:12:36 +0000