Mercurial > hg > webserver / file comparison

comparison: src/server/util/LinkedList.hh

src/server/util/LinkedList.hh

changeset 14
b8bf95b39952
parent 1
3c066d52342d
child 115
51d9a15eac98
equal deleted inserted replaced
13:1fdbf4170ef4 14:b8bf95b39952
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
5 *
6 * THE BSD LICENSE
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 *
17 * Neither the name of the nor the names of its contributors may be
18 * used to endorse or promote products derived from this software without
19 * specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
25 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #ifndef _LINKED_LIST_H_
35 #define _LINKED_LIST_H_
36
37 /*
38 * Provided a template implementation of a simple linked list.
39 * It is a reference based container (stores the pointers to the
40 * objects contained) It doesn't check for duplicates etc and find
41 * (delete) will find(delete) the first occurence of an element.
42 *
43 * Iterator class can be used for traversal using the "++" operator.
44 */
45 template <class C> class CList; // forward declaration
46 template <class C> class CListIterator; // forward declaration
47 template <class C> class CListConstIterator; // forward declaration
48
49 template <class C> class CListElmt {
50 friend class CList<C>;
51 friend class CListIterator<C>;
52 friend class CListConstIterator<C>;
53 private:
54 CListElmt(C* refP, int id) : _refP(refP), _nextP(0), _prevP(0), _id(id)
55 {
56 // Nothing really has to be done here
57 };
58
59
60 private:
61 int _id;
62 C *_refP;
63 #if defined(AIX)
64 CListElmt<C> *_nextP;
65 CListElmt<C> *_prevP;
66 #else
67 CListElmt *_nextP;
68 CListElmt *_prevP;
69 #endif
70 };
71
72 //
73 // NOTE : If you need the find functionality, make sure that
74 // class C has "==" defined.
75 //
76 template <class C> class CList {
77 friend class CListIterator<C>;
78 friend class CListConstIterator<C>;
79 private:
80 CListElmt<C>* _headP;
81 CListElmt<C>* _tailP;
82 CListElmt<C>* Lookup(C * memberP)
83 {
84 CListElmt<C> *curEltP = _headP;
85
86 while (curEltP)
87 {
88 if (curEltP->_refP == memberP)
89 break;
90 curEltP = curEltP->_nextP;
91 };
92 return(curEltP);
93 };
94
95 int _nextId;
96 int _numElts;
97 int autoDestroy;
98 C* Remove(CListElmt<C> *elmtP)
99 {
100 C *recP = NULL;
101 if (elmtP)
102 {
103 if (elmtP->_nextP)
104 elmtP->_nextP->_prevP = elmtP->_prevP;
105 if (elmtP->_prevP)
106 elmtP->_prevP->_nextP = elmtP->_nextP;
107 if (elmtP == _tailP)
108 _tailP = elmtP->_prevP;
109 if (elmtP == _headP)
110 _headP = _headP->_nextP;
111 recP = elmtP->_refP;
112 _numElts--;
113 delete elmtP;
114 };
115 if ( (1==autoDestroy) && recP)
116 delete recP;
117
118 return(recP);
119 };
120
121
122 public:
123 CList() : _headP(0), _tailP(0), _nextId(0), _numElts(0), autoDestroy(0)
124 {
125 // Nothing really has to be done here
126 };
127
128 void setAutoDestroy(int setting)
129 {
130 autoDestroy = setting;
131 };
132
133 virtual ~CList()
134 {
135 while (_headP)
136 Remove(_headP);
137 };
138
139 int NextId()
140 {
141 return _nextId;
142 };
143
144 int Append(C* refP)
145 {
146 CListElmt<C> *newElmtP = new CListElmt<C>(refP, _nextId++);
147 newElmtP->_prevP = _tailP;
148 if (_tailP)
149 _tailP->_nextP = newElmtP;
150 if (_headP == 0)
151 _headP = newElmtP;
152 _tailP = newElmtP;
153 _numElts++;
154 return(newElmtP->_id);
155 };
156
157 int Member(C* memberP)
158 {
159 return(Lookup(memberP) != 0);
160 };
161
162 int Delete(C* memberP)
163 {
164 CListElmt<C> *listElmtP = Lookup(memberP);
165 if (listElmtP)
166 {
167 (void) Remove(listElmtP);
168 return(1);
169 }
170 return(0);
171 };
172
173 int NumEntries() const { return _numElts; }
174 C* Find(C* memberP) // Lookup based on == operator for class C
175 {
176 CListElmt<C> *curEltP = _headP;
177
178 while (curEltP)
179 {
180 if (curEltP->_refP == memberP)
181 break;
182 curEltP = curEltP->_nextP;
183 };
184 return(curEltP ? curEltP->_refP : 0);
185 };
186
187 C* First() { return(_headP ? _headP->_refP : 0); }
188 C* Last() { return(_tailP ? _tailP->_refP : 0); }
189 };
190
191 template <class C> class CListIterator {
192 private:
193 CList<C>* _listP;
194 int _curId;
195 public:
196 CListIterator(CList<C>* linkedListP) : _listP(linkedListP), _curId(-1)
197 {
198 // Nothing more to be done
199 };
200
201 virtual ~CListIterator()
202 {
203 _listP = NULL;
204 };
205
206 C* operator++() // Define ++ operator to move forward along the list.
207 {
208 C *valueP = NULL;
209 CListElmt<C> *curEltP = _listP->_headP;
210
211 while (curEltP)
212 {
213 if (curEltP->_id > _curId)
214 {
215 _curId = curEltP->_id;
216 return(curEltP->_refP);
217 }
218 curEltP = curEltP->_nextP;
219 }
220 _curId = -1;
221 return(NULL);
222 };
223
224 void operator()() // Overload the function operator to reset the iterator
225 {
226 _curId = -1;
227 };
228
229 };
230
231 template <class C> class CListConstIterator {
232 private:
233 const CList<C>* _listP;
234 int _curId;
235 public:
236 CListConstIterator(const CList<C>* linkedListP)
237 : _listP(linkedListP), _curId(-1)
238 {
239 // Nothing more to be done
240 };
241
242 virtual ~CListConstIterator()
243 {
244 _listP = NULL;
245 };
246
247 const C* operator++() // Define ++ operator to move forward along the list.
248 {
249 const C *valueP = NULL;
250 const CListElmt<C> *curEltP = _listP->_headP;
251
252 while (curEltP)
253 {
254 if (curEltP->_id > _curId)
255 {
256 _curId = curEltP->_id;
257 return(curEltP->_refP);
258 }
259 curEltP = curEltP->_nextP;
260 }
261 _curId = -1;
262 return(NULL);
263 };
264
265 void operator()() // Overload the function operator to reset the iterator
266 {
267 _curId = -1;
268 };
269
270 };
271
272 #endif // _LINKED_LIST_H_

Mercurial Repository: webserver

mercurial