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