db/mork/src/morkDeque.h

   1 /*************************************************************************
   2 This software is part of a public domain IronDoc source code distribution,
   3 and is provided on an "AS IS" basis, with all risks borne by the consumers
   4 or users of the IronDoc software.  There are no warranties, guarantees, or
   5 promises about quality of any kind; and no remedies for failure exist.
   6
   7 Permission is hereby granted to use this IronDoc software for any purpose
   8 at all, without need for written agreements, without royalty or license
   9 fees, and without fees or obligations of any other kind.  Anyone can use,
  10 copy, change and distribute this software for any purpose, and nothing is
  11 required, implicitly or otherwise, in exchange for this usage.
  12
  13 You cannot apply your own copyright to this software, but otherwise you
  14 are encouraged to enjoy the use of this software in any way you see fit.
  15 However, it would be rude to remove names of developers from the code.
  16 (IronDoc is also known by the short name "Fe" and a longer name "Ferrum",
  17 which are used interchangeably with the name IronDoc in the sources.)
  18 *************************************************************************/
  19 /*
  20  * File:      morkDeque.h
  21  * Contains:  Ferrum deque (double ended queue (linked list))
  22  *
  23  * Copied directly from public domain IronDoc, with minor naming tweaks:
  24  * Designed and written by David McCusker, but all this code is public domain.
  25  * There are no warranties, no guarantees, no promises, and no remedies.
  26  */
  27
  28 #ifndef _MORKDEQUE_
  29 #define _MORKDEQUE_ 1
  30
  31 #ifndef _MORK_
  32 #include "mork.h"
  33 #endif
  34
  35 /*=============================================================================
  36  * morkNext: linked list node for very simple, singly-linked list
  37  */
  38
  39 class morkNext /*d*/ {
  40 public:
  41   morkNext*  mNext_Link;
  42
  43 public:
  44   morkNext(int inZero) : mNext_Link( 0 ) { }
  45
  46   morkNext(morkNext* ioLink) : mNext_Link( ioLink ) { }
  47
  48   morkNext(); // mNext_Link( 0 ), { }
  49
  50 public:
  51   morkNext*  GetNextLink() const { return mNext_Link; }
  52
  53 public: // link memory management methods
  54   static void* MakeNewNext(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev);
  55   void ZapOldNext(morkEnv* ev, nsIMdbHeap* ioHeap);
  56
  57 public: // link memory management operators
  58   void* operator new(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev) CPP_THROW_NEW
  59   { return morkNext::MakeNewNext(inSize, ioHeap, ev); }
  60
  61   void operator delete(void* ioAddress) // DO NOT CALL THIS, hope to crash:
  62   { ((morkNext*) 0)->ZapOldNext((morkEnv*) 0, (nsIMdbHeap*) 0); } // boom
  63 };
  64
  65 /*=============================================================================
  66  * morkList: simple, singly-linked list
  67  */
  68
  69 /*| morkList: a list of singly-linked members (instances of morkNext), where
  70 **| the number of list members might be so numerous that we must about cost
  71 **| for two pointer link slots per member (as happens with morkLink).
  72 **|
  73 **|| morkList is intended to support lists of changes in morkTable, where we
  74 **| are worried about the space cost of representing such changes. (Later we
  75 **| can use an array instead, when we get even more worried, to avoid cost
  76 **| of link slots at all, per member).
  77 **|
  78 **|| Do NOT create cycles in links using this list class, since we do not
  79 **| deal with them very nicely.
  80 |*/
  81 class morkList /*d*/  {
  82 public:
  83   morkNext*  mList_Head; // first link in the list
  84   morkNext*  mList_Tail; // last link in the list
  85
  86 public:
  87   morkNext*  GetListHead() const { return mList_Head; }
  88   morkNext*  GetListTail() const { return mList_Tail; }
  89
  90   mork_bool IsListEmpty() const { return ( mList_Head == 0 ); }
  91   mork_bool HasListMembers() const { return ( mList_Head != 0 ); }
  92
  93 public:
  94   morkList(); // : mList_Head( 0 ), mList_Tail( 0 ) { }
  95
  96   void CutAndZapAllListMembers(morkEnv* ev, nsIMdbHeap* ioHeap);
  97   // make empty list, zapping every member by calling ZapOldNext()
  98
  99   void CutAllListMembers();
 100   // just make list empty, dropping members without zapping
 101
 102 public:
 103   morkNext* PopHead(); // cut head of list
 104
 105   // Note we don't support PopTail(), so use morkDeque if you need that.
 106
 107   void PushHead(morkNext* ioLink); // add to head of list
 108   void PushTail(morkNext* ioLink); // add to tail of list
 109 };
 110
 111 /*=============================================================================
 112  * morkLink: linked list node embedded in objs to allow insertion in morkDeques
 113  */
 114
 115 class morkLink /*d*/ {
 116 public:
 117   morkLink*  mLink_Next;
 118   morkLink*  mLink_Prev;
 119
 120 public:
 121   morkLink(int inZero) : mLink_Next( 0 ), mLink_Prev( 0 ) { }
 122
 123   morkLink(); // mLink_Next( 0 ), mLink_Prev( 0 ) { }
 124
 125 public:
 126   morkLink*  Next() const { return mLink_Next; }
 127   morkLink*  Prev() const { return mLink_Prev; }
 128
 129   void SelfRefer() { mLink_Next = mLink_Prev = this; }
 130   void Clear() { mLink_Next = mLink_Prev = 0; }
 131
 132   void AddBefore(morkLink* old)
 133   {
 134     ((old)->mLink_Prev->mLink_Next = (this))->mLink_Prev = (old)->mLink_Prev;
 135     ((this)->mLink_Next = (old))->mLink_Prev = this;
 136   }
 137
 138   void AddAfter(morkLink* old)
 139   {
 140     ((old)->mLink_Next->mLink_Prev = (this))->mLink_Next = (old)->mLink_Next;
 141     ((this)->mLink_Prev = (old))->mLink_Next = this;
 142   }
 143
 144   void Remove()
 145   {
 146     (mLink_Prev->mLink_Next = mLink_Next)->mLink_Prev = mLink_Prev;
 147   }
 148
 149 public: // link memory management methods
 150   static void* MakeNewLink(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev);
 151   void ZapOldLink(morkEnv* ev, nsIMdbHeap* ioHeap);
 152
 153 public: // link memory management operators
 154   void* operator new(size_t inSize, nsIMdbHeap& ioHeap, morkEnv* ev) CPP_THROW_NEW
 155   { return morkLink::MakeNewLink(inSize, ioHeap, ev); }
 156
 157 };
 158
 159 /*=============================================================================
 160  * morkDeque: doubly linked list modeled after VAX queue instructions
 161  */
 162
 163 class morkDeque /*d*/ {
 164 public:
 165   morkLink  mDeque_Head;
 166
 167 public: // construction
 168   morkDeque(); // { mDeque_Head.SelfRefer(); }
 169
 170 public:// methods
 171   morkLink* RemoveFirst();
 172
 173   morkLink* RemoveLast();
 174
 175   morkLink* At(mork_pos index) const ; /* one-based, not zero-based */
 176
 177   mork_pos IndexOf(const morkLink* inMember) const;
 178     /* one-based index ; zero means member is not in deque */
 179
 180   mork_num Length() const;
 181
 182   /* the following method is more efficient for long lists: */
 183   int LengthCompare(mork_num inCount) const;
 184   /* -1: length < count, 0: length == count,  1: length > count */
 185
 186 public: // inlines
 187
 188   mork_bool IsEmpty()const
 189   { return (mDeque_Head.mLink_Next == (morkLink*) &mDeque_Head); }
 190
 191   morkLink* After(const morkLink* old) const
 192   { return (((old)->mLink_Next != &mDeque_Head)?
 193             (old)->mLink_Next : (morkLink*) 0); }
 194
 195   morkLink* Before(const morkLink* old) const
 196   { return (((old)->mLink_Prev != &mDeque_Head)?
 197             (old)->mLink_Prev : (morkLink*) 0); }
 198
 199   morkLink*  First() const
 200   { return ((mDeque_Head.mLink_Next != &mDeque_Head)?
 201     mDeque_Head.mLink_Next : (morkLink*) 0); }
 202
 203   morkLink*  Last() const
 204   { return ((mDeque_Head.mLink_Prev != &mDeque_Head)?
 205     mDeque_Head.mLink_Prev : (morkLink*) 0); }
 206
 207 /*
 208 From IronDoc documentation for AddFirst:
 209 +--------+   +--------+      +--------+   +--------+   +--------+
 210 | h.next |-->| b.next |      | h.next |-->| a.next |-->| b.next |
 211 +--------+   +--------+  ==> +--------+   +--------+   +--------+
 212 | h.prev |<--| b.prev |      | h.prev |<--| a.prev |<--| b.prev |
 213 +--------+   +--------+      +--------+   +--------+   +--------+
 214 */
 215
 216   void AddFirst(morkLink* in) /*i*/
 217   {
 218     ( (mDeque_Head.mLink_Next->mLink_Prev =
 219       (in))->mLink_Next = mDeque_Head.mLink_Next,
 220         ((in)->mLink_Prev = &mDeque_Head)->mLink_Next = (in) );
 221   }
 222 /*
 223 From IronDoc documentation for AddLast:
 224 +--------+   +--------+      +--------+   +--------+   +--------+
 225 | y.next |-->| h.next |      | y.next |-->| z.next |-->| h.next |
 226 +--------+   +--------+  ==> +--------+   +--------+   +--------+
 227 | y.prev |<--| h.prev |      | y.prev |<--| z.prev |<--| h.prev |
 228 +--------+   +--------+      +--------+   +--------+   +--------+
 229 */
 230
 231   void AddLast(morkLink* in)
 232   {
 233     ( (mDeque_Head.mLink_Prev->mLink_Next =
 234       (in))->mLink_Prev = mDeque_Head.mLink_Prev,
 235         ((in)->mLink_Next = &mDeque_Head)->mLink_Prev = (in) );
 236   }
 237 };
 238
 239 #endif /* _MORKDEQUE_ */