src/core/forward_list.h

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file forward_list.h Forward list implementation. */
   9
  10 #ifndef FORWARD_LIST_H
  11 #define FORWARD_LIST_H
  12
  13 /**
  14  * Forward list link.
  15  * @tparam T The type of the objects in the list.
  16  * @tparam S Unused; can be used to disambiguate the class if you need to
  17  * derive twice from it.
  18  */
  19 template <class T, typename S = void>
  20 struct ForwardListLink {
  21         typedef T Type;
  22
  23         Type *next;
  24
  25         ForwardListLink() : next(NULL) { }
  26
  27         ForwardListLink (const ForwardListLink &) : next(NULL) { }
  28
  29         ForwardListLink& operator = (const ForwardListLink &)
  30         {
  31                 next = NULL;
  32                 return *this;
  33         }
  34 };
  35
  36 /**
  37  * Implementation of a generic forward list.
  38  *
  39  * We have a hand-written implementation of a forward list for the following
  40  * reasons:
  41  *
  42  * 1. std::forward_list is not in C++98, and we still support some compilers
  43  * that do not implement C++11.
  44  *
  45  * 2. The implementation of a forward list below has the next element pointer
  46  * embedded in the struct, and it must be defined by the struct itself. This
  47  * allows a struct to be part of more than one list at the same time.
  48  *
  49  * @tparam TLink The link type; must derive from ForwardListLink.
  50  */
  51 template <class TLink>
  52 struct ForwardList {
  53         typedef TLink Link;
  54         typedef typename Link::Type Type;
  55
  56         Type *head;
  57
  58         ForwardList() : head(NULL) { }
  59
  60         ForwardList (const ForwardList &) DELETED;
  61         ForwardList& operator = (const ForwardList &) DELETED;
  62
  63 private:
  64         /** Internal find function. */
  65         Type **find_internal (const Type *t)
  66         {
  67                 Type **p = &head;
  68                 while (*p != NULL && *p != t) {
  69                         p = &(*p)->Link::next;
  70                 }
  71                 return p;
  72         }
  73
  74         /** Internal find tail function. */
  75         Type **find_tail (void)
  76         {
  77                 return find_internal (NULL);
  78         }
  79
  80         /** Internal predicate-based find function. */
  81         template <class Pred>
  82         Type **find_pred_internal (Pred pred)
  83         {
  84                 Type **p = &head;
  85                 while (*p != NULL && !pred((const Type*)(*p))) {
  86                         p = &(*p)->Link::next;
  87                 }
  88                 return p;
  89         }
  90
  91         /** Internal remove function. */
  92         Type *remove_internal (Type **p)
  93         {
  94                 Type *r = *p;
  95                 if (r == NULL) return NULL;
  96                 *p = r->Link::next;
  97                 r->Link::next = NULL;
  98                 return r;
  99         }
 100
 101         /** Internal detach function. */
 102         Type *detach_internal (Type **p)
 103         {
 104                 Type *r = *p;
 105                 if (r == NULL) return NULL;
 106                 *p = NULL;
 107                 return r;
 108         }
 109
 110 public:
 111         /** Append an item or chain of items. */
 112         void append (Type *t)
 113         {
 114                 *find_tail() = t;
 115         }
 116
 117         /** Prepend an item. */
 118         void prepend (Type *t)
 119         {
 120                 assert (t->Link::next == NULL);
 121                 t->Link::next = head;
 122                 head = t;
 123         }
 124
 125         /** Find an item. */
 126         Type *find (const Type *t)
 127         {
 128                 return *find_internal(t);
 129         }
 130
 131         /** Find an item. */
 132         template <class Pred>
 133         Type *find_pred (Pred pred)
 134         {
 135                 return *find_pred_internal(pred);
 136         }
 137
 138         /** Remove an item. */
 139         Type *remove (const Type *t)
 140         {
 141                 return remove_internal (find_internal (t));
 142         }
 143
 144         /** Remove an item. */
 145         template <class Pred>
 146         Type *remove_pred (Pred pred)
 147         {
 148                 return remove_internal (find_pred_internal (pred));
 149         }
 150
 151         /** Detach an item chain. */
 152         Type *detach (const Type *t)
 153         {
 154                 return detach_internal (find_internal (t));
 155         }
 156
 157         /** Detach an item chain. */
 158         template <class Pred>
 159         Type *detach_pred (Pred pred)
 160         {
 161                 return detach_internal (find_pred_internal (pred));
 162         }
 163
 164         /** Detach the whole list. */
 165         Type *detach_all (void)
 166         {
 167                 Type *r = head;
 168                 head = NULL;
 169                 return r;
 170         }
 171 };
 172
 173 #endif /* FORWARD_LIST_H */