1 karl 1.21 //%2005////////////////////////////////////////////////////////////////////////
|
2 kumpf 1.16 //
|
3 karl 1.19 // 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 karl 1.18 // IBM Corp.; EMC Corporation, The Open Group.
|
7 karl 1.19 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
|
9 karl 1.21 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
|
11 mike 1.2 //
12 // Permission is hereby granted, free of charge, to any person obtaining a copy
|
13 kumpf 1.16 // of this software and associated documentation files (the "Software"), to
14 // deal in the Software without restriction, including without limitation the
15 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
|
16 mike 1.2 // sell copies of the Software, and to permit persons to whom the Software is
17 // furnished to do so, subject to the following conditions:
18 //
|
19 kumpf 1.16 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
|
20 mike 1.2 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
21 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
|
22 kumpf 1.16 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
23 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
24 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
|
25 mike 1.2 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 //
28 //==============================================================================
29 //
30 // Author: Mike Day (mdday@us.ibm.com)
31 //
|
32 joyce.j 1.20 // Modified By: Josephine Eskaline Joyce (jojustin@in.ibm.com) for PEP#101
|
33 mike 1.2 //
34 //%/////////////////////////////////////////////////////////////////////////////
35
36 #include <Pegasus/Common/Config.h>
|
37 kumpf 1.17 #include <Pegasus/Common/Linkage.h>
|
38 mday 1.13 #include <assert.h>
|
39 joyce.j 1.20 #include <Pegasus/Common/AutoPtr.h>
|
40 mike 1.2
41 #ifndef PEG_INTERNAL_DQ_include
42 #define PEG_INTERNAL_DQ_include
43
44 PEGASUS_NAMESPACE_BEGIN
45
46 #define PEG_DQUEUE_FIRST 0
47 #define PEG_DQUEUE_LAST 1
48
49
50 class PEGASUS_COMMON_LINKAGE internal_dq {
51 private:
52 void *_rep;
53 internal_dq *_next;
54 internal_dq *_prev;
55 internal_dq *_cur;
56 Boolean _isHead ;
57 int _count;
58
|
59 mday 1.9
|
60 mike 1.2 // unlink this node from whichever list it is on
|
61 mday 1.15 void unlink( void )
|
62 mike 1.2 {
63 _prev->_next = _next;
64 _next->_prev = _prev;
|
65 mday 1.5 _next = _prev = 0;
|
66 mike 1.2 }
67
|
68 mday 1.15 void insert_first(internal_dq & head)
|
69 mike 1.2 {
70 _prev = &head;
71 _next = head._next;
72 head._next->_prev = this;
73 head._next = this;
74 head._count++;
75 }
76
|
77 mday 1.15 void insert_last(internal_dq & head)
|
78 mike 1.2 {
79 _next = &head;
80 _prev = head._prev;
81 head._prev->_next = this;
82 head._prev = this;
83 head._count++;
84 }
85
|
86 mday 1.15 void *remove( int code )
|
87 mike 1.2 {
88 void *ret = NULL;
89
90 if( _count > 0 ) {
91 internal_dq *temp = NULL;
92 if(code == PEG_DQUEUE_FIRST )
93 temp = _next;
94 else
95 temp = _prev;
96
97 temp->unlink();
98 ret = temp->_rep;
99 // unhinge ret from temp so it doesn't get destroyed
100 temp->_rep = NULL ;
101 delete temp;
102 _count--;
103 }
104 return(ret);
105 }
106
107 public:
108 mike 1.2
109 internal_dq(Boolean head = true) : _rep(NULL), _isHead(head), _count(0)
110 {
111 _next = this;
112 _prev = this;
113 _cur = this;
114 }
115
116 virtual ~internal_dq()
117 {
|
118 mday 1.15 if (_isHead == true )
|
119 mday 1.5 empty_list();
|
120 mike 1.2 }
121
|
122 mday 1.15 void insert_first(void *element)
|
123 mike 1.2 {
124 if(element == 0)
125 return;
126
|
127 joyce.j 1.20 AutoPtr<internal_dq> ins(new internal_dq(false));
|
128 mike 1.2 ins->_rep = element;
129 ins->insert_first(*this);
|
130 joyce.j 1.20 ins.release();
|
131 mike 1.2 }
132
|
133 mday 1.15 void insert_last(void *element)
|
134 mike 1.2 {
135 if(element == 0)
136 return;
137
|
138 joyce.j 1.20 AutoPtr<internal_dq> ins(new internal_dq(false));
|
139 mike 1.2 ins->_rep = element;
140 ins->insert_last(*this);
|
141 joyce.j 1.20 ins.release();
|
142 mike 1.2 }
143
|
144 mday 1.15 virtual void empty_list( void )
|
145 mike 1.2 {
|
146 mday 1.5 if ( _isHead == true )
147 {
148 while( _count > 0 ) {
149 internal_dq *temp = _next;
150 temp->unlink();
151 if(temp->_rep != NULL)
152 ::operator delete(temp->_rep);
153 delete temp;
154 _count--;
155 }
|
156 mike 1.2 }
|
157 mday 1.5
|
158 mike 1.2 return;
159 }
160
|
161 mday 1.15 void *remove_first ( void ) { return(remove(PEG_DQUEUE_FIRST) );}
162 void *remove_last ( void ) { return(remove(PEG_DQUEUE_LAST) );}
|
163 mike 1.2
|
164 mday 1.15 void *remove(const void *key)
|
165 mike 1.2 {
|
166 mday 1.4 if(key == 0)
167 return 0;
|
168 mike 1.2 void *ret = 0;
|
169 mday 1.4
|
170 mike 1.2 if(_count > 0)
171 {
172 internal_dq *temp = _next;
173 if(_cur->_rep == key)
174 {
175 temp = _cur;
|
176 mday 1.10 _cur = _cur->_prev;
|
177 mike 1.2 }
178
179 while ( temp->_isHead == false ) {
180 if( temp->_rep == key ) {
|
181 mday 1.10 _cur = temp->_prev;
|
182 mike 1.2 temp->unlink();
183 ret = temp->_rep;
184 temp->_rep = NULL;
185 delete temp;
186 _count--;
187 break;
188 }
189 temp = temp->_next;
190 }
191 }
192 return(ret);
193 }
194
|
195 mday 1.15 void *reference(const void *key)
|
196 mike 1.2 {
197 if(key == 0)
198 return 0;
199
200 if( _count > 0 ) {
201 internal_dq *temp = _next;
202 while(temp->_isHead == false ) {
203 if(key == temp->_rep)
204 {
205 _cur = temp;
206 return(temp->_rep);
207 }
208
209 temp = temp->_next;
210 }
211 }
212 return 0;
213 }
214
|
215 mday 1.15 void *next( const void * ref)
|
216 mike 1.2 {
217 if( ref == 0)
218 _cur = _next;
219 else {
220 _cur = _cur->_next;
221 }
222 return(_cur->_rep);
223 }
224
|
225 mday 1.15 void *prev( const void * ref)
|
226 mike 1.2 {
227 if( ref == 0 )
228 _cur = _prev;
229 else {
230 _cur = _cur->_prev;
231 }
232 return(_cur->_rep);
233 }
234
|
235 mday 1.15 Boolean exists(const void *key)
|
236 mike 1.2 {
237 if(key == 0 )
238 return false;
239
240 Boolean ret = false;
241
242 if( _count > 0) {
243 internal_dq *temp = _next;
244 while(temp->_isHead == false )
245 {
246 if( temp->_rep == key )
247 {
248 ret = true;
249 break;
250 }
251 temp = temp->_next;
252 }
253 }
254 return(ret);
255 }
|
256 mday 1.15 virtual Uint32 count(void) { return _count ; }
|
257 mike 1.2 } ;
|
258 mday 1.9
259
|
260 mike 1.2
261
|
262 mday 1.6 template<class L> class PEGASUS_COMMON_LINKAGE unlocked_dq
|
263 mike 1.2 {
|
264 mday 1.6 private:
265 L *_rep;
266 unlocked_dq<L> *_next;
267 unlocked_dq<L> *_prev;
268 unlocked_dq<L> *_cur;
269 Boolean _isHead ;
270 int _count;
271
272 // unlink this node from whichever list it is on
|
273 mday 1.15 void unlink( void )
|
274 mday 1.6 {
275 _prev->_next = _next;
276 _next->_prev = _prev;
277 _next = _prev = 0;
278 }
279
|
280 mday 1.7 void insert_first(unlocked_dq<L> & head)
|
281 mday 1.6 {
|
282 mday 1.7 _prev = &head;
283 _next = head._next;
284 head._next->_prev = this;
285 head._next = this;
286 (head._count)++;
|
287 mday 1.6 }
288
|
289 mday 1.7 void insert_last(unlocked_dq<L> & head)
290 {
291 _next = &head;
292 _prev = head._prev;
293 head._prev->_next = this;
294 head._prev = this;
295 (head._count)++;
|
296 mday 1.6 }
297
|
298 mday 1.15 L *remove( int code )
|
299 mday 1.6 {
300 L *ret = NULL;
301
302 if( _count > 0 ) {
303 unlocked_dq<L> *temp = NULL;
304 if(code == PEG_DQUEUE_FIRST )
305 temp = _next;
306 else
307 temp = _prev;
308
309 temp->unlink();
310 ret = temp->_rep;
311 // unhinge ret from temp so it doesn't get destroyed
312 temp->_rep = NULL ;
313 delete temp;
314 _count--;
315 }
316 return(ret);
317 }
318
319 public:
|
320 mike 1.2
|
321 mday 1.6 unlocked_dq() : _rep(0), _isHead(false), _count(0)
322 {
|
323 mday 1.7 _next = 0;
324 _prev = 0;
325 _cur = 0;
|
326 mday 1.6 }
|
327 mike 1.2
|
328 mday 1.6 unlocked_dq(Boolean head ) : _rep(NULL), _isHead(head), _count(0)
329 {
|
330 mday 1.7 if ( _isHead == true )
331 {
332 _next = this;
333 _prev = this;
334 _cur = this;
335 }
336
|
337 mday 1.6 }
338
339 virtual ~unlocked_dq()
340 {
|
341 mday 1.15 if ( _isHead == true)
|
342 mday 1.6 empty_list();
343 }
344
|
345 mday 1.7 void insert_first(L *element)
|
346 mike 1.2 {
|
347 mday 1.4 if( element == 0 )
348 return;
|
349 mday 1.7 unlocked_dq<L> *ins = new unlocked_dq<L>(false);
|
350 mday 1.6 ins->_rep = element;
|
351 mday 1.7 ins->insert_first(*this);
|
352 mike 1.2 }
353
|
354 mday 1.7 void insert_last(L *element)
|
355 mike 1.2 {
|
356 mday 1.4 if( element == 0 )
357 return;
|
358 mday 1.6 unlocked_dq<L> *ins = new unlocked_dq<L>();
359 ins->_rep = element;
|
360 mday 1.7 ins->insert_last(*this);
|
361 mike 1.2 }
362
|
363 mday 1.15 virtual void empty_list( void )
|
364 mike 1.2 {
365
|
366 mday 1.6 if ( _isHead == true )
|
367 mday 1.4 {
|
368 mday 1.6 while( _count > 0 ) {
369 unlocked_dq<L> *temp = _next;
370 temp->unlink();
371 delete temp->_rep;
372 delete temp;
373 _count--;
374 }
|
375 mday 1.4 }
|
376 mday 1.6
377 return;
|
378 mday 1.4 }
|
379 mday 1.6
|
380 mday 1.15 L *remove_first ( void ) { return(remove(PEG_DQUEUE_FIRST) );}
381 L *remove_last ( void ) { return(remove(PEG_DQUEUE_LAST) );}
|
382 mday 1.6
|
383 mday 1.4
|
384 mday 1.15 virtual L *remove(const L *key)
|
385 mike 1.2 {
386 if(key == 0)
387 return 0;
|
388 mday 1.6 L *ret = 0;
|
389 mike 1.2
|
390 mday 1.6 if(_count > 0)
|
391 mike 1.2 {
|
392 mday 1.6 unlocked_dq<L> *temp = _next;
393 if(_cur->_rep == key)
394 {
395 temp = _cur;
396 _cur = _cur->_next;
397
398 }
399
400 while ( temp->_isHead == false ) {
401 if( temp->_rep == key ) {
402 temp->unlink();
403 ret = temp->_rep;
404 temp->_rep = NULL;
405 delete temp;
406 _count--;
407 break;
408 }
409 temp = temp->_next;
410 }
|
411 mike 1.2 }
|
412 mday 1.6 return(ret);
|
413 mike 1.2 }
|
414 mday 1.6
|
415 mike 1.2
|
416 mday 1.15 virtual L *remove(const void *key)
|
417 mike 1.2 {
|
418 mday 1.6
|
419 mday 1.4 if(key == 0)
420 return 0;
|
421 kumpf 1.8 return unlocked_dq<L>::remove(reinterpret_cast<const L *>(key));
|
422 mike 1.2 }
423
|
424 mday 1.15 virtual L *reference(const void *key)
|
425 mike 1.2 {
426 if( key == 0 )
427 return 0;
428
|
429 mday 1.6 if(_count > 0 )
|
430 mike 1.2 {
|
431 mday 1.6 L *ret = next(0);
|
432 mike 1.2 while(ret != 0)
433 {
434 if(ret->operator==(key))
435 return ret;
|
436 mday 1.6 ret = next(ret);
|
437 mike 1.2 }
438 }
439 return(0);
440 }
441
|
442 mday 1.15 virtual L *reference(const L *key)
|
443 mike 1.2 {
444 if(key == 0)
445 return 0;
446
|
447 mday 1.6 if(_count > 0 )
|
448 mike 1.2 {
|
449 mday 1.6 L *ret = next(0);
|
450 mike 1.2 while(ret != 0)
451 {
452 if(ret->operator==(key))
453 return ret;
|
454 mday 1.6 ret = next(ret);
|
455 mike 1.2 }
456 }
457 return(0);
458 }
459
|
460 mday 1.6
|
461 mday 1.15 virtual L *next(const void *ref)
|
462 mike 1.2 {
|
463 mday 1.15 assert(this->_isHead == true);
|
464 mday 1.6
465 if( ref == 0)
|
466 mday 1.7 _cur = this->_next;
|
467 mday 1.6 else {
|
468 mday 1.7 _cur = _cur->_next;
|
469 mday 1.6 }
470 return(_cur->_rep);
|
471 mike 1.2 }
472
|
473 mday 1.15 virtual L *prev(const void *ref)
|
474 mike 1.2 {
|
475 mday 1.15 assert(this->_isHead == true);
|
476 mday 1.6 if( ref == 0 )
477 _cur = _prev;
478 else {
479 _cur = _cur->_prev;
480 }
481 return(_cur->_rep);
|
482 mike 1.2 }
483
|
484 kumpf 1.8 virtual Boolean exists(const void *key)
|
485 mike 1.2 {
486 if(key == 0)
487 return false;
488
489 Boolean ret = false;
|
490 mday 1.6 if(_count > 0)
|
491 mike 1.2 {
|
492 mday 1.6 L *found = next(0);
|
493 mike 1.2 while(found != 0)
494 {
495 if(found->operator==(key) == true)
496 {
497 ret = true;
498 break;
499 }
|
500 mday 1.6 found = next(found);
|
501 mike 1.2 }
502 }
503 return(ret);
504 }
505
|
506 mday 1.15 virtual Uint32 count(void) { return _count ; }
|
507 mike 1.2 };
508
509 PEGASUS_NAMESPACE_END
510
511 #endif // PEG_INTERNAL_DQ_include
|