1 files changed, 147 insertions, 0 deletions
diff --git a/src/observers.hh b/src/observers.hh
new file mode 100644
index 0000000..526464d
--- /dev/null
+++ b/src/observers.hh
@@ -0,0 +1,147 @@
+// -*- mode: c++; c-basic-offset: 2; -*-
+
+#ifndef OBSERVERS_HH
+#define OBSERVERS_HH
+
+template<typename T>
+class Observers {
+private:
+  struct Entry {
+    T const item_;
+    unsigned int ref_;
+    bool deleted_;
+    Entry* next_;
+
+    Entry(T const& item, Entry* next)
+      : item_(item), ref_(0), deleted_(false), next_(next) {
+    }
+  };
+
+public:
+  class Iterator {
+  public:
+    Iterator(Observers* observers)
+      : observers_(observers), cur_(nullptr) {
+    }
+    Iterator(Iterator const& iter)
+      : observers_(iter.observers_), cur_(iter.cur_) {
+      if (cur_) observers_->ref(cur_);
+    }
+    ~Iterator() {
+      if (cur_) observers_->unref(cur_);
+    }
+
+    Iterator& operator=(Iterator const& iter) {
+      if (cur_) observers_->unref(cur_);
+      observers_ = iter.observers_;
+      cur_ = iter.cur_;
+      if (cur_) observers_->ref(cur_);
+      return *this;
+    }
+
+    bool operator==(Iterator const& iter) const {
+      return observers_ == iter.observers_ && cur_ == iter.cur_;
+    }
+    bool operator!=(Iterator const& iter) const {
+      return observers_ != iter.observers_ || cur_ != iter.cur_;
+    }
+
+    bool has_next() const {
+      auto n = cur_ ? cur_->next_ : observers_->first_;
+      while (n && n->deleted_) n = n->next_;
+      return n;
+    }
+
+    T const& next() {
+      if (cur_) {
+        assert(cur_->next_);
+        auto last = cur_;
+        cur_ = cur_->next_;
+        observers_->unref(last);
+      } else {
+        assert(observers_->first_);
+        cur_ = observers_->first_;
+      }
+      while (cur_ && cur_->deleted_) cur_ = cur_->next_;
+      assert(cur_);
+      observers_->ref(cur_);
+      return cur_->item_;
+    }
+
+  private:
+    Observers* observers_;
+    Entry* cur_;
+  };
+
+  Observers()
+    : first_(nullptr) {
+  }
+
+  ~Observers() {
+    auto c = first_;
+    while (c) {
+      auto n = c->next_;
+      delete c;
+      c = n;
+    }
+  }
+
+  void insert(T const& item) {
+    first_ = new Entry(item, first_);
+  }
+
+  void erase(T const& item) {
+    if (!first_) return;
+    auto c = first_;
+    if (c->item_ == item) {
+      if (c->ref_ == 0) {
+        first_ = c->next_;
+        delete c;
+      } else {
+        c->deleted_ = true;
+      }
+      return;
+    }
+    while (c->next_) {
+      if (c->next_->item_ == item) {
+        if (c->next_->ref_ == 0) {
+          auto del = c->next_;
+          c->next_ = del->next_;
+          delete del;
+        } else {
+          c->next_->deleted_ = true;
+        }
+        return;
+      }
+      c = c->next_;
+    }
+  }
+
+  Iterator notify() {
+    return Iterator(this);
+  }
+
+private:
+  void ref(Entry* entry) {
+    assert(entry->ref_ > 0 || !entry->deleted_);
+    entry->ref_++;
+  }
+
+  void unref(Entry* entry) {
+    assert(entry->ref_ > 0);
+    if (--entry->ref_ == 0 && entry->deleted_) {
+      if (entry == first_) {
+        first_ = entry->next_;
+      } else {
+        auto c = first_;
+        while (c->next_ != entry) c = c->next_;
+        c->next_ = entry->next_;
+      }
+      delete entry;
+    }
+  }
+
+  Entry* first_;
+};
+
+#endif  // OBSERVERS_HH