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