junction/QSBR.h

   1 /*------------------------------------------------------------------------
   2   Junction: Concurrent data structures in C++
   3   Copyright (c) 2016 Jeff Preshing
   4
   5   Distributed under the Simplified BSD License.
   6   Original location: https://github.com/preshing/junction
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the LICENSE file for more information.
  11 ------------------------------------------------------------------------*/
  12
  13 #ifndef JUNCTION_QSBR_H
  14 #define JUNCTION_QSBR_H
  15
  16 #include <junction/Core.h>
  17 #include <turf/Mutex.h>
  18 #include <turf/RaceDetector.h>
  19 #include <vector>
  20 #include <string.h>
  21
  22 namespace junction {
  23
  24 class QSBR {
  25 private:
  26     struct Action {
  27         void (*func)(void*);
  28         uptr param[4]; // Size limit found experimentally. Verified by assert below.
  29
  30         Action(void (*f)(void*), void* p, ureg paramSize) : func(f) {
  31             TURF_ASSERT(paramSize <= sizeof(param)); // Verify size limit.
  32             memcpy(&param, p, paramSize);
  33         }
  34         void operator()() {
  35             func(&param);
  36         }
  37     };
  38
  39     struct Status {
  40         u16 inUse : 1;
  41         u16 wasIdle : 1;
  42         s16 nextFree : 14;
  43
  44         Status() : inUse(1), wasIdle(0), nextFree(0) {
  45         }
  46     };
  47
  48     turf::Mutex m_mutex;
  49     TURF_DEFINE_RACE_DETECTOR(m_flushRaceDetector)
  50     std::vector<Status> m_status;
  51     sreg m_freeIndex;
  52     sreg m_numContexts;
  53     sreg m_remaining;
  54     std::vector<Action> m_deferredActions;
  55     std::vector<Action> m_pendingActions;
  56
  57     void onAllQuiescentStatesPassed(std::vector<Action>& callbacks);
  58
  59 public:
  60     typedef u16 Context;
  61
  62     QSBR() : m_freeIndex(-1), m_numContexts(0), m_remaining(0) {
  63     }
  64     Context createContext();
  65     void destroyContext(Context context);
  66
  67     template <class T>
  68     void enqueue(void (T::*pmf)(), T* target) {
  69         struct Closure {
  70             void (T::*pmf)();
  71             T* target;
  72             static void thunk(void* param) {
  73                 Closure* self = (Closure*) param;
  74                 TURF_CALL_MEMBER (*self->target, self->pmf)();
  75             }
  76         };
  77         Closure closure = {pmf, target};
  78         turf::LockGuard<turf::Mutex> guard(m_mutex);
  79         TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  80         m_deferredActions.push_back(Action(Closure::thunk, &closure, sizeof(closure)));
  81     }
  82
  83     void update(Context context);
  84     void flush();
  85 };
  86
  87 extern QSBR DefaultQSBR;
  88
  89 } // junction
  90
  91 #endif // JUNCTION_QSBR_H