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