blt-dev 2.4z-7ubuntu2 / usr / include / bltTree.h

/*
 * bltTree.h --
 *
 * Copyright 1998-1999 Lucent Technologies, Inc.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies or any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Lucent Technologies disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 *
 *	The "tree" data object was created by George A. Howlett.
 */

#ifndef _BLT_TREE_H
#define _BLT_TREE_H

#include <bltChain.h>
#include <bltHash.h>
#include <bltPool.h>

typedef struct Blt_TreeNodeStruct *Blt_TreeNode;
typedef struct Blt_TreeObjectStruct *Blt_TreeObject;
typedef struct Blt_TreeClientStruct *Blt_Tree;
typedef struct Blt_TreeTraceStruct *Blt_TreeTrace;
typedef struct Blt_TreeValueStruct *Blt_TreeValue;
typedef struct Blt_TreeTagEntryStruct Blt_TreeTagEntry;
typedef struct Blt_TreeTagTableStruct Blt_TreeTagTable;

typedef char *Blt_TreeKey;

#define TREE_PREORDER		(1<<0)
#define TREE_POSTORDER		(1<<1)
#define TREE_INORDER		(1<<2)
#define TREE_BREADTHFIRST	(1<<3)

#define TREE_TRACE_UNSET	(1<<3)
#define TREE_TRACE_WRITE	(1<<4)
#define TREE_TRACE_READ		(1<<5)
#define TREE_TRACE_CREATE	(1<<6)
#define TREE_TRACE_ALL		\
    (TREE_TRACE_UNSET | TREE_TRACE_WRITE | TREE_TRACE_READ | TREE_TRACE_CREATE)
#define TREE_TRACE_MASK		(TREE_TRACE_ALL)

#define TREE_TRACE_FOREIGN_ONLY	(1<<8)
#define TREE_TRACE_ACTIVE	(1<<9)

#define TREE_NOTIFY_CREATE	(1<<0)
#define TREE_NOTIFY_DELETE	(1<<1)
#define TREE_NOTIFY_MOVE	(1<<2)
#define TREE_NOTIFY_SORT	(1<<3)
#define TREE_NOTIFY_RELABEL	(1<<4)
#define TREE_NOTIFY_ALL		\
    (TREE_NOTIFY_CREATE | TREE_NOTIFY_DELETE | TREE_NOTIFY_MOVE | \
	TREE_NOTIFY_SORT | TREE_NOTIFY_RELABEL)
#define TREE_NOTIFY_MASK	(TREE_NOTIFY_ALL)

#define TREE_NOTIFY_WHENIDLE	 (1<<8)
#define TREE_NOTIFY_FOREIGN_ONLY (1<<9)
#define TREE_NOTIFY_ACTIVE	 (1<<10)

typedef struct {
    int type;
    Blt_Tree tree;
    int inode;			/* Node of event */
    Tcl_Interp *interp;
} Blt_TreeNotifyEvent;

typedef struct {
    Blt_TreeNode node;		/* Node being searched. */
    unsigned long nextIndex;	/* Index of next bucket to be
				 * enumerated after present one. */
    Blt_TreeValue nextValue;	/* Next entry to be enumerated in the
				 * the current bucket. */
} Blt_TreeKeySearch;

/*
 * Blt_TreeObject --
 *
 *	Structure providing the internal representation of the tree
 *	object.	A tree is uniquely identified by a combination of 
 *	its name and originating namespace.  Two trees in the same 
 *	interpreter can have the same names but reside in different 
 *	namespaces.
 *
 *	The tree object represents a general-ordered tree of nodes.
 *	Each node may contain a heterogeneous collection of data
 *	values. Each value is identified by a field name and nodes 
 *	do not need to contain the same data fields. Data field
 *	names are saved as reference counted strings and can be 
 *	shared among nodes.
 *
 *	The tree is threaded.  A node contains both a pointer to 
 *	back its parents and another to its siblings.  Therefore
 *	the tree maybe traversed non-recursively.
 * 
 *	A tree object can be shared by several clients.  When a
 *	client wants to use a tree object, it is given a token
 *	that represents the tree.  The tree object uses the tokens
 *	to keep track of its clients.  When all clients have 
 *	released their tokens the tree is automatically destroyed.
 */
struct Blt_TreeObjectStruct {
    Tcl_Interp *interp;		/* Interpreter associated with this tree. */

    char *name;

    Tcl_Namespace *nsPtr;

    Blt_HashEntry *hashPtr;	/* Pointer to this tree object in tree
				 * object hash table. */
    Blt_HashTable *tablePtr;

    Blt_TreeNode root;		/* Root of the entire tree. */

    char *sortNodesCmd;		/* Tcl command to invoke to sort entries */

    Blt_Chain *clients;		/* List of clients using this tree */

    Blt_Pool nodePool;
    Blt_Pool valuePool;

    Blt_HashTable nodeTable;	/* Table of node identifiers. Used to
				 * search for a node pointer given an inode.*/
    unsigned int nextInode;

    unsigned int nNodes;	/* Always counts root node. */

    unsigned int depth;		/* Maximum depth of the tree. */

    unsigned int flags;		/* Internal flags. See definitions
				 * below. */
    unsigned int notifyFlags;	/* Notification flags. See definitions
				 * below. */

};

/*
 * Blt_TreeNodeStruct --
 *
 *	Structure representing a node in a general ordered tree.
 *	Nodes are identified by their index, or inode.  Nodes also
 *	have names, but nodes names are not unique and can be 
 *	changed.  Inodes are valid even if the node is moved.
 *
 *	Each node can contain a list of data fields.  Fields are
 *	name-value pairs.  The values are represented by Tcl_Objs.
 *	
 */
struct Blt_TreeNodeStruct {
    Blt_TreeNode parent;	/* Parent node. If NULL, then this is
				   the root node. */
    Blt_TreeNode next;		/* Next sibling node. */
    Blt_TreeNode prev;		/* Previous sibling node. */
    Blt_TreeNode first;		/* First child node. */
    Blt_TreeNode last;		/* Last child node. */

    Blt_TreeKey label;		/* Node label (doesn't have to be
				 * unique). */

    Blt_TreeObject treeObject;

    Blt_TreeValue values;	/* Depending upon the number of values
				 * stored, this is either a chain or
				 * hash table of Blt_TreeValue
				 * structures.  (Note: if logSize is 
				 * 0, then this is a list).  Each
				 * value contains key/value data
				 * pair.  The data is a Tcl_Obj. */

    unsigned short nValues;	/* # of values for this node. */

    unsigned short logSize;	/* Size of hash table indicated as a
				 * power of 2 (e.g. if logSize=3, then
				 * table size is 8). If 0, this
				 * indicates that the node's values
				 * are stored as a list. */

    unsigned int nChildren;	/* # of children for this node. */
    unsigned int inode;		/* Serial number of the node. */

    unsigned short depth;	/* The depth of this node in the tree. */

    unsigned short flags;
};

struct Blt_TreeTagEntryStruct {
    char *tagName;
    Blt_HashEntry *hashPtr;
    Blt_HashTable nodeTable;
};

struct Blt_TreeTagTableStruct {
    Blt_HashTable tagTable;
    int refCount;
};

/*
 * Blt_TreeClientStruct --
 *
 *	A tree can be shared by several clients.  Each client allocates
 *	this structure which acts as a ticket for using the tree.  Clients
 *	can designate notifier routines that are automatically invoked
 *	by the tree object whenever the tree is changed is specific
 *	ways by other clients.
 */

struct Blt_TreeClientStruct {
    unsigned int magic;		/* Magic value indicating whether a
				 * generic pointer is really a tree
				 * token or not. */
    Blt_ChainLink *linkPtr;	/* Pointer into the server's chain of
				 * clients. */
    Blt_TreeObject treeObject;	/* Pointer to the structure containing
				 * the master information about the
				 * tree used by the client.  If NULL,
				 * this indicates that the tree has
				 * been destroyed (but as of yet, this
				 * client hasn't recognized it). */

    Blt_Chain *events;		/* Chain of node event handlers. */
    Blt_Chain *traces;		/* Chain of data field callbacks. */
    Blt_TreeNode root;		/* Designated root for this client */
    Blt_TreeTagTable *tagTablePtr;
};


typedef int (Blt_TreeNotifyEventProc) _ANSI_ARGS_((ClientData clientData, 
	Blt_TreeNotifyEvent *eventPtr));

typedef int (Blt_TreeTraceProc) _ANSI_ARGS_((ClientData clientData, 
	Tcl_Interp *interp, Blt_TreeNode node, Blt_TreeKey key, 
	unsigned int flags));

typedef int (Blt_TreeEnumProc) _ANSI_ARGS_((Blt_TreeNode node, Blt_TreeKey key,
	Tcl_Obj *valuePtr));

typedef int (Blt_TreeCompareNodesProc) _ANSI_ARGS_((Blt_TreeNode *n1Ptr, 
	Blt_TreeNode *n2Ptr));

typedef int (Blt_TreeApplyProc) _ANSI_ARGS_((Blt_TreeNode node, 
	ClientData clientData, int order));

struct Blt_TreeTraceStruct {
    ClientData clientData;
    Blt_TreeKey key;
    Blt_TreeNode node;
    unsigned int mask;
    Blt_TreeTraceProc *proc;
};

/*
 * Structure definition for information used to keep track of searches
 * through hash tables:p
 */
struct Blt_TreeKeySearchStruct {
    Blt_TreeNode node;		/* Table being searched. */
    unsigned long nextIndex;	/* Index of next bucket to be
				 * enumerated after present one. */
    Blt_TreeValue nextValue;	/* Next entry to be enumerated in the
				 * the current bucket. */
};

EXTERN Blt_TreeKey Blt_TreeGetKey _ANSI_ARGS_((CONST char *string));

EXTERN Blt_TreeNode Blt_TreeCreateNode _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode parent, CONST char *name, int position)); 
EXTERN Blt_TreeNode Blt_TreeCreateNodeWithId _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode parent, CONST char *name, int position, int inode)); 

EXTERN int Blt_TreeDeleteNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));

EXTERN int Blt_TreeMoveNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_TreeNode parent, Blt_TreeNode before));

EXTERN Blt_TreeNode Blt_TreeGetNode _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int inode));

EXTERN Blt_TreeNode Blt_TreeFindChild _ANSI_ARGS_((Blt_TreeNode parent, 
	CONST char *name));

EXTERN Blt_TreeNode Blt_TreeFirstChild _ANSI_ARGS_((Blt_TreeNode parent));

EXTERN Blt_TreeNode Blt_TreeNextSibling _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeLastChild _ANSI_ARGS_((Blt_TreeNode parent));

EXTERN Blt_TreeNode Blt_TreePrevSibling _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeNextNode _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreePrevNode _ANSI_ARGS_((Blt_TreeNode root,
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeChangeRoot _ANSI_ARGS_((Blt_Tree tree,
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeEndNode _ANSI_ARGS_((Blt_TreeNode node,
	unsigned int nodeFlags));

EXTERN int Blt_TreeIsBefore _ANSI_ARGS_((Blt_TreeNode node1, 
	Blt_TreeNode node2));

EXTERN int Blt_TreeIsAncestor _ANSI_ARGS_((Blt_TreeNode node1, 
	Blt_TreeNode node2));

EXTERN int Blt_TreePrivateValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
	Blt_TreeNode node, Blt_TreeKey key));

EXTERN int Blt_TreePublicValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree,
	Blt_TreeNode node, Blt_TreeKey key));

EXTERN int Blt_TreeGetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree, 
	Blt_TreeNode node, CONST char *string, Tcl_Obj **valuePtr));

EXTERN int Blt_TreeValueExists _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	CONST char *string));

EXTERN int Blt_TreeSetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree, 
	Blt_TreeNode node, CONST char *string, Tcl_Obj *valuePtr));

EXTERN int Blt_TreeUnsetValue _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree, 
	Blt_TreeNode node, CONST char *string));

EXTERN int Blt_TreeGetArrayValue _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName, 
	CONST char *elemName, Tcl_Obj **valueObjPtrPtr));

EXTERN int Blt_TreeSetArrayValue _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName, 
	CONST char *elemName, Tcl_Obj *valueObjPtr));

EXTERN int Blt_TreeUnsetArrayValue _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, CONST char *arrayName, 
	CONST char *elemName));

EXTERN int Blt_TreeArrayValueExists _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, CONST char *arrayName, CONST char *elemName));

EXTERN int Blt_TreeArrayNames _ANSI_ARGS_((Tcl_Interp *interp, Blt_Tree tree, 
	Blt_TreeNode node, CONST char *arrayName, Tcl_Obj *listObjPtr));

EXTERN int Blt_TreeGetValueByKey _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key, 
	Tcl_Obj **valuePtr));

