1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=99 ft=cpp:
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
17 * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
20 * The Initial Developer of the Original Code is
21 * the Mozilla Corporation.
24 * Brendan Eich <brendan@mozilla.org> (Original Author)
25 * Chris Waterson <waterson@netscape.com>
26 * L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
27 * Luke Wagner <lw@mozilla.com>
29 * Alternatively, the contents of this file may be used under the terms of
30 * either of the GNU General Public License Version 2 or later (the "GPL"),
31 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
32 * in which case the provisions of the GPL or the LGPL are applicable instead
33 * of those above. If you wish to allow use of your version of this file only
34 * under the terms of either the GPL or the LGPL, and not to allow others to
35 * use your version of this file under the terms of the MPL, indicate your
36 * decision by deleting the provisions above and replace them with the notice
37 * and other provisions required by the GPL or the LGPL. If you do not delete
38 * the provisions above, a recipient may use your version of this file under
39 * the terms of any one of the MPL, the GPL or the LGPL.
41 * ***** END LICENSE BLOCK ***** */
43 #ifndef jshashtable_h_
44 #define jshashtable_h_
50 /* Integral types for all hash functions. */
51 typedef uint32 HashNumber
;
55 /* Reusable implementation of HashMap and HashSet. */
56 template <class T
, class HashPolicy
, class AllocPolicy
>
57 class HashTable
: AllocPolicy
59 typedef typename
tl::StripConst
<T
>::result NonConstT
;
60 typedef typename
HashPolicy::KeyType Key
;
61 typedef typename
HashPolicy::Lookup Lookup
;
64 * T::operator= is a private operation for HashMap::Entry. HashMap::Entry
65 * makes HashTable a friend, but MSVC does not allow HashMap::Entry to make
66 * HashTable::Entry a friend. So do assignment here:
68 static void assignT(NonConstT
&dst
, const T
&src
) { dst
= src
; }
75 Entry() : keyHash(0), t() {}
76 void operator=(const Entry
&rhs
) { keyHash
= rhs
.keyHash
; assignT(t
, rhs
.t
); }
80 bool isFree() const { return keyHash
== sFreeKey
; }
81 void setFree() { keyHash
= sFreeKey
; assignT(t
, T()); }
82 bool isRemoved() const { return keyHash
== sRemovedKey
; }
83 void setRemoved() { keyHash
= sRemovedKey
; assignT(t
, T()); }
84 bool isLive() const { return isLiveHash(keyHash
); }
85 void setLive(HashNumber hn
) { JS_ASSERT(isLiveHash(hn
)); keyHash
= hn
; }
87 void setCollision() { JS_ASSERT(isLive()); keyHash
|= sCollisionBit
; }
88 void setCollision(HashNumber collisionBit
) {
89 JS_ASSERT(isLive()); keyHash
|= collisionBit
;
91 void unsetCollision() { JS_ASSERT(isLive()); keyHash
&= ~sCollisionBit
; }
92 bool hasCollision() const { JS_ASSERT(isLive()); return keyHash
& sCollisionBit
; }
93 bool matchHash(HashNumber hn
) { return (keyHash
& ~sCollisionBit
) == hn
; }
94 HashNumber
getKeyHash() const { JS_ASSERT(!hasCollision()); return keyHash
; }
98 * A nullable pointer to a hash table element. A Ptr |p| can be tested
99 * either explicitly |if (p.found()) p->...| or using boolean conversion
100 * |if (p) p->...|. Ptr objects must not be used after any mutating hash
101 * table operations unless |generation()| is tested.
105 friend class HashTable
;
106 typedef void (Ptr::* ConvertibleToBool
)();
112 Ptr(Entry
&entry
) : entry(&entry
) {}
115 bool found() const { return entry
->isLive(); }
116 operator ConvertibleToBool() const { return found() ? &Ptr::nonNull
: 0; }
117 bool operator==(const Ptr
&rhs
) const { JS_ASSERT(found() && rhs
.found()); return entry
== rhs
.entry
; }
118 bool operator!=(const Ptr
&rhs
) const { return !(*this == rhs
); }
120 T
&operator*() const { return entry
->t
; }
121 T
*operator->() const { return &entry
->t
; }
124 /* A Ptr that can be used to add a key after a failed lookup. */
125 class AddPtr
: public Ptr
127 friend class HashTable
;
130 uint64 mutationCount
;
132 AddPtr(Entry
&entry
, HashNumber hn
, uint64 mutationCount
)
133 : Ptr(entry
), keyHash(hn
), mutationCount(mutationCount
) {}
135 AddPtr(Entry
&entry
, HashNumber hn
) : Ptr(entry
), keyHash(hn
) {}
140 * A collection of hash table entries. The collection is enumerated by
141 * calling |front()| followed by |popFront()| as long as |!empty()|. As
142 * with Ptr/AddPtr, Range objects must not be used after any mutating hash
143 * table operation unless the |generation()| is tested.
148 friend class HashTable
;
150 Range(Entry
*c
, Entry
*e
) : cur(c
), end(e
) {
151 while (cur
!= end
&& !cur
->isLive())
169 while (++cur
!= end
&& !cur
->isLive());
174 * A Range whose lifetime delimits a mutating enumeration of a hash table.
175 * Since rehashing when elements were removed during enumeration would be
176 * bad, it is postponed until |endEnumeration()| is called. If
177 * |endEnumeration()| is not called before an Enum's constructor, it will
178 * be called automatically. Since |endEnumeration()| touches the hash
179 * table, the user must ensure that the hash table is still alive when this
182 class Enum
: public Range
184 friend class HashTable
;
191 void operator=(const Enum
&);
194 template<class Map
> explicit
195 Enum(Map
&map
) : Range(map
.all()), table(map
.impl
), removed(false) {}
198 * Removes the |front()| element from the table, leaving |front()|
199 * invalid until the next call to |popFront()|. For example:
202 * for (HashSet<int>::Enum e(s); !e.empty(); e.popFront())
203 * if (e.front() == 42)
207 table
.remove(*this->cur
);
211 /* Potentially rehashes the table. */
214 table
.checkUnderloaded();
217 /* Can be used to end the enumeration before the destructor. */
218 void endEnumeration() {
220 table
.checkUnderloaded();
227 uint32 hashShift
; /* multiplicative hash shift */
228 uint32 tableCapacity
; /* = JS_BIT(sHashBits - hashShift) */
229 uint32 entryCount
; /* number of entries in table */
230 uint32 gen
; /* entry storage generation number */
231 uint32 removedCount
; /* removed entry sentinels in table */
232 Entry
*table
; /* entry storage */
234 void setTableSizeLog2(unsigned sizeLog2
) {
235 hashShift
= sHashBits
- sizeLog2
;
236 tableCapacity
= JS_BIT(sizeLog2
);
240 mutable struct Stats
{
241 uint32 searches
; /* total number of table searches */
242 uint32 steps
; /* hash chain links traversed */
243 uint32 hits
; /* searches that found key */
244 uint32 misses
; /* searches that didn't find key */
245 uint32 addOverRemoved
; /* adds that recycled a removed entry */
246 uint32 removes
; /* calls to remove */
247 uint32 removeFrees
; /* calls to remove that freed the entry */
248 uint32 grows
; /* table expansions */
249 uint32 shrinks
; /* table contractions */
250 uint32 compresses
; /* table compressions */
258 friend class js::ReentrancyGuard
;
259 mutable bool entered
;
260 uint64 mutationCount
;
263 static const unsigned sMinSizeLog2
= 4;
264 static const unsigned sMinSize
= 1 << sMinSizeLog2
;
265 static const unsigned sSizeLimit
= JS_BIT(24);
266 static const unsigned sHashBits
= tl::BitSize
<HashNumber
>::result
;
267 static const uint8 sMinAlphaFrac
= 64; /* (0x100 * .25) taken from jsdhash.h */
268 static const uint8 sMaxAlphaFrac
= 192; /* (0x100 * .75) taken from jsdhash.h */
269 static const uint8 sInvMaxAlpha
= 171; /* (ceil(0x100 / .75) >> 1) */
270 static const HashNumber sGoldenRatio
= 0x9E3779B9U
; /* taken from jsdhash.h */
271 static const HashNumber sCollisionBit
= 1;
272 static const HashNumber sFreeKey
= 0;
273 static const HashNumber sRemovedKey
= 1;
275 static bool isLiveHash(HashNumber hash
)
277 return hash
> sRemovedKey
;
280 static HashNumber
prepareHash(const Lookup
& l
)
282 HashNumber keyHash
= HashPolicy::hash(l
);
284 /* Improve keyHash distribution. */
285 keyHash
*= sGoldenRatio
;
287 /* Avoid reserved hash codes. */
288 if (!isLiveHash(keyHash
))
289 keyHash
-= (sRemovedKey
+ 1);
290 return keyHash
& ~sCollisionBit
;
293 static Entry
*createTable(AllocPolicy
&alloc
, uint32 capacity
)
295 Entry
*newTable
= (Entry
*)alloc
.malloc(capacity
* sizeof(Entry
));
298 for (Entry
*e
= newTable
, *end
= e
+ capacity
; e
!= end
; ++e
)
303 static void destroyTable(AllocPolicy
&alloc
, Entry
*oldTable
, uint32 capacity
)
305 for (Entry
*e
= oldTable
, *end
= e
+ capacity
; e
!= end
; ++e
)
307 alloc
.free(oldTable
);
311 HashTable(AllocPolicy ap
)
323 bool init(uint32 length
)
325 /* Make sure that init isn't called twice. */
326 JS_ASSERT(table
== NULL
);
329 * Correct for sMaxAlphaFrac such that the table will not resize
330 * when adding 'length' entries.
332 JS_ASSERT(length
< (uint32(1) << 23));
333 uint32 capacity
= (length
* sInvMaxAlpha
) >> 7;
335 if (capacity
< sMinSize
)
338 /* FIXME: use JS_CEILING_LOG2 when PGO stops crashing (bug 543034). */
339 uint32 roundUp
= sMinSize
, roundUpLog2
= sMinSizeLog2
;
340 while (roundUp
< capacity
) {
346 if (capacity
>= sSizeLimit
) {
347 this->reportAllocOverflow();
351 table
= createTable(*this, capacity
);
355 setTableSizeLog2(roundUpLog2
);
356 METER(memset(&stats
, 0, sizeof(stats
)));
360 bool initialized() const
368 destroyTable(*this, table
, tableCapacity
);
372 static HashNumber
hash1(HashNumber hash0
, uint32 shift
) {
373 return hash0
>> shift
;
376 static HashNumber
hash2(HashNumber hash0
, uint32 log2
, uint32 shift
) {
377 return ((hash0
<< log2
) >> shift
) | 1;
381 return entryCount
+ removedCount
>= ((sMaxAlphaFrac
* tableCapacity
) >> 8);
385 return tableCapacity
> sMinSize
&&
386 entryCount
<= ((sMinAlphaFrac
* tableCapacity
) >> 8);
389 static bool match(Entry
&e
, const Lookup
&l
) {
390 return HashPolicy::match(HashPolicy::getKey(e
.t
), l
);
393 Entry
&lookup(const Lookup
&l
, HashNumber keyHash
, unsigned collisionBit
) const
395 JS_ASSERT(isLiveHash(keyHash
));
396 JS_ASSERT(!(keyHash
& sCollisionBit
));
397 JS_ASSERT(collisionBit
== 0 || collisionBit
== sCollisionBit
);
399 METER(stats
.searches
++);
401 /* Compute the primary hash address. */
402 HashNumber h1
= hash1(keyHash
, hashShift
);
403 Entry
*entry
= &table
[h1
];
405 /* Miss: return space for a new entry. */
406 if (entry
->isFree()) {
407 METER(stats
.misses
++);
411 /* Hit: return entry. */
412 if (entry
->matchHash(keyHash
) && match(*entry
, l
)) {
417 /* Collision: double hash. */
418 unsigned sizeLog2
= sHashBits
- hashShift
;
419 HashNumber h2
= hash2(keyHash
, sizeLog2
, hashShift
);
420 HashNumber sizeMask
= (HashNumber(1) << sizeLog2
) - 1;
422 /* Save the first removed entry pointer so we can recycle later. */
423 Entry
*firstRemoved
= NULL
;
426 if (JS_UNLIKELY(entry
->isRemoved())) {
428 firstRemoved
= entry
;
430 entry
->setCollision(collisionBit
);
433 METER(stats
.steps
++);
438 if (entry
->isFree()) {
439 METER(stats
.misses
++);
440 return firstRemoved
? *firstRemoved
: *entry
;
443 if (entry
->matchHash(keyHash
) && match(*entry
, l
)) {
451 * This is a copy of lookup hardcoded to the assumptions:
452 * 1. the lookup is a lookupForAdd
453 * 2. the key, whose |keyHash| has been passed is not in the table,
454 * 3. no entries have been removed from the table.
455 * This specialized search avoids the need for recovering lookup values
456 * from entries, which allows more flexible Lookup/Key types.
458 Entry
&findFreeEntry(HashNumber keyHash
)
460 METER(stats
.searches
++);
461 JS_ASSERT(!(keyHash
& sCollisionBit
));
463 /* N.B. the |keyHash| has already been distributed. */
465 /* Compute the primary hash address. */
466 HashNumber h1
= hash1(keyHash
, hashShift
);
467 Entry
*entry
= &table
[h1
];
469 /* Miss: return space for a new entry. */
470 if (entry
->isFree()) {
471 METER(stats
.misses
++);
475 /* Collision: double hash. */
476 unsigned sizeLog2
= sHashBits
- hashShift
;
477 HashNumber h2
= hash2(keyHash
, sizeLog2
, hashShift
);
478 HashNumber sizeMask
= (HashNumber(1) << sizeLog2
) - 1;
481 JS_ASSERT(!entry
->isRemoved());
482 entry
->setCollision();
484 METER(stats
.steps
++);
489 if (entry
->isFree()) {
490 METER(stats
.misses
++);
496 bool changeTableSize(int deltaLog2
)
498 /* Look, but don't touch, until we succeed in getting new entry store. */
499 Entry
*oldTable
= table
;
500 uint32 oldCap
= tableCapacity
;
501 uint32 newLog2
= sHashBits
- hashShift
+ deltaLog2
;
502 uint32 newCapacity
= JS_BIT(newLog2
);
503 if (newCapacity
>= sSizeLimit
) {
504 this->reportAllocOverflow();
508 Entry
*newTable
= createTable(*this, newCapacity
);
512 /* We can't fail from here on, so update table parameters. */
513 setTableSizeLog2(newLog2
);
518 /* Copy only live entries, leaving removed ones behind. */
519 for (Entry
*src
= oldTable
, *end
= src
+ oldCap
; src
!= end
; ++src
) {
521 src
->unsetCollision();
522 findFreeEntry(src
->getKeyHash()) = *src
;
526 destroyTable(*this, oldTable
, oldCap
);
530 void remove(Entry
&e
)
532 METER(stats
.removes
++);
533 if (e
.hasCollision()) {
537 METER(stats
.removeFrees
++);
546 void checkUnderloaded()
549 METER(stats
.shrinks
++);
550 (void) changeTableSize(-1);
557 for (Entry
*e
= table
, *end
= table
+ tableCapacity
; e
!= end
; ++e
)
567 return Range(table
, table
+ tableCapacity
);
574 uint32
count() const{
578 uint32
generation() const {
582 Ptr
lookup(const Lookup
&l
) const {
583 ReentrancyGuard
g(*this);
584 HashNumber keyHash
= prepareHash(l
);
585 return Ptr(lookup(l
, keyHash
, 0));
588 AddPtr
lookupForAdd(const Lookup
&l
) const {
589 ReentrancyGuard
g(*this);
590 HashNumber keyHash
= prepareHash(l
);
591 Entry
&entry
= lookup(l
, keyHash
, sCollisionBit
);
593 return AddPtr(entry
, keyHash
, mutationCount
);
595 return AddPtr(entry
, keyHash
);
601 ReentrancyGuard
g(*this);
602 JS_ASSERT(mutationCount
== p
.mutationCount
);
604 JS_ASSERT(!p
.found());
605 JS_ASSERT(!(p
.keyHash
& sCollisionBit
));
608 * Changing an entry from removed to live does not affect whether we
609 * are overloaded and can be handled separately.
611 if (p
.entry
->isRemoved()) {
612 METER(stats
.addOverRemoved
++);
614 p
.keyHash
|= sCollisionBit
;
616 /* If alpha is >= .75, grow or compress the table. */
618 /* Compress if a quarter or more of all entries are removed. */
620 if (removedCount
>= (tableCapacity
>> 2)) {
621 METER(stats
.compresses
++);
624 METER(stats
.grows
++);
628 if (!changeTableSize(deltaLog2
))
631 /* Preserve the validity of |p.entry|. */
632 p
.entry
= &findFreeEntry(p
.keyHash
);
636 p
.entry
->setLive(p
.keyHash
);
645 * There is an important contract between the caller and callee for this
646 * function: if add() returns true, the caller must assign the T value
647 * which produced p before using the hashtable again.
649 bool add(AddPtr
&p
, T
** pentry
)
653 *pentry
= &p
.entry
->t
;
657 bool add(AddPtr
&p
, const T
&t
)
665 bool relookupOrAdd(AddPtr
& p
, const Lookup
&l
, const T
& t
)
668 p
.mutationCount
= mutationCount
;
671 ReentrancyGuard
g(*this);
672 p
.entry
= &lookup(l
, p
.keyHash
, sCollisionBit
);
674 return p
.found() || add(p
, t
);
679 ReentrancyGuard
g(*this);
680 JS_ASSERT(p
.found());
692 * A hash policy P for a hash table with key-type Key must provide:
693 * - a type |P::Lookup| to use to lookup table entries;
694 * - a static member function |P::hash| with signature
696 * static js::HashNumber hash(Lookup)
698 * to use to hash the lookup type; and
699 * - a static member function |P::match| with signature
701 * static bool match(Key, Lookup)
703 * to use to test equality of key and lookup values.
705 * Normally, Lookup = Key. In general, though, different values and types of
706 * values can be used to lookup and store. If a Lookup value |l| is != to the
707 * added Key value |k|, the user must ensure that |P::match(k,l)|. E.g.:
709 * js::HashSet<Key, P>::AddPtr p = h.lookup(l);
711 * assert(P::match(k, l)); // must hold
716 /* Default hashing policies. */
721 static HashNumber
hash(const Lookup
&l
) {
722 /* Hash if can implicitly cast to hash number type. */
725 static bool match(const Key
&k
, const Lookup
&l
) {
726 /* Use builtin or overloaded operator==. */
731 /* Specialized hashing policy for pointer types. */
733 struct DefaultHasher
<T
*>
736 static HashNumber
hash(T
*l
) {
738 * Strip often-0 lower bits for better distribution after multiplying
739 * by the sGoldenRatio.
741 return HashNumber(reinterpret_cast<size_t>(l
) >>
742 tl::FloorLog2
<sizeof(void *)>::result
);
744 static bool match(T
*k
, T
*l
) {
750 * JS-friendly, STL-like container providing a hash-based map from keys to
751 * values. In particular, HashMap calls constructors and destructors of all
752 * objects added so non-PODs may be used safely.
754 * Key/Value requirements:
755 * - default constructible, copyable, destructible, assignable
756 * HashPolicy requirements:
757 * - see "Hash policy" above (default js::DefaultHasher<Key>)
759 * - see "Allocation policies" in jstl.h (default js::ContextAllocPolicy)
761 * N.B: HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
762 * called by HashMap must not call back into the same HashMap object.
763 * N.B: Due to the lack of exception handling, the user must call |init()|.
765 template <class Key
, class Value
, class HashPolicy
, class AllocPolicy
>
769 typedef typename
HashPolicy::Lookup Lookup
;
773 template <class, class, class> friend class detail::HashTable
;
774 void operator=(const Entry
&rhs
) {
775 const_cast<Key
&>(key
) = rhs
.key
;
780 Entry() : key(), value() {}
781 Entry(const Key
&k
, const Value
&v
) : key(k
), value(v
) {}
788 /* Implement HashMap using HashTable. Lift |Key| operations to |Entry|. */
789 struct MapHashPolicy
: HashPolicy
792 static const Key
&getKey(Entry
&e
) { return e
.key
; }
794 typedef detail::HashTable
<Entry
, MapHashPolicy
, AllocPolicy
> Impl
;
796 friend class Impl::Enum
;
798 /* Not implicitly copyable (expensive). May add explicit |clone| later. */
799 HashMap(const HashMap
&);
800 HashMap
&operator=(const HashMap
&);
806 * HashMap construction is fallible (due to OOM); thus the user must call
807 * init after constructing a HashMap and check the return value.
809 HashMap(AllocPolicy a
= AllocPolicy()) : impl(a
) {}
810 bool init(uint32 len
= 0) { return impl
.init(len
); }
811 bool initialized() const { return impl
.initialized(); }
814 * Return whether the given lookup value is present in the map. E.g.:
816 * typedef HashMap<int,char> HM;
818 * if (HM::Ptr p = h.lookup(3)) {
819 * const HM::Entry &e = *p; // p acts like a pointer to Entry
820 * assert(p->key == 3); // Entry contains the key
821 * char val = p->value; // and value
824 * Also see the definition of Ptr in HashTable above (with T = Entry).
826 typedef typename
Impl::Ptr Ptr
;
827 Ptr
lookup(const Lookup
&l
) const { return impl
.lookup(l
); }
829 /* Assuming |p.found()|, remove |*p|. */
830 void remove(Ptr p
) { impl
.remove(p
); }
833 * Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
834 * insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
835 * |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new Entry. E.g.:
837 * typedef HashMap<int,char> HM;
839 * HM::AddPtr p = h.lookupForAdd(3);
841 * if (!h.add(p, 3, 'a'))
844 * const HM::Entry &e = *p; // p acts like a pointer to Entry
845 * assert(p->key == 3); // Entry contains the key
846 * char val = p->value; // and value
848 * Also see the definition of AddPtr in HashTable above (with T = Entry).
850 * N.B. The caller must ensure that no mutating hash table operations
851 * occur between a pair of |lookupForAdd| and |add| calls. To avoid
852 * looking up the key a second time, the caller may use the more efficient
853 * relookupOrAdd method. This method reuses part of the hashing computation
854 * to more efficiently insert the key if it has not been added. For
855 * example, a mutation-handling version of the previous example:
857 * HM::AddPtr p = h.lookupForAdd(3);
859 * call_that_may_mutate_h();
860 * if (!h.relookupOrAdd(p, 3, 'a'))
863 * const HM::Entry &e = *p;
864 * assert(p->key == 3);
865 * char val = p->value;
867 typedef typename
Impl::AddPtr AddPtr
;
868 AddPtr
lookupForAdd(const Lookup
&l
) const {
869 return impl
.lookupForAdd(l
);
872 bool add(AddPtr
&p
, const Key
&k
, const Value
&v
) {
874 if (!impl
.add(p
, &pentry
))
876 const_cast<Key
&>(pentry
->key
) = k
;
881 bool add(AddPtr
&p
, const Key
&k
) {
883 if (!impl
.add(p
, &pentry
))
885 const_cast<Key
&>(pentry
->key
) = k
;
889 bool relookupOrAdd(AddPtr
&p
, const Key
&k
, const Value
&v
) {
890 return impl
.relookupOrAdd(p
, k
, Entry(k
, v
));
894 * |all()| returns a Range containing |count()| elements. E.g.:
896 * typedef HashMap<int,char> HM;
898 * for (HM::Range r = h.all(); !r.empty(); r.popFront())
899 * char c = r.front().value;
901 * Also see the definition of Range in HashTable above (with T = Entry).
903 typedef typename
Impl::Range Range
;
904 Range
all() const { return impl
.all(); }
905 size_t count() const { return impl
.count(); }
908 * Typedef for the enumeration class. An Enum may be used to examine and
909 * remove table entries:
911 * typedef HashMap<int,char> HM;
913 * for (HM::Enum e(s); !e.empty(); e.popFront())
914 * if (e.front().value == 'l')
917 * Table resize may occur in Enum's destructor. Also see the definition of
918 * Enum in HashTable above (with T = Entry).
920 typedef typename
Impl::Enum Enum
;
922 /* Remove all entries. */
923 void clear() { impl
.clear(); }
925 /* Does the table contain any entries? */
926 bool empty() const { return impl
.empty(); }
929 * If |generation()| is the same before and after a HashMap operation,
930 * pointers into the table remain valid.
932 unsigned generation() const { return impl
.generation(); }
934 /* Shorthand operations: */
936 bool has(const Lookup
&l
) const {
937 return impl
.lookup(l
) != NULL
;
940 Entry
*put(const Key
&k
, const Value
&v
) {
941 AddPtr p
= lookupForAdd(k
);
946 return add(p
, k
, v
) ? &*p
: NULL
;
949 void remove(const Lookup
&l
) {
950 if (Ptr p
= lookup(l
))
956 * JS-friendly, STL-like container providing a hash-based set of values. In
957 * particular, HashSet calls constructors and destructors of all objects added
958 * so non-PODs may be used safely.
961 * - default constructible, copyable, destructible, assignable
962 * HashPolicy requirements:
963 * - see "Hash policy" above (default js::DefaultHasher<Key>)
965 * - see "Allocation policies" in jstl.h (default js::ContextAllocPolicy)
967 * N.B: HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
968 * HashSet must not call back into the same HashSet object.
969 * N.B: Due to the lack of exception handling, the user must call |init()|.
971 template <class T
, class HashPolicy
, class AllocPolicy
>
974 typedef typename
HashPolicy::Lookup Lookup
;
976 /* Implement HashSet in terms of HashTable. */
977 struct SetOps
: HashPolicy
{
979 static const KeyType
&getKey(const T
&t
) { return t
; }
981 typedef detail::HashTable
<const T
, SetOps
, AllocPolicy
> Impl
;
983 friend class Impl::Enum
;
985 /* Not implicitly copyable (expensive). May add explicit |clone| later. */
986 HashSet(const HashSet
&);
987 HashSet
&operator=(const HashSet
&);
993 * HashSet construction is fallible (due to OOM); thus the user must call
994 * init after constructing a HashSet and check the return value.
996 HashSet(AllocPolicy a
= AllocPolicy()) : impl(a
) {}
997 bool init(uint32 len
= 0) { return impl
.init(len
); }
998 bool initialized() const { return impl
.initialized(); }
1001 * Return whether the given lookup value is present in the map. E.g.:
1003 * typedef HashSet<int> HS;
1005 * if (HS::Ptr p = h.lookup(3)) {
1006 * assert(*p == 3); // p acts like a pointer to int
1009 * Also see the definition of Ptr in HashTable above.
1011 typedef typename
Impl::Ptr Ptr
;
1012 Ptr
lookup(const Lookup
&l
) const { return impl
.lookup(l
); }
1014 /* Assuming |p.found()|, remove |*p|. */
1015 void remove(Ptr p
) { impl
.remove(p
); }
1018 * Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
1019 * insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
1020 * |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
1022 * typedef HashSet<int> HS;
1024 * HS::AddPtr p = h.lookupForAdd(3);
1029 * assert(*p == 3); // p acts like a pointer to int
1031 * Also see the definition of AddPtr in HashTable above.
1033 * N.B. The caller must ensure that no mutating hash table operations
1034 * occur between a pair of |lookupForAdd| and |add| calls. To avoid
1035 * looking up the key a second time, the caller may use the more efficient
1036 * relookupOrAdd method. This method reuses part of the hashing computation
1037 * to more efficiently insert the key if it has not been added. For
1038 * example, a mutation-handling version of the previous example:
1040 * HS::AddPtr p = h.lookupForAdd(3);
1042 * call_that_may_mutate_h();
1043 * if (!h.relookupOrAdd(p, 3, 3))
1048 * Note that relookupOrAdd(p,l,t) performs Lookup using l and adds the
1049 * entry t, where the caller ensures match(l,t).
1051 typedef typename
Impl::AddPtr AddPtr
;
1052 AddPtr
lookupForAdd(const Lookup
&l
) const {
1053 return impl
.lookupForAdd(l
);
1056 bool add(AddPtr
&p
, const T
&t
) {
1057 return impl
.add(p
, t
);
1060 bool relookupOrAdd(AddPtr
&p
, const Lookup
&l
, const T
&t
) {
1061 return impl
.relookupOrAdd(p
, l
, t
);
1065 * |all()| returns a Range containing |count()| elements:
1067 * typedef HashSet<int> HS;
1069 * for (HS::Range r = h.all(); !r.empty(); r.popFront())
1070 * int i = r.front();
1072 * Also see the definition of Range in HashTable above.
1074 typedef typename
Impl::Range Range
;
1075 Range
all() const { return impl
.all(); }
1076 size_t count() const { return impl
.count(); }
1079 * Typedef for the enumeration class. An Enum may be used to examine and
1080 * remove table entries:
1082 * typedef HashSet<int> HS;
1084 * for (HS::Enum e(s); !e.empty(); e.popFront())
1085 * if (e.front() == 42)
1088 * Table resize may occur in Enum's destructor. Also see the definition of
1089 * Enum in HashTable above.
1091 typedef typename
Impl::Enum Enum
;
1093 /* Remove all entries. */
1094 void clear() { impl
.clear(); }
1096 /* Does the table contain any entries? */
1097 bool empty() const { return impl
.empty(); }
1100 * If |generation()| is the same before and after a HashSet operation,
1101 * pointers into the table remain valid.
1103 unsigned generation() const { return impl
.generation(); }
1105 /* Shorthand operations: */
1107 bool has(const Lookup
&l
) const {
1108 return impl
.lookup(l
) != NULL
;
1111 const T
*put(const T
&t
) {
1112 AddPtr p
= lookupForAdd(t
);
1113 return p
? &*p
: (add(p
, t
) ? &*p
: NULL
);
1116 void remove(const Lookup
&l
) {
1117 if (Ptr p
= lookup(l
))
1122 } /* namespace js */