gistfile1.hpp

template <typedef T>
class hazard_manager {

  template <unsigned Exp = 8>
  class zet {
    static const PRInt32 sCapacity = 1 << Exp;
    hazard* mStore[sCapacity];
    PRInt32 sCount;
  public:
    zet() : sCount(0) {
      for (PRInt32 i = 0; i < sCapacity; ++i)
        mStore[i] = 0;
    }
    typedef PRInt32 HzID;
    HzID insert(hazard* h) {
      PR_AtomicIncrement(&sCount);
      for (;;) {
        if (sCount >= sCapacity)
          PR_Sleep(PR_INTERVAL_NO_WAIT);
        for (PRInt32 i = 0; i < sCapacity; ++i)
          if (CAS(&mStore[i], 0, h))
            return i;
      }
    }
    hazard* remove(HzID id) {
      hazard* rv = (hazard*)PR_AtomicSet((PRInt32*)&mStore[id], 0);
      PR_AtomicDecrement(&sCount);
      return rv;
    }
    PRBool find(const hazard* const h) const {
      for (PRInt32 i = 0; i < sCapacity; ++i)
        if (mStore[i] && h == mStore[i])
          return PR_TRUE;
      return PR_FALSE;
    }
  };

  zet mHazards, mRetired;
  // May not return until a reservation is available:
  zet::HzID reserve(hazard*);
  // Always returns in constant time:
  hazard* unreserve(zet::HzID);
  // May not return until a retirement is possible.
  void retire(hazard*);

public:
  class hazard {
    T* mPtr;
    hazard_manager* const mMgr;
    reservation mRes;
  public:
    hazard(hazard_manager* mgr)
      : mMgr(mgr)
      , mRes(mgr->reserve(this))
    {}
   ~hazard() { mMgr->unreserve(mRes); }
    void retire() { mMgr->retire(this); }
    hazard& operator=(T* tp) { mPtr = tp; return *this; }
    operator T*() { return mPtr; }
  private:
    hazard();
    static void* operator new(size_t) CPP_THROW_NEW;
    static void  operator delete(void*);
  };
};

template <typedef T>
class Queue : hazard_manager<Cell> {
public:
  // ...
  bool dequeue(const T& t)
  {
    hazard p(this), n(this);
    do
    {
      p = head;
      n = p->next;
      if (!n)
        return false;
    } while (CAS(&head, p, n));
    t = n->value;
    p.retire();
    return true;
  }
};