source: branches/geomap/src/objects/RpTree.h @ 6632

Last change on this file since 6632 was 5673, checked in by ldelgass, 9 years ago

Fix line endings, set eol-style to native on all C/C++ sources.
  • Property svn:eol-style set to native
File size: 17.4 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 _RP_TREE_H
29#define _RP_TREE_H
30
31#include <RpInt.h>
32#include <RpChain.h>
33#include <RpHash.h>
34#include <RpPool.h>
35
36typedef struct Rp_TreeNodeStruct *Rp_TreeNode;
37typedef struct Rp_TreeObjectStruct *Rp_TreeObject;
38typedef struct Rp_TreeClientStruct *Rp_Tree;
39typedef struct Rp_TreeTraceStruct *Rp_TreeTrace;
40typedef struct Rp_TreeValueStruct *Rp_TreeValue;
41typedef struct Rp_TreeTagEntryStruct Rp_TreeTagEntry;
42typedef struct Rp_TreeTagTableStruct Rp_TreeTagTable;
43
44typedef char *Rp_TreeKey;
45
46#define TREE_PREORDER       (1<<0)
47#define TREE_POSTORDER      (1<<1)
48#define TREE_INORDER        (1<<2)
49#define TREE_BREADTHFIRST   (1<<3)
50
51#define TREE_TRACE_UNSET    (1<<3)
52#define TREE_TRACE_WRITE    (1<<4)
53#define TREE_TRACE_READ     (1<<5)
54#define TREE_TRACE_CREATE   (1<<6)
55#define TREE_TRACE_ALL      \
56    (TREE_TRACE_UNSET | TREE_TRACE_WRITE | TREE_TRACE_READ | TREE_TRACE_CREATE)
57#define TREE_TRACE_MASK     (TREE_TRACE_ALL)
58
59#define TREE_TRACE_FOREIGN_ONLY (1<<8)
60#define TREE_TRACE_ACTIVE   (1<<9)
61
62#define TREE_NOTIFY_CREATE  (1<<0)
63#define TREE_NOTIFY_DELETE  (1<<1)
64#define TREE_NOTIFY_MOVE    (1<<2)
65#define TREE_NOTIFY_SORT    (1<<3)
66#define TREE_NOTIFY_RELABEL (1<<4)
67#define TREE_NOTIFY_ALL     \
68    (TREE_NOTIFY_CREATE | TREE_NOTIFY_DELETE | TREE_NOTIFY_MOVE | \
69    TREE_NOTIFY_SORT | TREE_NOTIFY_RELABEL)
70#define TREE_NOTIFY_MASK    (TREE_NOTIFY_ALL)
71
72#define TREE_NOTIFY_WHENIDLE    (1<<8)
73#define TREE_NOTIFY_FOREIGN_ONLY (1<<9)
74#define TREE_NOTIFY_ACTIVE      (1<<10)
75
76typedef struct {
77    int type;
78    Rp_Tree tree;
79    int inode;          /* Node of event */
80    // Tcl_Interp *interp;
81} Rp_TreeNotifyEvent;
82
83typedef struct {
84    Rp_TreeNode node;           /* Node being searched. */
85    unsigned long nextIndex;    /* Index of next bucket to be
86                                 * enumerated after present one. */
87    Rp_TreeValue nextValue;     /* Next entry to be enumerated in the
88                                 * the current bucket. */
89} Rp_TreeKeySearch;
90
91/*
92 * Rp_TreeObject --
93 *
94 *  Structure providing the internal representation of the tree
95 *  object. A tree is uniquely identified by a combination of
96 *  its name and originating namespace.  Two trees in the same
97 *  interpreter can have the same names but reside in different
98 *  namespaces.
99 *
100 *  The tree object represents a general-ordered tree of nodes.
101 *  Each node may contain a heterogeneous collection of data
102 *  values. Each value is identified by a field name and nodes
103 *  do not need to contain the same data fields. Data field
104 *  names are saved as reference counted strings and can be
105 *  shared among nodes.
106 *
107 *  The tree is threaded.  A node contains both a pointer to
108 *  back its parents and another to its siblings.  Therefore
109 *  the tree maybe traversed non-recursively.
110 *
111 *  A tree object can be shared by several clients.  When a
112 *  client wants to use a tree object, it is given a token
113 *  that represents the tree.  The tree object uses the tokens
114 *  to keep track of its clients.  When all clients have
115 *  released their tokens the tree is automatically destroyed.
116 */
117struct Rp_TreeObjectStruct {
118//    Tcl_Interp *interp;     /* Interpreter associated with this tree. */
119
120    char *name;
121
122//    Tcl_Namespace *nsPtr;
123
124    Rp_HashEntry *hashPtr;  /* Pointer to this tree object in tree
125                             * object hash table. */
126    Rp_HashTable *tablePtr;
127
128    Rp_TreeNode root;       /* Root of the entire tree. */
129
130    char *sortNodesCmd;     /* Tcl command to invoke to sort entries */
131
132    Rp_Chain *clients;      /* List of clients using this tree */
133
134    Rp_Pool nodePool;
135    Rp_Pool valuePool;
136
137    Rp_HashTable nodeTable; /* Table of node identifiers. Used to
138                             * search for a node pointer given an inode.*/
139    unsigned int nextInode;
140
141    unsigned int nNodes;    /* Always counts root node. */
142
143    unsigned int depth;     /* Maximum depth of the tree. */
144
145    unsigned int flags;     /* Internal flags. See definitions
146                             * below. */
147    unsigned int notifyFlags;   /* Notification flags. See definitions
148                                 * below. */
149
150};
151
152/*
153 * Rp_TreeNodeStruct --
154 *
155 *  Structure representing a node in a general ordered tree.
156 *  Nodes are identified by their index, or inode.  Nodes also
157 *  have names, but nodes names are not unique and can be
158 *  changed.  Inodes are valid even if the node is moved.
159 *
160 *  Each node can contain a list of data fields.  Fields are
161 *  name-value pairs.  The values are represented by Tcl_Objs.
162 *
163 */
164struct Rp_TreeNodeStruct {
165    Rp_TreeNode parent; /* Parent node. If NULL, then this is
166                           the root node. */
167    Rp_TreeNode next;       /* Next sibling node. */
168    Rp_TreeNode prev;       /* Previous sibling node. */
169    Rp_TreeNode first;      /* First child node. */
170    Rp_TreeNode last;       /* Last child node. */
171
172    Rp_TreeKey label;       /* Node label (doesn't have to be
173                             * unique). */
174
175    Rp_TreeObject treeObject;
176
177    Rp_TreeValue values;    /* Depending upon the number of values
178                             * stored, this is either a chain or
179                             * hash table of Rp_TreeValue
180                             * structures.  (Note: if logSize is
181                             * 0, then this is a list).  Each
182                             * value contains key/value data
183                             * pair.  The data is a Tcl_Obj. */
184
185    unsigned short nValues; /* # of values for this node. */
186
187    unsigned short logSize; /* Size of hash table indicated as a
188                             * power of 2 (e.g. if logSize=3, then
189                             * table size is 8). If 0, this
190                             * indicates that the node's values
191                             * are stored as a list. */
192
193    unsigned int nChildren; /* # of children for this node. */
194    // unsigned int inode;     /* Serial number of the node. */
195    size_t inode;           /* Serial number of the node. */
196
197    unsigned short depth;   /* The depth of this node in the tree. */
198
199    unsigned short flags;
200};
201
202struct Rp_TreeTagEntryStruct {
203    char *tagName;
204    Rp_HashEntry *hashPtr;
205    Rp_HashTable nodeTable;
206};
207
208struct Rp_TreeTagTableStruct {
209    Rp_HashTable tagTable;
210    int refCount;
211};
212
213/*
214 * Rp_TreeClientStruct --
215 *
216 *  A tree can be shared by several clients.  Each client allocates
217 *  this structure which acts as a ticket for using the tree.  Clients
218 *  can designate notifier routines that are automatically invoked
219 *  by the tree object whenever the tree is changed is specific
220 *  ways by other clients.
221 */
222
223struct Rp_TreeClientStruct {
224    unsigned int magic;     /* Magic value indicating whether a
225                             * generic pointer is really a tree
226                             * token or not. */
227    Rp_ChainLink *linkPtr;  /* Pointer into the server's chain of
228                             * clients. */
229    Rp_TreeObject treeObject;   /* Pointer to the structure containing
230                                 * the master information about the
231                                 * tree used by the client.  If NULL,
232                                 * this indicates that the tree has
233                                 * been destroyed (but as of yet, this
234                                 * client hasn't recognized it). */
235
236    Rp_Chain *events;       /* Chain of node event handlers. */
237    Rp_Chain *traces;       /* Chain of data field callbacks. */
238    Rp_TreeNode root;       /* Designated root for this client */
239    Rp_TreeTagTable *tagTablePtr;
240};
241
242
243typedef int (Rp_TreeNotifyEventProc) _ANSI_ARGS_((ClientData clientData,
244        Rp_TreeNotifyEvent *eventPtr));
245
246typedef int (Rp_TreeTraceProc) _ANSI_ARGS_((ClientData clientData,
247        Rp_TreeNode node, Rp_TreeKey key, unsigned int flags));
248
249typedef int (Rp_TreeEnumProc) _ANSI_ARGS_((Rp_TreeNode node, Rp_TreeKey key,
250        // Tcl_Obj *valuePtr));
251        void *valuePtr));
252
253typedef int (Rp_TreeCompareNodesProc) _ANSI_ARGS_((Rp_TreeNode *n1Ptr,
254        Rp_TreeNode *n2Ptr));
255
256typedef int (Rp_TreeApplyProc) _ANSI_ARGS_((Rp_TreeNode node,
257        ClientData clientData, int order));
258
259struct Rp_TreeTraceStruct {
260    ClientData clientData;
261    Rp_TreeKey key;
262    Rp_TreeNode node;
263    unsigned int mask;
264    Rp_TreeTraceProc *proc;
265};
266
267/*
268 * Structure definition for information used to keep track of searches
269 * through hash tables:p
270 */
271struct Rp_TreeKeySearchStruct {
272    Rp_TreeNode node;           /* Table being searched. */
273    unsigned long nextIndex;    /* Index of next bucket to be
274                                 * enumerated after present one. */
275    Rp_TreeValue nextValue;     /* Next entry to be enumerated in the
276                                 * the current bucket. */
277};
278
279EXTERN Rp_TreeKey Rp_TreeGetKey _ANSI_ARGS_((CONST char *string));
280
281EXTERN Rp_TreeNode Rp_TreeCreateNode _ANSI_ARGS_((Rp_Tree tree,
282        Rp_TreeNode parent, CONST char *name, int position));
283EXTERN Rp_TreeNode Rp_TreeCreateNodeWithId _ANSI_ARGS_((Rp_Tree tree,
284        Rp_TreeNode parent, CONST char *name, size_t inode, int position));
285
286EXTERN int Rp_TreeDeleteNode _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node));
287
288EXTERN int Rp_TreeMoveNode _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
289        Rp_TreeNode parent, Rp_TreeNode before));
290
291EXTERN Rp_TreeNode Rp_TreeGetNode _ANSI_ARGS_((Rp_Tree tree, size_t inode));
292
293EXTERN Rp_TreeNode Rp_TreeFindChild _ANSI_ARGS_((Rp_TreeNode parent,
294        CONST char *name));
295
296EXTERN Rp_TreeNode Rp_TreeFindChildNext _ANSI_ARGS_((Rp_TreeNode child,
297        CONST char *name));
298
299EXTERN Rp_TreeNode Rp_TreeFirstChild _ANSI_ARGS_((Rp_TreeNode parent));
300
301EXTERN Rp_TreeNode Rp_TreeNextSibling _ANSI_ARGS_((Rp_TreeNode node));
302
303EXTERN Rp_TreeNode Rp_TreeLastChild _ANSI_ARGS_((Rp_TreeNode parent));
304
305EXTERN Rp_TreeNode Rp_TreePrevSibling _ANSI_ARGS_((Rp_TreeNode node));
306
307EXTERN Rp_TreeNode Rp_TreeNextNode _ANSI_ARGS_((Rp_TreeNode root,
308        Rp_TreeNode node));
309
310EXTERN Rp_TreeNode Rp_TreePrevNode _ANSI_ARGS_((Rp_TreeNode root,
311        Rp_TreeNode node));
312
313EXTERN Rp_TreeNode Rp_TreeChangeRoot _ANSI_ARGS_((Rp_Tree tree,
314        Rp_TreeNode node));
315
316EXTERN Rp_TreeNode Rp_TreeEndNode _ANSI_ARGS_((Rp_TreeNode node,
317        unsigned int nodeFlags));
318
319EXTERN int Rp_TreeIsBefore _ANSI_ARGS_((Rp_TreeNode node1,
320        Rp_TreeNode node2));
321
322EXTERN int Rp_TreeIsAncestor _ANSI_ARGS_((Rp_TreeNode node1,
323        Rp_TreeNode node2));
324
325EXTERN int Rp_TreePrivateValue _ANSI_ARGS_((Rp_Tree tree,
326        Rp_TreeNode node, Rp_TreeKey key));
327
328EXTERN int Rp_TreePublicValue _ANSI_ARGS_((Rp_Tree tree,
329        Rp_TreeNode node, Rp_TreeKey key));
330
331EXTERN int Rp_TreeGetValue _ANSI_ARGS_((Rp_Tree tree,
332        // Rp_TreeNode node, CONST char *string, Tcl_Obj **valuePtr));
333        Rp_TreeNode node, CONST char *string, void **valuePtr));
334
335EXTERN int Rp_TreeValueExists _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
336        CONST char *string));
337
338EXTERN int Rp_TreeSetValue _ANSI_ARGS_((Rp_Tree tree,
339        // Rp_TreeNode node, CONST char *string, Tcl_Obj *valuePtr));
340        Rp_TreeNode node, CONST char *string, void *valuePtr));
341
342EXTERN int Rp_TreeUnsetValue _ANSI_ARGS_((Rp_Tree tree,
343        Rp_TreeNode node, CONST char *string));
344
345EXTERN int Rp_TreeGetArrayValue _ANSI_ARGS_((
346        Rp_Tree tree, Rp_TreeNode node, CONST char *arrayName,
347        // CONST char *elemName, Tcl_Obj **valueObjPtrPtr));
348        CONST char *elemName, void **valueObjPtrPtr));
349
350EXTERN int Rp_TreeSetArrayValue _ANSI_ARGS_((
351        Rp_Tree tree, Rp_TreeNode node, CONST char *arrayName,
352        //CONST char *elemName, Tcl_Obj *valueObjPtr));
353        CONST char *elemName, void *valueObjPtr));
354
355EXTERN int Rp_TreeUnsetArrayValue _ANSI_ARGS_((
356        Rp_Tree tree, Rp_TreeNode node, CONST char *arrayName,
357        CONST char *elemName));
358
359EXTERN int Rp_TreeArrayValueExists _ANSI_ARGS_((Rp_Tree tree,
360        Rp_TreeNode node, CONST char *arrayName, CONST char *elemName));
361
362EXTERN int Rp_TreeArrayNames _ANSI_ARGS_((Rp_Tree tree,
363        // Rp_TreeNode node, CONST char *arrayName, Tcl_Obj *listObjPtr));
364        Rp_TreeNode node, CONST char *arrayName, void *listObjPtr));
365
366EXTERN int Rp_TreeGetValueByKey _ANSI_ARGS_((
367        Rp_Tree tree, Rp_TreeNode node, Rp_TreeKey key,
368        // Tcl_Obj **valuePtr));
369        void **valuePtr));
370
371EXTERN int Rp_TreeSetValueByKey _ANSI_ARGS_((
372        // Rp_Tree tree, Rp_TreeNode node, Rp_TreeKey key, Tcl_Obj *valuePtr));
373        Rp_Tree tree, Rp_TreeNode node, Rp_TreeKey key, void *valuePtr));
374
375EXTERN int Rp_TreeUnsetValueByKey _ANSI_ARGS_((
376        Rp_Tree tree, Rp_TreeNode node, Rp_TreeKey key));
377
378EXTERN int Rp_TreeValueExistsByKey _ANSI_ARGS_((Rp_Tree tree,
379        Rp_TreeNode node, Rp_TreeKey key));
380
381EXTERN Rp_TreeKey Rp_TreeFirstKey _ANSI_ARGS_((Rp_Tree tree,
382        Rp_TreeNode node, Rp_TreeKeySearch *cursorPtr));
383
384EXTERN Rp_TreeKey Rp_TreeNextKey _ANSI_ARGS_((Rp_Tree tree,
385        Rp_TreeKeySearch *cursorPtr));
386
387EXTERN int Rp_TreeApply _ANSI_ARGS_((Rp_TreeNode root,
388        Rp_TreeApplyProc *proc, ClientData clientData));
389
390EXTERN int Rp_TreeApplyDFS _ANSI_ARGS_((Rp_TreeNode root,
391        Rp_TreeApplyProc *proc, ClientData clientData, int order));
392
393EXTERN int Rp_TreeApplyBFS _ANSI_ARGS_((Rp_TreeNode root,
394        Rp_TreeApplyProc *proc, ClientData clientData));
395
396EXTERN int Rp_TreeApplyXML _ANSI_ARGS_((Rp_TreeNode root,
397        Rp_TreeApplyProc *proc, ClientData clientData));
398
399EXTERN int Rp_TreeSortNode _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
400        Rp_TreeCompareNodesProc *proc));
401
402EXTERN int Rp_TreeCreate _ANSI_ARGS_((CONST char *name,
403        Rp_Tree *treePtr));
404
405// EXTERN int Rp_TreeExists _ANSI_ARGS_((CONST char *name));
406
407// EXTERN int Rp_TreeGetToken _ANSI_ARGS_((CONST char *name,
408//         Rp_Tree *treePtr));
409
410EXTERN int Rp_TreeGetTokenFromToken _ANSI_ARGS_((
411        CONST Rp_Tree tree, Rp_Tree *newToken));
412
413EXTERN void Rp_TreeReleaseToken _ANSI_ARGS_((Rp_Tree tree));
414
415EXTERN int Rp_TreeSize _ANSI_ARGS_((Rp_TreeNode node));
416
417EXTERN Rp_TreeTrace Rp_TreeCreateTrace _ANSI_ARGS_((Rp_Tree tree,
418        Rp_TreeNode node, CONST char *keyPattern, CONST char *tagName,
419        unsigned int mask, Rp_TreeTraceProc *proc, ClientData clientData));
420
421EXTERN void Rp_TreeDeleteTrace _ANSI_ARGS_((Rp_TreeTrace token));
422
423EXTERN void Rp_TreeCreateEventHandler _ANSI_ARGS_((Rp_Tree tree,
424        unsigned int mask, Rp_TreeNotifyEventProc *proc,
425        ClientData clientData));
426
427EXTERN void Rp_TreeDeleteEventHandler _ANSI_ARGS_((Rp_Tree tree,
428        unsigned int mask, Rp_TreeNotifyEventProc *proc,
429        ClientData clientData));
430
431EXTERN void Rp_TreeRelabelNode _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
432        CONST char *string));
433EXTERN void Rp_TreeRelabelNode2 _ANSI_ARGS_((Rp_TreeNode node,
434        CONST char *string));
435//EXTERN char *Rp_TreeNodePath _ANSI_ARGS_((Rp_TreeNode node,
436//        Tcl_DString *resultPtr));
437EXTERN int Rp_TreeNodePosition _ANSI_ARGS_((Rp_TreeNode node));
438
439EXTERN void Rp_TreeClearTags _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node));
440EXTERN int Rp_TreeHasTag _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
441        CONST char *tagName));
442EXTERN void Rp_TreeAddTag _ANSI_ARGS_((Rp_Tree tree, Rp_TreeNode node,
443        CONST char *tagName));
444EXTERN void Rp_TreeForgetTag _ANSI_ARGS_((Rp_Tree tree, CONST char *tagName));
445EXTERN Rp_HashTable *Rp_TreeTagHashTable _ANSI_ARGS_((Rp_Tree tree,
446        CONST char *tagName));
447EXTERN int Rp_TreeTagTableIsShared _ANSI_ARGS_((Rp_Tree tree));
448EXTERN int Rp_TreeShareTagTable _ANSI_ARGS_((Rp_Tree src, Rp_Tree target));
449EXTERN Rp_HashEntry *Rp_TreeFirstTag _ANSI_ARGS_((Rp_Tree tree,
450        Rp_HashSearch *searchPtr));
451
452#define Rp_TreeName(token)              ((token)->treeObject->name)
453#define Rp_TreeRootNode(token)          ((token)->root)
454#define Rp_TreeChangeRoot(token, node)  ((token)->root = (node))
455
456#define Rp_TreeNodeDepth(token, node)   ((node)->depth - (token)->root->depth)
457#define Rp_TreeNodeLabel(node)          ((node)->label)
458#define Rp_TreeNodeId(node)             ((node)->inode)
459#define Rp_TreeNodeParent(node)         ((node)->parent)
460#define Rp_TreeNodeDegree(node)         ((node)->nChildren)
461
462#define Rp_TreeIsLeaf(node)             ((node)->nChildren == 0)
463#define Rp_TreeNextNodeId(token)        ((token)->treeObject->nextInode)
464
465#define Rp_TreeFirstChild(node)         ((node)->first)
466#define Rp_TreeLastChild(node)          ((node)->last)
467#define Rp_TreeNextSibling(node)        (((node) == NULL) ? NULL : (node)->next)
468#define Rp_TreePrevSibling(node)        (((node) == NULL) ? NULL : (node)->prev)
469
470#endif /* _RP_TREE_H */
Note: See TracBrowser for help on using the repository browser.