Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/map.c @ 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 - 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 map.c
29 * <pre>
30 *
31 * This is an interface for map and set functions, based on using
32 * red-black binary search trees. Because these trees are sorted,
33 * they are O(nlogn) to build. They allow logn insertion, find
34 * and deletion of elements.
35 *
36 * Both the map and set are ordered by key value, with unique keys.
37 * For the map, the elements are key/value pairs.
38 * For the set we only store unique, ordered keys, and the value
39 * (set to 0 in the implementation) is ignored.
40 *
41 * The keys for the map and set can be any of the three types in the
42 * l_rbtree_keytype enum. The values stored can be any of the four
43 * types in the rb_type union.
44 *
45 * In-order forward and reverse iterators are provided for maps and sets.
46 * To forward iterate over the map for any type of key (in this example,
47 * uint32), extracting integer values:
48 *
49 * L_AMAP *m = l_amapCreate(L_UINT_TYPE);
50 * [add elements to the map ...]
51 * L_AMAP_NODE *n = l_amapGetFirst(m);
52 * while (n) {
53 * l_int32 val = n->value.itype;
54 * // do something ...
55 * n = l_amapGetNext(n);
56 * }
57 *
58 * If the nodes are deleted during the iteration:
59 *
60 * L_AMAP *m = l_amapCreate(L_UINT_TYPE);
61 * [add elements to the map ...]
62 * L_AMAP_NODE *n = l_amapGetFirst(m);
63 * L_AMAP_NODE *nn;
64 * while (n) {
65 * nn = l_amapGetNext(n);
66 * l_int32 val = n->value.itype;
67 * l_uint32 key = n->key.utype;
68 * // do something ...
69 * l_amapDelete(m, n->key);
70 * n = nn;
71 * }
72 *
73 * See prog/maptest.c and prog/settest.c for more examples of usage.
74 *
75 * Interface to (a) map using a general key and storing general values
76 * L_AMAP *l_amapCreate()
77 * RB_TYPE *l_amapFind()
78 * void l_amapInsert()
79 * void l_amapDelete()
80 * void l_amapDestroy()
81 * L_AMAP_NODE *l_amapGetFirst()
82 * L_AMAP_NODE *l_amapGetNext()
83 * L_AMAP_NODE *l_amapGetLast()
84 * L_AMAP_NODE *l_amapGetPrev()
85 * l_int32 l_amapSize()
86 *
87 * Interface to (a) set using a general key
88 * L_ASET *l_asetCreate()
89 * RB_TYPE *l_asetFind()
90 * void l_asetInsert()
91 * void l_asetDelete()
92 * void l_asetDestroy()
93 * L_ASET_NODE *l_asetGetFirst()
94 * L_ASET_NODE *l_asetGetNext()
95 * L_ASET_NODE *l_asetGetLast()
96 * L_ASET_NODE *l_asetGetPrev()
97 * l_int32 l_asetSize()
98 * </pre>
99 */
100
101 #ifdef HAVE_CONFIG_H
102 #include <config_auto.h>
103 #endif /* HAVE_CONFIG_H */
104
105 #include "allheaders.h"
106
107 /* ------------------------------------------------------------- *
108 * Interface to Map *
109 * ------------------------------------------------------------- */
110 L_AMAP *
111 l_amapCreate(l_int32 keytype)
112 {
113 L_AMAP *m;
114
115 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
116 keytype != L_FLOAT_TYPE)
117 return (L_AMAP *)ERROR_PTR("invalid keytype", __func__, NULL);
118
119 m = (L_AMAP *)LEPT_CALLOC(1, sizeof(L_AMAP));
120 m->keytype = keytype;
121 return m;
122 }
123
124 RB_TYPE *
125 l_amapFind(L_AMAP *m,
126 RB_TYPE key)
127 {
128 return l_rbtreeLookup(m, key);
129 }
130
131 void
132 l_amapInsert(L_AMAP *m,
133 RB_TYPE key,
134 RB_TYPE value)
135 {
136 l_rbtreeInsert(m, key, value);
137 }
138
139 void
140 l_amapDelete(L_AMAP *m,
141 RB_TYPE key)
142 {
143 l_rbtreeDelete(m, key);
144 }
145
146 void
147 l_amapDestroy(L_AMAP **pm)
148 {
149 l_rbtreeDestroy(pm);
150 }
151
152 L_AMAP_NODE *
153 l_amapGetFirst(L_AMAP *m)
154 {
155 return l_rbtreeGetFirst(m);
156 }
157
158 L_AMAP_NODE *
159 l_amapGetNext(L_AMAP_NODE *n)
160 {
161 return l_rbtreeGetNext(n);
162 }
163
164 L_AMAP_NODE *
165 l_amapGetLast(L_AMAP *m)
166 {
167 return l_rbtreeGetLast(m);
168 }
169
170 L_AMAP_NODE *
171 l_amapGetPrev(L_AMAP_NODE *n)
172 {
173 return l_rbtreeGetPrev(n);
174 }
175
176 l_int32
177 l_amapSize(L_AMAP *m)
178 {
179 return l_rbtreeGetCount(m);
180 }
181
182
183 /* ------------------------------------------------------------- *
184 * Interface to Set *
185 * ------------------------------------------------------------- */
186 L_ASET *
187 l_asetCreate(l_int32 keytype)
188 {
189 L_ASET *s;
190
191 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
192 keytype != L_FLOAT_TYPE)
193 return (L_ASET *)ERROR_PTR("invalid keytype", __func__, NULL);
194
195 s = (L_ASET *)LEPT_CALLOC(1, sizeof(L_ASET));
196 s->keytype = keytype;
197 return s;
198 }
199
200 /*
201 * l_asetFind()
202 *
203 * This returns NULL if not found, non-null if it is. In the latter
204 * case, the value stored in the returned pointer has no significance.
205 */
206 RB_TYPE *
207 l_asetFind(L_ASET *s,
208 RB_TYPE key)
209 {
210 return l_rbtreeLookup(s, key);
211 }
212
213 void
214 l_asetInsert(L_ASET *s,
215 RB_TYPE key)
216 {
217 RB_TYPE value;
218
219 value.itype = 0; /* meaningless */
220 l_rbtreeInsert(s, key, value);
221 }
222
223 void
224 l_asetDelete(L_ASET *s,
225 RB_TYPE key)
226 {
227 l_rbtreeDelete(s, key);
228 }
229
230 void
231 l_asetDestroy(L_ASET **ps)
232 {
233 l_rbtreeDestroy(ps);
234 }
235
236 L_ASET_NODE *
237 l_asetGetFirst(L_ASET *s)
238 {
239 return l_rbtreeGetFirst(s);
240 }
241
242 L_ASET_NODE *
243 l_asetGetNext(L_ASET_NODE *n)
244 {
245 return l_rbtreeGetNext(n);
246 }
247
248 L_ASET_NODE *
249 l_asetGetLast(L_ASET *s)
250 {
251 return l_rbtreeGetLast(s);
252 }
253
254 L_ASET_NODE *
255 l_asetGetPrev(L_ASET_NODE *n)
256 {
257 return l_rbtreeGetPrev(n);
258 }
259
260 l_int32
261 l_asetSize(L_ASET *s)
262 {
263 return l_rbtreeGetCount(s);
264 }