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
|
/*-------------------------------------------------------------------------
* Copyright (C) 2000-2001 National Center for Supercomputing Applications
* All rights reserved.
*
*-------------------------------------------------------------------------
*
* 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)(void *k1, 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 Intern(n) ( LeftCnt(n) && RightCnt(n) )
# define UnBal(n) ( LeftCnt(n)>RightCnt(n) ? LEFT : \
LeftCnt(n)==RightCnt(n) ? 0 : RIGHT)
# define Double(n) ( H5TB_DOUBLE & (n)->flags )
# define Other(side) ( LEFT + RIGHT - (side) )
# define Delta(n,s) ( ( Heavy(n,s) ? 1 : -1 ) \
* ( Double(n) ? 2 : UnBal(n) ? 1 : 0 ) )
# 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
#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_NODE *H5TB_dfind (H5TB_TREE * tree, void * key, H5TB_NODE ** pp);
H5_DLL H5TB_NODE *H5TB_find(H5TB_NODE * root, 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, H5TB_cmp_t cmp, int arg);
H5_DLL void *H5TB_rem(H5TB_NODE ** root, H5TB_NODE * node, void * *kp);
H5_DLL H5TB_NODE *H5TB_first (H5TB_NODE * root);
H5_DLL H5TB_NODE *H5TB_last (H5TB_NODE * root);
H5_DLL H5TB_NODE *H5TB_next (H5TB_NODE * node);
H5_DLL H5TB_NODE *H5TB_prev (H5TB_NODE * node);
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);
#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 */
|
