gprofng/src/vec.h

   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
  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 */