mirror of
https://github.com/autc04/Retro68.git
synced 2024-06-07 13:33:06 +00:00
525 lines
11 KiB
C++
525 lines
11 KiB
C++
/* 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 */
|