Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/include/mupdf/fitz/heap-imp.h @ 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 // Copyright (C) 2004-2025 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 /* This file has preprocessor magic in it to instantiate both
24 * prototypes and implementations for heap sorting structures
25 * of various different types. Effectively, it's templating for
26 * C.
27 *
28 * If you are including this file directly without intending to
29 * be instantiating a new set of heap sort functions, you are
30 * doing the wrong thing.
31 */
32
33 #ifndef MUPDF_FITZ_HEAP_I_KNOW_WHAT_IM_DOING
34 #error Do not include heap-imp.h unless you know what you are doing
35 #endif
36
37 #define HEAP_XCAT(A,B) A##B
38 #define HEAP_CAT(A,B) HEAP_XCAT(A,B)
39
40 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
41 typedef struct
42 {
43 int max;
44 int len;
45 HEAP_CONTAINER_TYPE *heap;
46 } HEAP_TYPE_NAME;
47 #endif
48
49 void HEAP_CAT(HEAP_TYPE_NAME,_insert)(fz_context *ctx, HEAP_TYPE_NAME *heap, HEAP_CONTAINER_TYPE v
50 #ifndef HEAP_CMP
51 , int (*HEAP_CMP)(HEAP_CONTAINER_TYPE *a, HEAP_CONTAINER_TYPE *b)
52 #endif
53 )
54 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
55 ;
56 #else
57 {
58 int i;
59 HEAP_CONTAINER_TYPE *h;
60
61 if (heap->max == heap->len)
62 {
63 int m = heap->max * 2;
64
65 if (m == 0)
66 m = 32;
67
68 heap->heap = (HEAP_CONTAINER_TYPE *)fz_realloc(ctx, heap->heap, sizeof(*heap->heap) * m);
69 heap->max = m;
70 }
71 h = heap->heap;
72
73 /* Insert it into the heap. Consider inserting at position i, and
74 * then 'heapify' back. We can delay the actual insertion to the
75 * end of the process. */
76 i = heap->len++;
77 while (i != 0)
78 {
79 int parent_idx = (i-1)/2;
80 HEAP_CONTAINER_TYPE *parent_val = &h[parent_idx];
81 if (HEAP_CMP(parent_val, &v) > 0)
82 break;
83 h[i] = h[parent_idx];
84 i = parent_idx;
85 }
86 h[i] = v;
87 }
88 #endif
89
90 void HEAP_CAT(HEAP_TYPE_NAME,_sort)(fz_context *ctx, HEAP_TYPE_NAME *heap
91 #ifndef HEAP_CMP
92 , int (*HEAP_CMP)(HEAP_CONTAINER_TYPE *a, HEAP_CONTAINER_TYPE *b)
93 #endif
94 )
95 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
96 ;
97 #else
98 {
99 int j;
100 HEAP_CONTAINER_TYPE *h = heap->heap;
101
102 /* elements j to len are always sorted. 0 to j are always a valid heap. Gradually move j to 0. */
103 for (j = heap->len-1; j > 0; j--)
104 {
105 int k;
106 HEAP_CONTAINER_TYPE val;
107
108 /* Swap max element with j. Invariant valid for next value to j. */
109 val = h[j];
110 h[j] = h[0];
111 /* Now reform the heap. 0 to k is a valid heap. */
112 k = 0;
113 while (1)
114 {
115 int kid = k*2+1;
116 if (kid >= j)
117 break;
118 if (kid+1 < j && (HEAP_CMP(&h[kid+1], &h[kid])) > 0)
119 kid++;
120 if ((HEAP_CMP(&val, &h[kid])) > 0)
121 break;
122 h[k] = h[kid];
123 k = kid;
124 }
125 h[k] = val;
126 }
127 }
128 #endif
129
130 void HEAP_CAT(HEAP_TYPE_NAME,_uniq)(fz_context *ctx, HEAP_TYPE_NAME *heap
131 #ifndef HEAP_CMP
132 , int (*HEAP_CMP)(HEAP_CONTAINER_TYPE *a, HEAP_CONTAINER_TYPE *b)
133 #endif
134 )
135 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
136 ;
137 #else
138 {
139 int n = heap->len;
140 int i, j = 0;
141 HEAP_CONTAINER_TYPE *h = heap->heap;
142
143 if (n == 0)
144 return;
145
146 j = 0;
147 for (i = 1; i < n; i++)
148 {
149 if (HEAP_CMP(&h[j], &h[i]) == 0)
150 continue;
151 j++;
152 if (i != j)
153 h[j] = h[i];
154 }
155 heap->len = j+1;
156 }
157 #endif
158
159 #ifdef HEAP_DUMP
160 void HEAP_CAT(HEAP_TYPE_NAME,_dump)(fz_context *ctx, fz_output *out, HEAP_TYPE_NAME *heap)
161 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
162 ;
163 #else
164 {
165 int n = heap->len;
166 int i;
167 HEAP_CONTAINER_TYPE *h = heap->heap;
168
169 fz_write_printf(ctx, out, "Heap %p len %d:\n", heap, n);
170 for (i = 0; i < n; i++)
171 HEAP_DUMP(ctx, out, i, &h[i]);
172 }
173 #endif
174
175 void HEAP_CAT(HEAP_TYPE_NAME,_debug)(fz_context *ctx, HEAP_TYPE_NAME *heap)
176 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
177 ;
178 #else
179 {
180 HEAP_CAT(HEAP_TYPE_NAME,_dump)(ctx, fz_stddbg(ctx), heap);
181 }
182 #endif
183 #endif
184
185 #undef HEAP_CONTAINER_TYPE
186 #undef HEAP_TYPE_NAME
187 #undef HEAP_CMP
188 #undef HEAP_XCAT
189 #undef HEAP_CAT
190 #undef HEAP_DUMP