nanojit/Containers.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2004-2007
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef __nanojit_Containers__
  41 #define __nanojit_Containers__
  42
  43 namespace nanojit
  44 {
  45     /** simple linear bit array, memory taken from Allocator
  46      *  warning: when bit array grows, old memory is wasted since it
  47      *  was allocated from Allocator.  pre-size the bitmap when possible
  48      *  by passing nbits to the constructor. */
  49     class BitSet {
  50         Allocator &allocator;
  51         int cap;
  52         int64_t *bits;
  53         static const int64_t ONE = 1;
  54         static const int SHIFT = 6;
  55
  56         inline int bitnum2word(int i) {
  57             return i >> 6;
  58         }
  59         inline int64_t bitnum2mask(int i) {
  60             return ONE << (i & 63);
  61         }
  62
  63         /** keep doubling array to fit at least w words */
  64         void grow(int w);
  65
  66     public:
  67         BitSet(Allocator& allocator, int nbits=128);
  68
  69         /** clear all bits */
  70         void reset();
  71
  72         /** perform a bitwise or with BitSet other, return true if
  73          *  this bitset was modified */
  74         bool setFrom(BitSet& other);
  75
  76         /** return bit i as a bool */
  77         bool get(int i) {
  78             NanoAssert(i >= 0);
  79             int w = bitnum2word(i);
  80             if (w < cap)
  81                 return (bits[w] & bitnum2mask(i)) != 0;
  82             return false;
  83         }
  84
  85         /** set bit i */
  86         void set(int i) {
  87             NanoAssert(i >= 0);
  88             int w = bitnum2word(i);
  89             if (w >= cap)
  90                 grow(w);
  91             bits[w] |= bitnum2mask(i);
  92         }
  93
  94         /** clear bit i */
  95         void clear(int i) {
  96             NanoAssert(i >= 0);
  97             int w = bitnum2word(i);
  98             if (w < cap)
  99                 bits[w] &= ~bitnum2mask(i);
 100         }
 101     };
 102
 103     /** Seq is a single node in a linked list */
 104     template<class T> class Seq {
 105     public:
 106         Seq(T head, Seq<T>* tail=NULL) : head(head), tail(tail) {}
 107         T       head;
 108         Seq<T>* tail;
 109     };
 110
 111     /** SeqBuilder is used to create a linked list of Seq<T> by inserting
 112      *  nodes either at the beginning, with insert(), or at the end, with
 113      *  add().  Once built, the actual list can be retained while this
 114      *  SeqBuilder can be discarded.  */
 115     template<class T> class SeqBuilder {
 116     public:
 117         SeqBuilder(Allocator& allocator)
 118             : allocator(allocator)
 119             , items(NULL)
 120             , last(NULL)
 121         { }
 122
 123         /** add item to beginning of list */
 124         void insert(T item) {
 125             Seq<T>* e = new (allocator) Seq<T>(item, items);
 126             if (last == NULL)
 127                 last = e;
 128             items = e;
 129         }
 130
 131         /** add item to end of list */
 132         void add(T item) {
 133             Seq<T>* e = new (allocator) Seq<T>(item);
 134             if (last == NULL)
 135                 items = e;
 136             else
 137                 last->tail = e;
 138             last = e;
 139         }
 140
 141         /** return first item in sequence */
 142         Seq<T>* get() const {
 143             return items;
 144         }
 145
 146         /** self explanitory */
 147         bool isEmpty() const {
 148             return items == NULL;
 149         }
 150
 151         /** de-reference all items */
 152         void clear() {
 153             items = last = NULL;
 154         }
 155
 156     private:
 157         Allocator& allocator;
 158         Seq<T>* items;
 159         Seq<T>* last;
 160     };
 161
 162 #ifdef NANOJIT_64BIT
 163     static inline size_t murmurhash(const void *key, size_t len) {
 164         const uint64_t m = 0xc6a4a7935bd1e995;
 165         const int r = 47;
 166         uint64_t h = 0;
 167
 168         const uint64_t *data = (const uint64_t*)key;
 169         const uint64_t *end = data + (len/8);
 170
 171         while(data != end)
 172             {
 173                 uint64_t k = *data++;
 174
 175                 k *= m;
 176                 k ^= k >> r;
 177                 k *= m;
 178
 179                 h ^= k;
 180                 h *= m;
 181             }
 182
 183         const unsigned char *data2 = (const unsigned char*)data;
 184
 185         switch(len & 7) {
 186         case 7: h ^= uint64_t(data2[6]) << 48;
 187         case 6: h ^= uint64_t(data2[5]) << 40;
 188         case 5: h ^= uint64_t(data2[4]) << 32;
 189         case 4: h ^= uint64_t(data2[3]) << 24;
 190         case 3: h ^= uint64_t(data2[2]) << 16;
 191         case 2: h ^= uint64_t(data2[1]) << 8;
 192         case 1: h ^= uint64_t(data2[0]);
 193             h *= m;
 194         };
 195
 196         h ^= h >> r;
 197         h *= m;
 198         h ^= h >> r;
 199
 200         return (size_t)h;
 201     }
 202 #else
 203     static inline size_t murmurhash(const void * key, size_t len) {
 204         const uint32_t m = 0x5bd1e995;
 205         const int r = 24;
 206         uint32_t h = 0;
 207
 208         const unsigned char * data = (const unsigned char *)key;
 209         while(len >= 4) {
 210             uint32_t k = *(size_t *)(void*)data;
 211
 212             k *= m;
 213             k ^= k >> r;
 214             k *= m;
 215
 216             h *= m;
 217             h ^= k;
 218
 219             data += 4;
 220             len -= 4;
 221         }
 222
 223         switch(len) {
 224         case 3: h ^= data[2] << 16;
 225         case 2: h ^= data[1] << 8;
 226         case 1: h ^= data[0];
 227             h *= m;
 228         };
 229
 230         h ^= h >> 13;
 231         h *= m;
 232         h ^= h >> 15;
 233
 234         return (size_t)h;
 235     }
 236 #endif
 237
 238     template<class K> struct DefaultHash {
 239         static size_t hash(const K &k) {
 240             // (const void*) cast is required by ARM RVCT 2.2
 241             return murmurhash((const void*) &k, sizeof(K));
 242         }
 243     };
 244
 245     template<class K> struct DefaultHash<K*> {
 246         static size_t hash(K* k) {
 247             uintptr_t h = (uintptr_t) k;
 248             // move the low 3 bits higher up since they're often 0
 249             h = (h>>3) ^ (h<<((sizeof(uintptr_t) * 8) - 3));
 250             return (size_t) h;
 251         }
 252     };
 253
 254     /** Bucket hashtable with a fixed # of buckets (never rehash)
 255      *  Intended for use when a reasonable # of buckets can be estimated ahead of time.
 256      *  Note that operator== is used to compare keys.
 257      */
 258     template<class K, class T, class H=DefaultHash<K> > class HashMap {
 259         Allocator& allocator;
 260         size_t nbuckets;
 261         class Node {
 262         public:
 263             K key;
 264             T value;
 265             Node(K k, T v) : key(k), value(v) { }
 266         };
 267         Seq<Node>** buckets;
 268
 269         /** return the node containing K, and the bucket index, or NULL if not found */
 270         Node* find(K k, size_t &i) {
 271             i = H::hash(k) % nbuckets;
 272             for (Seq<Node>* p = buckets[i]; p != NULL; p = p->tail) {
 273                 if (p->head.key == k)
 274                     return &p->head;
 275             }
 276             return NULL;
 277         }
 278     public:
 279         HashMap(Allocator& a, size_t nbuckets = 16)
 280             : allocator(a)
 281             , nbuckets(nbuckets)
 282             , buckets(new (a) Seq<Node>*[nbuckets])
 283         {
 284             NanoAssert(nbuckets > 0);
 285             clear();
 286         }
 287
 288         /** clear all buckets.  Since we allocate all memory from Allocator,
 289          *  nothing needs to be freed. */
 290         void clear() {
 291             VMPI_memset(buckets, 0, sizeof(Seq<Node>*) * nbuckets);
 292         }
 293
 294         /** add (k,v) to the map.  If k is already in the map, replace the value */
 295         void put(const K& k, const T& v) {
 296             size_t i;
 297             Node* n = find(k, i);
 298             if (n) {
 299                 n->value = v;
 300                 return;
 301             }
 302             buckets[i] = new (allocator) Seq<Node>(Node(k,v), buckets[i]);
 303         }
 304
 305         /** return v for element k, or T(0) if k is not present */
 306         T get(const K& k) {
 307             size_t i;
 308             Node* n = find(k, i);
 309             return n ? n->value : 0;
 310         }
 311
 312         /** returns true if k is in the map. */
 313         bool containsKey(const K& k) {
 314             size_t i;
 315             return find(k, i) != 0;
 316         }
 317
 318         /** remove k from the map, if it is present.  if not, remove()
 319          *  silently returns */
 320         void remove(const K& k) {
 321             size_t i = H::hash(k) % nbuckets;
 322             Seq<Node>** prev = &buckets[i];
 323             for (Seq<Node>* p = buckets[i]; p != NULL; p = p->tail) {
 324                 if (p->head.key == k) {
 325                     (*prev) = p->tail;
 326                     return;
 327                 }
 328                 prev = &p->tail;
 329             }
 330         }
 331
 332         /** Iter is an iterator for HashMap, intended to be instantiated on
 333          *  the stack.  Iteration order is undefined.  Mutating the hashmap
 334          *  while iteration is in progress gives undefined results.  All iteration
 335          *  state is in class Iter, so multiple iterations can be in progress
 336          *  at the same time.  for example:
 337          *
 338          *  HashMap<K,T>::Iter iter(map);
 339          *  while (iter.next()) {
 340          *     K *k = iter.key();
 341          *     T *t = iter.value();
 342          *  }
 343          */
 344         class Iter {
 345             friend class HashMap;
 346             const HashMap<K,T,H> &map;
 347             int bucket;
 348             const Seq<Node>* current;
 349
 350         public:
 351             Iter(HashMap<K,T,H>& map) : map(map), bucket((int)map.nbuckets-1), current(NULL)
 352             { }
 353
 354             /** return true if more (k,v) remain to be visited */
 355             bool next() {
 356                 if (current)
 357                     current = current->tail;
 358                 while (bucket >= 0 && !current)
 359                     current = map.buckets[bucket--];
 360                 return current != NULL;
 361             }
 362
 363             /** return the current key */
 364             const K& key() const {
 365                 NanoAssert(current != NULL);
 366                 return current->head.key;
 367             }
 368
 369             /** return the current value */
 370             const T& value() const {
 371                 NanoAssert(current != NULL);
 372                 return current->head.value;
 373             }
 374         };
 375
 376         /** return true if the hashmap has no elements */
 377         bool isEmpty() {
 378             Iter iter(*this);
 379             return !iter.next();
 380         }
 381     };
 382
 383     /**
 384      * Simple binary tree.  No balancing is performed under the assumption
 385      * that the only users of this structure are not performance critical.
 386      */
 387     template<class K, class T> class TreeMap {
 388         Allocator& alloc;
 389         class Node {
 390         public:
 391             Node* left;
 392             Node* right;
 393             K key;
 394             T value;
 395             Node(K k, T v) : left(NULL), right(NULL), key(k), value(v)
 396             { }
 397         };
 398         Node* root;
 399
 400         /**
 401          * helper method to recursively insert (k,v) below Node n or a child
 402          * of n so that the binary search tree remains well formed.
 403          */
 404         void insert(Node* &n, K k, T v) {
 405             if (!n)
 406                 n = new (alloc) Node(k, v);
 407             else if (k == n->key)
 408                 n->value = v;
 409             else if (k < n->key)
 410                 insert(n->left, k, v);
 411             else
 412                 insert(n->right, k, v);
 413         }
 414
 415         /**
 416          * search for key k below Node n and return n if found, or the
 417          * closest parent n where k should be inserted.
 418          */
 419         Node* find(Node* n, K k) {
 420             if (!n)
 421                 return NULL;
 422             if (k == n->key)
 423                 return n;
 424             if (k < n->key)
 425                 return find(n->left, k);
 426             if (n->right)
 427                 return find(n->right, k);
 428             return n;
 429         }
 430
 431     public:
 432         TreeMap(Allocator& alloc) : alloc(alloc), root(NULL)
 433         { }
 434
 435         /** set k = v in the map.  if k already exists, replace its value */
 436         void put(K k, T v) {
 437             insert(root, k, v);
 438         }
 439
 440         /** return the closest key that is <= k, or NULL if k
 441             is smaller than every key in the Map. */
 442         K findNear(K k) {
 443             Node* n = find(root, k);
 444             return n ? n->key : 0;
 445         }
 446
 447         /** returns the value for k or NULL */
 448         T get(K k) {
 449             Node* n = find(root, k);
 450             return (n && n->key == k) ? n->value : 0;
 451         }
 452
 453         /** returns true iff k is in the Map. */
 454         bool containsKey(K k) {
 455             Node* n = find(root, k);
 456             return n && n->key == k;
 457         }
 458
 459         /** make the tree empty.  trivial since we dont manage elements */
 460         void clear() {
 461             root = NULL;
 462         }
 463     };
 464 }
 465 #endif // __nanojit_Containers__