Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/include/mupdf/fitz/heap.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 /* This header file declares some useful heap functions. (Heap
34 * as in heap sort, not as in memory heap). It uses some
35 * clever (read "hacky") multiple inclusion techniques to allow
36 * us to generate multiple different versions of this code.
37 * This is kinda like 'templating' in C++, but without language
38 * support.
39 */
40
41 /* For every instance of this code, we end up a heap structure:
42 *
43 * typedef struct
44 * {
45 * int max;
46 * int len;
47 * <TYPE> *heap;
48 * } fz_<TYPE>_heap;
49 *
50 * This can be created and initialised on the stack in user code using:
51 *
52 * fz_<TYPE>_heap heap = { 0 };
53 *
54 * and some functions.
55 *
56 * When <TYPE> is a simple int (or float or similar), the ordering required is
57 * obvious, and so the functions are simple (Form 1):
58 *
59 * First some to insert elements into the heap:
60 *
61 * void fz_<TYPE>_heap_insert(fz_context *ctx, fz_<TYPE>_heap *heap, <TYPE> v);
62 *
63 * Once all the elements have been inserted, the heap can be sorted:
64 *
65 * void fz_<TYPE>_heap_sort(fz_context *ctx, fz_<TYPE>_heap *heap);
66 *
67 * Once sorted, repeated elements can be removed:
68 *
69 * void fz_<TYPE>_heap_uniq(fz_context *ctx, fz_<TYPE>_heap *heap);
70 *
71 *
72 * For more complex TYPEs (such as pointers) the ordering may not be implicit within the <TYPE>,
73 * but rather depends upon the data found by dereferencing those pointers. For such types,
74 * the functions are modified with a <COMPARE> function, of the form used by qsort etc:
75 *
76 * int <COMPARE>(<TYPE>x, <TYPE>y) that returns 0 for x == y, +ve for x > y, and -ve for x < y.
77 *
78 * The functions are modified thus (Form 2):
79 *
80 * void fz_<TYPE>_heap_insert(fz_context *ctx, fz_<TYPE>_heap *heap, <TYPE> v, <COMPARE> t);
81 * void fz_<TYPE>_heap_sort(fz_context *ctx, fz_<TYPE>_heap *heap, <COMPARE> t);
82 * void fz_<TYPE>_heap_uniq(fz_context *ctx, fz_<TYPE>_heap *heap, <COMPARE> t);
83 *
84 * Currently, we define:
85 *
86 * fz_int_heap Operates on 'int' values. Form 1.
87 * fz_ptr_heap Operates on 'void *' values. Form 2.
88 * fz_int2_heap Operates on 'typedef struct { int a; int b} fz_int2' values,
89 * with the sort/uniq being done based on 'a' alone. Form 1.
90 * fz_intptr_heap Operates on 'typedef struct { int a; void *b} fz_intptr' values,
91 * with the sort/uniq being done based on 'a' alone. Form 1.
92 */
93
94 /* Everything after this point is preprocessor magic. Ignore it, and just read the above
95 * unless you are wanting to instantiate a new set of functions. */
96
97 #ifndef MUPDF_FITZ_HEAP_H
98
99 #define MUPDF_FITZ_HEAP_H
100
101 #define MUPDF_FITZ_HEAP_I_KNOW_WHAT_IM_DOING
102
103 /* Instantiate fz_int_heap */
104 #define HEAP_TYPE_NAME fz_int_heap
105 #define HEAP_CONTAINER_TYPE int
106 #define HEAP_CMP(a,b) ((*a) - (*b))
107 #define HEAP_DUMP(CTX, OUT, I, A) fz_write_printf(CTX, OUT, "%d: %d\n", I, *A)
108 #include "mupdf/fitz/heap-imp.h"
109
110 /* Instantiate fz_ptr_heap */
111 #define HEAP_TYPE_NAME fz_ptr_heap
112 #define HEAP_CONTAINER_TYPE void *
113 #include "mupdf/fitz/heap-imp.h"
114
115 /* Instantiate fz_int2_heap */
116 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
117 typedef struct
118 {
119 int a;
120 int b;
121 } fz_int2;
122 #endif
123 #define HEAP_TYPE_NAME fz_int2_heap
124 #define HEAP_CMP(A,B) (((A)->a) - ((B)->a))
125 #define HEAP_CONTAINER_TYPE fz_int2
126 #define HEAP_DUMP(CTX, OUT, I, A) fz_write_printf(CTX, OUT, "%d: %d %d\n", I, (A)->a, (A)->b)
127 #include "mupdf/fitz/heap-imp.h"
128
129 /* Instantiate fz_intptr_heap */
130 #ifndef MUPDF_FITZ_HEAP_IMPLEMENT
131 typedef struct
132 {
133 int a;
134 void *b;
135 } fz_intptr;
136 #endif
137 #define HEAP_TYPE_NAME fz_intptr_heap
138 #define HEAP_CONTAINER_TYPE fz_intptr
139 #define HEAP_CMP(A,B) (((A)->a) - ((B)->a))
140 #define HEAP_DUMP(CTX, OUT, I, A) fz_write_printf(CTX, OUT, "%d: %d %p\n", I, (A)->a, (A)->b)
141 #include "mupdf/fitz/heap-imp.h"
142
143 #endif /* MUPDF_FITZ_HEAP_H */