/src/leptonica/src/ptra.c
Line | Count | Source (jump to first uncovered line) |
1 | | /*====================================================================* |
2 | | - Copyright (C) 2001 Leptonica. All rights reserved. |
3 | | - |
4 | | - Redistribution and use in source and binary forms, with or without |
5 | | - modification, are permitted provided that the following conditions |
6 | | - are met: |
7 | | - 1. Redistributions of source code must retain the above copyright |
8 | | - notice, this list of conditions and the following disclaimer. |
9 | | - 2. Redistributions in binary form must reproduce the above |
10 | | - copyright notice, this list of conditions and the following |
11 | | - disclaimer in the documentation and/or other materials |
12 | | - provided with the distribution. |
13 | | - |
14 | | - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
15 | | - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
16 | | - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
17 | | - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY |
18 | | - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
19 | | - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
20 | | - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
21 | | - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
22 | | - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
23 | | - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
24 | | - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
25 | | *====================================================================*/ |
26 | | |
27 | | /*! |
28 | | * \file ptra.c |
29 | | * <pre> |
30 | | * |
31 | | * Ptra creation and destruction |
32 | | * L_PTRA *ptraCreate() |
33 | | * void *ptraDestroy() |
34 | | * |
35 | | * Add/insert/remove/replace generic ptr object |
36 | | * l_int32 ptraAdd() |
37 | | * static l_int32 ptraExtendArray() |
38 | | * l_int32 ptraInsert() |
39 | | * void *ptraRemove() |
40 | | * void *ptraRemoveLast() |
41 | | * void *ptraReplace() |
42 | | * l_int32 ptraSwap() |
43 | | * l_int32 ptraCompactArray() |
44 | | * |
45 | | * Other array operations |
46 | | * l_int32 ptraReverse() |
47 | | * l_int32 ptraJoin() |
48 | | * |
49 | | * Simple Ptra accessors |
50 | | * l_int32 ptraGetMaxIndex() |
51 | | * l_int32 ptraGetActualCount() |
52 | | * void *ptraGetPtrToItem() |
53 | | * |
54 | | * Ptraa creation and destruction |
55 | | * L_PTRAA *ptraaCreate() |
56 | | * void *ptraaDestroy() |
57 | | * |
58 | | * Ptraa accessors |
59 | | * l_int32 ptraaGetSize() |
60 | | * l_int32 ptraaInsertPtra() |
61 | | * L_PTRA *ptraaGetPtra() |
62 | | * |
63 | | * Ptraa conversion |
64 | | * L_PTRA *ptraaFlattenToPtra() |
65 | | * |
66 | | * Notes on the Ptra: |
67 | | * |
68 | | * (1) The Ptra is a struct, not an array. Always use the accessors |
69 | | * in this file, never the fields directly. |
70 | | * (2) Items can be placed anywhere in the allocated ptr array, |
71 | | * including one index beyond the last ptr (in which case the |
72 | | * ptr array is realloc'd). |
73 | | * (3) Thus, the items on the ptr array need not be compacted. In |
74 | | * general there will be null pointers in the ptr array. |
75 | | * (4) A compacted array will remain compacted on removal if |
76 | | * arbitrary items are removed with compaction, or if items |
77 | | * are removed from the end of the array. |
78 | | * (5) For addition to and removal from the end of the array, this |
79 | | * functions exactly like a stack, and with the same O(1) cost. |
80 | | * (6) This differs from the generic stack in that we allow |
81 | | * random access for insertion, removal and replacement. |
82 | | * Removal can be done without compacting the array. |
83 | | * Insertion into a null ptr in the array has no effect on |
84 | | * the other pointers, but insertion into a location already |
85 | | * occupied by an item has a cost proportional to the |
86 | | * distance to the next null ptr in the array. |
87 | | * (7) Null ptrs are valid input args for both insertion and |
88 | | * replacement; this allows arbitrary swapping. |
89 | | * (8) The item in the array with the largest index is at pa->imax. |
90 | | * This can be any value from -1 (initialized; all array ptrs |
91 | | * are null) up to pa->nalloc - 1 (the last ptr in the array). |
92 | | * (9) In referring to the array: the first ptr is the "top" or |
93 | | * "beginning"; the last pointer is the "bottom" or "end"; |
94 | | * items are shifted "up" towards the top when compaction occurs; |
95 | | * and items are shifted "down" towards the bottom when forced to |
96 | | * move due to an insertion. |
97 | | * (10) It should be emphasized that insertion, removal and replacement |
98 | | * are general: |
99 | | * * You can insert an item into any ptr location in the |
100 | | * allocated ptr array, as well as into the next ptr address |
101 | | * beyond the allocated array (in which case a realloc will occur). |
102 | | * * You can remove or replace an item from any ptr location |
103 | | * in the allocated ptr array. |
104 | | * * When inserting into an occupied location, you have |
105 | | * three options for downshifting. |
106 | | * * When removing, you can either leave the ptr null or |
107 | | * compact the array. |
108 | | * |
109 | | * Notes on the Ptraa: |
110 | | * |
111 | | * (1) The Ptraa is a fixed size ptr array for holding Ptra. |
112 | | * In that respect, it is different from other pointer arrays, which |
113 | | * are extensible and grow using the *Add*() functions. |
114 | | * (2) In general, the Ptra ptrs in the Ptraa can be randomly occupied. |
115 | | * A typical usage is to allow an O(n) horizontal sort of Pix, |
116 | | * where the size of the Ptra array is the width of the image, |
117 | | * and each Ptra is an array of all the Pix at a specific x location. |
118 | | * </pre> |
119 | | */ |
120 | | |
121 | | #ifdef HAVE_CONFIG_H |
122 | | #include <config_auto.h> |
123 | | #endif /* HAVE_CONFIG_H */ |
124 | | |
125 | | #include "allheaders.h" |
126 | | |
127 | | /* Bounds on initial array size */ |
128 | | LEPT_DLL const l_uint32 MaxInitPtraSize = 1000001; |
129 | | static const l_int32 DefaultInitPtraSize = 20; /*!< n'importe quoi */ |
130 | | |
131 | | /* Static function */ |
132 | | static l_int32 ptraExtendArray(L_PTRA *pa); |
133 | | |
134 | | /*--------------------------------------------------------------------------* |
135 | | * Ptra creation and destruction * |
136 | | *--------------------------------------------------------------------------*/ |
137 | | /*! |
138 | | * \brief ptraCreate() |
139 | | * |
140 | | * \param[in] n size of ptr array to be alloc'd; use 0 for default |
141 | | * \return pa, or NULL on error |
142 | | */ |
143 | | L_PTRA * |
144 | | ptraCreate(l_int32 n) |
145 | 0 | { |
146 | 0 | L_PTRA *pa; |
147 | |
|
148 | 0 | if (n > (l_int32)MaxInitPtraSize) { |
149 | 0 | L_ERROR("n = %d > maxsize = %d\n", __func__, n, MaxInitPtraSize); |
150 | 0 | return NULL; |
151 | 0 | } |
152 | 0 | if (n <= 0) n = DefaultInitPtraSize; |
153 | |
|
154 | 0 | pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA)); |
155 | 0 | if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) { |
156 | 0 | ptraDestroy(&pa, 0, 0); |
157 | 0 | return (L_PTRA *)ERROR_PTR("ptr array not made", __func__, NULL); |
158 | 0 | } |
159 | 0 | pa->nalloc = n; |
160 | 0 | pa->imax = -1; |
161 | 0 | pa->nactual = 0; |
162 | 0 | return pa; |
163 | 0 | } |
164 | | |
165 | | |
166 | | /*! |
167 | | * \brief ptraDestroy() |
168 | | * |
169 | | * \param[in,out] ppa will be set to null before returning |
170 | | * \param[in] freeflag TRUE to free each remaining item in the array |
171 | | * \param[in] warnflag TRUE to warn if any remaining items |
172 | | * are not destroyed |
173 | | * \return void |
174 | | * |
175 | | * <pre> |
176 | | * Notes: |
177 | | * (1) If %freeflag == TRUE, frees each item in the array. |
178 | | * (2) If %freeflag == FALSE and %warnflag == TRUE, and there are |
179 | | * items on the array, this gives a warning and destroys the array. |
180 | | * If these items are not owned elsewhere, this will cause |
181 | | * a memory leak of all the items that were on the array. |
182 | | * So if the items are not owned elsewhere and require their |
183 | | * own destroy function, they must be destroyed before the ptra. |
184 | | * (3) If %warnflag == FALSE, no warnings will be issued. This is |
185 | | * useful if the items are owned elsewhere, such as a |
186 | | * PixMemoryStore(). |
187 | | * (4) To destroy the ptra, we destroy the ptr array, then |
188 | | * the ptra, and then null the contents of the input ptr. |
189 | | * </pre> |
190 | | */ |
191 | | void |
192 | | ptraDestroy(L_PTRA **ppa, |
193 | | l_int32 freeflag, |
194 | | l_int32 warnflag) |
195 | 0 | { |
196 | 0 | l_int32 i, nactual; |
197 | 0 | void *item; |
198 | 0 | L_PTRA *pa; |
199 | |
|
200 | 0 | if (ppa == NULL) { |
201 | 0 | L_WARNING("ptr address is NULL\n", __func__); |
202 | 0 | return; |
203 | 0 | } |
204 | 0 | if ((pa = *ppa) == NULL) |
205 | 0 | return; |
206 | | |
207 | 0 | ptraGetActualCount(pa, &nactual); |
208 | 0 | if (nactual > 0) { |
209 | 0 | if (freeflag) { |
210 | 0 | for (i = 0; i <= pa->imax; i++) { |
211 | 0 | if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL) |
212 | 0 | LEPT_FREE(item); |
213 | 0 | } |
214 | 0 | } else if (warnflag) { |
215 | 0 | L_WARNING("potential memory leak of %d items in ptra\n", |
216 | 0 | __func__, nactual); |
217 | 0 | } |
218 | 0 | } |
219 | |
|
220 | 0 | LEPT_FREE(pa->array); |
221 | 0 | LEPT_FREE(pa); |
222 | 0 | *ppa = NULL; |
223 | 0 | } |
224 | | |
225 | | |
226 | | /*--------------------------------------------------------------------------* |
227 | | * Add/insert/remove/replace generic ptr object * |
228 | | *--------------------------------------------------------------------------*/ |
229 | | /*! |
230 | | * \brief ptraAdd() |
231 | | * |
232 | | * \param[in] pa ptra |
233 | | * \param[in] item generic ptr to a struct |
234 | | * \return 0 if OK, 1 on error |
235 | | * |
236 | | * <pre> |
237 | | * Notes: |
238 | | * (1) This adds the element to the next location beyond imax, |
239 | | * which is the largest occupied ptr in the array. This is |
240 | | * what you expect from a stack, where all ptrs up to and |
241 | | * including imax are occupied, but here the occuption of |
242 | | * items in the array is entirely arbitrary. |
243 | | * </pre> |
244 | | */ |
245 | | l_ok |
246 | | ptraAdd(L_PTRA *pa, |
247 | | void *item) |
248 | 0 | { |
249 | 0 | l_int32 imax; |
250 | |
|
251 | 0 | if (!pa) |
252 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
253 | 0 | if (!item) |
254 | 0 | return ERROR_INT("item not defined", __func__, 1); |
255 | | |
256 | 0 | ptraGetMaxIndex(pa, &imax); |
257 | 0 | if (imax >= pa->nalloc - 1 && ptraExtendArray(pa)) |
258 | 0 | return ERROR_INT("extension failure", __func__, 1); |
259 | 0 | pa->array[imax + 1] = (void *)item; |
260 | 0 | pa->imax++; |
261 | 0 | pa->nactual++; |
262 | 0 | return 0; |
263 | 0 | } |
264 | | |
265 | | |
266 | | /*! |
267 | | * \brief ptraExtendArray() |
268 | | * |
269 | | * \param[in] pa |
270 | | * \return 0 if OK, 1 on error |
271 | | */ |
272 | | static l_int32 |
273 | | ptraExtendArray(L_PTRA *pa) |
274 | 0 | { |
275 | 0 | if (!pa) |
276 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
277 | | |
278 | 0 | if ((pa->array = (void **)reallocNew((void **)&pa->array, |
279 | 0 | sizeof(void *) * pa->nalloc, |
280 | 0 | 2 * sizeof(void *) * pa->nalloc)) == NULL) |
281 | 0 | return ERROR_INT("new ptr array not returned", __func__, 1); |
282 | | |
283 | 0 | pa->nalloc *= 2; |
284 | 0 | return 0; |
285 | 0 | } |
286 | | |
287 | | |
288 | | /*! |
289 | | * \brief ptraInsert() |
290 | | * |
291 | | * \param[in] pa ptra |
292 | | * \param[in] index location in ptra to insert new value |
293 | | * \param[in] item generic ptr to a struct; can be null |
294 | | * \param[in] shiftflag L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT |
295 | | * \return 0 if OK, 1 on error |
296 | | * |
297 | | * <pre> |
298 | | * Notes: |
299 | | * (1) This checks first to see if the location is valid, and |
300 | | * then if there is presently an item there. If there is not, |
301 | | * it is simply inserted into that location. |
302 | | * (2) If there is an item at the insert location, items must be |
303 | | * moved down to make room for the insert. In the downward |
304 | | * shift there are three options, given by %shiftflag. |
305 | | * ~ If %shiftflag == L_AUTO_DOWNSHIFT, a decision is made |
306 | | * whether, in a cascade of items, to downshift a minimum |
307 | | * amount or for all items above %index. The decision is |
308 | | * based on the expectation of finding holes (null ptrs) |
309 | | * between %index and the bottom of the array. |
310 | | * Assuming the holes are distributed uniformly, if 2 or more |
311 | | * holes are expected, we do a minimum shift. |
312 | | * ~ If %shiftflag == L_MIN_DOWNSHIFT, the downward shifting |
313 | | * cascade of items progresses a minimum amount, until |
314 | | * the first empty slot is reached. This mode requires |
315 | | * some computation before the actual shifting is done. |
316 | | * ~ If %shiftflag == L_FULL_DOWNSHIFT, a shifting cascade is |
317 | | * performed where pa[i] --> pa[i + 1] for all i >= index. |
318 | | * Then, the item is inserted at pa[index]. |
319 | | * (3) If you are not using L_AUTO_DOWNSHIFT, the rule of thumb is |
320 | | * to use L_FULL_DOWNSHIFT if the array is compacted (each |
321 | | * element points to an item), and to use L_MIN_DOWNSHIFT |
322 | | * if there are a significant number of null pointers. |
323 | | * There is no penalty to using L_MIN_DOWNSHIFT for a |
324 | | * compacted array, however, because the full shift is required |
325 | | * and we don't do the O(n) computation to look for holes. |
326 | | * (4) This should not be used repeatedly on large arrays, |
327 | | * because the function is generally O(n). |
328 | | * (5) However, it can be used repeatedly if we start with an empty |
329 | | * ptr array and insert only once at each location. For example, |
330 | | * you can support an array of Numa, where at each ptr location |
331 | | * you store either 0 or 1 Numa, and the Numa can be added |
332 | | * randomly to the ptr array. |
333 | | * </pre> |
334 | | */ |
335 | | l_ok |
336 | | ptraInsert(L_PTRA *pa, |
337 | | l_int32 index, |
338 | | void *item, |
339 | | l_int32 shiftflag) |
340 | 0 | { |
341 | 0 | l_int32 i, ihole, imax; |
342 | 0 | l_float32 nexpected; |
343 | |
|
344 | 0 | if (!pa) |
345 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
346 | 0 | if (index < 0 || index > pa->nalloc) |
347 | 0 | return ERROR_INT("index not in [0 ... nalloc]", __func__, 1); |
348 | 0 | if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT && |
349 | 0 | shiftflag != L_FULL_DOWNSHIFT) |
350 | 0 | return ERROR_INT("invalid shiftflag", __func__, 1); |
351 | | |
352 | 0 | if (item) pa->nactual++; |
353 | 0 | if (index == pa->nalloc) { /* can happen when index == n */ |
354 | 0 | if (ptraExtendArray(pa)) |
355 | 0 | return ERROR_INT("extension failure", __func__, 1); |
356 | 0 | } |
357 | | |
358 | | /* We are inserting into a hole or adding to the end of the array. |
359 | | * No existing items are moved. */ |
360 | 0 | ptraGetMaxIndex(pa, &imax); |
361 | 0 | if (pa->array[index] == NULL) { |
362 | 0 | pa->array[index] = item; |
363 | 0 | if (item && index > imax) /* new item put beyond max so far */ |
364 | 0 | pa->imax = index; |
365 | 0 | return 0; |
366 | 0 | } |
367 | | |
368 | | /* We are inserting at the location of an existing item, |
369 | | * forcing the existing item and those below to shift down. |
370 | | * First, extend the array automatically if the last element |
371 | | * (nalloc - 1) is occupied (imax). This may not be necessary |
372 | | * in every situation, but only an anomalous sequence of insertions |
373 | | * into the array would cause extra ptr allocation. */ |
374 | 0 | if (imax >= pa->nalloc - 1 && ptraExtendArray(pa)) |
375 | 0 | return ERROR_INT("extension failure", __func__, 1); |
376 | | |
377 | | /* If there are no holes, do a full downshift. |
378 | | * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number |
379 | | * of holes between index and n to determine the shift mode */ |
380 | 0 | if (imax + 1 == pa->nactual) { |
381 | 0 | shiftflag = L_FULL_DOWNSHIFT; |
382 | 0 | } else if (shiftflag == L_AUTO_DOWNSHIFT) { |
383 | 0 | if (imax < 10) { |
384 | 0 | shiftflag = L_FULL_DOWNSHIFT; /* no big deal */ |
385 | 0 | } else { |
386 | 0 | nexpected = (l_float32)(imax - pa->nactual) * |
387 | 0 | (l_float32)((imax - index) / imax); |
388 | 0 | shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT; |
389 | 0 | } |
390 | 0 | } |
391 | |
|
392 | 0 | if (shiftflag == L_MIN_DOWNSHIFT) { /* run down looking for a hole */ |
393 | 0 | for (ihole = index + 1; ihole <= imax; ihole++) { |
394 | 0 | if (pa->array[ihole] == NULL) |
395 | 0 | break; |
396 | 0 | } |
397 | 0 | } else { /* L_FULL_DOWNSHIFT */ |
398 | 0 | ihole = imax + 1; |
399 | 0 | } |
400 | |
|
401 | 0 | for (i = ihole; i > index; i--) |
402 | 0 | pa->array[i] = pa->array[i - 1]; |
403 | 0 | pa->array[index] = (void *)item; |
404 | 0 | if (ihole == imax + 1) /* the last item was shifted down */ |
405 | 0 | pa->imax++; |
406 | |
|
407 | 0 | return 0; |
408 | 0 | } |
409 | | |
410 | | |
411 | | /*! |
412 | | * \brief ptraRemove() |
413 | | * |
414 | | * \param[in] pa ptra |
415 | | * \param[in] index element to be removed |
416 | | * \param[in] flag L_NO_COMPACTION, L_COMPACTION |
417 | | * \return item, or NULL on error |
418 | | * |
419 | | * <pre> |
420 | | * Notes: |
421 | | * (1) If flag == L_NO_COMPACTION, this removes the item and |
422 | | * nulls the ptr on the array. If it takes the last item |
423 | | * in the array, pa->n is reduced to the next item. |
424 | | * (2) If flag == L_COMPACTION, this compacts the array for |
425 | | * for all i >= index. It should not be used repeatedly on |
426 | | * large arrays, because compaction is O(n). |
427 | | * (3) The ability to remove without automatic compaction allows |
428 | | * removal with cost O(1). |
429 | | * </pre> |
430 | | */ |
431 | | void * |
432 | | ptraRemove(L_PTRA *pa, |
433 | | l_int32 index, |
434 | | l_int32 flag) |
435 | 0 | { |
436 | 0 | l_int32 i, imax, fromend, icurrent; |
437 | 0 | void *item; |
438 | |
|
439 | 0 | if (!pa) |
440 | 0 | return (void *)ERROR_PTR("pa not defined", __func__, NULL); |
441 | 0 | ptraGetMaxIndex(pa, &imax); |
442 | 0 | if (index < 0 || index > imax) |
443 | 0 | return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL); |
444 | | |
445 | 0 | item = pa->array[index]; |
446 | 0 | if (item) |
447 | 0 | pa->nactual--; |
448 | 0 | pa->array[index] = NULL; |
449 | | |
450 | | /* If we took the last item, need to reduce pa->n */ |
451 | 0 | fromend = (index == imax); |
452 | 0 | if (fromend) { |
453 | 0 | for (i = index - 1; i >= 0; i--) { |
454 | 0 | if (pa->array[i]) |
455 | 0 | break; |
456 | 0 | } |
457 | 0 | pa->imax = i; |
458 | 0 | } |
459 | | |
460 | | /* Compact from index to the end of the array */ |
461 | 0 | if (!fromend && flag == L_COMPACTION) { |
462 | 0 | for (icurrent = index, i = index + 1; i <= imax; i++) { |
463 | 0 | if (pa->array[i]) |
464 | 0 | pa->array[icurrent++] = pa->array[i]; |
465 | 0 | } |
466 | 0 | pa->imax = icurrent - 1; |
467 | 0 | } |
468 | 0 | return item; |
469 | 0 | } |
470 | | |
471 | | |
472 | | /*! |
473 | | * \brief ptraRemoveLast() |
474 | | * |
475 | | * \param[in] pa ptra |
476 | | * \return item, or NULL on error or if the array is empty |
477 | | */ |
478 | | void * |
479 | | ptraRemoveLast(L_PTRA *pa) |
480 | 0 | { |
481 | 0 | l_int32 imax; |
482 | |
|
483 | 0 | if (!pa) |
484 | 0 | return (void *)ERROR_PTR("pa not defined", __func__, NULL); |
485 | | |
486 | | /* Remove the last item in the array. No compaction is required. */ |
487 | 0 | ptraGetMaxIndex(pa, &imax); |
488 | 0 | if (imax >= 0) |
489 | 0 | return ptraRemove(pa, imax, L_NO_COMPACTION); |
490 | 0 | else /* empty */ |
491 | 0 | return NULL; |
492 | 0 | } |
493 | | |
494 | | |
495 | | /*! |
496 | | * \brief ptraReplace() |
497 | | * |
498 | | * \param[in] pa ptra |
499 | | * \param[in] index element to be replaced |
500 | | * \param[in] item new generic ptr to a struct; can be null |
501 | | * \param[in] freeflag TRUE to free old item; FALSE to return it |
502 | | * \return item old item, if it exists and is not freed, |
503 | | * or NULL on error |
504 | | */ |
505 | | void * |
506 | | ptraReplace(L_PTRA *pa, |
507 | | l_int32 index, |
508 | | void *item, |
509 | | l_int32 freeflag) |
510 | 0 | { |
511 | 0 | l_int32 imax; |
512 | 0 | void *olditem; |
513 | |
|
514 | 0 | if (!pa) |
515 | 0 | return (void *)ERROR_PTR("pa not defined", __func__, NULL); |
516 | 0 | ptraGetMaxIndex(pa, &imax); |
517 | 0 | if (index < 0 || index > imax) |
518 | 0 | return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL); |
519 | | |
520 | 0 | olditem = pa->array[index]; |
521 | 0 | pa->array[index] = item; |
522 | 0 | if (!item && olditem) |
523 | 0 | pa->nactual--; |
524 | 0 | else if (item && !olditem) |
525 | 0 | pa->nactual++; |
526 | |
|
527 | 0 | if (freeflag == FALSE) |
528 | 0 | return olditem; |
529 | | |
530 | 0 | if (olditem) |
531 | 0 | LEPT_FREE(olditem); |
532 | 0 | return NULL; |
533 | 0 | } |
534 | | |
535 | | |
536 | | /*! |
537 | | * \brief ptraSwap() |
538 | | * |
539 | | * \param[in] pa ptra |
540 | | * \param[in] index1 |
541 | | * \param[in] index2 |
542 | | * \return 0 if OK, 1 on error |
543 | | */ |
544 | | l_ok |
545 | | ptraSwap(L_PTRA *pa, |
546 | | l_int32 index1, |
547 | | l_int32 index2) |
548 | 0 | { |
549 | 0 | l_int32 imax; |
550 | 0 | void *item; |
551 | |
|
552 | 0 | if (!pa) |
553 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
554 | 0 | if (index1 == index2) |
555 | 0 | return 0; |
556 | 0 | ptraGetMaxIndex(pa, &imax); |
557 | 0 | if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax) |
558 | 0 | return ERROR_INT("invalid index: not in [0 ... imax]", __func__, 1); |
559 | | |
560 | 0 | item = ptraRemove(pa, index1, L_NO_COMPACTION); |
561 | 0 | item = ptraReplace(pa, index2, item, FALSE); |
562 | 0 | ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT); |
563 | 0 | return 0; |
564 | 0 | } |
565 | | |
566 | | |
567 | | /*! |
568 | | * \brief ptraCompactArray() |
569 | | * |
570 | | * \param[in] pa |
571 | | * \return 0 if OK, 1 on error |
572 | | * |
573 | | * <pre> |
574 | | * Notes: |
575 | | * (1) This compacts the items on the array, filling any empty ptrs. |
576 | | * (2) This does not change the size of the array of ptrs. |
577 | | * </pre> |
578 | | */ |
579 | | l_ok |
580 | | ptraCompactArray(L_PTRA *pa) |
581 | 0 | { |
582 | 0 | l_int32 i, imax, nactual, index; |
583 | |
|
584 | 0 | if (!pa) |
585 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
586 | 0 | ptraGetMaxIndex(pa, &imax); |
587 | 0 | ptraGetActualCount(pa, &nactual); |
588 | 0 | if (imax + 1 == nactual) return 0; |
589 | | |
590 | | /* Compact the array */ |
591 | 0 | for (i = 0, index = 0; i <= imax; i++) { |
592 | 0 | if (pa->array[i]) |
593 | 0 | pa->array[index++] = pa->array[i]; |
594 | 0 | } |
595 | 0 | pa->imax = index - 1; |
596 | 0 | if (nactual != index) |
597 | 0 | L_ERROR("index = %d; != nactual\n", __func__, index); |
598 | |
|
599 | 0 | return 0; |
600 | 0 | } |
601 | | |
602 | | |
603 | | /*----------------------------------------------------------------------* |
604 | | * Other array operations * |
605 | | *----------------------------------------------------------------------*/ |
606 | | /*! |
607 | | * \brief ptraReverse() |
608 | | * |
609 | | * \param[in] pa ptra |
610 | | * \return 0 if OK, 1 on error |
611 | | */ |
612 | | l_ok |
613 | | ptraReverse(L_PTRA *pa) |
614 | 0 | { |
615 | 0 | l_int32 i, imax; |
616 | |
|
617 | 0 | if (!pa) |
618 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
619 | 0 | ptraGetMaxIndex(pa, &imax); |
620 | |
|
621 | 0 | for (i = 0; i < (imax + 1) / 2; i++) |
622 | 0 | ptraSwap(pa, i, imax - i); |
623 | 0 | return 0; |
624 | 0 | } |
625 | | |
626 | | |
627 | | /*! |
628 | | * \brief ptraJoin() |
629 | | * |
630 | | * \param[in] pa1 add to this one |
631 | | * \param[in] pa2 appended to pa1, and emptied of items; can be null |
632 | | * \return 0 if OK, 1 on error |
633 | | */ |
634 | | l_ok |
635 | | ptraJoin(L_PTRA *pa1, |
636 | | L_PTRA *pa2) |
637 | 0 | { |
638 | 0 | l_int32 i, imax; |
639 | 0 | void *item; |
640 | |
|
641 | 0 | if (!pa1) |
642 | 0 | return ERROR_INT("pa1 not defined", __func__, 1); |
643 | 0 | if (!pa2) |
644 | 0 | return 0; |
645 | | |
646 | 0 | ptraGetMaxIndex(pa2, &imax); |
647 | 0 | for (i = 0; i <= imax; i++) { |
648 | 0 | item = ptraRemove(pa2, i, L_NO_COMPACTION); |
649 | 0 | ptraAdd(pa1, item); |
650 | 0 | } |
651 | |
|
652 | 0 | return 0; |
653 | 0 | } |
654 | | |
655 | | |
656 | | |
657 | | /*----------------------------------------------------------------------* |
658 | | * Simple ptra accessors * |
659 | | *----------------------------------------------------------------------*/ |
660 | | /*! |
661 | | * \brief ptraGetMaxIndex() |
662 | | * |
663 | | * \param[in] pa ptra |
664 | | * \param[out] pmaxindex index of last item in the array; |
665 | | * \return 0 if OK; 1 on error |
666 | | * |
667 | | * <pre> |
668 | | * Notes: |
669 | | * (1) The largest index to an item in the array is %maxindex. |
670 | | * %maxindex is one less than the number of items that would be |
671 | | * in the array if there were no null pointers between 0 |
672 | | * and %maxindex - 1. However, because the internal ptr array |
673 | | * need not be compacted, there may be NULL pointers at |
674 | | * indices below %maxindex; for example, if items have |
675 | | * been removed. |
676 | | * (2) When an item is added to the end of the array, it goes |
677 | | * into pa->array[maxindex + 1], and maxindex is then |
678 | | * incremented by 1. |
679 | | * (3) If there are no items in the array, this returns %maxindex = -1. |
680 | | * </pre> |
681 | | */ |
682 | | l_ok |
683 | | ptraGetMaxIndex(L_PTRA *pa, |
684 | | l_int32 *pmaxindex) |
685 | 0 | { |
686 | 0 | if (!pa) |
687 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
688 | 0 | if (!pmaxindex) |
689 | 0 | return ERROR_INT("&maxindex not defined", __func__, 1); |
690 | 0 | *pmaxindex = pa->imax; |
691 | 0 | return 0; |
692 | 0 | } |
693 | | |
694 | | |
695 | | /*! |
696 | | * \brief ptraGetActualCount() |
697 | | * |
698 | | * \param[in] pa ptra |
699 | | * \param[out] pcount actual number of items on the ptr array |
700 | | * \return 0 if OK; 1 on error |
701 | | * |
702 | | * <pre> |
703 | | * Notes: |
704 | | * (1) The actual number of items on the ptr array, pa->nactual, |
705 | | * will be smaller than pa->n if the array is not compacted. |
706 | | * </pre> |
707 | | */ |
708 | | l_ok |
709 | | ptraGetActualCount(L_PTRA *pa, |
710 | | l_int32 *pcount) |
711 | 0 | { |
712 | 0 | if (!pa) |
713 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
714 | 0 | if (!pcount) |
715 | 0 | return ERROR_INT("&count not defined", __func__, 1); |
716 | 0 | *pcount = pa->nactual; |
717 | |
|
718 | 0 | return 0; |
719 | 0 | } |
720 | | |
721 | | |
722 | | /*! |
723 | | * \brief ptraGetPtrToItem() |
724 | | * |
725 | | * \param[in] pa ptra |
726 | | * \param[in] index of element to be retrieved |
727 | | * \return a ptr to the element, or NULL on error |
728 | | * |
729 | | * <pre> |
730 | | * Notes: |
731 | | * (1) This returns a ptr to the item. You must cast it to |
732 | | * the type of item. Do not destroy it; the item belongs |
733 | | * to the Ptra. |
734 | | * (2) This can access all possible items on the ptr array. |
735 | | * If an item doesn't exist, it returns null. |
736 | | * </pre> |
737 | | */ |
738 | | void * |
739 | | ptraGetPtrToItem(L_PTRA *pa, |
740 | | l_int32 index) |
741 | 0 | { |
742 | 0 | if (!pa) |
743 | 0 | return (void *)ERROR_PTR("pa not defined", __func__, NULL); |
744 | 0 | if (index < 0 || index >= pa->nalloc) |
745 | 0 | return (void *)ERROR_PTR("index not in [0 ... nalloc-1]", |
746 | 0 | __func__, NULL); |
747 | | |
748 | 0 | return pa->array[index]; |
749 | 0 | } |
750 | | |
751 | | |
752 | | /*--------------------------------------------------------------------------* |
753 | | * Ptraa creation and destruction * |
754 | | *--------------------------------------------------------------------------*/ |
755 | | /*! |
756 | | * \brief ptraaCreate() |
757 | | * |
758 | | * \param[in] n size of ptr array to be alloc'd |
759 | | * \return paa, or NULL on error |
760 | | * |
761 | | * <pre> |
762 | | * Notes: |
763 | | * (1) The ptraa is generated with a fixed size, that can not change. |
764 | | * The ptra can be generated and inserted randomly into this array. |
765 | | * </pre> |
766 | | */ |
767 | | L_PTRAA * |
768 | | ptraaCreate(l_int32 n) |
769 | 0 | { |
770 | 0 | L_PTRAA *paa; |
771 | |
|
772 | 0 | if (n <= 0) |
773 | 0 | return (L_PTRAA *)ERROR_PTR("n must be > 0", __func__, NULL); |
774 | | |
775 | 0 | paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA)); |
776 | 0 | if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) { |
777 | 0 | ptraaDestroy(&paa, 0, 0); |
778 | 0 | return (L_PTRAA *)ERROR_PTR("ptr array not made", __func__, NULL); |
779 | 0 | } |
780 | 0 | paa->nalloc = n; |
781 | 0 | return paa; |
782 | 0 | } |
783 | | |
784 | | |
785 | | /*! |
786 | | * \brief ptraaDestroy() |
787 | | * |
788 | | * \param[in,out] ppaa will be set to null before returning |
789 | | * \param[in] freeflag TRUE to free each remaining item in each ptra |
790 | | * \param[in] warnflag TRUE to warn if any remaining items |
791 | | * are not destroyed |
792 | | * \return void |
793 | | * |
794 | | * <pre> |
795 | | * Notes: |
796 | | * (1) See ptraDestroy() for use of %freeflag and %warnflag. |
797 | | * (2) To destroy the ptraa, we destroy each ptra, then the ptr array, |
798 | | * then the ptraa, and then null the contents of the input ptr. |
799 | | * </pre> |
800 | | */ |
801 | | void |
802 | | ptraaDestroy(L_PTRAA **ppaa, |
803 | | l_int32 freeflag, |
804 | | l_int32 warnflag) |
805 | 0 | { |
806 | 0 | l_int32 i, n; |
807 | 0 | L_PTRA *pa; |
808 | 0 | L_PTRAA *paa; |
809 | |
|
810 | 0 | if (ppaa == NULL) { |
811 | 0 | L_WARNING("ptr address is NULL\n", __func__); |
812 | 0 | return; |
813 | 0 | } |
814 | 0 | if ((paa = *ppaa) == NULL) |
815 | 0 | return; |
816 | | |
817 | 0 | ptraaGetSize(paa, &n); |
818 | 0 | for (i = 0; i < n; i++) { |
819 | 0 | pa = ptraaGetPtra(paa, i, L_REMOVE); |
820 | 0 | ptraDestroy(&pa, freeflag, warnflag); |
821 | 0 | } |
822 | |
|
823 | 0 | LEPT_FREE(paa->ptra); |
824 | 0 | LEPT_FREE(paa); |
825 | 0 | *ppaa = NULL; |
826 | 0 | } |
827 | | |
828 | | |
829 | | /*--------------------------------------------------------------------------* |
830 | | * Ptraa accessors * |
831 | | *--------------------------------------------------------------------------*/ |
832 | | /*! |
833 | | * \brief ptraaGetSize() |
834 | | * |
835 | | * \param[in] paa |
836 | | * \param[out] psize size of ptr array |
837 | | * \return 0 if OK; 1 on error |
838 | | */ |
839 | | l_ok |
840 | | ptraaGetSize(L_PTRAA *paa, |
841 | | l_int32 *psize) |
842 | 0 | { |
843 | 0 | if (!paa) |
844 | 0 | return ERROR_INT("paa not defined", __func__, 1); |
845 | 0 | if (!psize) |
846 | 0 | return ERROR_INT("&size not defined", __func__, 1); |
847 | 0 | *psize = paa->nalloc; |
848 | |
|
849 | 0 | return 0; |
850 | 0 | } |
851 | | |
852 | | |
853 | | /*! |
854 | | * \brief ptraaInsertPtra() |
855 | | * |
856 | | * \param[in] paa ptraa |
857 | | * \param[in] index location in array for insertion |
858 | | * \param[in] pa to be inserted |
859 | | * \return 0 if OK; 1 on error |
860 | | * |
861 | | * <pre> |
862 | | * Notes: |
863 | | * (1) Caller should check return value. On success, the Ptra |
864 | | * is inserted in the Ptraa and is owned by it. However, |
865 | | * on error, the Ptra remains owned by the caller. |
866 | | * </pre> |
867 | | */ |
868 | | l_ok |
869 | | ptraaInsertPtra(L_PTRAA *paa, |
870 | | l_int32 index, |
871 | | L_PTRA *pa) |
872 | 0 | { |
873 | 0 | l_int32 n; |
874 | |
|
875 | 0 | if (!paa) |
876 | 0 | return ERROR_INT("paa not defined", __func__, 1); |
877 | 0 | if (!pa) |
878 | 0 | return ERROR_INT("pa not defined", __func__, 1); |
879 | 0 | ptraaGetSize(paa, &n); |
880 | 0 | if (index < 0 || index >= n) |
881 | 0 | return ERROR_INT("invalid index", __func__, 1); |
882 | 0 | if (paa->ptra[index] != NULL) |
883 | 0 | return ERROR_INT("ptra already stored at index", __func__, 1); |
884 | | |
885 | 0 | paa->ptra[index] = pa; |
886 | 0 | return 0; |
887 | 0 | } |
888 | | |
889 | | |
890 | | /*! |
891 | | * \brief ptraaGetPtra() |
892 | | * |
893 | | * \param[in] paa ptraa |
894 | | * \param[in] index location in array |
895 | | * \param[in] accessflag L_HANDLE_ONLY, L_REMOVE |
896 | | * \return ptra at index location, or NULL on error or if there |
897 | | * is no ptra there. |
898 | | * |
899 | | * <pre> |
900 | | * Notes: |
901 | | * (1) This returns the ptra ptr. If %accessflag == L_HANDLE_ONLY, |
902 | | * the ptra is left on the ptraa. If %accessflag == L_REMOVE, |
903 | | * the ptr in the ptraa is set to NULL, and the caller |
904 | | * is responsible for disposing of the ptra (either putting it |
905 | | * back on the ptraa, or destroying it). |
906 | | * (2) This returns NULL if there is no Ptra at the index location. |
907 | | * </pre> |
908 | | */ |
909 | | L_PTRA * |
910 | | ptraaGetPtra(L_PTRAA *paa, |
911 | | l_int32 index, |
912 | | l_int32 accessflag) |
913 | 0 | { |
914 | 0 | l_int32 n; |
915 | 0 | L_PTRA *pa; |
916 | |
|
917 | 0 | if (!paa) |
918 | 0 | return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL); |
919 | 0 | ptraaGetSize(paa, &n); |
920 | 0 | if (index < 0 || index >= n) |
921 | 0 | return (L_PTRA *)ERROR_PTR("invalid index", __func__, NULL); |
922 | 0 | if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE) |
923 | 0 | return (L_PTRA *)ERROR_PTR("invalid accessflag", __func__, NULL); |
924 | | |
925 | 0 | pa = paa->ptra[index]; |
926 | 0 | if (accessflag == L_REMOVE) |
927 | 0 | paa->ptra[index] = NULL; |
928 | 0 | return pa; |
929 | 0 | } |
930 | | |
931 | | |
932 | | /*--------------------------------------------------------------------------* |
933 | | * Ptraa conversion * |
934 | | *--------------------------------------------------------------------------*/ |
935 | | /*! |
936 | | * \brief ptraaFlattenToPtra() |
937 | | * |
938 | | * \param[in] paa ptraa |
939 | | * \return ptra, or NULL on error |
940 | | * |
941 | | * <pre> |
942 | | * Notes: |
943 | | * (1) This 'flattens' the ptraa to a ptra, taking the items in |
944 | | * each ptra, in order, starting with the first ptra, etc. |
945 | | * (2) As a side-effect, the ptra are all removed from the ptraa |
946 | | * and destroyed, leaving an empty ptraa. |
947 | | * </pre> |
948 | | */ |
949 | | L_PTRA * |
950 | | ptraaFlattenToPtra(L_PTRAA *paa) |
951 | 0 | { |
952 | 0 | l_int32 i, n; |
953 | 0 | L_PTRA *pat, *pad; |
954 | |
|
955 | 0 | if (!paa) |
956 | 0 | return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL); |
957 | | |
958 | 0 | pad = ptraCreate(0); |
959 | 0 | ptraaGetSize(paa, &n); |
960 | 0 | for (i = 0; i < n; i++) { |
961 | 0 | pat = ptraaGetPtra(paa, i, L_REMOVE); |
962 | 0 | if (!pat) continue; |
963 | 0 | ptraJoin(pad, pat); |
964 | 0 | ptraDestroy(&pat, FALSE, FALSE); /* they're all empty */ |
965 | 0 | } |
966 | |
|
967 | 0 | return pad; |
968 | 0 | } |