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