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
|
/* struct::tree - critcl - layer 1 declarations
* (a) Data structures.
*/
#ifndef _DS_H
#define _DS_H 1
#include "tclpre9compat.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 */
Tcl_Size nchildren; /* # nodes used in previous array */
Tcl_Size 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
*/
Tcl_Size index; /* Index of node in 'child' array of its
* parent */
Tcl_Size depth; /* Distance to root node.
* 0 <=> root */
Tcl_Size height; /* Distance to deepest child.
* 0 <=> Leaf. */
Tcl_Size 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:
*/
|