persistance.h

Go to the documentation of this file.

#ifndef PERSISTANCE_H
#define PERSISTANCE_H


#ifndef ENABLE_PERSISTANCE

#  include "persistance-noop.h"

#else

#include <vector>
#include <iterator>
#include "hash_set.h"
#include "hash_map.h"
#include "iterator_wrapper.h"
#include "assert.h"
#include <limits>

class PersistantObject;

namespace hashers {
  template <> struct hash<PersistantObject*> {
    unsigned long operator() (const PersistantObject* obj) const {
      return (unsigned long)(obj);
    }
  };
  template <> struct hash<const PersistantObject*> {
    unsigned long operator() (const PersistantObject* obj) const {
      return (unsigned long)(obj);
    }
  };
};

class PersistantStore {
    friend class PersistantObject;
  public:
    PersistantStore ();
    int add_checkpoint(); /* return the new view number */
    void set_view(int);
    void set_view_current();
    void undo();
    void commit();

    int get_time() const;
    bool viewing_current() const;
    bool logging() const;
    bool logging_after_pop() const;

  private:
    void notify_access(PersistantObject* data);

    void notify_born(PersistantObject* data);

    void notify_died(PersistantObject* data);

    typedef hashers::hash_set<PersistantObject*> ModifySet;
    std::vector<ModifySet> modifications_;
    std::vector<ModifySet> births_;
    ModifySet died_in_pop_; /* don't commit/undo these, we just deleted them! */

    int current_view_;

    /* True if we are currently popping a checkpoint off. */
    bool popping_;

    /* illegal */
    PersistantStore(const PersistantStore&);
    PersistantStore& operator = (const PersistantStore&);
};

class PersistantObject {
  public:
    /* Save a bit on storage. */
    PersistantStore& get_store() const {
      return store_;
    }

  protected:
    friend class PersistantStore;

    PersistantObject(PersistantStore& store) : store_(store) {
      store_.notify_born(this);
    }

    virtual ~PersistantObject() {
      store_.notify_died(this);
    }

    virtual void undo() = 0;

    virtual void commit() = 0;

    virtual void preincarnate() = 0;

    void notify_access() { store_.notify_access(this); }

    int current_view() const { return store_.current_view_; }

    int logging() const { return store_.logging(); }

    int logging_after_pop() const { return store_.logging_after_pop(); }

  private:
    PersistantStore& store_;

    /* illegal */
    PersistantObject(const PersistantObject&);
    PersistantObject& operator = (const PersistantObject&);
};

template <class datum_type, bool copy_on_push> class StackPersistantObject
: public PersistantObject
{
  protected:
    struct timed_entry {
      int time;
      datum_type datum;
      timed_entry(int t, const datum_type& d) :
        time(t), datum(d) { }
    };

    StackPersistantObject(PersistantStore& store,
        const datum_type& initial)
      : PersistantObject(store)
      {
        data_.push_back(timed_entry(store.get_time(), initial));
      }
    virtual ~StackPersistantObject() { }

    datum_type& get_handle() {
      int time = current_view();
      if (data_.back().time != time) {
    /* Don't notify unless we're pushing a new timestep on:
       we either have notified already, or we were allocated
       during this timestep. */
    notify_access();
        assert(data_.back().time < time);
        if(copy_on_push) {
          data_.push_back(timed_entry(time, data_.back().datum));
        } else {
          data_.push_back(timed_entry(time, datum_type()));
        }
      }
      return data_.back().datum;
    }

    int get_current_index() const {
      int time = current_view();
      for (int idx = data_.size() - 1; idx >= 0; idx--) {
        if (data_[idx].time <= time) {
          return idx;
        }
      }
      assert(0);
      return -1;
    }

    virtual void merge_times(datum_type& older, const datum_type& newer) = 0;

  private:
    virtual void commit() {
      assert(data_.size() >= 2);
      timed_entry& newer = data_[data_.size() - 1];
      timed_entry& older = data_[data_.size() - 2];
      int timestep_after_commit = newer.time - 1;
      if (older.time == timestep_after_commit) {
    merge_times(older.datum, newer.datum);
    data_.pop_back();
      } else {
    newer.time = timestep_after_commit;
      }
    }

    virtual void preincarnate() {
      /* we can only be preincarnated if we're at the first checkpoint */
      assert(data_.size() == 1);
      data_[0].time--;
    }

  protected:
    std::vector<timed_entry> data_;

  private:
    /* illegal */
    StackPersistantObject(const StackPersistantObject&);
    StackPersistantObject& operator = (const StackPersistantObject&);
};


