michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef ds_InlineMap_h
michael@0: #define ds_InlineMap_h
michael@0: 
michael@0: #include "jsalloc.h"
michael@0: 
michael@0: #include "js/HashTable.h"
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: /*
michael@0:  * A type can only be used as an InlineMap key if zero is an invalid key value
michael@0:  * (and thus may be used as a tombstone value by InlineMap).
michael@0:  */
michael@0: template <typename T> struct ZeroIsReserved         { static const bool result = false; };
michael@0: template <typename T> struct ZeroIsReserved<T *>    { static const bool result = true; };
michael@0: 
michael@0: template <typename K, typename V, size_t InlineElems>
michael@0: class InlineMap
michael@0: {
michael@0:   public:
michael@0:     typedef HashMap<K, V, DefaultHasher<K>, SystemAllocPolicy> WordMap;
michael@0: 
michael@0:     struct InlineElem
michael@0:     {
michael@0:         K key;
michael@0:         V value;
michael@0:     };
michael@0: 
michael@0:   private:
michael@0:     typedef typename WordMap::Ptr       WordMapPtr;
michael@0:     typedef typename WordMap::AddPtr    WordMapAddPtr;
michael@0:     typedef typename WordMap::Range     WordMapRange;
michael@0: 
michael@0:     size_t          inlNext;
michael@0:     size_t          inlCount;
michael@0:     InlineElem      inl[InlineElems];
michael@0:     WordMap         map;
michael@0: 
michael@0:     void checkStaticInvariants() {
michael@0:         JS_STATIC_ASSERT(ZeroIsReserved<K>::result);
michael@0:     }
michael@0: 
michael@0:     bool usingMap() const {
michael@0:         return inlNext > InlineElems;
michael@0:     }
michael@0: 
michael@0:     bool switchToMap() {
michael@0:         JS_ASSERT(inlNext == InlineElems);
michael@0: 
michael@0:         if (map.initialized()) {
michael@0:             map.clear();
michael@0:         } else {
michael@0:             if (!map.init(count()))
michael@0:                 return false;
michael@0:             JS_ASSERT(map.initialized());
michael@0:         }
michael@0: 
michael@0:         for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
michael@0:             if (it->key && !map.putNew(it->key, it->value))
michael@0:                 return false;
michael@0:         }
michael@0: 
michael@0:         inlNext = InlineElems + 1;
michael@0:         JS_ASSERT(map.count() == inlCount);
michael@0:         JS_ASSERT(usingMap());
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     MOZ_NEVER_INLINE
michael@0:     bool switchAndAdd(const K &key, const V &value) {
michael@0:         if (!switchToMap())
michael@0:             return false;
michael@0: 
michael@0:         return map.putNew(key, value);
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     explicit InlineMap()
michael@0:       : inlNext(0), inlCount(0) {
michael@0:         checkStaticInvariants(); /* Force the template to instantiate the static invariants. */
michael@0:     }
michael@0: 
michael@0:     class Entry
michael@0:     {
michael@0:         friend class InlineMap;
michael@0:         const K &key_;
michael@0:         V &value_;
michael@0: 
michael@0:         Entry(const K &key, V &value) : key_(key), value_(value) {}
michael@0: 
michael@0:       public:
michael@0:         const K &key() { return key_; }
michael@0:         V &value() { return value_; }
michael@0:     }; /* class Entry */
michael@0: 
michael@0:     class Ptr
michael@0:     {
michael@0:         friend class InlineMap;
michael@0: 
michael@0:         WordMapPtr  mapPtr;
michael@0:         InlineElem  *inlPtr;
michael@0:         bool        isInlinePtr;
michael@0: 
michael@0:         typedef Ptr ******* ConvertibleToBool;
michael@0: 
michael@0:         explicit Ptr(WordMapPtr p) : mapPtr(p), isInlinePtr(false) {}
michael@0:         explicit Ptr(InlineElem *ie) : inlPtr(ie), isInlinePtr(true) {}
michael@0:         void operator==(const Ptr &other);
michael@0: 
michael@0:       public:
michael@0:         /* Leaves Ptr uninitialized. */
michael@0:         Ptr() {
michael@0: #ifdef DEBUG
michael@0:             inlPtr = (InlineElem *) 0xbad;
michael@0:             isInlinePtr = true;
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         /* Default copy constructor works for this structure. */
michael@0: 
michael@0:         bool found() const {
michael@0:             return isInlinePtr ? bool(inlPtr) : mapPtr.found();
michael@0:         }
michael@0: 
michael@0:         operator ConvertibleToBool() const {
michael@0:             return ConvertibleToBool(found());
michael@0:         }
michael@0: 
michael@0:         K &key() {
michael@0:             JS_ASSERT(found());
michael@0:             return isInlinePtr ? inlPtr->key : mapPtr->key();
michael@0:         }
michael@0: 
michael@0:         V &value() {
michael@0:             JS_ASSERT(found());
michael@0:             return isInlinePtr ? inlPtr->value : mapPtr->value();
michael@0:         }
michael@0:     }; /* class Ptr */
michael@0: 
michael@0:     class AddPtr
michael@0:     {
michael@0:         friend class InlineMap;
michael@0: 
michael@0:         WordMapAddPtr   mapAddPtr;
michael@0:         InlineElem      *inlAddPtr;
michael@0:         bool            isInlinePtr;
michael@0:         /* Indicates whether inlAddPtr is a found result or an add pointer. */
michael@0:         bool            inlPtrFound;
michael@0: 
michael@0:         AddPtr(InlineElem *ptr, bool found)
michael@0:           : inlAddPtr(ptr), isInlinePtr(true), inlPtrFound(found)
michael@0:         {}
michael@0: 
michael@0:         AddPtr(const WordMapAddPtr &p) : mapAddPtr(p), isInlinePtr(false) {}
michael@0: 
michael@0:         void operator==(const AddPtr &other);
michael@0: 
michael@0:         typedef AddPtr ******* ConvertibleToBool;
michael@0: 
michael@0:       public:
michael@0:         AddPtr() {}
michael@0: 
michael@0:         bool found() const {
michael@0:             return isInlinePtr ? inlPtrFound : mapAddPtr.found();
michael@0:         }
michael@0: 
michael@0:         operator ConvertibleToBool() const {
michael@0:             return found() ? ConvertibleToBool(1) : ConvertibleToBool(0);
michael@0:         }
michael@0: 
michael@0:         V &value() {
michael@0:             JS_ASSERT(found());
michael@0:             if (isInlinePtr)
michael@0:                 return inlAddPtr->value;
michael@0:             return mapAddPtr->value();
michael@0:         }
michael@0:     }; /* class AddPtr */
michael@0: 
michael@0:     size_t count() {
michael@0:         return usingMap() ? map.count() : inlCount;
michael@0:     }
michael@0: 
michael@0:     bool empty() const {
michael@0:         return usingMap() ? map.empty() : !inlCount;
michael@0:     }
michael@0: 
michael@0:     void clear() {
michael@0:         inlNext = 0;
michael@0:         inlCount = 0;
michael@0:     }
michael@0: 
michael@0:     bool isMap() const {
michael@0:         return usingMap();
michael@0:     }
michael@0: 
michael@0:     const WordMap &asMap() const {
michael@0:         JS_ASSERT(isMap());
michael@0:         return map;
michael@0:     }
michael@0: 
michael@0:     const InlineElem *asInline() const {
michael@0:         JS_ASSERT(!isMap());
michael@0:         return inl;
michael@0:     }
michael@0: 
michael@0:     const InlineElem *inlineEnd() const {
michael@0:         JS_ASSERT(!isMap());
michael@0:         return inl + inlNext;
michael@0:     }
michael@0: 
michael@0:     MOZ_ALWAYS_INLINE
michael@0:     Ptr lookup(const K &key) {
michael@0:         if (usingMap())
michael@0:             return Ptr(map.lookup(key));
michael@0: 
michael@0:         for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
michael@0:             if (it->key == key)
michael@0:                 return Ptr(it);
michael@0:         }
michael@0: 
michael@0:         return Ptr(nullptr);
michael@0:     }
michael@0: 
michael@0:     MOZ_ALWAYS_INLINE
michael@0:     AddPtr lookupForAdd(const K &key) {
michael@0:         if (usingMap())
michael@0:             return AddPtr(map.lookupForAdd(key));
michael@0: 
michael@0:         for (InlineElem *it = inl, *end = inl + inlNext; it != end; ++it) {
michael@0:             if (it->key == key)
michael@0:                 return AddPtr(it, true);
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * The add pointer that's returned here may indicate the limit entry of
michael@0:          * the linear space, in which case the |add| operation will initialize
michael@0:          * the map if necessary and add the entry there.
michael@0:          */
michael@0:         return AddPtr(inl + inlNext, false);
michael@0:     }
michael@0: 
michael@0:     MOZ_ALWAYS_INLINE
michael@0:     bool add(AddPtr &p, const K &key, const V &value) {
michael@0:         JS_ASSERT(!p);
michael@0: 
michael@0:         if (p.isInlinePtr) {
michael@0:             InlineElem *addPtr = p.inlAddPtr;
michael@0:             JS_ASSERT(addPtr == inl + inlNext);
michael@0: 
michael@0:             /* Switching to map mode before we add this pointer. */
michael@0:             if (addPtr == inl + InlineElems)
michael@0:                 return switchAndAdd(key, value);
michael@0: 
michael@0:             JS_ASSERT(!p.found());
michael@0:             JS_ASSERT(uintptr_t(inl + inlNext) == uintptr_t(p.inlAddPtr));
michael@0:             p.inlAddPtr->key = key;
michael@0:             p.inlAddPtr->value = value;
michael@0:             ++inlCount;
michael@0:             ++inlNext;
michael@0:             return true;
michael@0:         }
michael@0: 
michael@0:         return map.add(p.mapAddPtr, key, value);
michael@0:     }
michael@0: 
michael@0:     MOZ_ALWAYS_INLINE
michael@0:     bool put(const K &key, const V &value) {
michael@0:         AddPtr p = lookupForAdd(key);
michael@0:         if (p) {
michael@0:             p.value() = value;
michael@0:             return true;
michael@0:         }
michael@0:         return add(p, key, value);
michael@0:     }
michael@0: 
michael@0:     void remove(Ptr p) {
michael@0:         JS_ASSERT(p);
michael@0:         if (p.isInlinePtr) {
michael@0:             JS_ASSERT(inlCount > 0);
michael@0:             JS_ASSERT(p.inlPtr->key != nullptr);
michael@0:             p.inlPtr->key = nullptr;
michael@0:             --inlCount;
michael@0:             return;
michael@0:         }
michael@0:         JS_ASSERT(map.initialized() && usingMap());
michael@0:         map.remove(p.mapPtr);
michael@0:     }
michael@0: 
michael@0:     void remove(const K &key) {
michael@0:         if (Ptr p = lookup(key))
michael@0:             remove(p);
michael@0:     }
michael@0: 
michael@0:     class Range
michael@0:     {
michael@0:         friend class InlineMap;
michael@0: 
michael@0:         WordMapRange    mapRange;
michael@0:         InlineElem      *cur;
michael@0:         InlineElem      *end;
michael@0:         bool            isInline;
michael@0: 
michael@0:         explicit Range(WordMapRange r)
michael@0:           : cur(nullptr), end(nullptr), /* Avoid GCC 4.3.3 over-warning. */
michael@0:             isInline(false) {
michael@0:             mapRange = r;
michael@0:             JS_ASSERT(!isInlineRange());
michael@0:         }
michael@0: 
michael@0:         Range(const InlineElem *begin, const InlineElem *end_)
michael@0:           : cur(const_cast<InlineElem *>(begin)),
michael@0:             end(const_cast<InlineElem *>(end_)),
michael@0:             isInline(true) {
michael@0:             advancePastNulls(cur);
michael@0:             JS_ASSERT(isInlineRange());
michael@0:         }
michael@0: 
michael@0:         bool checkInlineRangeInvariants() const {
michael@0:             JS_ASSERT(uintptr_t(cur) <= uintptr_t(end));
michael@0:             JS_ASSERT_IF(cur != end, cur->key != nullptr);
michael@0:             return true;
michael@0:         }
michael@0: 
michael@0:         bool isInlineRange() const {
michael@0:             JS_ASSERT_IF(isInline, checkInlineRangeInvariants());
michael@0:             return isInline;
michael@0:         }
michael@0: 
michael@0:         void advancePastNulls(InlineElem *begin) {
michael@0:             InlineElem *newCur = begin;
michael@0:             while (newCur < end && nullptr == newCur->key)
michael@0:                 ++newCur;
michael@0:             JS_ASSERT(uintptr_t(newCur) <= uintptr_t(end));
michael@0:             cur = newCur;
michael@0:         }
michael@0: 
michael@0:         void bumpCurPtr() {
michael@0:             JS_ASSERT(isInlineRange());
michael@0:             advancePastNulls(cur + 1);
michael@0:         }
michael@0: 
michael@0:         void operator==(const Range &other);
michael@0: 
michael@0:       public:
michael@0:         bool empty() const {
michael@0:             return isInlineRange() ? cur == end : mapRange.empty();
michael@0:         }
michael@0: 
michael@0:         Entry front() {
michael@0:             JS_ASSERT(!empty());
michael@0:             if (isInlineRange())
michael@0:                 return Entry(cur->key, cur->value);
michael@0:             return Entry(mapRange.front().key(), mapRange.front().value());
michael@0:         }
michael@0: 
michael@0:         void popFront() {
michael@0:             JS_ASSERT(!empty());
michael@0:             if (isInlineRange())
michael@0:                 bumpCurPtr();
michael@0:             else
michael@0:                 mapRange.popFront();
michael@0:         }
michael@0:     }; /* class Range */
michael@0: 
michael@0:     Range all() const {
michael@0:         return usingMap() ? Range(map.all()) : Range(inl, inl + inlNext);
michael@0:     }
michael@0: }; /* class InlineMap */
michael@0: 
michael@0: } /* namespace js */
michael@0: 
michael@0: #endif /* ds_InlineMap_h */