src/base/dbl_list.hh

   1 /*
   2  * Copyright (c) 2000-2001, 2003-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  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 FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Steve Reinhardt
  29  */
  30
  31 #ifndef __DBL_LIST_HH__
  32 #define __DBL_LIST_HH__
  33
  34 class DblListEl {
  35     DblListEl *next;
  36     DblListEl *prev;
  37
  38     // remove this from list
  39     void remove() {
  40         prev->next = next;
  41         next->prev = prev;
  42     }
  43
  44     // insert this before old_el
  45     void insertBefore(DblListEl *old_el) {
  46         prev = old_el->prev;
  47         next = old_el;
  48         prev->next = this;
  49         next->prev = this;
  50     }
  51
  52     // insert this after old_el
  53     void insertAfter(DblListEl *old_el) {
  54         next = old_el->next;
  55         prev = old_el;
  56         next->prev = this;
  57         prev->next = this;
  58     }
  59
  60     friend class DblListBase;
  61 };
  62
  63
  64 //
  65 // doubly-linked list of DblListEl objects
  66 //
  67 class DblListBase {
  68     // dummy list head element: dummy.next is head, dummy.prev is tail
  69     DblListEl dummy;
  70
  71     // length counter
  72     unsigned length;
  73
  74     DblListEl *valid_or_null(DblListEl *el) {
  75         // make sure users never see the dummy element
  76         return (el == &dummy) ? NULL : el;
  77     }
  78
  79   public:
  80
  81     DblListEl *head() {
  82         return valid_or_null(dummy.next);
  83     }
  84
  85     DblListEl *tail() {
  86         return valid_or_null(dummy.prev);
  87     }
  88
  89     DblListEl *next(DblListEl *el) {
  90         return valid_or_null(el->next);
  91     }
  92
  93     DblListEl *prev(DblListEl *el) {
  94         return valid_or_null(el->prev);
  95     }
  96
  97     bool is_empty() {
  98         return (dummy.next == &dummy);
  99     }
 100
 101     void remove(DblListEl *el) {
 102         el->remove();
 103         --length;
 104     }
 105
 106     void insertBefore(DblListEl *new_el, DblListEl *old_el) {
 107         new_el->insertBefore(old_el);
 108         ++length;
 109     }
 110
 111     void insertAfter(DblListEl *new_el, DblListEl *old_el) {
 112         new_el->insertAfter(old_el);
 113         ++length;
 114     }
 115
 116     // append to end of list, i.e. as dummy.prev
 117     void append(DblListEl *el) {
 118         insertBefore(el, &dummy);
 119     }
 120
 121     // prepend to front of list (push), i.e. as dummy.next
 122     void prepend(DblListEl *el) {
 123         insertAfter(el, &dummy);
 124     }
 125
 126     DblListEl *pop() {
 127         DblListEl *hd = head();
 128         if (hd != NULL)
 129             remove(hd);
 130         return hd;
 131     }
 132
 133     // constructor
 134     DblListBase() {
 135         dummy.next = dummy.prev = &dummy;
 136         length = 0;
 137     }
 138 };
 139
 140
 141 //
 142 // Template class serves solely to cast args & return values
 143 // to appropriate type (T *)
 144 //
 145 template<class T> class DblList : private DblListBase {
 146
 147   public:
 148
 149     T *head() { return (T *)DblListBase::head(); }
 150     T *tail() { return (T *)DblListBase::tail(); }
 151
 152     T *next(T *el) { return (T *)DblListBase::next(el); }
 153     T *prev(T *el) { return (T *)DblListBase::prev(el); }
 154
 155     bool is_empty() { return DblListBase::is_empty(); }
 156
 157     void remove(T *el) { DblListBase::remove(el); }
 158
 159     void append(T *el) { DblListBase::append(el); }
 160     void prepend(T *el) { DblListBase::prepend(el); }
 161
 162     T *pop() { return (T *)DblListBase::pop(); }
 163
 164     DblList<T>() { }
 165 };
 166
 167 #endif // __DBL_LIST_HH__