template <class Datum> class PersistantData
: public StackPersistantObject<Datum, true> {
  public:
    PersistantData (PersistantStore& store, const Datum& initial)
      : StackPersistantObject<Datum, true>(store, initial)
      { }
    virtual ~PersistantData() { }

    const Datum& operator *() const {
      return this->data_[this->get_current_index()].datum;
    }

    Datum& access() {
      return this->get_handle();
    }

  protected:
    virtual void undo() {
      this->data_.pop_back();
    }
    virtual void merge_times(Datum& older, const Datum& newer) {
      /* just lose the old value */
      older = newer;
    }

  private:
    /* illegal */
    PersistantData(const PersistantData&);
    PersistantData& operator = (const PersistantData&);
};

template <class Datum, int n> class PersistantArray {
  private:
    PersistantData<Datum> *data_[n];

  public:
    /* Create the array using the default element.  Requires the
       datum to have a no-arg constructor. */
    PersistantArray(PersistantStore& store) {
      for(int i = 0; i < n; i++) {
        data_[i] = new PersistantData<Datum>(store, Datum());
      }
    }

    /* Create the array using a given initial element. */
    PersistantArray(PersistantStore& store, const Datum& initial) {
      for(int i = 0; i < n; i++) {
        data_[i] = new PersistantData<Datum>(store, initial);
      }
    }

    ~PersistantArray() {
      for(int i = 0; i < n; i++) {
        delete data_[i];
      }
    }

    const Datum& operator[] (int i) const {
      return **data_[i];
    }
    Datum& access (int i) {
      return data_[i]->access();
    }

    class iterator : public Tumble::iterators::dedereferencer<PersistantData<Datum>**, Datum, const Datum&> {
      private:
        typedef Tumble::iterators::dedereferencer<PersistantData<Datum>**, Datum, const Datum&> super;
      public:
        iterator() { }
        iterator(PersistantData<Datum>** it) : super(it) { }
        iterator(PersistantArray& array) : super(array.begin()) { }
    };
    class const_iterator : public Tumble::iterators::dedereferencer<const PersistantData<Datum>* const *, const Datum> {
      private:
        typedef Tumble::iterators::dedereferencer<const PersistantData<Datum>*const *, const Datum> super;
      public:
        const_iterator() { }
        const_iterator(const PersistantData<Datum>* const * it) : super(it) { }
        const_iterator(const PersistantArray& array) : super(array.begin()) { }
    };

    iterator begin() { return data_; }
    const_iterator begin() const { return data_; }
    iterator end() { return data_ + n; }
    const_iterator end() const { return data_ + n; }

    iterator operator+ (int i) {
      assert(i <= n);
      return iterator(data_ + i);
    }
    const_iterator operator+ (int i) const {
      assert(i <= n);
      return const_iterator(data_ + i);
    }

  private:
    /* illegal */
    PersistantArray(const PersistantArray&);
    PersistantArray& operator = (const PersistantArray&);
};

