tesseract  5.0.0-alpha-619-ge9db
elst.h
Go to the documentation of this file.
1 /**********************************************************************
2  * File: elst.h (Formerly elist.h)
3  * Description: Embedded list module include file.
4  * Author: Phil Cheatle
5  *
6  * (C) Copyright 1991, Hewlett-Packard Ltd.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *
17  **********************************************************************/
18 
19 #ifndef ELST_H
20 #define ELST_H
21 
22 #include <cstdio>
23 #include <tesseract/serialis.h>
24 #include "lsterr.h"
25 
26 class ELIST_ITERATOR;
27 
28 /**********************************************************************
29 This module implements list classes and iterators.
30 The following list types and iterators are provided:
31 
32  List type List Class Iterator Class Element Class
33  --------- ---------- -------------- -------------
34 
35  Embedded list ELIST
36  ELIST_ITERATOR
37  ELIST_LINK
38  (Single linked)
39 
40  Embedded list ELIST2
41  ELIST2_ITERATOR
42  ELIST2_LINK
43  (Double linked)
44 
45  Cons List CLIST
46  CLIST_ITERATOR
47  CLIST_LINK
48  (Single linked)
49 
50 An embedded list is where the list pointers are provided by a generic class.
51 Data types to be listed inherit from the generic class. Data is thus linked
52 in only ONE list at any one time.
53 
54 A cons list has a separate structure for a "cons cell". This contains the
55 list pointer(s) AND a pointer to the data structure held on the list. A
56 structure can be on many cons lists at the same time, and the structure does
57 not need to inherit from any generic class in order to be on the list.
58 
59 The implementation of lists is very careful about space and speed overheads.
60 This is why many embedded lists are provided. The same concerns mean that
61 in-line type coercion is done, rather than use virtual functions. This is
62 cumbersome in that each data type to be listed requires its own iterator and
63 list class - though macros can generate these. It also prevents heterogeneous
64 lists.
65 **********************************************************************/
66 
67 /**********************************************************************
68  * CLASS - ELIST_LINK
69  *
70  * Generic link class for singly linked lists with embedded links
71  *
72  * Note: No destructor - elements are assumed to be destroyed EITHER after
73  * they have been extracted from a list OR by the ELIST destructor which
74  * walks the list.
75  **********************************************************************/
76 
77 class DLLSYM ELIST_LINK
78 {
79  friend class ELIST_ITERATOR;
80  friend class ELIST;
81 
82  ELIST_LINK *next;
83 
84  public:
85  ELIST_LINK() {
86  next = nullptr;
87  }
88  //constructor
89 
90  ELIST_LINK(const ELIST_LINK &) { // don't copy link.
91  next = nullptr;
92  }
93 
94  void operator=( // don't copy links
95  const ELIST_LINK &) {
96  next = nullptr;
97  }
98 };
99 
100 /**********************************************************************
101  * CLASS - ELIST
102  *
103  * Generic list class for singly linked lists with embedded links
104  **********************************************************************/
105 
106 class DLLSYM ELIST
107 {
108  friend class ELIST_ITERATOR;
109 
110  ELIST_LINK *last; //End of list
111  //(Points to head)
112  ELIST_LINK *First() { // return first
113  return last ? last->next : nullptr;
114  }
115 
116  public:
117  ELIST() { //constructor
118  last = nullptr;
119  }
120 
121  void internal_clear ( //destroy all links
122  //ptr to zapper functn
123  void (*zapper) (ELIST_LINK *));
124 
125  bool empty() const { //is list empty?
126  return !last;
127  }
128 
129  bool singleton() const {
130  return last ? (last == last->next) : false;
131  }
132 
133  void shallow_copy( //dangerous!!
134  ELIST *from_list) { //beware destructors!!
135  last = from_list->last;
136  }
137 
138  //ptr to copier functn
139  void internal_deep_copy (ELIST_LINK * (*copier) (ELIST_LINK *),
140  const ELIST * list); //list being copied
141 
142  void assign_to_sublist( //to this list
143  ELIST_ITERATOR *start_it, //from list start
144  ELIST_ITERATOR *end_it); //from list end
145 
146  int32_t length() const; // # elements in list
147 
148  void sort ( //sort elements
149  int comparator ( //comparison routine
150  const void *, const void *));
151 
152  // Assuming list has been sorted already, insert new_link to
153  // keep the list sorted according to the same comparison function.
154  // Comparison function is the same as used by sort, i.e. uses double
155  // indirection. Time is O(1) to add to beginning or end.
156  // Time is linear to add pre-sorted items to an empty list.
157  // If unique is set to true and comparator() returns 0 (an entry with the
158  // same information as the one contained in new_link is already in the
159  // list) - new_link is not added to the list and the function returns the
160  // pointer to the identical entry that already exists in the list
161  // (otherwise the function returns new_link).
162  ELIST_LINK *add_sorted_and_find(int comparator(const void*, const void*),
163  bool unique, ELIST_LINK* new_link);
164 
165  // Same as above, but returns true if the new entry was inserted, false
166  // if the identical entry already existed in the list.
167  bool add_sorted(int comparator(const void*, const void*),
168  bool unique, ELIST_LINK* new_link) {
169  return (add_sorted_and_find(comparator, unique, new_link) == new_link);
170  }
171 
172 };
173 
174 /***********************************************************************
175  * CLASS - ELIST_ITERATOR
176  *
177  * Generic iterator class for singly linked lists with embedded links
178  **********************************************************************/
179 
181 {
183 
184  ELIST *list; //List being iterated
185  ELIST_LINK *prev; //prev element
186  ELIST_LINK *current; //current element
187  ELIST_LINK *next; //next element
188  ELIST_LINK *cycle_pt; //point we are cycling the list to.
189  bool ex_current_was_last; //current extracted was end of list
190  bool ex_current_was_cycle_pt; //current extracted was cycle point
191  bool started_cycling; //Have we moved off the start?
192 
193  ELIST_LINK *extract_sublist( //from this current...
194  ELIST_ITERATOR *other_it); //to other current
195 
196  public:
197  ELIST_ITERATOR() { //constructor
198  list = nullptr;
199  } //unassigned list
200 
201  explicit ELIST_ITERATOR(ELIST *list_to_iterate);
202 
203  void set_to_list( //change list
204  ELIST *list_to_iterate);
205 
206  void add_after_then_move( //add after current &
207  ELIST_LINK *new_link); //move to new
208 
209  void add_after_stay_put( //add after current &
210  ELIST_LINK *new_link); //stay at current
211 
212  void add_before_then_move( //add before current &
213  ELIST_LINK *new_link); //move to new
214 
215  void add_before_stay_put( //add before current &
216  ELIST_LINK *new_link); //stay at current
217 
218  void add_list_after( //add a list &
219  ELIST *list_to_add); //stay at current
220 
221  void add_list_before( //add a list &
222  ELIST *list_to_add); //move to it 1st item
223 
224  ELIST_LINK *data() { //get current data
225  #ifndef NDEBUG
226  if (!list)
227  NO_LIST.error ("ELIST_ITERATOR::data", ABORT, nullptr);
228  if (!current)
229  NULL_DATA.error ("ELIST_ITERATOR::data", ABORT, nullptr);
230  #endif
231  return current;
232  }
233 
234  ELIST_LINK *data_relative( //get data + or - ...
235  int8_t offset); //offset from current
236 
237  ELIST_LINK *forward(); //move to next element
238 
239  ELIST_LINK *extract(); //remove from list
240 
241  ELIST_LINK *move_to_first(); //go to start of list
242 
243  ELIST_LINK *move_to_last(); //go to end of list
244 
245  void mark_cycle_pt(); //remember current
246 
247  bool empty() { //is list empty?
248  #ifndef NDEBUG
249  if (!list)
250  NO_LIST.error ("ELIST_ITERATOR::empty", ABORT, nullptr);
251  #endif
252  return list->empty ();
253  }
254 
255  bool current_extracted() { //current extracted?
256  return !current;
257  }
258 
259  bool at_first(); //Current is first?
260 
261  bool at_last(); //Current is last?
262 
263  bool cycled_list(); //Completed a cycle?
264 
265  void add_to_end( // add at end &
266  ELIST_LINK *new_link); // don't move
267 
268  void exchange( //positions of 2 links
269  ELIST_ITERATOR *other_it); //other iterator
270 
271  int32_t length(); //# elements in list
272 
273  void sort ( //sort elements
274  int comparator ( //comparison routine
275  const void *, const void *));
276 
277 };
278 
279 /***********************************************************************
280  * ELIST_ITERATOR::set_to_list
281  *
282  * (Re-)initialise the iterator to point to the start of the list_to_iterate
283  * over.
284  **********************************************************************/
285 
286 inline void ELIST_ITERATOR::set_to_list( //change list
287  ELIST *list_to_iterate) {
288  #ifndef NDEBUG
289  if (!list_to_iterate)
290  BAD_PARAMETER.error ("ELIST_ITERATOR::set_to_list", ABORT,
291  "list_to_iterate is nullptr");
292  #endif
293 
294  list = list_to_iterate;
295  prev = list->last;
296  current = list->First ();
297  next = current ? current->next : nullptr;
298  cycle_pt = nullptr; //await explicit set
299  started_cycling = false;
300  ex_current_was_last = false;
301  ex_current_was_cycle_pt = false;
302 }
303 
304 
305 /***********************************************************************
306  * ELIST_ITERATOR::ELIST_ITERATOR
307  *
308  * CONSTRUCTOR - set iterator to specified list;
309  **********************************************************************/
310 
311 inline ELIST_ITERATOR::ELIST_ITERATOR(ELIST *list_to_iterate) {
312  set_to_list(list_to_iterate);
313 }
314 
315 
316 /***********************************************************************
317  * ELIST_ITERATOR::add_after_then_move
318  *
319  * Add a new element to the list after the current element and move the
320  * iterator to the new element.
321  **********************************************************************/
322 
323 inline void ELIST_ITERATOR::add_after_then_move( // element to add
324  ELIST_LINK *new_element) {
325  #ifndef NDEBUG
326  if (!list)
327  NO_LIST.error ("ELIST_ITERATOR::add_after_then_move", ABORT, nullptr);
328  if (!new_element)
329  BAD_PARAMETER.error ("ELIST_ITERATOR::add_after_then_move", ABORT,
330  "new_element is nullptr");
331  if (new_element->next)
332  STILL_LINKED.error ("ELIST_ITERATOR::add_after_then_move", ABORT, nullptr);
333  #endif
334 
335  if (list->empty ()) {
336  new_element->next = new_element;
337  list->last = new_element;
338  prev = next = new_element;
339  }
340  else {
341  new_element->next = next;
342 
343  if (current) { //not extracted
344  current->next = new_element;
345  prev = current;
346  if (current == list->last)
347  list->last = new_element;
348  }
349  else { //current extracted
350  prev->next = new_element;
351  if (ex_current_was_last)
352  list->last = new_element;
353  if (ex_current_was_cycle_pt)
354  cycle_pt = new_element;
355  }
356  }
357  current = new_element;
358 }
359 
360 
361 /***********************************************************************
362  * ELIST_ITERATOR::add_after_stay_put
363  *
364  * Add a new element to the list after the current element but do not move
365  * the iterator to the new element.
366  **********************************************************************/
367 
368 inline void ELIST_ITERATOR::add_after_stay_put( // element to add
369  ELIST_LINK *new_element) {
370  #ifndef NDEBUG
371  if (!list)
372  NO_LIST.error ("ELIST_ITERATOR::add_after_stay_put", ABORT, nullptr);
373  if (!new_element)
374  BAD_PARAMETER.error ("ELIST_ITERATOR::add_after_stay_put", ABORT,
375  "new_element is nullptr");
376  if (new_element->next)
377  STILL_LINKED.error ("ELIST_ITERATOR::add_after_stay_put", ABORT, nullptr);
378  #endif
379 
380  if (list->empty ()) {
381  new_element->next = new_element;
382  list->last = new_element;
383  prev = next = new_element;
384  ex_current_was_last = false;
385  current = nullptr;
386  }
387  else {
388  new_element->next = next;
389 
390  if (current) { //not extracted
391  current->next = new_element;
392  if (prev == current)
393  prev = new_element;
394  if (current == list->last)
395  list->last = new_element;
396  }
397  else { //current extracted
398  prev->next = new_element;
399  if (ex_current_was_last) {
400  list->last = new_element;
401  ex_current_was_last = false;
402  }
403  }
404  next = new_element;
405  }
406 }
407 
408 
409 /***********************************************************************
410  * ELIST_ITERATOR::add_before_then_move
411  *
412  * Add a new element to the list before the current element and move the
413  * iterator to the new element.
414  **********************************************************************/
415 
416 inline void ELIST_ITERATOR::add_before_then_move( // element to add
417  ELIST_LINK *new_element) {
418  #ifndef NDEBUG
419  if (!list)
420  NO_LIST.error ("ELIST_ITERATOR::add_before_then_move", ABORT, nullptr);
421  if (!new_element)
422  BAD_PARAMETER.error ("ELIST_ITERATOR::add_before_then_move", ABORT,
423  "new_element is nullptr");
424  if (new_element->next)
425  STILL_LINKED.error ("ELIST_ITERATOR::add_before_then_move", ABORT, nullptr);
426  #endif
427 
428  if (list->empty ()) {
429  new_element->next = new_element;
430  list->last = new_element;
431  prev = next = new_element;
432  }
433  else {
434  prev->next = new_element;
435  if (current) { //not extracted
436  new_element->next = current;
437  next = current;
438  }
439  else { //current extracted
440  new_element->next = next;
441  if (ex_current_was_last)
442  list->last = new_element;
443  if (ex_current_was_cycle_pt)
444  cycle_pt = new_element;
445  }
446  }
447  current = new_element;
448 }
449 
450 /***********************************************************************
451  * ELIST_ITERATOR::add_before_stay_put
452  *
453  * Add a new element to the list before the current element but don't move the
454  * iterator to the new element.
455  **********************************************************************/
456 
457 inline void ELIST_ITERATOR::add_before_stay_put( // element to add
458  ELIST_LINK *new_element) {
459  #ifndef NDEBUG
460  if (!list)
461  NO_LIST.error ("ELIST_ITERATOR::add_before_stay_put", ABORT, nullptr);
462  if (!new_element)
463  BAD_PARAMETER.error ("ELIST_ITERATOR::add_before_stay_put", ABORT,
464  "new_element is nullptr");
465  if (new_element->next)
466  STILL_LINKED.error ("ELIST_ITERATOR::add_before_stay_put", ABORT, nullptr);
467  #endif
468 
469  if (list->empty ()) {
470  new_element->next = new_element;
471  list->last = new_element;
472  prev = next = new_element;
473  ex_current_was_last = true;
474  current = nullptr;
475  }
476  else {
477  prev->next = new_element;
478  if (current) { //not extracted
479  new_element->next = current;
480  if (next == current)
481  next = new_element;
482  }
483  else { //current extracted
484  new_element->next = next;
485  if (ex_current_was_last)
486  list->last = new_element;
487  }
488  prev = new_element;
489  }
490 }
491 
492 /***********************************************************************
493  * ELIST_ITERATOR::add_list_after
494  *
495  * Insert another list to this list after the current element but don't move
496  *the
497  * iterator.
498  **********************************************************************/
499 
500 inline void ELIST_ITERATOR::add_list_after(ELIST *list_to_add) {
501  #ifndef NDEBUG
502  if (!list)
503  NO_LIST.error ("ELIST_ITERATOR::add_list_after", ABORT, nullptr);
504  if (!list_to_add)
505  BAD_PARAMETER.error ("ELIST_ITERATOR::add_list_after", ABORT,
506  "list_to_add is nullptr");
507  #endif
508 
509  if (!list_to_add->empty ()) {
510  if (list->empty ()) {
511  list->last = list_to_add->last;
512  prev = list->last;
513  next = list->First ();
514  ex_current_was_last = true;
515  current = nullptr;
516  }
517  else {
518  if (current) { //not extracted
519  current->next = list_to_add->First ();
520  if (current == list->last)
521  list->last = list_to_add->last;
522  list_to_add->last->next = next;
523  next = current->next;
524  }
525  else { //current extracted
526  prev->next = list_to_add->First ();
527  if (ex_current_was_last) {
528  list->last = list_to_add->last;
529  ex_current_was_last = false;
530  }
531  list_to_add->last->next = next;
532  next = prev->next;
533  }
534  }
535  list_to_add->last = nullptr;
536  }
537 }
538 
539 
540 /***********************************************************************
541  * ELIST_ITERATOR::add_list_before
542  *
543  * Insert another list to this list before the current element. Move the
544  * iterator to the start of the inserted elements
545  * iterator.
546  **********************************************************************/
547 
548 inline void ELIST_ITERATOR::add_list_before(ELIST *list_to_add) {
549  #ifndef NDEBUG
550  if (!list)
551  NO_LIST.error ("ELIST_ITERATOR::add_list_before", ABORT, nullptr);
552  if (!list_to_add)
553  BAD_PARAMETER.error ("ELIST_ITERATOR::add_list_before", ABORT,
554  "list_to_add is nullptr");
555  #endif
556 
557  if (!list_to_add->empty ()) {
558  if (list->empty ()) {
559  list->last = list_to_add->last;
560  prev = list->last;
561  current = list->First ();
562  next = current->next;
563  ex_current_was_last = false;
564  }
565  else {
566  prev->next = list_to_add->First ();
567  if (current) { //not extracted
568  list_to_add->last->next = current;
569  }
570  else { //current extracted
571  list_to_add->last->next = next;
572  if (ex_current_was_last)
573  list->last = list_to_add->last;
574  if (ex_current_was_cycle_pt)
575  cycle_pt = prev->next;
576  }
577  current = prev->next;
578  next = current->next;
579  }
580  list_to_add->last = nullptr;
581  }
582 }
583 
584 
585 /***********************************************************************
586  * ELIST_ITERATOR::extract
587  *
588  * Do extraction by removing current from the list, returning it to the
589  * caller, but NOT updating the iterator. (So that any calling loop can do
590  * this.) The iterator's current points to nullptr. If the extracted element
591  * is to be deleted, this is the callers responsibility.
592  **********************************************************************/
593 
595  ELIST_LINK *extracted_link;
596 
597  #ifndef NDEBUG
598  if (!list)
599  NO_LIST.error ("ELIST_ITERATOR::extract", ABORT, nullptr);
600  if (!current) //list empty or
601  //element extracted
602  NULL_CURRENT.error ("ELIST_ITERATOR::extract",
603  ABORT, nullptr);
604  #endif
605 
606  if (list->singleton()) {
607  // Special case where we do need to change the iterator.
608  prev = next = list->last = nullptr;
609  } else {
610  prev->next = next; //remove from list
611 
612  ex_current_was_last = (current == list->last);
613  if (ex_current_was_last) list->last = prev;
614  }
615  // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
616  ex_current_was_cycle_pt = (current == cycle_pt);
617  extracted_link = current;
618  extracted_link->next = nullptr; //for safety
619  current = nullptr;
620  return extracted_link;
621 }
622 
623 
624 /***********************************************************************
625  * ELIST_ITERATOR::move_to_first()
626  *
627  * Move current so that it is set to the start of the list.
628  * Return data just in case anyone wants it.
629  **********************************************************************/
630 
632  #ifndef NDEBUG
633  if (!list)
634  NO_LIST.error ("ELIST_ITERATOR::move_to_first", ABORT, nullptr);
635  #endif
636 
637  current = list->First ();
638  prev = list->last;
639  next = current ? current->next : nullptr;
640  return current;
641 }
642 
643 
644 /***********************************************************************
645  * ELIST_ITERATOR::mark_cycle_pt()
646  *
647  * Remember the current location so that we can tell whether we've returned
648  * to this point later.
649  *
650  * If the current point is deleted either now, or in the future, the cycle
651  * point will be set to the next item which is set to current. This could be
652  * by a forward, add_after_then_move or add_after_then_move.
653  **********************************************************************/
654 
655 inline void ELIST_ITERATOR::mark_cycle_pt() {
656  #ifndef NDEBUG
657  if (!list)
658  NO_LIST.error ("ELIST_ITERATOR::mark_cycle_pt", ABORT, nullptr);
659  #endif
660 
661  if (current)
662  cycle_pt = current;
663  else
664  ex_current_was_cycle_pt = true;
665  started_cycling = false;
666 }
667 
668 
669 /***********************************************************************
670  * ELIST_ITERATOR::at_first()
671  *
672  * Are we at the start of the list?
673  *
674  **********************************************************************/
675 
676 inline bool ELIST_ITERATOR::at_first() {
677  #ifndef NDEBUG
678  if (!list)
679  NO_LIST.error ("ELIST_ITERATOR::at_first", ABORT, nullptr);
680  #endif
681 
682  //we're at a deleted
683  return ((list->empty ()) || (current == list->First ()) || ((current == nullptr) &&
684  (prev == list->last) && //NON-last pt between
685  !ex_current_was_last)); //first and last
686 }
687 
688 
689 /***********************************************************************
690  * ELIST_ITERATOR::at_last()
691  *
692  * Are we at the end of the list?
693  *
694  **********************************************************************/
695 
696 inline bool ELIST_ITERATOR::at_last() {
697  #ifndef NDEBUG
698  if (!list)
699  NO_LIST.error ("ELIST_ITERATOR::at_last", ABORT, nullptr);
700  #endif
701 
702  //we're at a deleted
703  return ((list->empty ()) || (current == list->last) || ((current == nullptr) &&
704  (prev == list->last) && //last point between
705  ex_current_was_last)); //first and last
706 }
707 
708 
709 /***********************************************************************
710  * ELIST_ITERATOR::cycled_list()
711  *
712  * Have we returned to the cycle_pt since it was set?
713  *
714  **********************************************************************/
715 
716 inline bool ELIST_ITERATOR::cycled_list() {
717  #ifndef NDEBUG
718  if (!list)
719  NO_LIST.error ("ELIST_ITERATOR::cycled_list", ABORT, nullptr);
720  #endif
721 
722  return ((list->empty ()) || ((current == cycle_pt) && started_cycling));
723 
724 }
725 
726 
727 /***********************************************************************
728  * ELIST_ITERATOR::length()
729  *
730  * Return the length of the list
731  *
732  **********************************************************************/
733 
734 inline int32_t ELIST_ITERATOR::length() {
735  #ifndef NDEBUG
736  if (!list)
737  NO_LIST.error ("ELIST_ITERATOR::length", ABORT, nullptr);
738  #endif
739 
740  return list->length ();
741 }
742 
743 
744 /***********************************************************************
745  * ELIST_ITERATOR::sort()
746  *
747  * Sort the elements of the list, then reposition at the start.
748  *
749  **********************************************************************/
750 
751 inline void
752 ELIST_ITERATOR::sort ( //sort elements
753 int comparator ( //comparison routine
754 const void *, const void *)) {
755  #ifndef NDEBUG
756  if (!list)
757  NO_LIST.error ("ELIST_ITERATOR::sort", ABORT, nullptr);
758  #endif
759 
760  list->sort (comparator);
761  move_to_first();
762 }
763 
764 
765 /***********************************************************************
766  * ELIST_ITERATOR::add_to_end
767  *
768  * Add a new element to the end of the list without moving the iterator.
769  * This is provided because a single linked list cannot move to the last as
770  * the iterator couldn't set its prev pointer. Adding to the end is
771  * essential for implementing
772  queues.
773 **********************************************************************/
774 
775 inline void ELIST_ITERATOR::add_to_end( // element to add
776  ELIST_LINK *new_element) {
777  #ifndef NDEBUG
778  if (!list)
779  NO_LIST.error ("ELIST_ITERATOR::add_to_end", ABORT, nullptr);
780  if (!new_element)
781  BAD_PARAMETER.error ("ELIST_ITERATOR::add_to_end", ABORT,
782  "new_element is nullptr");
783  if (new_element->next)
784  STILL_LINKED.error ("ELIST_ITERATOR::add_to_end", ABORT, nullptr);
785  #endif
786 
787  if (this->at_last ()) {
788  this->add_after_stay_put (new_element);
789  }
790  else {
791  if (this->at_first ()) {
792  this->add_before_stay_put (new_element);
793  list->last = new_element;
794  }
795  else { //Iteratr is elsewhere
796  new_element->next = list->last->next;
797  list->last->next = new_element;
798  list->last = new_element;
799  }
800  }
801 }
802 
803 
804 /***********************************************************************
805  ******************** MACROS **************************************
806  ***********************************************************************/
807 
808 /***********************************************************************
809  QUOTE_IT MACRO DEFINITION
810  ===========================
811 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens
812 ***********************************************************************/
813 
814 #define QUOTE_IT(parm) #parm
815 
816 /***********************************************************************
817  ELISTIZE(CLASSNAME) MACRO
818  ============================
819 
820 CLASSNAME is assumed to be the name of a class which has a baseclass of
821 ELIST_LINK.
822 
823 NOTE: Because we don't use virtual functions in the list code, the list code
824 will NOT work correctly for classes derived from this.
825 
826 The macros generate:
827  - An element deletion function: CLASSNAME##_zapper
828  - An E_LIST subclass: CLASSNAME##_LIST
829  - An E_LIST_ITERATOR subclass: CLASSNAME##_IT
830 
831 NOTE: Generated names are DELIBERATELY designed to clash with those for
832 ELIST2IZE but NOT with those for CLISTIZE.
833 
834 Two macros are provided: ELISTIZE and ELISTIZEH.
835 The ...IZEH macros just define the class names for use in .h files
836 The ...IZE macros define the code use in .c files
837 ***********************************************************************/
838 
839 /***********************************************************************
840  ELISTIZEH(CLASSNAME) MACRO
841 
842 ELISTIZEH is a concatenation of 3 fragments ELISTIZEH_A, ELISTIZEH_B and
843 ELISTIZEH_C.
844 ***********************************************************************/
845 
846 #define ELISTIZEH_A(CLASSNAME) \
847  \
848 extern DLLSYM void CLASSNAME##_zapper(ELIST_LINK* link);
849 
850 #define ELISTIZEH_B(CLASSNAME) \
851  \
852 /*********************************************************************** \
853 * CLASS - CLASSNAME##_LIST \
854 * \
855 * List class for class CLASSNAME \
856 * \
857 **********************************************************************/ \
858  \
859 class DLLSYM CLASSNAME##_LIST : public ELIST { \
860  public: \
861  CLASSNAME##_LIST():ELIST() {} \
862  \
863  void clear() { /* delete elements */\
864  ELIST::internal_clear(&CLASSNAME##_zapper); \
865  } \
866  \
867  ~CLASSNAME##_LIST() { \
868  clear(); \
869  } \
870  \
871  /* Become a deep copy of src_list*/ \
872  void deep_copy(const CLASSNAME##_LIST* src_list, \
873  CLASSNAME* (*copier)(const CLASSNAME*)); \
874  \
875 private: \
876  /* Prevent assign and copy construction. */ \
877  CLASSNAME##_LIST(const CLASSNAME##_LIST&) { \
878  DONT_CONSTRUCT_LIST_BY_COPY.error(QUOTE_IT(CLASSNAME##_LIST), ABORT, nullptr);\
879  } \
880  void operator=(const CLASSNAME##_LIST&) { \
881  DONT_ASSIGN_LISTS.error(QUOTE_IT(CLASSNAME##_LIST), ABORT, nullptr); \
882  } \
883 
884 #define ELISTIZEH_C(CLASSNAME) \
885 }; \
886  \
887  \
888  \
889 /*********************************************************************** \
890 * CLASS - CLASSNAME##_IT \
891 * \
892 * Iterator class for class CLASSNAME##_LIST \
893 * \
894 * Note: We don't need to coerce pointers to member functions input \
895 * parameters as these are automatically converted to the type of the base \
896 * type. ("A ptr to a class may be converted to a pointer to a public base \
897 * class of that class") \
898 **********************************************************************/ \
899  \
900 class DLLSYM CLASSNAME##_IT : public ELIST_ITERATOR { \
901  public: \
902  CLASSNAME##_IT():ELIST_ITERATOR(){} \
903  \
904  /* TODO(rays) This constructor should be explicit, but that means changing \
905  hundreds of incorrect initializations of iterators that use = over () */ \
906  CLASSNAME##_IT(CLASSNAME##_LIST* list) : ELIST_ITERATOR(list) {} \
907  \
908  CLASSNAME* data() { \
909  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::data()); \
910  } \
911  \
912  CLASSNAME* data_relative(int8_t offset) { \
913  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::data_relative(offset));\
914  } \
915  \
916  CLASSNAME* forward() { \
917  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::forward()); \
918  } \
919  \
920  CLASSNAME* extract() { \
921  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::extract()); \
922  } \
923  \
924  CLASSNAME* move_to_first() { \
925  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::move_to_first()); \
926  } \
927  \
928  CLASSNAME* move_to_last() { \
929  return reinterpret_cast<CLASSNAME*>(ELIST_ITERATOR::move_to_last()); \
930  } \
931 };
932 
933 #define ELISTIZEH(CLASSNAME) \
934  \
935 ELISTIZEH_A(CLASSNAME) \
936  \
937 ELISTIZEH_B(CLASSNAME) \
938  \
939 ELISTIZEH_C(CLASSNAME)
940 
941 
942 /***********************************************************************
943  ELISTIZE(CLASSNAME) MACRO
944 ***********************************************************************/
945 
946 #define ELISTIZE(CLASSNAME) \
947  \
948  /*********************************************************************** \
949  * CLASSNAME##_zapper \
950  * \
951  * A function which can delete a CLASSNAME element. This is passed to the \
952  * generic clear list member function so that when a list is cleared the \
953  * elements on the list are properly destroyed from the base class, even \
954  * though we don't use a virtual destructor function. \
955  **********************************************************************/ \
956  \
957  DLLSYM void CLASSNAME##_zapper(ELIST_LINK *link) { \
958  delete reinterpret_cast<CLASSNAME *>(link); \
959  } \
960  \
961  /* Become a deep copy of src_list*/ \
962  void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST *src_list, \
963  CLASSNAME *(*copier)(const CLASSNAME *)) { \
964  CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST *>(src_list)); \
965  CLASSNAME##_IT to_it(this); \
966  \
967  for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \
968  to_it.add_after_then_move((*copier)(from_it.data())); \
969  }
970 
971 #endif
BAD_PARAMETER
constexpr ERRCODE BAD_PARAMETER("List parameter error")
ELIST_ITERATOR::length
int32_t length()
Definition: elst.h:714
lsterr.h
list_rec::next
list_rec * next
Definition: oldlist.h:75
ELIST_ITERATOR
Definition: elst.h:175
NULL_CURRENT
constexpr ERRCODE NULL_CURRENT("List current position is nullptr")
ELIST_ITERATOR::add_after_stay_put
void add_after_stay_put(ELIST_LINK *new_link)
Definition: elst.h:359
ELIST::length
int32_t length() const
Definition: elst.cpp:84
ELIST
Definition: elst.h:102
ELIST_ITERATOR::add_list_before
void add_list_before(ELIST *list_to_add)
Definition: elst.h:535
ELIST_ITERATOR::extract
ELIST_LINK * extract()
Definition: elst.h:580
ELIST_ITERATOR::sort
void sort(int comparator(const void *, const void *))
Definition: elst.h:731
ELIST_ITERATOR::at_last
bool at_last()
Definition: elst.h:678
ELIST::sort
void sort(int comparator(const void *, const void *))
Definition: elst.cpp:101
ERRCODE::error
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:33
last
LIST last(LIST var_list)
Definition: oldlist.cpp:151
NULL_DATA
constexpr ERRCODE NULL_DATA("List would have returned a nullptr data pointer")
ELIST_ITERATOR::empty
bool empty()
Definition: elst.h:245
ELIST_ITERATOR::mark_cycle_pt
void mark_cycle_pt()
Definition: elst.h:639
ELIST
Definition: cleanapi_test.cc:19
ELIST_ITERATOR::add_after_then_move
void add_after_then_move(ELIST_LINK *new_link)
Definition: elst.h:315
ELIST::singleton
bool singleton() const
Definition: elst.h:128
DLLSYM
#define DLLSYM
Definition: platform.h:21
ELIST_ITERATOR::cycled_list
bool cycled_list()
Definition: elst.h:697
ELIST_ITERATOR::at_first
bool at_first()
Definition: elst.h:659
ELIST_ITERATOR::add_before_then_move
void add_before_then_move(ELIST_LINK *new_link)
Definition: elst.h:406
STILL_LINKED
constexpr ERRCODE STILL_LINKED("Attempting to add an element with non nullptr links, to a list")
ELIST_ITERATOR::set_to_list
void set_to_list(ELIST *list_to_iterate)
Definition: elst.h:280
ELIST_ITERATOR::add_to_end
void add_to_end(ELIST_LINK *new_link)
Definition: elst.h:753
ELIST_LINK
Definition: elst.h:74
serialis.h
ELIST_ITERATOR::add_list_after
void add_list_after(ELIST *list_to_add)
Definition: elst.h:488
ABORT
Definition: errcode.h:43
ELIST::assign_to_sublist
void assign_to_sublist(ELIST_ITERATOR *start_it, ELIST_ITERATOR *end_it)
Definition: elst.cpp:67
ELIST_ITERATOR::move_to_first
ELIST_LINK * move_to_first()
Definition: elst.h:616
ELIST_ITERATOR::add_before_stay_put
void add_before_stay_put(ELIST_LINK *new_link)
Definition: elst.h:446
NO_LIST
constexpr ERRCODE NO_LIST("Iterator not set to a list")
ELIST_ITERATOR::ELIST_ITERATOR
ELIST_ITERATOR()
Definition: elst.h:195
ELIST::empty
bool empty() const
Definition: elst.h:124