Mercurial > hgrepos > Python2 > PyMuPDF

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