1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 #ifndef __nsCheapSets_h__
7 #define __nsCheapSets_h__
9 #include "nsTHashtable.h"
13 * A set that takes up minimal size when there are 0 or 1 entries in the set.
14 * Use for cases where sizes of 0 and 1 are even slightly common.
16 template<typename EntryType
>
20 typedef typename
EntryType::KeyType KeyType
;
21 typedef PLDHashOperator (*Enumerator
)(EntryType
* aEntry
, void* userArg
);
23 nsCheapSet() : mState(ZERO
) {}
24 ~nsCheapSet() { Clear(); }
35 GetSingleEntry()->~EntryType();
41 NS_NOTREACHED("bogus state");
47 nsresult
Put(const KeyType aVal
);
49 void Remove(const KeyType aVal
);
51 bool Contains(const KeyType aVal
)
57 return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal
));
59 return !!mUnion
.table
->GetEntry(aVal
);
61 NS_NOTREACHED("bogus state");
66 uint32_t EnumerateEntries(Enumerator aEnumFunc
, void* aUserArg
)
72 if (aEnumFunc(GetSingleEntry(), aUserArg
) == PL_DHASH_REMOVE
) {
73 GetSingleEntry()->~EntryType();
78 return mUnion
.table
->EnumerateEntries(aEnumFunc
, aUserArg
);
80 NS_NOTREACHED("bogus state");
86 EntryType
* GetSingleEntry()
88 return reinterpret_cast<EntryType
*>(&mUnion
.singleEntry
[0]);
100 nsTHashtable
<EntryType
>* table
;
101 char singleEntry
[sizeof(EntryType
)];
103 enum SetState mState
;
106 template<typename EntryType
>
108 nsCheapSet
<EntryType
>::Put(const KeyType aVal
)
112 new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal
));
116 nsTHashtable
<EntryType
>* table
= new nsTHashtable
<EntryType
>();
117 EntryType
* entry
= GetSingleEntry();
118 table
->PutEntry(entry
->GetKey());
120 mUnion
.table
= table
;
125 mUnion
.table
->PutEntry(aVal
);
128 NS_NOTREACHED("bogus state");
133 template<typename EntryType
>
135 nsCheapSet
<EntryType
>::Remove(const KeyType aVal
)
141 if (Contains(aVal
)) {
142 GetSingleEntry()->~EntryType();
147 mUnion
.table
->RemoveEntry(aVal
);
150 NS_NOTREACHED("bogus state");