source: trunk/kitgen/8.x/blt/generic/bltTree.h@ 181

Last change on this file since 181 was 175, checked in by demin, 12 years ago

initial commit

File size: 15.8 KB
Line 
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
35typedef struct Blt_TreeNodeStruct *Blt_TreeNode;
36typedef struct Blt_TreeObjectStruct *Blt_TreeObject;
37typedef struct Blt_TreeClientStruct *Blt_Tree;
38typedef struct Blt_TreeTraceStruct *Blt_TreeTrace;
39typedef struct Blt_TreeValueStruct *Blt_TreeValue;
40typedef struct Blt_TreeTagEntryStruct Blt_TreeTagEntry;
41typedef struct Blt_TreeTagTableStruct Blt_TreeTagTable;
42
43typedef 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
75typedef struct {
76 int type;
77 Blt_Tree tree;
78 int inode; /* Node of event */
79 Tcl_Interp *interp;
80} Blt_TreeNotifyEvent;
81
82typedef 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 */
116struct 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 */
163struct 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
200struct Blt_TreeTagEntryStruct {
201 char *tagName;
202 Blt_HashEntry *hashPtr;
203 Blt_HashTable nodeTable;
204};
205
206struct 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
221struct 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
241typedef int (Blt_TreeNotifyEventProc) _ANSI_ARGS_((ClientData clientData,
242 Blt_TreeNotifyEvent *eventPtr));
243
244typedef int (Blt_TreeTraceProc) _ANSI_ARGS_((ClientData clientData,
245 Tcl_Interp *interp, Blt_TreeNode node, Blt_TreeKey key,
246 unsigned int flags));
247
248typedef int (Blt_TreeEnumProc) _ANSI_ARGS_((Blt_TreeNode node, Blt_TreeKey key,
249 Tcl_Obj *valuePtr));
250
251typedef int (Blt_TreeCompareNodesProc) _ANSI_ARGS_((Blt_TreeNode *n1Ptr,
252 Blt_TreeNode *n2Ptr));
253
254typedef int (Blt_TreeApplyProc) _ANSI_ARGS_((Blt_TreeNode node,
255 ClientData clientData, int order));
256
257struct 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 */
269struct 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
277EXTERN Blt_TreeKey Blt_TreeGetKey _ANSI_ARGS_((CONST char *string));
278
279EXTERN Blt_TreeNode Blt_TreeCreateNode _ANSI_ARGS_((Blt_Tree tree,
280 Blt_TreeNode parent, CONST char *name, int position));
281EXTERN Blt_TreeNode Blt_TreeCreateNodeWithId _ANSI_ARGS_((Blt_Tree tree,
282 Blt_TreeNode parent, CONST char *name, int position, int inode));
283
284EXTERN int Blt_TreeDeleteNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));
285
286EXTERN int Blt_TreeMoveNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
287 Blt_TreeNode parent, Blt_TreeNode before));
288
289EXTERN Blt_TreeNode Blt_TreeGetNode _ANSI_ARGS_((Blt_Tree tree,
290 unsigned int inode));
291
292EXTERN Blt_TreeNode Blt_TreeFindChild _ANSI_ARGS_((Blt_TreeNode parent,
293 CONST char *name));
294
295EXTERN Blt_TreeNode Blt_TreeFirstChild _ANSI_ARGS_((Blt_TreeNode parent));
296
297EXTERN Blt_TreeNode Blt_TreeNextSibling _ANSI_ARGS_((Blt_TreeNode node));
298
299EXTERN Blt_TreeNode Blt_TreeLastChild _ANSI_ARGS_((Blt_TreeNode parent));
300
301EXTERN Blt_TreeNode Blt_TreePrevSibling _ANSI_ARGS_((Blt_TreeNode node));
302
303EXTERN Blt_TreeNode Blt_TreeNextNode _ANSI_ARGS_((Blt_TreeNode root,
304 Blt_TreeNode node));
305
306EXTERN Blt_TreeNode Blt_TreePrevNode _ANSI_ARGS_((Blt_TreeNode root,
307 Blt_TreeNode node));
308
309EXTERN Blt_TreeNode Blt_TreeChangeRoot _ANSI_ARGS_((Blt_Tree tree,
310 Blt_TreeNode node));
311
312EXTERN Blt_TreeNode Blt_TreeEndNode _ANSI_ARGS_((Blt_TreeNode node,
313 unsigned int nodeFlags));
314
315EXTERN int Blt_TreeIsBefore _ANSI_ARGS_((Blt_TreeNode node1,
316 Blt_TreeNode node2));
317
318EXTERN int Blt_TreeIsAncestor _ANSI_ARGS_((Blt_TreeNode node1,
319 Blt_TreeNode node2));
320
321EXTERN int Blt_TreePrivateValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
322 Blt_TreeNode node, Blt_TreeKey key));
323
324EXTERN int Blt_TreePublicValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
325 Blt_TreeNode node, Blt_TreeKey key));
326
327EXTERN int Blt_TreeGetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
328 Blt_TreeNode node, CONST char *string, Tcl_Obj **valuePtr));
329
330EXTERN int Blt_TreeValueExists _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
331 CONST char *string));
332
333EXTERN int Blt_TreeSetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
334 Blt_TreeNode node, CONST char *string, Tcl_Obj *valuePtr));
335
336EXTERN int Blt_TreeUnsetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
337 Blt_TreeNode node, CONST char *string));
338
339EXTERN 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
343EXTERN 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
347EXTERN int Blt_TreeUnsetArrayValue _ANSI_ARGS_((Tcl_Interp *interp,
348 Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName,
349 CONST char *elemName));
350
351EXTERN int Blt_TreeArrayValueExists _ANSI_ARGS_((Blt_Tree tree,
352 Blt_TreeNode node, CONST char *arrayName, CONST char *elemName));
353
354EXTERN int Blt_TreeArrayNames _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
355 Blt_TreeNode node, CONST char *arrayName, Tcl_Obj *listObjPtr));
356
357EXTERN int Blt_TreeGetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
358 Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key,
359 Tcl_Obj **valuePtr));
360
361EXTERN int Blt_TreeSetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
362 Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key, Tcl_Obj *valuePtr));
363
364EXTERN int Blt_TreeUnsetValueByKey _ANSI_ARGS_((Tcl_Interp *interp,
365 Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key));
366
367EXTERN int Blt_TreeValueExistsByKey _ANSI_ARGS_((Blt_Tree tree,
368 Blt_TreeNode node, Blt_TreeKey key));
369
370EXTERN Blt_TreeKey Blt_TreeFirstKey _ANSI_ARGS_((Blt_Tree tree,
371 Blt_TreeNode node, Blt_TreeKeySearch *cursorPtr));
372
373EXTERN Blt_TreeKey Blt_TreeNextKey _ANSI_ARGS_((Blt_Tree tree,
374 Blt_TreeKeySearch *cursorPtr));
375
376EXTERN int Blt_TreeApply _ANSI_ARGS_((Blt_TreeNode root,
377 Blt_TreeApplyProc *proc, ClientData clientData));
378
379EXTERN int Blt_TreeApplyDFS _ANSI_ARGS_((Blt_TreeNode root,
380 Blt_TreeApplyProc *proc, ClientData clientData, int order));
381
382EXTERN int Blt_TreeApplyBFS _ANSI_ARGS_((Blt_TreeNode root,
383 Blt_TreeApplyProc *proc, ClientData clientData));
384
385EXTERN int Blt_TreeSortNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
386 Blt_TreeCompareNodesProc *proc));
387
388EXTERN int Blt_TreeCreate _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name,
389 Blt_Tree *treePtr));
390
391EXTERN int Blt_TreeExists _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name));
392
393EXTERN int Blt_TreeGetToken _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name,
394 Blt_Tree *treePtr));
395
396EXTERN void Blt_TreeReleaseToken _ANSI_ARGS_((Blt_Tree tree));
397
398EXTERN int Blt_TreeSize _ANSI_ARGS_((Blt_TreeNode node));
399
400EXTERN 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
404EXTERN void Blt_TreeDeleteTrace _ANSI_ARGS_((Blt_TreeTrace token));
405
406EXTERN void Blt_TreeCreateEventHandler _ANSI_ARGS_((Blt_Tree tree,
407 unsigned int mask, Blt_TreeNotifyEventProc *proc,
408 ClientData clientData));
409
410EXTERN void Blt_TreeDeleteEventHandler _ANSI_ARGS_((Blt_Tree tree,
411 unsigned int mask, Blt_TreeNotifyEventProc *proc,
412 ClientData clientData));
413
414EXTERN void Blt_TreeRelabelNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
415 CONST char *string));
416EXTERN void Blt_TreeRelabelNode2 _ANSI_ARGS_((Blt_TreeNode node,
417 CONST char *string));
418EXTERN char *Blt_TreeNodePath _ANSI_ARGS_((Blt_TreeNode node,
419 Tcl_DString *resultPtr));
420EXTERN int Blt_TreeNodePosition _ANSI_ARGS_((Blt_TreeNode node));
421
422EXTERN void Blt_TreeClearTags _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));
423EXTERN int Blt_TreeHasTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
424 CONST char *tagName));
425EXTERN void Blt_TreeAddTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node,
426 CONST char *tagName));
427EXTERN void Blt_TreeForgetTag _ANSI_ARGS_((Blt_Tree tree, CONST char *tagName));
428EXTERN Blt_HashTable *Blt_TreeTagHashTable _ANSI_ARGS_((Blt_Tree tree,
429 CONST char *tagName));
430EXTERN int Blt_TreeTagTableIsShared _ANSI_ARGS_((Blt_Tree tree));
431EXTERN int Blt_TreeShareTagTable _ANSI_ARGS_((Blt_Tree src, Blt_Tree target));
432EXTERN 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
Note: See TracBrowser for help on using the repository browser.