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