1 /**********************************************************************
2 * File: elst2.h (Formerly elist2.h)
3 * Description: Double linked embedded list module include file.
4 * Author: Phil Cheatle
5 * Created: Wed Jan 23 11:04:47 GMT 1991
6 *
7 * (C) Copyright 1991, Hewlett-Packard Ltd.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 *
18 **********************************************************************/
19
20 #ifndef ELST2_H
21 #define ELST2_H
22
23 #include <stdio.h>
24 #include "host.h"
25 #include "serialis.h"
26 #include "lsterr.h"
27
28 class ELIST2_ITERATOR;
29
30 /**********************************************************************
31 DESIGN NOTE
32 ===========
33
34 It would probably be possible to implement the ELIST2 classes as derived
35 classes from ELIST. I haven't done this because:
36
37 a) I think it would be harder to understand the code
38 (Though the problem with not inheriting is that changes to ELIST must be
39 reflected in ELIST2 and vice versa)
40
41 b) Most of the code is inline so:
42 i) The duplication in source does not affect the run time code size - the
43 code is copied inline anyway!
44
45 ii) The compiler should have a bit less work to do!
46 **********************************************************************/
47
48 /**********************************************************************
49 * CLASS - ELIST2_LINK
50 *
51 * Generic link class for doubly linked lists with embedded links
52 *
53 * Note: No destructor - elements are assumed to be destroyed EITHER after
54 * they have been extracted from a list OR by the ELIST2 destructor which
55 * walks the list.
56 **********************************************************************/
57
58 class DLLSYM ELIST2_LINK
59 {
60 friend class ELIST2_ITERATOR;
61 friend class ELIST2;
62
63 ELIST2_LINK *prev;
64 ELIST2_LINK *next;
65
66 public:
ELIST2_LINK()67 ELIST2_LINK() { //constructor
68 prev = next = NULL;
69 }
70
ELIST2_LINK(const ELIST2_LINK &)71 ELIST2_LINK( //copy constructor
72 const ELIST2_LINK &) { //dont copy link
73 prev = next = NULL;
74 }
75
76 void operator= ( //dont copy links
77 const ELIST2_LINK &) {
78 prev = next = NULL;
79 }
80
81 /* NOTE that none of the serialise member functions are required for
82 ELIST2_LINKs as they are never serialised. (We demand that the derived
83 class terminates recursion - just to make sure that it defines the member
84 functions anyway.)
85 */
86 };
87
88 /**********************************************************************
89 * CLASS - ELIST2
90 *
91 * Generic list class for doubly linked lists with embedded links
92 **********************************************************************/
93
94 class DLLSYM ELIST2
95 {
96 friend class ELIST2_ITERATOR;
97
98 ELIST2_LINK *last; //End of list
99 //(Points to head)
First()100 ELIST2_LINK *First() { // return first
101 return last ? last->next : NULL;
102 }
103
104 public:
ELIST2()105 ELIST2() { //constructor
106 last = NULL;
107 }
108
109 void internal_clear ( //destroy all links
110 void (*zapper) (ELIST2_LINK *));
111 //ptr to zapper functn
112
empty()113 bool empty() { //is list empty?
114 return !last;
115 }
116
singleton()117 bool singleton() {
118 return last ? (last == last->next) : FALSE;
119 }
120
shallow_copy(ELIST2 * from_list)121 void shallow_copy( //dangerous!!
122 ELIST2 *from_list) { //beware destructors!!
123 last = from_list->last;
124 }
125
126 //ptr to copier functn
127 void internal_deep_copy (ELIST2_LINK * (*copier) (ELIST2_LINK *),
128 const ELIST2 * list); //list being copied
129
130 void assign_to_sublist( //to this list
131 ELIST2_ITERATOR *start_it, //from list start
132 ELIST2_ITERATOR *end_it); //from list end
133
134 inT32 length(); //# elements in list
135
136 void sort ( //sort elements
137 int comparator ( //comparison routine
138 const void *, const void *));
139
140 // Assuming list has been sorted already, insert new_link to
141 // keep the list sorted according to the same comparison function.
142 // Comparision function is the same as used by sort, i.e. uses double
143 // indirection. Time is O(1) to add to beginning or end.
144 // Time is linear to add pre-sorted items to an empty list.
145 void add_sorted(int comparator(const void*, const void*),
146 ELIST2_LINK* new_link);
147
148 void internal_dump ( //serialise each elem
149 FILE * f, //to this file
150 void element_serialiser ( //using this function
151 FILE *, ELIST2_LINK *));
152
153 void internal_de_dump ( //de_serial each elem
154 FILE * f, //from this file
155 //using this function
156 ELIST2_LINK * element_de_serialiser (
157 FILE *));
158
159 void prep_serialise(); //change last to count
160
161 /* Note that dump() and de_dump() are not required as calls to dump/de_dump a
162 list class should be handled by a class derived from this.
163
164 make_serialise is not required for a similar reason.
165 */
166 };
167
168 /***********************************************************************
169 * CLASS - ELIST2_ITERATOR
170 *
171 * Generic iterator class for doubly linked lists with embedded links
172 **********************************************************************/
173
174 class DLLSYM ELIST2_ITERATOR
175 {
176 friend void ELIST2::assign_to_sublist(ELIST2_ITERATOR *, ELIST2_ITERATOR *);
177
178 ELIST2 *list; //List being iterated
179 ELIST2_LINK *prev; //prev element
180 ELIST2_LINK *current; //current element
181 ELIST2_LINK *next; //next element
182 bool ex_current_was_last; //current extracted
183 //was end of list
184 bool ex_current_was_cycle_pt; //current extracted
185 //was cycle point
186 ELIST2_LINK *cycle_pt; //point we are cycling
187 //the list to.
188 bool started_cycling; //Have we moved off
189 //the start?
190
191 ELIST2_LINK *extract_sublist( //from this current...
192 ELIST2_ITERATOR *other_it); //to other current
193
194 public:
ELIST2_ITERATOR()195 ELIST2_ITERATOR() { //constructor
196 list = NULL;
197 } //unassigned list
198
199 ELIST2_ITERATOR( //constructor
200 ELIST2 *list_to_iterate);
201
202 void set_to_list( //change list
203 ELIST2 *list_to_iterate);
204
205 void add_after_then_move( //add after current &
206 ELIST2_LINK *new_link); //move to new
207
208 void add_after_stay_put( //add after current &
209 ELIST2_LINK *new_link); //stay at current
210
211 void add_before_then_move( //add before current &
212 ELIST2_LINK *new_link); //move to new
213
214 void add_before_stay_put( //add before current &
215 ELIST2_LINK *new_link); //stay at current
216
217 void add_list_after( //add a list &
218 ELIST2 *list_to_add); //stay at current
219
220 void add_list_before( //add a list &
221 ELIST2 *list_to_add); //move to it 1st item
222
data()223 ELIST2_LINK *data() { //get current data
224 #ifndef NDEBUG
225 if (!current)
226 NULL_DATA.error ("ELIST2_ITERATOR::data", ABORT, NULL);
227 if (!list)
228 NO_LIST.error ("ELIST2_ITERATOR::data", ABORT, NULL);
229 #endif
230 return current;
231 }
232
233 ELIST2_LINK *data_relative( //get data + or - ...
234 inT8 offset); //offset from current
235
236 ELIST2_LINK *forward(); //move to next element
237
238 ELIST2_LINK *backward(); //move to prev element
239
240 ELIST2_LINK *extract(); //remove from list
241
242 //go to start of list
243 ELIST2_LINK *move_to_first();
244
245 ELIST2_LINK *move_to_last(); //go to end of list
246
247 void mark_cycle_pt(); //remember current
248
empty()249 bool empty() { //is list empty?
250 #ifndef NDEBUG
251 if (!list)
252 NO_LIST.error ("ELIST2_ITERATOR::empty", ABORT, NULL);
253 #endif
254 return list->empty ();
255 }
256
current_extracted()257 bool current_extracted() { //current extracted?
258 return !current;
259 }
260
261 bool at_first(); //Current is first?
262
263 bool at_last(); //Current is last?
264
265 bool cycled_list(); //Completed a cycle?
266
267 void add_to_end( //add at end &
268 ELIST2_LINK *new_link); //dont move
269
270 void exchange( //positions of 2 links
271 ELIST2_ITERATOR *other_it); //other iterator
272
273 inT32 length(); //# elements in list
274
275 void sort ( //sort elements
276 int comparator ( //comparison routine
277 const void *, const void *));
278
279 };
280
281 /***********************************************************************
282 * ELIST2_ITERATOR::set_to_list
283 *
284 * (Re-)initialise the iterator to point to the start of the list_to_iterate
285 * over.
286 **********************************************************************/
287
set_to_list(ELIST2 * list_to_iterate)288 inline void ELIST2_ITERATOR::set_to_list( //change list
289 ELIST2 *list_to_iterate) {
290 #ifndef NDEBUG
291 if (!this)
292 NULL_OBJECT.error ("ELIST2_ITERATOR::set_to_list", ABORT, NULL);
293 if (!list_to_iterate)
294 BAD_PARAMETER.error ("ELIST2_ITERATOR::set_to_list", ABORT,
295 "list_to_iterate is NULL");
296 #endif
297
298 list = list_to_iterate;
299 prev = list->last;
300 current = list->First ();
301 next = current ? current->next : NULL;
302 cycle_pt = NULL; //await explicit set
303 started_cycling = FALSE;
304 ex_current_was_last = FALSE;
305 ex_current_was_cycle_pt = FALSE;
306 }
307
308
309 /***********************************************************************
310 * ELIST2_ITERATOR::ELIST2_ITERATOR
311 *
312 * CONSTRUCTOR - set iterator to specified list;
313 **********************************************************************/
314
ELIST2_ITERATOR(ELIST2 * list_to_iterate)315 inline ELIST2_ITERATOR::ELIST2_ITERATOR(ELIST2 *list_to_iterate) {
316 set_to_list(list_to_iterate);
317 }
318
319
320 /***********************************************************************
321 * ELIST2_ITERATOR::add_after_then_move
322 *
323 * Add a new element to the list after the current element and move the
324 * iterator to the new element.
325 **********************************************************************/
326
add_after_then_move(ELIST2_LINK * new_element)327 inline void ELIST2_ITERATOR::add_after_then_move( // element to add
328 ELIST2_LINK *new_element) {
329 #ifndef NDEBUG
330 if (!this)
331 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
332 if (!list)
333 NO_LIST.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
334 if (!new_element)
335 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_then_move", ABORT,
336 "new_element is NULL");
337 if (new_element->next)
338 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
339 #endif
340
341 if (list->empty ()) {
342 new_element->next = new_element;
343 new_element->prev = new_element;
344 list->last = new_element;
345 prev = next = new_element;
346 }
347 else {
348 new_element->next = next;
349 next->prev = new_element;
350
351 if (current) { //not extracted
352 new_element->prev = current;
353 current->next = new_element;
354 prev = current;
355 if (current == list->last)
356 list->last = new_element;
357 }
358 else { //current extracted
359 new_element->prev = prev;
360 prev->next = new_element;
361 if (ex_current_was_last)
362 list->last = new_element;
363 if (ex_current_was_cycle_pt)
364 cycle_pt = new_element;
365 }
366 }
367 current = new_element;
368 }
369
370
371 /***********************************************************************
372 * ELIST2_ITERATOR::add_after_stay_put
373 *
374 * Add a new element to the list after the current element but do not move
375 * the iterator to the new element.
376 **********************************************************************/
377
add_after_stay_put(ELIST2_LINK * new_element)378 inline void ELIST2_ITERATOR::add_after_stay_put( // element to add
379 ELIST2_LINK *new_element) {
380 #ifndef NDEBUG
381 if (!this)
382 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
383 if (!list)
384 NO_LIST.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
385 if (!new_element)
386 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT,
387 "new_element is NULL");
388 if (new_element->next)
389 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
390 #endif
391
392 if (list->empty ()) {
393 new_element->next = new_element;
394 new_element->prev = new_element;
395 list->last = new_element;
396 prev = next = new_element;
397 ex_current_was_last = FALSE;
398 current = NULL;
399 }
400 else {
401 new_element->next = next;
402 next->prev = new_element;
403
404 if (current) { //not extracted
405 new_element->prev = current;
406 current->next = new_element;
407 if (prev == current)
408 prev = new_element;
409 if (current == list->last)
410 list->last = new_element;
411 }
412 else { //current extracted
413 new_element->prev = prev;
414 prev->next = new_element;
415 if (ex_current_was_last) {
416 list->last = new_element;
417 ex_current_was_last = FALSE;
418 }
419 }
420 next = new_element;
421 }
422 }
423
424
425 /***********************************************************************
426 * ELIST2_ITERATOR::add_before_then_move
427 *
428 * Add a new element to the list before the current element and move the
429 * iterator to the new element.
430 **********************************************************************/
431
add_before_then_move(ELIST2_LINK * new_element)432 inline void ELIST2_ITERATOR::add_before_then_move( // element to add
433 ELIST2_LINK *new_element) {
434 #ifndef NDEBUG
435 if (!this)
436 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
437 if (!list)
438 NO_LIST.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
439 if (!new_element)
440 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_then_move", ABORT,
441 "new_element is NULL");
442 if (new_element->next)
443 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
444 #endif
445
446 if (list->empty ()) {
447 new_element->next = new_element;
448 new_element->prev = new_element;
449 list->last = new_element;
450 prev = next = new_element;
451 }
452 else {
453 prev->next = new_element;
454 new_element->prev = prev;
455
456 if (current) { //not extracted
457 new_element->next = current;
458 current->prev = new_element;
459 next = current;
460 }
461 else { //current extracted
462 new_element->next = next;
463 next->prev = new_element;
464 if (ex_current_was_last)
465 list->last = new_element;
466 if (ex_current_was_cycle_pt)
467 cycle_pt = new_element;
468 }
469 }
470 current = new_element;
471 }
472
473
474 /***********************************************************************
475 * ELIST2_ITERATOR::add_before_stay_put
476 *
477 * Add a new element to the list before the current element but dont move the
478 * iterator to the new element.
479 **********************************************************************/
480
add_before_stay_put(ELIST2_LINK * new_element)481 inline void ELIST2_ITERATOR::add_before_stay_put( // element to add
482 ELIST2_LINK *new_element) {
483 #ifndef NDEBUG
484 if (!this)
485 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
486 if (!list)
487 NO_LIST.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
488 if (!new_element)
489 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT,
490 "new_element is NULL");
491 if (new_element->next)
492 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
493 #endif
494
495 if (list->empty ()) {
496 new_element->next = new_element;
497 new_element->prev = new_element;
498 list->last = new_element;
499 prev = next = new_element;
500 ex_current_was_last = TRUE;
501 current = NULL;
502 }
503 else {
504 prev->next = new_element;
505 new_element->prev = prev;
506
507 if (current) { //not extracted
508 new_element->next = current;
509 current->prev = new_element;
510 if (next == current)
511 next = new_element;
512 }
513 else { //current extracted
514 new_element->next = next;
515 next->prev = new_element;
516 if (ex_current_was_last)
517 list->last = new_element;
518 }
519 prev = new_element;
520 }
521 }
522
523
524 /***********************************************************************
525 * ELIST2_ITERATOR::add_list_after
526 *
527 * Insert another list to this list after the current element but dont move the
528 * iterator.
529 **********************************************************************/
530
add_list_after(ELIST2 * list_to_add)531 inline void ELIST2_ITERATOR::add_list_after(ELIST2 *list_to_add) {
532 #ifndef NDEBUG
533 if (!this)
534 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL);
535 if (!list)
536 NO_LIST.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL);
537 if (!list_to_add)
538 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_after", ABORT,
539 "list_to_add is NULL");
540 #endif
541
542 if (!list_to_add->empty ()) {
543 if (list->empty ()) {
544 list->last = list_to_add->last;
545 prev = list->last;
546 next = list->First ();
547 ex_current_was_last = TRUE;
548 current = NULL;
549 }
550 else {
551 if (current) { //not extracted
552 current->next = list_to_add->First ();
553 current->next->prev = current;
554 if (current == list->last)
555 list->last = list_to_add->last;
556 list_to_add->last->next = next;
557 next->prev = list_to_add->last;
558 next = current->next;
559 }
560 else { //current extracted
561 prev->next = list_to_add->First ();
562 prev->next->prev = prev;
563 if (ex_current_was_last) {
564 list->last = list_to_add->last;
565 ex_current_was_last = FALSE;
566 }
567 list_to_add->last->next = next;
568 next->prev = list_to_add->last;
569 next = prev->next;
570 }
571 }
572 list_to_add->last = NULL;
573 }
574 }
575
576
577 /***********************************************************************
578 * ELIST2_ITERATOR::add_list_before
579 *
580 * Insert another list to this list before the current element. Move the
581 * iterator to the start of the inserted elements
582 * iterator.
583 **********************************************************************/
584
add_list_before(ELIST2 * list_to_add)585 inline void ELIST2_ITERATOR::add_list_before(ELIST2 *list_to_add) {
586 #ifndef NDEBUG
587 if (!this)
588 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL);
589 if (!list)
590 NO_LIST.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL);
591 if (!list_to_add)
592 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_before", ABORT,
593 "list_to_add is NULL");
594 #endif
595
596 if (!list_to_add->empty ()) {
597 if (list->empty ()) {
598 list->last = list_to_add->last;
599 prev = list->last;
600 current = list->First ();
601 next = current->next;
602 ex_current_was_last = FALSE;
603 }
604 else {
605 prev->next = list_to_add->First ();
606 prev->next->prev = prev;
607
608 if (current) { //not extracted
609 list_to_add->last->next = current;
610 current->prev = list_to_add->last;
611 }
612 else { //current extracted
613 list_to_add->last->next = next;
614 next->prev = list_to_add->last;
615 if (ex_current_was_last)
616 list->last = list_to_add->last;
617 if (ex_current_was_cycle_pt)
618 cycle_pt = prev->next;
619 }
620 current = prev->next;
621 next = current->next;
622 }
623 list_to_add->last = NULL;
624 }
625 }
626
627
628 /***********************************************************************
629 * ELIST2_ITERATOR::extract
630 *
631 * Do extraction by removing current from the list, returning it to the
632 * caller, but NOT updating the iterator. (So that any calling loop can do
633 * this.) The iterator's current points to NULL. If the extracted element
634 * is to be deleted, this is the callers responsibility.
635 **********************************************************************/
636
extract()637 inline ELIST2_LINK *ELIST2_ITERATOR::extract() {
638 ELIST2_LINK *extracted_link;
639
640 #ifndef NDEBUG
641 if (!this)
642 NULL_OBJECT.error ("ELIST2_ITERATOR::extract", ABORT, NULL);
643 if (!list)
644 NO_LIST.error ("ELIST2_ITERATOR::extract", ABORT, NULL);
645 if (!current) //list empty or
646 //element extracted
647 NULL_CURRENT.error ("ELIST2_ITERATOR::extract",
648 ABORT, NULL);
649 #endif
650
651 if (list->singleton()) {
652 // Special case where we do need to change the iterator.
653 prev = next = list->last = NULL;
654 } else {
655 prev->next = next; //remove from list
656 next->prev = prev;
657
658 if (current == list->last) {
659 list->last = prev;
660 ex_current_was_last = TRUE;
661 } else {
662 ex_current_was_last = FALSE;
663 }
664 }
665 // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
666 ex_current_was_cycle_pt = (current == cycle_pt) ? TRUE : FALSE;
667 extracted_link = current;
668 extracted_link->next = NULL; //for safety
669 extracted_link->prev = NULL; //for safety
670 current = NULL;
671 return extracted_link;
672 }
673
674
675 /***********************************************************************
676 * ELIST2_ITERATOR::move_to_first()
677 *
678 * Move current so that it is set to the start of the list.
679 * Return data just in case anyone wants it.
680 **********************************************************************/
681
move_to_first()682 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_first() {
683 #ifndef NDEBUG
684 if (!this)
685 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL);
686 if (!list)
687 NO_LIST.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL);
688 #endif
689
690 current = list->First ();
691 prev = list->last;
692 next = current ? current->next : NULL;
693 return current;
694 }
695
696
697 /***********************************************************************
698 * ELIST2_ITERATOR::move_to_last()
699 *
700 * Move current so that it is set to the end of the list.
701 * Return data just in case anyone wants it.
702 **********************************************************************/
703
move_to_last()704 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_last() {
705 #ifndef NDEBUG
706 if (!this)
707 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL);
708 if (!list)
709 NO_LIST.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL);
710 #endif
711
712 current = list->last;
713 prev = current ? current->prev : NULL;
714 next = current ? current->next : NULL;
715 return current;
716 }
717
718
719 /***********************************************************************
720 * ELIST2_ITERATOR::mark_cycle_pt()
721 *
722 * Remember the current location so that we can tell whether we've returned
723 * to this point later.
724 *
725 * If the current point is deleted either now, or in the future, the cycle
726 * point will be set to the next item which is set to current. This could be
727 * by a forward, add_after_then_move or add_after_then_move.
728 **********************************************************************/
729
mark_cycle_pt()730 inline void ELIST2_ITERATOR::mark_cycle_pt() {
731 #ifndef NDEBUG
732 if (!this)
733 NULL_OBJECT.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL);
734 if (!list)
735 NO_LIST.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL);
736 #endif
737
738 if (current)
739 cycle_pt = current;
740 else
741 ex_current_was_cycle_pt = TRUE;
742 started_cycling = FALSE;
743 }
744
745
746 /***********************************************************************
747 * ELIST2_ITERATOR::at_first()
748 *
749 * Are we at the start of the list?
750 *
751 **********************************************************************/
752
at_first()753 inline bool ELIST2_ITERATOR::at_first() {
754 #ifndef NDEBUG
755 if (!this)
756 NULL_OBJECT.error ("ELIST2_ITERATOR::at_first", ABORT, NULL);
757 if (!list)
758 NO_LIST.error ("ELIST2_ITERATOR::at_first", ABORT, NULL);
759 #endif
760
761 //we're at a deleted
762 return ((list->empty ()) || (current == list->First ()) || ((current == NULL) &&
763 (prev == list->last) && //NON-last pt between
764 !ex_current_was_last)); //first and last
765 }
766
767
768 /***********************************************************************
769 * ELIST2_ITERATOR::at_last()
770 *
771 * Are we at the end of the list?
772 *
773 **********************************************************************/
774
at_last()775 inline bool ELIST2_ITERATOR::at_last() {
776 #ifndef NDEBUG
777 if (!this)
778 NULL_OBJECT.error ("ELIST2_ITERATOR::at_last", ABORT, NULL);
779 if (!list)
780 NO_LIST.error ("ELIST2_ITERATOR::at_last", ABORT, NULL);
781 #endif
782
783 //we're at a deleted
784 return ((list->empty ()) || (current == list->last) || ((current == NULL) &&
785 (prev == list->last) && //last point between
786 ex_current_was_last)); //first and last
787 }
788
789
790 /***********************************************************************
791 * ELIST2_ITERATOR::cycled_list()
792 *
793 * Have we returned to the cycle_pt since it was set?
794 *
795 **********************************************************************/
796
cycled_list()797 inline bool ELIST2_ITERATOR::cycled_list() {
798 #ifndef NDEBUG
799 if (!this)
800 NULL_OBJECT.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL);
801 if (!list)
802 NO_LIST.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL);
803 #endif
804
805 return ((list->empty ()) || ((current == cycle_pt) && started_cycling));
806
807 }
808
809
810 /***********************************************************************
811 * ELIST2_ITERATOR::length()
812 *
813 * Return the length of the list
814 *
815 **********************************************************************/
816
length()817 inline inT32 ELIST2_ITERATOR::length() {
818 #ifndef NDEBUG
819 if (!this)
820 NULL_OBJECT.error ("ELIST2_ITERATOR::length", ABORT, NULL);
821 if (!list)
822 NO_LIST.error ("ELIST2_ITERATOR::length", ABORT, NULL);
823 #endif
824
825 return list->length ();
826 }
827
828
829 /***********************************************************************
830 * ELIST2_ITERATOR::sort()
831 *
832 * Sort the elements of the list, then reposition at the start.
833 *
834 **********************************************************************/
835
836 inline void
sort(int comparator (const void *,const void *))837 ELIST2_ITERATOR::sort ( //sort elements
838 int comparator ( //comparison routine
839 const void *, const void *)) {
840 #ifndef NDEBUG
841 if (!this)
842 NULL_OBJECT.error ("ELIST2_ITERATOR::sort", ABORT, NULL);
843 if (!list)
844 NO_LIST.error ("ELIST2_ITERATOR::sort", ABORT, NULL);
845 #endif
846
847 list->sort (comparator);
848 move_to_first();
849 }
850
851
852 /***********************************************************************
853 * ELIST2_ITERATOR::add_to_end
854 *
855 * Add a new element to the end of the list without moving the iterator.
856 * This is provided because a single linked list cannot move to the last as
857 * the iterator couldn't set its prev pointer. Adding to the end is
858 * essential for implementing
859 queues.
860 **********************************************************************/
861
add_to_end(ELIST2_LINK * new_element)862 inline void ELIST2_ITERATOR::add_to_end( // element to add
863 ELIST2_LINK *new_element) {
864 #ifndef NDEBUG
865 if (!this)
866 NULL_OBJECT.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
867 if (!list)
868 NO_LIST.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
869 if (!new_element)
870 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_to_end", ABORT,
871 "new_element is NULL");
872 if (new_element->next)
873 STILL_LINKED.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
874 #endif
875
876 if (this->at_last ()) {
877 this->add_after_stay_put (new_element);
878 }
879 else {
880 if (this->at_first ()) {
881 this->add_before_stay_put (new_element);
882 list->last = new_element;
883 }
884 else { //Iteratr is elsewhere
885 new_element->next = list->last->next;
886 new_element->prev = list->last;
887 list->last->next->prev = new_element;
888 list->last->next = new_element;
889 list->last = new_element;
890 }
891 }
892 }
893
894
895 /***********************************************************************
896 QUOTE_IT MACRO DEFINITION
897 ===========================
898 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens
899 ***********************************************************************/
900
901 #define QUOTE_IT( parm ) #parm
902
903 /***********************************************************************
904 ELIST2IZE( CLASSNAME ) MACRO DEFINITION
905 ======================================
906
907 CLASSNAME is assumed to be the name of a class which has a baseclass of
908 ELIST2_LINK.
909
910 NOTE: Because we dont use virtual functions in the list code, the list code
911 will NOT work correctly for classes derived from this.
912
913 The macro generates:
914 - An element deletion function: CLASSNAME##_zapper
915 - An element serialiser function" CLASSNAME##_serialiser
916 - An element de-serialiser function" CLASSNAME##_de_serialiser
917 - An E_LIST2 subclass: CLASSNAME##_LIST
918 - An E_LIST2_ITERATOR subclass:
919 CLASSNAME##_IT
920
921 NOTE: Generated names are DELIBERATELY designed to clash with those for
922 ELISTIZE but NOT with those for CLISTIZE and CLIST2IZE
923
924 Four macros are provided: ELIST2IZE, ELIST2IZE_S, ELIST2IZEH and ELIST2IZEH_S
925 The ...IZEH macros just define the class names for use in .h files
926 The ...IZE macros define the code use in .c files
927 The _S versions define lists which can be serialised. They assume that
928 the make_serialise() macro is used in the list element class derived from
929 ELIST2_LINK to define serialise() and de_serialise() members for the list
930 elements.
931 ***********************************************************************/
932
933 /***********************************************************************
934 ELIST2IZEH( CLASSNAME ) and ELIST2IZEH_S( CLASSNAME ) MACROS
935
936 These macros are constructed from 3 fragments ELIST2IZEH_A, ELIST2IZEH_B and
937 ELIST2IZEH_C. ELIST2IZEH is simply a concatenation of these parts.
938 ELIST2IZEH_S has some additional bits thrown in the gaps.
939 ***********************************************************************/
940
941 #define ELIST2IZEH_A( CLASSNAME ) \
942 \
943 extern DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
944 ELIST2_LINK* link); /*link to delete*/
945
946 #define ELIST2IZEH_B( CLASSNAME ) \
947 \
948 /*********************************************************************** \
949 * CLASS - CLASSNAME##_LIST \
950 * \
951 * List class for class CLASSNAME \
952 * \
953 **********************************************************************/ \
954 \
955 class DLLSYM CLASSNAME##_LIST : public ELIST2 \
956 { \
957 public: \
958 CLASSNAME##_LIST():ELIST2() {} \
959 /* constructor */ \
960 \
961 CLASSNAME##_LIST( /* dont construct */ \
962 const CLASSNAME##_LIST&) /*by initial assign*/\
963 { DONT_CONSTRUCT_LIST_BY_COPY.error( QUOTE_IT( CLASSNAME##_LIST ), \
964 ABORT, NULL ); } \
965 \
966 void clear() /* delete elements */\
967 { ELIST2::internal_clear( &CLASSNAME##_zapper ); } \
968 \
969 ~CLASSNAME##_LIST() /* destructor */ \
970 { clear(); } \
971 \
972 /* Become a deep copy of src_list*/ \
973 void deep_copy(const CLASSNAME##_LIST* src_list, \
974 CLASSNAME* (*copier)(const CLASSNAME*)); \
975 \
976 void operator=( /* prevent assign */ \
977 const CLASSNAME##_LIST&) \
978 { DONT_ASSIGN_LISTS.error( QUOTE_IT( CLASSNAME##_LIST ), \
979 ABORT, NULL ); }
980
981 #define ELIST2IZEH_C( CLASSNAME ) \
982 }; \
983 \
984 \
985 \
986 /*********************************************************************** \
987 * CLASS - CLASSNAME##_IT \
988 * \
989 * Iterator class for class CLASSNAME##_LIST \
990 * \
991 * Note: We don't need to coerce pointers to member functions input \
992 * parameters as these are automatically converted to the type of the base \
993 * type. ("A ptr to a class may be converted to a pointer to a public base \
994 * class of that class") \
995 **********************************************************************/ \
996 \
997 class DLLSYM CLASSNAME##_IT : public ELIST2_ITERATOR \
998 { \
999 public: \
1000 CLASSNAME##_IT():ELIST2_ITERATOR(){} \
1001 \
1002 CLASSNAME##_IT( \
1003 CLASSNAME##_LIST* list):ELIST2_ITERATOR(list){} \
1004 \
1005 CLASSNAME* data() \
1006 { return (CLASSNAME*) ELIST2_ITERATOR::data(); } \
1007 \
1008 CLASSNAME* data_relative( \
1009 inT8 offset) \
1010 { return (CLASSNAME*) ELIST2_ITERATOR::data_relative( offset ); } \
1011 \
1012 CLASSNAME* forward() \
1013 { return (CLASSNAME*) ELIST2_ITERATOR::forward(); } \
1014 \
1015 CLASSNAME* backward() \
1016 { return (CLASSNAME*) ELIST2_ITERATOR::backward(); } \
1017 \
1018 CLASSNAME* extract() \
1019 { return (CLASSNAME*) ELIST2_ITERATOR::extract(); } \
1020 \
1021 CLASSNAME* move_to_first() \
1022 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_first(); } \
1023 \
1024 CLASSNAME* move_to_last() \
1025 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_last(); } \
1026 };
1027
1028 #define ELIST2IZEH( CLASSNAME ) \
1029 \
1030 ELIST2IZEH_A( CLASSNAME ) \
1031 \
1032 ELIST2IZEH_B( CLASSNAME ) \
1033 \
1034 ELIST2IZEH_C( CLASSNAME )
1035
1036 #define ELIST2IZEH_S( CLASSNAME ) \
1037 \
1038 ELIST2IZEH_A( CLASSNAME ) \
1039 \
1040 extern DLLSYM void CLASSNAME##_serialiser( \
1041 FILE* f, \
1042 ELIST2_LINK* element); \
1043 \
1044 extern DLLSYM ELIST2_LINK* CLASSNAME##_de_serialiser( \
1045 FILE* f); \
1046 \
1047 ELIST2IZEH_B( CLASSNAME ) \
1048 \
1049 void dump( /* dump to file */ \
1050 FILE* f) \
1051 { ELIST2::internal_dump( f, &CLASSNAME##_serialiser );} \
1052 \
1053 void de_dump( /* get from file */ \
1054 FILE* f) \
1055 { ELIST2::internal_de_dump( f, &CLASSNAME##_de_serialiser );} \
1056 \
1057 make_serialise( CLASSNAME##_LIST ) \
1058 \
1059 ELIST2IZEH_C( CLASSNAME )
1060
1061 /***********************************************************************
1062 ELIST2IZE( CLASSNAME ) and ELIST2IZE_S( CLASSNAME ) MACROS
1063 ELIST2IZE_S is a simple extension to ELIST2IZE
1064 ***********************************************************************/
1065
1066 #define ELIST2IZE( CLASSNAME ) \
1067 \
1068 /*********************************************************************** \
1069 * CLASSNAME##_zapper \
1070 * \
1071 * A function which can delete a CLASSNAME element. This is passed to the \
1072 * generic clear list member function so that when a list is cleared the \
1073 * elements on the list are properly destroyed from the base class, even \
1074 * though we dont use a virtual destructor function. \
1075 **********************************************************************/ \
1076 \
1077 DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
1078 ELIST2_LINK* link) /*link to delete*/ \
1079 { \
1080 delete (CLASSNAME *) link; \
1081 } \
1082 \
1083 /* Become a deep copy of src_list*/ \
1084 void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST* src_list, \
1085 CLASSNAME* (*copier)(const CLASSNAME*)) { \
1086 \
1087 CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST*>(src_list)); \
1088 CLASSNAME##_IT to_it(this); \
1089 \
1090 for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \
1091 to_it.add_after_then_move((*copier)(from_it.data())); \
1092 }
1093
1094 #define ELIST2IZE_S( CLASSNAME ) \
1095 \
1096 ELIST2IZE( CLASSNAME ) \
1097 \
1098 /*********************************************************************** \
1099 * CLASSNAME##_serialiser \
1100 * \
1101 * A function which can serialise an element \
1102 * This is passed to the generic dump member function so that when a list is \
1103 * serialised the elements on the list are properly serialised. \
1104 **********************************************************************/ \
1105 \
1106 DLLSYM void CLASSNAME##_serialiser(FILE* f, ELIST2_LINK* element) { \
1107 reinterpret_cast<CLASSNAME*>(element)->serialise(f); \
1108 } \
1109 \
1110 /*********************************************************************** \
1111 * CLASSNAME##_de_serialiser \
1112 * \
1113 * A function which can de-serialise an element \
1114 * This is passed to the generic de-dump member function so that when a list \
1115 * is de-serialised the elements on the list are properly de-serialised. \
1116 **********************************************************************/ \
1117 \
1118 DLLSYM ELIST2_LINK* CLASSNAME##_de_serialiser(FILE* f) { \
1119 return reinterpret_cast<ELIST2_LINK*>(CLASSNAME::de_serialise(f)); \
1120 }
1121 #endif
1122