linked_list.hpp

00001 /*
00002  * Singly-linked list.
00003  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00004  */
00005 
00006 #ifndef UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED
00007 #define UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED
00008 
00009 #include <cstdlib>
00010 #include <cassert>
00011 #include <uavcan/build_config.hpp>
00012 #include <uavcan/util/templates.hpp>
00013 
00014 namespace uavcan
00015 {
00016 /**
00017  * Classes that are supposed to be linked-listed should derive this.
00018  */
00019 template <typename T>
00020 class UAVCAN_EXPORT LinkedListNode : Noncopyable
00021 {
00022     T* next_;
00023 
00024 protected:
00025     LinkedListNode()
00026         : next_(UAVCAN_NULLPTR)
00027     { }
00028 
00029     ~LinkedListNode() { }
00030 
00031 public:
00032     T* getNextListNode() const { return next_; }
00033 
00034     void setNextListNode(T* node)
00035     {
00036         next_ = node;
00037     }
00038 };
00039 
00040 /**
00041  * Linked list root.
00042  */
00043 template <typename T>
00044 class UAVCAN_EXPORT LinkedListRoot : Noncopyable
00045 {
00046     T* root_;
00047 
00048 public:
00049     LinkedListRoot()
00050         : root_(UAVCAN_NULLPTR)
00051     { }
00052 
00053     T* get() const { return root_; }
00054     bool isEmpty() const { return get() == UAVCAN_NULLPTR; }
00055 
00056     /**
00057      * Complexity: O(N)
00058      */
00059     unsigned getLength() const;
00060 
00061     /**
00062      * Inserts the node to the beginning of the list.
00063      * If the node is already present in the list, it will be relocated to the beginning.
00064      * Complexity: O(N)
00065      */
00066     void insert(T* node);
00067 
00068     /**
00069      * Inserts the node immediately before the node X where predicate(X) returns true.
00070      * If the node is already present in the list, it can be relocated to a new position.
00071      * Complexity: O(2N) (calls remove())
00072      */
00073     template <typename Predicate>
00074     void insertBefore(T* node, Predicate predicate);
00075 
00076     /**
00077      * Removes only the first occurence of the node.
00078      * Complexity: O(N)
00079      */
00080     void remove(const T* node);
00081 };
00082 
00083 // ----------------------------------------------------------------------------
00084 
00085 /*
00086  * LinkedListRoot<>
00087  */
00088 template <typename T>
00089 unsigned LinkedListRoot<T>::getLength() const
00090 {
00091     T* node = root_;
00092     unsigned cnt = 0;
00093     while (node)
00094     {
00095         cnt++;
00096         node = node->getNextListNode();
00097     }
00098     return cnt;
00099 }
00100 
00101 template <typename T>
00102 void LinkedListRoot<T>::insert(T* node)
00103 {
00104     if (node == UAVCAN_NULLPTR)
00105     {
00106         UAVCAN_ASSERT(0);
00107         return;
00108     }
00109     remove(node);  // Making sure there will be no loops
00110     node->setNextListNode(root_);
00111     root_ = node;
00112 }
00113 
00114 template <typename T>
00115 template <typename Predicate>
00116 void LinkedListRoot<T>::insertBefore(T* node, Predicate predicate)
00117 {
00118     if (node == UAVCAN_NULLPTR)
00119     {
00120         UAVCAN_ASSERT(0);
00121         return;
00122     }
00123 
00124     remove(node);
00125 
00126     if (root_ == UAVCAN_NULLPTR || predicate(root_))
00127     {
00128         node->setNextListNode(root_);
00129         root_ = node;
00130     }
00131     else
00132     {
00133         T* p = root_;
00134         while (p->getNextListNode())
00135         {
00136             if (predicate(p->getNextListNode()))
00137             {
00138                 break;
00139             }
00140             p = p->getNextListNode();
00141         }
00142         node->setNextListNode(p->getNextListNode());
00143         p->setNextListNode(node);
00144     }
00145 }
00146 
00147 template <typename T>
00148 void LinkedListRoot<T>::remove(const T* node)
00149 {
00150     if (root_ == UAVCAN_NULLPTR || node == UAVCAN_NULLPTR)
00151     {
00152         return;
00153     }
00154 
00155     if (root_ == node)
00156     {
00157         root_ = root_->getNextListNode();
00158     }
00159     else
00160     {
00161         T* p = root_;
00162         while (p->getNextListNode())
00163         {
00164             if (p->getNextListNode() == node)
00165             {
00166                 p->setNextListNode(p->getNextListNode()->getNextListNode());
00167                 break;
00168             }
00169             p = p->getNextListNode();
00170         }
00171     }
00172 }
00173 
00174 }
00175 
00176 #endif // UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED