Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/tree.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 // Copyright (C) 2004-2021 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 #include "mupdf/fitz.h"
24
25 #include <string.h>
26
27 /* AA-tree */
28
29 struct fz_tree
30 {
31 char *key;
32 void *value;
33 fz_tree *left, *right;
34 int level;
35 };
36
37 static fz_tree tree_sentinel = { "", NULL, &tree_sentinel, &tree_sentinel, 0 };
38
39 static fz_tree *fz_tree_new_node(fz_context *ctx, const char *key, void *value)
40 {
41 fz_tree *node = fz_malloc_struct(ctx, fz_tree);
42 fz_try(ctx)
43 {
44 node->key = fz_strdup(ctx, key);
45 node->value = value;
46 node->left = node->right = &tree_sentinel;
47 node->level = 1;
48 }
49 fz_catch(ctx)
50 {
51 fz_free(ctx, node);
52 fz_rethrow(ctx);
53 }
54 return node;
55 }
56
57 void *fz_tree_lookup(fz_context *ctx, fz_tree *node, const char *key)
58 {
59 if (node)
60 {
61 while (node != &tree_sentinel)
62 {
63 int c = strcmp(key, node->key);
64 if (c == 0)
65 return node->value;
66 else if (c < 0)
67 node = node->left;
68 else
69 node = node->right;
70 }
71 }
72 return NULL;
73 }
74
75 static fz_tree *fz_tree_skew(fz_tree *node)
76 {
77 if (node->level != 0)
78 {
79 if (node->left->level == node->level)
80 {
81 fz_tree *save = node;
82 node = node->left;
83 save->left = node->right;
84 node->right = save;
85 }
86 node->right = fz_tree_skew(node->right);
87 }
88 return node;
89 }
90
91 static fz_tree *fz_tree_split(fz_tree *node)
92 {
93 if (node->level != 0 && node->right->right->level == node->level)
94 {
95 fz_tree *save = node;
96 node = node->right;
97 save->right = node->left;
98 node->left = save;
99 node->level++;
100 node->right = fz_tree_split(node->right);
101 }
102 return node;
103 }
104
105 fz_tree *fz_tree_insert(fz_context *ctx, fz_tree *node, const char *key, void *value)
106 {
107 if (node && node != &tree_sentinel)
108 {
109 int c = strcmp(key, node->key);
110 if (c < 0)
111 node->left = fz_tree_insert(ctx, node->left, key, value);
112 else
113 node->right = fz_tree_insert(ctx, node->right, key, value);
114 node = fz_tree_skew(node);
115 node = fz_tree_split(node);
116 return node;
117 }
118 else
119 {
120 return fz_tree_new_node(ctx, key, value);
121 }
122 }
123
124 void fz_drop_tree(fz_context *ctx, fz_tree *node, void (*dropfunc)(fz_context *ctx, void *value))
125 {
126 if (node)
127 {
128 if (node->left != &tree_sentinel)
129 fz_drop_tree(ctx, node->left, dropfunc);
130 if (node->right != &tree_sentinel)
131 fz_drop_tree(ctx, node->right, dropfunc);
132 fz_free(ctx, node->key);
133 if (dropfunc)
134 dropfunc(ctx, node->value);
135 fz_free(ctx, node);
136 }
137 }