include/intrusive_list_impl.h

   1 /*
   2  * InspIRCd -- Internet Relay Chat Daemon
   3  *
   4  *   Copyright (C) 2013-2014 Attila Molnar <attilamolnar@hush.com>
   5  *
   6  * This file is part of InspIRCd.  InspIRCd is free software: you can
   7  * redistribute it and/or modify it under the terms of the GNU General Public
   8  * License as published by the Free Software Foundation, version 2.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  12  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  13  * details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19
  20 template <typename T, typename Tag>
  21 class INSPIRCD_INTRUSIVE_LIST_NAME
  22 {
  23  public:
  24         class iterator : public std::iterator<std::bidirectional_iterator_tag, T*>
  25         {
  26                 T* curr;
  27
  28          public:
  29                 iterator(T* i = NULL)
  30                         : curr(i)
  31                 {
  32                 }
  33
  34                 iterator& operator++()
  35                 {
  36                         curr = curr->intrusive_list_node<T, Tag>::ptr_next;
  37                         return *this;
  38                 }
  39
  40                 iterator operator++(int)
  41                 {
  42                         iterator ret(*this);
  43                         operator++();
  44                         return ret;
  45                 }
  46
  47                 iterator& operator--()
  48                 {
  49                         curr = curr->intrusive_list_node<T, Tag>::ptr_prev;
  50                         return *this;
  51                 }
  52
  53                 iterator operator--(int)
  54                 {
  55                         iterator ret(*this);
  56                         operator--();
  57                         return ret;
  58                 }
  59
  60                 bool operator==(const iterator& other) const { return (curr == other.curr); }
  61                 bool operator!=(const iterator& other) const { return (curr != other.curr); }
  62                 T* operator*() const { return curr; }
  63         };
  64
  65         typedef iterator const_iterator;
  66
  67         INSPIRCD_INTRUSIVE_LIST_NAME()
  68                 : listhead(NULL)
  69 #ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
  70                 , listtail(NULL)
  71 #endif
  72                 , listsize(0)
  73         {
  74         }
  75
  76         bool empty() const
  77         {
  78                 return (size() == 0);
  79         }
  80
  81         size_t size() const
  82         {
  83                 return listsize;
  84         }
  85
  86         iterator begin() const
  87         {
  88                 return iterator(listhead);
  89         }
  90
  91         iterator end() const
  92         {
  93                 return iterator();
  94         }
  95
  96         void pop_front()
  97         {
  98                 erase(listhead);
  99         }
 100
 101         T* front() const
 102         {
 103                 return listhead;
 104         }
 105
 106         void push_front(T* x)
 107         {
 108                 if (listsize++)
 109                 {
 110                         x->intrusive_list_node<T, Tag>::ptr_next = listhead;
 111                         listhead->intrusive_list_node<T, Tag>::ptr_prev = x;
 112                 }
 113 #ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
 114                 else
 115                         listtail = x;
 116 #endif
 117                 listhead = x;
 118         }
 119
 120 #ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
 121         T* back() const
 122         {
 123                 return listtail;
 124         }
 125
 126         void push_back(T* x)
 127         {
 128                 if (listsize++)
 129                 {
 130                         x->intrusive_list_node<T, Tag>::ptr_prev = listtail;
 131                         listtail->intrusive_list_node<T, Tag>::ptr_next = x;
 132                 }
 133                 else
 134                         listhead = x;
 135                 listtail = x;
 136         }
 137
 138         void pop_back()
 139         {
 140                 erase(listtail);
 141         }
 142 #endif
 143
 144         void erase(const iterator& it)
 145         {
 146                 erase(*it);
 147         }
 148
 149         void erase(T* x)
 150         {
 151                 if (listhead == x)
 152                         listhead = x->intrusive_list_node<T, Tag>::ptr_next;
 153 #ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
 154                 if (listtail == x)
 155                         listtail = x->intrusive_list_node<T, Tag>::ptr_prev;
 156 #endif
 157                 x->intrusive_list_node<T, Tag>::unlink();
 158                 listsize--;
 159         }
 160
 161  private:
 162         T* listhead;
 163 #ifdef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
 164         T* listtail;
 165 #endif
 166         size_t listsize;
 167 };