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 namespace insp
  25 {
  26
  27 struct intrusive_list_def_tag { };
  28
  29 template <typename T, typename Tag = intrusive_list_def_tag> class intrusive_list;
  30 template <typename T, typename Tag = intrusive_list_def_tag> class intrusive_list_tail;
  31
  32 template <typename T, typename Tag = intrusive_list_def_tag>
  33 class intrusive_list_node
  34 {
  35         T* ptr_next;
  36         T* ptr_prev;
  37
  38         void unlink()
  39         {
  40                 if (ptr_next)
  41                         ptr_next->intrusive_list_node<T, Tag>::ptr_prev = this->ptr_prev;
  42                 if (ptr_prev)
  43                         ptr_prev->intrusive_list_node<T, Tag>::ptr_next = this->ptr_next;
  44                 ptr_next = ptr_prev = NULL;
  45         }
  46
  47  public:
  48         intrusive_list_node()
  49                 : ptr_next(NULL)
  50                 , ptr_prev(NULL)
  51         {
  52         }
  53
  54         friend class intrusive_list<T, Tag>;
  55         friend class intrusive_list_tail<T, Tag>;
  56 };
  57
  58 } // namespace insp
  59
  60 // Intrusive list where the list only has a pointer to the head element
  61 #define INSPIRCD_INTRUSIVE_LIST_NAME intrusive_list
  62 #include "intrusive_list_impl.h"
  63 #undef INSPIRCD_INTRUSIVE_LIST_NAME
  64
  65 // Intrusive list where the list maintains a pointer to both the head and the tail elements.
  66 // Additional methods: back(), push_back(), pop_back()
  67 #define INSPIRCD_INTRUSIVE_LIST_NAME intrusive_list_tail
  68 #define INSPIRCD_INTRUSIVE_LIST_HAS_TAIL
  69 #include "intrusive_list_impl.h"
  70 #undef INSPIRCD_INTRUSIVE_LIST_NAME
  71 #undef INSPIRCD_INTRUSIVE_LIST_HAS_TAIL