michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef __nsCheapSets_h__
michael@0: #define __nsCheapSets_h__
michael@0: 
michael@0: #include "nsTHashtable.h"
michael@0: #include <stdint.h>
michael@0: 
michael@0: /**
michael@0:  * A set that takes up minimal size when there are 0 or 1 entries in the set.
michael@0:  * Use for cases where sizes of 0 and 1 are even slightly common.
michael@0:  */
michael@0: template<typename EntryType>
michael@0: class nsCheapSet
michael@0: {
michael@0: public:
michael@0:   typedef typename EntryType::KeyType KeyType;
michael@0:   typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
michael@0: 
michael@0:   nsCheapSet() : mState(ZERO)
michael@0:   {
michael@0:   }
michael@0:   ~nsCheapSet()
michael@0:   {
michael@0:     switch (mState) {
michael@0:     case ZERO:
michael@0:       break;
michael@0:     case ONE:
michael@0:       GetSingleEntry()->~EntryType();
michael@0:       break;
michael@0:     case MANY:
michael@0:       delete mUnion.table;
michael@0:       break;
michael@0:     default:
michael@0:       NS_NOTREACHED("bogus state");
michael@0:       break;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   nsresult Put(const KeyType aVal);
michael@0: 
michael@0:   void Remove(const KeyType aVal);
michael@0: 
michael@0:   bool Contains(const KeyType aVal)
michael@0:   {
michael@0:     switch (mState) {
michael@0:     case ZERO:
michael@0:       return false;
michael@0:     case ONE:
michael@0:       return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
michael@0:     case MANY:
michael@0:       return !!mUnion.table->GetEntry(aVal);
michael@0:     default:
michael@0:       NS_NOTREACHED("bogus state");
michael@0:       return false;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg)
michael@0:   {
michael@0:     switch (mState) {
michael@0:     case ZERO:
michael@0:       return 0;
michael@0:     case ONE:
michael@0:       if (enumFunc(GetSingleEntry(), userArg) == PL_DHASH_REMOVE) {
michael@0:         GetSingleEntry()->~EntryType();
michael@0:         mState = ZERO;
michael@0:       }
michael@0:       return 1;
michael@0:     case MANY:
michael@0:       return mUnion.table->EnumerateEntries(enumFunc, userArg);
michael@0:     default:
michael@0:       NS_NOTREACHED("bogus state");
michael@0:       return 0;
michael@0:     }
michael@0:   }
michael@0: 
michael@0: private:
michael@0:   EntryType* GetSingleEntry()
michael@0:   {
michael@0:     return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
michael@0:   }
michael@0: 
michael@0:   enum SetState {
michael@0:     ZERO,
michael@0:     ONE,
michael@0:     MANY
michael@0:   };
michael@0: 
michael@0:   union {
michael@0:     nsTHashtable<EntryType> *table;
michael@0:     char singleEntry[sizeof(EntryType)];
michael@0:   } mUnion;
michael@0:   enum SetState mState;
michael@0: };
michael@0: 
michael@0: template<typename EntryType>
michael@0: nsresult
michael@0: nsCheapSet<EntryType>::Put(const KeyType aVal)
michael@0: {
michael@0:   switch (mState) {
michael@0:   case ZERO:
michael@0:     new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
michael@0:     mState = ONE;
michael@0:     return NS_OK;
michael@0:   case ONE:
michael@0:     {
michael@0:       nsTHashtable<EntryType> *table = new nsTHashtable<EntryType>();
michael@0:       EntryType *entry = GetSingleEntry();
michael@0:       table->PutEntry(entry->GetKey());
michael@0:       entry->~EntryType();
michael@0:       mUnion.table = table;
michael@0:       mState = MANY;
michael@0:     }
michael@0:     // Fall through.
michael@0:   case MANY:
michael@0:     mUnion.table->PutEntry(aVal);
michael@0:     return NS_OK;
michael@0:   default:
michael@0:     NS_NOTREACHED("bogus state");
michael@0:     return NS_OK;
michael@0:   }
michael@0: }
michael@0: 
michael@0: template<typename EntryType>
michael@0: void
michael@0: nsCheapSet<EntryType>::Remove(const KeyType aVal)
michael@0: {
michael@0:   switch (mState) {
michael@0:   case ZERO:
michael@0:     break;
michael@0:   case ONE:
michael@0:     if (Contains(aVal)) {
michael@0:       GetSingleEntry()->~EntryType();
michael@0:       mState = ZERO;
michael@0:     }
michael@0:     break;
michael@0:   case MANY:
michael@0:     mUnion.table->RemoveEntry(aVal);
michael@0:     break;
michael@0:   default:
michael@0:     NS_NOTREACHED("bogus state");
michael@0:     break;
michael@0:   }
michael@0: }
michael@0: 
michael@0: #endif