1 mike  1.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.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           #include "List.h"
 37           #include "PegasusAssert.h"
 38           
 39           PEGASUS_NAMESPACE_BEGIN
 40           
 41           ListRep::ListRep(void (*destructor)(Linkable*)) : 
 42               _front(0), _back(0), _size(0)
 43 mike  1.2 {
 44               if (destructor)
 45           	_destructor = destructor;
 46               else
 47           	_destructor = 0;
 48           }
 49           
 50           ListRep::~ListRep()
 51           {
 52               PEGASUS_DEBUG_ASSERT(_magic);
 53           
 54               clear();
 55           #ifdef PEGASUS_DEBUG
 56               memset(this, 0xDD, sizeof(ListRep));
 57           #endif
 58           }
 59           
 60           void ListRep::clear()
 61           {
 62               PEGASUS_DEBUG_ASSERT(_magic);
 63           
 64 mike  1.2     if (_destructor)
 65               {
 66           	// Reset _front, _back, and _size in case the destructor calls
 67           	// a method of List.
 68           
 69           	Linkable* front = _front;
 70           	Linkable* back = _back;
 71           	size_t size= _size;
 72           
 73           	_front = 0;
 74           	_back = 0;
 75           	_size = 0;
 76           
 77           	for (Linkable* p = front; p; )
 78           	{
 79           	    PEGASUS_DEBUG_ASSERT(p->magic);
 80           	    Linkable* next = p->next;
 81           	    p->list = 0;
 82           	    _destructor(p);
 83           	    p = next;
 84           	}
 85 mike  1.2     }
 86           }
 87           
 88           void ListRep::insert_front(Linkable* elem)
 89           {
 90               PEGASUS_DEBUG_ASSERT(_magic);
 91               PEGASUS_DEBUG_ASSERT(elem != 0);
 92               PEGASUS_DEBUG_ASSERT(elem->magic);
 93               PEGASUS_DEBUG_ASSERT(elem->list == 0);
 94           
 95               elem->list = this;
 96               elem->next = _front;
 97               elem->prev = 0;
 98           
 99               if (_front)
100           	_front->prev = elem;
101               else
102           	_back = elem;
103           
104               _front = elem;
105               _size++;
106 mike  1.2 }
107           
108           void ListRep::insert_back(Linkable* elem)
109           {
110               PEGASUS_DEBUG_ASSERT(_magic);
111               PEGASUS_DEBUG_ASSERT(elem != 0);
112               PEGASUS_DEBUG_ASSERT(elem->magic);
113               PEGASUS_DEBUG_ASSERT(elem->list == 0);
114           
115               elem->list = this;
116               elem->prev = _back;
117               elem->next = 0;
118           
119               if (_back)
120           	_back->next = elem;
121               else
122           	_front = elem;
123           
124               _back = elem;
125               _size++;
126           }
127 mike  1.2 
128           void ListRep::insert_after(
129               Linkable* pos, 
130               Linkable* elem)
131           {
132               PEGASUS_DEBUG_ASSERT(_magic);
133               PEGASUS_DEBUG_ASSERT(pos != 0);
134               PEGASUS_DEBUG_ASSERT(elem != 0);
135               PEGASUS_DEBUG_ASSERT(elem->magic);
136               PEGASUS_DEBUG_ASSERT(pos->magic);
137               PEGASUS_DEBUG_ASSERT(elem->list == 0);
138           
139               elem->list = this;
140               elem->prev = pos;
141               elem->next = pos->next;
142           
143               if (pos->next)
144           	pos->next->prev = elem;
145           
146               pos->next = elem;
147           
148 mike  1.2     if (pos == _back)
149           	_back = elem;
150           
151               _size++;
152           }
153           
154           void ListRep::insert_before(
155               Linkable* pos, 
156               Linkable* elem)
157           {
158               PEGASUS_DEBUG_ASSERT(_magic);
159               PEGASUS_DEBUG_ASSERT(pos != 0);
160               PEGASUS_DEBUG_ASSERT(elem != 0);
161               PEGASUS_DEBUG_ASSERT(pos->magic);
162               PEGASUS_DEBUG_ASSERT(elem->magic);
163               PEGASUS_DEBUG_ASSERT(elem->list == 0);
164           
165               elem->list = this;
166               elem->next = pos;
167               elem->prev = pos->prev;
168           
169 mike  1.2     if (pos->prev)
170           	pos->prev->next = elem;
171           
172               pos->prev = elem;
173           
174               if (pos == _front)
175           	_front = elem;
176           
177               _size++;
178           }
179           
180           void ListRep::remove(Linkable* pos)
181           {
182               PEGASUS_DEBUG_ASSERT(_magic);
183               PEGASUS_DEBUG_ASSERT(pos != 0);
184               PEGASUS_DEBUG_ASSERT(pos->magic);
185               PEGASUS_DEBUG_ASSERT(pos->list == this);
186               PEGASUS_DEBUG_ASSERT(_size != 0);
187           
188               if (_size == 0)
189           	return;
190 mike  1.2 
191               if (pos->prev)
192           	pos->prev->next = pos->next;
193           
194               if (pos->next)
195           	pos->next->prev = pos->prev;
196           
197               if (pos == _front)
198           	_front = pos->next;
199           
200               if (pos == _back)
201           	_back = pos->prev;
202           
203               pos->list = 0;
204           
205               _size--;
206           }
207           
208           bool ListRep::contains(const Linkable* elem)
209           {
210               PEGASUS_DEBUG_ASSERT(_magic);
211 mike  1.2     PEGASUS_DEBUG_ASSERT(elem != 0);
212               PEGASUS_DEBUG_ASSERT(elem->magic);
213           
214               for (const Linkable* p = _front; p; p = p->next)
215               {
216           	if (p == elem)
217           	    return true;
218               }
219           
220               // Not found!
221               return false;
222           }
223           
224           Linkable* ListRep::remove_front()
225           {
226               PEGASUS_DEBUG_ASSERT(_magic);
227           
228               if (_size == 0)
229           	return 0;
230           
231               Linkable* elem = _front;
232 mike  1.2     remove(elem);
233           
234               return elem;
235           }
236           
237           Linkable* ListRep::remove_back()
238           {
239               PEGASUS_DEBUG_ASSERT(_magic);
240               PEGASUS_DEBUG_ASSERT(_size > 0);
241           
242               Linkable* elem = _back;
243               remove(elem);
244           
245               return elem;
246           }
247           
248           Linkable* ListRep::find(ListRep::Equal equal, const void* client_data)
249           {
250               PEGASUS_DEBUG_ASSERT(_magic);
251               PEGASUS_DEBUG_ASSERT(equal != 0);
252           
253 mike  1.2     for (Linkable* p = _front; p; p = p->next)
254               {
255           	if ((*equal)(p, client_data))
256           	{
257           	    PEGASUS_DEBUG_ASSERT(p->magic);
258           	    return p;
259           	}
260               }
261           
262               // Not found!
263               return 0;
264           }
265           
266           Linkable* ListRep::remove(ListRep::Equal equal, const void* client_data)
267           {
268               PEGASUS_DEBUG_ASSERT(_magic);
269               PEGASUS_DEBUG_ASSERT(equal != 0);
270           
271               Linkable* p = find(equal, client_data);
272           
273               if (p)
274 mike  1.2     {
275           	PEGASUS_DEBUG_ASSERT(p->magic);
276           	remove(p);
277               }
278           
279               return p;
280           }
281           
282           void ListRep::apply(ListRep::Apply apply, const void* client_data)
283           {
284               PEGASUS_DEBUG_ASSERT(_magic);
285               PEGASUS_DEBUG_ASSERT(apply != 0);
286           
287               for (Linkable* p = _front; p; p = p->next)
288           	(*apply)(p, client_data);
289           }
290           
291           PEGASUS_NAMESPACE_END