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   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
  28   nsCheapSet() : mState(ZERO) { mUnion.table = nullptr; }
  29   ~nsCheapSet() { Clear(); }
  30
  31   /**
  32    * Remove all entries.
  33    */
  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
  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
  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:
  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>
 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>
 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