source: trunk/include/cppbase/bs_list.h

Last change on this file was 250, checked in by umoeller, 23 years ago

Build updates, moved files from warpin.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 17.3 KB
Line 
1
2/*
3 *@@sourcefile bs_list.h:
4 * replacement for the STL list class template.
5 * All STL code has been removed from WarpIN
6 * with 0.9.14.
7 *
8 * This list class only supplies a subset of the
9 * STL list functionality. The advantages of using
10 * this new implementation though are the following:
11 *
12 * 1) This list template produces FAR less code
13 * bloat. Most code here is inlined and only
14 * consists of a couple of lines for every
15 * method, which mostly calls into the
16 * linklist.c code from the XWPhelpers. In
17 * other words, the list class template is
18 * only a wrapper around linklist.c for
19 * type-safety.
20 *
21 * 2) WarpIN compiles almost twice as fast now
22 * because the incredibly complex STL headers
23 * with all those nested templates are gone.
24 *
25 * 3) This implementation does not call copy
26 * constructors all the time. The STL is not
27 * good at managing pointers; instead, its
28 * containers assume to contain the real
29 * data at all times.
30 *
31 * By contrast, the list code here _only_
32 * operates on pointers. With list<P>, it
33 * is assumed that P is a type that was
34 * created with new and that delete can
35 * (and will) be invoked on it.
36 * You cannot instantiate the list class for
37 * a non-pointer type.
38 *
39 * The XWPHelpers linklist.c code has been used
40 * in XWorkplace forever and can be considered
41 * fairly bug-free.
42 *
43 * This header supplies two class templates:
44 *
45 * 1) list_iterator<P> is a type-safe wrapper
46 * around the LISTNODE. list_iterator++
47 * will give you the next node, for example,
48 * and *list_iterator gives you the actual
49 * data. This is very similar to the STL.
50 *
51 * 2) list<P> is a type-safe wrapper around
52 * LINKLIST. It typedefs an iterator
53 * internally so you can use list<P>::iterator
54 * as with the STL. Again, this will only
55 * handle _pointer_ types.
56 *
57 * Terminology:
58 *
59 * -- list<P>: the list itself. A template wrapper
60 * around a LINKLIST.
61 *
62 * -- list node: a node inside a list<P>, uses
63 * a LISTNODE inside.
64 *
65 * -- list<P>::iterator: a template wrapper around
66 * a LISTNODE. *(list<P>::iterator) points
67 * to the data.
68 *
69 * -- data: a pointer of type P that is stored with
70 * the list node.
71 *
72 * One more difference to the STL is that the
73 * list operates in two modes. When constructing
74 * a list<P>, the constructor expects the
75 * mode to be specified, which must be one
76 * of the following:
77 *
78 * -- STORE: whenever a node is deleted,
79 * the list should invoke delete on
80 * the data (P pointer) also.
81 *
82 * -- SHADOW: delete must not be invoked.
83 *
84 * Presently, the list constructor enforces the
85 * mode to be specified to make sure that the
86 * implementor makes a decision about which list
87 * mode should be used. This might change in
88 * the future.
89 *
90 * Example usage:
91 *
92 + struct MYSTRUCT
93 + {
94 + int dummy;
95 +
96 + MYSTRUCT(i) {dummy = i;}
97 + }
98 +
99 + // create a list of MYSTRUCT pointers
100 + list<MYSTRUCT*> MyList(STORE);
101 + // store new MYSTRUCT's in the list
102 + MyList.push_back(new MYSTRUCT(1));
103 + MyList.push_back(new MYSTRUCT(2));
104 +
105 + // now run through the list
106 + list<MYSTRUCT*>::iterator start, end;
107 + start = MyList.begin(); // returns first list node
108 + end = MyList.end(); // returns past last list node
109 + while (start != end) // for all items
110 + {
111 + MYSTRUCT *pData = *start; // dereference the data
112 + if (pData->dummy == 2)
113 + break;
114 +
115 + // next list node
116 + start++
117 + }
118 *
119 *@@added V0.9.14 (2001-07-12) [umoeller]
120 *@@include #include "helpers\linklist.h"
121 */
122
123#ifndef BSLIST_INCLUDED
124 #define BSLIST_INCLUDED
125
126 /* ******************************************************************
127 *
128 * Replacement list class template
129 *
130 ********************************************************************/
131
132 #include "helpers\linklist.h"
133
134 template <class P>
135 class list;
136
137 /*
138 *@@ list_iterator:
139 * a list_iterator<P> is a LISTNODE
140 * whose pNode->pItemData == P.
141 *
142 * list<P> typedefs list<P>::iterator
143 * to be a list_iterator<P>.
144 *
145 * P must be deletable (i.e. created
146 * on the heap with new()).
147 */
148
149 template <class P>
150 class list_iterator
151 {
152 /*
153 public:
154 void* operator new(size_t n) { return malloc(n);};
155 void operator delete(void* p) { free(p);};
156 */
157
158 public:
159 PLISTNODE pNode;
160
161 /*
162 *@@ list_iterator:
163 * constructor.
164 */
165
166 inline list_iterator()
167 {
168 pNode = 0;
169 }
170
171 /*
172 *@@ list_iterator:
173 * copy constructor to convert from a
174 * PLISTNODE.
175 */
176
177 inline list_iterator(const PLISTNODE p)
178 {
179 pNode = p;
180 }
181
182 /*
183 *@@ ~list_iterator:
184 * destructor. Does nothing.
185 */
186
187 inline ~list_iterator()
188 {
189
190 }
191
192 /*
193 *@@ operator++:
194 * overloaded prefix ++ operator so we
195 * can easily run thru the list nodes.
196 */
197
198 void inline operator++()
199 {
200 if (pNode)
201 pNode = pNode->pNext;
202 }
203
204 /*
205 *@@ operator++:
206 * overloaded postfix ++ operator so
207 * we can easily run thru the list nodes.
208 *
209 * The int i is just stupid C++ syntax, the
210 * int is always zero, it's just for
211 * distinguishing between prefix and postfix.
212 */
213
214 void inline operator++(int i)
215 {
216 if (pNode)
217 pNode = pNode->pNext;
218 }
219 };
220
221 template <class P>
222 bool inline operator==(list_iterator<P> &p1, list_iterator<P> &p2)
223 {
224 return (p1.pNode == p2.pNode);
225 }
226
227 template <class P>
228 bool inline operator==(const list_iterator<P> &p1, const list_iterator<P> &p2)
229 {
230 return (p1.pNode == p2.pNode);
231 }
232
233 template <class P>
234 bool inline operator!=(list_iterator<P> &p1, list_iterator<P> &p2)
235 {
236 return (p1.pNode != p2.pNode);
237 }
238
239 template <class P>
240 P inline operator*(list_iterator<P> &p)
241 {
242 return (P)p.pNode->pItemData;
243 }
244
245 /*
246 *@@ list_reverse_iterator:
247 *
248 */
249
250 template <class T>
251 class list_reverse_iterator : public list_iterator<T>
252 {
253 public:
254 inline list_reverse_iterator()
255 : list_iterator<T>()
256 {
257 }
258
259 inline list_reverse_iterator(const PLISTNODE p)
260 : list_iterator<T>(p)
261 {
262 }
263
264 void inline operator++()
265 {
266 if (pNode)
267 pNode = pNode->pPrevious;
268 }
269
270 // overload postfix ++ operator: first arg is class, second is int
271 // (stupid compiler syntax, the int is always zero, it's just
272 // for distinguishing between prefix and postfix)
273 void inline operator++(int i)
274 {
275 if (pNode)
276 pNode = pNode->pPrevious;
277 }
278 };
279
280 enum LISTMODE {SHADOW, STORE};
281
282 /*
283 *@@ list:
284 * a list<P> is a list whose LISTNODES
285 * point to instances of P.
286 *
287 * As opposed to the STL list, this does
288 * not store copies of the data. Instead,
289 * it is assumed that P is deletable. It
290 * must be a pointer and have been created
291 * with new().
292 *
293 * A list can operate in two modes. In
294 * "shadow" mode, the list will not invoke
295 * delete on the data pointers when the
296 * nodes are removed. In "store" mode,
297 * it will. It is not a good idea to have
298 * to "store" lists point to the same
299 * data members; in general, if you have
300 * several lists pointing to the same data,
301 * you should have one master list in
302 * "store" mode only.
303 */
304
305 template <class P>
306 class list
307 {
308 /*
309 public:
310 void* operator new( size_t n) { return malloc(n);};
311 void operator delete( void* p) { free(p);};
312 */
313
314 public:
315 const LISTMODE _mode;
316
317 protected:
318 LINKLIST ll;
319
320 void KillNode(PLISTNODE p)
321 {
322 P p2 = (P)p->pItemData;
323
324 #ifdef __DEBUG__
325 BSRoot::WriteToDebugLog("list::KillNode for %s at 0x%lX\n",
326 p2->QueryClassName(),
327 p2);
328 #endif
329
330 if (_mode == STORE)
331 delete p2;
332 lstRemoveNode(&ll, p);
333 }
334
335 /*
336 *@@ CopyFrom:
337 * private helper for copy constructors and such.
338 */
339
340 void CopyFrom(const list<P> &llSource)
341 {
342 PLISTNODE p = lstQueryFirstNode((PLINKLIST)&llSource.ll);
343 while (p)
344 {
345 lstAppendItem(&ll, p->pItemData);
346
347 p = p->pNext;
348 }
349 }
350
351 public:
352 typedef list_iterator<P> iterator;
353 typedef list_reverse_iterator<P> reverse_iterator;
354
355 /*
356 *@@ list:
357 * default constructor.
358 */
359
360 list(LISTMODE mode) // = SHADOW)
361 : _mode(mode)
362 {
363 lstInit(&ll, FALSE);
364 }
365
366 // copy constructor
367 list(const list<P> &llSource)
368 : _mode(SHADOW)
369 {
370 CopyFrom(llSource);
371 }
372
373 /*
374 *@@ ~list:
375 * destructor.
376 *
377 * If the list is in STORE mode,
378 * delete will be invoked on each
379 * list data item as well.
380 */
381
382 ~list()
383 {
384 clear();
385 }
386
387 /*
388 *@@ operator=:
389 * copies the list nodes, but does NOT
390 * copy the data nodes.
391 */
392
393 const list<P> operator=(const list<P> &llSource)
394 {
395 CopyFrom(llSource);
396 return *this;
397 }
398
399 /*
400 *@@ push_front:
401 *
402 */
403
404 void inline push_front(const P p)
405 {
406 lstInsertItemBefore(&ll,
407 p,
408 0); // index to insert before
409 }
410
411 /*
412 *@@ push_back:
413 *
414 */
415
416 void inline push_back(const P p)
417 {
418 lstAppendItem(&ll, p);
419 }
420
421 /*
422 *@@ remove:
423 * removes the list node which
424 * points to the specified data
425 * item.
426 *
427 * If the list is in STORE mode,
428 * delete will be invoked on p's
429 * data item as well.
430 */
431
432 void inline remove(P p)
433 {
434 PLISTNODE pNode = lstNodeFromItem(&ll, p);
435 if (pNode)
436 KillNode(pNode);
437 }
438
439 /*
440 *@@ pop_back:
441 * removes the last element.
442 *
443 * If the list is in STORE mode,
444 * delete will be invoked on the
445 * data item as well.
446 */
447
448 void inline pop_back()
449 {
450 PLISTNODE pNode = lstQueryLastNode(&ll);
451 if (pNode)
452 KillNode(pNode);
453 }
454
455 /*
456 *@@ erase:
457 * erases the specified list node.
458 * Returns the node after that node
459 * or end().
460 *
461 * If the list is in STORE mode,
462 * delete will be invoked on the
463 * data item as well.
464 */
465
466 void inline erase(iterator pos)
467 {
468 KillNode(pos.pNode);
469 }
470
471 /*
472 *@@ erase:
473 *
474 * If the list is in STORE mode,
475 * delete will be invoked on each
476 * list data item as well.
477 */
478
479 void inline erase(iterator first, // first to erase
480 iterator last) // last to erase (not included)
481 {
482 PLISTNODE p = first.pNode;
483 while (p)
484 {
485 PLISTNODE pNext = p->pNext;
486
487 KillNode(p);
488
489 p = pNext;
490 if (p == last.pNode)
491 break;
492 }
493 }
494
495 /*
496 *@@ clear:
497 * empties the entire list.
498 *
499 * If the list is in STORE mode,
500 * delete will be invoked on each
501 * list data item as well.
502 */
503
504 void clear()
505 {
506 PLISTNODE p = lstQueryFirstNode(&ll);
507 while (p)
508 {
509 PLISTNODE pNext = p->pNext;
510
511 KillNode(p);
512
513 p = pNext;
514 }
515 }
516
517 /*
518 *@@ empty:
519 * returns TRUE if the list is empty.
520 */
521
522 bool inline empty() const
523 {
524 return (lstCountItems(&ll) == 0);
525 }
526
527 /*
528 *@@ count:
529 * returns the no.of items on the list.
530 *
531 *@@added V0.9.18 (2002-03-08) [umoeller]
532 */
533
534 unsigned long inline count() const
535 {
536 return (lstCountItems(&ll));
537 }
538
539 /*
540 *@@ begin:
541 * returns a list iterator to the first
542 * list item.
543 */
544
545 list<P>::iterator inline begin() const
546 {
547 return lstQueryFirstNode(&ll);
548 }
549
550 /*
551 *@@ end:
552 * returns a list iterator to point
553 * behind the last list item.
554 *
555 * This is special. STL list defines
556 * the "end" iterator to point _past_
557 * the last element... it does not
558 * return the last element itself.
559 *
560 * A regular STL item loop looks like
561 * this:
562 *
563 + list<X>::iterator i;
564 + for (i = list.begin();
565 + i != list.end();
566 + i++)
567 + {
568 + X x = *i;
569 + }
570 *
571 * So for convenience, we define end()
572 * to return NULL, because
573 * list_iterator::operator++ will set its
574 * member to NULL also if there's no next
575 * item.
576 */
577
578 const list<P>::iterator inline end() const
579 {
580 return (const list<P>::iterator)NULL;
581 }
582
583 /*
584 *@@ rbegin:
585 * for reverse iteration. Returns the last
586 * item.
587 */
588
589 list<P>::reverse_iterator inline rbegin()
590 {
591 return lstQueryLastNode(&ll);
592 }
593
594 list<P>::reverse_iterator inline rend()
595 {
596 return (list<P>::reverse_iterator)NULL;
597 }
598
599 P inline back()
600 {
601 PLISTNODE pNode = lstQueryLastNode(&ll);
602 if (pNode)
603 return (P)pNode->pItemData;
604
605 return (P)NULL;
606 }
607
608 void inline sort(PFNSORTLIST pfnCompare)
609 {
610 lstQuickSort(&ll,
611 pfnCompare,
612 NULL);
613 }
614 };
615
616#endif
617
618
Note: See TracBrowser for help on using the repository browser.