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