1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
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/. */
6
7 #ifndef __nsCheapSets_h__
8 #define __nsCheapSets_h__
9
10 #include "nsTHashtable.h"
11 #include <stdint.h>
12
13 enum nsCheapSetOperator
14 {
15 OpNext = 0, // enumerator says continue
16 OpRemove = 1, // enumerator says remove and continue
17 };
18
19 /**
20 * A set that takes up minimal size when there are 0 or 1 entries in the set.
21 * Use for cases where sizes of 0 and 1 are even slightly common.
22 */
23 template<typename EntryType>
24 class nsCheapSet
25 {
26 public:
27 typedef typename EntryType::KeyType KeyType;
28 typedef nsCheapSetOperator (*Enumerator)(EntryType* aEntry, void* userArg);
29
nsCheapSet()30 nsCheapSet() : mState(ZERO) {}
~nsCheapSet()31 ~nsCheapSet() { Clear(); }
32
33 /**
34 * Remove all entries.
35 */
Clear()36 void Clear()
37 {
38 switch (mState) {
39 case ZERO:
40 break;
41 case ONE:
42 GetSingleEntry()->~EntryType();
43 break;
44 case MANY:
45 delete mUnion.table;
46 break;
47 default:
48 NS_NOTREACHED("bogus state");
49 break;
50 }
51 mState = ZERO;
52 }
53
54 void Put(const KeyType aVal);
55
56 void Remove(const KeyType aVal);
57
Contains(const KeyType aVal)58 bool Contains(const KeyType aVal)
59 {
60 switch (mState) {
61 case ZERO:
62 return false;
63 case ONE:
64 return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
65 case MANY:
66 return !!mUnion.table->GetEntry(aVal);
67 default:
68 NS_NOTREACHED("bogus state");
69 return false;
70 }
71 }
72
EnumerateEntries(Enumerator aEnumFunc,void * aUserArg)73 uint32_t EnumerateEntries(Enumerator aEnumFunc, void* aUserArg)
74 {
75 switch (mState) {
76 case ZERO:
77 return 0;
78 case ONE:
79 if (aEnumFunc(GetSingleEntry(), aUserArg) == OpRemove) {
80 GetSingleEntry()->~EntryType();
81 mState = ZERO;
82 }
83 return 1;
84 case MANY: {
85 uint32_t n = mUnion.table->Count();
86 for (auto iter = mUnion.table->Iter(); !iter.Done(); iter.Next()) {
87 auto entry = static_cast<EntryType*>(iter.Get());
88 if (aEnumFunc(entry, aUserArg) == OpRemove) {
89 iter.Remove();
90 }
91 }
92 return n;
93 }
94 default:
95 NS_NOTREACHED("bogus state");
96 return 0;
97 }
98 }
99
100 private:
GetSingleEntry()101 EntryType* GetSingleEntry()
102 {
103 return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
104 }
105
106 enum SetState
107 {
108 ZERO,
109 ONE,
110 MANY
111 };
112
113 union
114 {
115 nsTHashtable<EntryType>* table;
116 char singleEntry[sizeof(EntryType)];
117 } mUnion;
118 enum SetState mState;
119 };
120
121 template<typename EntryType>
122 void
Put(const KeyType aVal)123 nsCheapSet<EntryType>::Put(const KeyType aVal)
124 {
125 switch (mState) {
126 case ZERO:
127 new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
128 mState = ONE;
129 return;
130 case ONE: {
131 nsTHashtable<EntryType>* table = new nsTHashtable<EntryType>();
132 EntryType* entry = GetSingleEntry();
133 table->PutEntry(entry->GetKey());
134 entry->~EntryType();
135 mUnion.table = table;
136 mState = MANY;
137 }
138 MOZ_FALLTHROUGH;
139
140 case MANY:
141 mUnion.table->PutEntry(aVal);
142 return;
143 default:
144 NS_NOTREACHED("bogus state");
145 return;
146 }
147 }
148
149 template<typename EntryType>
150 void
Remove(const KeyType aVal)151 nsCheapSet<EntryType>::Remove(const KeyType aVal)
152 {
153 switch (mState) {
154 case ZERO:
155 break;
156 case ONE:
157 if (Contains(aVal)) {
158 GetSingleEntry()->~EntryType();
159 mState = ZERO;
160 }
161 break;
162 case MANY:
163 mUnion.table->RemoveEntry(aVal);
164 break;
165 default:
166 NS_NOTREACHED("bogus state");
167 break;
168 }
169 }
170
171 #endif
172