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 */
L_Rbtree_Node
Definition:
rbtree.h:78
L_Rbtree
Definition:
rbtree.h:70
Rb_Type
Definition:
rbtree.h:62
src
rbtree.h
Generated by
1.9.1