Back to index

enigmail  1.4.3
LinkedList.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  * vim: set ts=4 sw=4 tw=80 et cin:
00003  *
00004  * ***** BEGIN LICENSE BLOCK *****
00005  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006  *
00007  * The contents of this file are subject to the Mozilla Public License Version
00008  * 1.1 (the "License"); you may not use this file except in compliance with
00009  * the License. You may obtain a copy of the License at:
00010  * http://www.mozilla.org/MPL/
00011  *
00012  * Software distributed under the License is distributed on an "AS IS" basis,
00013  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00014  * for the specific language governing rights and limitations under the
00015  * License.
00016  *
00017  * The Original Code is Mozilla Code.
00018  *
00019  * The Initial Developer of the Original Code is
00020  *   The Mozilla Foundation
00021  * Portions created by the Initial Developer are Copyright (C) 2012
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *   Justin Lebar <justin.lebar@gmail.com>
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either the GNU General Public License Version 2 or later (the "GPL"), or
00029  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 /* A type-safe doubly-linked list class. */
00042 
00043 /*
00044  * The classes LinkedList<T> and LinkedListElement<T> together form a
00045  * convenient, type-safe doubly-linked list implementation.
00046  *
00047  * The class T which will be inserted into the linked list must inherit from
00048  * LinkedListElement<T>.  A given object may be in only one linked list at a
00049  * time.
00050  *
00051  * For example, you might use LinkedList in a simple observer list class as
00052  * follows.
00053  *
00054  *   class Observer : public LinkedListElement<Observer>
00055  *   {
00056  *     void observe(char* topic) { ... }
00057  *   };
00058  *
00059  *   class ObserverContainer
00060  *   {
00061  *   private:
00062  *     LinkedList<ElemType> list;
00063  *
00064  *   public:
00065  *
00066  *     void addObserver(Observer* observer)
00067  *     {
00068  *       // Will assert if |observer| is part of another list.
00069  *       list.insertBack(observer);
00070  *     }
00071  *
00072  *     void removeObserver(Observer* observer)
00073  *     {
00074  *       // Will assert if |observer| is not part of some list.
00075  *       observer.remove();
00076  *     }
00077  *
00078  *     void notifyObservers(char* topic)
00079  *     {
00080  *       for (Observer* o = list.getFirst();
00081  *            o != NULL;
00082  *            o = o->getNext()) {
00083  *         o->Observe(topic);
00084  *       }
00085  *     }
00086  *   };
00087  *
00088  */
00089 
00090 #ifndef mozilla_LinkedList_h_
00091 #define mozilla_LinkedList_h_
00092 
00093 #include "mozilla/Assertions.h"
00094 #include "mozilla/Attributes.h"
00095 
00096 #ifdef __cplusplus
00097 
00098 namespace mozilla {
00099 
00100 template<typename T>
00101 class LinkedList;
00102 
00103 template<typename T>
00104 class LinkedListElement
00105 {
00106     /*
00107      * It's convenient that we return NULL when getNext() or getPrevious() hits
00108      * the end of the list, but doing so costs an extra word of storage in each
00109      * linked list node (to keep track of whether |this| is the sentinel node)
00110      * and a branch on this value in getNext/getPrevious.
00111      *
00112      * We could get rid of the extra word of storage by shoving the "is
00113      * sentinel" bit into one of the pointers, although this would, of course,
00114      * have performance implications of its own.
00115      *
00116      * But the goal here isn't to win an award for the fastest or slimmest
00117      * linked list; rather, we want a *convenient* linked list.  So we won't
00118      * waste time guessing which micro-optimization strategy is best.
00119      *
00120      *
00121      * Speaking of unnecessary work, it's worth addressing here why we wrote
00122      * mozilla::LinkedList in the first place, instead of using stl::list.
00123      *
00124      * The key difference between mozilla::LinkedList and stl::list is that
00125      * mozilla::LinkedList stores the prev/next pointers in the object itself,
00126      * while stl::list stores the prev/next pointers in a list element which
00127      * itself points to the object being stored.
00128      *
00129      * mozilla::LinkedList's approach makes it harder to store an object in more
00130      * than one list.  But the upside is that you can call next() / prev() /
00131      * remove() directly on the object.  With stl::list, you'd need to store a
00132      * pointer to its iterator in the object in order to accomplish this.  Not
00133      * only would this waste space, but you'd have to remember to update that
00134      * pointer every time you added or removed the object from a list.
00135      *
00136      * In-place, constant-time removal is a killer feature of doubly-linked
00137      * lists, and supporting this painlessly was a key design criterion.
00138      */
00139 
00140 private:
00141     LinkedListElement* next;
00142     LinkedListElement* prev;
00143     const bool isSentinel;
00144 
00145 public:
00146     LinkedListElement()
00147         : next(this)
00148         , prev(this)
00149         , isSentinel(false)
00150     {
00151     }
00152 
00153     /*
00154      * Get the next element in the list, or NULL if this is the last element in
00155      * the list.
00156      */
00157     T* getNext()
00158     {
00159         return next->asT();
00160     }
00161 
00162     /*
00163      * Get the previous element in the list, or NULL if this is the first element
00164      * in the list.
00165      */
00166     T* getPrevious()
00167     {
00168         return prev->asT();
00169     }
00170 
00171     /*
00172      * Insert elem after this element in the list.  |this| must be part of a
00173      * linked list when you call setNext(); otherwise, this method will assert.
00174      */
00175     void setNext(T* elem)
00176     {
00177         MOZ_ASSERT(isInList());
00178         setNextUnsafe(elem);
00179     }
00180 
00181     /*
00182      * Insert elem before this element in the list.  |this| must be part of a
00183      * linked list when you call setPrevious(); otherwise, this method will
00184      * assert.
00185      */
00186     void setPrevious(T* elem)
00187     {
00188         MOZ_ASSERT(isInList());
00189         setPreviousUnsafe(elem);
00190     }
00191 
00192     /*
00193      * Remove this element from the list which contains it.  If this element is
00194      * not currently part of a linked list, this method asserts.
00195      */
00196     void remove()
00197     {
00198         MOZ_ASSERT(isInList());
00199 
00200         prev->next = next;
00201         next->prev = prev;
00202         next = this;
00203         prev = this;
00204     }
00205 
00206     /*
00207      * Return true if |this| part is of a linked list, and false otherwise.
00208      */
00209     bool isInList()
00210     {
00211         MOZ_ASSERT((next == this) == (prev == this));
00212         return next != this;
00213     }
00214 
00215 private:
00216     LinkedListElement& operator=(const LinkedList<T>& other) MOZ_DELETE;
00217     LinkedListElement(const LinkedList<T>& other) MOZ_DELETE;
00218 
00219     friend class LinkedList<T>;
00220 
00221     enum NodeKind {
00222         NODE_KIND_NORMAL,
00223         NODE_KIND_SENTINEL
00224     };
00225 
00226     LinkedListElement(NodeKind nodeKind)
00227         : next(this)
00228         , prev(this)
00229         , isSentinel(nodeKind == NODE_KIND_SENTINEL)
00230     {
00231     }
00232 
00233     /*
00234      * Return |this| cast to T* if we're a normal node, or return NULL if we're
00235      * a sentinel node.
00236      */
00237     T* asT()
00238     {
00239         if (isSentinel)
00240             return NULL;
00241 
00242         return static_cast<T*>(this);
00243     }
00244 
00245     /*
00246      * Insert elem after this element, but don't check that this element is in
00247      * the list.  This is called by LinkedList::insertFront().
00248      */
00249     void setNextUnsafe(T* elem)
00250     {
00251         LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
00252         MOZ_ASSERT(!listElem->isInList());
00253 
00254         listElem->next = this->next;
00255         listElem->prev = this;
00256         this->next->prev = listElem;
00257         this->next = listElem;
00258     }
00259 
00260     /*
00261      * Insert elem before this element, but don't check that this element is in
00262      * the list.  This is called by LinkedList::insertBack().
00263      */
00264     void setPreviousUnsafe(T* elem)
00265     {
00266         LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
00267         MOZ_ASSERT(!listElem->isInList());
00268 
00269         listElem->next = this;
00270         listElem->prev = this->prev;
00271         this->prev->next = listElem;
00272         this->prev = listElem;
00273     }
00274 };
00275 
00276 template<typename T>
00277 class LinkedList
00278 {
00279 private:
00280     LinkedListElement<T> sentinel;
00281 
00282 public:
00283     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
00284     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
00285 
00286     LinkedList()
00287         : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL)
00288     {
00289     }
00290 
00291     /*
00292      * Add elem to the front of the list.
00293      */
00294     void insertFront(T* elem)
00295     {
00296         /* Bypass setNext()'s this->isInList() assertion. */
00297         sentinel.setNextUnsafe(elem);
00298     }
00299 
00300     /*
00301      * Add elem to the back of the list.
00302      */
00303     void insertBack(T* elem)
00304     {
00305         sentinel.setPreviousUnsafe(elem);
00306     }
00307 
00308     /*
00309      * Get the first element of the list, or NULL if the list is empty.
00310      */
00311     T* getFirst()
00312     {
00313         return sentinel.getNext();
00314     }
00315 
00316     /*
00317      * Get the last element of the list, or NULL if the list is empty.
00318      */
00319     T* getLast()
00320     {
00321         return sentinel.getPrevious();
00322     }
00323 
00324     /*
00325      * Get and remove the first element of the list.  If the list is empty,
00326      * return NULL.
00327      */
00328     T* popFirst()
00329     {
00330         T* ret = sentinel.getNext();
00331         if (ret)
00332             static_cast<LinkedListElement<T>*>(ret)->remove();
00333 
00334         return ret;
00335     }
00336 
00337     /*
00338      * Get and remove the last element of the list.  If the list is empty,
00339      * return NULL.
00340      */
00341     T* popLast()
00342     {
00343         T* ret = sentinel.getPrevious();
00344         if (ret)
00345             static_cast<LinkedListElement<T>*>(ret)->remove();
00346 
00347         return ret;
00348     }
00349 
00350     /*
00351      * Return true if the list is empty, or false otherwise.
00352      */
00353     bool isEmpty()
00354     {
00355         return !sentinel.isInList();
00356     }
00357 
00358     /*
00359      * In a debug build, make sure that the list is sane (no cycles, consistent
00360      * next/prev pointers, only one sentinel).  Has no effect in release builds.
00361      */
00362     void debugAssertIsSane()
00363     {
00364 #ifdef DEBUG
00365         /*
00366          * Check for cycles in the forward singly-linked list using the
00367          * tortoise/hare algorithm.
00368          */
00369         for (LinkedListElement<T>* slow = sentinel.next,
00370                                  * fast1 = sentinel.next->next,
00371                                  * fast2 = sentinel.next->next->next;
00372              slow != sentinel && fast1 != sentinel && fast2 != sentinel;
00373              slow = slow->next,
00374              fast1 = fast2->next,
00375              fast2 = fast1->next) {
00376 
00377             MOZ_ASSERT(slow != fast1);
00378             MOZ_ASSERT(slow != fast2);
00379         }
00380 
00381         /* Check for cycles in the backward singly-linked list. */
00382         for (LinkedListElement<T>* slow = sentinel.prev,
00383                                  * fast1 = sentinel.prev->prev,
00384                                  * fast2 = sentinel.prev->prev->prev;
00385              slow != sentinel && fast1 != sentinel && fast2 != sentinel;
00386              slow = slow->prev,
00387              fast1 = fast2->prev,
00388              fast2 = fast1->prev) {
00389 
00390             MOZ_ASSERT(slow != fast1);
00391             MOZ_ASSERT(slow != fast2);
00392         }
00393 
00394         /*
00395          * Check that |sentinel| is the only node in the list with
00396          * isSentinel == true.
00397          */
00398         for (LinkedListElement<T>* elem = sentinel.next;
00399              elem != sentinel;
00400              elem = elem->next) {
00401 
00402           MOZ_ASSERT(!elem->isSentinel);
00403         }
00404 
00405         /* Check that the next/prev pointers match up. */
00406         LinkedListElement<T>* prev = sentinel;
00407         LinkedListElement<T>* cur = sentinel.next;
00408         do {
00409             MOZ_ASSERT(cur->prev == prev);
00410             MOZ_ASSERT(prev->next == cur);
00411 
00412             prev = cur;
00413             cur = cur->next;
00414         } while (cur != sentinel);
00415 #endif /* ifdef DEBUG */
00416     }
00417 };
00418 
00419 } /* namespace mozilla */
00420 
00421 #endif /* ifdef __cplusplus */
00422 #endif /* ifdef mozilla_LinkedList_h_ */