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 //%/////////////////////////////////////////////////////////////////////////////
33
34 #ifndef _Pegasus_Common_List_h
35 #define _Pegasus_Common_List_h
36
37 #include <Pegasus/Common/Config.h>
38 #include <Pegasus/Common/Linkage.h>
39 #include <Pegasus/Common/Linkable.h>
40 #include <Pegasus/Common/Magic.h>
41
42 PEGASUS_NAMESPACE_BEGIN
43 mike 1.2
44 /** The NullLock class can be passed as the LockType template parameter to the
|
45 kumpf 1.4 List template class. The NullLock implements no-ops for the lock(),
|
46 mike 1.2 try_lock() and unlock() operations.
47 */
48 class NullLock
49 {
50 public:
51
52 /** no-op lock().
53 */
54 void lock() { }
55
56 /** no-op try_lock().
57 */
58 void try_lock() { }
59
60 /** no-op unlock().
61 */
62 void unlock() { }
63 };
64
65 // Intrusive list implementation class (internal to List class).
66 class PEGASUS_COMMON_LINKAGE ListRep
67 mike 1.2 {
68 public:
69
70 typedef bool (*Equal)(const Linkable* elem, const void* client_data);
71
72 typedef void (*Apply)(const Linkable* elem, const void* client_data);
73
74 ListRep(void (*destructor)(Linkable*));
75
76 ~ListRep();
77
78 void clear();
79
|
80 kumpf 1.5 Uint32 size() const { return _size; }
|
81 mike 1.2
|
82 kumpf 1.5 Boolean empty() const { return _size == 0; }
|
83 mike 1.2
84 Linkable* front() { return _front; }
85
86 const Linkable* front() const { return _front; }
87
88 Linkable* back() { return _back; }
89
90 const Linkable* back() const { return _back; }
91
92 void next(Linkable*& elem) { elem = elem->next; };
93
94 void prev(Linkable*& elem) { elem = elem->prev; };
95
96 void insert_front(Linkable* elem);
97
98 void insert_back(Linkable* elem);
99
100 void insert_after(Linkable* pos, Linkable* elem);
101
102 void insert_before(Linkable* pos, Linkable* elem);
103
104 mike 1.2 void remove(Linkable* pos);
105
106 bool contains(const Linkable* elem);
107
108 Linkable* remove_front();
109
110 Linkable* remove_back();
111
112 Linkable* find(Equal equal, const void* client_data);
113
114 Linkable* remove(Equal equal, const void* client_data);
115
116 void apply(Apply apply, const void* client_data);
117
118 private:
119
120 ListRep(const ListRep& x) { }
121 ListRep& operator=(const ListRep& x) { return *this; }
122
123 Magic<0x6456FD0A> _magic;
124 Linkable* _front;
125 mike 1.2 Linkable* _back;
|
126 kumpf 1.5 Uint32 _size;
|
127 mike 1.2 void (*_destructor)(Linkable*);
128 };
129
130 /** The List class implements an intrusive linked list. We say it is intrusive
|
131 kumpf 1.4 because the element class must derive from Linkable, which provides the
132 link fields used by this implementation. An intrusive implementation has
|
133 mike 1.2 two main benefits: it is more efficient and uses less memory. Recall that
134 a non-intrusive linked list must allocate an additional "node" object that
135 contains the links fields as well as a pointer to the element. This implies
136 that removal is O(N) since an element must be located before it can be
137 removed. Also, the extra memory object compromises space and efficiency.
138
139 The List template takes two arguments: the element type and the lock type.
140 Again, the element type must derive from Linkable. The lock type is used
|
141 kumpf 1.4 to synchronize access to the list operations and can be any class that
|
142 mike 1.2 implements these methods: lock(), try_lock(), unlock(). Here are three
143 classes that can be used as the lock type.
144
145 - NullLock - no locking at all.
146 - Mutex - non-recursive mutex.
|
147 mike 1.3 - Mutex - recursive mutex.
|
148 mike 1.2
|
149 kumpf 1.4 Now we consider an example. So you want to create a list of Person
|
150 mike 1.2 elements. First you must derive from the Linkable class as shown below.
151
|
152 kumpf 1.4 \code
153 class Person : public Linkable
154 {
155 Person(const String& name);
156 .
157 .
158 .
159 }
160 \endcode
|
161 mike 1.2
162 Linkable is a non-virtual base class and contains the link fields this
163 implementation will use to place Person elements onto the list. Second,
164 you must instantiate the List template. Here are three possibilities.
165
|
166 kumpf 1.4 \code
167 List<Person, NullLink>; // Do no synchronization.
168 List<Person, Mutex>; // Use Mutex class to synchronize.
169 List<Person, Mutex>; // Use Mutex class to synchronize.
170 \endcode
|
171 mike 1.2
172 Finally, use the list. The following example adds three Person objects
173 to the back of the list and removes one from the front.
174
|
175 kumpf 1.4 \code
176 typedef List<Person, Mutex> PersonList;
177 PersonList list;
178
179 list.insert_back(new Person("John"));
180 list.insert_back(new Person("Mary"));
181 list.insert_back(new Person("Jane"));
|
182 mike 1.2
|
183 kumpf 1.4 Person* person = list.remove_front();
184 \endcode
|
185 mike 1.2
|
186 kumpf 1.4 One recurring usage pattern is exhausting the elements of a list. For
|
187 mike 1.2 example (this is thread-safe).
188
|
189 kumpf 1.4 \code
190 Person* person;
|
191 mike 1.2
|
192 kumpf 1.4 while ((person = list.remove_front())
193 {
194 // Do something with person here.
195 }
196 \endcode
|
197 mike 1.2
198 Another pattern is to iterate the elements of the list, which requires a
199 lock for the duration of the iteration. For example:
200
|
201 kumpf 1.4 \code
202 list.lock();
|
203 mike 1.2
|
204 kumpf 1.4 for (Person* p = list.front(); p; p = list.next_of(p))
205 {
206 // Use p here!
207 }
|
208 mike 1.2
|
209 kumpf 1.4 list.unlock();
210 \endcode
|
211 mike 1.2
212 Beware that this pattern fails for non-recursive mutexes since the mutex
213 is locked once by our example and again by front(). You may have noticed
214 that if an exception is thrown before unlock(), that the mutex will
215 remain locked. For this reason, the List class contains an AutoLock class
|
216 kumpf 1.4 that will automatically release the mutex. We now rework the previous
|
217 mike 1.2 example to use an AutoLock object.
218
|
219 kumpf 1.4 \code
220 {
221 PersonList::AutoLock autoLock(list);
222
223 for (Person* p = list.front(); p; p = list.next_of(p))
224 {
225 // Use p here!
226 }
227 }
228 \endcode
|
229 mike 1.2
|
230 kumpf 1.4 The List class provides a special find function to simplify recurring
|
231 mike 1.2 lookups of an element by some specific criteria. For example, lets add an
232 equal function to our Person class as follows:
233
|
234 kumpf 1.4 \code
235 class Person : public Linkable
236 {
237 Person(const String& name);
238 const String& name();
239
240 static bool equal(const Person* person, const char* client_data)
241 {
242 const String& name = *((const String*)client_data);
243 return person->name() == name;
244 }
245 }
246 \endcode
|
247 mike 1.2
248 This equal function may now be passed to the find() function to lookup
249 a specific person in a thread-safe way. For example:
250
|
251 kumpf 1.4 \code
252 const String name = "John";
253 Person* person = list.find(Person::equal, &name);
254
255 if (person)
256 {
257 // Found John!
258 }
259 \endcode
|
260 mike 1.2
261 Similary, we can delete "John" by using the equal-form of remove().
262
|
263 kumpf 1.4 \code
264 const String name = "John";
265 Person* person = list.remove(Person::equal, &name);
266 \endcode
|
267 mike 1.2
268 Finally, we can "apply" a function to every element of the list using
269 the apply method. For example:
270
|
271 kumpf 1.4 \code
272 static void _print(Person* person, const void* client_data)
273 {
274 printf("%s\n", (const char*)client_data);
275 person->print();
276 }
|
277 mike 1.2
|
278 kumpf 1.4 list.apply(_print, "My List");
279 \endcode
|
280 mike 1.2 */
281 template<class ElemType, class LockType>
282 class List
283 {
284 public:
285
286 typedef List<ElemType, LockType> This;
287
288 typedef bool (*Equal)(const ElemType* elem, const void* client_data);
289
290 typedef void (*Apply)(const ElemType* elem, const void* client_data);
291
292 /** Default constructor.
293 */
|
294 kumpf 1.4 List() : _rep(_destructor)
|
295 mike 1.2 {
296 }
297
298 /** Destructor.
299 */
300 ~List()
301 {
|
302 kumpf 1.4 AutoLock al(*this);
303 _rep.clear();
|
304 mike 1.2 }
305
306 /** Remove and delete all elements in this list. size() returns zero
|
307 kumpf 1.4 after this is called.
|
308 mike 1.2 */
309 void clear()
310 {
|
311 kumpf 1.4 AutoLock al(*this);
312 _rep.clear();
|
313 mike 1.2 }
314
315 /** Returns the number of elements in the list.
316 */
|
317 kumpf 1.5 Uint32 size() const
|
318 mike 1.2 {
|
319 kumpf 1.4 AutoLock al(*this);
320 return _rep.size();
|
321 mike 1.2 }
322
323 /** Returns true if the list is empty (i.e., has zero elements).
324 */
|
325 kumpf 1.5 Boolean is_empty() const
|
326 kumpf 1.4 {
327 AutoLock al(*this);
328 return _rep.empty();
|
329 mike 1.2 }
330
331 /** Obtains a pointer to the element at the front of the list.
332 */
|
333 kumpf 1.4 ElemType* front()
334 {
335 AutoLock al(*this);
336 return static_cast<ElemType*>(_rep.front());
|
337 mike 1.2 }
338
339 /** Obtains a const-pointer to the element at the front of the list.
340 */
341 const ElemType* front() const
|
342 kumpf 1.4 {
343 AutoLock al(*this);
344 return static_cast<const ElemType*>(_rep.front());
|
345 mike 1.2 }
346
347 /** Obtains a pointer to the element at the back of the list.
348 */
|
349 kumpf 1.4 ElemType* back()
350 {
351 AutoLock al(*this);
352 return static_cast<ElemType*>(_rep.back());
|
353 mike 1.2 }
354
355 /** Obtains a const-pointer to the element at the back of the list.
356 */
357 const ElemType* back() const
|
358 kumpf 1.4 {
359 AutoLock al(*this);
360 return static_cast<const ElemType*>(_rep.back());
|
361 mike 1.2 }
362
363 /** Returns the element after elem (used to iterate list).
364 */
|
365 kumpf 1.4 ElemType* next_of(ElemType* elem)
|
366 mike 1.2 {
|
367 kumpf 1.4 return static_cast<ElemType*>(elem->next);
|
368 mike 1.2 }
369
370 /** Returns the element before elem (used to iterate list).
371 */
|
372 kumpf 1.4 ElemType* prev_of(ElemType* elem)
|
373 mike 1.2 {
|
374 kumpf 1.4 return static_cast<ElemType*>(elem->prev);
|
375 mike 1.2 }
376
377 /** Insert elem at the front of the list.
378 */
379 void insert_front(ElemType* elem)
380 {
|
381 kumpf 1.4 AutoLock al(*this);
382 _rep.insert_front(elem);
|
383 mike 1.2 }
384
385 /** Insert elem at the back of the list.
386 */
387 void insert_back(ElemType* elem)
388 {
|
389 kumpf 1.4 AutoLock al(*this);
390 _rep.insert_back(elem);
|
391 mike 1.2 }
392
393 /** Insert elem after pos.
394 */
395 void insert_after(ElemType* pos, ElemType* elem)
396 {
|
397 kumpf 1.4 AutoLock al(*this);
398 _rep.insert_after(pos, elem);
|
399 mike 1.2 }
400
401 /** Insert elem before pos.
402 */
403 void insert_before(ElemType* pos, ElemType* elem)
404 {
|
405 kumpf 1.4 AutoLock al(*this);
406 _rep.insert_before(pos, elem);
|
407 mike 1.2 }
408
409 /** Remove the given element.
410 */
411 void remove(ElemType* pos)
412 {
|
413 kumpf 1.4 AutoLock al(*this);
414 _rep.remove(pos);
|
415 mike 1.2 }
416
417 /** Returns true if the list contains the given element.
418 */
419 bool contains(const ElemType* elem)
420 {
|
421 kumpf 1.4 AutoLock al(*this);
422 return _rep.contains(elem);
|
423 mike 1.2 }
424
425 /** Removes and returns the element at the front of the list.
426 */
427 ElemType* remove_front()
428 {
|
429 kumpf 1.4 AutoLock al(*this);
430 return static_cast<ElemType*>(_rep.remove_front());
|
431 mike 1.2 }
432
433 /** Removes and returns the element at the back of the list.
434 */
435 ElemType* remove_back()
436 {
|
437 kumpf 1.4 AutoLock al(*this);
438 return static_cast<ElemType*>(_rep.remove_back());
|
439 mike 1.2 }
440
441 /** Attempts to find an element in the list that satisfies the equal()
442 predicate. Returns first element satisfying equal() or null if none.
443 */
444 ElemType* find(Equal equal, const void* client_data)
445 {
|
446 kumpf 1.4 AutoLock al(*this);
447 return static_cast<ElemType*>(
448 _rep.find(ListRep::Equal(equal), client_data));
|
449 mike 1.2 }
450
451 /** Attempts to remove the element in the list that satisfies the equal()
452 predicate. Removes and returns the first element satisfying equal() or
|
453 kumpf 1.4 null if none.
|
454 mike 1.2 */
455 ElemType* remove(Equal equal, const void* client_data)
456 {
|
457 kumpf 1.4 AutoLock al(*this);
458 return static_cast<ElemType*>(
459 _rep.remove(ListRep::Equal(equal), client_data));
|
460 mike 1.2 }
461
462 /** Apply the given function to every element of the list.
463 */
464 void apply(Apply apply, const void* client_data)
465 {
|
466 kumpf 1.4 AutoLock al(*this);
467 _rep.apply(ListRep::Apply(apply), client_data);
|
468 mike 1.2 }
469
470 /** Lock the list.
471 */
472 void lock() { _lock.lock(); }
473
474 /** Try to lock the list.
475 */
476 void try_lock() { _lock.try_lock(); }
477
478 /** Unlock the list.
479 */
480 void unlock() { _lock.unlock(); }
481
482 /** Get reference to lock type.
483 */
484 LockType& getLock() const { return ((This*)this)->_lock; }
485
486 /** An instance of this class is used to lock this list on construction
|
487 kumpf 1.4 and later unlock it on destruction.
|
488 mike 1.2 */
489 class AutoLock
490 {
491 public:
492
|
493 kumpf 1.4 /**
494 */
495 AutoLock(const This& list) : _lock(list.getLock())
496 {
497 _lock.lock();
498 }
499
500 /**
501 */
502 ~AutoLock()
503 {
504 _lock.unlock();
505 }
|
506 mike 1.2
507 private:
|
508 kumpf 1.4 LockType& _lock;
|
509 mike 1.2 };
510
511 private:
512
513 static void _destructor(Linkable* ptr)
514 {
|
515 kumpf 1.4 delete static_cast<ElemType*>(ptr);
|
516 mike 1.2 }
517
518 ListRep _rep;
519 LockType _lock;
520 };
521
522 PEGASUS_NAMESPACE_END
523
524 #endif /* _Pegasus_Common_List_h */
|
Return to
List.h
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common