From fc9426a5a11e93bb17bbb944b2555fa6ac4183f3 Mon Sep 17 00:00:00 2001
From: Kefu Chai <kchai@redhat.com>
Date: Fri, 27 Mar 2015 16:45:20 +0800
Subject: [PATCH] xlist: add compare operator for iterator

* and add basic test cases for xlist

Signed-off-by: Kefu Chai <kchai@redhat.com>
---
 src/include/xlist.h    |  13 ++++-
 src/test/Makefile.am   |   5 ++
 src/test/test_xlist.cc | 118 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 134 insertions(+), 2 deletions(-)
 create mode 100644 src/test/test_xlist.cc

diff --git a/src/include/xlist.h b/src/include/xlist.h
index dcde2250d054..a98e7b296e85 100644
--- a/src/include/xlist.h
+++ b/src/include/xlist.h
@@ -16,6 +16,7 @@
 #define CEPH_XLIST_H
 
 #include "include/assert.h"
+#include <iterator>
 #include <cstdlib>
 
 template<typename T>
@@ -57,6 +58,8 @@ public:
     }
   };
 
+  typedef item* const_reference;
+
 private:
   item *_front, *_back;
   int _size;
@@ -151,7 +154,7 @@ public:
     remove(_back);
   }
 
-  class iterator {
+  class iterator: std::iterator<std::forward_iterator_tag, T> {
   private:
     item *cur;
   public:
@@ -164,12 +167,18 @@ public:
       return *this;
     }
     bool end() const { return cur == 0; }
+    bool operator==(const iterator& rhs) const {
+      return cur == rhs.cur;
+    }
+    bool operator!=(const iterator& rhs) const {
+      return cur != rhs.cur;
+    }
   };
 
   iterator begin() { return iterator(_front); }
   iterator end() { return iterator(NULL); }
 
-  class const_iterator {
+  class const_iterator: std::iterator<std::forward_iterator_tag, T> {
   private:
     item *cur;
   public:
diff --git a/src/test/Makefile.am b/src/test/Makefile.am
index 43b485e70edd..3f69d5ead8b7 100644
--- a/src/test/Makefile.am
+++ b/src/test/Makefile.am
@@ -278,6 +278,11 @@ unittest_bufferlist_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL)
 unittest_bufferlist_CXXFLAGS = $(UNITTEST_CXXFLAGS)
 check_PROGRAMS += unittest_bufferlist
 
+unittest_xlist_SOURCES = test/test_xlist.cc
+unittest_xlist_LDADD = $(UNITTEST_LDADD) $(LIBCOMMON)
+unittest_xlist_CXXFLAGS = $(UNITTEST_CXXFLAGS)
+check_PROGRAMS += unittest_xlist
+
 unittest_crc32c_SOURCES = test/common/test_crc32c.cc
 unittest_crc32c_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL)
 unittest_crc32c_CXXFLAGS = $(UNITTEST_CXXFLAGS)
diff --git a/src/test/test_xlist.cc b/src/test/test_xlist.cc
new file mode 100644
index 000000000000..9d5eadd0e975
--- /dev/null
+++ b/src/test/test_xlist.cc
@@ -0,0 +1,118 @@
+#include <algorithm>
+#include <iterator>
+#include <vector>
+#include "include/xlist.h"
+
+#include "gtest/gtest.h"
+
+
+struct Item {
+  xlist<Item*>::item xitem;
+  int val;
+
+  Item(int v) :
+    xitem(this),
+    val(v)
+  {}
+};
+
+class XlistTest : public testing::Test
+{
+protected:
+  typedef xlist<Item*> ItemList;
+  typedef std::vector<Item*> Items;
+  typedef std::vector<ItemList::item*> Refs;
+  Items items;
+  // for filling up an ItemList
+  Refs refs;
+
+  virtual void SetUp() {
+    for (int i = 0; i < 13; i++) {
+      items.push_back(new Item(i));
+      refs.push_back(&items.back()->xitem);
+    }
+  }
+  virtual void TearDown() {
+    for (Items::iterator i = items.begin(); i != items.end(); ++i) {
+      delete *i;
+    }
+    items.clear();
+  }
+};
+
+TEST_F(XlistTest, capability) {
+  ItemList list;
+  ASSERT_TRUE(list.empty());
+  ASSERT_EQ(list.size(), 0);
+
+  std::copy(refs.begin(), refs.end(), std::back_inserter(list));
+  ASSERT_EQ((size_t)list.size(), refs.size());
+
+  list.clear();
+  ASSERT_TRUE(list.empty());
+  ASSERT_EQ(list.size(), 0);
+}
+
+TEST_F(XlistTest, traverse) {
+  ItemList list;
+  std::copy(refs.begin(), refs.end(), std::back_inserter(list));
+
+  // advance until iterator::end()
+  size_t index = 0;
+  for (ItemList::iterator i = list.begin(); !i.end(); ++i) {
+    ASSERT_EQ(*i, items[index]);
+    index++;
+  }
+  // advance until i == v.end()
+  index = 0;
+  for (ItemList::iterator i = list.begin(); i != list.end(); ++i) {
+    ASSERT_EQ(*i, items[index]);
+    index++;
+  }
+  list.clear();
+}
+
+TEST_F(XlistTest, move_around) {
+  Item item1(42), item2(17);
+  ItemList list;
+
+  // only a single element in the list
+  list.push_back(&item1.xitem);
+  ASSERT_EQ(&item1, list.front());
+  ASSERT_EQ(&item1, list.back());
+
+  list.push_back(&item2.xitem);
+  ASSERT_EQ(&item1, list.front());
+  ASSERT_EQ(&item2, list.back());
+
+  // move item2 to the front
+  list.push_front(&item2.xitem);
+  ASSERT_EQ(&item2, list.front());
+  ASSERT_EQ(&item1, list.back());
+
+  // and move it back
+  list.push_back(&item2.xitem);
+  ASSERT_EQ(&item1, list.front());
+  ASSERT_EQ(&item2, list.back());
+
+  list.clear();
+}
+
+TEST_F(XlistTest, item_queries) {
+  Item item(42);
+  ItemList list;
+  list.push_back(&item.xitem);
+
+  ASSERT_TRUE(item.xitem.is_on_list());
+  ASSERT_EQ(&list, item.xitem.get_list());
+
+  ASSERT_TRUE(item.xitem.remove_myself());
+  ASSERT_FALSE(item.xitem.is_on_list());
+  ASSERT_TRUE(item.xitem.get_list() == NULL);
+}
+
+// Local Variables:
+// compile-command: "cd .. ;
+//   make unittest_xlist &&
+//   ./unittest_xlist"
+// End:
-- 
2.47.3