-
Notifications
You must be signed in to change notification settings - Fork 3k
/
small_array.h
211 lines (172 loc) · 7.43 KB
/
small_array.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
/*
+----------------------------------------------------------------------+
| HipHop for PHP |
+----------------------------------------------------------------------+
| Copyright (c) 2010 Facebook, Inc. (http://www.facebook.com) |
+----------------------------------------------------------------------+
| This source file is subject to version 3.01 of the PHP license, |
| that is bundled with this package in the file LICENSE, and is |
| available through the world-wide-web at the following url: |
| http://www.php.net/license/3_01.txt |
| If you did not receive a copy of the PHP license and are unable to |
| obtain it through the world-wide-web, please send a note to |
| license@php.net so we can mail you a copy immediately. |
+----------------------------------------------------------------------+
*/
#ifndef __HPHP_SMALL_ARRAY_H__
#define __HPHP_SMALL_ARRAY_H__
#include <runtime/base/types.h>
#include <runtime/base/array/array_data.h>
#include <runtime/base/memory/smart_allocator.h>
#include <runtime/base/complex_types.h>
namespace HPHP {
///////////////////////////////////////////////////////////////////////////////
class SmallArray : public ArrayData {
public:
static const int SARR_SIZE = 7;
static const int SARR_TABLE_SIZE = 8;
SmallArray();
virtual ~SmallArray() { }
virtual ssize_t size() const { return m_nNumOfElements; }
virtual Variant getKey(ssize_t pos) const;
virtual Variant getValue(ssize_t pos) const;
virtual void fetchValue(ssize_t pos, Variant & v) const;
virtual CVarRef getValueRef(ssize_t pos) const;
virtual bool isVectorData() const;
virtual bool supportValueRef() const { return true; }
virtual ssize_t iter_begin() const { return m_nListHead; }
virtual ssize_t iter_end() const { return m_nListTail; }
virtual ssize_t iter_advance(ssize_t prev) const;
virtual ssize_t iter_rewind(ssize_t prev) const;
virtual Variant reset();
virtual Variant prev();
virtual Variant current() const;
virtual Variant next();
virtual Variant end();
virtual Variant key() const;
virtual Variant value(ssize_t &pos) const;
virtual Variant each();
virtual bool exists(int64 k, int64 prehash = -1) const;
virtual bool exists(litstr k, int64 prehash = -1) const;
virtual bool exists(CStrRef k, int64 prehash = -1) const;
virtual bool exists(CVarRef k, int64 prehash = -1) const;
virtual bool idxExists(ssize_t idx) const;
virtual Variant get(int64 k, int64 prehash = -1, bool error = false) const;
virtual Variant get(litstr k, int64 prehash = -1, bool error = false) const;
virtual Variant get(CStrRef k, int64 prehash = -1, bool error = false) const;
virtual Variant get(CVarRef k, int64 prehash = -1, bool error = false) const;
virtual void load(CVarRef k, Variant &v) const;
virtual ssize_t getIndex(int64 k, int64 prehash = -1) const;
virtual ssize_t getIndex(litstr k, int64 prehash = -1) const;
virtual ssize_t getIndex(CStrRef k, int64 prehash = -1) const;
virtual ssize_t getIndex(CVarRef k, int64 prehash = -1) const;
virtual ArrayData *lval(Variant *&ret, bool copy);
virtual ArrayData *lval(int64 k, Variant *&ret, bool copy,
int64 prehash = -1, bool checkExist = false);
virtual ArrayData *lval(litstr k, Variant *&ret, bool copy,
int64 prehash = -1, bool checkExist = false);
virtual ArrayData *lval(CStrRef k, Variant *&ret, bool copy,
int64 prehash = -1, bool checkExist = false);
virtual ArrayData *lval(CVarRef k, Variant *&ret, bool copy,
int64 prehash = -1, bool checkExist = false);
virtual ArrayData *set(int64 k, CVarRef v, bool copy, int64 prehash = -1);
virtual ArrayData *set(litstr k, CVarRef v, bool copy, int64 prehash = -1);
virtual ArrayData *set(CStrRef k, CVarRef v, bool copy, int64 prehash = -1);
virtual ArrayData *set(CVarRef k, CVarRef v, bool copy, int64 prehash = -1);
virtual ArrayData *remove(int64 k, bool copy, int64 prehash = -1);
virtual ArrayData *remove(litstr k, bool copy, int64 prehash = -1);
virtual ArrayData *remove(CStrRef k, bool copy, int64 prehash = -1);
virtual ArrayData *remove(CVarRef k, bool copy, int64 prehash = -1);
virtual ArrayData *copy() const;
virtual ArrayData *append(CVarRef v, bool copy);
virtual ArrayData *append(const ArrayData *elems, ArrayOp op, bool copy);
virtual ArrayData *pop(Variant &value);
virtual ArrayData *dequeue(Variant &value);
virtual ArrayData *prepend(CVarRef v, bool copy);
virtual void renumber();
virtual void onSetStatic();
virtual void getFullPos(FullPos &pos);
virtual bool setFullPos(const FullPos &pos);
virtual CVarRef currentRef();
virtual CVarRef endRef();
virtual ArrayData *escalate(bool mutableIteration = false) const;
DECLARE_SMART_ALLOCATION_NOCALLBACKS(SmallArray);
enum Kind {
Empty,
IntKey,
StrKey
};
class Bucket {
public:
Kind kind;
int8 prev;
int8 next;
int64 h;
StringData *key;
Variant data;
Bucket() : kind(Empty), key(NULL) { }
Bucket(const Bucket &other) : kind(other.kind), key(other.key) {
if (kind != Empty) {
prev = other.prev; next = other.next;
h = other.h;
if (other.data.isReferenced()) other.data.setContagious();
data = other.data;
if (key) key->incRefCount();
}
}
~Bucket() {
if (key && key->decRefCount() == 0) DELETE(StringData)(key);
}
};
private:
int8 m_nNumOfElements;
int8 m_nListHead;
int8 m_nListTail;
unsigned long m_nNextFreeElement;
Bucket m_arBuckets[SARR_TABLE_SIZE];
static int int_ihash(int64 h) { return h & (SARR_TABLE_SIZE - 1); }
static int str_ihash(int h) { return h & (SARR_TABLE_SIZE - 1); }
static int str_ohash(const char *k, int len) {
if (len == 0) return 0;
return k[0] ^ k[len - 1] ^ k[len >> 1];
}
void connect_to_global_dllist(int p, Bucket &b) {
ASSERT(p >= 0 && p < SARR_TABLE_SIZE);
b.prev = m_nListTail;
b.next = ArrayData::invalid_index;
m_nListTail = p;
if (b.prev >= 0) m_arBuckets[(int)b.prev].next = p;
if (m_nListHead < 0) m_nListHead = p;
if (m_pos < 0) m_pos = p;
}
ArrayData *escalateToZendArray() const;
inline int find(int64 h) const;
inline int find(const char *k, int len) const;
SmallArray *copyImpl() const {
SmallArray *a = NEW(SmallArray)(*this);
a->_count = 0;
return a;
}
// m_arBuckets[p].kind == Empty
inline Bucket *addKey(int p, int64 h);
inline Bucket *addKey(int p, litstr key, int len);
inline Bucket *addKey(int p, StringData *key);
// no-op if the key already exists
inline bool add(int64 h, CVarRef data);
inline bool add(litstr key, int64 h, CVarRef data);
inline bool add(StringData *key, int64 h, CVarRef data);
inline void erase(Bucket *pb);
inline void nextInsert(CVarRef v);
};
///////////////////////////////////////////////////////////////////////////////
// Small empty arrays
class StaticEmptySmallArray : public SmallArray {
public:
StaticEmptySmallArray() { setStatic(); }
static SmallArray *Get() { return &s_theEmptyArray; }
private:
static StaticEmptySmallArray s_theEmptyArray;
};
///////////////////////////////////////////////////////////////////////////////
}
#endif // __HPHP_SMALL_ZEND_ARRAY_H__