1/* Copyright (C) 2021 Free Software Foundation, Inc.
2   Contributed by Oracle.
3
4   This file is part of GNU Binutils.
5
6   This program is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 3, or (at your option)
9   any later version.
10
11   This program is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program; if not, write to the Free Software
18   Foundation, 51 Franklin Street - Fifth Floor, Boston,
19   MA 02110-1301, USA.  */
20
21#ifndef _PERFAN_VEC_H
22#define _PERFAN_VEC_H
23
24#include <assert.h>
25#include <inttypes.h>
26#include <string.h>
27#include <stdlib.h>
28
29// This package implements a vector of items.
30
31#define Destroy(x)      if (x) { (x)->destroy(); delete (x); (x) = NULL; }
32#define VecSize(x)      ((x) ? (x)->size() : 0)
33
34void destroy (void *vec); // Free up the "two-dimension" Vectors
35
36typedef int (*CompareFunc)(const void*, const void*);
37typedef int (*ExtCompareFunc)(const void*, const void*, const void*);
38typedef int (*SearchFunc)(char*, char*);
39
40extern "C"
41{
42  typedef int (*StdCompareFunc)(const void*, const void*);
43}
44
45enum Search_type
46{
47  LINEAR,
48  BINARY,
49  HASH
50};
51
52enum Direction
53{
54  FORWARD,
55  REVERSE
56};
57
58enum VecType
59{
60  VEC_VOID = 0,
61  VEC_INTEGER,
62  VEC_CHAR,
63  VEC_BOOL,
64  VEC_DOUBLE,
65  VEC_LLONG,
66  VEC_VOIDARR,
67  VEC_STRING,
68  VEC_INTARR,
69  VEC_BOOLARR,
70  VEC_LLONGARR,
71  VEC_STRINGARR,
72  VEC_DOUBLEARR
73};
74
75template <class ITEM> void
76qsort (ITEM *, size_t, ExtCompareFunc, void *);
77
78template <typename ITEM> class Vector
79{
80public:
81
82  Vector ()
83  {
84    count = 0;
85    data = NULL;
86    limit = 0;
87    sorted = false;
88  };
89
90  Vector (long sz);
91
92  virtual
93  ~Vector ()
94  {
95    free (data);
96  }
97
98  void append (const ITEM item);
99  void addAll (Vector<ITEM> *vec);
100  Vector<ITEM> *copy ();        // Return a copy of "this".
101
102  ITEM
103  fetch (long index)
104  {
105    return data[index];
106  }
107
108  ITEM
109  get (long index)
110  {
111    return data[index];
112  }
113
114  // Return the first index in "this" that equals "item".
115  // Return -1 if "item" is not found.
116  long find (const ITEM item);
117  long find_r (const ITEM item);
118
119  // Insert "item" into "index"'th slot of "this",
120  // moving everything over by 1.
121  void insert (long index, const ITEM item);
122
123  // Insert "item" after locating its appropriate index
124  void incorporate (const ITEM item, CompareFunc func);
125
126  // Remove and return the "index"'th item from "this",
127  // moving everything over by 1.
128  ITEM remove (long index);
129
130  // Swap two items in "this",
131  void swap (long index1, long index2);
132
133  long
134  size ()
135  {
136    return count;
137  }
138
139  // Store "item" into the "index"'th slot of "this".
140  void store (long index, const ITEM item);
141
142  void
143  put (long index, const ITEM item)
144  {
145    store (index, item);
146  }
147
148  // Sort the vector according to compare
149  void
150  sort (CompareFunc compare, void *arg = NULL)
151  {
152    qsort (data, count, (ExtCompareFunc) compare, arg);
153    sorted = true;
154  }
155
156  // Binary search, vector must be sorted
157  long bisearch (long start, long end, void *key, CompareFunc func);
158  void destroy ();      // delete all vector elements (must be pointers!)
159
160  void
161  reset ()
162  {
163    count = 0;
164    sorted = false;
165  }
166
167  bool
168  is_sorted ()
169  {
170    return sorted;
171  }
172
173  virtual VecType
174  type ()
175  {
176    return VEC_VOID;
177  }
178
179  virtual void
180  dump (const char * /* msg */)
181  {
182    return;
183  }
184
185private:
186
187  void resize (long index);
188
189  ITEM *data;   // Pointer to data vector
190  long count;   // Number of items
191  long limit;   // Vector length (power of 2)
192  bool sorted;
193};
194
195template<> VecType Vector<int>::type ();
196template<> VecType Vector<unsigned>::type ();
197template<> VecType Vector<char>::type ();
198template<> VecType Vector<bool>::type ();
199template<> VecType Vector<double>::type ();
200template<> VecType Vector<long long>::type ();
201template<> VecType Vector<uint64_t>::type ();
202template<> VecType Vector<void*>::type ();
203template<> VecType Vector<char*>::type ();
204template<> VecType Vector<Vector<int>*>::type ();
205template<> VecType Vector<Vector<char*>*>::type ();
206template<> VecType Vector<Vector<long long>*>::type ();
207template<> void Vector<char *>::destroy ();
208
209#define KILOCHUNK   1024
210#define MEGACHUNK   1024*1024
211#define GIGACHUNK   1024*1024*1024
212
213// A standard looping construct:
214#define Vec_loop(ITEM, vec, index, item) \
215if (vec != NULL) \
216    for (index = 0, item = ((vec)->size() > 0) ? (vec)->fetch(0) : (ITEM)0; \
217	 index < (vec)->size(); \
218	 item = (++index < (vec)->size()) ? (vec)->fetch(index) : (ITEM)0)
219
220template <typename ITEM>
221Vector<ITEM>::Vector (long sz)
222{
223  count = 0;
224  limit = sz > 0 ? sz : KILOCHUNK; // was 0;
225  data = limit ? (ITEM *) malloc (sizeof (ITEM) * limit) : NULL;
226  sorted = false;
227}
228
229template <typename ITEM> void
230Vector<ITEM>
231::resize (long index)
232{
233  if (index < limit)
234    return;
235  if (limit < 16)
236    limit = 16;
237  while (index >= limit)
238    {
239      if (limit > GIGACHUNK)
240	limit += GIGACHUNK; // Deoptimization for large experiments
241      else
242	limit = limit * 2;
243    }
244  data = (ITEM *) realloc (data, limit * sizeof (ITEM));
245}
246
247template <typename ITEM> void
248Vector<ITEM>::append (const ITEM item)
249{
250  // This routine will append "item" to the end of "this".
251  if (count >= limit)
252    resize (count);
253  data[count++] = item;
254}
255
256template <typename ITEM> void
257Vector<ITEM>::addAll (Vector<ITEM> *vec)
258{
259  if (vec)
260    for (int i = 0, sz = vec->size (); i < sz; i++)
261      append (vec->fetch (i));
262}
263
264template <typename ITEM> Vector<ITEM> *
265Vector<ITEM>::copy ()
266{
267  // This routine will return a copy of "this".
268  Vector<ITEM> *vector;
269  vector = new Vector<ITEM>;
270  vector->count = count;
271  vector->limit = limit;
272  vector->data = (ITEM *) malloc (sizeof (ITEM) * limit);
273  (void) memcpy ((char *) vector->data, (char *) data, sizeof (ITEM) * count);
274  return vector;
275}
276
277template <typename ITEM> long
278Vector<ITEM>::find (const ITEM match_item)
279{
280  for (long i = 0; i < size (); i++)
281    if (match_item == get (i))
282      return i;
283  return -1;
284}
285
286template <typename ITEM> long
287Vector<ITEM>::find_r (const ITEM match_item)
288{
289  for (long i = size () - 1; i >= 0; i--)
290    if (match_item == get (i))
291      return i;
292  return -1;
293}
294
295template <typename ITEM> void
296Vector<ITEM>::insert (long index, const ITEM item)
297{
298  // This routine will insert "item" into the "index"'th slot of "this".
299  // An error occurs if "index" > size().
300  // "index" is allowed to be equal to "count" in the case that
301  // you are inserting past the last element of the vector.
302  // In that case, the bcopy below becomes a no-op.
303  assert (index >= 0);
304  assert (index <= count);
305  append (item);
306  (void) memmove (((char *) (&data[index + 1])), (char *) (&data[index]),
307		  (count - index - 1) * sizeof (ITEM));
308  data[index] = item;
309}
310
311template <typename ITEM> ITEM
312Vector<ITEM>::remove (long index)
313{
314  // This routine will remove the "index"'th item from "this" and
315  // return it.  An error occurs if "index" >= size();.
316  assert (index >= 0);
317  assert (index < count);
318  ITEM item = data[index];
319  for (long i = index + 1; i < count; i++)
320    data[i - 1] = data[i];
321  count--;
322  // Bad code that works good when ITEM is a pointer type
323  data[count] = item;
324  return data[count];
325}
326
327template <typename ITEM> void
328Vector<ITEM>::swap (long index1, long index2)
329{
330  ITEM item;
331  item = data[index1];
332  data[index1] = data[index2];
333  data[index2] = item;
334}
335
336template <typename ITEM> void
337Vector<ITEM>::store (long index, const ITEM item)
338{
339  if (index >= count)
340    {
341      resize (index);
342      memset (&data[count], 0, (index - count) * sizeof (ITEM));
343      count = index + 1;
344    }
345  data[index] = item;
346}
347
348// This routine performs a binary search across
349// the entire vector, with "start" being the low boundary.
350// It is assumed that the vector is SORTED in
351// ASCENDING ORDER by the same criteria as the
352// compare function.
353// If no match is found, -1 is returned.
354template <typename ITEM> long
355Vector<ITEM>::bisearch (long start, long end, void *key, CompareFunc compare)
356{
357  ITEM *itemp;
358  if (end == -1)
359    end = count;
360  if (start >= end)
361    return -1; // start exceeds limit
362  itemp = (ITEM *) bsearch ((char *) key, (char *) &data[start],
363			  end - start, sizeof (ITEM), (StdCompareFunc) compare);
364  if (itemp == (ITEM *) 0)
365    return -1; // not found
366  return (long) (itemp - data);
367}
368
369template <typename ITEM> void
370Vector<ITEM>::incorporate (const ITEM item, CompareFunc compare)
371{
372  long lt = 0;
373  long rt = count - 1;
374  while (lt <= rt)
375    {
376      long md = (lt + rt) / 2;
377      if (compare (data[md], item) < 0)
378	lt = md + 1;
379      else
380	rt = md - 1;
381    }
382  if (lt == count)
383    append (item);
384  else
385    insert (lt, item);
386}
387
388#define QSTHRESH 6
389
390template <typename ITEM> void
391qsort (ITEM *base, size_t nelem, ExtCompareFunc qcmp, void *arg)
392{
393  for (;;)
394    {
395      // For small arrays use insertion sort
396      if (nelem < QSTHRESH)
397	{
398	  for (size_t i = 1; i < nelem; i++)
399	    {
400	      ITEM *p = base + i;
401	      ITEM *q = p - 1;
402	      if (qcmp (q, p, arg) > 0)
403		{
404		  ITEM t = *p;
405		  *p = *q;
406		  while (q > base && qcmp (q - 1, &t, arg) > 0)
407		    {
408		      *q = *(q - 1);
409		      --q;
410		    }
411		  *q = t;
412		}
413	    }
414	  return;
415	}
416
417      ITEM *last = base + nelem - 1;
418      ITEM *mid = base + nelem / 2;
419      // Sort the first, middle, and last elements
420      ITEM *a1 = base, *a2, *a3;
421      if (qcmp (base, mid, arg) > 0)
422	{
423	  if (qcmp (mid, last, arg) > 0)
424	    { // l-m-b
425	      a2 = last;
426	      a3 = last;
427	    }
428	  else if (qcmp (base, last, arg) > 0)
429	    { // l-b-m
430	      a2 = mid;
431	      a3 = last;
432	    }
433	  else
434	    { // m-b-l
435	      a2 = mid;
436	      a3 = mid;
437	    }
438	}
439      else if (qcmp (mid, last, arg) > 0)
440	{
441	  a1 = mid;
442	  a3 = last;
443	  if (qcmp (base, last, arg) > 0)  // m-l-b
444	    a2 = base;
445	  else  // b-l-m
446	    a2 = a3;
447	}
448      else // b-m-l
449	a3 = a2 = a1;
450      if (a1 != a2)
451	{
452	  ITEM t = *a1;
453	  *a1 = *a2;
454	  if (a2 != a3)
455	    *a2 = *a3;
456	  *a3 = t;
457	}
458
459      // Partition
460      ITEM *i = base + 1;
461      ITEM *j = last - 1;
462      for (;;)
463	{
464	  while (i < mid && qcmp (i, mid, arg) <= 0)
465	    i++;
466	  while (j > mid && qcmp (mid, j, arg) <= 0)
467	    j--;
468	  if (i == j)
469	    break;
470	  ITEM t = *i;
471	  *i = *j;
472	  *j = t;
473	  if (i == mid)
474	    {
475	      mid = j;
476	      i++;
477	    }
478	  else if (j == mid)
479	    {
480	      mid = i;
481	      j--;
482	    }
483	  else
484	    {
485	      i++;
486	      j--;
487	    }
488	}
489
490      // Compare two partitions. Do the smaller one by recursion
491      // and loop over the larger one.
492      size_t nleft = mid - base;
493      size_t nright = nelem - nleft - 1;
494      if (nleft <= nright)
495	{
496	  qsort (base, nleft, qcmp, arg);
497	  base = mid + 1;
498	  nelem = nright;
499	}
500      else
501	{
502	  qsort (mid + 1, nright, qcmp, arg);
503	  nelem = nleft;
504	}
505    }
506}
507
508template<> inline void
509Vector<char*>::destroy ()
510{
511  for (long i = 0; i < count; i++)
512    free (data[i]);
513  count = 0;
514}
515
516template <typename ITEM> inline void
517Vector<ITEM>::destroy ()
518{
519  for (long i = 0; i < count; i++)
520    delete data[i];
521  count = 0;
522}
523
524#endif /* _VEC_H */
525