Back to index

lightning-sunbird  0.9+nobinonly
morkDeque.h
Go to the documentation of this file.
00001 /*************************************************************************
00002 This software is part of a public domain IronDoc source code distribution,
00003 and is provided on an "AS IS" basis, with all risks borne by the consumers
00004 or users of the IronDoc software.  There are no warranties, guarantees, or
00005 promises about quality of any kind; and no remedies for failure exist. 
00006 
00007 Permission is hereby granted to use this IronDoc software for any purpose
00008 at all, without need for written agreements, without royalty or license
00009 fees, and without fees or obligations of any other kind.  Anyone can use,
00010 copy, change and distribute this software for any purpose, and nothing is
00011 required, implicitly or otherwise, in exchange for this usage.
00012 
00013 You cannot apply your own copyright to this software, but otherwise you
00014 are encouraged to enjoy the use of this software in any way you see fit.
00015 However, it would be rude to remove names of developers from the code.
00016 (IronDoc is also known by the short name "Fe" and a longer name "Ferrum",
00017 which are used interchangeably with the name IronDoc in the sources.)
00018 *************************************************************************/
00019 /*
00020  * File:      morkDeque.h 
00021  * Contains:  Ferrum deque (double ended queue (linked list))
00022  *
00023  * Copied directly from public domain IronDoc, with minor naming tweaks:
00024  * Designed and written by David McCusker, but all this code is public domain.
00025  * There are no warranties, no guarantees, no promises, and no remedies.
00026  */
00027 
00028 #ifndef _MORKDEQUE_
00029 #define _MORKDEQUE_ 1
00030 
00031 #ifndef _MORK_
00032 #include "mork.h"
00033 #endif
00034 
00035 /*=============================================================================
00036  * morkNext: linked list node for very simple, singly-linked list
00037  */
00038 
00039 class morkNext /*d*/ {  
00040 public:
00041   morkNext*  mNext_Link;
00042   
00043 public:
00044   morkNext(int inZero) : mNext_Link( 0 ) { }
00045   
00046   morkNext(morkNext* ioLink) : mNext_Link( ioLink ) { }
00047   
00048   morkNext(); // mNext_Link( 0 ), { }
00049   
00050 public:
00051   morkNext*  GetNextLink() const { return mNext_Link; }
00052   
00053 public: // link memory management methods
00054   static void* MakeNewNext(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev);
00055   void ZapOldNext(morkEnv* ev, nsIMdbHeap* ioHeap);
00056 
00057 public: // link memory management operators
00058   void* operator new(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev) CPP_THROW_NEW
00059   { return morkNext::MakeNewNext(inSize, ioHeap, ev); }
00060   
00061   void operator delete(void* ioAddress) // DO NOT CALL THIS, hope to crash:
00062   { ((morkNext*) 0)->ZapOldNext((morkEnv*) 0, (nsIMdbHeap*) 0); } // boom
00063 };
00064 
00065 /*=============================================================================
00066  * morkList: simple, singly-linked list
00067  */
00068 
00069 /*| morkList: a list of singly-linked members (instances of morkNext), where
00070 **| the number of list members might be so numerous that we must about cost
00071 **| for two pointer link slots per member (as happens with morkLink).
00072 **|
00073 **|| morkList is intended to support lists of changes in morkTable, where we
00074 **| are worried about the space cost of representing such changes. (Later we
00075 **| can use an array instead, when we get even more worried, to avoid cost
00076 **| of link slots at all, per member).
00077 **|
00078 **|| Do NOT create cycles in links using this list class, since we do not
00079 **| deal with them very nicely.
00080 |*/
00081 class morkList /*d*/  {  
00082 public:
00083   morkNext*  mList_Head; // first link in the list
00084   morkNext*  mList_Tail; // last link in the list
00085   
00086 public:
00087   morkNext*  GetListHead() const { return mList_Head; }
00088   morkNext*  GetListTail() const { return mList_Tail; }
00089 
00090   mork_bool IsListEmpty() const { return ( mList_Head == 0 ); }
00091   mork_bool HasListMembers() const { return ( mList_Head != 0 ); }
00092   
00093 public:
00094   morkList(); // : mList_Head( 0 ), mList_Tail( 0 ) { }
00095   
00096   void CutAndZapAllListMembers(morkEnv* ev, nsIMdbHeap* ioHeap);
00097   // make empty list, zapping every member by calling ZapOldNext()
00098 
00099   void CutAllListMembers();
00100   // just make list empty, dropping members without zapping
00101 
00102 public:
00103   morkNext* PopHead(); // cut head of list
00104   
00105   // Note we don't support PopTail(), so use morkDeque if you need that.
00106   
00107   void PushHead(morkNext* ioLink); // add to head of list
00108   void PushTail(morkNext* ioLink); // add to tail of list
00109 };
00110 
00111 /*=============================================================================
00112  * morkLink: linked list node embedded in objs to allow insertion in morkDeques
00113  */
00114 
00115 class morkLink /*d*/ {  
00116 public:
00117   morkLink*  mLink_Next;
00118   morkLink*  mLink_Prev;
00119   
00120 public:
00121   morkLink(int inZero) : mLink_Next( 0 ), mLink_Prev( 0 ) { }
00122   
00123   morkLink(); // mLink_Next( 0 ), mLink_Prev( 0 ) { }
00124   
00125 public:
00126   morkLink*  Next() const { return mLink_Next; }
00127   morkLink*  Prev() const { return mLink_Prev; }
00128   
00129   void SelfRefer() { mLink_Next = mLink_Prev = this; }
00130   void Clear() { mLink_Next = mLink_Prev = 0; }
00131   
00132   void AddBefore(morkLink* old)
00133   {
00134     ((old)->mLink_Prev->mLink_Next = (this))->mLink_Prev = (old)->mLink_Prev;
00135     ((this)->mLink_Next = (old))->mLink_Prev = this;
00136   }
00137   
00138   void AddAfter(morkLink* old)
00139   {
00140     ((old)->mLink_Next->mLink_Prev = (this))->mLink_Next = (old)->mLink_Next;
00141     ((this)->mLink_Prev = (old))->mLink_Next = this;
00142   }
00143   
00144   void Remove()
00145   {
00146     (mLink_Prev->mLink_Next = mLink_Next)->mLink_Prev = mLink_Prev;
00147   }
00148   
00149 public: // link memory management methods
00150   static void* MakeNewLink(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev);
00151   void ZapOldLink(morkEnv* ev, nsIMdbHeap* ioHeap);
00152 
00153 public: // link memory management operators
00154   void* operator new(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev) CPP_THROW_NEW
00155   { return morkLink::MakeNewLink(inSize, ioHeap, ev); }
00156   
00157 };
00158 
00159 /*=============================================================================
00160  * morkDeque: doubly linked list modeled after VAX queue instructions
00161  */
00162 
00163 class morkDeque /*d*/ {
00164 public:
00165   morkLink  mDeque_Head;
00166 
00167 public: // construction
00168   morkDeque(); // { mDeque_Head.SelfRefer(); }
00169 
00170 public:// methods
00171   morkLink* RemoveFirst();
00172 
00173   morkLink* RemoveLast();
00174 
00175   morkLink* At(mork_pos index) const ; /* one-based, not zero-based */
00176 
00177   mork_pos IndexOf(const morkLink* inMember) const; 
00178     /* one-based index ; zero means member is not in deque */
00179 
00180   mork_num Length() const;
00181 
00182   /* the following method is more efficient for long lists: */
00183   int LengthCompare(mork_num inCount) const;
00184   /* -1: length < count, 0: length == count,  1: length > count */
00185 
00186 public: // inlines
00187 
00188   mork_bool IsEmpty()const 
00189   { return (mDeque_Head.mLink_Next == (morkLink*) &mDeque_Head); }
00190 
00191   morkLink* After(const morkLink* old) const
00192   { return (((old)->mLink_Next != &mDeque_Head)?
00193             (old)->mLink_Next : (morkLink*) 0); }
00194 
00195   morkLink* Before(const morkLink* old) const
00196   { return (((old)->mLink_Prev != &mDeque_Head)?
00197             (old)->mLink_Prev : (morkLink*) 0); }
00198 
00199   morkLink*  First() const
00200   { return ((mDeque_Head.mLink_Next != &mDeque_Head)?
00201     mDeque_Head.mLink_Next : (morkLink*) 0); }
00202 
00203   morkLink*  Last() const
00204   { return ((mDeque_Head.mLink_Prev != &mDeque_Head)?
00205     mDeque_Head.mLink_Prev : (morkLink*) 0); }
00206     
00207 /*
00208 From IronDoc documentation for AddFirst:
00209 +--------+   +--------+      +--------+   +--------+   +--------+
00210 | h.next |-->| b.next |      | h.next |-->| a.next |-->| b.next |
00211 +--------+   +--------+  ==> +--------+   +--------+   +--------+
00212 | h.prev |<--| b.prev |      | h.prev |<--| a.prev |<--| b.prev |
00213 +--------+   +--------+      +--------+   +--------+   +--------+
00214 */
00215 
00216   void AddFirst(morkLink* in) /*i*/ 
00217   {
00218     ( (mDeque_Head.mLink_Next->mLink_Prev = 
00219       (in))->mLink_Next = mDeque_Head.mLink_Next, 
00220         ((in)->mLink_Prev = &mDeque_Head)->mLink_Next = (in) );
00221   }
00222 /*
00223 From IronDoc documentation for AddLast:
00224 +--------+   +--------+      +--------+   +--------+   +--------+
00225 | y.next |-->| h.next |      | y.next |-->| z.next |-->| h.next |
00226 +--------+   +--------+  ==> +--------+   +--------+   +--------+
00227 | y.prev |<--| h.prev |      | y.prev |<--| z.prev |<--| h.prev |
00228 +--------+   +--------+      +--------+   +--------+   +--------+
00229 */
00230 
00231   void AddLast(morkLink* in)
00232   {
00233     ( (mDeque_Head.mLink_Prev->mLink_Next = 
00234       (in))->mLink_Prev = mDeque_Head.mLink_Prev, 
00235         ((in)->mLink_Next = &mDeque_Head)->mLink_Prev = (in) );
00236   }
00237 };
00238 
00239 #endif /* _MORKDEQUE_ */