Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccutil/elst2.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: 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);
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
162 ELIST2_LINK *ELIST2_ITERATOR::forward() {
163 #ifndef NDEBUG
164 if (!list)
165 NO_LIST.error("ELIST2_ITERATOR::forward", ABORT);
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);
187 #endif
188
189 next = current->next;
190
191 #ifndef NDEBUG
192 if (!next) {
193 NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT,
194 "This is: %p Current is: %p",
195 static_cast<void *>(this),
196 static_cast<void *>(current));
197 }
198 #endif
199
200 return current;
201 }
202
203 /***********************************************************************
204 * ELIST2_ITERATOR::backward
205 *
206 * Move the iterator to the previous element of the list.
207 * REMEMBER: ALL LISTS ARE CIRCULAR.
208 **********************************************************************/
209
210 ELIST2_LINK *ELIST2_ITERATOR::backward() {
211 #ifndef NDEBUG
212 if (!list)
213 NO_LIST.error("ELIST2_ITERATOR::backward", ABORT);
214 #endif
215 if (list->empty()) {
216 return nullptr;
217 }
218
219 if (current) { // not removed so
220 // set previous
221 next = current;
222 started_cycling = true;
223 // In case prev is deleted by another iterator, get it from current.
224 current = current->prev;
225 } else {
226 if (ex_current_was_cycle_pt) {
227 cycle_pt = prev;
228 }
229 current = prev;
230 }
231
232 #ifndef NDEBUG
233 if (!current)
234 NULL_DATA.error("ELIST2_ITERATOR::backward", ABORT);
235 if (!prev) {
236 NULL_PREV.error("ELIST2_ITERATOR::backward", ABORT,
237 "This is: %p Current is: %p",
238 static_cast<void *>(this),
239 static_cast<void *>(current));
240 }
241 #endif
242
243 prev = current->prev;
244 return current;
245 }
246
247 /***********************************************************************
248 * ELIST2_ITERATOR::data_relative
249 *
250 * Return the data pointer to the element "offset" elements from current.
251 * (This function can't be INLINEd because it contains a loop)
252 **********************************************************************/
253
254 ELIST2_LINK *ELIST2_ITERATOR::data_relative( // get data + or - ..
255 int8_t offset) { // offset from current
256 ELIST2_LINK *ptr;
257
258 #ifndef NDEBUG
259 if (!list)
260 NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
261 if (list->empty())
262 EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
263 #endif
264
265 if (offset < 0) {
266 for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) {
267 ;
268 }
269 } else {
270 for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
271 ;
272 }
273 }
274
275 #ifndef NDEBUG
276 if (!ptr)
277 NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT);
278 #endif
279
280 return ptr;
281 }
282
283 /***********************************************************************
284 * ELIST2_ITERATOR::exchange()
285 *
286 * Given another iterator, whose current element is a different element on
287 * the same list list OR an element of another list, exchange the two current
288 * elements. On return, each iterator points to the element which was the
289 * other iterators current on entry.
290 * (This function hasn't been in-lined because its a bit big!)
291 **********************************************************************/
292
293 void ELIST2_ITERATOR::exchange( // positions of 2 links
294 ELIST2_ITERATOR *other_it) { // other iterator
295 constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists");
296
297 ELIST2_LINK *old_current;
298
299 #ifndef NDEBUG
300 if (!list)
301 NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT);
302 if (!other_it)
303 BAD_PARAMETER.error("ELIST2_ITERATOR::exchange", ABORT, "other_it nullptr");
304 if (!(other_it->list))
305 NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT, "other_it");
306 #endif
307
308 /* Do nothing if either list is empty or if both iterators reference the same
309 link */
310
311 if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) {
312 return;
313 }
314
315 /* Error if either current element is deleted */
316
317 if (!current || !other_it->current) {
318 DONT_EXCHANGE_DELETED.error("ELIST2_ITERATOR.exchange", ABORT);
319 }
320
321 /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
322 (other before this); non-doubleton adjacent elements (this before other);
323 non-adjacent elements. */
324
325 // adjacent links
326 if ((next == other_it->current) || (other_it->next == current)) {
327 // doubleton list
328 if ((next == other_it->current) && (other_it->next == current)) {
329 prev = next = current;
330 other_it->prev = other_it->next = other_it->current;
331 } else { // non-doubleton with
332 // adjacent links
333 // other before this
334 if (other_it->next == current) {
335 other_it->prev->next = current;
336 other_it->current->next = next;
337 other_it->current->prev = current;
338 current->next = other_it->current;
339 current->prev = other_it->prev;
340 next->prev = other_it->current;
341
342 other_it->next = other_it->current;
343 prev = current;
344 } else { // this before other
345 prev->next = other_it->current;
346 current->next = other_it->next;
347 current->prev = other_it->current;
348 other_it->current->next = current;
349 other_it->current->prev = prev;
350 other_it->next->prev = current;
351
352 next = current;
353 other_it->prev = other_it->current;
354 }
355 }
356 } else { // no overlap
357 prev->next = other_it->current;
358 current->next = other_it->next;
359 current->prev = other_it->prev;
360 next->prev = other_it->current;
361 other_it->prev->next = current;
362 other_it->current->next = next;
363 other_it->current->prev = prev;
364 other_it->next->prev = current;
365 }
366
367 /* update end of list pointer when necessary (remember that the 2 iterators
368 may iterate over different lists!) */
369
370 if (list->last == current) {
371 list->last = other_it->current;
372 }
373 if (other_it->list->last == other_it->current) {
374 other_it->list->last = current;
375 }
376
377 if (current == cycle_pt) {
378 cycle_pt = other_it->cycle_pt;
379 }
380 if (other_it->current == other_it->cycle_pt) {
381 other_it->cycle_pt = cycle_pt;
382 }
383
384 /* The actual exchange - in all cases*/
385
386 old_current = current;
387 current = other_it->current;
388 other_it->current = old_current;
389 }
390
391 /***********************************************************************
392 * ELIST2_ITERATOR::extract_sublist()
393 *
394 * This is a private member, used only by ELIST2::assign_to_sublist.
395 * Given another iterator for the same list, extract the links from THIS to
396 * OTHER inclusive, link them into a new circular list, and return a
397 * pointer to the last element.
398 * (Can't inline this function because it contains a loop)
399 **********************************************************************/
400
401 ELIST2_LINK *ELIST2_ITERATOR::extract_sublist( // from this current
402 ELIST2_ITERATOR *other_it) { // to other current
403 #ifndef NDEBUG
404 constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists");
405 constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points");
406 #endif
407 constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
408
409 ELIST2_ITERATOR temp_it = *this;
410 ELIST2_LINK *end_of_new_list;
411
412 #ifndef NDEBUG
413 if (!other_it)
414 BAD_PARAMETER.error("ELIST2_ITERATOR::extract_sublist", ABORT, "other_it nullptr");
415 if (!list)
416 NO_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT);
417 if (list != other_it->list)
418 BAD_EXTRACTION_PTS.error("ELIST2_ITERATOR.extract_sublist", ABORT);
419 if (list->empty())
420 EMPTY_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT);
421
422 if (!current || !other_it->current)
423 DONT_EXTRACT_DELETED.error("ELIST2_ITERATOR.extract_sublist", ABORT);
424 #endif
425
426 ex_current_was_last = other_it->ex_current_was_last = false;
427 ex_current_was_cycle_pt = false;
428 other_it->ex_current_was_cycle_pt = false;
429
430 temp_it.mark_cycle_pt();
431 do { // walk sublist
432 if (temp_it.cycled_list()) { // can't find end pt
433 BAD_SUBLIST.error("ELIST2_ITERATOR.extract_sublist", ABORT);
434 }
435
436 if (temp_it.at_last()) {
437 list->last = prev;
438 ex_current_was_last = other_it->ex_current_was_last = true;
439 }
440
441 if (temp_it.current == cycle_pt) {
442 ex_current_was_cycle_pt = true;
443 }
444
445 if (temp_it.current == other_it->cycle_pt) {
446 other_it->ex_current_was_cycle_pt = true;
447 }
448
449 temp_it.forward();
450 }
451 // do INCLUSIVE list
452 while (temp_it.prev != other_it->current);
453
454 // circularise sublist
455 other_it->current->next = current;
456 // circularise sublist
457 current->prev = other_it->current;
458 end_of_new_list = other_it->current;
459
460 // sublist = whole list
461 if (prev == other_it->current) {
462 list->last = nullptr;
463 prev = current = next = nullptr;
464 other_it->prev = other_it->current = other_it->next = nullptr;
465 } else {
466 prev->next = other_it->next;
467 other_it->next->prev = prev;
468
469 current = other_it->current = nullptr;
470 next = other_it->next;
471 other_it->prev = prev;
472 }
473 return end_of_new_list;
474 }
475
476 } // namespace tesseract