dom/workers/Queue.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 mozilla_dom_workerinternal_Queue_h
   8 #define mozilla_dom_workerinternal_Queue_h
   9
  10 #include "mozilla/Mutex.h"
  11 #include "nsTArray.h"
  12
  13 namespace mozilla::dom::workerinternals {
  14
  15 template <typename T, int TCount>
  16 struct StorageWithTArray {
  17   typedef AutoTArray<T, TCount> StorageType;
  18
  19   static void Reverse(StorageType& aStorage) {
  20     uint32_t length = aStorage.Length();
  21     for (uint32_t index = 0; index < length / 2; index++) {
  22       uint32_t reverseIndex = length - 1 - index;
  23
  24       T t1 = aStorage.ElementAt(index);
  25       T t2 = aStorage.ElementAt(reverseIndex);
  26
  27       aStorage.ReplaceElementsAt(index, 1, t2);
  28       aStorage.ReplaceElementsAt(reverseIndex, 1, t1);
  29     }
  30   }
  31
  32   static bool IsEmpty(const StorageType& aStorage) {
  33     return !!aStorage.IsEmpty();
  34   }
  35
  36   static void Push(StorageType& aStorage, const T& aEntry) {
  37     aStorage.AppendElement(aEntry);
  38   }
  39
  40   static bool Pop(StorageType& aStorage, T& aEntry) {
  41     if (IsEmpty(aStorage)) {
  42       return false;
  43     }
  44
  45     aEntry = aStorage.PopLastElement();
  46     return true;
  47   }
  48
  49   static void Clear(StorageType& aStorage) { aStorage.Clear(); }
  50
  51   static void Compact(StorageType& aStorage) { aStorage.Compact(); }
  52 };
  53
  54 class MOZ_CAPABILITY LockingWithMutex {
  55   mozilla::Mutex mMutex;
  56
  57  protected:
  58   LockingWithMutex() : mMutex("LockingWithMutex::mMutex") {}
  59
  60   void Lock() MOZ_CAPABILITY_ACQUIRE() { mMutex.Lock(); }
  61
  62   void Unlock() MOZ_CAPABILITY_RELEASE() { mMutex.Unlock(); }
  63
  64   class MOZ_SCOPED_CAPABILITY AutoLock {
  65     LockingWithMutex& mHost;
  66
  67    public:
  68     explicit AutoLock(LockingWithMutex& aHost) MOZ_CAPABILITY_ACQUIRE(aHost)
  69         : mHost(aHost) {
  70       mHost.Lock();
  71     }
  72
  73     ~AutoLock() MOZ_CAPABILITY_RELEASE() { mHost.Unlock(); }
  74   };
  75
  76   friend class AutoLock;
  77 };
  78
  79 class NoLocking {
  80  protected:
  81   void Lock() {}
  82
  83   void Unlock() {}
  84
  85   class AutoLock {
  86    public:
  87     explicit AutoLock(NoLocking& aHost) {}
  88
  89     ~AutoLock() = default;
  90   };
  91 };
  92
  93 template <typename T, int TCount = 256, class LockingPolicy = NoLocking,
  94           class StoragePolicy =
  95               StorageWithTArray<T, TCount % 2 ? TCount / 2 + 1 : TCount / 2> >
  96 class Queue : public LockingPolicy {
  97   typedef typename StoragePolicy::StorageType StorageType;
  98   typedef typename LockingPolicy::AutoLock AutoLock;
  99
 100   StorageType mStorage1;
 101   StorageType mStorage2;
 102
 103   StorageType* mFront;
 104   StorageType* mBack;
 105
 106  public:
 107   Queue() : mFront(&mStorage1), mBack(&mStorage2) {}
 108
 109   bool IsEmpty() {
 110     AutoLock lock(*this);
 111     return StoragePolicy::IsEmpty(*mFront) && StoragePolicy::IsEmpty(*mBack);
 112   }
 113
 114   void Push(const T& aEntry) {
 115     AutoLock lock(*this);
 116     StoragePolicy::Push(*mBack, aEntry);
 117   }
 118
 119   bool Pop(T& aEntry) {
 120     AutoLock lock(*this);
 121     if (StoragePolicy::IsEmpty(*mFront)) {
 122       StoragePolicy::Compact(*mFront);
 123       StoragePolicy::Reverse(*mBack);
 124       StorageType* tmp = mFront;
 125       mFront = mBack;
 126       mBack = tmp;
 127     }
 128     return StoragePolicy::Pop(*mFront, aEntry);
 129   }
 130
 131   void Clear() {
 132     AutoLock lock(*this);
 133     StoragePolicy::Clear(*mFront);
 134     StoragePolicy::Clear(*mBack);
 135   }
 136
 137   // XXX Do we need this?
 138   void Lock() { LockingPolicy::Lock(); }
 139
 140   // XXX Do we need this?
 141   void Unlock() { LockingPolicy::Unlock(); }
 142
 143  private:
 144   // Queue is not copyable.
 145   Queue(const Queue&);
 146   Queue& operator=(const Queue&);
 147 };
 148
 149 }  // namespace mozilla::dom::workerinternals
 150
 151 #endif /* mozilla_dom_workerinternals_Queue_h*/