Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/rbtree.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 /*====================================================================*
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 * Modified from the excellent code here:
29 * http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
30 * which has been placed in the public domain under the Creative Commons
31 * CC0 1.0 waiver (http://creativecommons.org/publicdomain/zero/1.0/).
32 *
33 * When the key is generated from a hash (e.g., string --> uint64),
34 * there is always the possibility of having collisions, but to make
35 * the collision probability very low requires using a large hash.
36 * For that reason, the key types are 64 bit quantities, which will result
37 * in a negligible probabililty of collisions for millions of hashed values.
38 * Using 8 byte keys instead of 4 byte keys requires a little more
39 * storage, but the simplification in being able to ignore collisions
40 * with the red-black trees for most applications is worth it.
41 */
42
43 #ifndef LEPTONICA_RBTREE_H
44 #define LEPTONICA_RBTREE_H
45
46 /*! The three valid key types for red-black trees, maps and sets. */
47 /*! RBTree Key Type */
48 enum {
49 L_INT_TYPE = 1,
50 L_UINT_TYPE = 2,
51 L_FLOAT_TYPE = 3
52 };
53
54 /*!
55 * Storage for keys and values for red-black trees, maps and sets.
56 * <pre>
57 * Note:
58 * (1) Keys and values of the valid key types are all 64-bit
59 * (2) (void *) can be used for values but not for keys.
60 * </pre>
61 */
62 union Rb_Type {
63 l_int64 itype;
64 l_uint64 utype;
65 l_float64 ftype;
66 void *ptype;
67 };
68 typedef union Rb_Type RB_TYPE;
69
70 struct L_Rbtree {
71 struct L_Rbtree_Node *root;
72 l_int32 keytype;
73 };
74 typedef struct L_Rbtree L_RBTREE;
75 typedef struct L_Rbtree L_AMAP; /* hide underlying implementation for map */
76 typedef struct L_Rbtree L_ASET; /* hide underlying implementation for set */
77
78 struct L_Rbtree_Node {
79 union Rb_Type key;
80 union Rb_Type value;
81 struct L_Rbtree_Node *left;
82 struct L_Rbtree_Node *right;
83 struct L_Rbtree_Node *parent;
84 l_int32 color;
85 };
86 typedef struct L_Rbtree_Node L_RBTREE_NODE;
87 typedef struct L_Rbtree_Node L_AMAP_NODE; /* hide tree implementation */
88 typedef struct L_Rbtree_Node L_ASET_NODE; /* hide tree implementation */
89
90
91 #endif /* LEPTONICA_RBTREE_H */