Leptonica  1.82.0
Image processing and image analysis suite
rbtree.h
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 
48 enum {
49  L_INT_TYPE = 1,
50  L_UINT_TYPE = 2,
51  L_FLOAT_TYPE = 3
52 };
53 
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 */
Definition: rbtree.h:62