Add Observers, useful class for notifying listeners

4 files changed, 256 insertions, 1 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
diff --git a/test/Makefile.am b/test/Makefile.am
index c23bd9f..4daf511 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -2,7 +2,8 @@ MAINTAINERCLEANFILES = Makefile.in
 
 AM_CXXFLAGS = @DEFINES@
 
-TESTS = test-url test-http test-args test-xdg test-paths test-strings
+TESTS = test-url test-http test-args test-xdg test-paths test-strings \
+        test-observers
 
 check_PROGRAMS = $(TESTS)
 
@@ -23,3 +24,5 @@ test_strings_LDADD = $(top_builddir)/src/libtp.a
 
 test_paths_SOURCES = test-paths.cc
 test_paths_LDADD = $(top_builddir)/src/libtp.a
+
+test_observers_SOURCES = test-observers.cc
diff --git a/test/test-observers.cc b/test/test-observers.cc
new file mode 100644
index 0000000..be1418d
--- /dev/null
+++ b/test/test-observers.cc
@@ -0,0 +1,94 @@
+// -*- mode: c++; c-basic-offset: 2; -*-
+
+#include "common.hh"
+#include "test.hh"
+
+#include "observers.hh"
+
+namespace {
+
+bool test_sanity() {
+  Observers<int> obs;
+  ASSERT_EQ(false, obs.notify().has_next());
+  obs.insert(1);
+  auto it = obs.notify();
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(1, it.next());
+  ASSERT_EQ(false, it.has_next());
+  obs.erase(2);
+  it = obs.notify();
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(1, it.next());
+  obs.erase(1);
+  ASSERT_EQ(false, obs.notify().has_next());
+  return true;
+}
+
+bool test_insert() {
+  Observers<int> obs;
+  auto it = obs.notify();
+  ASSERT_EQ(false, it.has_next());
+  obs.insert(1);
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(1, it.next());
+  obs.insert(2);
+  ASSERT_EQ(false, it.has_next());
+  it = obs.notify();
+  ASSERT_EQ(true, it.has_next());
+  int other;
+  switch (it.next()) {
+  case 1:
+    other = 2;
+    break;
+  case 2:
+    other = 1;
+    break;
+  default:
+    ASSERT_TRUE(false);
+  }
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(other, it.next());
+  return true;
+}
+
+bool test_erase() {
+  Observers<int> obs;
+  auto it = obs.notify();
+  ASSERT_EQ(false, it.has_next());
+  obs.insert(1);
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(1, it.next());
+  ASSERT_EQ(false, it.has_next());
+  obs.erase(1);
+  auto it2 = obs.notify();
+  ASSERT_EQ(false, it2.has_next());
+  it = it2;
+
+  obs.insert(4);
+  obs.insert(3);
+  obs.insert(2);
+  it = obs.notify();
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(2, it.next());
+  obs.erase(2);
+  it2 = obs.notify();
+  ASSERT_EQ(true, it2.has_next());
+  ASSERT_EQ(3, it2.next());
+  obs.erase(3);
+  ASSERT_EQ(true, it.has_next());
+  ASSERT_EQ(4, it.next());
+  ASSERT_EQ(true, it2.has_next());
+  ASSERT_EQ(4, it2.next());
+
+  return true;
+}
+
+}  // namespace
+
+int main(void) {
+  BEFORE;
+  RUN(test_sanity());
+  RUN(test_insert());
+  RUN(test_erase());
+  AFTER;
+}
diff --git a/test/test.hh b/test/test.hh
index 8d1f661..153a5b3 100644
--- a/test/test.hh
+++ b/test/test.hh
@@ -34,6 +34,17 @@
     }                                                                   \
   } while (false)
 
+#define ASSERT_TRUE(actual)                                             \
+  do {                                                                  \
+    auto a_ = (actual);                                                 \
+    if (!a_) {                                                          \
+      std::cerr << __FILE__ << ':' << __LINE__ << ": "                  \
+                << __FUNCTION__ << ": Expected " << a_                  \
+                << " to be true" << std::endl;                          \
+      return false;                                                     \
+    }                                                                   \
+  } while (false)
+
 #define ASSERT_STREQ(expected, actual)                                  \
   do {                                                                  \
     auto e_ = (expected);                                               \