src/Util/ListHead.hpp

   1 /*
   2  * Copyright (C) 2010-2011 Max Kellermann <max@duempel.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the
  14  * distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  20  * FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  27  * OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef XCSOAR_UTIL_LIST_HEAD_HPP
  31 #define XCSOAR_UTIL_LIST_HEAD_HPP
  32
  33 #include "Compiler.h"
  34
  35 #include <stddef.h>
  36 #include <iterator>
  37 #include <cassert>
  38
  39 /**
  40  * A doubly linked list implementation, similar to linux/list.h.  It
  41  * is very cheap at runtime, because the prev/next pointers are
  42  * included in each item, instead of doing a separate allocation.  To
  43  * use it, derive your class/struct from this one.
  44  */
  45 class ListHead {
  46   ListHead *next, *prev;
  47
  48 #ifndef NDEBUG
  49   enum {
  50     UNKNOWN,
  51     HEAD,
  52     CONNECTED,
  53     DISCONNECTED,
  54   } type;
  55 #endif
  56
  57 public:
  58   /**
  59    * Cheap non-initializing constructor.
  60    */
  61 #ifndef NDEBUG
  62   ListHead()
  63     :type(UNKNOWN) {}
  64 #else
  65   ListHead() = default;
  66 #endif
  67
  68   struct empty {};
  69
  70   /**
  71    * Initialize an empty list.
  72    */
  73   ListHead(empty)
  74     :next(this), prev(this)
  75 #ifndef NDEBUG
  76     , type(HEAD)
  77 #endif
  78   {}
  79
  80   const ListHead *GetPrevious() const {
  81     assert(type == CONNECTED || type == HEAD);
  82
  83     return prev;
  84   }
  85
  86   ListHead *GetPrevious() {
  87     assert(type == CONNECTED || type == HEAD);
  88
  89     return prev;
  90   }
  91
  92   const ListHead *GetNext() const {
  93     assert(type == CONNECTED || type == HEAD);
  94
  95     return next;
  96   }
  97
  98   ListHead *GetNext() {
  99     assert(type == CONNECTED || type == HEAD);
 100
 101     return next;
 102   }
 103
 104   bool IsEmpty() const {
 105     assert(type == HEAD);
 106     assert((prev == this) == (next == this));
 107     return prev == this;
 108   }
 109
 110   /**
 111    * Is the specified item the first one in the list?
 112    */
 113   bool IsFirst(const ListHead &item) const {
 114     assert(type == HEAD);
 115
 116     return item.prev == this;
 117   }
 118
 119   /**
 120    * Is the specified item the last one in the list?
 121    */
 122   bool IsLast(const ListHead &item) const {
 123     assert(type == HEAD);
 124
 125     return item.next == this;
 126   }
 127
 128   /**
 129    * Is the specified item the first or the last one in the list?
 130    */
 131   bool IsEdge(const ListHead &item) const {
 132     return IsFirst(item) || IsLast(item);
 133   }
 134
 135   /**
 136    * Count the number of items in this list, not including the current
 137    * one.
 138    */
 139   gcc_pure
 140   unsigned Count() const {
 141     assert(type == HEAD);
 142
 143     unsigned n = 0;
 144     for (const ListHead *p = next; p != this; p = p->next)
 145       ++n;
 146     return n;
 147   }
 148
 149   /**
 150    * Turns this object into an empty list.
 151    */
 152   void Clear() {
 153 #ifndef NDEBUG
 154     assert(type == UNKNOWN || type == HEAD);
 155 #endif
 156
 157     prev = next = this;
 158
 159 #ifndef NDEBUG
 160     type = HEAD;
 161 #endif
 162   }
 163
 164   /**
 165    * Remove this item from the linked list.
 166    */
 167   void Remove() {
 168     assert(type == CONNECTED);
 169     assert(prev->next == this);
 170     assert(next->prev == this);
 171
 172     next->prev = prev;
 173     prev->next = next;
 174
 175 #ifndef NDEBUG
 176     type = DISCONNECTED;
 177 #endif
 178   }
 179
 180   /**
 181    * Remove this item from the linked list.  This variant allows
 182    * removing a const object from the list.  Debug information is not
 183    * updated, this object must not ever be used again.  Use with care!
 184    */
 185   void RemoveConst() const {
 186     assert(type == CONNECTED);
 187     assert(prev->next == this);
 188     assert(next->prev == this);
 189
 190     next->prev = prev;
 191     prev->next = next;
 192   }
 193
 194   /**
 195    * Insert this item after the specified one.  It must not be in the
 196    * list already (or in another list).
 197    */
 198   void InsertAfter(ListHead &other) {
 199     assert(type == UNKNOWN || type == DISCONNECTED);
 200     assert(&other != this);
 201     assert(&other != this);
 202     assert(other.type == HEAD || other.type == CONNECTED);
 203     assert(other.prev->next == &other);
 204     assert(other.next->prev == &other);
 205
 206     next = other.next;
 207     next->prev = this;
 208     prev = &other;
 209     other.next = this;
 210
 211 #ifndef NDEBUG
 212     type = CONNECTED;
 213 #endif
 214   }
 215
 216   /**
 217    * Insert this item before the specified one.  It must not be in the
 218    * list already (or in another list).
 219    */
 220   void InsertBefore(ListHead &other) {
 221     assert(type == UNKNOWN || type == DISCONNECTED);
 222     assert(&other != this);
 223     assert(&other != this);
 224     assert(other.type == HEAD || other.type == CONNECTED);
 225     assert(other.prev->next == &other);
 226     assert(other.next->prev == &other);
 227
 228     prev = other.prev;
 229     prev->next = this;
 230     next = &other;
 231     other.prev = this;
 232
 233 #ifndef NDEBUG
 234     type = CONNECTED;
 235 #endif
 236   }
 237
 238   /**
 239    * Move this item from its current position in the list after the
 240    * specified one.
 241    */
 242   void MoveAfter(ListHead &other) {
 243     assert(type == CONNECTED);
 244     assert(other.type == HEAD || other.type == CONNECTED);
 245
 246     if (prev == &other) {
 247       assert(other.next == this);
 248       return;
 249     }
 250
 251     Remove();
 252     InsertAfter(other);
 253   }
 254
 255   /**
 256    * Insert this item with the specified one.
 257    */
 258   void Replace(ListHead &other) {
 259     assert(type == CONNECTED);
 260     assert(&other != this);
 261     assert(prev->next == this);
 262     assert(next->prev == this);
 263     assert(other.type == UNKNOWN || other.type == DISCONNECTED);
 264
 265     other.next = next;
 266     other.prev = prev;
 267
 268     next->prev = &other;
 269     prev->next = &other;
 270
 271 #ifndef NDEBUG
 272     type = DISCONNECTED;
 273     other.type = CONNECTED;
 274 #endif
 275   }
 276
 277   /**
 278    * Changes the type from CONNECTED to DISCONNECTED.  Call this on
 279    * the copy of an existing object.
 280    */
 281   void SetDisconnected() {
 282 #ifndef NDEBUG
 283     assert(type == CONNECTED);
 284     type = DISCONNECTED;
 285 #endif
 286   }
 287
 288   class const_iterator {
 289     friend class ListHead;
 290
 291     const ListHead *current;
 292
 293     constexpr
 294     const_iterator(const ListHead *_current):current(_current) {}
 295
 296   public:
 297     typedef std::bidirectional_iterator_tag iterator_category;
 298     typedef ptrdiff_t difference_type;
 299     typedef const ListHead value_type;
 300     typedef const ListHead *pointer;
 301     typedef const ListHead &reference;
 302
 303     const_iterator() = default;
 304
 305     reference operator*() const {
 306       return *current;
 307     }
 308
 309     pointer operator->() const {
 310       return current;
 311     }
 312
 313     const_iterator &operator++() {
 314       current = current->next;
 315       return *this;
 316     }
 317
 318     const_iterator operator++(int) {
 319       const_iterator old = *this;
 320       current = current->next;
 321       return old;
 322     }
 323
 324     const_iterator &operator--() {
 325       current = current->prev;
 326       return *this;
 327     }
 328
 329     const_iterator operator--(int) {
 330       const_iterator old = *this;
 331       current = current->prev;
 332       return old;
 333     }
 334
 335     bool operator==(const const_iterator &other) const {
 336       return current == other.current;
 337     }
 338
 339     bool operator!=(const const_iterator &other) const {
 340       return current != other.current;
 341     }
 342   };
 343
 344   const_iterator begin() const {
 345     assert(type == HEAD);
 346
 347     return next;
 348   }
 349
 350   const_iterator end() const {
 351     assert(type == HEAD);
 352
 353     return this;
 354   }
 355
 356   class const_reverse_iterator {
 357     friend class ListHead;
 358
 359     const ListHead *current;
 360
 361     constexpr
 362     const_reverse_iterator(const ListHead *_current):current(_current) {}
 363
 364   public:
 365     typedef std::bidirectional_iterator_tag iterator_category;
 366     typedef ptrdiff_t difference_type;
 367     typedef const ListHead value_type;
 368     typedef const ListHead *pointer;
 369     typedef const ListHead &reference;
 370
 371     const_reverse_iterator() = default;
 372
 373     reference operator*() const {
 374       return *current;
 375     }
 376
 377     pointer operator->() const {
 378       return current;
 379     }
 380
 381     const_reverse_iterator &operator++() {
 382       current = current->prev;
 383       return *this;
 384     }
 385
 386     const_reverse_iterator operator++(int) {
 387       const_reverse_iterator old = *this;
 388       current = current->prev;
 389       return old;
 390     }
 391
 392     const_reverse_iterator &operator--() {
 393       current = current->next;
 394       return *this;
 395     }
 396
 397     const_reverse_iterator operator--(int) {
 398       const_reverse_iterator old = *this;
 399       current = current->next;
 400       return old;
 401     }
 402
 403     bool operator==(const const_reverse_iterator &other) const {
 404       return current == other.current;
 405     }
 406
 407     bool operator!=(const const_reverse_iterator &other) const {
 408       return current != other.current;
 409     }
 410   };
 411
 412   const_reverse_iterator rbegin() const {
 413     assert(type == HEAD);
 414
 415     return prev;
 416   }
 417
 418   const_reverse_iterator rend() const {
 419     assert(type == HEAD);
 420
 421     return this;
 422   }
 423 };
 424
 425 #endif