From 969791d3980f061288abf620d28761e42b1eeddc Mon Sep 17 00:00:00 2001 From: =?utf8?q?=EB=B0=95=EC=A2=85=ED=98=84/=EB=8F=99=EC=9E=91=EC=A0=9C?= =?utf8?q?=EC=96=B4Lab=28SR=29/Staff=20Engineer/=EC=82=BC=EC=84=B1?= =?utf8?q?=EC=A0=84=EC=9E=90?= Date: Thu, 19 Jul 2018 14:41:22 +0900 Subject: [PATCH] [coco] Add 'DLinkedList' traits (#703) * [coco] Add 'DLinkedList' traits This commit adds 'DLinkedList::Node' and 'DLinkedList::Head' traits. coco IR entities will use these traits to support traverse and manipulation of the order of entities. Signed-off-by: Jonghyun Park * Update assert per feedback --- contrib/coco/core/include/coco/ADT/DLinkedList.h | 161 +++++++++++++++++++++++ contrib/coco/core/src/ADT/DLinkedList.test.cpp | 88 +++++++++++++ 2 files changed, 249 insertions(+) create mode 100644 contrib/coco/core/include/coco/ADT/DLinkedList.h create mode 100644 contrib/coco/core/src/ADT/DLinkedList.test.cpp diff --git a/contrib/coco/core/include/coco/ADT/DLinkedList.h b/contrib/coco/core/include/coco/ADT/DLinkedList.h new file mode 100644 index 0000000..bf19fe9 --- /dev/null +++ b/contrib/coco/core/include/coco/ADT/DLinkedList.h @@ -0,0 +1,161 @@ +#ifndef __COCO_ADT_DLINKED_LIST_H__ +#define __COCO_ADT_DLINKED_LIST_H__ + +#include "coco/ADT/PtrLink.h" + +#include + +namespace coco +{ + +// **CAUTION** Child SHOULD inherit DLinkedList::Node +template struct DLinkedList +{ + class Head + { + public: + Head(Parent *parent, PtrLink *link) : _parent{parent}, _link{link} + { + _head = nullptr; + _tail = nullptr; + } + + public: + Head(const Head &) = delete; + Head(Head &&) = delete; + + public: + Child *head(void) const { return _head; } + Child *tail(void) const { return _tail; } + + public: + bool empty(void) const + { + if (_head == nullptr) + { + assert(_head == _tail); + return true; + } + + assert(_head != nullptr); + assert(_tail != nullptr); + return false; + } + + public: + void enlist(Child *child) + { + assert((child->prev() == nullptr) || (child->prev()->parent() == _parent)); + assert((child->next() == nullptr) || (child->next()->parent() == _parent)); + + if (empty()) + { + _head = child; + _tail = child; + } + else + { + if (child->next() == _head) + { + // _child is a new head + assert(child->prev() == nullptr); + _head = child; + } + + if (child->prev() == _tail) + { + // _child is a new tail + assert(child->next() == nullptr); + _tail = child; + } + } + + // Update parent-child relation + _link->set(child, _parent); + } + + public: + void append(Child *child) + { + if (empty()) + { + enlist(child); + } + else + { + child->insertAfter(_tail); + } + } + + private: + Parent * const _parent; + PtrLink * const _link; + + private: + Child * _head; + Child * _tail; + }; + + class Node + { + public: + Node(const PtrLink *link) : _link{link} + { + _prev = nullptr; + _next = nullptr; + } + + public: + virtual ~Node() = default; + + public: + Parent *parent(void) const { return _link->find(reinterpret_cast(this)); } + + public: + Child *prev(void) const { return _prev; } + Child *next(void) const { return _next; } + + public: + virtual Head *head(void) const = 0; + + public: + void insertAfter(Child *prev) + { + assert(prev != nullptr); + assert(prev->head() != nullptr); + + assert(_prev == nullptr); + assert(_next == nullptr); + + // REQUIRE Child should inherit Node class + auto curr = reinterpret_cast(this); + + // Update the link of the current node + _prev = prev; + _next = prev->next(); + + // Update the link of the sibling nodes + if (auto next = prev->next()) + { + next->_prev = curr; + } + prev->_next = curr; + + // Update parent-child relation + assert(parent() == nullptr); + prev->head()->enlist(curr); + assert(parent() == prev->parent()); + }; + + private: + const PtrLink * const _link; + + private: + Child *_prev; + Child *_next; + }; +}; + +} // namespace coco + +#endif // __COCO_ADT_DLINKED_LIST_H__ diff --git a/contrib/coco/core/src/ADT/DLinkedList.test.cpp b/contrib/coco/core/src/ADT/DLinkedList.test.cpp new file mode 100644 index 0000000..8459df3 --- /dev/null +++ b/contrib/coco/core/src/ADT/DLinkedList.test.cpp @@ -0,0 +1,88 @@ +#include "coco/ADT/DLinkedList.h" + +#include + +namespace +{ + +class Parent; +class Child; + +using ChildList = coco::DLinkedList::Head; + +class Parent +{ +public: + Parent(coco::PtrLink *link) : _list{this, link} + { + // DO NOTHING + } + +public: + ChildList *children(void) { return &_list; } + +private: + ChildList _list; +}; + +class Child : public coco::DLinkedList::Node +{ +public: + Child(const coco::PtrLink *link) : coco::DLinkedList::Node{link} + { + // DO NOTHING + } + +public: + ChildList *head(void) const override { return parent()->children(); } +}; + +} // namespace + +TEST(ADT_DLINKED_LINK, insert_two_elements) +{ + auto link = new coco::PtrLink<::Child, ::Parent>{}; + auto parent = new ::Parent{link}; + + ASSERT_EQ(parent->children()->head(), nullptr); + ASSERT_EQ(parent->children()->tail(), nullptr); + + auto child_1 = new ::Child{link}; + + ASSERT_EQ(child_1->parent(), nullptr); + ASSERT_EQ(child_1->prev(), nullptr); + ASSERT_EQ(child_1->next(), nullptr); + + parent->children()->append(child_1); + + ASSERT_EQ(child_1->parent(), parent); + ASSERT_EQ(child_1->prev(), nullptr); + ASSERT_EQ(child_1->next(), nullptr); + + ASSERT_EQ(parent->children()->head(), child_1); + ASSERT_EQ(parent->children()->tail(), child_1); + + auto child_2 = new ::Child{link}; + + ASSERT_EQ(child_2->parent(), nullptr); + ASSERT_EQ(child_2->prev(), nullptr); + ASSERT_EQ(child_2->next(), nullptr); + + child_2->insertAfter(child_1); + + ASSERT_EQ(child_2->parent(), parent); + ASSERT_EQ(child_2->prev(), child_1); + ASSERT_EQ(child_2->next(), nullptr); + + ASSERT_EQ(child_1->parent(), parent); + ASSERT_EQ(child_1->prev(), nullptr); + ASSERT_EQ(child_1->next(), child_2); + + ASSERT_EQ(parent->children()->head(), child_1); + ASSERT_EQ(parent->children()->tail(), child_2); + + delete child_2; + delete child_1; + delete parent; + delete link; +} -- 2.7.4