1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/InlineMap.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,378 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef ds_InlineMap_h
1.11 +#define ds_InlineMap_h
1.12 +
1.13 +#include "jsalloc.h"
1.14 +
1.15 +#include "js/HashTable.h"
1.16 +
1.17 +namespace js {
1.18 +
1.19 +/*
1.20 + * A type can only be used as an InlineMap key if zero is an invalid key value
1.21 + * (and thus may be used as a tombstone value by InlineMap).
1.22 + */
1.23 +template <typename T> struct ZeroIsReserved { static const bool result = false; };
1.24 +template <typename T> struct ZeroIsReserved<T *> { static const bool result = true; };
1.25 +
1.26 +template <typename K, typename V, size_t InlineElems>
1.27 +class InlineMap
1.28 +{
1.29 + public:
1.30 + typedef HashMap<K, V, DefaultHasher<K>, SystemAllocPolicy> WordMap;
1.31 +
1.32 + struct InlineElem
1.33 + {
1.34 + K key;
1.35 + V value;
1.36 + };
1.37 +
1.38 + private:
1.39 + typedef typename WordMap::Ptr WordMapPtr;
1.40 + typedef typename WordMap::AddPtr WordMapAddPtr;
1.41 + typedef typename WordMap::Range WordMapRange;
1.42 +
1.43 + size_t inlNext;
1.44 + size_t inlCount;
1.45 + InlineElem inl[InlineElems];
1.46 + WordMap map;
1.47 +
1.48 + void checkStaticInvariants() {
1.49 + JS_STATIC_ASSERT(ZeroIsReserved<K>::result);
1.50 + }
1.51 +
1.52 + bool usingMap() const {
1.53 + return inlNext > InlineElems;
1.54 + }
1.55 +
1.56 + bool switchToMap() {
1.57 + JS_ASSERT(inlNext == InlineElems);
1.58 +
1.59 + if (map.initialized()) {
1.60 + map.clear();
1.61 + } else {
1.62 + if (!map.init(count()))
1.63 + return false;
1.64 + JS_ASSERT(map.initialized());
1.65 + }
1.66 +
1.67 + for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
1.68 + if (it->key && !map.putNew(it->key, it->value))
1.69 + return false;
1.70 + }
1.71 +
1.72 + inlNext = InlineElems + 1;
1.73 + JS_ASSERT(map.count() == inlCount);
1.74 + JS_ASSERT(usingMap());
1.75 + return true;
1.76 + }
1.77 +
1.78 + MOZ_NEVER_INLINE
1.79 + bool switchAndAdd(const K &key, const V &value) {
1.80 + if (!switchToMap())
1.81 + return false;
1.82 +
1.83 + return map.putNew(key, value);
1.84 + }
1.85 +
1.86 + public:
1.87 + explicit InlineMap()
1.88 + : inlNext(0), inlCount(0) {
1.89 + checkStaticInvariants(); /* Force the template to instantiate the static invariants. */
1.90 + }
1.91 +
1.92 + class Entry
1.93 + {
1.94 + friend class InlineMap;
1.95 + const K &key_;
1.96 + V &value_;
1.97 +
1.98 + Entry(const K &key, V &value) : key_(key), value_(value) {}
1.99 +
1.100 + public:
1.101 + const K &key() { return key_; }
1.102 + V &value() { return value_; }
1.103 + }; /* class Entry */
1.104 +
1.105 + class Ptr
1.106 + {
1.107 + friend class InlineMap;
1.108 +
1.109 + WordMapPtr mapPtr;
1.110 + InlineElem *inlPtr;
1.111 + bool isInlinePtr;
1.112 +
1.113 + typedef Ptr ******* ConvertibleToBool;
1.114 +
1.115 + explicit Ptr(WordMapPtr p) : mapPtr(p), isInlinePtr(false) {}
1.116 + explicit Ptr(InlineElem *ie) : inlPtr(ie), isInlinePtr(true) {}
1.117 + void operator==(const Ptr &other);
1.118 +
1.119 + public:
1.120 + /* Leaves Ptr uninitialized. */
1.121 + Ptr() {
1.122 +#ifdef DEBUG
1.123 + inlPtr = (InlineElem *) 0xbad;
1.124 + isInlinePtr = true;
1.125 +#endif
1.126 + }
1.127 +
1.128 + /* Default copy constructor works for this structure. */
1.129 +
1.130 + bool found() const {
1.131 + return isInlinePtr ? bool(inlPtr) : mapPtr.found();
1.132 + }
1.133 +
1.134 + operator ConvertibleToBool() const {
1.135 + return ConvertibleToBool(found());
1.136 + }
1.137 +
1.138 + K &key() {
1.139 + JS_ASSERT(found());
1.140 + return isInlinePtr ? inlPtr->key : mapPtr->key();
1.141 + }
1.142 +
1.143 + V &value() {
1.144 + JS_ASSERT(found());
1.145 + return isInlinePtr ? inlPtr->value : mapPtr->value();
1.146 + }
1.147 + }; /* class Ptr */
1.148 +
1.149 + class AddPtr
1.150 + {
1.151 + friend class InlineMap;
1.152 +
1.153 + WordMapAddPtr mapAddPtr;
1.154 + InlineElem *inlAddPtr;
1.155 + bool isInlinePtr;
1.156 + /* Indicates whether inlAddPtr is a found result or an add pointer. */
1.157 + bool inlPtrFound;
1.158 +
1.159 + AddPtr(InlineElem *ptr, bool found)
1.160 + : inlAddPtr(ptr), isInlinePtr(true), inlPtrFound(found)
1.161 + {}
1.162 +
1.163 + AddPtr(const WordMapAddPtr &p) : mapAddPtr(p), isInlinePtr(false) {}
1.164 +
1.165 + void operator==(const AddPtr &other);
1.166 +
1.167 + typedef AddPtr ******* ConvertibleToBool;
1.168 +
1.169 + public:
1.170 + AddPtr() {}
1.171 +
1.172 + bool found() const {
1.173 + return isInlinePtr ? inlPtrFound : mapAddPtr.found();
1.174 + }
1.175 +
1.176 + operator ConvertibleToBool() const {
1.177 + return found() ? ConvertibleToBool(1) : ConvertibleToBool(0);
1.178 + }
1.179 +
1.180 + V &value() {
1.181 + JS_ASSERT(found());
1.182 + if (isInlinePtr)
1.183 + return inlAddPtr->value;
1.184 + return mapAddPtr->value();
1.185 + }
1.186 + }; /* class AddPtr */
1.187 +
1.188 + size_t count() {
1.189 + return usingMap() ? map.count() : inlCount;
1.190 + }
1.191 +
1.192 + bool empty() const {
1.193 + return usingMap() ? map.empty() : !inlCount;
1.194 + }
1.195 +
1.196 + void clear() {
1.197 + inlNext = 0;
1.198 + inlCount = 0;
1.199 + }
1.200 +
1.201 + bool isMap() const {
1.202 + return usingMap();
1.203 + }
1.204 +
1.205 + const WordMap &asMap() const {
1.206 + JS_ASSERT(isMap());
1.207 + return map;
1.208 + }
1.209 +
1.210 + const InlineElem *asInline() const {
1.211 + JS_ASSERT(!isMap());
1.212 + return inl;
1.213 + }
1.214 +
1.215 + const InlineElem *inlineEnd() const {
1.216 + JS_ASSERT(!isMap());
1.217 + return inl + inlNext;
1.218 + }
1.219 +
1.220 + MOZ_ALWAYS_INLINE
1.221 + Ptr lookup(const K &key) {
1.222 + if (usingMap())
1.223 + return Ptr(map.lookup(key));
1.224 +
1.225 + for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
1.226 + if (it->key == key)
1.227 + return Ptr(it);
1.228 + }
1.229 +
1.230 + return Ptr(nullptr);
1.231 + }
1.232 +
1.233 + MOZ_ALWAYS_INLINE
1.234 + AddPtr lookupForAdd(const K &key) {
1.235 + if (usingMap())
1.236 + return AddPtr(map.lookupForAdd(key));
1.237 +
1.238 + for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
1.239 + if (it->key == key)
1.240 + return AddPtr(it, true);
1.241 + }
1.242 +
1.243 + /*
1.244 + * The add pointer that's returned here may indicate the limit entry of
1.245 + * the linear space, in which case the |add| operation will initialize
1.246 + * the map if necessary and add the entry there.
1.247 + */
1.248 + return AddPtr(inl + inlNext, false);
1.249 + }
1.250 +
1.251 + MOZ_ALWAYS_INLINE
1.252 + bool add(AddPtr &p, const K &key, const V &value) {
1.253 + JS_ASSERT(!p);
1.254 +
1.255 + if (p.isInlinePtr) {
1.256 + InlineElem *addPtr = p.inlAddPtr;
1.257 + JS_ASSERT(addPtr == inl + inlNext);
1.258 +
1.259 + /* Switching to map mode before we add this pointer. */
1.260 + if (addPtr == inl + InlineElems)
1.261 + return switchAndAdd(key, value);
1.262 +
1.263 + JS_ASSERT(!p.found());
1.264 + JS_ASSERT(uintptr_t(inl + inlNext) == uintptr_t(p.inlAddPtr));
1.265 + p.inlAddPtr->key = key;
1.266 + p.inlAddPtr->value = value;
1.267 + ++inlCount;
1.268 + ++inlNext;
1.269 + return true;
1.270 + }
1.271 +
1.272 + return map.add(p.mapAddPtr, key, value);
1.273 + }
1.274 +
1.275 + MOZ_ALWAYS_INLINE
1.276 + bool put(const K &key, const V &value) {
1.277 + AddPtr p = lookupForAdd(key);
1.278 + if (p) {
1.279 + p.value() = value;
1.280 + return true;
1.281 + }
1.282 + return add(p, key, value);
1.283 + }
1.284 +
1.285 + void remove(Ptr p) {
1.286 + JS_ASSERT(p);
1.287 + if (p.isInlinePtr) {
1.288 + JS_ASSERT(inlCount > 0);
1.289 + JS_ASSERT(p.inlPtr->key != nullptr);
1.290 + p.inlPtr->key = nullptr;
1.291 + --inlCount;
1.292 + return;
1.293 + }
1.294 + JS_ASSERT(map.initialized() && usingMap());
1.295 + map.remove(p.mapPtr);
1.296 + }
1.297 +
1.298 + void remove(const K &key) {
1.299 + if (Ptr p = lookup(key))
1.300 + remove(p);
1.301 + }
1.302 +
1.303 + class Range
1.304 + {
1.305 + friend class InlineMap;
1.306 +
1.307 + WordMapRange mapRange;
1.308 + InlineElem *cur;
1.309 + InlineElem *end;
1.310 + bool isInline;
1.311 +
1.312 + explicit Range(WordMapRange r)
1.313 + : cur(nullptr), end(nullptr), /* Avoid GCC 4.3.3 over-warning. */
1.314 + isInline(false) {
1.315 + mapRange = r;
1.316 + JS_ASSERT(!isInlineRange());
1.317 + }
1.318 +
1.319 + Range(const InlineElem *begin, const InlineElem *end_)
1.320 + : cur(const_cast<InlineElem *>(begin)),
1.321 + end(const_cast<InlineElem *>(end_)),
1.322 + isInline(true) {
1.323 + advancePastNulls(cur);
1.324 + JS_ASSERT(isInlineRange());
1.325 + }
1.326 +
1.327 + bool checkInlineRangeInvariants() const {
1.328 + JS_ASSERT(uintptr_t(cur) <= uintptr_t(end));
1.329 + JS_ASSERT_IF(cur != end, cur->key != nullptr);
1.330 + return true;
1.331 + }
1.332 +
1.333 + bool isInlineRange() const {
1.334 + JS_ASSERT_IF(isInline, checkInlineRangeInvariants());
1.335 + return isInline;
1.336 + }
1.337 +
1.338 + void advancePastNulls(InlineElem *begin) {
1.339 + InlineElem *newCur = begin;
1.340 + while (newCur < end && nullptr == newCur->key)
1.341 + ++newCur;
1.342 + JS_ASSERT(uintptr_t(newCur) <= uintptr_t(end));
1.343 + cur = newCur;
1.344 + }
1.345 +
1.346 + void bumpCurPtr() {
1.347 + JS_ASSERT(isInlineRange());
1.348 + advancePastNulls(cur + 1);
1.349 + }
1.350 +
1.351 + void operator==(const Range &other);
1.352 +
1.353 + public:
1.354 + bool empty() const {
1.355 + return isInlineRange() ? cur == end : mapRange.empty();
1.356 + }
1.357 +
1.358 + Entry front() {
1.359 + JS_ASSERT(!empty());
1.360 + if (isInlineRange())
1.361 + return Entry(cur->key, cur->value);
1.362 + return Entry(mapRange.front().key(), mapRange.front().value());
1.363 + }
1.364 +
1.365 + void popFront() {
1.366 + JS_ASSERT(!empty());
1.367 + if (isInlineRange())
1.368 + bumpCurPtr();
1.369 + else
1.370 + mapRange.popFront();
1.371 + }
1.372 + }; /* class Range */
1.373 +
1.374 + Range all() const {
1.375 + return usingMap() ? Range(map.all()) : Range(inl, inl + inlNext);
1.376 + }
1.377 +}; /* class InlineMap */
1.378 +
1.379 +} /* namespace js */
1.380 +
1.381 +#endif /* ds_InlineMap_h */
