1 /* Copyright (C) 2021-2023 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
34 void destroy (void *vec); // Free up the "two-dimension" Vectors
35
36 typedef int (*CompareFunc)(const void*, const void*);
37 typedef int (*ExtCompareFunc)(const void*, const void*, const void*);
38 typedef int (*SearchFunc)(char*, char*);
39
40 extern "C"
41 {
42 typedef int (*StdCompareFunc)(const void*, const void*);
43 }
44
45 enum Search_type
46 {
47 LINEAR,
48 BINARY,
49 HASH
50 };
51
52 enum Direction
53 {
54 FORWARD,
55 REVERSE
56 };
57
58 enum 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
75 template <class ITEM> void
76 qsort (ITEM *, size_t, ExtCompareFunc, void *);
77
78 template <typename ITEM> class Vector
79 {
80 public:
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
185 private:
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
195 template<> VecType Vector<int>::type ();
196 template<> VecType Vector<unsigned>::type ();
197 template<> VecType Vector<char>::type ();
198 template<> VecType Vector<bool>::type ();
199 template<> VecType Vector<double>::type ();
200 template<> VecType Vector<long long>::type ();
201 template<> VecType Vector<uint64_t>::type ();
202 template<> VecType Vector<void*>::type ();
203 template<> VecType Vector<char*>::type ();
204 template<> VecType Vector<Vector<int>*>::type ();
205 template<> VecType Vector<Vector<char*>*>::type ();
206 template<> VecType Vector<Vector<long long>*>::type ();
207 template<> 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) \
215 if (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
220 template <typename ITEM>
221 Vector<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
229 template <typename ITEM> void
230 Vector<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
247 template <typename ITEM> void
248 Vector<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
256 template <typename ITEM> void
257 Vector<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
264 template <typename ITEM> Vector<ITEM> *
265 Vector<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
277 template <typename ITEM> long
278 Vector<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
286 template <typename ITEM> long
287 Vector<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
295 template <typename ITEM> void
296 Vector<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
311 template <typename ITEM> ITEM
312 Vector<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
327 template <typename ITEM> void
328 Vector<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
336 template <typename ITEM> void
337 Vector<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.
354 template <typename ITEM> long
355 Vector<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
369 template <typename ITEM> void
370 Vector<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
390 template <typename ITEM> void
391 qsort (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
508 template<> inline void
509 Vector<char*>::destroy ()
510 {
511 for (long i = 0; i < count; i++)
512 free (data[i]);
513 count = 0;
514 }
515
516 template <typename ITEM> inline void
517 Vector<ITEM>::destroy ()
518 {
519 for (long i = 0; i < count; i++)
520 delete data[i];
521 count = 0;
522 }
523
524 #endif /* _VEC_H */