On: Lock-Free Data Structures (2004)

[infogulch]

Why couldn't the last reader delete the old map?

I guess the problem with this implementation is it requires a last reader for every write. If there are always readers, the second Update will block.

  // infogulch's lock-free implementation of WRRMMap
  template <class K, class V>
  class WRRMMap {
     Map<K, V>* pMap_, * pGC_;
     unsigned readers;
  public:
     V Lookup (const K& k) {
        unsigned r
        while (r = readers, !CAS(&readers, r, r+1)); // increment readers
        V ret = (*pMap_) [k];
        while (r = readers, !CAS(&readers, r, r-1)); // decrement
        if (r == 1 && pGC_) { // last reader. garbage collect
            delete pGC_;
            pGC_ = 0;
        }
        return ret;
     }
     void Update(const K& k,
           const V& v) {
        Map<K, V>* pNew = 0, * pOld;
        do {
           pOld = pMap_;
           delete pNew;
           pNew = new Map<K, V>(*pOld);
           (*pNew) [k] = v;
        } while (!CAS(&pMap_, pOld, pNew));
        // DON'T delete pMap_;
        // wait for the GC spot to be open, set it
        while (!CAS(&pGC_, 0, pOld));
     }
  };

(Meta question: ok to put this much code here?)

[optimusclimb → infogulch]

Sample set of one answer to your meta question: You could always just use a public gist, however I hope to never see the day where people have a problem on HN with a bunch of interesting code being posted.