LogService
libdadi: utility tools for distributed applications
FullLinkedList.hh
00001 /****************************************************************************/
00002 /* Thread safe generic Double linked list with full access                  */
00003 /*                                                                          */
00004 /*  Author(s):                                                              */
00005 /*    - Georg Hoesch (hoesch@in.tum.de)                                     */
00006 /*    - Cyrille Pontvieux (cyrille.pontvieux@edu.univ-fcomte.fr)            */
00007 /*                                                                          */
00008 /*  This file is part of DIET .                                             */
00009 /*                                                                          */
00010 /*  Copyright (C) 2000-2003 ENS Lyon, LIFC, INSA, INRIA and SysFera (2000)  */
00011 /*                                                                          */
00012 /*  - Frederic.Desprez@ens-lyon.fr (Project Manager)                        */
00013 /*  - Eddy.Caron@ens-lyon.fr (Technical Manager)                            */
00014 /*  - Tech@sysfera.com (Maintainer and Technical Support)                   */
00015 /*                                                                          */
00016 /*  This software is a computer program whose purpose is to provide an      */
00017 /*  distributed logging services.                                           */
00018 /*                                                                          */
00019 /*                                                                          */
00020 /*  This software is governed by the CeCILL license under French law and    */
00021 /*  abiding by the rules of distribution of free software.  You can  use,   */
00022 /*  modify and/ or redistribute the software under the terms of the CeCILL  */
00023 /*  license as circulated by CEA, CNRS and INRIA at the following URL       */
00024 /*  "http://www.cecill.info".                                               */
00025 /*                                                                          */
00026 /*  As a counterpart to the access to the source code and  rights to copy,  */
00027 /*  modify and redistribute granted by the license, users are provided      */
00028 /*  only with a limited warranty  and the software's author,  the holder    */
00029 /*  of the economic rights,  and the successive licensors  have only        */
00030 /*  limited liability.                                                      */
00031 /*                                                                          */
00032 /*  In this respect, the user's attention is drawn to the risks             */
00033 /*  associated with loading,  using,  modifying and/or developing or        */
00034 /*  reproducing the software by the user in light of its specific status    */
00035 /*  of free software, that may mean  that it is complicated to              */
00036 /*  manipulate, and  that  also therefore means  that it is reserved for    */
00037 /*  developers and experienced professionals having in-depth computer       */
00038 /*  knowledge. Users are therefore encouraged to load and test the          */
00039 /*  software's suitability as regards their requirements in conditions      */
00040 /*  enabling the security of their systems and/or data to be ensured and,   */
00041 /*  more generally, to use and operate it in the same conditions as         */
00042 /*  regards security.                                                       */
00043 /*                                                                          */
00044 /*  The fact that you are presently reading this means that you have had    */
00045 /*  knowledge of the CeCILL license and that you accept its terms.          */
00046 /*                                                                          */
00047 /****************************************************************************/
00048 /* $Id$
00049  * $Log$
00050  * Revision 1.2  2006/06/01 16:13:47  rbolze
00051  * change to be able to compile with gcc-4
00052  * Thanks to Abdelkader Amar who has done the work.
00053  *
00054  * Revision 1.1  2004/01/09 11:07:12  ghoesch
00055  * Restructured the whole LogService source tree.
00056  * Added autotools make process. Cleaned up code.
00057  * Removed some testers. Ready to release.
00058  *
00059  ****************************************************************************/
00060 
00061 #ifndef _FULLLINKEDLIST_HH_
00062 #define _FULLLINKEDLIST_HH_
00063 
00064 #include <omnithread.h>
00065 #include <sys/types.h>
00066 #include <assert.h>
00067 
00068 
00069 class Node;
00070 /****************************************************************************
00071  * This is a thread safe generic double linked list. It offers ReadWrite
00072  * and Readonly access to the list with the two iterators Iterator and
00073  * ReadIterator. Several Readers can exist at a time, while writers have
00074  * exclusive access to the list. Other iterators created in this time
00075  * will be blocked until the active iterator is deleted, so don't keep
00076  * your iterators to long. Write iterators have the possibility to
00077  * release their write-rights and become a read iterator without
00078  * releasing their read lock.
00079  *
00080  * The current implementation of this list does not distinguish between
00081  * readers and writers, but the behaviour can be implemented by changing
00082  * the functions lockReadWrite, lockRead, unlockRead and unlockWrite.
00083  *
00084  * This list deals with a copy of all the elements (T) but you can also use
00085  * some special functions to deal with references, but use them carrefully.
00086  */
00087 template<class T>
00088 class FullLinkedList {
00089 // FIXME: relocate this
00093   struct Node {
00097     Node* next;
00101     Node* previous;
00105     T* element;
00106   };
00107 
00108 public:
00109 /*****************************************************************************
00110  * PUBLIC METHODS
00111  ****************************************************************************/
00112   class ReadIterator;
00113   class Iterator;
00114 
00118   FullLinkedList();
00119 
00124   explicit FullLinkedList(FullLinkedList<T>& newFLL);
00125 
00130   ~FullLinkedList();
00131 
00135   FullLinkedList<T>&
00136   operator =(FullLinkedList<T>& newFLL);
00137 
00143   void
00144   emptyIt();
00145 
00153   void
00154   push(T* element);
00155 
00164   void
00165   pushRef(T* element);
00166 
00174   void
00175   shift(T* element);
00176 
00185   void
00186   shiftRef(T* element);
00187 
00195   T*
00196   pop();
00197 
00205   T*
00206   unshift();
00207 
00216   void
00217   appendList(FullLinkedList<T>* list);
00218 
00227   Iterator*
00228   getIterator();
00229 
00238   ReadIterator*
00239   getReadIterator();
00240 
00250   ReadIterator*
00251   reduceWriteIterator(Iterator* rwIterator);
00252 
00253 /*****************************************************************************
00254  * ITERATOR SECTION - INNER CLASSES
00255  ****************************************************************************/
00256 public:
00263   class ReadIterator {
00264     // these two are necessary for the private constructors
00265     friend class FullLinkedList;
00266     /***************************************************************************
00267      * PUBLIC METHODS
00268      **************************************************************************/
00269   public:
00277     virtual
00278     ~ReadIterator();
00279 
00284     inline void
00285     reset();
00286 
00291     inline void
00292     resetToLast();
00293 
00297     inline bool
00298     hasCurrent();
00299 
00304     inline bool
00305     hasNext();
00306 
00311     inline bool
00312     hasPrevious();
00313 
00319     inline T*
00320     getCurrent();
00321 
00329     inline T*
00330     getCurrentRef();
00331 
00336     inline T*
00337     next();
00338 
00344     inline T*
00345     nextRef();
00346 
00351     inline T*
00352     previous();
00353 
00359     inline T*
00360     previousRef();
00361 
00365     inline unsigned int
00366     length();
00367 
00368     /***************************************************************************
00369      * PROTECTED METHODS
00370      **************************************************************************/
00371   protected:
00377     explicit ReadIterator(FullLinkedList* controlledList);
00378 
00379     /***************************************************************************
00380      * PROTECTED FIELDS
00381      **************************************************************************/
00385     FullLinkedList* linkedList;
00386 
00390     // FullLinkedList::Node* currentNode;
00391     Node* currentNode;
00392 
00401     bool noReadRelease;
00402   };
00403 
00404 
00412   class Iterator: public FullLinkedList::ReadIterator {
00413     friend class FullLinkedList;
00414     /***************************************************************************
00415      * PUBLIC METHODS
00416      **************************************************************************/
00417   public:
00424     virtual
00425     ~Iterator();
00426 
00434     void
00435     removeCurrent();
00436 
00447     T*
00448     removeAndGetCurrent();
00449 
00461     void
00462     insertAfter(T* element);
00463 
00474     void
00475     insertAfterRef(T* element);
00476 
00488     void
00489     insertBefore(T* element);
00490 
00501     void
00502     insertBeforeRef(T* element);
00503 
00504     /***************************************************************************
00505      * PRIVATE METHODS
00506      **************************************************************************/
00507   private:
00513     explicit Iterator(FullLinkedList* controlledList);
00514   };  // end of inner class Iterator
00515 
00516 /*****************************************************************************
00517  * PRIVATE METHODS
00518  ****************************************************************************/
00519 private:
00520   void
00521   operatorEqualPrivate(FullLinkedList<T>& newFLL);
00522 
00523   void
00524   emptyItPrivate();
00525 
00526   void
00527   appendListPrivate(FullLinkedList<T>* list);
00528 
00534   void
00535   lockReadWrite();
00536 
00541   void
00542   lockRead();
00543 
00548   void
00549   unlockWrite();
00550 
00555   void
00556   unlockRead();
00557 
00562   void
00563   unlockReadWrite();
00564 
00565 /*****************************************************************************
00566  * PRIVATE FIELDS
00567  ****************************************************************************/
00571   long counter;
00572 
00576   Node* first;
00577 
00582   Node* last;
00583 
00588   mutable omni_mutex writerMutex;
00589 
00594   int readerCount;
00595 
00599   mutable omni_mutex readerCountMutex;
00600 
00605   mutable omni_mutex readersExistMutex;
00606 };
00607 
00612 #include "FullLinkedList.cc"
00613 
00614 #endif  // _FULLLINKEDLIST_HH_
 All Classes Functions Variables