1/* struct::tree - critcl - layer 1 declarations
2 * (a) Data structures.
3 */
4
5#ifndef _DS_H
6#define _DS_H 1
7
8#include "tcl.h"
9
10/* Forward declarations of references to trees & nodes.
11 */
12
13typedef struct T*  TPtr;
14typedef struct TN* TNPtr;
15
16/* Node structure.
17 */
18
19typedef struct TN {
20    /* Node identity / handle */
21    /* Internal rep should be of type */
22    /* 'tcllib::struct::tree/critcl::node'. */
23    /* See below. */
24
25    Tcl_Obj*	   name;
26    Tcl_HashEntry* he;
27
28    /* Basic linkage of node to its tree */
29
30    TPtr  tree;	     /* Tree the node belongs to */
31    TNPtr nextleaf;  /* Double linked list of all */
32    TNPtr prevleaf;  /* leaf nodes */
33    TNPtr nextnode;  /* Double linked list of all */
34    TNPtr prevnode;  /* nodes */
35
36    /* Node navigation. Parent/Children/Siblings */
37
38    TNPtr  parent; /* Parent node */
39
40    TNPtr* child;	/* Array of children. Can
41			 * be NULL. leaf node implies
42			 * NULL, and vice versa */
43    int	   nchildren;	/* # nodes used in previous array */
44    int	   maxchildren; /* Size of previous array */
45
46    TNPtr left;	  /* Sibling to the left, NULL if no such  */
47    TNPtr right;  /* Sibling to the right, NULL if no such */
48
49    /* Node attributes */
50
51    Tcl_HashTable* attr; /* Node attributes. NULL if the
52			  * node has none */
53
54    /* Cache for properties of the node based on the tree
55     * structure
56     */
57
58    int index;	/* Index of node in 'child' array of its
59		 * parent */
60    int depth;	/* Distance to root node.
61		 * 0 <=> root */
62    int height; /* Distance to deepest child.
63		 * 0 <=> Leaf. */
64    int desc;	/* #Descendants */
65
66} TN;
67
68/* Tree structure
69 */
70
71typedef struct T {
72    Tcl_Command cmd;	/* Token of the object command for
73			 * the tree */
74
75    Tcl_HashTable node; /* Mapping
76			 * Node names -> Node structure */
77
78    int counter;	/* Counter used by the generator
79			 * of node names */
80
81    TN* root;		/* Root node of the tree. */
82
83    TN* leaves;		/* List of all leaf nodes */
84    int nleaves;	/* List length */
85
86    TN* nodes;		/* List of all nodes */
87    int nnodes;		/* List length */
88
89    int structure;	/* Boolean flag. Set to true if the
90			 * depth/height/desc information
91			 * in the nodes is valid. Reset to
92			 * false by all operations changing
93			 * the structure of the tree. */
94
95    /* Generation of node handles. Tree local storage, makes code thread
96     * oblivious.
97     */
98
99    char handle [50];
100
101} T;
102
103#endif /* _DS_H */
104
105/*
106 * Local Variables:
107 * mode: c
108 * c-basic-offset: 4
109 * fill-column: 78
110 * End:
111 */
112