gprofng/src/Table.cc

   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 #include "config.h"
  22 #include <stdio.h>
  23
  24 #include "IndexMap2D.h"
  25 #include "DbeSession.h"
  26 #include "FilterExp.h"
  27 #include "Table.h"
  28 #include "util.h"
  29 #include "i18n.h"
  30
  31 char *
  32 get_prof_data_type_name (int t)
  33 {
  34   switch (t)
  35     {
  36     case DATA_SAMPLE:   return NTXT("PROFDATA_TYPE_SAMPLE");
  37     case DATA_GCEVENT:  return NTXT("PROFDATA_TYPE_GCEVENT");
  38     case DATA_HEAPSZ:   return NTXT("PROFDATA_TYPE_HEAPSZ");
  39     case DATA_CLOCK:    return NTXT("PROFDATA_TYPE_CLOCK");
  40     case DATA_HWC:      return NTXT("PROFDATA_TYPE_HWC");
  41     case DATA_SYNCH:    return NTXT("PROFDATA_TYPE_SYNCH");
  42     case DATA_HEAP:     return NTXT("PROFDATA_TYPE_HEAP");
  43     case DATA_OMP:      return NTXT("PROFDATA_TYPE_OMP");
  44     case DATA_OMP2:     return NTXT("PROFDATA_TYPE_OMP2");
  45     case DATA_OMP3:     return NTXT("PROFDATA_TYPE_OMP3");
  46     case DATA_OMP4:     return NTXT("PROFDATA_TYPE_OMP4");
  47     case DATA_OMP5:     return NTXT("PROFDATA_TYPE_OMP5");
  48     case DATA_IOTRACE:  return NTXT("PROFDATA_TYPE_IOTRACE");
  49     default: abort ();
  50       return NTXT ("PROFDATA_TYPE_ERROR");
  51     }
  52 }
  53
  54 char *
  55 get_prof_data_type_uname (int t)
  56 {
  57   switch (t)
  58     {
  59     case DATA_SAMPLE:   return GTXT("Process-wide Resource Utilization");
  60     case DATA_GCEVENT:  return GTXT("Java Garbage Collection Events");
  61     case DATA_HEAPSZ:   return GTXT("Heap Size");
  62     case DATA_CLOCK:    return GTXT("Clock Profiling");
  63     case DATA_HWC:      return GTXT("HW Counter Profiling");
  64     case DATA_SYNCH:    return GTXT("Synchronization Tracing");
  65     case DATA_HEAP:     return GTXT("Heap Tracing");
  66     case DATA_OMP:      return GTXT("OpenMP Profiling");
  67     case DATA_OMP2:     return GTXT("OpenMP Profiling");
  68     case DATA_OMP3:     return GTXT("OpenMP Profiling");
  69     case DATA_OMP4:     return GTXT("OpenMP Profiling");
  70     case DATA_OMP5:     return GTXT("OpenMP Profiling");
  71     case DATA_IOTRACE:  return GTXT("IO Tracing");
  72     default: abort ();
  73       return NTXT ("PROFDATA_TYPE_ERROR");
  74     }
  75 }
  76
  77 int assert_level = 0; // set to 1 to bypass problematic asserts
  78
  79 #define ASSERT_SKIP (assert_level)
  80
  81 /*
  82  *    class PropDescr
  83  */
  84
  85 PropDescr::PropDescr (int _propID, const char *_name)
  86 {
  87   propID = _propID;
  88   name = strdup (_name ? _name : NTXT (""));
  89   uname = NULL;
  90   vtype = TYPE_NONE;
  91   flags = 0;
  92   stateNames = NULL;
  93   stateUNames = NULL;
  94 }
  95
  96 PropDescr::~PropDescr ()
  97 {
  98   free (name);
  99   free (uname);
 100   if (stateNames)
 101     {
 102       stateNames->destroy ();
 103       delete stateNames;
 104     }
 105   if (stateUNames)
 106     {
 107       stateUNames->destroy ();
 108       delete stateUNames;
 109     }
 110 }
 111
 112 void
 113 PropDescr::addState (int value, const char *stname, const char *stuname)
 114 {
 115   if (value < 0 || stname == NULL)
 116     return;
 117   if (stateNames == NULL)
 118     stateNames = new Vector<char*>;
 119   stateNames->store (value, strdup (stname));
 120   if (stateUNames == NULL)
 121     stateUNames = new Vector<char*>;
 122   stateUNames->store (value, strdup (stuname));
 123 }
 124
 125 char *
 126 PropDescr::getStateName (int value)
 127 {
 128   if (stateNames && value >= 0 && value < stateNames->size ())
 129     return stateNames->fetch (value);
 130   return NULL;
 131 }
 132
 133 char *
 134 PropDescr::getStateUName (int value)
 135 {
 136   if (stateUNames && value >= 0 && value < stateUNames->size ())
 137     return stateUNames->fetch (value);
 138   return NULL;
 139 }
 140
 141 /*
 142  *    class FieldDescr
 143  */
 144
 145 FieldDescr::FieldDescr (int _propID, const char *_name)
 146 {
 147   propID = _propID;
 148   name = _name ? strdup (_name) : NULL;
 149   offset = 0;
 150   vtype = TYPE_NONE;
 151   format = NULL;
 152 }
 153
 154 FieldDescr::~FieldDescr ()
 155 {
 156   free (name);
 157   free (format);
 158 }
 159
 160 /*
 161  *    class PacketDescriptor
 162  */
 163
 164 PacketDescriptor::PacketDescriptor (DataDescriptor *_ddscr)
 165 {
 166   ddscr = _ddscr;
 167   fields = new Vector<FieldDescr*>;
 168 }
 169
 170 PacketDescriptor::~PacketDescriptor ()
 171 {
 172   fields->destroy ();
 173   delete fields;
 174 }
 175
 176 void
 177 PacketDescriptor::addField (FieldDescr *fldDscr)
 178 {
 179   if (fldDscr == NULL)
 180     return;
 181   fields->append (fldDscr);
 182 }
 183
 184 /*
 185  *    class Data
 186  */
 187
 188 /* Check compatibility between Datum and Data */
 189 static void
 190 checkCompatibility (VType_type v1, VType_type v2)
 191 {
 192   switch (v1)
 193     {
 194     case TYPE_NONE:
 195     case TYPE_STRING:
 196     case TYPE_DOUBLE:
 197     case TYPE_OBJ:
 198     case TYPE_DATE:
 199       assert (v1 == v2);
 200       break;
 201     case TYPE_INT32:
 202     case TYPE_UINT32:
 203       assert (v2 == TYPE_INT32 ||
 204               v2 == TYPE_UINT32);
 205       break;
 206     case TYPE_INT64:
 207     case TYPE_UINT64:
 208       assert (v2 == TYPE_INT64 ||
 209               v2 == TYPE_UINT64);
 210       break;
 211     default:
 212       assert (0);
 213     }
 214 }
 215
 216 class DataINT32 : public Data
 217 {
 218 public:
 219
 220   DataINT32 ()
 221   {
 222     data = new Vector<int32_t>;
 223   }
 224
 225   virtual
 226   ~DataINT32 ()
 227   {
 228     delete data;
 229   }
 230
 231   virtual VType_type
 232   type ()
 233   {
 234     return TYPE_INT32;
 235   }
 236
 237   virtual void
 238   reset ()
 239   {
 240     data->reset ();
 241   }
 242
 243   virtual long
 244   getSize ()
 245   {
 246     return data->size ();
 247   }
 248
 249   virtual int
 250   fetchInt (long i)
 251   {
 252     return (int) data->fetch (i);
 253   }
 254
 255   virtual unsigned long long
 256   fetchULong (long i)
 257   {
 258     return (unsigned long long) data->fetch (i);
 259   }
 260
 261   virtual long long
 262   fetchLong (long i)
 263   {
 264     return (long long) data->fetch (i);
 265   }
 266
 267   virtual char *
 268   fetchString (long i)
 269   {
 270     return dbe_sprintf (NTXT ("%d"), data->fetch (i));
 271   }
 272
 273   virtual double
 274   fetchDouble (long i)
 275   {
 276     return (double) data->fetch (i);
 277   }
 278
 279   virtual void *
 280   fetchObject (long)
 281   {
 282     assert (ASSERT_SKIP);
 283     return NULL;
 284   }
 285
 286   virtual void
 287   setDatumValue (long idx, const Datum *val)
 288   {
 289     data->store (idx, val->i);
 290   }
 291
 292   virtual void
 293   setValue (long idx, uint64_t val)
 294   {
 295     data->store (idx, (int32_t) val);
 296   }
 297
 298   virtual void
 299   setObjValue (long, void*)
 300   {
 301     assert (ASSERT_SKIP);
 302     return;
 303   }
 304
 305   virtual int
 306   cmpValues (long idx1, long idx2)
 307   {
 308     int32_t i1 = data->fetch (idx1);
 309     int32_t i2 = data->fetch (idx2);
 310     return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
 311   }
 312
 313   virtual int
 314   cmpDatumValue (long idx, const Datum *val)
 315   {
 316     int32_t i1 = data->fetch (idx);
 317     int32_t i2 = val->i;
 318     return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
 319   }
 320
 321 private:
 322   Vector<int32_t> *data;
 323 };
 324
 325 class DataUINT32 : public Data
 326 {
 327 public:
 328
 329   DataUINT32 ()
 330   {
 331     data = new Vector<uint32_t>;
 332   }
 333
 334   virtual
 335   ~DataUINT32 ()
 336   {
 337     delete data;
 338   }
 339
 340   virtual VType_type
 341   type ()
 342   {
 343     return TYPE_UINT32;
 344   }
 345
 346   virtual void
 347   reset ()
 348   {
 349     data->reset ();
 350   }
 351
 352   virtual long
 353   getSize ()
 354   {
 355     return data->size ();
 356   }
 357
 358   virtual int
 359   fetchInt (long i)
 360   {
 361     return (int) data->fetch (i);
 362   }
 363
 364   virtual unsigned long long
 365   fetchULong (long i)
 366   {
 367     return (unsigned long long) data->fetch (i);
 368   }
 369
 370   virtual long long
 371   fetchLong (long i)
 372   {
 373     return (long long) data->fetch (i);
 374   }
 375
 376   virtual char *
 377   fetchString (long i)
 378   {
 379     return dbe_sprintf (NTXT ("%u"), data->fetch (i));
 380   }
 381
 382   virtual double
 383   fetchDouble (long i)
 384   {
 385     return (double) data->fetch (i);
 386   }
 387
 388   virtual void *
 389   fetchObject (long)
 390   {
 391     assert (ASSERT_SKIP);
 392     return NULL;
 393   }
 394
 395   virtual void
 396   setDatumValue (long idx, const Datum *val)
 397   {
 398     data->store (idx, val->i);
 399   }
 400
 401   virtual void
 402   setValue (long idx, uint64_t val)
 403   {
 404     data->store (idx, (uint32_t) val);
 405   }
 406
 407   virtual void
 408   setObjValue (long, void*)
 409   {
 410     assert (ASSERT_SKIP);
 411     return;
 412   }
 413
 414   virtual int
 415   cmpValues (long idx1, long idx2)
 416   {
 417     uint32_t u1 = data->fetch (idx1);
 418     uint32_t u2 = data->fetch (idx2);
 419     return u1 < u2 ? -1 : u1 > u2 ? 1 : 0;
 420   }
 421
 422   virtual int
 423   cmpDatumValue (long idx, const Datum *val)
 424   {
 425     uint32_t u1 = data->fetch (idx);
 426     uint32_t u2 = (uint32_t) val->i;
 427     return u1 < u2 ? -1 : u1 > u2 ? 1 : 0;
 428   }
 429
 430 private:
 431   Vector<uint32_t> *data;
 432 };
 433
 434 class DataINT64 : public Data
 435 {
 436 public:
 437
 438   DataINT64 ()
 439   {
 440     data = new Vector<int64_t>;
 441   }
 442
 443   virtual
 444   ~DataINT64 ()
 445   {
 446     delete data;
 447   }
 448
 449   virtual VType_type
 450   type ()
 451   {
 452     return TYPE_INT64;
 453   }
 454
 455   virtual void
 456   reset ()
 457   {
 458     data->reset ();
 459   }
 460
 461   virtual long
 462   getSize ()
 463   {
 464     return data->size ();
 465   }
 466
 467   virtual int
 468   fetchInt (long i)
 469   {
 470     return (int) data->fetch (i);
 471   }
 472
 473   virtual unsigned long long
 474   fetchULong (long i)
 475   {
 476     return (unsigned long long) data->fetch (i);
 477   }
 478
 479   virtual long long
 480   fetchLong (long i)
 481   {
 482     return (long long) data->fetch (i);
 483   }
 484
 485   virtual char *
 486   fetchString (long i)
 487   {
 488     return dbe_sprintf (NTXT ("%lld"), (long long) data->fetch (i));
 489   }
 490
 491   virtual double
 492   fetchDouble (long i)
 493   {
 494     return (double) data->fetch (i);
 495   }
 496
 497   virtual void *
 498   fetchObject (long)
 499   {
 500     assert (ASSERT_SKIP);
 501     return NULL;
 502   }
 503
 504   virtual void
 505   setDatumValue (long idx, const Datum *val)
 506   {
 507     data->store (idx, val->ll);
 508   }
 509
 510   virtual void
 511   setValue (long idx, uint64_t val)
 512   {
 513     data->store (idx, (int64_t) val);
 514   }
 515
 516   virtual void
 517   setObjValue (long, void*)
 518   {
 519     assert (ASSERT_SKIP);
 520     return;
 521   }
 522
 523   virtual int
 524   cmpValues (long idx1, long idx2)
 525   {
 526     int64_t i1 = data->fetch (idx1);
 527     int64_t i2 = data->fetch (idx2);
 528     return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
 529   }
 530
 531   virtual int
 532   cmpDatumValue (long idx, const Datum *val)
 533   {
 534     int64_t i1 = data->fetch (idx);
 535     int64_t i2 = val->ll;
 536     return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
 537   }
 538
 539 private:
 540   Vector<int64_t> *data;
 541 };
 542
 543 class DataUINT64 : public Data
 544 {
 545 public:
 546
 547   DataUINT64 ()
 548   {
 549     data = new Vector<uint64_t>;
 550   }
 551
 552   virtual
 553   ~DataUINT64 ()
 554   {
 555     delete data;
 556   }
 557
 558   virtual VType_type
 559   type ()
 560   {
 561     return TYPE_UINT64;
 562   }
 563
 564   virtual void
 565   reset ()
 566   {
 567     data->reset ();
 568   }
 569
 570   virtual long
 571   getSize ()
 572   {
 573     return data->size ();
 574   }
 575
 576   virtual int
 577   fetchInt (long i)
 578   {
 579     return (int) data->fetch (i);
 580   }
 581
 582   virtual unsigned long long
 583   fetchULong (long i)
 584   {
 585     return (unsigned long long) data->fetch (i);
 586   }
 587
 588   virtual long long
 589   fetchLong (long i)
 590   {
 591     return (long long) data->fetch (i);
 592   }
 593
 594   virtual char *
 595   fetchString (long i)
 596   {
 597     return dbe_sprintf (NTXT ("%llu"), (long long) data->fetch (i));
 598   }
 599
 600   virtual double
 601   fetchDouble (long i)
 602   {
 603     return (double) data->fetch (i);
 604   }
 605
 606   virtual void *
 607   fetchObject (long)
 608   {
 609     assert (ASSERT_SKIP);
 610     return NULL;
 611   }
 612
 613   virtual void
 614   setDatumValue (long idx, const Datum *val)
 615   {
 616     data->store (idx, val->ll);
 617   }
 618
 619   virtual void
 620   setValue (long idx, uint64_t val)
 621   {
 622     data->store (idx, val);
 623   }
 624
 625   virtual void
 626   setObjValue (long, void*)
 627   {
 628     assert (ASSERT_SKIP);
 629     return;
 630   }
 631
 632   virtual int
 633   cmpValues (long idx1, long idx2)
 634   {
 635     uint64_t u1 = data->fetch (idx1);
 636     uint64_t u2 = data->fetch (idx2);
 637     return u1 < u2 ? -1 : u1 > u2 ? 1 : 0;
 638   }
 639
 640   virtual int
 641   cmpDatumValue (long idx, const Datum *val)
 642   {
 643     uint64_t u1 = data->fetch (idx);
 644     uint64_t u2 = (uint64_t) val->ll;
 645     return u1 < u2 ? -1 : u1 > u2 ? 1 : 0;
 646   }
 647
 648 private:
 649   Vector<uint64_t> *data;
 650 };
 651
 652 class DataOBJECT : public Data
 653 {
 654 public:
 655
 656   DataOBJECT ()
 657   {
 658     dtype = TYPE_OBJ;
 659     data = new Vector<void*>;
 660   }
 661
 662   DataOBJECT (VType_type _dtype)
 663   {
 664     dtype = _dtype;
 665     data = new Vector<void*>;
 666   }
 667
 668   virtual
 669   ~DataOBJECT ()
 670   {
 671     delete data;
 672   }
 673
 674   virtual VType_type
 675   type ()
 676   {
 677     return dtype;
 678   }
 679
 680   virtual void
 681   reset ()
 682   {
 683     data->reset ();
 684   }
 685
 686   virtual long
 687   getSize ()
 688   {
 689     return data->size ();
 690   }
 691
 692   virtual int
 693   fetchInt (long)
 694   {
 695     assert (ASSERT_SKIP);
 696     return 0;
 697   }
 698
 699   virtual unsigned long long
 700   fetchULong (long)
 701   {
 702     assert (ASSERT_SKIP);
 703     return 0LL;
 704   }
 705
 706   virtual long long
 707   fetchLong (long)
 708   {
 709     assert (ASSERT_SKIP);
 710     return 0LL;
 711   }
 712
 713   virtual char *
 714   fetchString (long i)
 715   {
 716     return dbe_sprintf (NTXT ("%lu"), (unsigned long) data->fetch (i));
 717   }
 718
 719   virtual double
 720   fetchDouble (long)
 721   {
 722     assert (ASSERT_SKIP);
 723     return 0.0;
 724   }
 725
 726   virtual void *
 727   fetchObject (long i)
 728   {
 729     return data->fetch (i);
 730   }
 731
 732   virtual void
 733   setDatumValue (long idx, const Datum *val)
 734   {
 735     data->store (idx, val->p);
 736   }
 737
 738   virtual void
 739   setValue (long, uint64_t)
 740   {
 741     assert (ASSERT_SKIP);
 742     return;
 743   }
 744
 745   virtual void
 746   setObjValue (long idx, void *p)
 747   {
 748     data->store (idx, p);
 749   }
 750
 751   virtual int
 752   cmpValues (long, long)
 753   {
 754     return 0;
 755   }
 756
 757   virtual int
 758   cmpDatumValue (long, const Datum *)
 759   {
 760     return 0;
 761   }
 762
 763 private:
 764   VType_type dtype;
 765   Vector<void*> *data;
 766 };
 767
 768 class DataSTRING : public Data
 769 {
 770 public:
 771
 772   DataSTRING ()
 773   {
 774     data = new Vector<char*>;
 775   }
 776
 777   virtual
 778   ~DataSTRING ()
 779   {
 780     data->destroy ();
 781     delete data;
 782   }
 783
 784   virtual VType_type
 785   type ()
 786   {
 787     return TYPE_STRING;
 788   }
 789
 790   virtual void
 791   reset ()
 792   {
 793     data->reset ();
 794   }
 795
 796   virtual long
 797   getSize ()
 798   {
 799     return data->size ();
 800   }
 801
 802   virtual int
 803   fetchInt (long)
 804   {
 805     return 0;
 806   }
 807
 808   virtual unsigned long long
 809   fetchULong (long)
 810   {
 811     return 0LL;
 812   }
 813
 814   virtual long long
 815   fetchLong (long)
 816   {
 817     return 0LL;
 818   }
 819
 820   virtual char *
 821   fetchString (long i)
 822   {
 823     return strdup (data->fetch (i));
 824   }
 825
 826   virtual double
 827   fetchDouble (long)
 828   {
 829     return 0.0;
 830   }
 831
 832   virtual void *
 833   fetchObject (long i)
 834   {
 835     return data->fetch (i);
 836   }
 837
 838   virtual void
 839   setDatumValue (long idx, const Datum *val)
 840   {
 841     data->store (idx, val->l);
 842   }
 843
 844   virtual void
 845   setValue (long, uint64_t)
 846   {
 847     return;
 848   }
 849
 850   virtual void
 851   setObjValue (long idx, void *p)
 852   {
 853     data->store (idx, (char*) p);
 854   }
 855
 856   virtual int
 857   cmpValues (long, long)
 858   {
 859     return 0;
 860   }
 861
 862   virtual int
 863   cmpDatumValue (long, const Datum *)
 864   {
 865     return 0;
 866   }
 867
 868 private:
 869   Vector<char*> *data;
 870 };
 871
 872 class DataDOUBLE : public Data
 873 {
 874 public:
 875
 876   DataDOUBLE ()
 877   {
 878     data = new Vector<double>;
 879   }
 880
 881   virtual
 882   ~DataDOUBLE ()
 883   {
 884     delete data;
 885   }
 886
 887   virtual VType_type
 888   type ()
 889   {
 890     return TYPE_DOUBLE;
 891   }
 892
 893   virtual void
 894   reset ()
 895   {
 896     data->reset ();
 897   }
 898
 899   virtual long
 900   getSize ()
 901   {
 902     return data->size ();
 903   }
 904
 905   virtual int
 906   fetchInt (long i)
 907   {
 908     return (int) data->fetch (i);
 909   }
 910
 911   virtual unsigned long long
 912   fetchULong (long i)
 913   {
 914     return (unsigned long long) data->fetch (i);
 915   }
 916
 917   virtual long long
 918   fetchLong (long i)
 919   {
 920     return (long long) data->fetch (i);
 921   }
 922
 923   virtual char *
 924   fetchString (long i)
 925   {
 926     return dbe_sprintf (NTXT ("%f"), data->fetch (i));
 927   }
 928
 929   virtual double
 930   fetchDouble (long i)
 931   {
 932     return data->fetch (i);
 933   }
 934
 935   virtual void
 936   setDatumValue (long idx, const Datum *val)
 937   {
 938     data->store (idx, val->d);
 939   }
 940
 941   virtual void
 942   setValue (long idx, uint64_t val)
 943   {
 944     data->store (idx, (double) val);
 945   }
 946
 947   virtual void
 948   setObjValue (long, void*)
 949   {
 950     return;
 951   }
 952
 953   virtual void *
 954   fetchObject (long)
 955   {
 956     return NULL;
 957   }
 958
 959   virtual int
 960   cmpValues (long idx1, long idx2)
 961   {
 962     double d1 = data->fetch (idx1);
 963     double d2 = data->fetch (idx2);
 964     return d1 < d2 ? -1 : d1 > d2 ? 1 : 0;
 965   }
 966
 967   virtual int
 968   cmpDatumValue (long idx, const Datum *val)
 969   {
 970     double d1 = data->fetch (idx);
 971     double d2 = val->d;
 972     return d1 < d2 ? -1 : d1 > d2 ? 1 : 0;
 973   }
 974
 975 private:
 976   Vector<double> *data;
 977 };
 978
 979 Data *
 980 Data::newData (VType_type vtype)
 981 {
 982   switch (vtype)
 983     {
 984     case TYPE_INT32:
 985       return new DataINT32;
 986     case TYPE_UINT32:
 987       return new DataUINT32;
 988     case TYPE_INT64:
 989       return new DataINT64;
 990     case TYPE_UINT64:
 991       return new DataUINT64;
 992     case TYPE_OBJ:
 993       return new DataOBJECT;
 994     case TYPE_STRING:
 995       return new DataSTRING;
 996     case TYPE_DOUBLE:
 997       return new DataDOUBLE;
 998     default:
 999       return NULL;
1000     }
1001 }
1002
1003 /*
1004  *    class DataDescriptor
1005  */
1006 DataDescriptor::DataDescriptor (int _id, const char *_name, const char *_uname,
1007                                 int _flags)
1008 {
1009   isMaster = true;
1010   id = _id;
1011   name = _name ? strdup (_name) : strdup (NTXT (""));
1012   uname = _uname ? strdup (_uname) : strdup (NTXT (""));
1013   flags = _flags;
1014
1015   // master data, shared with reference copies:
1016   master_size = 0;
1017   master_resolveFrameInfoDone = false;
1018   props = new Vector<PropDescr*>;
1019   data = new Vector<Data*>;
1020   setsTBR = new Vector<Vector<long long>*>;
1021
1022   // master references point to self:
1023   ref_size = &master_size;
1024   ref_resolveFrameInfoDone = &master_resolveFrameInfoDone;
1025 }
1026
1027 DataDescriptor::DataDescriptor (int _id, const char *_name, const char *_uname,
1028                                 DataDescriptor* dDscr)
1029 {
1030   isMaster = false;
1031   id = _id;
1032   name = _name ? strdup (_name) : strdup (NTXT (""));
1033   uname = _uname ? strdup (_uname) : strdup (NTXT (""));
1034   flags = dDscr->flags;
1035
1036   // references point to master DataDescriptor
1037   ref_size = &dDscr->master_size;
1038   ref_resolveFrameInfoDone = &dDscr->master_resolveFrameInfoDone;
1039   props = dDscr->props;
1040   data = dDscr->data;
1041   setsTBR = dDscr->setsTBR;
1042
1043   // data that should never be accessed in reference copy
1044   master_size = -1;
1045   master_resolveFrameInfoDone = false;
1046 }
1047
1048 DataDescriptor::~DataDescriptor ()
1049 {
1050   free (name);
1051   free (uname);
1052   if (!isMaster)
1053     return;
1054   props->destroy ();
1055   delete props;
1056   data->destroy ();
1057   delete data;
1058   setsTBR->destroy ();
1059   delete setsTBR;
1060 }
1061
1062 void
1063 DataDescriptor::reset ()
1064 {
1065   if (!isMaster)
1066     return;
1067   for (int i = 0; i < data->size (); i++)
1068     {
1069       Data *d = data->fetch (i);
1070       if (d != NULL)
1071         d->reset ();
1072       Vector<long long> *set = setsTBR->fetch (i);
1073       if (set != NULL)
1074         set->reset ();
1075     }
1076   master_size = 0;
1077 }
1078
1079 PropDescr *
1080 DataDescriptor::getProp (int prop_id)
1081 {
1082   for (int i = 0; i < props->size (); i++)
1083     {
1084       PropDescr *propDscr = props->fetch (i);
1085       if (propDscr->propID == prop_id)
1086         return propDscr;
1087     }
1088   return NULL;
1089 }
1090
1091 Data *
1092 DataDescriptor::getData (int prop_id)
1093 {
1094   if (prop_id < 0 || prop_id >= data->size ())
1095     return NULL;
1096   return data->fetch (prop_id);
1097 }
1098
1099 void
1100 DataDescriptor::addProperty (PropDescr *propDscr)
1101 {
1102   if (propDscr == NULL)
1103     return;
1104   if (propDscr->propID < 0)
1105     return;
1106   PropDescr *oldProp = getProp (propDscr->propID);
1107   if (oldProp != NULL)
1108     {
1109       checkCompatibility (propDscr->vtype, oldProp->vtype); //YXXX depends on experiment correctness
1110       delete propDscr;
1111       return;
1112     }
1113   props->append (propDscr);
1114   data->store (propDscr->propID, Data::newData (propDscr->vtype));
1115   setsTBR->store (propDscr->propID, NULL);
1116 }
1117
1118 long
1119 DataDescriptor::addRecord ()
1120 {
1121   if (!isMaster)
1122     return -1;
1123   return master_size++;
1124 }
1125
1126 static void
1127 checkEntity (Vector<long long> *set, long long val)
1128 {
1129   // Binary search
1130   int lo = 0;
1131   int hi = set->size () - 1;
1132   while (lo <= hi)
1133     {
1134       int md = (lo + hi) / 2;
1135       long long ent = set->fetch (md);
1136       if (ent < val)
1137         lo = md + 1;
1138       else if (ent > val)
1139         hi = md - 1;
1140       else
1141         return;
1142     }
1143   set->insert (lo, val);
1144 }
1145
1146 void
1147 DataDescriptor::setDatumValue (int prop_id, long idx, const Datum *val)
1148 {
1149   if (idx >= *ref_size)
1150     return;
1151   Data *d = getData (prop_id);
1152   if (d != NULL)
1153     {
1154       VType_type datum_type = val->type;
1155       VType_type data_type = d->type ();
1156       checkCompatibility (datum_type, data_type);
1157       d->setDatumValue (idx, val);
1158       Vector<long long> *set = setsTBR->fetch (prop_id);
1159       if (set != NULL)// Sets are maintained
1160         checkEntity (set, d->fetchLong (idx));
1161     }
1162 }
1163
1164 void
1165 DataDescriptor::setValue (int prop_id, long idx, uint64_t val)
1166 {
1167   if (idx >= *ref_size)
1168     return;
1169   Data *d = getData (prop_id);
1170   if (d != NULL)
1171     {
1172       d->setValue (idx, val);
1173       Vector<long long> *set = setsTBR->fetch (prop_id);
1174       if (set != NULL)// Sets are maintained
1175         checkEntity (set, d->fetchLong (idx));
1176     }
1177 }
1178
1179 void
1180 DataDescriptor::setObjValue (int prop_id, long idx, void *val)
1181 {
1182   if (idx >= *ref_size)
1183     return;
1184   Data *d = getData (prop_id);
1185   if (d != NULL)
1186     d->setObjValue (idx, val);
1187 }
1188
1189 DataView *
1190 DataDescriptor::createView ()
1191 {
1192   return new DataView (this);
1193 }
1194
1195 DataView *
1196 DataDescriptor::createImmutableView ()
1197 {
1198   return new DataView (this, DataView::DV_IMMUTABLE);
1199 }
1200
1201 DataView *
1202 DataDescriptor::createExtManagedView ()
1203 {
1204   return new DataView (this, DataView::DV_EXT_MANAGED);
1205 }
1206
1207 int
1208 DataDescriptor::getIntValue (int prop_id, long idx)
1209 {
1210   Data *d = getData (prop_id);
1211   if (d == NULL || idx >= d->getSize ())
1212     return 0;
1213   return d->fetchInt (idx);
1214 }
1215
1216 unsigned long long
1217 DataDescriptor::getULongValue (int prop_id, long idx)
1218 {
1219   Data *d = getData (prop_id);
1220   if (d == NULL || idx >= d->getSize ())
1221     return 0L;
1222   return d->fetchULong (idx);
1223 }
1224
1225 long long
1226 DataDescriptor::getLongValue (int prop_id, long idx)
1227 {
1228   Data *d = getData (prop_id);
1229   if (d == NULL || idx >= d->getSize ())
1230     return 0L;
1231   return d->fetchLong (idx);
1232 }
1233
1234 void *
1235 DataDescriptor::getObjValue (int prop_id, long idx)
1236 {
1237   Data *d = getData (prop_id);
1238   if (d == NULL || idx >= d->getSize ())
1239     return NULL;
1240   return d->fetchObject (idx);
1241 }
1242
1243 static int
1244 pcmp (const void *p1, const void *p2, const void *arg)
1245 {
1246   long idx1 = *(long*) p1; // index1 into Data
1247   long idx2 = *(long*) p2; // index2 into Data
1248   for (Data **dsorted = (Data**) arg; *dsorted != DATA_SORT_EOL; dsorted++)
1249     {
1250       Data *data = *dsorted;
1251       if (data == NULL)// sort property not in this data, skip this criteria
1252         continue;
1253       int res = data->cmpValues (idx1, idx2);
1254       if (res)
1255         return res;
1256     }
1257   // Provide stable sort
1258   return idx1 < idx2 ? -1 : idx1 > idx2 ? 1 : 0;
1259 }
1260
1261 Vector<long long> *
1262 DataDescriptor::getSet (int prop_id)
1263 {
1264   if (prop_id < 0 || prop_id >= setsTBR->size ())
1265     return NULL;
1266   Vector<long long> *set = setsTBR->fetch (prop_id);
1267   if (set != NULL)
1268     return set;
1269
1270   Data *d = getData (prop_id);
1271   if (d == NULL)
1272     return NULL;
1273   set = new Vector<long long>;
1274   for (long i = 0; i<*ref_size; ++i)
1275     checkEntity (set, d->fetchLong (i));
1276   setsTBR->store (prop_id, set);
1277
1278   return set;
1279 }
1280
1281 /*
1282  *    class DataView
1283  */
1284 DataView::DataView (DataDescriptor *_ddscr)
1285 {
1286   init (_ddscr, DV_NORMAL);
1287 }
1288
1289 DataView::DataView (DataDescriptor *_ddscr, DataViewType _type)
1290 {
1291   init (_ddscr, _type);
1292 }
1293
1294 void
1295 DataView::init (DataDescriptor *_ddscr, DataViewType _type)
1296 {
1297   ddscr = _ddscr;
1298   type = _type;
1299   switch (type)
1300     {
1301     case DV_IMMUTABLE:
1302       ddsize = ddscr->getSize ();
1303       index = NULL;
1304       break;
1305     case DV_NORMAL:
1306     case DV_EXT_MANAGED:
1307       ddsize = 0;
1308       index = new Vector<long>;
1309       break;
1310     }
1311   for (int ii = 0; ii < (MAX_SORT_DIMENSIONS + 1); ii++)
1312     sortedBy[ii] = DATA_SORT_EOL;
1313   filter = NULL;
1314 }
1315
1316 DataView::~DataView ()
1317 {
1318   delete filter;
1319   delete index;
1320 }
1321
1322 void
1323 DataView::appendDataDescriptorId (long pkt_id /* ddscr index */)
1324 {
1325   if (type != DV_EXT_MANAGED)
1326     return; // updates allowed only on externally managed DataViews
1327   long curr_ddsize = ddscr->getSize ();
1328   if (pkt_id < 0 || pkt_id >= curr_ddsize)
1329     return; // error!
1330   index->append (pkt_id);
1331 }
1332
1333 void
1334 DataView::setDataDescriptorValue (int prop_id, long pkt_id, uint64_t val)
1335 {
1336   ddscr->setValue (prop_id, pkt_id, val);
1337 }
1338
1339 long long
1340 DataView::getDataDescriptorValue (int prop_id, long pkt_id)
1341 {
1342   return ddscr->getLongValue (prop_id, pkt_id);
1343 }
1344
1345 Vector<PropDescr*>*
1346 DataView::getProps ()
1347 {
1348   return ddscr->getProps ();
1349 };
1350
1351 PropDescr*
1352 DataView::getProp (int prop_id)
1353 {
1354   return ddscr->getProp (prop_id);
1355 };
1356
1357 void
1358 DataView::filter_in_chunks (fltr_dbe_ctx *dctx)
1359 {
1360   Expression::Context *e_ctx = new Expression::Context (dctx->fltr->ctx->dbev, dctx->fltr->ctx->exp);
1361   Expression *n_expr = dctx->fltr->expr->copy ();
1362   bool noParFilter = dctx->fltr->noParFilter;
1363   FilterExp *nFilter = new FilterExp (n_expr, e_ctx, noParFilter);
1364   long iter = dctx->begin;
1365   long end = dctx->end;
1366   long orig_ddsize = dctx->orig_ddsize;
1367   while (iter < end)
1368     {
1369       nFilter->put (dctx->tmpView, iter);
1370       if (nFilter->passes ())
1371         dctx->idxArr[iter - orig_ddsize] = 1;
1372       iter += 1;
1373     }
1374   delete nFilter;
1375 }
1376
1377 bool
1378 DataView::checkUpdate ()
1379 {
1380   long newSize = ddscr->getSize ();
1381   if (ddsize == newSize)
1382     return false;
1383   if (index == NULL)
1384     return false;
1385   if (type == DV_EXT_MANAGED)
1386     return false;
1387   bool updated = false;
1388   if (filter)
1389     {
1390       DataView *tmpView = ddscr->createImmutableView ();
1391       assert (tmpView->getSize () == newSize);
1392       while (ddsize < newSize)
1393         {
1394           filter->put (tmpView, ddsize);
1395           if (filter->passes ())
1396             index->append (ddsize);
1397           ddsize += 1;
1398         }
1399       delete tmpView;
1400       return updated;
1401     }
1402   while (ddsize < newSize)
1403     {
1404       index->append (ddsize);
1405       updated = true;
1406       ddsize += 1;
1407     }
1408   return updated;
1409 }
1410
1411 long
1412 DataView::getSize ()
1413 {
1414   if (checkUpdate () && sortedBy[0] != DATA_SORT_EOL)
1415     // note: after new filter is set, getSize() incurs cost of
1416     // sorting even if caller isn't interested in sort
1417     index->sort ((CompareFunc) pcmp, sortedBy);
1418
1419   if (index == NULL)
1420     return ddscr->getSize ();
1421   return index->size ();
1422 }
1423
1424 void
1425 DataView::setDatumValue (int prop_id, long idx, const Datum *val)
1426 {
1427   ddscr->setDatumValue (prop_id, getIdByIdx (idx), val);
1428 }
1429
1430 void
1431 DataView::setValue (int prop_id, long idx, uint64_t val)
1432 {
1433   ddscr->setValue (prop_id, getIdByIdx (idx), val);
1434 }
1435
1436 void
1437 DataView::setObjValue (int prop_id, long idx, void *val)
1438 {
1439   ddscr->setObjValue (prop_id, getIdByIdx (idx), val);
1440 }
1441
1442 int
1443 DataView::getIntValue (int prop_id, long idx)
1444 {
1445   return ddscr->getIntValue (prop_id, getIdByIdx (idx));
1446 }
1447
1448 unsigned long long
1449 DataView::getULongValue (int prop_id, long idx)
1450 {
1451   return ddscr->getULongValue (prop_id, getIdByIdx (idx));
1452 }
1453
1454 long long
1455 DataView::getLongValue (int prop_id, long idx)
1456 {
1457   return ddscr->getLongValue (prop_id, getIdByIdx (idx));
1458 }
1459
1460 void *
1461 DataView::getObjValue (int prop_id, long idx)
1462 {
1463   return ddscr->getObjValue (prop_id, getIdByIdx (idx));
1464 }
1465
1466 void
1467 DataView::sort (const int props[], int prop_count)
1468 {
1469   if (index == NULL)
1470     {
1471       assert (ASSERT_SKIP);
1472       return;
1473     }
1474   assert (prop_count >= 0 && prop_count < MAX_SORT_DIMENSIONS);
1475   bool sort_changed = false; // see if sort has changed...
1476   for (int ii = 0; ii <= prop_count; ii++)
1477     { // sortedBy size is prop_count+1
1478       Data *data;
1479       if (ii == prop_count)
1480         data = DATA_SORT_EOL; // special end of array marker
1481       else
1482         data = ddscr->getData (props[ii]);
1483       if (sortedBy[ii] != data)
1484         {
1485           sortedBy[ii] = data;
1486           sort_changed = true;
1487         }
1488     }
1489   if (!checkUpdate () && !sort_changed)
1490     return;
1491   index->sort ((CompareFunc) pcmp, sortedBy);
1492 }
1493
1494 void
1495 DataView::sort (int prop0)
1496 {
1497   sort (&prop0, 1);
1498 }
1499
1500 void
1501 DataView::sort (int prop0, int prop1)
1502 {
1503   int props[2] = {prop0, prop1};
1504   sort (props, 2);
1505 }
1506
1507 void
1508 DataView::sort (int prop0, int prop1, int prop2)
1509 {
1510   int props[3] = {prop0, prop1, prop2};
1511   sort (props, 3);
1512 }
1513
1514 void
1515 DataView::setFilter (FilterExp *f)
1516 {
1517   if (index == NULL)
1518     {
1519       assert (ASSERT_SKIP);
1520       return;
1521     }
1522   delete filter;
1523   filter = f;
1524   index->reset ();
1525   ddsize = 0;
1526   checkUpdate ();
1527 }
1528
1529 long
1530 DataView::getIdByIdx (long idx)
1531 {
1532   if (index == NULL)
1533     return idx;
1534   return index->fetch (idx);
1535 }
1536
1537 static int
1538 tvalcmp (long data_id, const Datum valColumns[], Data *sortedBy[])
1539 {
1540   for (int ii = 0; ii < MAX_SORT_DIMENSIONS; ii++)
1541     {
1542       if (sortedBy[ii] == DATA_SORT_EOL)
1543         break;
1544       Data *d = sortedBy[ii];
1545       if (d == NULL)// property doesn't exist in data; compare always matches
1546         continue;
1547       const Datum *tvalue = &valColumns[ii];
1548       int res = d->cmpDatumValue (data_id, tvalue);
1549       if (res)
1550         return res;
1551     }
1552   return 0;
1553 }
1554
1555 static void
1556 checkSortTypes (const Datum valColumns[], Data *sortedBy[])
1557 {
1558 #ifndef NDEBUG
1559   for (int ii = 0; ii < MAX_SORT_DIMENSIONS; ii++)
1560     {
1561       if (sortedBy[ii] == DATA_SORT_EOL)
1562         break;
1563       Data *d = sortedBy[ii];
1564       if (d == NULL)// property doesn't exist in data; compare always matches
1565         continue;
1566       VType_type datum_type = valColumns[ii].type;
1567       VType_type data_type = d->type ();
1568       checkCompatibility (datum_type, data_type);
1569     }
1570 #endif
1571 }
1572
1573 bool
1574 DataView::idxRootDimensionsMatch (long idx, const Datum valColumns[])
1575 {
1576   // compares idx vs. valColumns[] - If all dimensions match
1577   // (except sort leaf), then the leaf value is valid => return true.
1578   // Otherwise, return false.
1579   checkSortTypes (valColumns, sortedBy);
1580   if (idx < 0 || idx >= index->size ()) // fell off end of array
1581     return false;
1582   long data_id = index->fetch (idx);
1583
1584   // we will check all dimensions for a match except the "leaf" dimension
1585   for (int ii = 0; ii < (MAX_SORT_DIMENSIONS - 1); ii++)
1586     {
1587       if (sortedBy[ii + 1] == DATA_SORT_EOL)
1588         break; // we are at leaf dimension, don't care about it's value
1589       if (sortedBy[ii] == DATA_SORT_EOL)
1590         break; // end of list
1591       Data *d = sortedBy[ii];
1592       if (d == NULL) // property doesn't exist in data; compare always matches
1593         continue;
1594       const Datum *tvalue = &valColumns[ii];
1595       int res = d->cmpDatumValue (data_id, tvalue);
1596       if (res)
1597         return false;
1598     }
1599   return true;
1600 }
1601
1602 long
1603 DataView::getIdxByVals (const Datum valColumns[], Relation rel)
1604 {
1605   // checks sortedBy[] columns for match; relation only used on last column
1606   return getIdxByVals (valColumns, rel, -1, -1);
1607 }
1608
1609 long
1610 DataView::getIdxByVals (const Datum valColumns[], Relation rel,
1611                         long minIdx, long maxIdx)
1612 {
1613   // checks sortedBy[] columns for match; relation only used on last column
1614   checkSortTypes (valColumns, sortedBy);
1615   if (index == NULL || sortedBy[0] == DATA_SORT_EOL)
1616     return -1;
1617
1618   long lo;
1619   if (minIdx < 0)
1620     lo = 0;
1621   else
1622     lo = minIdx;
1623
1624   long hi;
1625   if (maxIdx < 0 || maxIdx >= index->size ())
1626     hi = index->size () - 1;
1627   else
1628     hi = maxIdx;
1629
1630   long md = -1;
1631   while (lo <= hi)
1632     {
1633       md = (lo + hi) / 2;
1634       int cmp = tvalcmp (index->fetch (md), valColumns, sortedBy);
1635       if (cmp < 0)
1636         {
1637           lo = md + 1;
1638           continue;
1639         }
1640       else if (cmp > 0)
1641         {
1642           hi = md - 1;
1643           continue;
1644         }
1645
1646       // cmp == 0, we have an exact match
1647       switch (rel)
1648         {
1649         case REL_LT:
1650           hi = md - 1; // continue searching
1651           break;
1652         case REL_GT:
1653           lo = md + 1; // continue searching
1654           break;
1655         case REL_LTEQ:
1656         case REL_GTEQ:
1657         case REL_EQ:
1658           // note: "md" may not be deterministic if multiple matches exist
1659           return md; // a match => done.
1660         }
1661     }
1662
1663   // no exact match found
1664   switch (rel)
1665     {
1666     case REL_LT:
1667     case REL_LTEQ:
1668       md = hi;
1669       break;
1670     case REL_GT:
1671     case REL_GTEQ:
1672       md = lo;
1673       break;
1674     case REL_EQ:
1675       return -1;
1676     }
1677   if (idxRootDimensionsMatch (md, valColumns))
1678     return md;
1679   return -1;
1680 }
1681
1682 void
1683 DataView::removeDbeViewIdx (long idx)
1684 {
1685   index->remove (idx);
1686 }
1687