EXTERN int Blt_TreeSetValueByKey _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key, Tcl_Obj *valuePtr));

EXTERN int Blt_TreeUnsetValueByKey _ANSI_ARGS_((Tcl_Interp *interp, 
	Blt_Tree tree, Blt_TreeNode node, Blt_TreeKey key));

EXTERN int Blt_TreeValueExistsByKey _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, Blt_TreeKey key));

EXTERN Blt_TreeKey Blt_TreeFirstKey _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, Blt_TreeKeySearch *cursorPtr));

EXTERN Blt_TreeKey Blt_TreeNextKey _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeKeySearch *cursorPtr));

EXTERN int Blt_TreeApply _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData));

EXTERN int Blt_TreeApplyDFS _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData, int order));

EXTERN int Blt_TreeApplyBFS _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData));

EXTERN int Blt_TreeSortNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_TreeCompareNodesProc *proc));

EXTERN int Blt_TreeCreate _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name,
	Blt_Tree *treePtr));

EXTERN int Blt_TreeExists _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name));

EXTERN int Blt_TreeGetToken _ANSI_ARGS_((Tcl_Interp *interp, CONST char *name, 
	Blt_Tree *treePtr));

EXTERN void Blt_TreeReleaseToken _ANSI_ARGS_((Blt_Tree tree));

EXTERN int Blt_TreeSize _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeTrace Blt_TreeCreateTrace _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, CONST char *keyPattern, CONST char *tagName,
	unsigned int mask, Blt_TreeTraceProc *proc, ClientData clientData));

EXTERN void Blt_TreeDeleteTrace _ANSI_ARGS_((Blt_TreeTrace token));

EXTERN void Blt_TreeCreateEventHandler _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int mask, Blt_TreeNotifyEventProc *proc, 
	ClientData clientData));

EXTERN void Blt_TreeDeleteEventHandler _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int mask, Blt_TreeNotifyEventProc *proc, 
	ClientData clientData));

EXTERN void Blt_TreeRelabelNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	CONST char *string));
EXTERN void Blt_TreeRelabelNode2 _ANSI_ARGS_((Blt_TreeNode node, 
	CONST char *string));
EXTERN char *Blt_TreeNodePath _ANSI_ARGS_((Blt_TreeNode node, 
	Tcl_DString *resultPtr));	
EXTERN int Blt_TreeNodePosition _ANSI_ARGS_((Blt_TreeNode node));

EXTERN void Blt_TreeClearTags _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));
EXTERN int Blt_TreeHasTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	CONST char *tagName));
EXTERN void Blt_TreeAddTag _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	CONST char *tagName));
EXTERN void Blt_TreeForgetTag _ANSI_ARGS_((Blt_Tree tree, CONST char *tagName));
EXTERN Blt_HashTable *Blt_TreeTagHashTable _ANSI_ARGS_((Blt_Tree tree, 
	CONST char *tagName));
EXTERN int Blt_TreeTagTableIsShared _ANSI_ARGS_((Blt_Tree tree));
EXTERN int Blt_TreeShareTagTable _ANSI_ARGS_((Blt_Tree src, Blt_Tree target));
EXTERN Blt_HashEntry *Blt_TreeFirstTag _ANSI_ARGS_((Blt_Tree tree, 
	Blt_HashSearch *searchPtr));

#define Blt_TreeName(token)	((token)->treeObject->name)
#define Blt_TreeRootNode(token)	((token)->root)
#define Blt_TreeChangeRoot(token, node) ((token)->root = (node))

#define Blt_TreeNodeDepth(token, node)	((node)->depth - (token)->root->depth)
#define Blt_TreeNodeLabel(node)	 ((node)->label)
#define Blt_TreeNodeId(node)	 ((node)->inode)
#define Blt_TreeNodeParent(node) ((node)->parent)
#define Blt_TreeNodeDegree(node) ((node)->nChildren)

#define Blt_TreeIsLeaf(node)     ((node)->nChildren == 0)
#define Blt_TreeNextNodeId(token)     ((token)->treeObject->nextInode)

#define Blt_TreeFirstChild(node) ((node)->first)
#define Blt_TreeLastChild(node) ((node)->last)
#define Blt_TreeNextSibling(node) (((node) == NULL) ? NULL : (node)->next)
#define Blt_TreePrevSibling(node) (((node) == NULL) ? NULL : (node)->prev)

#endif /* _BLT_TREE_H */