xpcom/ds/nsCheapSets.h

   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   ~nsCheapSet() { Clear(); }
  25
  26   /**
  27    * Remove all entries.
  28    */
  29   void Clear()
  30   {
  31     switch (mState) {
  32       case ZERO:
  33         break;
  34       case ONE:
  35         GetSingleEntry()->~EntryType();
  36         break;
  37       case MANY:
  38         delete mUnion.table;
  39         break;
  40       default:
  41         NS_NOTREACHED("bogus state");
  42         break;
  43     }
  44     mState = ZERO;
  45   }
  46
  47   nsresult Put(const KeyType aVal);
  48
  49   void Remove(const KeyType aVal);
  50
  51   bool Contains(const KeyType aVal)
  52   {
  53     switch (mState) {
  54       case ZERO:
  55         return false;
  56       case ONE:
  57         return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
  58       case MANY:
  59         return !!mUnion.table->GetEntry(aVal);
  60       default:
  61         NS_NOTREACHED("bogus state");
  62         return false;
  63     }
  64   }
  65
  66   uint32_t EnumerateEntries(Enumerator aEnumFunc, void* aUserArg)
  67   {
  68     switch (mState) {
  69       case ZERO:
  70         return 0;
  71       case ONE:
  72         if (aEnumFunc(GetSingleEntry(), aUserArg) == PL_DHASH_REMOVE) {
  73           GetSingleEntry()->~EntryType();
  74           mState = ZERO;
  75         }
  76         return 1;
  77       case MANY:
  78         return mUnion.table->EnumerateEntries(aEnumFunc, aUserArg);
  79       default:
  80         NS_NOTREACHED("bogus state");
  81         return 0;
  82     }
  83   }
  84
  85 private:
  86   EntryType* GetSingleEntry()
  87   {
  88     return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
  89   }
  90
  91   enum SetState
  92   {
  93     ZERO,
  94     ONE,
  95     MANY
  96   };
  97
  98   union
  99   {
 100     nsTHashtable<EntryType>* table;
 101     char singleEntry[sizeof(EntryType)];
 102   } mUnion;
 103   enum SetState mState;
 104 };
 105
 106 template<typename EntryType>
 107 nsresult
 108 nsCheapSet<EntryType>::Put(const KeyType aVal)
 109 {
 110   switch (mState) {
 111     case ZERO:
 112       new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
 113       mState = ONE;
 114       return NS_OK;
 115     case ONE: {
 116       nsTHashtable<EntryType>* table = new nsTHashtable<EntryType>();
 117       EntryType* entry = GetSingleEntry();
 118       table->PutEntry(entry->GetKey());
 119       entry->~EntryType();
 120       mUnion.table = table;
 121       mState = MANY;
 122     }
 123     // Fall through.
 124     case MANY:
 125       mUnion.table->PutEntry(aVal);
 126       return NS_OK;
 127     default:
 128       NS_NOTREACHED("bogus state");
 129       return NS_OK;
 130   }
 131 }
 132
 133 template<typename EntryType>
 134 void
 135 nsCheapSet<EntryType>::Remove(const KeyType aVal)
 136 {
 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       NS_NOTREACHED("bogus state");
 151       break;
 152   }
 153 }
 154
 155 #endif