| 1 |
|
|---|
| 2 | /*
|
|---|
| 3 | * bltTree.h --
|
|---|
| 4 | *
|
|---|
| 5 | * Copyright 1998-1999 Lucent Technologies, Inc.
|
|---|
| 6 | *
|
|---|
| 7 | * Permission to use, copy, modify, and distribute this software and
|
|---|
| 8 | * its documentation for any purpose and without fee is hereby
|
|---|
| 9 | * granted, provided that the above copyright notice appear in all
|
|---|
| 10 | * copies and that both that the copyright notice and warranty
|
|---|
| 11 | * disclaimer appear in supporting documentation, and that the names
|
|---|
| 12 | * of Lucent Technologies or any of their entities not be used in
|
|---|
| 13 | * advertising or publicity pertaining to distribution of the software
|
|---|
| 14 | * without specific, written prior permission.
|
|---|
| 15 | *
|
|---|
| 16 | * Lucent Technologies disclaims all warranties with regard to this
|
|---|
| 17 | * software, including all implied warranties of merchantability and
|
|---|
| 18 | * fitness. In no event shall Lucent Technologies be liable for any
|
|---|
| 19 | * special, indirect or consequential damages or any damages
|
|---|
| 20 | * whatsoever resulting from loss of use, data or profits, whether in
|
|---|
| 21 | * an action of contract, negligence or other tortuous action, arising
|
|---|
| 22 | * out of or in connection with the use or performance of this
|
|---|
| 23 | * software.
|
|---|
| 24 | *
|
|---|
| 25 | * The "tree" data object was created by George A. Howlett.
|
|---|
| 26 | */
|
|---|
| 27 |
|
|---|
| 28 | #ifndef _BLT_TREE_H
|
|---|
| 29 | #define _BLT_TREE_H
|
|---|
| 30 |
|
|---|
| 31 | #include <bltChain.h>
|
|---|
| 32 | #include <bltHash.h>
|
|---|
| 33 | #include <bltPool.h>
|
|---|
| 34 |
|
|---|
| 35 | typedef struct Blt_TreeNodeStruct *Blt_TreeNode;
|
|---|
| 36 | typedef struct Blt_TreeObjectStruct *Blt_TreeObject;
|
|---|
| 37 | typedef struct Blt_TreeClientStruct *Blt_Tree;
|
|---|
| 38 | typedef struct Blt_TreeTraceStruct *Blt_TreeTrace;
|
|---|
| 39 | typedef struct Blt_TreeValueStruct *Blt_TreeValue;
|
|---|
| 40 | typedef struct Blt_TreeTagEntryStruct Blt_TreeTagEntry;
|
|---|
| 41 | typedef struct Blt_TreeTagTableStruct Blt_TreeTagTable;
|
|---|
| 42 |
|
|---|
| 43 | typedef char *Blt_TreeKey;
|
|---|
| 44 |
|
|---|
| 45 | #define TREE_PREORDER (1<<0)
|
|---|
| 46 | #define TREE_POSTORDER (1<<1)
|
|---|
| 47 | #define TREE_INORDER (1<<2)
|
|---|
| 48 | #define TREE_BREADTHFIRST (1<<3)
|
|---|
| 49 |
|
|---|
| 50 | #define TREE_TRACE_UNSET (1<<3)
|
|---|
| 51 | #define TREE_TRACE_WRITE (1<<4)
|
|---|
| 52 | #define TREE_TRACE_READ (1<<5)
|
|---|
| 53 | #define TREE_TRACE_CREATE (1<<6)
|
|---|
| 54 | #define TREE_TRACE_ALL \
|
|---|
| 55 | (TREE_TRACE_UNSET | TREE_TRACE_WRITE | TREE_TRACE_READ | TREE_TRACE_CREATE)
|
|---|
| 56 | #define TREE_TRACE_MASK (TREE_TRACE_ALL)
|
|---|
| 57 |
|
|---|
| 58 | #define TREE_TRACE_FOREIGN_ONLY (1<<8)
|
|---|
| 59 | #define TREE_TRACE_ACTIVE (1<<9)
|
|---|
| 60 |
|
|---|
| 61 | #define TREE_NOTIFY_CREATE (1<<0)
|
|---|
| 62 | #define TREE_NOTIFY_DELETE (1<<1)
|
|---|
| 63 | #define TREE_NOTIFY_MOVE (1<<2)
|
|---|
| 64 | #define TREE_NOTIFY_SORT (1<<3)
|
|---|
| 65 | #define TREE_NOTIFY_RELABEL (1<<4)
|
|---|
| 66 | #define TREE_NOTIFY_ALL \
|
|---|
| 67 | (TREE_NOTIFY_CREATE | TREE_NOTIFY_DELETE | TREE_NOTIFY_MOVE | \
|
|---|
| 68 | TREE_NOTIFY_SORT | TREE_NOTIFY_RELABEL)
|
|---|
| 69 | #define TREE_NOTIFY_MASK (TREE_NOTIFY_ALL)
|
|---|
| 70 |
|
|---|
| 71 | #define TREE_NOTIFY_WHENIDLE (1<<8)
|
|---|
| 72 | #define TREE_NOTIFY_FOREIGN_ONLY (1<<9)
|
|---|
| 73 | #define TREE_NOTIFY_ACTIVE (1<<10)
|
|---|
| 74 |
|
|---|
| 75 | typedef struct {
|
|---|
| 76 | int type;
|
|---|
| 77 | Blt_Tree tree;
|
|---|
| 78 | int inode; /* Node of event */
|
|---|
| 79 | Tcl_Interp *interp;
|
|---|
| 80 | } Blt_TreeNotifyEvent;
|
|---|
| 81 |
|
|---|
| 82 | typedef struct {
|
|---|
| 83 | Blt_TreeNode node; /* Node being searched. */
|
|---|
| 84 | unsigned long nextIndex; /* Index of next bucket to be
|
|---|
| 85 | * enumerated after present one. */
|
|---|
| 86 | Blt_TreeValue nextValue; /* Next entry to be enumerated in the
|
|---|
| 87 | * the current bucket. */
|
|---|
| 88 | } Blt_TreeKeySearch;
|
|---|
| 89 |
|
|---|
| 90 | /*
|
|---|
| 91 | * Blt_TreeObject --
|
|---|
| 92 | *
|
|---|
| 93 | * Structure providing the internal representation of the tree
|
|---|
| 94 | * object. A tree is uniquely identified by a combination of
|
|---|
| 95 | * its name and originating namespace. Two trees in the same
|
|---|
| 96 | * interpreter can have the same names but reside in different
|
|---|
| 97 | * namespaces.
|
|---|
| 98 | *
|
|---|
| 99 | * The tree object represents a general-ordered tree of nodes.
|
|---|
| 100 | * Each node may contain a heterogeneous collection of data
|
|---|
| 101 | * values. Each value is identified by a field name and nodes
|
|---|
| 102 | * do not need to contain the same data fields. Data field
|
|---|
| 103 | * names are saved as reference counted strings and can be
|
|---|
| 104 | * shared among nodes.
|
|---|
| 105 | *
|
|---|
| 106 | * The tree is threaded. A node contains both a pointer to
|
|---|
| 107 | * back its parents and another to its siblings. Therefore
|
|---|
| 108 | * the tree maybe traversed non-recursively.
|
|---|
| 109 | *
|
|---|
| 110 | * A tree object can be shared by several clients. When a
|
|---|
| 111 | * client wants to use a tree object, it is given a token
|
|---|
| 112 | * that represents the tree. The tree object uses the tokens
|
|---|
| 113 | * to keep track of its clients. When all clients have
|
|---|
| 114 | * released their tokens the tree is automatically destroyed.
|
|---|
| 115 | */
|
|---|
| 116 | struct Blt_TreeObjectStruct {
|
|---|
| 117 | Tcl_Interp *interp; /* Interpreter associated with this tree. */
|
|---|
| 118 |
|
|---|
| 119 | char *name;
|
|---|
| 120 |
|
|---|
| 121 | Tcl_Namespace *nsPtr;
|
|---|
| 122 |
|
|---|
| 123 | Blt_HashEntry *hashPtr; /* Pointer to this tree object in tree
|
|---|
| 124 | * object hash table. */
|
|---|
| 125 | Blt_HashTable *tablePtr;
|
|---|
| 126 |
|
|---|
| 127 | Blt_TreeNode root; /* Root of the entire tree. */
|
|---|
| 128 |
|
|---|
| 129 | char *sortNodesCmd; /* Tcl command to invoke to sort entries */
|
|---|
| 130 |
|
|---|
| 131 | Blt_Chain *clients; /* List of clients using this tree */
|
|---|
| 132 |
|
|---|
| 133 | Blt_Pool nodePool;
|
|---|
| 134 | Blt_Pool valuePool;
|
|---|
| 135 |
|
|---|
| 136 | Blt_HashTable nodeTable; /* Table of node identifiers. Used to
|
|---|
| 137 | * search for a node pointer given an inode.*/
|
|---|
| 138 | unsigned int nextInode;
|
|---|
| 139 |
|
|---|
| 140 | unsigned int nNodes; /* Always counts root node. */
|
|---|
| 141 |
|
|---|
| 142 | unsigned int depth; /* Maximum depth of the tree. */
|
|---|
| 143 |
|
|---|
| 144 | unsigned int flags; /* Internal flags. See definitions
|
|---|
| 145 | * below. */
|
|---|
| 146 | unsigned int notifyFlags; /* Notification flags. See definitions
|
|---|
| 147 | * below. */
|
|---|
| 148 |
|
|---|
| 149 | };
|
|---|
| 150 |
|
|---|
| 151 | /*
|
|---|
| 152 | * Blt_TreeNodeStruct --
|
|---|
| 153 | *
|
|---|
| 154 | * Structure representing a node in a general ordered tree.
|
|---|
| 155 | * Nodes are identified by their index, or inode. Nodes also
|
|---|
| 156 | * have names, but nodes names are not unique and can be
|
|---|
| 157 | * changed. Inodes are valid even if the node is moved.
|
|---|
| 158 | *
|
|---|
| 159 | * Each node can contain a list of data fields. Fields are
|
|---|
| 160 | * name-value pairs. The values are represented by Tcl_Objs.
|
|---|
| 161 | *
|
|---|
| 162 | */
|
|---|
| 163 | struct Blt_TreeNodeStruct {
|
|---|
| 164 | Blt_TreeNode parent; /* Parent node. If NULL, then this is
|
|---|
| 165 | the root node. */
|
|---|
| 166 | Blt_TreeNode next; /* Next sibling node. */
|
|---|
| 167 | Blt_TreeNode prev; /* Previous sibling node. */
|
|---|
| 168 | Blt_TreeNode first; /* First child node. */
|
|---|
| 169 | Blt_TreeNode last; /* Last child node. */
|
|---|
| 170 |
|
|---|
| 171 | Blt_TreeKey label; /* Node label (doesn't have to be
|
|---|
| 172 | * unique). */
|
|---|
| 173 |
|
|---|
| 174 | Blt_TreeObject treeObject;
|
|---|
| 175 |
|
|---|
| 176 | Blt_TreeValue values; /* Depending upon the number of values
|
|---|
| 177 | * stored, this is either a chain or
|
|---|
| 178 | * hash table of Blt_TreeValue
|
|---|
| 179 | * structures. (Note: if logSize is
|
|---|
| 180 | * 0, then this is a list). Each
|
|---|
| 181 | * value contains key/value data
|
|---|
| 182 | * pair. The data is a Tcl_Obj. */
|
|---|
| 183 |
|
|---|
| 184 | unsigned short nValues; /* # of values for this node. */
|
|---|
| 185 |
|
|---|
| 186 | unsigned short logSize; /* Size of hash table indicated as a
|
|---|
| 187 | * power of 2 (e.g. if logSize=3, then
|
|---|
| 188 | * table size is 8). If 0, this
|
|---|
| 189 | * indicates that the node's values
|
|---|
| 190 | * are stored as a list. */
|
|---|
| 191 |
|
|---|
| 192 | unsigned int nChildren; /* # of children for this node. */
|
|---|
| 193 | unsigned int inode; /* Serial number of the node. */
|
|---|
| 194 |
|
|---|
| 195 | unsigned short depth; /* The depth of this node in the tree. */
|
|---|
| 196 |
|
|---|
| 197 | unsigned short flags;
|
|---|
| 198 | };
|
|---|
| 199 |
|
|---|
| 200 | struct Blt_TreeTagEntryStruct {
|
|---|
| 201 | char *tagName;
|
|---|
| 202 | Blt_HashEntry *hashPtr;
|
|---|
| 203 | Blt_HashTable nodeTable;
|
|---|
| 204 | };
|
|---|
| 205 |
|
|---|
| 206 | struct Blt_TreeTagTableStruct {
|
|---|
| 207 | Blt_HashTable tagTable;
|
|---|
| 208 | int refCount;
|
|---|
| 209 | };
|
|---|
| 210 |
|
|---|
| 211 | /*
|
|---|
| 212 | * Blt_TreeClientStruct --
|
|---|
| 213 | *
|
|---|
| 214 | * A tree can be shared by several clients. Each client allocates
|
|---|
| 215 | * this structure which acts as a ticket for using the tree. Clients
|
|---|
| 216 | * can designate notifier routines that are automatically invoked
|
|---|
| 217 | * by the tree object whenever the tree is changed is specific
|
|---|
| 218 | * ways by other clients.
|
|---|
| 219 | */
|
|---|
| 220 |
|
|---|
| 221 | struct Blt_TreeClientStruct {
|
|---|
| 222 | unsigned int magic; /* Magic value indicating whether a
|
|---|
| 223 | * generic pointer is really a tree
|
|---|
| 224 | * token or not. */
|
|---|
| 225 | Blt_ChainLink *linkPtr; /* Pointer into the server's chain of
|
|---|
| 226 | * clients. */
|
|---|
| 227 | Blt_TreeObject treeObject; /* Pointer to the structure containing
|
|---|
| 228 | * the master information about the
|
|---|
| 229 | * tree used by the client. If NULL,
|
|---|
| 230 | * this indicates that the tree has
|
|---|
| 231 | * been destroyed (but as of yet, this
|
|---|
| 232 | * client hasn't recognized it). */
|
|---|
| 233 |
|
|---|
| 234 | Blt_Chain *events; /* Chain of node event handlers. */
|
|---|
| 235 | Blt_Chain *traces; /* Chain of data field callbacks. */
|
|---|
| 236 | Blt_TreeNode root; /* Designated root for this client */
|
|---|
| 237 | Blt_TreeTagTable *tagTablePtr;
|
|---|
| 238 | };
|
|---|
| 239 |
|
|---|
| 240 |
|
|---|
| 241 | typedef int (Blt_TreeNotifyEventProc) _ANSI_ARGS_((ClientData clientData,
|
|---|
| 242 | Blt_TreeNotifyEvent *eventPtr));
|
|---|
| 243 |
|
|---|
| 244 | typedef int (Blt_TreeTraceProc) _ANSI_ARGS_((ClientData clientData,
|
|---|
| 245 | Tcl_Interp *interp, Blt_TreeNode node, Blt_TreeKey key,
|
|---|
| 246 | unsigned int flags));
|
|---|
| 247 |
|
|---|
| 248 | typedef int (Blt_TreeEnumProc) _ANSI_ARGS_((Blt_TreeNode node, Blt_TreeKey key,
|
|---|
| 249 | Tcl_Obj *valuePtr));
|
|---|
| 250 |
|
|---|
| 251 | typedef int (Blt_TreeCompareNodesProc) _ANSI_ARGS_((Blt_TreeNode *n1Ptr,
|
|---|
| 252 | Blt_TreeNode *n2Ptr));
|
|---|
| 253 |
|
|---|
| 254 | typedef int (Blt_TreeApplyProc) _ANSI_ARGS_((Blt_TreeNode node,
|
|---|
| 255 | ClientData clientData, int order));
|
|---|
| 256 |
|
|---|
| 257 | struct Blt_TreeTraceStruct {
|
|---|
| 258 | ClientData clientData;
|
|---|
| 259 | Blt_TreeKey key;
|
|---|
| 260 | Blt_TreeNode node;
|
|---|
| 261 | unsigned int mask;
|
|---|
| 262 | Blt_TreeTraceProc *proc;
|
|---|
| 263 | };
|
|---|
| 264 |
|
|---|
| 265 | /*
|
|---|
| 266 | * Structure definition for information used to keep track of searches
|
|---|
| 267 | * through hash tables:p
|
|---|
| 268 | */
|
|---|
| 269 | struct Blt_TreeKeySearchStruct {
|
|---|
| 270 | Blt_TreeNode node; /* Table being searched. */
|
|---|
| 271 | unsigned long nextIndex; /* Index of next bucket to be
|
|---|
| 272 | * enumerated after present one. */
|
|---|
| 273 | Blt_TreeValue nextValue; /* Next entry to be enumerated in the
|
|---|
| 274 | * the current bucket. */
|
|---|
| 275 | };
|
|---|
| 276 |
|
|---|
| 277 | EXTERN Blt_TreeKey Blt_TreeGetKey _ANSI_ARGS_((CONST char *string));
|
|---|
| 278 |
|
|---|
| 279 | EXTERN Blt_TreeNode Blt_TreeCreateNode _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 280 | Blt_TreeNode parent, CONST char *name, int position));
|
|---|
| 281 | EXTERN Blt_TreeNode Blt_TreeCreateNodeWithId _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 282 | Blt_TreeNode parent, CONST char *name, int position, int inode));
|
|---|
| 283 |
|
|---|
| 284 | EXTERN int Blt_TreeDeleteNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));
|
|---|
| 285 |
|
|---|
| 286 | EXTERN int Blt_TreeMoveNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 287 | Blt_TreeNode parent, Blt_TreeNode before));
|
|---|
| 288 |
|
|---|
| 289 | EXTERN Blt_TreeNode Blt_TreeGetNode _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 290 | unsigned int inode));
|
|---|
| 291 |
|
|---|
| 292 | EXTERN Blt_TreeNode Blt_TreeFindChild _ANSI_ARGS_((Blt_TreeNode parent,
|
|---|
| 293 | CONST char *name));
|
|---|
| 294 |
|
|---|
| 295 | EXTERN Blt_TreeNode Blt_TreeFirstChild _ANSI_ARGS_((Blt_TreeNode parent));
|
|---|
| 296 |
|
|---|
| 297 | EXTERN Blt_TreeNode Blt_TreeNextSibling _ANSI_ARGS_((Blt_TreeNode node));
|
|---|
| 298 |
|
|---|
| 299 | EXTERN Blt_TreeNode Blt_TreeLastChild _ANSI_ARGS_((Blt_TreeNode parent));
|
|---|
| 300 |
|
|---|
| 301 | EXTERN Blt_TreeNode Blt_TreePrevSibling _ANSI_ARGS_((Blt_TreeNode node));
|
|---|
| 302 |
|
|---|
| 303 | EXTERN Blt_TreeNode Blt_TreeNextNode _ANSI_ARGS_((Blt_TreeNode root,
|
|---|
| 304 | Blt_TreeNode node));
|
|---|
| 305 |
|
|---|
| 306 | EXTERN Blt_TreeNode Blt_TreePrevNode _ANSI_ARGS_((Blt_TreeNode root,
|
|---|
| 307 | Blt_TreeNode node));
|
|---|
| 308 |
|
|---|
| 309 | EXTERN Blt_TreeNode Blt_TreeChangeRoot _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 310 | Blt_TreeNode node));
|
|---|
| 311 |
|
|---|
| 312 | EXTERN Blt_TreeNode Blt_TreeEndNode _ANSI_ARGS_((Blt_TreeNode node,
|
|---|
| 313 | unsigned int nodeFlags));
|
|---|
| 314 |
|
|---|
| 315 | EXTERN int Blt_TreeIsBefore _ANSI_ARGS_((Blt_TreeNode node1,
|
|---|
| 316 | Blt_TreeNode node2));
|
|---|
| 317 |
|
|---|
| 318 | EXTERN int Blt_TreeIsAncestor _ANSI_ARGS_((Blt_TreeNode node1,
|
|---|
| 319 | Blt_TreeNode node2));
|
|---|
| 320 |
|
|---|
| 321 | EXTERN int Blt_TreePrivateValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 322 | Blt_TreeNode node, Blt_TreeKey key));
|
|---|
| 323 |
|
|---|
| 324 | EXTERN int Blt_TreePublicValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 325 | Blt_TreeNode node, Blt_TreeKey key));
|
|---|
| 326 |
|
|---|
| 327 | EXTERN int Blt_TreeGetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 328 | Blt_TreeNode node, CONST char *string, Tcl_Obj **valuePtr));
|
|---|
| 329 |
|
|---|
| 330 | EXTERN int Blt_TreeValueExists _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 331 | CONST char *string));
|
|---|
| 332 |
|
|---|
| 333 | EXTERN int Blt_TreeSetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 334 | Blt_TreeNode node, CONST char *string, Tcl_Obj *valuePtr));
|
|---|
| 335 |
|
|---|
| 336 | EXTERN int Blt_TreeUnsetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 337 | Blt_TreeNode node, CONST char *string));
|
|---|
| 338 |
|
|---|
| 339 | EXTERN int Blt_TreeGetArrayValue _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 340 | Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName,
|
|---|
| 341 | CONST char *elemName, Tcl_Obj **valueObjPtrPtr));
|
|---|
| 342 |
|
|---|
| 343 | EXTERN int Blt_TreeSetArrayValue _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 344 | Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName,
|
|---|
| 345 | CONST char *elemName, Tcl_Obj *valueObjPtr));
|
|---|
| 346 |
|
|---|
| 347 | EXTERN int Blt_TreeUnsetArrayValue _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 348 | Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName,
|
|---|
| 349 | CONST char *elemName));
|
|---|
| 350 |
|
|---|
| 351 | EXTERN int Blt_TreeArrayValueExists _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 352 | Blt_TreeNode node, CONST char *arrayName, CONST char *elemName));
|
|---|
| 353 |
|
|---|
| 354 | EXTERN int Blt_TreeArrayNames _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
|
|---|
| 355 | Blt_TreeNode node, CONST char *arrayName, Tcl_Obj *listObjPtr));
|
|---|
| 356 |
|
|---|
| 357 | EXTERN int Blt_TreeGetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 358 | Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key,
|
|---|
| 359 | Tcl_Obj **valuePtr));
|
|---|
| 360 |
|
|---|
| 361 | EXTERN int Blt_TreeSetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 362 | Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key, Tcl_Obj *valuePtr));
|
|---|
| 363 |
|
|---|
| 364 | EXTERN int Blt_TreeUnsetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
|
|---|
| 365 | Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key));
|
|---|
| 366 |
|
|---|
| 367 | EXTERN int Blt_TreeValueExistsByKey _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 368 | Blt_TreeNode node, Blt_TreeKey key));
|
|---|
| 369 |
|
|---|
| 370 | EXTERN Blt_TreeKey Blt_TreeFirstKey _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 371 | Blt_TreeNode node, Blt_TreeKeySearch *cursorPtr));
|
|---|
| 372 |
|
|---|
| 373 | EXTERN Blt_TreeKey Blt_TreeNextKey _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 374 | Blt_TreeKeySearch *cursorPtr));
|
|---|
| 375 |
|
|---|
| 376 | EXTERN int Blt_TreeApply _ANSI_ARGS_((Blt_TreeNode root,
|
|---|
| 377 | Blt_TreeApplyProc *proc, ClientData clientData));
|
|---|
| 378 |
|
|---|
| 379 | EXTERN int Blt_TreeApplyDFS _ANSI_ARGS_((Blt_TreeNode root,
|
|---|
| 380 | Blt_TreeApplyProc *proc, ClientData clientData, int order));
|
|---|
| 381 |
|
|---|
| 382 | EXTERN int Blt_TreeApplyBFS _ANSI_ARGS_((Blt_TreeNode root,
|
|---|
| 383 | Blt_TreeApplyProc *proc, ClientData clientData));
|
|---|
| 384 |
|
|---|
| 385 | EXTERN int Blt_TreeSortNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 386 | Blt_TreeCompareNodesProc *proc));
|
|---|
| 387 |
|
|---|
| 388 | EXTERN int Blt_TreeCreate _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name,
|
|---|
| 389 | Blt_Tree *treePtr));
|
|---|
| 390 |
|
|---|
| 391 | EXTERN int Blt_TreeExists _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name));
|
|---|
| 392 |
|
|---|
| 393 | EXTERN int Blt_TreeGetToken _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name,
|
|---|
| 394 | Blt_Tree *treePtr));
|
|---|
| 395 |
|
|---|
| 396 | EXTERN void Blt_TreeReleaseToken _ANSI_ARGS_((Blt_Tree tree));
|
|---|
| 397 |
|
|---|
| 398 | EXTERN int Blt_TreeSize _ANSI_ARGS_((Blt_TreeNode node));
|
|---|
| 399 |
|
|---|
| 400 | EXTERN Blt_TreeTrace Blt_TreeCreateTrace _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 401 | Blt_TreeNode node, CONST char *keyPattern, CONST char *tagName,
|
|---|
| 402 | unsigned int mask, Blt_TreeTraceProc *proc, ClientData clientData));
|
|---|
| 403 |
|
|---|
| 404 | EXTERN void Blt_TreeDeleteTrace _ANSI_ARGS_((Blt_TreeTrace token));
|
|---|
| 405 |
|
|---|
| 406 | EXTERN void Blt_TreeCreateEventHandler _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 407 | unsigned int mask, Blt_TreeNotifyEventProc *proc,
|
|---|
| 408 | ClientData clientData));
|
|---|
| 409 |
|
|---|
| 410 | EXTERN void Blt_TreeDeleteEventHandler _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 411 | unsigned int mask, Blt_TreeNotifyEventProc *proc,
|
|---|
| 412 | ClientData clientData));
|
|---|
| 413 |
|
|---|
| 414 | EXTERN void Blt_TreeRelabelNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 415 | CONST char *string));
|
|---|
| 416 | EXTERN void Blt_TreeRelabelNode2 _ANSI_ARGS_((Blt_TreeNode node,
|
|---|
| 417 | CONST char *string));
|
|---|
| 418 | EXTERN char *Blt_TreeNodePath _ANSI_ARGS_((Blt_TreeNode node,
|
|---|
| 419 | Tcl_DString *resultPtr));
|
|---|
| 420 | EXTERN int Blt_TreeNodePosition _ANSI_ARGS_((Blt_TreeNode node));
|
|---|
| 421 |
|
|---|
| 422 | EXTERN void Blt_TreeClearTags _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));
|
|---|
| 423 | EXTERN int Blt_TreeHasTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 424 | CONST char *tagName));
|
|---|
| 425 | EXTERN void Blt_TreeAddTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
|
|---|
| 426 | CONST char *tagName));
|
|---|
| 427 | EXTERN void Blt_TreeForgetTag _ANSI_ARGS_((Blt_Tree tree, CONST char *tagName));
|
|---|
| 428 | EXTERN Blt_HashTable *Blt_TreeTagHashTable _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 429 | CONST char *tagName));
|
|---|
| 430 | EXTERN int Blt_TreeTagTableIsShared _ANSI_ARGS_((Blt_Tree tree));
|
|---|
| 431 | EXTERN int Blt_TreeShareTagTable _ANSI_ARGS_((Blt_Tree src, Blt_Tree target));
|
|---|
| 432 | EXTERN Blt_HashEntry *Blt_TreeFirstTag _ANSI_ARGS_((Blt_Tree tree,
|
|---|
| 433 | Blt_HashSearch *searchPtr));
|
|---|
| 434 |
|
|---|
| 435 | #define Blt_TreeName(token) ((token)->treeObject->name)
|
|---|
| 436 | #define Blt_TreeRootNode(token) ((token)->root)
|
|---|
| 437 | #define Blt_TreeChangeRoot(token, node) ((token)->root = (node))
|
|---|
| 438 |
|
|---|
| 439 | #define Blt_TreeNodeDepth(token, node) ((node)->depth - (token)->root->depth)
|
|---|
| 440 | #define Blt_TreeNodeLabel(node) ((node)->label)
|
|---|
| 441 | #define Blt_TreeNodeId(node) ((node)->inode)
|
|---|
| 442 | #define Blt_TreeNodeParent(node) ((node)->parent)
|
|---|
| 443 | #define Blt_TreeNodeDegree(node) ((node)->nChildren)
|
|---|
| 444 |
|
|---|
| 445 | #define Blt_TreeIsLeaf(node) ((node)->nChildren == 0)
|
|---|
| 446 | #define Blt_TreeNextNodeId(token) ((token)->treeObject->nextInode)
|
|---|
| 447 |
|
|---|
| 448 | #define Blt_TreeFirstChild(node) ((node)->first)
|
|---|
| 449 | #define Blt_TreeLastChild(node) ((node)->last)
|
|---|
| 450 | #define Blt_TreeNextSibling(node) (((node) == NULL) ? NULL : (node)->next)
|
|---|
| 451 | #define Blt_TreePrevSibling(node) (((node) == NULL) ? NULL : (node)->prev)
|
|---|
| 452 |
|
|---|
| 453 | #endif /* _BLT_TREE_H */
|
|---|
| 454 |
|
|---|
