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 recP = NULL;
118 }
119
120 return(recP);
121 };
122
123
124 public:
125 CList() : _headP(0), _tailP(0), _nextId(0), _numElts(0), autoDestroy(0)
126 {
127 // Nothing really has to be done here
128 };
129
130 void setAutoDestroy(int setting)
131 {
132 autoDestroy = setting;
133 };
134
135 virtual ~CList()
136 {
137 while (_headP)
138 Remove(_headP);
139 };
140
141 int NextId()
142 {
143 return _nextId;
144 };
145
146 int Append(C* refP)
147 {
148 CListElmt<C> *newElmtP = new CListElmt<C>(refP, _nextId++);
149 newElmtP->_prevP = _tailP;
150 if (_tailP)
151 _tailP->_nextP = newElmtP;
152 if (_headP == 0)
153 _headP = newElmtP;
154 _tailP = newElmtP;
155 _numElts++;
156 return(newElmtP->_id);
157 };
158
159 int Member(C* memberP)
160 {
161 return(Lookup(memberP) != 0);
162 };
163
164 int Delete(C* memberP)
165 {
166 CListElmt<C> *listElmtP = Lookup(memberP);
167 if (listElmtP)
168 {
169 (void) Remove(listElmtP);
170 return(1);
171 }
172 return(0);
173 };
174
175 int NumEntries() const { return _numElts; }
176 C* Find(C* memberP) // Lookup based on == operator for class C
177 {
178 CListElmt<C> *curEltP = _headP;
179
180 while (curEltP)
181 {
182 if (curEltP->_refP == memberP)
183 break;
184 curEltP = curEltP->_nextP;
185 };
186 return(curEltP ? curEltP->_refP : 0);
187 };
188
189 C* First() { return(_headP ? _headP->_refP : 0); }
190 C* Last() { return(_tailP ? _tailP->_refP : 0); }
191 };
192
193 template <class C> class CListIterator {
194 private:
195 CList<C>* _listP;
196 int _curId;
197 public:
198 CListIterator(CList<C>* linkedListP) : _listP(linkedListP), _curId(-1)
199 {
200 // Nothing more to be done
201 };
202
203 virtual ~CListIterator()
204 {
205 _listP = NULL;
206 };
207
208 C* operator++() // Define ++ operator to move forward along the list.
209 {
210 C *valueP = NULL;
211 CListElmt<C> *curEltP = _listP->_headP;
212
213 while (curEltP)
214 {
215 if (curEltP->_id > _curId)
216 {
217 _curId = curEltP->_id;
218 return(curEltP->_refP);
219 }
220 curEltP = curEltP->_nextP;
221 }
222 _curId = -1;
223 return(NULL);
224 };
225
226 void operator()() // Overload the function operator to reset the iterator
227 {
228 _curId = -1;
229 };
230
231 };
232
233 template <class C> class CListConstIterator {
234 private:
235 const CList<C>* _listP;
236 int _curId;
237 public:
238 CListConstIterator(const CList<C>* linkedListP)
239 : _listP(linkedListP), _curId(-1)
240 {
241 // Nothing more to be done
242 };
243
244 virtual ~CListConstIterator()
245 {
246 _listP = NULL;
247 };
248
249 const C* operator++() // Define ++ operator to move forward along the list.
250 {
251 const C *valueP = NULL;
252 const CListElmt<C> *curEltP = _listP->_headP;
253
254 while (curEltP)
255 {
256 if (curEltP->_id > _curId)
257 {
258 _curId = curEltP->_id;
259 return(curEltP->_refP);
260 }
261 curEltP = curEltP->_nextP;
262 }
263 _curId = -1;
264 return(NULL);
265 };
266
267 void operator()() // Overload the function operator to reset the iterator
268 {
269 _curId = -1;
270 };
271
272 };
273
274 #endif // _LINKED_LIST_H_
275