template <class Datum> class PersistantVector {
  public:
    /* Defined in the order on the SGI STL page for vector */
    typedef typename std::vector<Datum>::value_type value_type;
    typedef typename std::vector<Datum>::pointer pointer;
    typedef typename std::vector<Datum>::reference reference;
    typedef typename std::vector<Datum>::const_reference const_reference;
    typedef typename std::vector<Datum>::size_type size_type;
    typedef typename std::vector<Datum>::difference_type difference_type;

    typedef Tumble::iterators::dedereferencer<PersistantData<Datum>**, value_type, const_reference> iterator;
    typedef Tumble::iterators::dedereferencer<const PersistantData<Datum>*const *, value_type, const_reference> const_iterator;

    /* TODO: reverse_iterator, const_reverse_iterator */

    iterator begin() { return iterator(data_); }
    iterator end() { return iterator(data_ + size()); }

    const_iterator begin() const { return const_iterator(data_); }
    const_iterator end() const { return const_iterator(data_ + size()); }

    /* TODO: rbegin, rend */

    size_type size() const { return *size_; }
    size_type max_size() const { return std::numeric_limits<int>::max(); }
    size_type capacity() const { return allocated_size_; /* not really... */ }
    bool empty() const { return size() == 0; }

    /* reference operator[](size_type i)
       - don't allow accidentally allocating when trying to just read */
    reference access(size_type i) {
      assert(i < size()); /* would fail if we'd never allocated */
      if (data_[i] == NULL) {
        data_[i] = new PersistantData<value_type>(get_store(), Datum());
      }
      return data_[i]->access();
    }

    const_reference operator[](size_type i) const {
      assert(i < size());
      return **(data_[i]);
    }

    PersistantVector(PersistantStore& store) :
      size_(store, 0), data_(NULL), allocated_size_(0) { }

    PersistantVector(PersistantStore& store, size_type n) :
      size_(store, 0), data_(NULL), allocated_size_(0) {
        reserve(n);
        for(size_type i = 0; i < n; i++) {
          data_[i] = new PersistantData<Datum>(get_store(), Datum());
        }
        size_.access() = n;
      }

    PersistantVector(PersistantStore& store, size_type n, const Datum& t) :
      size_(store, 0), data_(NULL), allocated_size_(0) {
        reserve(n);
        for(size_type i = 0; i < n; i++) {
          data_[i] = new PersistantData<Datum>(get_store(), t);
        }
        size_.access() = n;
      }

    template <class InputIterator>
    PersistantVector(PersistantStore& store, InputIterator begin,
                     InputIterator end) :
      size_(store, 0), data_(NULL), allocated_size_(0) {
        for( ; begin != end; ++begin) {
          push_back(*begin);
        }
      }

    ~PersistantVector() {
      for(size_type i = 0; i < allocated_size_; i++) {
        delete data_[i];
      }
      delete[] data_;
    }

    void reserve(size_type sz) {
      if (sz <= allocated_size_) {
        return;
      }
      size_type oldalloc = allocated_size_;
      PersistantData<value_type> **olddata = data_;

      allocated_size_ = sz;
      data_ = new PersistantData<value_type>* [sz];
      for(size_type i = 0; i < oldalloc; i++) {
        data_[i] = olddata[i];
      }
      for(size_type i = oldalloc; i < sz; i++) {
        data_[i] = NULL;
      }
      delete[] olddata;
    }

    reference access_front() {
      return access(0);
    }
    const_reference front() const {
      return operator[] (0);
    }

    reference access_back() {
      return access(size() - 1);
    }

    const_reference back() const {
      return operator[] (size() - 1);
    }

    void push_back(const Datum& d) {
      size_type sz = size();
      ensure_capacity(sz + 1);
      if (data_[sz] == NULL) {
        data_[sz] = new PersistantData<value_type> (get_store(), d);
      } else {
        data_[sz]->access() = d;
      }
      ++size_.access();
    }

    void pop_back() {
      --size_.access();
    }

    iterator insert(iterator pos, const Datum& x) {
      if (pos == end()) {
        push_back(x);
      }
      else {
        difference_type index = pos - begin();
        assert(index >= 0); assert(index < size());
        push_back(back());
        for(size_type i = size() - 1; i > index; i--) {
          access(i) = operator[](i - 1);
        }
        access(index) = x;
      }
    }

    iterator erase(iterator pos) {
      difference_type index = pos - begin();
      assert(index >= 0); assert(size_type(index) < size());
      size_type sz = size();
      for(size_type i = index; i < sz - 1; i++) {
        access(i) = operator[](i + 1);
      }
      pop_back();
    }

    void clear() {
      size_.access() = 0;
    }

    PersistantStore& get_store() const {
      return size_.get_store();
    }

  private:
    void ensure_capacity(size_type sz) {
      if (sz > allocated_size_) {
        if (allocated_size_ == 0) {
          reserve(sz);
        } else {
          reserve((allocated_size_ * 2 > sz) ? (allocated_size_ * 2) : sz);
        }
      }
    }

  private:
    /* illegal */
    PersistantVector(const PersistantVector&);
    PersistantVector& operator=(const PersistantVector&);

  private:
    /* Data members */
    PersistantData<size_type> size_;
    PersistantData<value_type> **data_;
    size_type allocated_size_;
};

