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