Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccutil/clst.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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);
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
213 void *CLIST_ITERATOR::forward() {
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);
250 if (list->empty())
251 EMPTY_LIST.error("CLIST_ITERATOR::data_relative", ABORT);
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
275 void *CLIST_ITERATOR::move_to_last() {
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);
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);
393 if (list->empty())
394 EMPTY_LIST.error("CLIST_ITERATOR::extract_sublist", ABORT);
395
396 if (!current || !other_it->current)
397 DONT_EXTRACT_DELETED.error("CLIST_ITERATOR.extract_sublist", ABORT);
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);
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