/* Copyright (C) 2021-2024 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 */