1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Copyright by the Board of Trustees of the University of Illinois. *
* All rights reserved. *
* *
* This file is part of HDF5. The full HDF5 copyright notice, including *
* terms governing use, modification, and redistribution, is contained in *
* the files COPYING and Copyright.html. COPYING can be found at the root *
* of the source code distribution tree; Copyright.html can be found at the *
* root level of an installed copy of the electronic HDF5 document set and *
* is linked from the top-level documents page. It can also be found at *
* http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have *
* access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*-------------------------------------------------------------------------
*
* Created: H5TBprivate.h
* Apr 22 2000
* Quincey Koziol <koziol@ncsa.uiuc.edu>
*
* Purpose: Private non-prototype header.
*
* Modifications:
*
*-------------------------------------------------------------------------
*/
#ifndef _H5TBprivate_H
#define _H5TBprivate_H
/* Public headers needed by this file */
#ifdef LATER
#include "H5TBpublic.h" /*Public API prototypes */
#endif /* LATER */
/* Typedef for key comparison function */
typedef int (*H5TB_cmp_t)(const void *k1, const void *k2, int cmparg);
/* Shortcut macros for links */
# define PARENT 0
# define LEFT 1
# define RIGHT 2
# define Parent link[PARENT]
# define Lchild link[LEFT]
# define Rchild link[RIGHT]
/* Tree-balancing flags */
# define H5TB_HEAVY(s) s /* If the `s' sub-tree is deeper than the other */
# define H5TB_DOUBLE 4 /* If "heavy" sub-tree is two levels deeper */
# define H5TB_INTERN 8 /* If node is internal (has two children) */
# define H5TB_UNBAL ( H5TB_HEAVY(LEFT) | H5TB_HEAVY(RIGHT) )
# define H5TB_FLAGS ( H5TB_UNBAL | H5TB_INTERN | H5TB_DOUBLE )
# define H5TB_CHILD(s) ( H5TB_INTERN | H5TB_HEAVY(s) )
/* Internal macros */
# define LeftCnt(node) ( (node)->lcnt ) /* Left descendants */
# define RightCnt(node) ( (node)->rcnt ) /* Right descendants */
# define Cnt(node,s) ( LEFT==(s) ? LeftCnt(node) : RightCnt(node) )
# define HasChild(n,s) ( Cnt(n,s)>0 )
# define Heavy(n,s) ( (s) & (LeftCnt(n)>RightCnt(n) ? LEFT : \
LeftCnt(n)==RightCnt(n) ? 0 : RIGHT))
# define HeavyCnt(l,r,s) ( (s) & ((l)>(r) ? LEFT : (l)==(r) ? 0 : RIGHT))
# define Intern(n) ( LeftCnt(n) && RightCnt(n) )
# define UnBal(n) ( LeftCnt(n)>RightCnt(n) ? LEFT : \
LeftCnt(n)==RightCnt(n) ? 0 : RIGHT)
# define UnBalanced(n) ( LeftCnt(n)!=RightCnt(n) )
# define UnBalancedCnt(l,r) ( (l)!=(r) )
# define Double(n) ( H5TB_DOUBLE & (n)->flags )
# define Other(side) ( LEFT + RIGHT - (side) )
# define Weight(n) ( Double(n) ? 2 : UnBalanced(n) )
# define WeightCnt(l,r,d) ( (d) ? 2 : UnBalancedCnt(l,r) )
# define Delta(n,s) ( Heavy(n,s) ? Weight(n) : -Weight(n) )
# define DeltaCnt(l,r,d,s) ( HeavyCnt(l,r,s) ? WeightCnt(l,r,d) : \
-WeightCnt(l,r,d) )
# define SetFlags(n,s,b,i) ( ( -2<(b) && (b)<2 ? 0 : H5TB_DOUBLE ) \
| ( 0>(b) ? H5TB_HEAVY(s) : (b)>0 ? H5TB_HEAVY(Other(s)) : 0 ) \
| ( (i) ? H5TB_INTERN : 0 ) )
/* Internal types for flags & leaf counts */
typedef unsigned long H5TB_flag;
typedef unsigned long H5TB_leaf;
/* Threaded node structure */
typedef struct H5TB_node
{
void * data; /* Pointer to user data to be associated with node */
void * key; /* Field to sort nodes on */
struct H5TB_node *link[3]; /* Pointers to parent, left child, and right child */
H5TB_flag flags; /* Combination of the bit fields */
H5TB_leaf lcnt; /* count of left children */
H5TB_leaf rcnt; /* count of right children */
} H5TB_NODE;
/* Threaded tree structure */
typedef struct H5TB_tree
{
H5TB_NODE *root; /* Pointer to actual root of tbbt tree */
unsigned long count; /* The number of nodes in the tree currently */
unsigned fast_compare; /* use a faster in-line compare (with casts) instead of function call */
H5TB_cmp_t compar; /* Key comparison function */
int cmparg;
} H5TB_TREE;
/* Define the "fast compare" values */
#define H5TB_FAST_HADDR_COMPARE 1
#define H5TB_FAST_INTN_COMPARE 2
#define H5TB_FAST_STR_COMPARE 3
#define H5TB_FAST_HSIZE_COMPARE 4
/* Define an access macro for getting a node's data */
#define H5TB_NODE_DATA(n) ((n)->data)
/* Define some "function-like" macros */
#define H5TB_first(root) H5TB_end(root,LEFT)
#define H5TB_last(root) H5TB_end(root,RIGHT)
#define H5TB_next(node) H5TB_nbr(node,RIGHT)
#define H5TB_prev(node) H5TB_nbr(node,LEFT)
#if defined c_plusplus || defined __cplusplus
extern "C"
{
#endif /* c_plusplus || __cplusplus */
H5_DLL H5TB_TREE *H5TB_dmake (H5TB_cmp_t cmp, int arg, unsigned fast_compare);
H5_DLL H5TB_TREE *H5TB_fast_dmake (unsigned fast_compare);
H5_DLL H5TB_NODE *H5TB_dfind (H5TB_TREE * tree, const void * key, H5TB_NODE ** pp);
H5_DLL H5TB_NODE *H5TB_find(H5TB_NODE * root, const void * key, H5TB_cmp_t cmp,
int arg, H5TB_NODE ** pp);
H5_DLL H5TB_NODE *H5TB_dless (H5TB_TREE * tree, void * key, H5TB_NODE ** pp);
H5_DLL H5TB_NODE *H5TB_less (H5TB_NODE * root, void * key, H5TB_cmp_t cmp,
int arg, H5TB_NODE ** pp);
H5_DLL H5TB_NODE *H5TB_index (H5TB_NODE * root, unsigned indx);
H5_DLL H5TB_NODE *H5TB_dins (H5TB_TREE * tree, void * item, void * key);
H5_DLL H5TB_NODE *H5TB_ins (H5TB_NODE ** root, void * item, void * key, unsigned fast_compare, H5TB_cmp_t cmp, int arg);
H5_DLL void *H5TB_rem(H5TB_NODE ** root, H5TB_NODE * node, void * *kp);
H5_DLL H5TB_TREE *H5TB_dfree (H5TB_TREE * tree, void(*fd) (void *), void(*fk) (void *));
H5_DLL void *H5TB_free (H5TB_NODE ** root, void(*fd) (void *), void(*fk) (void *));
H5_DLL long H5TB_count (H5TB_TREE * tree);
H5_DLL H5TB_NODE * H5TB_end(H5TB_NODE * root, int side);
H5_DLL H5TB_NODE *H5TB_nbr(H5TB_NODE * ptr, int side);
#ifdef H5TB_DEBUG
H5_DLL herr_t H5TB_dump(H5TB_TREE *ptree, void (*key_dump)(void *,void *), int method);
#endif /* H5TB_DEBUG */
#if defined c_plusplus || defined __cplusplus
}
#endif /* c_plusplus || __cplusplus */
#endif /* _H5TBprivate_H */
|
