diff options
| -rw-r--r-- | src/observers.hh | 147 | ||||
| -rw-r--r-- | test/Makefile.am | 5 | ||||
| -rw-r--r-- | test/test-observers.cc | 94 | ||||
| -rw-r--r-- | test/test.hh | 11 |
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); \ |