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