template <class Datum>
bool operator==(const PersistantVector<Datum>& v1,
                const PersistantVector<Datum>& v2) {
  if (v1.size() != v2.size()) {
    return false;
  }
  typename PersistantVector<Datum>::const_iterator it1 = v1.begin();
  typename PersistantVector<Datum>::const_iterator it2 = v2.begin();
  while(it1 != v1.end()) {
    if (*it1 != *it2) {
      return false;
    }
    ++it1;
    ++it2;
  }
  return true;
}

template <class Datum>
bool operator< (const PersistantVector<Datum>& v1,
                const PersistantVector<Datum>& v2) {
  typename PersistantVector<Datum>::const_iterator it1 = v1.begin();
  typename PersistantVector<Datum>::const_iterator it2 = v2.begin();
  while(it1 != v1.end()) {
    if (it2 == v2.end()) {
      return true; /* v2 is longer, so it's lexicographically later */
    }
    if (*it1 < *it2) {
      return true;
    } else if (*it2 < *it1) {
      return false;
    }
    ++it1;
    ++it2;
  }
  if (it2 == v2.end()) {
    /* same length, so we're == */
    return false;
  } else {
    /* v2 is longer, so v1 is < */
    return true;
  }
}


/* really a member of PersistantMemoryPool */
template <class Datum> struct PMP_pair {
  struct PMP_hash {
    unsigned long operator() (const Datum& d) const {
      return (unsigned long)(d);
    }
  };
  hashers::hash_set<Datum, PMP_hash> allocated, deleted;
  typedef typename hashers::hash_set<Datum, PMP_hash>::iterator iterator;
};

template <class Datum> class PersistantMemoryPool
: public StackPersistantObject<PMP_pair<Datum*>, false> {
  public:
    PersistantMemoryPool(PersistantStore& store) :
      StackPersistantObject<PMP_pair<Datum*>, false>(store,PMP_pair<Datum*>())
    { }

    virtual ~PersistantMemoryPool() {
      /* go through all allocated items, delete them. */
      for(int i = this->data_.size() - 1; i >= 0; i--) {
        typename PMP_pair<Datum*>::iterator it;
        for(it = this->data_[i].datum.allocated.begin();
            it != this->data_[i].datum.allocated.end(); ++it) {
          dofinaldelete(*it);
        }
      }
      /* the allocated/deleted lists will be nuked automatically */
    }

    void mark_allocated(Datum *key) {
      /* whether or not we're logging, we need to keep track of 'key' */
      PMP_pair<Datum*>& handle = this->get_handle();
      handle.allocated.insert(key);
      assert(handle.deleted.count(key) == 0);
    }

    void mark_deleted(Datum *key) {
      /* whether or not we're logging, we need to keep track of 'key' */
      PMP_pair<Datum*>& handle = this->get_handle();
      if (handle.allocated.count(key) != 0) {
        /* delete/allocate in the same checkpoint: actually delete it,
           since now we will never undo the deletion. */
        handle.allocated.erase(key);
        dodelete(key);
      } else {
        assert(this->logging());
        handle.deleted.insert(key);
      }
    }

  protected:
    virtual void undo() {
      assert(this->logging());
      /* Allocated entries must be deleted; deleted entries
       * simply get not deleted. */
      typename PMP_pair<Datum*>::iterator it;
      for(it = this->data_.back().datum.allocated.begin();
          it != this->data_.back().datum.allocated.end(); ++it) {
        dodelete(*it);
      }
      this->data_.pop_back();
    }

    virtual void merge_times(PMP_pair<Datum*>& older,
                 const PMP_pair<Datum*>& newer) {
      older.allocated.insert(newer.allocated.begin(), newer.allocated.end());
      for (typename PMP_pair<Datum*>::iterator it = newer.deleted.begin();
      it != newer.deleted.end(); ++it) {
    if (older.allocated.erase(*it)) {
      /* allocated and deleted in the same timestep: just delete it */
      dodelete(*it);
    } else {
      /* allocated in a prior timestep; mark it deleted */
      assert(this->logging_after_pop()); // there must be a prior time
      older.deleted.insert(*it);
    }
      }
    }

    virtual void dodelete(Datum *d) {
      delete d;
    }

    virtual void dofinaldelete(Datum *d) {
      delete d;
    }

  private:
    /* illegal */
    PersistantMemoryPool(const PersistantMemoryPool&);
    PersistantMemoryPool& operator = (const PersistantMemoryPool&);
};

