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