junction/QSBR.cpp

   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 #include <junction/QSBR.h>
  14 #include <turf/Thread.h>
  15 #include <turf/Mutex.h>
  16 #include <turf/RaceDetector.h>
  17 #include <vector>
  18
  19 namespace junction {
  20
  21 QSBR DefaultQSBR;
  22
  23 QSBR::Context QSBR::createContext() {
  24     turf::LockGuard<turf::Mutex> guard(m_mutex);
  25     TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  26     m_numContexts++;
  27     m_remaining++;
  28     TURF_ASSERT(m_numContexts < (1 << 14));
  29     sreg context = m_freeIndex;
  30     if (context >= 0) {
  31         TURF_ASSERT(context < (sreg) m_status.size());
  32         TURF_ASSERT(!m_status[context].inUse);
  33         m_freeIndex = m_status[context].nextFree;
  34         m_status[context] = Status();
  35     } else {
  36         context = m_status.size();
  37         m_status.push_back(Status());
  38     }
  39     return context;
  40 }
  41
  42 void QSBR::destroyContext(QSBR::Context context) {
  43     std::vector<Action> actions;
  44     {
  45         turf::LockGuard<turf::Mutex> guard(m_mutex);
  46         TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  47         TURF_ASSERT(context < m_status.size());
  48         if (m_status[context].inUse && !m_status[context].wasIdle) {
  49             TURF_ASSERT(m_remaining > 0);
  50             --m_remaining;
  51         }
  52         m_status[context].inUse = 0;
  53         m_status[context].nextFree = m_freeIndex;
  54         m_freeIndex = context;
  55         m_numContexts--;
  56         if (m_remaining == 0)
  57             onAllQuiescentStatesPassed(actions);
  58     }
  59     for (ureg i = 0; i < actions.size(); i++)
  60         actions[i]();
  61 }
  62
  63 void QSBR::onAllQuiescentStatesPassed(std::vector<Action>& actions) {
  64     // m_mutex must be held
  65     actions.swap(m_pendingActions);
  66     m_pendingActions.swap(m_deferredActions);
  67     m_remaining = m_numContexts;
  68     for (ureg i = 0; i < m_status.size(); i++)
  69         m_status[i].wasIdle = 0;
  70 }
  71
  72 void QSBR::update(QSBR::Context context) {
  73     std::vector<Action> actions;
  74     {
  75         turf::LockGuard<turf::Mutex> guard(m_mutex);
  76         TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  77         TURF_ASSERT(context < m_status.size());
  78         Status& status = m_status[context];
  79         TURF_ASSERT(status.inUse);
  80         if (status.wasIdle)
  81             return;
  82         status.wasIdle = 1;
  83         TURF_ASSERT(m_remaining > 0);
  84         if (--m_remaining > 0)
  85             return;
  86         onAllQuiescentStatesPassed(actions);
  87     }
  88     for (ureg i = 0; i < actions.size(); i++)
  89         actions[i]();
  90 }
  91
  92 void QSBR::flush() {
  93     // This is like saying that all contexts are quiescent,
  94     // so we can issue all actions at once.
  95     // No lock is taken.
  96     TURF_RACE_DETECT_GUARD(m_flushRaceDetector); // There should be no concurrent operations
  97     for (ureg i = 0; i < m_pendingActions.size(); i++)
  98         m_pendingActions[i]();
  99     m_pendingActions.clear();
 100     for (ureg i = 0; i < m_deferredActions.size(); i++)
 101         m_deferredActions[i]();
 102     m_deferredActions.clear();
 103     m_remaining = m_numContexts;
 104 }
 105
 106 } // namespace junction