1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/ds/nsCheapSets.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,150 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef __nsCheapSets_h__
1.10 +#define __nsCheapSets_h__
1.11 +
1.12 +#include "nsTHashtable.h"
1.13 +#include <stdint.h>
1.14 +
1.15 +/**
1.16 + * A set that takes up minimal size when there are 0 or 1 entries in the set.
1.17 + * Use for cases where sizes of 0 and 1 are even slightly common.
1.18 + */
1.19 +template<typename EntryType>
1.20 +class nsCheapSet
1.21 +{
1.22 +public:
1.23 + typedef typename EntryType::KeyType KeyType;
1.24 + typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
1.25 +
1.26 + nsCheapSet() : mState(ZERO)
1.27 + {
1.28 + }
1.29 + ~nsCheapSet()
1.30 + {
1.31 + switch (mState) {
1.32 + case ZERO:
1.33 + break;
1.34 + case ONE:
1.35 + GetSingleEntry()->~EntryType();
1.36 + break;
1.37 + case MANY:
1.38 + delete mUnion.table;
1.39 + break;
1.40 + default:
1.41 + NS_NOTREACHED("bogus state");
1.42 + break;
1.43 + }
1.44 + }
1.45 +
1.46 + nsresult Put(const KeyType aVal);
1.47 +
1.48 + void Remove(const KeyType aVal);
1.49 +
1.50 + bool Contains(const KeyType aVal)
1.51 + {
1.52 + switch (mState) {
1.53 + case ZERO:
1.54 + return false;
1.55 + case ONE:
1.56 + return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
1.57 + case MANY:
1.58 + return !!mUnion.table->GetEntry(aVal);
1.59 + default:
1.60 + NS_NOTREACHED("bogus state");
1.61 + return false;
1.62 + }
1.63 + }
1.64 +
1.65 + uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg)
1.66 + {
1.67 + switch (mState) {
1.68 + case ZERO:
1.69 + return 0;
1.70 + case ONE:
1.71 + if (enumFunc(GetSingleEntry(), userArg) == PL_DHASH_REMOVE) {
1.72 + GetSingleEntry()->~EntryType();
1.73 + mState = ZERO;
1.74 + }
1.75 + return 1;
1.76 + case MANY:
1.77 + return mUnion.table->EnumerateEntries(enumFunc, userArg);
1.78 + default:
1.79 + NS_NOTREACHED("bogus state");
1.80 + return 0;
1.81 + }
1.82 + }
1.83 +
1.84 +private:
1.85 + EntryType* GetSingleEntry()
1.86 + {
1.87 + return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
1.88 + }
1.89 +
1.90 + enum SetState {
1.91 + ZERO,
1.92 + ONE,
1.93 + MANY
1.94 + };
1.95 +
1.96 + union {
1.97 + nsTHashtable<EntryType> *table;
1.98 + char singleEntry[sizeof(EntryType)];
1.99 + } mUnion;
1.100 + enum SetState mState;
1.101 +};
1.102 +
1.103 +template<typename EntryType>
1.104 +nsresult
1.105 +nsCheapSet<EntryType>::Put(const KeyType aVal)
1.106 +{
1.107 + switch (mState) {
1.108 + case ZERO:
1.109 + new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
1.110 + mState = ONE;
1.111 + return NS_OK;
1.112 + case ONE:
1.113 + {
1.114 + nsTHashtable<EntryType> *table = new nsTHashtable<EntryType>();
1.115 + EntryType *entry = GetSingleEntry();
1.116 + table->PutEntry(entry->GetKey());
1.117 + entry->~EntryType();
1.118 + mUnion.table = table;
1.119 + mState = MANY;
1.120 + }
1.121 + // Fall through.
1.122 + case MANY:
1.123 + mUnion.table->PutEntry(aVal);
1.124 + return NS_OK;
1.125 + default:
1.126 + NS_NOTREACHED("bogus state");
1.127 + return NS_OK;
1.128 + }
1.129 +}
1.130 +
1.131 +template<typename EntryType>
1.132 +void
1.133 +nsCheapSet<EntryType>::Remove(const KeyType aVal)
1.134 +{
1.135 + switch (mState) {
1.136 + case ZERO:
1.137 + break;
1.138 + case ONE:
1.139 + if (Contains(aVal)) {
1.140 + GetSingleEntry()->~EntryType();
1.141 + mState = ZERO;
1.142 + }
1.143 + break;
1.144 + case MANY:
1.145 + mUnion.table->RemoveEntry(aVal);
1.146 + break;
1.147 + default:
1.148 + NS_NOTREACHED("bogus state");
1.149 + break;
1.150 + }
1.151 +}
1.152 +
1.153 +#endif
