Back to index

lightning-sunbird  0.9+nobinonly
morkDeque.cpp
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.cpp
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 _MDB_
00029 #include "mdb.h"
00030 #endif
00031 
00032 #ifndef _MORK_
00033 #include "mork.h"
00034 #endif
00035 
00036 #ifndef _MORKDEQUE_
00037 #include "morkDeque.h"
00038 #endif
00039 
00040 #ifndef _MORKNODE_
00041 #include "morkNode.h"
00042 #endif
00043 
00044 #ifndef _MORKENV_
00045 #include "morkEnv.h"
00046 #endif
00047 
00048 /*=============================================================================
00049  * morkNext: linked list node for very simple, singly-linked list
00050  */
00051  
00052 morkNext::morkNext() : mNext_Link( 0 )
00053 {
00054 }
00055 
00056 /*static*/ void*
00057 morkNext::MakeNewNext(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev)
00058 {
00059   void* next = 0;
00060   if ( &ioHeap )
00061   {
00062     ioHeap.Alloc(ev->AsMdbEnv(), inSize, (void**) &next);
00063     if ( !next )
00064       ev->OutOfMemoryError();
00065   }
00066   else
00067     ev->NilPointerError();
00068   
00069   return next;
00070 }
00071 
00072 /*static*/
00073 void morkNext::ZapOldNext(morkEnv* ev, nsIMdbHeap* ioHeap)
00074 {
00075   if ( ioHeap )
00076   {
00077     if ( this )
00078       ioHeap->Free(ev->AsMdbEnv(), this);
00079   }
00080   else
00081     ev->NilPointerError();
00082 }
00083 
00084 /*=============================================================================
00085  * morkList: simple, singly-linked list
00086  */
00087 
00088 morkList::morkList() : mList_Head( 0 ), mList_Tail( 0 )
00089 {
00090 }
00091 
00092 void morkList::CutAndZapAllListMembers(morkEnv* ev, nsIMdbHeap* ioHeap)
00093 // make empty list, zapping every member by calling ZapOldNext()
00094 {
00095   if ( ioHeap )
00096   {
00097     morkNext* next = 0;
00098     while ( (next = this->PopHead()) != 0 )
00099       next->ZapOldNext(ev, ioHeap);
00100       
00101     mList_Head = 0;
00102     mList_Tail = 0;
00103   }
00104   else
00105     ev->NilPointerError();
00106 }
00107 
00108 void morkList::CutAllListMembers()
00109 // just make list empty, dropping members without zapping
00110 {
00111   while ( this->PopHead() )
00112     /* empty */;
00113 
00114   mList_Head = 0;
00115   mList_Tail = 0;
00116 }
00117 
00118 morkNext* morkList::PopHead() // cut head of list
00119 {
00120   morkNext* outHead = mList_Head;
00121   if ( outHead ) // anything to cut from list?
00122   {
00123     morkNext* next = outHead->mNext_Link;
00124     mList_Head = next;
00125     if ( !next ) // cut the last member, so tail no longer exists?
00126       mList_Tail = 0;
00127       
00128     outHead->mNext_Link = 0; // nil outgoing node link; unnecessary, but tidy
00129   }
00130   return outHead;
00131 }
00132 
00133 
00134 void morkList::PushHead(morkNext* ioLink) // add to head of list
00135 {
00136   morkNext* head = mList_Head; // old head of list
00137   morkNext* tail = mList_Tail; // old tail of list
00138   
00139   MORK_ASSERT( (head && tail) || (!head && !tail));
00140   
00141   ioLink->mNext_Link = head; // make old head follow the new link
00142   if ( !head ) // list was previously empty?
00143     mList_Tail = ioLink; // head is also tail for first member added
00144 
00145   mList_Head = ioLink; // head of list is the new link
00146 }
00147 
00148 void morkList::PushTail(morkNext* ioLink) // add to tail of list
00149 {
00150   morkNext* head = mList_Head; // old head of list
00151   morkNext* tail = mList_Tail; // old tail of list
00152   
00153   MORK_ASSERT( (head && tail) || (!head && !tail));
00154   
00155   ioLink->mNext_Link = 0; 
00156   if ( tail ) 
00157   {
00158          tail->mNext_Link = ioLink;
00159          mList_Tail = ioLink;
00160   }
00161   else // list was previously empty?
00162          mList_Head = mList_Tail = ioLink; // tail is also head for first member added
00163 }
00164 
00165 /*=============================================================================
00166  * morkLink: linked list node embedded in objs to allow insertion in morkDeques
00167  */
00168  
00169 morkLink::morkLink() : mLink_Next( 0 ), mLink_Prev( 0 )
00170 {
00171 }
00172 
00173 /*static*/ void*
00174 morkLink::MakeNewLink(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev)
00175 {
00176   void* alink = 0;
00177   if ( &ioHeap )
00178   {
00179     ioHeap.Alloc(ev->AsMdbEnv(), inSize, (void**) &alink);
00180     if ( !alink )
00181       ev->OutOfMemoryError();
00182   }
00183   else
00184     ev->NilPointerError();
00185   
00186   return alink;
00187 }
00188 
00189 /*static*/
00190 void morkLink::ZapOldLink(morkEnv* ev, nsIMdbHeap* ioHeap)
00191 {
00192   if ( ioHeap )
00193   {
00194     if ( this )
00195       ioHeap->Free(ev->AsMdbEnv(), this);
00196   }
00197   else
00198     ev->NilPointerError();
00199 }
00200   
00201 /*=============================================================================
00202  * morkDeque: doubly linked list modeled after VAX queue instructions
00203  */
00204 
00205 morkDeque::morkDeque()
00206 {
00207   mDeque_Head.SelfRefer();
00208 }
00209 
00210 
00211 /*| RemoveFirst: 
00212 |*/
00213 morkLink*
00214 morkDeque::RemoveFirst() /*i*/
00215 {
00216   morkLink* alink = mDeque_Head.mLink_Next;
00217   if ( alink != &mDeque_Head )
00218   {
00219     (mDeque_Head.mLink_Next = alink->mLink_Next)->mLink_Prev = 
00220       &mDeque_Head;
00221     return alink;
00222   }
00223   return (morkLink*) 0;
00224 }
00225 
00226 /*| RemoveLast: 
00227 |*/
00228 morkLink*
00229 morkDeque::RemoveLast() /*i*/
00230 {
00231   morkLink* alink = mDeque_Head.mLink_Prev;
00232   if ( alink != &mDeque_Head )
00233   {
00234     (mDeque_Head.mLink_Prev = alink->mLink_Prev)->mLink_Next = 
00235       &mDeque_Head;
00236     return alink;
00237   }
00238   return (morkLink*) 0;
00239 }
00240 
00241 /*| At: 
00242 |*/
00243 morkLink*
00244 morkDeque::At(mork_pos index) const /*i*/
00245   /* indexes are one based (and not zero based) */
00246 { 
00247   register mork_num count = 0;
00248   register morkLink* alink;
00249   for ( alink = this->First(); alink; alink = this->After(alink) )
00250   {
00251     if ( ++count == (mork_num) index )
00252       break;
00253   }
00254   return alink;
00255 }
00256 
00257 /*| IndexOf: 
00258 |*/
00259 mork_pos
00260 morkDeque::IndexOf(const morkLink* member) const /*i*/
00261   /* indexes are one based (and not zero based) */
00262   /* zero means member is not in deque */
00263 { 
00264   register mork_num count = 0;
00265   register const morkLink* alink;
00266   for ( alink = this->First(); alink; alink = this->After(alink) )
00267   {
00268     ++count;
00269     if ( member == alink )
00270       return (mork_pos) count;
00271   }
00272   return 0;
00273 }
00274 
00275 /*| Length: 
00276 |*/
00277 mork_num
00278 morkDeque::Length() const /*i*/
00279 { 
00280   register mork_num count = 0;
00281   register morkLink* alink;
00282   for ( alink = this->First(); alink; alink = this->After(alink) )
00283     ++count;
00284   return count;
00285 }
00286 
00287 /*| LengthCompare: 
00288 |*/
00289 int
00290 morkDeque::LengthCompare(mork_num c) const /*i*/
00291 { 
00292   register mork_num count = 0;
00293   register const morkLink* alink;
00294   for ( alink = this->First(); alink; alink = this->After(alink) )
00295   {
00296     if ( ++count > c )
00297       return 1;
00298   }
00299   return ( count == c )? 0 : -1;
00300 }