template <class Value>
class PersistantList {
  private:
    struct node {
      PersistantData<node*> prev_;
      PersistantData<node*> next_;
      PersistantData<Value> value_;
      node(PersistantStore& store, node *prev, node *next, const Value& initial)
    : prev_(store, prev), next_(store, next), value_(store, initial)
        { }
    };

    PersistantData<int> size_;
    PersistantData<node*> first_;
    PersistantData<node*> last_;
    PersistantMemoryPool<node> pool_;

    node *do_insert(node *prev, node *next, const Value& v) {
      node *newnode = new node(get_store(), prev, next, v);
      pool_.mark_allocated(newnode);
      size_.access()++;

      if (prev) {
    prev->next_.access() = newnode;
      } else {
    first_.access() = newnode;
      }
      if (next) {
    next->prev_.access() = newnode;
      } else {
    last_.access() = newnode;
      }
      return newnode;
    }

  public:
    struct const_iterator {
      friend class PersistantList;
      protected:
        node *n_;

        const_iterator(node *n) : n_(n) { }
      public:
        const_iterator() { }

        const Value& operator*() const {
          return *n_->value_;
        }
        const Value *operator->() const {
          return &operator*();
        }
        Value& access() {
          return n_->value_.access();
        }

        const_iterator& operator++() {
          n_ = *n_->next_; return *this;
        }
        const_iterator& operator--() {
          n_ = *n_->prev_; return *this;
        }
        bool operator== (const const_iterator& other) const {
          return n_ == other.n_;
        }
        bool operator!= (const const_iterator& other) const {
          return n_ != other.n_;
        }

        unsigned long hashcode() const {
          return (unsigned long) n_;
        }

        /* stl stuff */
        typedef ptrdiff_t                     difference_type;
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef Value                         value_type;
        typedef const Value   &               reference;
        typedef const Value   *               pointer;
    };
    
    struct iterator : public const_iterator {
      friend class PersistantList;
      private:
        iterator(node *n) : const_iterator(n) { }
      public:
        iterator() { }

        Value& access() const {
          return const_iterator::n_->value_.access();
        }

        iterator& operator++() {
          const_iterator::operator++();
          return *this;
        }
        iterator& operator--() {
          const_iterator::operator--();
          return *this;
        }
    };

    PersistantList(PersistantStore& store)
      : size_(store, 0), first_(store, NULL), last_(store, NULL), pool_(store)
      { }

    iterator begin() const {
      return iterator(*first_);
    }
    iterator end() const {
      return iterator(NULL);
    }
    const Value& back() const {
      return *iterator(*last_);
    }
    const Value& first() const {
      return *iterator(*first_);
    }
    int size() const {
      return *size_;
    }
    bool empty() const {
      return size() == 0;
    }

