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