Line data    Source code

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