xpcom/ds/nsCheapSets.h

   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
  30   nsCheapSet()
  31     : mState(ZERO)
  32   {
  33     mUnion.table = nullptr;
  34   }
  35   ~nsCheapSet() { Clear(); }
  36
  37   /**
  38    * Remove all entries.
  39    */
  40   void Clear()
  41   {
  42     switch (mState) {
  43       case ZERO:
  44         break;
  45       case ONE:
  46         GetSingleEntry()->~EntryType();
  47         break;
  48       case MANY:
  49         delete mUnion.table;
  50         break;
  51       default:
  52         MOZ_ASSERT_UNREACHABLE("bogus state");
  53         break;
  54     }
  55     mState = ZERO;
  56   }
  57
  58   void Put(const KeyType aVal);
  59
  60   void Remove(const KeyType aVal);
  61
  62   bool Contains(const KeyType aVal)
  63   {
  64     switch (mState) {
  65       case ZERO:
  66         return false;
  67       case ONE:
  68         return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
  69       case MANY:
  70         return !!mUnion.table->GetEntry(aVal);
  71       default:
  72         MOZ_ASSERT_UNREACHABLE("bogus state");
  73         return false;
  74     }
  75   }
  76
  77   uint32_t EnumerateEntries(Enumerator aEnumFunc, void* aUserArg)
  78   {
  79     switch (mState) {
  80       case ZERO:
  81         return 0;
  82       case ONE:
  83         if (aEnumFunc(GetSingleEntry(), aUserArg) == OpRemove) {
  84           GetSingleEntry()->~EntryType();
  85           mState = ZERO;
  86         }
  87         return 1;
  88       case MANY: {
  89         uint32_t n = mUnion.table->Count();
  90         for (auto iter = mUnion.table->Iter(); !iter.Done(); iter.Next()) {
  91           auto entry = static_cast<EntryType*>(iter.Get());
  92           if (aEnumFunc(entry, aUserArg) == OpRemove) {
  93             iter.Remove();
  94           }
  95         }
  96         return n;
  97       }
  98       default:
  99         MOZ_ASSERT_UNREACHABLE("bogus state");
 100         return 0;
 101     }
 102   }
 103
 104 private:
 105   EntryType* GetSingleEntry()
 106   {
 107     return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
 108   }
 109
 110   enum SetState
 111   {
 112     ZERO,
 113     ONE,
 114     MANY
 115   };
 116
 117   union
 118   {
 119     nsTHashtable<EntryType>* table;
 120     char singleEntry[sizeof(EntryType)];
 121   } mUnion;
 122   enum SetState mState;
 123 };
 124
 125 template<typename EntryType>
 126 void
 127 nsCheapSet<EntryType>::Put(const KeyType aVal)
 128 {
 129   switch (mState) {
 130     case ZERO:
 131       new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
 132       mState = ONE;
 133       return;
 134     case ONE: {
 135       nsTHashtable<EntryType>* table = new nsTHashtable<EntryType>();
 136       EntryType* entry = GetSingleEntry();
 137       table->PutEntry(entry->GetKey());
 138       entry->~EntryType();
 139       mUnion.table = table;
 140       mState = MANY;
 141     }
 142     MOZ_FALLTHROUGH;
 143
 144     case MANY:
 145       mUnion.table->PutEntry(aVal);
 146       return;
 147     default:
 148       MOZ_ASSERT_UNREACHABLE("bogus state");
 149       return;
 150   }
 151 }
 152
 153 template<typename EntryType>
 154 void
 155 nsCheapSet<EntryType>::Remove(const KeyType aVal)
 156 {
 157   switch (mState) {
 158     case ZERO:
 159       break;
 160     case ONE:
 161       if (Contains(aVal)) {
 162         GetSingleEntry()->~EntryType();
 163         mState = ZERO;
 164       }
 165       break;
 166     case MANY:
 167       mUnion.table->RemoveEntry(aVal);
 168       break;
 169     default:
 170       MOZ_ASSERT_UNREACHABLE("bogus state");
 171       break;
 172   }
 173 }
 174
 175 #endif