js/src/ds/InlineMap.h@6474c204b198
js/src/ds/InlineMap.h
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef ds_InlineMap_h
8 #define ds_InlineMap_h
10 #include "jsalloc.h"
12 #include "js/HashTable.h"
14 namespace js {
16 /*
17 * A type can only be used as an InlineMap key if zero is an invalid key value
18 * (and thus may be used as a tombstone value by InlineMap).
19 */
20 template <typename T> struct ZeroIsReserved { static const bool result = false; };
21 template <typename T> struct ZeroIsReserved<T *> { static const bool result = true; };
23 template <typename K, typename V, size_t InlineElems>
24 class InlineMap
25 {
26 public:
27 typedef HashMap<K, V, DefaultHasher<K>, SystemAllocPolicy> WordMap;
29 struct InlineElem
30 {
31 K key;
32 V value;
33 };
35 private:
36 typedef typename WordMap::Ptr WordMapPtr;
37 typedef typename WordMap::AddPtr WordMapAddPtr;
38 typedef typename WordMap::Range WordMapRange;
40 size_t inlNext;
41 size_t inlCount;
42 InlineElem inl[InlineElems];
43 WordMap map;
45 void checkStaticInvariants() {
46 JS_STATIC_ASSERT(ZeroIsReserved<K>::result);
47 }
49 bool usingMap() const {
50 return inlNext > InlineElems;
51 }
53 bool switchToMap() {
54 JS_ASSERT(inlNext == InlineElems);
56 if (map.initialized()) {
57 map.clear();
58 } else {
59 if (!map.init(count()))
60 return false;
61 JS_ASSERT(map.initialized());
62 }
64 for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
65 if (it->key && !map.putNew(it->key, it->value))
66 return false;
67 }
69 inlNext = InlineElems + 1;
70 JS_ASSERT(map.count() == inlCount);
71 JS_ASSERT(usingMap());
72 return true;
73 }
75 MOZ_NEVER_INLINE
76 bool switchAndAdd(const K &key, const V &value) {
77 if (!switchToMap())
78 return false;
80 return map.putNew(key, value);
81 }
83 public:
84 explicit InlineMap()
85 : inlNext(0), inlCount(0) {
86 checkStaticInvariants(); /* Force the template to instantiate the static invariants. */
87 }
89 class Entry
90 {
91 friend class InlineMap;
92 const K &key_;
93 V &value_;
95 Entry(const K &key, V &value) : key_(key), value_(value) {}
97 public:
98 const K &key() { return key_; }
99 V &value() { return value_; }
100 }; /* class Entry */
102 class Ptr
103 {
104 friend class InlineMap;
106 WordMapPtr mapPtr;
107 InlineElem *inlPtr;
108 bool isInlinePtr;
110 typedef Ptr ******* ConvertibleToBool;
112 explicit Ptr(WordMapPtr p) : mapPtr(p), isInlinePtr(false) {}
113 explicit Ptr(InlineElem *ie) : inlPtr(ie), isInlinePtr(true) {}
114 void operator==(const Ptr &other);
116 public:
117 /* Leaves Ptr uninitialized. */
118 Ptr() {
119 #ifdef DEBUG
120 inlPtr = (InlineElem *) 0xbad;
121 isInlinePtr = true;
122 #endif
123 }
125 /* Default copy constructor works for this structure. */
127 bool found() const {
128 return isInlinePtr ? bool(inlPtr) : mapPtr.found();
129 }
131 operator ConvertibleToBool() const {
132 return ConvertibleToBool(found());
133 }
135 K &key() {
136 JS_ASSERT(found());
137 return isInlinePtr ? inlPtr->key : mapPtr->key();
138 }
140 V &value() {
141 JS_ASSERT(found());
142 return isInlinePtr ? inlPtr->value : mapPtr->value();
143 }
144 }; /* class Ptr */
146 class AddPtr
147 {
148 friend class InlineMap;
150 WordMapAddPtr mapAddPtr;
151 InlineElem *inlAddPtr;
152 bool isInlinePtr;
153 /* Indicates whether inlAddPtr is a found result or an add pointer. */
154 bool inlPtrFound;
156 AddPtr(InlineElem *ptr, bool found)
157 : inlAddPtr(ptr), isInlinePtr(true), inlPtrFound(found)
158 {}
160 AddPtr(const WordMapAddPtr &p) : mapAddPtr(p), isInlinePtr(false) {}
162 void operator==(const AddPtr &other);
164 typedef AddPtr ******* ConvertibleToBool;
166 public:
167 AddPtr() {}
169 bool found() const {
170 return isInlinePtr ? inlPtrFound : mapAddPtr.found();
171 }
173 operator ConvertibleToBool() const {
174 return found() ? ConvertibleToBool(1) : ConvertibleToBool(0);
175 }
177 V &value() {
178 JS_ASSERT(found());
179 if (isInlinePtr)
180 return inlAddPtr->value;
181 return mapAddPtr->value();
182 }
183 }; /* class AddPtr */
185 size_t count() {
186 return usingMap() ? map.count() : inlCount;
187 }
189 bool empty() const {
190 return usingMap() ? map.empty() : !inlCount;
191 }
193 void clear() {
194 inlNext = 0;
195 inlCount = 0;
196 }
198 bool isMap() const {
199 return usingMap();
200 }
202 const WordMap &asMap() const {
203 JS_ASSERT(isMap());
204 return map;
205 }
207 const InlineElem *asInline() const {
208 JS_ASSERT(!isMap());
209 return inl;
210 }
212 const InlineElem *inlineEnd() const {
213 JS_ASSERT(!isMap());
214 return inl + inlNext;
215 }
217 MOZ_ALWAYS_INLINE
218 Ptr lookup(const K &key) {
219 if (usingMap())
220 return Ptr(map.lookup(key));
222 for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
223 if (it->key == key)
224 return Ptr(it);
225 }
227 return Ptr(nullptr);
228 }
230 MOZ_ALWAYS_INLINE
231 AddPtr lookupForAdd(const K &key) {
232 if (usingMap())
233 return AddPtr(map.lookupForAdd(key));
235 for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
236 if (it->key == key)
237 return AddPtr(it, true);
238 }
240 /*
241 * The add pointer that's returned here may indicate the limit entry of
242 * the linear space, in which case the |add| operation will initialize
243 * the map if necessary and add the entry there.
244 */
245 return AddPtr(inl + inlNext, false);
246 }
248 MOZ_ALWAYS_INLINE
249 bool add(AddPtr &p, const K &key, const V &value) {
250 JS_ASSERT(!p);
252 if (p.isInlinePtr) {
253 InlineElem *addPtr = p.inlAddPtr;
254 JS_ASSERT(addPtr == inl + inlNext);
256 /* Switching to map mode before we add this pointer. */
257 if (addPtr == inl + InlineElems)
258 return switchAndAdd(key, value);
260 JS_ASSERT(!p.found());
261 JS_ASSERT(uintptr_t(inl + inlNext) == uintptr_t(p.inlAddPtr));
262 p.inlAddPtr->key = key;
263 p.inlAddPtr->value = value;
264 ++inlCount;
265 ++inlNext;
266 return true;
267 }
269 return map.add(p.mapAddPtr, key, value);
270 }
272 MOZ_ALWAYS_INLINE
273 bool put(const K &key, const V &value) {
274 AddPtr p = lookupForAdd(key);
275 if (p) {
276 p.value() = value;
277 return true;
278 }
279 return add(p, key, value);
280 }
282 void remove(Ptr p) {
283 JS_ASSERT(p);
284 if (p.isInlinePtr) {
285 JS_ASSERT(inlCount > 0);
286 JS_ASSERT(p.inlPtr->key != nullptr);
287 p.inlPtr->key = nullptr;
288 --inlCount;
289 return;
290 }
291 JS_ASSERT(map.initialized() && usingMap());
292 map.remove(p.mapPtr);
293 }
295 void remove(const K &key) {
296 if (Ptr p = lookup(key))
297 remove(p);
298 }
300 class Range
301 {
302 friend class InlineMap;
304 WordMapRange mapRange;
305 InlineElem *cur;
306 InlineElem *end;
307 bool isInline;
309 explicit Range(WordMapRange r)
310 : cur(nullptr), end(nullptr), /* Avoid GCC 4.3.3 over-warning. */
311 isInline(false) {
312 mapRange = r;
313 JS_ASSERT(!isInlineRange());
314 }
316 Range(const InlineElem *begin, const InlineElem *end_)
317 : cur(const_cast<InlineElem *>(begin)),
318 end(const_cast<InlineElem *>(end_)),
319 isInline(true) {
320 advancePastNulls(cur);
321 JS_ASSERT(isInlineRange());
322 }
324 bool checkInlineRangeInvariants() const {
325 JS_ASSERT(uintptr_t(cur) <= uintptr_t(end));
326 JS_ASSERT_IF(cur != end, cur->key != nullptr);
327 return true;
328 }
330 bool isInlineRange() const {
331 JS_ASSERT_IF(isInline, checkInlineRangeInvariants());
332 return isInline;
333 }
335 void advancePastNulls(InlineElem *begin) {
336 InlineElem *newCur = begin;
337 while (newCur < end && nullptr == newCur->key)
338 ++newCur;
339 JS_ASSERT(uintptr_t(newCur) <= uintptr_t(end));
340 cur = newCur;
341 }
343 void bumpCurPtr() {
344 JS_ASSERT(isInlineRange());
345 advancePastNulls(cur + 1);
346 }
348 void operator==(const Range &other);
350 public:
351 bool empty() const {
352 return isInlineRange() ? cur == end : mapRange.empty();
353 }
355 Entry front() {
356 JS_ASSERT(!empty());
357 if (isInlineRange())
358 return Entry(cur->key, cur->value);
359 return Entry(mapRange.front().key(), mapRange.front().value());
360 }
362 void popFront() {
363 JS_ASSERT(!empty());
364 if (isInlineRange())
365 bumpCurPtr();
366 else
367 mapRange.popFront();
368 }
369 }; /* class Range */
371 Range all() const {
372 return usingMap() ? Range(map.all()) : Range(inl, inl + inlNext);
373 }
374 }; /* class InlineMap */
376 } /* namespace js */
378 #endif /* ds_InlineMap_h */
