tesseract  5.0.0
clst.h
Go to the documentation of this file.
1 /**********************************************************************
2  * File: clst.h (Formerly clist.h)
3  * Description: CONS cell 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 CLST_H
20 #define CLST_H
21 
22 #include "list.h"
23 #include "lsterr.h"
24 #include "serialis.h"
25 
26 #include <cstdio>
27 
28 namespace tesseract {
29 
30 class CLIST_ITERATOR;
31 
32 /**********************************************************************
33  * CLASS - CLIST_LINK
34  *
35  * Generic link class for singly linked CONS cell lists
36  *
37  * Note: No destructor - elements are assumed to be destroyed EITHER after
38  * they have been extracted from a list OR by the CLIST destructor which
39  * walks the list.
40  **********************************************************************/
41 
42 class CLIST_LINK {
43  friend class CLIST_ITERATOR;
44  friend class CLIST;
45 
46  CLIST_LINK *next;
47  void *data;
48 
49 public:
50  CLIST_LINK() { // constructor
51  data = next = nullptr;
52  }
53 
54  CLIST_LINK(const CLIST_LINK &) = delete;
55  void operator=(const CLIST_LINK &) = delete;
56 };
57 
58 /**********************************************************************
59  * CLASS - CLIST
60  *
61  * Generic list class for singly linked CONS cell lists
62  **********************************************************************/
63 
64 class TESS_API CLIST {
65  friend class CLIST_ITERATOR;
66 
67  CLIST_LINK *last = nullptr; // End of list
68 
69  //(Points to head)
70  CLIST_LINK *First() { // return first
71  return last != nullptr ? last->next : nullptr;
72  }
73 
74  const CLIST_LINK *First() const { // return first
75  return last != nullptr ? last->next : nullptr;
76  }
77 
78 public:
79  ~CLIST() { // destructor
80  shallow_clear();
81  }
82 
83  void internal_deep_clear( // destroy all links
84  void (*zapper)(void *)); // ptr to zapper functn
85 
86  void shallow_clear(); // clear list but don't
87  // delete data elements
88 
89  bool empty() const { // is list empty?
90  return !last;
91  }
92 
93  bool singleton() const {
94  return last != nullptr ? (last == last->next) : false;
95  }
96 
97  void shallow_copy( // dangerous!!
98  CLIST *from_list) { // beware destructors!!
99  last = from_list->last;
100  }
101 
102  void assign_to_sublist( // to this list
103  CLIST_ITERATOR *start_it, // from list start
104  CLIST_ITERATOR *end_it); // from list end
105 
106  int32_t length() const { //# elements in list
107  int32_t count = 0;
108  if (last != nullptr) {
109  count = 1;
110  for (auto it = last->next; it != last; it = it->next) {
111  count++;
112  }
113  }
114  return count;
115  }
116 
117  void sort( // sort elements
118  int comparator( // comparison routine
119  const void *, const void *));
120 
121  // Assuming list has been sorted already, insert new_data to
122  // keep the list sorted according to the same comparison function.
123  // Comparison function is the same as used by sort, i.e. uses double
124  // indirection. Time is O(1) to add to beginning or end.
125  // Time is linear to add pre-sorted items to an empty list.
126  // If unique, then don't add duplicate entries.
127  // Returns true if the element was added to the list.
128  bool add_sorted(int comparator(const void *, const void *), bool unique, void *new_data);
129 
130  // Assuming that the minuend and subtrahend are already sorted with
131  // the same comparison function, shallow clears this and then copies
132  // the set difference minuend - subtrahend to this, being the elements
133  // of minuend that do not compare equal to anything in subtrahend.
134  // If unique is true, any duplicates in minuend are also eliminated.
135  void set_subtract(int comparator(const void *, const void *), bool unique, CLIST *minuend,
136  CLIST *subtrahend);
137 };
138 
139 /***********************************************************************
140  * CLASS - CLIST_ITERATOR
141  *
142  * Generic iterator class for singly linked lists with embedded
143  *links
144  **********************************************************************/
145 
148 
149  CLIST *list; // List being iterated
150  CLIST_LINK *prev; // prev element
151  CLIST_LINK *current; // current element
152  CLIST_LINK *next; // next element
153  CLIST_LINK *cycle_pt; // point we are cycling the list to.
154  bool ex_current_was_last; // current extracted was end of list
155  bool ex_current_was_cycle_pt; // current extracted was cycle point
156  bool started_cycling; // Have we moved off the start?
157 
158  CLIST_LINK *extract_sublist( // from this current...
159  CLIST_ITERATOR *other_it); // to other current
160 
161 public:
162  CLIST_ITERATOR() { // constructor
163  list = nullptr;
164  } // unassigned list
165 
166  CLIST_ITERATOR( // constructor
167  CLIST *list_to_iterate);
168 
169  void set_to_list( // change list
170  CLIST *list_to_iterate);
171 
172  void add_after_then_move( // add after current &
173  void *new_data); // move to new
174 
175  void add_after_stay_put( // add after current &
176  void *new_data); // stay at current
177 
178  void add_before_then_move( // add before current &
179  void *new_data); // move to new
180 
181  void add_before_stay_put( // add before current &
182  void *new_data); // stay at current
183 
184  void add_list_after( // add a list &
185  CLIST *list_to_add); // stay at current
186 
187  void add_list_before( // add a list &
188  CLIST *list_to_add); // move to it 1st item
189 
190  void *data() { // get current data
191 #ifndef NDEBUG
192  if (!list) {
193  NO_LIST.error("CLIST_ITERATOR::data", ABORT, nullptr);
194  }
195 #endif
196  return current->data;
197  }
198 
199  void *data_relative( // get data + or - ...
200  int8_t offset); // offset from current
201 
202  void *forward(); // move to next element
203 
204  void *extract(); // remove from list
205 
206  void *move_to_first(); // go to start of list
207 
208  void *move_to_last(); // go to end of list
209 
210  void mark_cycle_pt(); // remember current
211 
212  bool empty() const { // is list empty?
213  return list->empty();
214  }
215 
216  bool current_extracted() const { // current extracted?
217  return !current;
218  }
219 
220  bool at_first() const; // Current is first?
221 
222  bool at_last() const; // Current is last?
223 
224  bool cycled_list() const; // Completed a cycle?
225 
226  void add_to_end( // add at end &
227  void *new_data); // don't move
228 
229  void exchange( // positions of 2 links
230  CLIST_ITERATOR *other_it); // other iterator
231 
232  int32_t length() const; //# elements in list
233 
234  void sort( // sort elements
235  int comparator( // comparison routine
236  const void *, const void *));
237 };
238 
239 /***********************************************************************
240  * CLIST_ITERATOR::set_to_list
241  *
242  * (Re-)initialise the iterator to point to the start of the list_to_iterate
243  * over.
244  **********************************************************************/
245 
246 inline void CLIST_ITERATOR::set_to_list( // change list
247  CLIST *list_to_iterate) {
248  list = list_to_iterate;
249  prev = list->last;
250  current = list->First();
251  next = current != nullptr ? current->next : nullptr;
252  cycle_pt = nullptr; // await explicit set
253  started_cycling = false;
254  ex_current_was_last = false;
255  ex_current_was_cycle_pt = false;
256 }
257 
258 /***********************************************************************
259  * CLIST_ITERATOR::CLIST_ITERATOR
260  *
261  * CONSTRUCTOR - set iterator to specified list;
262  **********************************************************************/
263 
264 inline CLIST_ITERATOR::CLIST_ITERATOR(CLIST *list_to_iterate) {
265  set_to_list(list_to_iterate);
266 }
267 
268 /***********************************************************************
269  * CLIST_ITERATOR::add_after_then_move
270  *
271  * Add a new element to the list after the current element and move the
272  * iterator to the new element.
273  **********************************************************************/
274 
275 inline void CLIST_ITERATOR::add_after_then_move( // element to add
276  void *new_data) {
277 #ifndef NDEBUG
278  if (!new_data) {
279  BAD_PARAMETER.error("CLIST_ITERATOR::add_after_then_move", ABORT, "new_data is nullptr");
280  }
281 #endif
282 
283  auto new_element = new CLIST_LINK;
284  new_element->data = new_data;
285 
286  if (list->empty()) {
287  new_element->next = new_element;
288  list->last = new_element;
289  prev = next = new_element;
290  } else {
291  new_element->next = next;
292 
293  if (current) { // not extracted
294  current->next = new_element;
295  prev = current;
296  if (current == list->last) {
297  list->last = new_element;
298  }
299  } else { // current extracted
300  prev->next = new_element;
301  if (ex_current_was_last) {
302  list->last = new_element;
303  }
304  if (ex_current_was_cycle_pt) {
305  cycle_pt = new_element;
306  }
307  }
308  }
309  current = new_element;
310 }
311 
312 /***********************************************************************
313  * CLIST_ITERATOR::add_after_stay_put
314  *
315  * Add a new element to the list after the current element but do not move
316  * the iterator to the new element.
317  **********************************************************************/
318 
319 inline void CLIST_ITERATOR::add_after_stay_put( // element to add
320  void *new_data) {
321 #ifndef NDEBUG
322  if (!new_data) {
323  BAD_PARAMETER.error("CLIST_ITERATOR::add_after_stay_put", ABORT, "new_data is nullptr");
324  }
325 #endif
326 
327  auto new_element = new CLIST_LINK;
328  new_element->data = new_data;
329 
330  if (list->empty()) {
331  new_element->next = new_element;
332  list->last = new_element;
333  prev = next = new_element;
334  ex_current_was_last = false;
335  current = nullptr;
336  } else {
337  new_element->next = next;
338 
339  if (current) { // not extracted
340  current->next = new_element;
341  if (prev == current) {
342  prev = new_element;
343  }
344  if (current == list->last) {
345  list->last = new_element;
346  }
347  } else { // current extracted
348  prev->next = new_element;
349  if (ex_current_was_last) {
350  list->last = new_element;
351  ex_current_was_last = false;
352  }
353  }
354  next = new_element;
355  }
356 }
357 
358 /***********************************************************************
359  * CLIST_ITERATOR::add_before_then_move
360  *
361  * Add a new element to the list before the current element and move the
362  * iterator to the new element.
363  **********************************************************************/
364 
365 inline void CLIST_ITERATOR::add_before_then_move( // element to add
366  void *new_data) {
367 #ifndef NDEBUG
368  if (!new_data) {
369  BAD_PARAMETER.error("CLIST_ITERATOR::add_before_then_move", ABORT, "new_data is nullptr");
370  }
371 #endif
372 
373  auto new_element = new CLIST_LINK;
374  new_element->data = new_data;
375 
376  if (list->empty()) {
377  new_element->next = new_element;
378  list->last = new_element;
379  prev = next = new_element;
380  } else {
381  prev->next = new_element;
382  if (current) { // not extracted
383  new_element->next = current;
384  next = current;
385  } else { // current extracted
386  new_element->next = next;
387  if (ex_current_was_last) {
388  list->last = new_element;
389  }
390  if (ex_current_was_cycle_pt) {
391  cycle_pt = new_element;
392  }
393  }
394  }
395  current = new_element;
396 }
397 
398 /***********************************************************************
399  * CLIST_ITERATOR::add_before_stay_put
400  *
401  * Add a new element to the list before the current element but don't move the
402  * iterator to the new element.
403  **********************************************************************/
404 
405 inline void CLIST_ITERATOR::add_before_stay_put( // element to add
406  void *new_data) {
407 #ifndef NDEBUG
408  if (!new_data) {
409  BAD_PARAMETER.error("CLIST_ITERATOR::add_before_stay_put", ABORT, "new_data is nullptr");
410  }
411 #endif
412 
413  auto new_element = new CLIST_LINK;
414  new_element->data = new_data;
415 
416  if (list->empty()) {
417  new_element->next = new_element;
418  list->last = new_element;
419  prev = next = new_element;
420  ex_current_was_last = true;
421  current = nullptr;
422  } else {
423  prev->next = new_element;
424  if (current) { // not extracted
425  new_element->next = current;
426  if (next == current) {
427  next = new_element;
428  }
429  } else { // current extracted
430  new_element->next = next;
431  if (ex_current_was_last) {
432  list->last = new_element;
433  }
434  }
435  prev = new_element;
436  }
437 }
438 
439 /***********************************************************************
440  * CLIST_ITERATOR::add_list_after
441  *
442  * Insert another list to this list after the current element but don't move
443  *the
444  * iterator.
445  **********************************************************************/
446 
447 inline void CLIST_ITERATOR::add_list_after(CLIST *list_to_add) {
448  if (!list_to_add->empty()) {
449  if (list->empty()) {
450  list->last = list_to_add->last;
451  prev = list->last;
452  next = list->First();
453  ex_current_was_last = true;
454  current = nullptr;
455  } else {
456  if (current) { // not extracted
457  current->next = list_to_add->First();
458  if (current == list->last) {
459  list->last = list_to_add->last;
460  }
461  list_to_add->last->next = next;
462  next = current->next;
463  } else { // current extracted
464  prev->next = list_to_add->First();
465  if (ex_current_was_last) {
466  list->last = list_to_add->last;
467  ex_current_was_last = false;
468  }
469  list_to_add->last->next = next;
470  next = prev->next;
471  }
472  }
473  list_to_add->last = nullptr;
474  }
475 }
476 
477 /***********************************************************************
478  * CLIST_ITERATOR::add_list_before
479  *
480  * Insert another list to this list before the current element. Move the
481  * iterator to the start of the inserted elements
482  * iterator.
483  **********************************************************************/
484 
485 inline void CLIST_ITERATOR::add_list_before(CLIST *list_to_add) {
486  if (!list_to_add->empty()) {
487  if (list->empty()) {
488  list->last = list_to_add->last;
489  prev = list->last;
490  current = list->First();
491  next = current->next;
492  ex_current_was_last = false;
493  } else {
494  prev->next = list_to_add->First();
495  if (current) { // not extracted
496  list_to_add->last->next = current;
497  } else { // current extracted
498  list_to_add->last->next = next;
499  if (ex_current_was_last) {
500  list->last = list_to_add->last;
501  }
502  if (ex_current_was_cycle_pt) {
503  cycle_pt = prev->next;
504  }
505  }
506  current = prev->next;
507  next = current->next;
508  }
509  list_to_add->last = nullptr;
510  }
511 }
512 
513 /***********************************************************************
514  * CLIST_ITERATOR::extract
515  *
516  * Do extraction by removing current from the list, deleting the cons cell
517  * and returning the data to the caller, but NOT updating the iterator. (So
518  * that any calling loop can do this.) The iterator's current points to
519  * nullptr. If the data is to be deleted, this is the callers responsibility.
520  **********************************************************************/
521 
522 inline void *CLIST_ITERATOR::extract() {
523 #ifndef NDEBUG
524  if (!current) { // list empty or
525  // element extracted
526  NULL_CURRENT.error("CLIST_ITERATOR::extract", ABORT, nullptr);
527  }
528 #endif
529 
530  if (list->singleton()) {
531  // Special case where we do need to change the iterator.
532  prev = next = list->last = nullptr;
533  } else {
534  prev->next = next; // remove from list
535 
536  if (current == list->last) {
537  list->last = prev;
538  ex_current_was_last = true;
539  } else {
540  ex_current_was_last = false;
541  }
542  }
543  // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
544  ex_current_was_cycle_pt = (current == cycle_pt);
545  auto extracted_data = current->data;
546  delete (current); // destroy CONS cell
547  current = nullptr;
548  return extracted_data;
549 }
550 
551 /***********************************************************************
552  * CLIST_ITERATOR::move_to_first()
553  *
554  * Move current so that it is set to the start of the list.
555  * Return data just in case anyone wants it.
556  **********************************************************************/
557 
559  current = list->First();
560  prev = list->last;
561  next = current != nullptr ? current->next : nullptr;
562  return current != nullptr ? current->data : nullptr;
563 }
564 
565 /***********************************************************************
566  * CLIST_ITERATOR::mark_cycle_pt()
567  *
568  * Remember the current location so that we can tell whether we've returned
569  * to this point later.
570  *
571  * If the current point is deleted either now, or in the future, the cycle
572  * point will be set to the next item which is set to current. This could be
573  * by a forward, add_after_then_move or add_after_then_move.
574  **********************************************************************/
575 
577 #ifndef NDEBUG
578  if (!list) {
579  NO_LIST.error("CLIST_ITERATOR::mark_cycle_pt", ABORT, nullptr);
580  }
581 #endif
582 
583  if (current) {
584  cycle_pt = current;
585  } else {
586  ex_current_was_cycle_pt = true;
587  }
588  started_cycling = false;
589 }
590 
591 /***********************************************************************
592  * CLIST_ITERATOR::at_first()
593  *
594  * Are we at the start of the list?
595  *
596  **********************************************************************/
597 
598 inline bool CLIST_ITERATOR::at_first() const {
599  // we're at a deleted
600  return ((list->empty()) || (current == list->First()) ||
601  ((current == nullptr) && (prev == list->last) && // NON-last pt between
602  !ex_current_was_last)); // first and last
603 }
604 
605 /***********************************************************************
606  * CLIST_ITERATOR::at_last()
607  *
608  * Are we at the end of the list?
609  *
610  **********************************************************************/
611 
612 inline bool CLIST_ITERATOR::at_last() const {
613  // we're at a deleted
614  return ((list->empty()) || (current == list->last) ||
615  ((current == nullptr) && (prev == list->last) && // last point between
616  ex_current_was_last)); // first and last
617 }
618 
619 /***********************************************************************
620  * CLIST_ITERATOR::cycled_list()
621  *
622  * Have we returned to the cycle_pt since it was set?
623  *
624  **********************************************************************/
625 
626 inline bool CLIST_ITERATOR::cycled_list() const {
627  return ((list->empty()) || ((current == cycle_pt) && started_cycling));
628 }
629 
630 /***********************************************************************
631  * CLIST_ITERATOR::length()
632  *
633  * Return the length of the list
634  *
635  **********************************************************************/
636 
637 inline int32_t CLIST_ITERATOR::length() const {
638  return list->length();
639 }
640 
641 /***********************************************************************
642  * CLIST_ITERATOR::sort()
643  *
644  * Sort the elements of the list, then reposition at the start.
645  *
646  **********************************************************************/
647 
648 inline void CLIST_ITERATOR::sort( // sort elements
649  int comparator( // comparison routine
650  const void *, const void *)) {
651  list->sort(comparator);
652  move_to_first();
653 }
654 
655 /***********************************************************************
656  * CLIST_ITERATOR::add_to_end
657  *
658  * Add a new element to the end of the list without moving the iterator.
659  * This is provided because a single linked list cannot move to the last as
660  * the iterator couldn't set its prev pointer. Adding to the end is
661  * essential for implementing
662  queues.
663 **********************************************************************/
664 
665 inline void CLIST_ITERATOR::add_to_end( // element to add
666  void *new_data) {
667 #ifndef NDEBUG
668  if (!list) {
669  NO_LIST.error("CLIST_ITERATOR::add_to_end", ABORT, nullptr);
670  }
671  if (!new_data) {
672  BAD_PARAMETER.error("CLIST_ITERATOR::add_to_end", ABORT, "new_data is nullptr");
673  }
674 #endif
675 
676  if (this->at_last()) {
677  this->add_after_stay_put(new_data);
678  } else {
679  if (this->at_first()) {
680  this->add_before_stay_put(new_data);
681  list->last = prev;
682  } else { // Iteratr is elsewhere
683  auto new_element = new CLIST_LINK;
684  new_element->data = new_data;
685 
686  new_element->next = list->last->next;
687  list->last->next = new_element;
688  list->last = new_element;
689  }
690  }
691 }
692 
693 template <typename CLASSNAME>
694 class X_CLIST : public CLIST {
695 public:
696  X_CLIST() = default;
697  X_CLIST(const X_CLIST &) = delete;
698  X_CLIST &operator=(const X_CLIST &) = delete;
699 
700  void deep_clear() {
701  internal_deep_clear([](void *link) {delete static_cast<CLASSNAME *>(link);});
702  }
703 };
704 
705 #define CLISTIZEH(CLASSNAME) \
706  class CLASSNAME##_CLIST : public X_CLIST<CLASSNAME> { \
707  public: \
708  using X_CLIST<CLASSNAME>::X_CLIST; \
709  }; \
710  class CLASSNAME##_C_IT : public X_ITER<CLIST_ITERATOR, CLASSNAME> { \
711  public: \
712  using X_ITER<CLIST_ITERATOR, CLASSNAME>::X_ITER; \
713  CLASSNAME##_C_IT(CLASSNAME##_CLIST *list) : X_ITER(list) {} \
714  };
715 
716 } // namespace tesseract
717 
718 #endif
LIST last(LIST var_list)
Definition: oldlist.cpp:153
constexpr ERRCODE BAD_PARAMETER("List parameter error")
constexpr ERRCODE NULL_CURRENT("List current position is nullptr")
constexpr ERRCODE NO_LIST("Iterator not set to a list")
@ ABORT
Definition: errcode.h:31
void operator=(const CLIST_LINK &)=delete
CLIST_LINK(const CLIST_LINK &)=delete
void sort(int comparator(const void *, const void *))
Definition: clst.cpp:104
int32_t length() const
Definition: clst.h:106
bool singleton() const
Definition: clst.h:93
void shallow_copy(CLIST *from_list)
Definition: clst.h:97
void assign_to_sublist(CLIST_ITERATOR *start_it, CLIST_ITERATOR *end_it)
Definition: clst.cpp:86
bool empty() const
Definition: clst.h:89
void internal_deep_clear(void(*zapper)(void *))
Definition: clst.cpp:36
void add_to_end(void *new_data)
Definition: clst.h:665
bool cycled_list() const
Definition: clst.h:626
void add_after_stay_put(void *new_data)
Definition: clst.h:319
void add_before_then_move(void *new_data)
Definition: clst.h:365
bool at_last() const
Definition: clst.h:612
void * move_to_first()
Definition: clst.h:558
bool current_extracted() const
Definition: clst.h:216
bool empty() const
Definition: clst.h:212
void add_list_after(CLIST *list_to_add)
Definition: clst.h:447
void set_to_list(CLIST *list_to_iterate)
Definition: clst.h:246
bool at_first() const
Definition: clst.h:598
int32_t length() const
Definition: clst.h:637
void add_after_then_move(void *new_data)
Definition: clst.h:275
void add_list_before(CLIST *list_to_add)
Definition: clst.h:485
void sort(int comparator(const void *, const void *))
Definition: clst.h:648
void add_before_stay_put(void *new_data)
Definition: clst.h:405
X_CLIST & operator=(const X_CLIST &)=delete
X_CLIST(const X_CLIST &)=delete
void deep_clear()
Definition: clst.h:700
void error(const char *caller, TessErrorLogCode action, const char *format,...) const __attribute__((format(printf
Definition: errcode.cpp:38
list_rec * next
Definition: oldlist.h:105
#define TESS_API
Definition: export.h:34