    iterator insert(iterator it, const Value& v) {
      node *prev = const_cast<node*>(*it.n_->prev_);
      node *next = const_cast<node*>(*it.n_->next_);
      return iterator(do_insert(prev, next, v));
    }
    iterator push_back(const Value& v) {
      return iterator(do_insert(const_cast<node*>(*last_), NULL, v));
    }
    iterator push_front(const Value& v) {
      return iterator(do_insert(NULL, const_cast<node*>(*first_), v));
    }

    iterator erase(iterator it) {
      node *prev = const_cast<node*>(*it.n_->prev_);
      node *next = const_cast<node*>(*it.n_->next_);
      if (prev) {
    prev->next_.access() = next;
      } else {
    first_.access() = next;
      }
      if (next) {
    next->prev_.access() = prev;
      } else {
    last_.access() = prev;
      }
      size_.access()--;
      pool_.mark_deleted(it.n_);
      return iterator(next);
    }
    void pop_back() {
      return erase(iterator(*last_));
    }
    void pop_front() {
      return erase(begin());
    }

    PersistantStore& get_store() const { return size_.get_store(); }
};

template <class Key, class HashFcn = hashers::hash<Key>,
      class EqualKey = std::equal_to<Key> >
class PersistantHashSet {
  private:
    struct map_data {
      private:
        PersistantData< bool > valid_;
        Key data_;
        PersistantData< map_data* > next_;
        PersistantData< map_data* > prev_;

      public:
        map_data(PersistantStore& store, const Key& dat)
          : valid_(store, true)
          , data_(dat)
          , next_(store, NULL)
          , prev_(store, NULL) {
          }

        /* unlink from the iterate list */
        void unlink() {
          map_data *next = get_next();
          map_data *prev = get_prev();
          if (next) {
            set_next(NULL);  // otherwise, it's already NULL
            next->set_prev(prev);
          }
          if (prev) {
            set_prev(NULL);  // otherwise, it's already NULL
            prev->set_next(next);
          }
        }

        bool has_data() const {
          return *valid_;
        }

        void set_valid(bool valid = true) {
          valid_.access() = valid;
        }

        const Key& get_data() const {
          assert(has_data());
          return data_;
        }
        const Key& unconditional_get_data() const {
          return data_;
        }

        map_data *get_next() const {
          return *next_;
        }

        map_data *get_prev() const {
          return *prev_;
        }

        void set_next(map_data *next) {
          next_.access() = next;
        }

        void set_prev(map_data *prev) {
          prev_.access() = prev;
        }
    };

    struct deref_hasher {
      HashFcn hasher_;
      int operator()(const Key *key) const {
    return hasher_(*key);
      }
    };

    struct deref_equal {
      EqualKey equal_;
      bool operator()(const Key *key1, const Key *key2) const {
    return equal_(*key1, *key2);
      }
    };

    typedef hashers::hash_map<const Key*, map_data*, deref_hasher, deref_equal> map_type;

    struct Reaper : public PersistantMemoryPool<map_data> {
      public:
    Reaper(PersistantStore& store, map_type& hashset)
      : PersistantMemoryPool<map_data>(store), hashset_(hashset) { }

      protected:
        /* Just remove from the hash; all the other stuff will magically
           get undone. */
    virtual void dodelete(map_data *data) {
      bool diderase;
          /* get the key out of the map_data, whether or not it's valid */
          diderase = hashset_.erase(& data->unconditional_get_data());
          assert(diderase);
      delete data;
    }
        /* on final deletion, just delete -- the hashset is about
           to go, too */

      private:
    map_type& hashset_;
    };

    map_data *internal_find(const Key& key) const {
      typename map_type::const_iterator it = datamap_.find(&key);
      if(it == datamap_.end()) {
        return NULL;
      } else {
        return (*it).second;
      }
    }

  public:
    class iterator {
      private:
    friend class PersistantHashSet;
    iterator(map_data *data) : datap(data) { }
      public:
    iterator() { datap = NULL; }

