← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/db/mork/src/morkDeque.h

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/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_ */