tesseract  5.0.0
elst.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: elst.cpp (Formerly elist.c)
3  * Description: Embedded list handling code which is not in the 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 #include "elst.h"
20 #include <cstdlib>
21 
22 namespace tesseract {
23 
24 /***********************************************************************
25  * ELIST::internal_clear
26  *
27  * Used by the destructor and the "clear" member function of derived list
28  * classes to destroy all the elements on the list.
29  * The calling function passes a "zapper" function which can be called to
30  * delete each element of the list, regardless of its derived type. This
31  * technique permits a generic clear function to destroy elements of
32  * different derived types correctly, without requiring virtual functions and
33  * the consequential memory overhead.
34  **********************************************************************/
35 
36 void ELIST::internal_clear( // destroy all links
37  void (*zapper)(void *)) {
38  // ptr to zapper functn
39  ELIST_LINK *ptr;
40  ELIST_LINK *next;
41 
42  if (!empty()) {
43  ptr = last->next; // set to first
44  last->next = nullptr; // break circle
45  last = nullptr; // set list empty
46  while (ptr) {
47  next = ptr->next;
48  zapper(ptr);
49  ptr = next;
50  }
51  }
52 }
53 
54 /***********************************************************************
55  * ELIST::assign_to_sublist
56  *
57  * The list is set to a sublist of another list. "This" list must be empty
58  * before this function is invoked. The two iterators passed must refer to
59  * the same list, different from "this" one. The sublist removed is the
60  * inclusive list from start_it's current position to end_it's current
61  * position. If this range passes over the end of the source list then the
62  * source list has its end set to the previous element of start_it. The
63  * extracted sublist is unaffected by the end point of the source list, its
64  * end point is always the end_it position.
65  **********************************************************************/
66 
67 void ELIST::assign_to_sublist( // to this list
68  ELIST_ITERATOR *start_it, // from list start
69  ELIST_ITERATOR *end_it) { // from list end
70  constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist");
71 
72  if (!empty()) {
73  LIST_NOT_EMPTY.error("ELIST.assign_to_sublist", ABORT, nullptr);
74  }
75 
76  last = start_it->extract_sublist(end_it);
77 }
78 
79 /***********************************************************************
80  * ELIST::sort
81  *
82  * Sort elements on list
83  * NB If you don't like the const declarations in the comparator, coerce yours:
84  * ( int (*)(const void *, const void *)
85  **********************************************************************/
86 
87 void ELIST::sort( // sort elements
88  int comparator( // comparison routine
89  const void *, const void *)) {
90  // Allocate an array of pointers, one per list element.
91  auto count = length();
92 
93  if (count > 0) {
94  // ptr array to sort
95  std::vector<ELIST_LINK *> base;
96  base.reserve(count);
97 
98  ELIST_ITERATOR it(this);
99 
100  // Extract all elements, putting the pointers in the array.
101  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
102  base.push_back(it.extract());
103  }
104 
105  // Sort the pointer array.
106  qsort(&base[0], count, sizeof(base[0]), comparator);
107 
108  // Rebuild the list from the sorted pointers.
109  for (auto current : base) {
110  it.add_to_end(current);
111  }
112  }
113 }
114 
115 // Assuming list has been sorted already, insert new_link to
116 // keep the list sorted according to the same comparison function.
117 // Comparison function is the same as used by sort, i.e. uses double
118 // indirection. Time is O(1) to add to beginning or end.
119 // Time is linear to add pre-sorted items to an empty list.
120 // If unique is set to true and comparator() returns 0 (an entry with the
121 // same information as the one contained in new_link is already in the
122 // list) - new_link is not added to the list and the function returns the
123 // pointer to the identical entry that already exists in the list
124 // (otherwise the function returns new_link).
125 ELIST_LINK *ELIST::add_sorted_and_find(int comparator(const void *, const void *), bool unique,
126  ELIST_LINK *new_link) {
127  // Check for adding at the end.
128  if (last == nullptr || comparator(&last, &new_link) < 0) {
129  if (last == nullptr) {
130  new_link->next = new_link;
131  } else {
132  new_link->next = last->next;
133  last->next = new_link;
134  }
135  last = new_link;
136  } else {
137  // Need to use an iterator.
138  ELIST_ITERATOR it(this);
139  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
140  ELIST_LINK *link = it.data();
141  int compare = comparator(&link, &new_link);
142  if (compare > 0) {
143  break;
144  } else if (unique && compare == 0) {
145  return link;
146  }
147  }
148  if (it.cycled_list()) {
149  it.add_to_end(new_link);
150  } else {
151  it.add_before_then_move(new_link);
152  }
153  }
154  return new_link;
155 }
156 
157 /***********************************************************************
158  * MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR
159  * =========================================
160  **********************************************************************/
161 
162 /***********************************************************************
163  * ELIST_ITERATOR::forward
164  *
165  * Move the iterator to the next element of the list.
166  * REMEMBER: ALL LISTS ARE CIRCULAR.
167  **********************************************************************/
168 
170 #ifndef NDEBUG
171  if (!list)
172  NO_LIST.error("ELIST_ITERATOR::forward", ABORT, nullptr);
173 #endif
174  if (list->empty()) {
175  return nullptr;
176  }
177 
178  if (current) { // not removed so
179  // set previous
180  prev = current;
181  started_cycling = true;
182  // In case next is deleted by another iterator, get next from current.
183  current = current->next;
184  } else {
185  if (ex_current_was_cycle_pt) {
186  cycle_pt = next;
187  }
188  current = next;
189  }
190 #ifndef NDEBUG
191  if (!current)
192  NULL_DATA.error("ELIST_ITERATOR::forward", ABORT, nullptr);
193 #endif
194  next = current->next;
195 
196 #ifndef NDEBUG
197  if (!next)
198  NULL_NEXT.error("ELIST_ITERATOR::forward", ABORT, "This is: %p Current is: %p", this, current);
199 #endif
200  return current;
201 }
202 
203 /***********************************************************************
204  * ELIST_ITERATOR::data_relative
205  *
206  * Return the data pointer to the element "offset" elements from current.
207  * "offset" must not be less than -1.
208  * (This function can't be INLINEd because it contains a loop)
209  **********************************************************************/
210 
212  int8_t offset) { // offset from current
213  ELIST_LINK *ptr;
214 
215 #ifndef NDEBUG
216  if (!list)
217  NO_LIST.error("ELIST_ITERATOR::data_relative", ABORT, nullptr);
218  if (list->empty())
219  EMPTY_LIST.error("ELIST_ITERATOR::data_relative", ABORT, nullptr);
220  if (offset < -1)
221  BAD_PARAMETER.error("ELIST_ITERATOR::data_relative", ABORT, "offset < -l");
222 #endif
223 
224  if (offset == -1) {
225  ptr = prev;
226  } else {
227  for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
228  ;
229  }
230  }
231 
232 #ifndef NDEBUG
233  if (!ptr)
234  NULL_DATA.error("ELIST_ITERATOR::data_relative", ABORT, nullptr);
235 #endif
236 
237  return ptr;
238 }
239 
240 /***********************************************************************
241  * ELIST_ITERATOR::move_to_last()
242  *
243  * Move current so that it is set to the end of the list.
244  * Return data just in case anyone wants it.
245  * (This function can't be INLINEd because it contains a loop)
246  **********************************************************************/
247 
249 #ifndef NDEBUG
250  if (!list)
251  NO_LIST.error("ELIST_ITERATOR::move_to_last", ABORT, nullptr);
252 #endif
253 
254  while (current != list->last) {
255  forward();
256  }
257 
258  return current;
259 }
260 
261 /***********************************************************************
262  * ELIST_ITERATOR::exchange()
263  *
264  * Given another iterator, whose current element is a different element on
265  * the same list list OR an element of another list, exchange the two current
266  * elements. On return, each iterator points to the element which was the
267  * other iterators current on entry.
268  * (This function hasn't been in-lined because its a bit big!)
269  **********************************************************************/
270 
271 void ELIST_ITERATOR::exchange( // positions of 2 links
272  ELIST_ITERATOR *other_it) { // other iterator
273  constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists");
274 
275  ELIST_LINK *old_current;
276 
277 #ifndef NDEBUG
278  if (!list)
279  NO_LIST.error("ELIST_ITERATOR::exchange", ABORT, nullptr);
280  if (!other_it)
281  BAD_PARAMETER.error("ELIST_ITERATOR::exchange", ABORT, "other_it nullptr");
282  if (!(other_it->list))
283  NO_LIST.error("ELIST_ITERATOR::exchange", ABORT, "other_it");
284 #endif
285 
286  /* Do nothing if either list is empty or if both iterators reference the same
287 link */
288 
289  if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) {
290  return;
291  }
292 
293  /* Error if either current element is deleted */
294 
295  if (!current || !other_it->current) {
296  DONT_EXCHANGE_DELETED.error("ELIST_ITERATOR.exchange", ABORT, nullptr);
297  }
298 
299  /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
300 (other before this); non-doubleton adjacent elements (this before other);
301 non-adjacent elements. */
302 
303  // adjacent links
304  if ((next == other_it->current) || (other_it->next == current)) {
305  // doubleton list
306  if ((next == other_it->current) && (other_it->next == current)) {
307  prev = next = current;
308  other_it->prev = other_it->next = other_it->current;
309  } else { // non-doubleton with
310  // adjacent links
311  // other before this
312  if (other_it->next == current) {
313  other_it->prev->next = current;
314  other_it->current->next = next;
315  current->next = other_it->current;
316  other_it->next = other_it->current;
317  prev = current;
318  } else { // this before other
319  prev->next = other_it->current;
320  current->next = other_it->next;
321  other_it->current->next = current;
322  next = current;
323  other_it->prev = other_it->current;
324  }
325  }
326  } else { // no overlap
327  prev->next = other_it->current;
328  current->next = other_it->next;
329  other_it->prev->next = current;
330  other_it->current->next = next;
331  }
332 
333  /* update end of list pointer when necessary (remember that the 2 iterators
334  may iterate over different lists!) */
335 
336  if (list->last == current) {
337  list->last = other_it->current;
338  }
339  if (other_it->list->last == other_it->current) {
340  other_it->list->last = current;
341  }
342 
343  if (current == cycle_pt) {
344  cycle_pt = other_it->cycle_pt;
345  }
346  if (other_it->current == other_it->cycle_pt) {
347  other_it->cycle_pt = cycle_pt;
348  }
349 
350  /* The actual exchange - in all cases*/
351 
352  old_current = current;
353  current = other_it->current;
354  other_it->current = old_current;
355 }
356 
357 /***********************************************************************
358  * ELIST_ITERATOR::extract_sublist()
359  *
360  * This is a private member, used only by ELIST::assign_to_sublist.
361  * Given another iterator for the same list, extract the links from THIS to
362  * OTHER inclusive, link them into a new circular list, and return a
363  * pointer to the last element.
364  * (Can't inline this function because it contains a loop)
365  **********************************************************************/
366 
367 ELIST_LINK *ELIST_ITERATOR::extract_sublist( // from this current
368  ELIST_ITERATOR *other_it) { // to other current
369 #ifndef NDEBUG
370  constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists");
371  constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points");
372 #endif
373  constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
374 
375  ELIST_ITERATOR temp_it = *this;
376  ELIST_LINK *end_of_new_list;
377 
378 #ifndef NDEBUG
379  if (!other_it)
380  BAD_PARAMETER.error("ELIST_ITERATOR::extract_sublist", ABORT, "other_it nullptr");
381  if (!list)
382  NO_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT, nullptr);
383  if (list != other_it->list)
384  BAD_EXTRACTION_PTS.error("ELIST_ITERATOR.extract_sublist", ABORT, nullptr);
385  if (list->empty())
386  EMPTY_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT, nullptr);
387 
388  if (!current || !other_it->current)
389  DONT_EXTRACT_DELETED.error("ELIST_ITERATOR.extract_sublist", ABORT, nullptr);
390 #endif
391 
392  ex_current_was_last = other_it->ex_current_was_last = false;
393  ex_current_was_cycle_pt = false;
394  other_it->ex_current_was_cycle_pt = false;
395 
396  temp_it.mark_cycle_pt();
397  do { // walk sublist
398  if (temp_it.cycled_list()) { // can't find end pt
399  BAD_SUBLIST.error("ELIST_ITERATOR.extract_sublist", ABORT, nullptr);
400  }
401 
402  if (temp_it.at_last()) {
403  list->last = prev;
404  ex_current_was_last = other_it->ex_current_was_last = true;
405  }
406 
407  if (temp_it.current == cycle_pt) {
408  ex_current_was_cycle_pt = true;
409  }
410 
411  if (temp_it.current == other_it->cycle_pt) {
412  other_it->ex_current_was_cycle_pt = true;
413  }
414 
415  temp_it.forward();
416  } while (temp_it.prev != other_it->current);
417 
418  // circularise sublist
419  other_it->current->next = current;
420  end_of_new_list = other_it->current;
421 
422  // sublist = whole list
423  if (prev == other_it->current) {
424  list->last = nullptr;
425  prev = current = next = nullptr;
426  other_it->prev = other_it->current = other_it->next = nullptr;
427  } else {
428  prev->next = other_it->next;
429  current = other_it->current = nullptr;
430  next = other_it->next;
431  other_it->prev = prev;
432  }
433  return end_of_new_list;
434 }
435 
436 } // namespace tesseract
constexpr ERRCODE BAD_PARAMETER("List parameter error")
constexpr ERRCODE NO_LIST("Iterator not set to a list")
constexpr ERRCODE NULL_NEXT("Next element on the list is nullptr")
constexpr ERRCODE EMPTY_LIST("List is empty")
@ ABORT
Definition: errcode.h:31
constexpr ERRCODE NULL_DATA("List would have returned a nullptr data pointer")
int32_t length() const
Definition: elst.h:146
void sort(int comparator(const void *, const void *))
Definition: elst.cpp:87
void assign_to_sublist(ELIST_ITERATOR *start_it, ELIST_ITERATOR *end_it)
Definition: elst.cpp:67
ELIST_LINK * add_sorted_and_find(int comparator(const void *, const void *), bool unique, ELIST_LINK *new_link)
Definition: elst.cpp:125
bool empty() const
Definition: elst.h:124
void internal_clear(void(*zapper)(void *))
Definition: elst.cpp:36
ELIST_LINK * move_to_last()
Definition: elst.cpp:248
bool at_last() const
Definition: elst.h:715
void add_to_end(ELIST_LINK *new_link)
Definition: elst.h:775
void exchange(ELIST_ITERATOR *other_it)
Definition: elst.cpp:271
ELIST_LINK * forward()
Definition: elst.cpp:169
void add_before_then_move(ELIST_LINK *new_link)
Definition: elst.h:429
bool cycled_list() const
Definition: elst.h:735
ELIST_LINK * data()
Definition: elst.h:231
ELIST_LINK * extract()
Definition: elst.h:610
ELIST_LINK * data_relative(int8_t offset)
Definition: elst.cpp:211
void error(const char *caller, TessErrorLogCode action, const char *format,...) const __attribute__((format(printf
Definition: errcode.cpp:38