source: trunk/src/objects/RpTree.h @ 4356

Last change on this file since 4356 was 1560, checked in by dkearney, 15 years ago

updates to the object system, fixed up tree and xml parser objects, added some basic tests for them and adopted number object to accept xml text and configure itself from the parsed xml. added fermi3.cc example program which contains suggested interface from apps meeting.
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.