    const Key& operator *() const {
      assert(datap->has_data());
      return datap->get_data();
    }
        const Key *operator->() const {
          return &operator*();
        }

    iterator& operator++() {
      assert(datap);
      datap = datap->get_next();
      return *this;
    }
    bool operator == (iterator other) const {
      return datap == other.datap;
    }
    bool operator != (iterator other) const {
      return ! (other == *this);
    }

        /* stl stuff */
        typedef ptrdiff_t                     difference_type;
        typedef std::forward_iterator_tag     iterator_category;
        typedef Key                           value_type;
        typedef const Key     &               reference;
        typedef const Key     *               pointer;

      private:
    map_data *datap;
    };
    /* all our iterators are const */
    typedef iterator const_iterator;

    PersistantHashSet(PersistantStore& store)
      : size_(store, 0), first_(store, NULL), reaper_(store, datamap_)
      { }

    iterator find(const Key& key) const {
      map_data *datap = internal_find(key);

      if(!datap || !datap->has_data()) {
        return end();
      } else {
        return iterator(datap);
      }
    }

    size_t count(const Key& key) const {
      return (find(key) == end()) ? 0 : 1;
    }

    bool operator[] (const Key& key) const {
      return find(key) != end();
    }

    int size() const {
      return *size_;
    }

    bool empty() const {
      return size() == 0;
    }

    std::pair<iterator,bool> insert(const Key& key) {
      assert(get_store().viewing_current());

      bool didinsert;
      map_data *founddata;

      founddata = internal_find(key);
      if (founddata == NULL) {
        founddata = new map_data(get_store(), key);
    reaper_.mark_allocated(founddata); /* avoid leaking on undo */
        datamap_.insert(std::make_pair(&(founddata->get_data()), founddata));
        push_first(founddata);
        didinsert = true;
      } else if (!founddata->has_data()) {
        founddata->set_valid();
        push_first(founddata);
        didinsert = true;
      } else {
        didinsert = false;
      }
      return std::make_pair(iterator(founddata), didinsert);
    }

    bool erase(iterator it) {
      assert(get_store().viewing_current());
      if(it == end()) {
        return false;
      }
      /* unlink the current data */
      map_data *datap = it.datap;
      assert(datap->has_data());
      unlink_data(datap);
      datap->set_valid(false);
      reaper_.mark_deleted(datap); /* possibly deletes it immediately */
      return true;
    }

    bool erase(const Key& key) {
      return erase(find(key));
    }

    void clear() {
      while (!empty()) {
        erase(begin());
      }
    }

    iterator begin() const {
      return iterator(*first_);
    }
    iterator end() const {
      return iterator(NULL);
    }

    PersistantStore& get_store() const { return size_.get_store(); }

  private:
    void push_first(map_data *newfirst) {
      map_data *oldfirst = *first_;
      assert(oldfirst == NULL || oldfirst->get_prev() == NULL);
      assert(newfirst->get_prev() == NULL);
      assert(newfirst->get_next() == NULL);
      if (oldfirst) {
    oldfirst->set_prev(newfirst);
    newfirst->set_next(oldfirst); /* otherwise, it's already NULL */
      }
      first_.access() = newfirst;
      size_.access()++;
    }

    void unlink_data(map_data *tounlink) {
      if (tounlink == begin().datap) {
        first_.access() = tounlink->get_next();
      }
      tounlink->unlink();
      if (tounlink->has_data()) {
    size_.access()--;
      }
    }

    map_type datamap_;
    PersistantData<int> size_;
    PersistantData<map_data*> first_;
    Reaper reaper_;

  private:
    /* illegal */
    PersistantHashSet(const PersistantHashSet&);
    PersistantHashSet& operator = (const PersistantHashSet&);
};

template <class Key, class Value, class HashFcn = hashers::hash<Key>,
      class EqualKey = std::equal_to<Key> >
class PersistantHashMap {
  public:
    class iterator;
    friend class iterator;

