js/src/nanojit/avmplus.h

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   4  * The contents of this file are subject to the Mozilla Public License Version 1.1 (the
   5  * "License"); you may not use this file except in compliance with the License. You may obtain
   6  * a copy of the License at http://www.mozilla.org/MPL/
   7  *
   8  * Software distributed under the License is distributed on an "AS IS" basis, WITHOUT
   9  * WARRANTY OF ANY KIND, either express or implied. See the License for the specific
  10  * language governing rights and limitations under the License.
  11  *
  12  * The Original Code is [Open Source Virtual Machine.]
  13  *
  14  * The Initial Developer of the Original Code is Adobe System Incorporated.  Portions created
  15  * by the Initial Developer are Copyright (C)[ 2004-2006 ] Adobe Systems Incorporated. All Rights
  16  * Reserved.
  17  *
  18  * Contributor(s): Adobe AS3 Team
  19  *                 Andreas Gal <gal@mozilla.com>
  20  *                 Asko Tontti <atontti@cc.hut.fi>
  21  *
  22  * Alternatively, the contents of this file may be used under the terms of either the GNU
  23  * General Public License Version 2 or later (the "GPL"), or the GNU Lesser General Public
  24  * License Version 2.1 or later (the "LGPL"), in which case the provisions of the GPL or the
  25  * LGPL are applicable instead of those above. If you wish to allow use of your version of this
  26  * file only under the terms of either the GPL or the LGPL, and not to allow others to use your
  27  * version of this file under the terms of the MPL, indicate your decision by deleting provisions
  28  * above and replace them with the notice and other provisions required by the GPL or the
  29  * LGPL. If you do not delete the provisions above, a recipient may use your version of this file
  30  * under the terms of any one of the MPL, the GPL or the LGPL.
  31  *
  32  ***** END LICENSE BLOCK ***** */
  33
  34 #ifndef avm_h___
  35 #define avm_h___
  36
  37 #include <assert.h>
  38 #include <string.h>
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41
  42 #if defined(AVMPLUS_LINUX) || defined(DARWIN) || defined(__FreeBSD__)
  43 #include <unistd.h>
  44 #include <sys/mman.h>
  45 #endif
  46
  47 #include "jstypes.h"
  48
  49 #define FASTCALL JS_FASTCALL
  50
  51 #if defined(JS_NO_FASTCALL)
  52 #define NJ_NO_FASTCALL
  53 #if defined(AVMPLUS_IA32)
  54 #define SIMULATE_FASTCALL(lr, state_ptr, frag_ptr, func_addr)   \
  55     asm volatile(                                               \
  56         "call *%%esi"                                           \
  57         : "=a" (lr)                                             \
  58         : "c" (state_ptr), "d" (frag_ptr), "S" (func_addr)      \
  59         : "memory", "cc"                                        \
  60     );
  61 #endif /* defined(AVMPLUS_IA32) */
  62 #endif /* defined(JS_NO_FASTCALL) */
  63
  64 #ifdef WIN32
  65 #include <windows.h>
  66 #endif
  67
  68 #ifdef DEBUG
  69 #if !defined _DEBUG
  70 #define _DEBUG
  71 #endif
  72 #define NJ_VERBOSE
  73 #define NJ_PROFILE
  74 #include <stdarg.h>
  75 #endif
  76
  77 #ifdef _DEBUG
  78 void NanoAssertFail();
  79 #endif
  80
  81 #define AvmAssert(x) assert(x)
  82 #define AvmAssertMsg(x, y)
  83 #define AvmDebugLog(x) printf x
  84
  85 #ifdef _MSC_VER
  86 /*
  87  * Can we just take a moment to think about what it means that MSVC doesn't have stdint.h in 2008?
  88  * Thanks for your time.
  89  */
  90 typedef JSUint8  uint8_t;
  91 typedef JSInt8   int8_t;
  92 typedef JSUint16 uint16_t;
  93 typedef JSInt16  int16_t;
  94 typedef JSUint32 uint32_t;
  95 typedef JSInt32  int32_t;
  96 typedef JSUint64 uint64_t;
  97 typedef JSInt64  int64_t;
  98 #else
  99 #include <stdint.h>
 100 #endif
 101
 102 #if defined(_MSC_VER) && defined(AVMPLUS_IA32)
 103 __declspec(naked) static inline __int64 rdtsc()
 104 {
 105     __asm
 106     {
 107         rdtsc;
 108         ret;
 109     }
 110 }
 111 #endif
 112
 113 #if defined(__i386__)
 114
 115 static __inline__ unsigned long long rdtsc(void)
 116 {
 117   unsigned long long int x;
 118      __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
 119      return x;
 120 }
 121 #elif defined(__x86_64__)
 122
 123 static __inline__ uint64_t rdtsc(void)
 124 {
 125   unsigned hi, lo;
 126   __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
 127   return ( (uint64_t)lo)|( ((uint64_t)hi)<<32 );
 128 }
 129
 130 #elif defined(__powerpc__)
 131
 132 typedef unsigned long long int unsigned long long;
 133
 134 static __inline__ unsigned long long rdtsc(void)
 135 {
 136   unsigned long long int result=0;
 137   unsigned long int upper, lower,tmp;
 138   __asm__ volatile(
 139                 "0:                  \n"
 140                 "\tmftbu   %0           \n"
 141                 "\tmftb    %1           \n"
 142                 "\tmftbu   %2           \n"
 143                 "\tcmpw    %2,%0        \n"
 144                 "\tbne     0b         \n"
 145                 : "=r"(upper),"=r"(lower),"=r"(tmp)
 146                 );
 147   result = upper;
 148   result = result<<32;
 149   result = result|lower;
 150
 151   return(result);
 152 }
 153
 154 #endif
 155
 156 struct JSContext;
 157
 158 namespace nanojit
 159 {
 160         class Fragment;
 161
 162         enum ExitType {
 163             BRANCH_EXIT,
 164             LOOP_EXIT,
 165             NESTED_EXIT,
 166             MISMATCH_EXIT,
 167             OOM_EXIT,
 168             OVERFLOW_EXIT
 169         };
 170
 171         struct SideExit
 172         {
 173         intptr_t ip_adj;
 174         intptr_t sp_adj;
 175         intptr_t rp_adj;
 176         Fragment *target;
 177         Fragment *from;
 178         int32_t calldepth;
 179         uint32 numGlobalSlots;
 180         uint32 numStackSlots;
 181         uint32 numStackSlotsBelowCurrentFrame;
 182         uint8 *typeMap;
 183         ExitType exitType;
 184 #if defined NJ_VERBOSE
 185                 uint32_t sid;
 186 #endif
 187         };
 188
 189         class LIns;
 190
 191         struct GuardRecord
 192         {
 193                 Fragment *target;
 194                 Fragment *from;
 195                 void *jmp;
 196                 void *origTarget;
 197                 SideExit *exit;
 198                 GuardRecord *outgoing;
 199                 GuardRecord *next;
 200                 LIns *guard;
 201                 int32_t calldepth;
 202 #if defined NJ_VERBOSE
 203                 uint32_t compileNbr;
 204                 uint32_t sid;
 205 #endif
 206         };
 207
 208         #define GuardRecordSize(g) sizeof(GuardRecord)
 209     #define SideExitSize(e) sizeof(SideExit)
 210 }
 211
 212 class GCObject
 213 {
 214 public:
 215     static void operator delete (void *gcObject)
 216     {
 217         free(gcObject);
 218     }
 219 };
 220
 221 #define MMGC_SUBCLASS_DECL : public GCObject
 222
 223 class GCFinalizedObject : public GCObject
 224 {
 225 public:
 226     static void operator delete (void *gcObject)
 227     {
 228         free(gcObject);
 229     }
 230 };
 231
 232 class GCHeap
 233 {
 234 public:
 235     int32_t kNativePageSize;
 236
 237     GCHeap()
 238     {
 239 #if defined _SC_PAGE_SIZE
 240         kNativePageSize = sysconf(_SC_PAGE_SIZE);
 241 #else
 242         kNativePageSize = 4096; // @todo: what is this?
 243 #endif
 244     }
 245
 246     inline void*
 247     Alloc(uint32_t pages)
 248     {
 249 #ifdef XP_WIN
 250         return VirtualAlloc(NULL,
 251                             pages * kNativePageSize,
 252                             MEM_COMMIT | MEM_RESERVE,
 253                             PAGE_EXECUTE_READWRITE);
 254 #elif defined AVMPLUS_LINUX || defined DARWIN
 255         /**
 256          * Don't use normal heap with mprotect+PROT_EXEC for executable code.
 257          * SELinux and friends don't allow this.
 258          */
 259         return mmap(NULL,
 260                     pages * kNativePageSize,
 261                     PROT_READ | PROT_WRITE | PROT_EXEC,
 262                     MAP_PRIVATE | MAP_ANON,
 263                     -1,
 264                     0);
 265 #else
 266         return valloc(pages * kNativePageSize);
 267 #endif
 268     }
 269
 270     inline void
 271     Free(void* p, uint32_t pages)
 272     {
 273 #ifdef XP_WIN
 274         VirtualFree(p, 0, MEM_RELEASE);
 275 #elif defined AVMPLUS_LINUX || defined DARWIN
 276         munmap(p, pages * kNativePageSize);
 277 #else
 278         free(p);
 279 #endif
 280     }
 281
 282 };
 283
 284 class GC
 285 {
 286     static GCHeap heap;
 287
 288 public:
 289     static inline void*
 290     Alloc(uint32_t bytes)
 291     {
 292         return calloc(1, bytes);
 293     }
 294
 295     static inline void
 296     Free(void* p)
 297     {
 298         free(p);
 299     }
 300
 301     static inline GCHeap*
 302     GetGCHeap()
 303     {
 304         return &heap;
 305     }
 306 };
 307
 308 inline void*
 309 operator new(size_t size, GC* gc)
 310 {
 311     return calloc(1, size);
 312 }
 313
 314 inline void
 315 operator delete(void* p)
 316 {
 317     free(p);
 318 }
 319
 320 #define DWB(x) x
 321 #define DRCWB(x) x
 322
 323 #define MMGC_MEM_TYPE(x)
 324
 325 typedef int FunctionID;
 326
 327 namespace avmplus
 328 {
 329     struct InterpState
 330     {
 331         void* sp; /* native stack pointer, stack[0] is spbase[0] */
 332         void* rp; /* call stack pointer */
 333         void* gp; /* global frame pointer */
 334         JSContext *cx; /* current VM context handle */
 335         void* eos; /* first unusable word after the native stack */
 336         void* eor; /* first unusable word after the call stack */
 337         nanojit::GuardRecord* nestedExit; /* innermost nested guard for NESTED_EXIT exits */
 338     };
 339
 340     class String
 341     {
 342     };
 343
 344     typedef class String AvmString;
 345
 346     class StringNullTerminatedUTF8
 347     {
 348         const char* cstr;
 349
 350     public:
 351         StringNullTerminatedUTF8(GC* gc, String* s)
 352         {
 353             cstr = strdup((const char*)s);
 354         }
 355
 356         ~StringNullTerminatedUTF8()
 357         {
 358             free((void*)cstr);
 359         }
 360
 361         inline
 362         const char* c_str()
 363         {
 364             return cstr;
 365         }
 366     };
 367
 368     typedef String* Stringp;
 369
 370     class AvmConfiguration
 371     {
 372     public:
 373         AvmConfiguration() {
 374             memset(this, 0, sizeof(AvmConfiguration));
 375 #ifdef DEBUG
 376             verbose = getenv("TRACEMONKEY") && strstr(getenv("TRACEMONKEY"), "verbose");
 377             verbose_addrs = 1;
 378             verbose_exits = 1;
 379             verbose_live = 1;
 380             show_stats = 1;
 381 #endif
 382             tree_opt = 0;
 383         }
 384
 385         uint32_t tree_opt:1;
 386         uint32_t quiet_opt:1;
 387         uint32_t verbose:1;
 388         uint32_t verbose_addrs:1;
 389         uint32_t verbose_live:1;
 390         uint32_t verbose_exits:1;
 391         uint32_t show_stats:1;
 392     };
 393
 394     static const int kstrconst_emptyString = 0;
 395
 396     class AvmInterpreter
 397     {
 398         class Labels {
 399         public:
 400             const char* format(const void* ip)
 401             {
 402                 static char buf[33];
 403                 sprintf(buf, "%p", ip);
 404                 return buf;
 405             }
 406         };
 407
 408         Labels _labels;
 409     public:
 410         Labels* labels;
 411
 412         AvmInterpreter()
 413         {
 414             labels = &_labels;
 415         }
 416
 417     };
 418
 419     class AvmConsole
 420     {
 421     public:
 422         AvmConsole& operator<<(const char* s)
 423         {
 424             fprintf(stdout, "%s", s);
 425             return *this;
 426         }
 427     };
 428
 429     class AvmCore
 430     {
 431     public:
 432         AvmInterpreter interp;
 433         AvmConsole console;
 434
 435         static AvmConfiguration config;
 436         static GC* gc;
 437         static String* k_str[];
 438         static bool sse2_available;
 439
 440         static inline bool
 441         use_sse2()
 442         {
 443             return sse2_available;
 444         }
 445
 446         static inline bool
 447         quiet_opt()
 448         {
 449             return config.quiet_opt;
 450         }
 451
 452         static inline bool
 453         verbose()
 454         {
 455             return config.verbose;
 456         }
 457
 458         static inline GC*
 459         GetGC()
 460         {
 461             return gc;
 462         }
 463
 464         static inline String* newString(const char* cstr) {
 465             return (String*)strdup(cstr);
 466         }
 467     };
 468
 469     class OSDep
 470     {
 471     public:
 472         static inline void
 473         getDate()
 474         {
 475         }
 476     };
 477
 478     /**
 479      * The List<T> template implements a simple List, which can
 480      * be templated to support different types.
 481      *
 482      * Elements can be added to the end, modified in the middle,
 483      * but no holes are allowed.  That is for set(n, v) to work
 484      * size() > n
 485      *
 486      * Note that [] operators are provided and you can violate the
 487      * set properties using these operators, if you want a real
 488      * list dont use the [] operators, if you want a general purpose
 489      * array use the [] operators.
 490      */
 491
 492     enum ListElementType { LIST_NonGCObjects, LIST_GCObjects };
 493
 494     template <typename T, ListElementType kElementType>
 495     class List
 496     {
 497     public:
 498         enum { kInitialCapacity = 128 };
 499
 500         List(GC *_gc, uint32_t _capacity=kInitialCapacity) : data(NULL), len(0), capacity(0)
 501         {
 502             ensureCapacity(_capacity);
 503         }
 504
 505         ~List()
 506         {
 507             //clear();
 508             destroy();
 509             // zero out in case we are part of an RCObject
 510             len = 0;
 511         }
 512
 513         inline void destroy()
 514         {
 515             if (data)
 516                 free(data);
 517         }
 518
 519         // 'this' steals the guts of 'that' and 'that' gets reset.
 520         void FASTCALL become(List& that)
 521         {
 522             this->destroy();
 523
 524             this->data = that.data;
 525             this->len = that.len;
 526             this->capacity = that.capacity;
 527
 528             that.data = 0;
 529             that.len = 0;
 530             that.capacity = 0;
 531         }
 532         uint32_t FASTCALL add(T value)
 533         {
 534             if (len >= capacity) {
 535                 grow();
 536             }
 537             wb(len++, value);
 538             return len-1;
 539         }
 540
 541         inline bool isEmpty() const
 542         {
 543             return len == 0;
 544         }
 545
 546         inline uint32_t size() const
 547         {
 548             return len;
 549         }
 550
 551         inline T get(uint32_t index) const
 552         {
 553             AvmAssert(index < len);
 554             return *(T*)(data + index);
 555         }
 556
 557         void FASTCALL set(uint32_t index, T value)
 558         {
 559             AvmAssert(index < capacity);
 560             if (index >= len)
 561             {
 562                 len = index+1;
 563             }
 564             AvmAssert(len <= capacity);
 565             wb(index, value);
 566         }
 567
 568         inline void clear()
 569         {
 570             zero_range(0, len);
 571             len = 0;
 572         }
 573
 574         int FASTCALL indexOf(T value) const
 575         {
 576             for(uint32_t i=0; i<len; i++)
 577                 if (get(i) == value)
 578                     return i;
 579             return -1;
 580         }
 581
 582         int FASTCALL lastIndexOf(T value) const
 583         {
 584             for(int32_t i=len-1; i>=0; i--)
 585                 if (get(i) == value)
 586                     return i;
 587             return -1;
 588         }
 589
 590         inline T last()
 591         {
 592             return get(len-1);
 593         }
 594
 595         T FASTCALL removeLast()
 596         {
 597             if(isEmpty())
 598                 return undef_list_val();
 599             T t = get(len-1);
 600             set(len-1, undef_list_val());
 601             len--;
 602             return t;
 603         }
 604
 605         inline T operator[](uint32_t index) const
 606         {
 607             AvmAssert(index < capacity);
 608             return get(index);
 609         }
 610
 611         void FASTCALL ensureCapacity(uint32_t cap)
 612         {
 613             if (cap > capacity) {
 614                 if (data == NULL) {
 615                     data = (T*)calloc(1, factor(cap));
 616                 } else {
 617                     data = (T*)realloc(data, factor(cap));
 618                     zero_range(capacity, cap - capacity);
 619                 }
 620                 capacity = cap;
 621             }
 622         }
 623
 624         void FASTCALL insert(uint32_t index, T value, uint32_t count = 1)
 625         {
 626             AvmAssert(index <= len);
 627             AvmAssert(count > 0);
 628             ensureCapacity(len+count);
 629             memmove(data + index + count, data + index, factor(len - index));
 630             wbzm(index, index+count, value);
 631             len += count;
 632         }
 633
 634         T FASTCALL removeAt(uint32_t index)
 635         {
 636             T old = get(index);
 637             // dec the refcount on the one we're removing
 638             wb(index, undef_list_val());
 639             memmove(data + index, data + index + 1, factor(len - index - 1));
 640             len--;
 641             return old;
 642         }
 643
 644     private:
 645         void FASTCALL grow()
 646         {
 647             // growth is fast at first, then slows at larger list sizes.
 648             uint32_t newMax = 0;
 649             const uint32_t curMax = capacity;
 650             if (curMax == 0)
 651                 newMax = kInitialCapacity;
 652             else if(curMax > 15)
 653                 newMax = curMax * 3/2;
 654             else
 655                 newMax = curMax * 2;
 656
 657             ensureCapacity(newMax);
 658         }
 659
 660         inline void do_wb_nongc(T* slot, T value)
 661         {
 662             *slot = value;
 663         }
 664
 665         inline void do_wb_gc(GCObject** slot, const GCObject** value)
 666         {
 667             *slot = (GCObject*)*value;
 668         }
 669
 670         void FASTCALL wb(uint32_t index, T value)
 671         {
 672             AvmAssert(index < capacity);
 673             AvmAssert(data != NULL);
 674             T* slot = &data[index];
 675             do_wb_nongc(slot, value);
 676         }
 677
 678         // multiple wb call with the same value, and assumption that existing value is all zero bits,
 679         // like
 680         //  for (uint32_t u = index; u < index_end; ++u)
 681         //      wb(u, value);
 682         void FASTCALL wbzm(uint32_t index, uint32_t index_end, T value)
 683         {
 684             AvmAssert(index < capacity);
 685             AvmAssert(index_end <= capacity);
 686             AvmAssert(index < index_end);
 687             AvmAssert(data != NULL);
 688             T* slot = data + index;
 689             for (  ; index < index_end; ++index, ++slot)
 690                 do_wb_nongc(slot, value);
 691         }
 692
 693         inline uint32_t factor(uint32_t index) const
 694         {
 695             return index * sizeof(T);
 696         }
 697
 698         void FASTCALL zero_range(uint32_t _first, uint32_t _count)
 699         {
 700             memset(data + _first, 0, factor(_count));
 701         }
 702
 703         // stuff that needs specialization based on the type
 704         static inline T undef_list_val();
 705
 706     private:
 707         List(const List& toCopy);           // unimplemented
 708         void operator=(const List& that);   // unimplemented
 709
 710     // ------------------------ DATA SECTION BEGIN
 711     private:
 712         T* data;
 713         uint32_t len;
 714         uint32_t capacity;
 715     // ------------------------ DATA SECTION END
 716
 717     };
 718
 719     // stuff that needs specialization based on the type
 720     template<typename T, ListElementType kElementType>
 721     /* static */ inline T List<T, kElementType>::undef_list_val() { return T(0); }
 722
 723     /**
 724      * The SortedMap<K,T> template implements an object that
 725      * maps keys to values.   The keys are sorted
 726      * from smallest to largest in the map. Time of operations
 727      * is as follows:
 728      *   put() is O(1) if the key is higher than any existing
 729      *         key; O(logN) if the key already exists,
 730      *         and O(N) otherwise.
 731      *   get() is an O(logN) binary search.
 732      *
 733      * no duplicates are allowed.
 734      */
 735     template <class K, class T, ListElementType valType>
 736     class SortedMap
 737     {
 738     public:
 739         enum { kInitialCapacity= 64 };
 740
 741         SortedMap(GC* gc, int _capacity=kInitialCapacity)
 742           : keys(gc, _capacity), values(gc, _capacity)
 743         {
 744         }
 745
 746         bool isEmpty() const
 747         {
 748             return keys.size() == 0;
 749         }
 750
 751         int size() const
 752         {
 753             return keys.size();
 754         }
 755
 756         void clear()
 757         {
 758             keys.clear();
 759             values.clear();
 760         }
 761
 762         void destroy()
 763         {
 764             keys.destroy();
 765             values.destroy();
 766         }
 767
 768         T put(K k, T v)
 769         {
 770             if (keys.size() == 0 || k > keys.last())
 771             {
 772                 keys.add(k);
 773                 values.add(v);
 774                 return (T)v;
 775             }
 776             else
 777             {
 778                 int i = find(k);
 779                 if (i >= 0)
 780                 {
 781                     T old = values[i];
 782                     keys.set(i, k);
 783                     values.set(i, v);
 784                     return old;
 785                 }
 786                 else
 787                 {
 788                     i = -i - 1; // recover the insertion point
 789                     AvmAssert(keys.size() != (uint32_t)i);
 790                     keys.insert(i, k);
 791                     values.insert(i, v);
 792                     return v;
 793                 }
 794             }
 795         }
 796
 797         T get(K k) const
 798         {
 799             int i = find(k);
 800             return i >= 0 ? values[i] : 0;
 801         }
 802
 803         bool get(K k, T& v) const
 804         {
 805             int i = find(k);
 806             if (i >= 0)
 807             {
 808                 v = values[i];
 809                 return true;
 810             }
 811             return false;
 812         }
 813
 814         bool containsKey(K k) const
 815         {
 816             int i = find(k);
 817             return (i >= 0) ? true : false;
 818         }
 819
 820         T remove(K k)
 821         {
 822             int i = find(k);
 823             return removeAt(i);
 824         }
 825
 826         T removeAt(int i)
 827         {
 828             T old = values.removeAt(i);
 829             keys.removeAt(i);
 830             return old;
 831         }
 832
 833         T removeFirst() { return isEmpty() ? (T)0 : removeAt(0); }
 834         T removeLast()  { return isEmpty() ? (T)0 : removeAt(keys.size()-1); }
 835         T first() const { return isEmpty() ? (T)0 : values[0]; }
 836         T last()  const { return isEmpty() ? (T)0 : values[keys.size()-1]; }
 837
 838         K firstKey() const  { return isEmpty() ? 0 : keys[0]; }
 839         K lastKey() const   { return isEmpty() ? 0 : keys[keys.size()-1]; }
 840
 841         // iterator
 842         T   at(int i) const { return values[i]; }
 843         K   keyAt(int i) const { return keys[i]; }
 844
 845         int findNear(K k) const {
 846             int i = find(k);
 847             return i >= 0 ? i : -i-2;
 848         }
 849     protected:
 850         List<K, LIST_NonGCObjects> keys;
 851         List<T, valType> values;
 852
 853         int find(K k) const
 854         {
 855             int lo = 0;
 856             int hi = keys.size()-1;
 857
 858             while (lo <= hi)
 859             {
 860                 int i = (lo + hi)/2;
 861                 K m = keys[i];
 862                 if (k > m)
 863                     lo = i + 1;
 864                 else if (k < m)
 865                     hi = i - 1;
 866                 else
 867                     return i; // key found
 868             }
 869             return -(lo + 1);  // key not found, low is the insertion point
 870         }
 871     };
 872
 873     #define GCSortedMap SortedMap
 874
 875     /**
 876      * Bit vectors are an efficent method of keeping True/False information
 877      * on a set of items or conditions. Class BitSet provides functions
 878      * to manipulate individual bits in the vector.
 879      *
 880      * Since most vectors are rather small an array of longs is used by
 881      * default to house the value of the bits.  If more bits are needed
 882      * then an array is allocated dynamically outside of this object.
 883      *
 884      * This object is not optimized for a fixed sized bit vector
 885      * it instead allows for dynamically growing the bit vector.
 886      */
 887     class BitSet
 888     {
 889         public:
 890             enum {  kUnit = 8*sizeof(long),
 891                     kDefaultCapacity = 4   };
 892
 893             BitSet()
 894             {
 895                 capacity = kDefaultCapacity;
 896                 reset();
 897             }
 898
 899             ~BitSet()
 900             {
 901                 if (capacity > kDefaultCapacity)
 902                     delete bits.ptr;
 903             }
 904
 905             void reset()
 906             {
 907                 if (capacity > kDefaultCapacity)
 908                     for(int i=0; i<capacity; i++)
 909                         bits.ptr[i] = 0;
 910                 else
 911                     for(int i=0; i<capacity; i++)
 912                         bits.ar[i] = 0;
 913             }
 914
 915             void set(GC *gc, int bitNbr)
 916             {
 917                 int index = bitNbr / kUnit;
 918                 int bit = bitNbr % kUnit;
 919                 if (index >= capacity)
 920                     grow(gc, index+1);
 921
 922                 if (capacity > kDefaultCapacity)
 923                     bits.ptr[index] |= (1<<bit);
 924                 else
 925                     bits.ar[index] |= (1<<bit);
 926             }
 927
 928             void clear(int bitNbr)
 929             {
 930                 int index = bitNbr / kUnit;
 931                 int bit = bitNbr % kUnit;
 932                 if (index < capacity)
 933                 {
 934                     if (capacity > kDefaultCapacity)
 935                         bits.ptr[index] &= ~(1<<bit);
 936                     else
 937                         bits.ar[index] &= ~(1<<bit);
 938                 }
 939             }
 940
 941             bool get(int bitNbr) const
 942             {
 943                 int index = bitNbr / kUnit;
 944                 int bit = bitNbr % kUnit;
 945                 bool value = false;
 946                 if (index < capacity)
 947                 {
 948                     if (capacity > kDefaultCapacity)
 949                         value = ( bits.ptr[index] & (1<<bit) ) ? true : false;
 950                     else
 951                         value = ( bits.ar[index] & (1<<bit) ) ? true : false;
 952                 }
 953                 return value;
 954             }
 955
 956         private:
 957             // Grow the array until at least newCapacity big
 958             void grow(GC *gc, int newCapacity)
 959             {
 960                 // create vector that is 2x bigger than requested
 961                 newCapacity *= 2;
 962                 //MEMTAG("BitVector::Grow - long[]");
 963                 long* newBits = (long*)calloc(1, newCapacity * sizeof(long));
 964                 //memset(newBits, 0, newCapacity * sizeof(long));
 965
 966                 // copy the old one
 967                 if (capacity > kDefaultCapacity)
 968                     for(int i=0; i<capacity; i++)
 969                         newBits[i] = bits.ptr[i];
 970                 else
 971                     for(int i=0; i<capacity; i++)
 972                         newBits[i] = bits.ar[i];
 973
 974                 // in with the new out with the old
 975                 if (capacity > kDefaultCapacity)
 976                     free(bits.ptr);
 977
 978                 bits.ptr = newBits;
 979                 capacity = newCapacity;
 980             }
 981
 982             // by default we use the array, but if the vector
 983             // size grows beyond kDefaultCapacity we allocate
 984             // space dynamically.
 985             int capacity;
 986             union
 987             {
 988                 long ar[kDefaultCapacity];
 989                 long*  ptr;
 990             }
 991             bits;
 992     };
 993 }
 994
 995 #endif