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
|
/* struct::tree - critcl - layer 1 declarations
* (a) Data structures.
*/
#ifndef _DS_H
#define _DS_H 1
#include "tcl.h"
/* Forward declarations of references to trees & nodes.
*/
typedef struct T* TPtr;
typedef struct TN* TNPtr;
/* Node structure.
*/
typedef struct TN {
/* Node identity / handle */
/* Internal rep should be of type */
/* 'tcllib::struct::tree/critcl::node'. */
/* See below. */
Tcl_Obj* name;
Tcl_HashEntry* he;
/* Basic linkage of node to its tree */
TPtr tree; /* Tree the node belongs to */
TNPtr nextleaf; /* Double linked list of all */
TNPtr prevleaf; /* leaf nodes */
TNPtr nextnode; /* Double linked list of all */
TNPtr prevnode; /* nodes */
/* Node navigation. Parent/Children/Siblings */
TNPtr parent; /* Parent node */
TNPtr* child; /* Array of children. Can
* be NULL. leaf node implies
* NULL, and vice versa */
int nchildren; /* # nodes used in previous array */
int maxchildren; /* Size of previous array */
TNPtr left; /* Sibling to the left, NULL if no such */
TNPtr right; /* Sibling to the right, NULL if no such */
/* Node attributes */
Tcl_HashTable* attr; /* Node attributes. NULL if the
* node has none */
/* Cache for properties of the node based on the tree
* structure
*/
int index; /* Index of node in 'child' array of its
* parent */
int depth; /* Distance to root node.
* 0 <=> root */
int height; /* Distance to deepest child.
* 0 <=> Leaf. */
int desc; /* #Descendants */
} TN;
/* Tree structure
*/
typedef struct T {
Tcl_Command cmd; /* Token of the object command for
* the tree */
Tcl_HashTable node; /* Mapping
* Node names -> Node structure */
int counter; /* Counter used by the generator
* of node names */
TN* root; /* Root node of the tree. */
TN* leaves; /* List of all leaf nodes */
int nleaves; /* List length */
TN* nodes; /* List of all nodes */
int nnodes; /* List length */
int structure; /* Boolean flag. Set to true if the
* depth/height/desc information
* in the nodes is valid. Reset to
* false by all operations changing
* the structure of the tree. */
/* Generation of node handles. Tree local storage, makes code thread
* oblivious.
*/
char handle [50];
} T;
#endif /* _DS_H */
/*
* Local Variables:
* mode: c
* c-basic-offset: 4
* fill-column: 78
* End:
*/
|
