include/intrusive_list_impl.h

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