1 mike 1.1.2.2 //%2006////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
4 // Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
6 // IBM Corp.; EMC Corporation, The Open Group.
7 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
9 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
11 // Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.;
12 // EMC Corporation; Symantec Corporation; The Open Group.
13 //
14 // Permission is hereby granted, free of charge, to any person obtaining a copy
15 // of this software and associated documentation files (the "Software"), to
16 // deal in the Software without restriction, including without limitation the
17 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
18 // sell copies of the Software, and to permit persons to whom the Software is
19 // furnished to do so, subject to the following conditions:
20 //
21 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
22 mike 1.1.2.2 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
23 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
24 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
25 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
26 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
27 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 //
30 //==============================================================================
31 //
32 // Author: Mike Brasher (m.brasher@inovadevelopment.com)
33 //
34 //%/////////////////////////////////////////////////////////////////////////////
35
|
36 mike 1.1.2.1 #include "List.h"
|
37 mike 1.1.2.2 #include "PegasusAssert.h"
|
38 mike 1.1.2.1
39 #ifdef PEGASUS_LINKABLE_SANITY
|
40 mike 1.1.2.2 # define PEGASUS_LIST_ASSERT(COND) PEGASUS_ASSERT(COND)
|
41 mike 1.1.2.1 #else
|
42 mike 1.1.2.2 # define PEGASUS_LIST_ASSERT(COND) /* empty */
|
43 mike 1.1.2.1 #endif
44
|
45 mike 1.1.2.2 #define PEGASUS_LIST_MAGIC 0x6456FD0A
|
46 mike 1.1.2.1
47 PEGASUS_NAMESPACE_BEGIN
48
49 ListRep::ListRep(void (*destructor)(Linkable*)) :
50 _magic(PEGASUS_LIST_MAGIC), _front(0), _back(0), _size(0)
51 {
52 if (destructor)
53 _destructor = destructor;
54 else
55 _destructor = 0;
56 }
57
58 ListRep::~ListRep()
59 {
|
60 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
|
61 mike 1.1.2.1
62 clear();
63 #ifdef PEGASUS_LINKABLE_SANITY
64 memset(this, 0xDD, sizeof(ListRep));
65 #endif
66 }
67
68 void ListRep::clear()
69 {
|
70 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
|
71 mike 1.1.2.1
72 if (_destructor)
73 {
|
74 mike 1.1.2.4 // Reset _front, _back, and _size in case the destructor calls
75 // a method of List.
|
76 mike 1.1.2.3
77 Linkable* front = _front;
78 Linkable* back = _back;
79 size_t size= _size;
80
81 _front = 0;
82 _back = 0;
83 _size = 0;
84
85 for (Linkable* p = front; p; )
|
86 mike 1.1.2.1 {
|
87 mike 1.1.2.2 PEGASUS_LIST_ASSERT(p->magic == PEGASUS_LINKABLE_MAGIC);
|
88 mike 1.1.2.1 Linkable* next = p->next;
89 _destructor(p);
90 p = next;
91 }
92 }
93 }
94
95 void ListRep::insert_front(Linkable* elem)
96 {
|
97 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
98 PEGASUS_LIST_ASSERT(elem != 0);
99 PEGASUS_LIST_ASSERT(elem->magic == PEGASUS_LINKABLE_MAGIC);
100 PEGASUS_LIST_ASSERT(elem->list == 0);
|
101 mike 1.1.2.1
102 elem->list = this;
103 elem->next = _front;
104 elem->prev = 0;
105
106 if (_front)
107 _front->prev = elem;
108 else
109 _back = elem;
110
111 _front = elem;
112 _size++;
113 }
114
115 void ListRep::insert_back(Linkable* elem)
116 {
|
117 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
118 PEGASUS_LIST_ASSERT(elem != 0);
119 PEGASUS_LIST_ASSERT(elem->magic == PEGASUS_LINKABLE_MAGIC);
120 PEGASUS_LIST_ASSERT(elem->list == 0);
|
121 mike 1.1.2.1
122 elem->list = this;
123 elem->prev = _back;
124 elem->next = 0;
125
126 if (_back)
127 _back->next = elem;
128 else
129 _front = elem;
130
131 _back = elem;
132 _size++;
133 }
134
135 void ListRep::insert_after(
136 Linkable* pos,
137 Linkable* elem)
138 {
|
139 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
140 PEGASUS_LIST_ASSERT(pos != 0);
141 PEGASUS_LIST_ASSERT(elem != 0);
142 PEGASUS_LIST_ASSERT(elem->magic == PEGASUS_LINKABLE_MAGIC);
143 PEGASUS_LIST_ASSERT(pos->magic == PEGASUS_LINKABLE_MAGIC);
144 PEGASUS_LIST_ASSERT(elem->list == 0);
|
145 mike 1.1.2.1
146 elem->list = this;
147 elem->prev = pos;
148 elem->next = pos->next;
149
150 if (pos->next)
151 pos->next->prev = elem;
152
153 pos->next = elem;
154
155 if (pos == _back)
156 _back = elem;
157
158 _size++;
159 }
160
161 void ListRep::insert_before(
162 Linkable* pos,
163 Linkable* elem)
164 {
|
165 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
166 PEGASUS_LIST_ASSERT(pos != 0);
167 PEGASUS_LIST_ASSERT(elem != 0);
168 PEGASUS_LIST_ASSERT(pos->magic == PEGASUS_LINKABLE_MAGIC);
169 PEGASUS_LIST_ASSERT(elem->magic == PEGASUS_LINKABLE_MAGIC);
170 PEGASUS_LIST_ASSERT(elem->list == 0);
|
171 mike 1.1.2.1
172 elem->list = this;
173 elem->next = pos;
174 elem->prev = pos->prev;
175
176 if (pos->prev)
177 pos->prev->next = elem;
178
179 pos->prev = elem;
180
181 if (pos == _front)
182 _front = elem;
183
184 _size++;
185 }
186
187 void ListRep::remove(Linkable* pos)
188 {
|
189 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
190 PEGASUS_LIST_ASSERT(pos != 0);
191 PEGASUS_LIST_ASSERT(pos->magic == PEGASUS_LINKABLE_MAGIC);
192 PEGASUS_LIST_ASSERT(pos->list == this);
193 PEGASUS_LIST_ASSERT(_size != 0);
|
194 mike 1.1.2.1
195 if (_size == 0)
196 return;
197
198 if (pos->prev)
199 pos->prev->next = pos->next;
200
201 if (pos->next)
202 pos->next->prev = pos->prev;
203
204 if (pos == _front)
205 _front = pos->next;
206
207 if (pos == _back)
208 _back = pos->prev;
209
210 pos->list = 0;
211
212 _size--;
213 }
214
215 mike 1.1.2.1 bool ListRep::contains(const Linkable* elem)
216 {
|
217 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
218 PEGASUS_LIST_ASSERT(elem != 0);
219 PEGASUS_LIST_ASSERT(elem->magic == PEGASUS_LINKABLE_MAGIC);
|
220 mike 1.1.2.1
221 for (const Linkable* p = _front; p; p = p->next)
222 {
223 if (p == elem)
224 return true;
225 }
226
227 // Not found!
228 return false;
229 }
230
231 Linkable* ListRep::remove_front()
232 {
|
233 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
|
234 mike 1.1.2.1
235 if (_size == 0)
236 return 0;
237
238 Linkable* elem = _front;
239 remove(elem);
240
241 return elem;
242 }
243
244 Linkable* ListRep::remove_back()
245 {
|
246 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
247 PEGASUS_LIST_ASSERT(_size > 0);
|
248 mike 1.1.2.1
249 Linkable* elem = _back;
250 remove(elem);
251
252 return elem;
253 }
254
255 Linkable* ListRep::find(ListRep::Equal equal, const void* client_data)
256 {
|
257 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
258 PEGASUS_LIST_ASSERT(equal != 0);
|
259 mike 1.1.2.1
260 for (Linkable* p = _front; p; p = p->next)
261 {
262 if ((*equal)(p, client_data))
263 {
|
264 mike 1.1.2.2 PEGASUS_LIST_ASSERT(p->magic == PEGASUS_LINKABLE_MAGIC);
|
265 mike 1.1.2.1 return p;
266 }
267 }
268
269 // Not found!
270 return 0;
271 }
272
273 Linkable* ListRep::remove(ListRep::Equal equal, const void* client_data)
274 {
|
275 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
276 PEGASUS_LIST_ASSERT(equal != 0);
|
277 mike 1.1.2.1
278 Linkable* p = find(equal, client_data);
279
280 if (p)
281 {
|
282 mike 1.1.2.2 PEGASUS_LIST_ASSERT(p->magic == PEGASUS_LINKABLE_MAGIC);
|
283 mike 1.1.2.1 remove(p);
284 }
285
286 return p;
287 }
288
289 void ListRep::apply(ListRep::Apply apply, const void* client_data)
290 {
|
291 mike 1.1.2.2 PEGASUS_LIST_ASSERT(_magic == PEGASUS_LIST_MAGIC);
292 PEGASUS_LIST_ASSERT(apply != 0);
|
293 mike 1.1.2.1
294 for (Linkable* p = _front; p; p = p->next)
295 (*apply)(p, client_data);
296 }
297
298 PEGASUS_NAMESPACE_END
|