  private:
    typedef PersistantData<Value> value_type;

    struct hasher {
      HashFcn fn;
      unsigned long operator()(const std::pair<Key,value_type*>& p) const {
        return fn(p.first);
      }
    };
    struct equaler {
      EqualKey fn;
      unsigned long operator()(const std::pair<Key,value_type*>& p1,
                               const std::pair<Key,value_type*>& p2) const {
        return fn(p1.first, p2.first);
      }
    };

    static std::pair<Key, value_type*> search_key(const Key& k) {
      return std::make_pair(k, (value_type*)NULL);
    }

    struct PHM_pair {
      friend class iterator;
      const Key& first;
      const Value& second;
      private:
      PHM_pair(const Key& k, value_type *vptr)
        : first(k), second(**vptr) { }
    };

    typedef PersistantHashSet< std::pair<Key, value_type*>,
        hasher, equaler> set_type;

    /* data members */
    set_type set_;
    PersistantMemoryPool<value_type> pool_;

  public:
    class iterator {
      friend class PersistantHashMap;
      private:
    typename set_type::iterator it_;
    iterator(typename set_type::iterator it) : it_(it) { }
      public:
    iterator() { }
    PHM_pair operator*() const {
      return PHM_pair((*it_).first, (*it_).second);
    }
    iterator& operator++() {
      ++it_;
      return *this;
    }
    bool operator==(const iterator& other) const {
      return it_ == other.it_;
    }
    bool operator!=(const iterator& other) const {
      return it_ != other.it_;
    }

        /* stl stuff */
        typedef ptrdiff_t                     difference_type;
        typedef std::forward_iterator_tag     iterator_category;
        typedef PHM_pair                      value_type;
        typedef const PHM_pair&               reference;
        typedef const PHM_pair*               pointer;
    };
    /* all our iterators are const */
    typedef iterator const_iterator;


    PersistantHashMap(PersistantStore& store)
      : set_(store), pool_(store)
      { }

    int size() const {
      return set_.size();
    }
    bool empty() const {
      return size() == 0;
    }
    iterator begin() const {
      return iterator(set_.begin());
    }
    iterator end() const {
      return iterator(set_.end());
    }
    iterator find(const Key& k) const {
      return iterator(set_.find(search_key(k)));
    }
    int count(const Key& k) const {
      if (find(k) == end()) {
        return 0;
      } else {
        return 1;
      }
    }

    std::pair<iterator,bool> insert(const std::pair<Key,Value>& v) {
      return insert(v.first, v.second);
    }

    std::pair<iterator,bool> insert(const Key& k, const Value& v) {
      std::pair<typename set_type::iterator,bool> p =
    set_.insert(search_key(k));
      typename set_type::iterator it = p.first;

      // cast away const so we can muck with the value
      value_type*& storedval = const_cast<value_type*&>( (*it).second );
      if (storedval) {
    storedval->access() = v;
    return std::make_pair(iterator(it), p.second);
      } else {
    storedval = new PersistantData<Value>(get_store(), v);
    pool_.mark_allocated(storedval);
    return std::make_pair(iterator(it), true);
      }
    }

    bool erase(iterator it) {
      return set_.erase(it.it_);
    }
    bool erase(const Key& k) {
      return erase(find(k));
    }

    /* This is only allowed when we are allowed to modify, and
     * is inefficient and ugly.  Use find() and insert() instead. */
    Value& operator[] (const Key& k) {
      iterator found = find(k);
      if (found == end()) {
        found = insert(k, Value()).first;
      }
      // cast away const so we can call access()
      value_type *storedval = const_cast<value_type*>((*found.it_).second);
      return storedval->access();
    }

    PersistantStore& get_store() const { return set_.get_store(); }

  private:
    /* illegal */
    PersistantHashMap(const PersistantHashMap&);
    PersistantHashMap& operator = (const PersistantHashMap&);
};
#endif /* ENABLE_PERSISTANCE */

#endif /* PERSISTANCE_H */

---