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