hphp/runtime/base/shared/immutable_map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- Facebook, Inc. (http://www.facebook.com)         |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_IMMUTABLE_MAP_H_
  18 #define incl_HPHP_IMMUTABLE_MAP_H_
  19
  20 #include "hphp/runtime/base/types.h"
  21 #include "hphp/util/lock.h"
  22 #include "hphp/util/hash.h"
  23 #include "hphp/util/atomic.h"
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27
  28 class SharedVariant;
  29 /**
  30  * an immutable map is a php-style array that can take strings and
  31  * ints as keys. the map also stores the order in which the elements
  32  * are inserted. once an element is added to the map, it can not be
  33  * removed.
  34  */
  35 class ImmutableMap {
  36 public:
  37   int indexOf(const StringData* key);
  38   int indexOf(int64_t key);
  39
  40   SharedVariant* getKeyIndex(int index) {
  41     assert(index < size());
  42     return buckets()[index].key;
  43   }
  44
  45   SharedVariant* getValIndex(int index) {
  46     assert(index < size());
  47     return buckets()[index].val;
  48   }
  49
  50   unsigned size() const {
  51     return m.m_num;
  52   }
  53
  54   unsigned capacity() const {
  55     return m.m_capacity_mask + 1;
  56   }
  57
  58   size_t getStructSize() {
  59     size_t size = sizeof(ImmutableMap) +
  60                   sizeof(Bucket) * m.m_num +
  61                   sizeof(int) * (m.m_capacity_mask + 1);
  62     return size;
  63   }
  64
  65   static ImmutableMap* Create(ArrayData* arr,
  66                               bool unserializeObj,
  67                               bool& shouldCache);
  68   static void Destroy(ImmutableMap* im);
  69 private:
  70   ImmutableMap() {}
  71   ~ImmutableMap() {}
  72   void add(int pos, SharedVariant *key, SharedVariant *val);
  73
  74   struct Bucket {
  75     /** index of the next bucket, or -1 if the end of a chain */
  76     int next;
  77     /** the value of this bucket */
  78     SharedVariant *key;
  79     SharedVariant *val;
  80   };
  81   /** index of the beginning of each hash chain */
  82   int *hash() const { return (int*)(this + 1); }
  83   /** buckets, stored in index order */
  84   Bucket* buckets() const { return (Bucket*)(hash() + m.m_capacity_mask + 1); }
  85   union {
  86     struct {
  87       unsigned int m_capacity_mask;
  88       unsigned int m_num;
  89     } m;
  90     SharedVariant* align_dummy;
  91   };
  92 };
  93
  94 ///////////////////////////////////////////////////////////////////////////////
  95 }
  96
  97 #endif /* incl_HPHP_IMMUTABLE_MAP_H_ */