include/intrusive_list.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 #pragma once
  21
  22 #include <iterator>
  23
  24 struct intrusive_list_def_tag { };
  25
  26 template <typename T, typename Tag = intrusive_list_def_tag> class intrusive_list;
  27
  28 template <typename T, typename Tag = intrusive_list_def_tag>
  29 struct intrusive_list_node
  30 {
  31         T* ptr_next;
  32         T* ptr_prev;
  33
  34         void unlink()
  35         {
  36                 if (ptr_next)
  37                         ptr_next->intrusive_list_node<T, Tag>::ptr_prev = this->ptr_prev;
  38                 if (ptr_prev)
  39                         ptr_prev->intrusive_list_node<T, Tag>::ptr_next = this->ptr_next;
  40                 ptr_next = ptr_prev = NULL;
  41         }
  42
  43  public:
  44         intrusive_list_node()
  45                 : ptr_next(NULL)
  46                 , ptr_prev(NULL)
  47         {
  48         }
  49
  50         friend class intrusive_list<T, Tag>;
  51 };
  52
  53 template <typename T, typename Tag>
  54 class intrusive_list
  55 {
  56  public:
  57         class iterator : public std::iterator<std::bidirectional_iterator_tag, T*>
  58         {
  59                 T* curr;
  60
  61          public:
  62                 iterator(T* i = NULL)
  63                         : curr(i)
  64                 {
  65                 }
  66
  67                 iterator& operator++()
  68                 {
  69                         curr = curr->intrusive_list_node<T, Tag>::ptr_next;
  70                         return *this;
  71                 }
  72
  73                 iterator operator++(int)
  74                 {
  75                         iterator ret(*this);
  76                         operator++();
  77                         return ret;
  78                 }
  79
  80                 void operator--()
  81                 {
  82                         curr = curr->intrusive_list_node<T, Tag>::ptr_prev;
  83                         return *this;
  84                 }
  85
  86                 iterator operator--(int)
  87                 {
  88                         iterator ret(*this);
  89                         operator--();
  90                         return ret;
  91                 }
  92
  93                 bool operator==(const iterator& other) const { return (curr == other.curr); }
  94                 bool operator!=(const iterator& other) const { return (curr != other.curr); }
  95                 T* operator*() const { return curr; }
  96         };
  97
  98         typedef iterator const_iterator;
  99
 100         intrusive_list()
 101                 : listhead(NULL)
 102                 , listsize(0)
 103         {
 104         }
 105
 106         bool empty() const
 107         {
 108                 return (size() == 0);
 109         }
 110
 111         size_t size() const
 112         {
 113                 return listsize;
 114         }
 115
 116         iterator begin() const
 117         {
 118                 return iterator(listhead);
 119         }
 120
 121         iterator end() const
 122         {
 123                 return iterator();
 124         }
 125
 126         void pop_front()
 127         {
 128                 erase(listhead);
 129         }
 130
 131         T* front() const
 132         {
 133                 return listhead;
 134         }
 135
 136         void push_front(T* x)
 137         {
 138                 if (listsize++)
 139                 {
 140                         x->intrusive_list_node<T, Tag>::ptr_next = listhead;
 141                         listhead->intrusive_list_node<T, Tag>::ptr_prev = x;
 142                 }
 143                 listhead = x;
 144         }
 145
 146         void erase(const iterator& it)
 147         {
 148                 erase(*it);
 149         }
 150
 151         void erase(T* x)
 152         {
 153                 if (listhead == x)
 154                         listhead = x->intrusive_list_node<T, Tag>::ptr_next;
 155                 x->intrusive_list_node<T, Tag>::unlink();
 156                 listsize--;
 157         }
 158
 159  private:
 160         T* listhead;
 161         size_t listsize;
 162 };