The Tor Browser / file comparison
comparison: xpcom/ds/nsCheapSets.h
xpcom/ds/nsCheapSets.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:511fb236c3d5 |
|---|---|
| 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/. */ | |
| 5 | |
| 6 #ifndef __nsCheapSets_h__ | |
| 7 #define __nsCheapSets_h__ | |
| 8 | |
| 9 #include "nsTHashtable.h" | |
| 10 #include <stdint.h> | |
| 11 | |
| 12 /** | |
| 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. | |
| 15 */ | |
| 16 template<typename EntryType> | |
| 17 class nsCheapSet | |
| 18 { | |
| 19 public: | |
| 20 typedef typename EntryType::KeyType KeyType; | |
| 21 typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg); | |
| 22 | |
| 23 nsCheapSet() : mState(ZERO) | |
| 24 { | |
| 25 } | |
| 26 ~nsCheapSet() | |
| 27 { | |
| 28 switch (mState) { | |
| 29 case ZERO: | |
| 30 break; | |
| 31 case ONE: | |
| 32 GetSingleEntry()->~EntryType(); | |
| 33 break; | |
| 34 case MANY: | |
| 35 delete mUnion.table; | |
| 36 break; | |
| 37 default: | |
| 38 NS_NOTREACHED("bogus state"); | |
| 39 break; | |
| 40 } | |
| 41 } | |
| 42 | |
| 43 nsresult Put(const KeyType aVal); | |
| 44 | |
| 45 void Remove(const KeyType aVal); | |
| 46 | |
| 47 bool Contains(const KeyType aVal) | |
| 48 { | |
| 49 switch (mState) { | |
| 50 case ZERO: | |
| 51 return false; | |
| 52 case ONE: | |
| 53 return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal)); | |
| 54 case MANY: | |
| 55 return !!mUnion.table->GetEntry(aVal); | |
| 56 default: | |
| 57 NS_NOTREACHED("bogus state"); | |
| 58 return false; | |
| 59 } | |
| 60 } | |
| 61 | |
| 62 uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg) | |
| 63 { | |
| 64 switch (mState) { | |
| 65 case ZERO: | |
| 66 return 0; | |
| 67 case ONE: | |
| 68 if (enumFunc(GetSingleEntry(), userArg) == PL_DHASH_REMOVE) { | |
| 69 GetSingleEntry()->~EntryType(); | |
| 70 mState = ZERO; | |
| 71 } | |
| 72 return 1; | |
| 73 case MANY: | |
| 74 return mUnion.table->EnumerateEntries(enumFunc, userArg); | |
| 75 default: | |
| 76 NS_NOTREACHED("bogus state"); | |
| 77 return 0; | |
| 78 } | |
| 79 } | |
| 80 | |
| 81 private: | |
| 82 EntryType* GetSingleEntry() | |
| 83 { | |
| 84 return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]); | |
| 85 } | |
| 86 | |
| 87 enum SetState { | |
| 88 ZERO, | |
| 89 ONE, | |
| 90 MANY | |
| 91 }; | |
| 92 | |
| 93 union { | |
| 94 nsTHashtable<EntryType> *table; | |
| 95 char singleEntry[sizeof(EntryType)]; | |
| 96 } mUnion; | |
| 97 enum SetState mState; | |
| 98 }; | |
| 99 | |
| 100 template<typename EntryType> | |
| 101 nsresult | |
| 102 nsCheapSet<EntryType>::Put(const KeyType aVal) | |
| 103 { | |
| 104 switch (mState) { | |
| 105 case ZERO: | |
| 106 new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal)); | |
| 107 mState = ONE; | |
| 108 return NS_OK; | |
| 109 case ONE: | |
| 110 { | |
| 111 nsTHashtable<EntryType> *table = new nsTHashtable<EntryType>(); | |
| 112 EntryType *entry = GetSingleEntry(); | |
| 113 table->PutEntry(entry->GetKey()); | |
| 114 entry->~EntryType(); | |
| 115 mUnion.table = table; | |
| 116 mState = MANY; | |
| 117 } | |
| 118 // Fall through. | |
| 119 case MANY: | |
| 120 mUnion.table->PutEntry(aVal); | |
| 121 return NS_OK; | |
| 122 default: | |
| 123 NS_NOTREACHED("bogus state"); | |
| 124 return NS_OK; | |
| 125 } | |
| 126 } | |
| 127 | |
| 128 template<typename EntryType> | |
| 129 void | |
| 130 nsCheapSet<EntryType>::Remove(const KeyType aVal) | |
| 131 { | |
| 132 switch (mState) { | |
| 133 case ZERO: | |
| 134 break; | |
| 135 case ONE: | |
| 136 if (Contains(aVal)) { | |
| 137 GetSingleEntry()->~EntryType(); | |
| 138 mState = ZERO; | |
| 139 } | |
| 140 break; | |
| 141 case MANY: | |
| 142 mUnion.table->RemoveEntry(aVal); | |
| 143 break; | |
| 144 default: | |
| 145 NS_NOTREACHED("bogus state"); | |
| 146 break; | |
| 147 } | |
| 148 } | |
| 149 | |
| 150 #endif |
