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