/*
 * bltTree.c --
 *
 * 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.
 */

#include "bltInt.h"

#ifndef NO_TREE

#include "bltChain.h"
#include "bltTree.h"

static Tcl_InterpDeleteProc TreeInterpDeleteProc;
static Blt_TreeApplyProc SizeApplyProc;
static Tcl_IdleProc NotifyIdleProc;

#define TREE_THREAD_KEY		"BLT Tree Data"
#define TREE_MAGIC		((unsigned int) 0x46170277)
#define TREE_DESTROYED		(1<<0)

typedef struct Blt_TreeNodeRec Node;
typedef struct Blt_TreeTokenRec ClientToken;
typedef struct Blt_TreeObjectRec TreeObject;

typedef struct {
    Tcl_HashTable treeTable;	/* Table of trees. */
    unsigned int nextId;
    Tcl_Interp *interp;
} TreeInterpData;


/*
 * Datum --
 *
 *	Tree nodes contain heterogeneous data fields, represented
 *	as a chain of these structures.  Each field contains the
 *	key of the field (Uid) and the value (Tcl_Obj) containing 
 *	the actual data representations.
 *
 */
typedef struct {
    Blt_Uid keyUid;		/* String identifying the data field */
    Tcl_Obj *objPtr;		/* Data representation. */
} Datum;

typedef struct {
    ClientData clientData;
    Blt_Uid keyUid;
    unsigned int mask;
    Blt_TreeNotifyEventProc *proc;
    Blt_TreeNotifyEvent event;
    int notifyPending;
} EventHandler;

typedef struct {
    ClientData clientData;
    char *keyPattern;
    Node *nodePtr;
    unsigned int mask;
    Blt_TreeTraceProc *proc;
    int isUid;
    ClientToken *tokenPtr;
    Blt_ChainLink *linkPtr;
} TraceHandler;


static TreeInterpData *
GetTreeInterpData(interp)
    Tcl_Interp *interp;
{
    TreeInterpData *dataPtr;
    Tcl_InterpDeleteProc *proc;

    dataPtr = (TreeInterpData *)
	Tcl_GetAssocData(interp, TREE_THREAD_KEY, &proc);
    if (dataPtr == NULL) {
	dataPtr = (TreeInterpData *)malloc(sizeof(TreeInterpData));
	assert(dataPtr);
	dataPtr->interp = interp;
	Tcl_SetAssocData(interp, TREE_THREAD_KEY, TreeInterpDeleteProc,
		 (ClientData)dataPtr);
	Tcl_InitHashTable(&(dataPtr->treeTable), TCL_STRING_KEYS);
    }
    return dataPtr;
}

static Node *
NewNode(treePtr, name)
    TreeObject *treePtr;
    char *name;
{
    Tcl_HashEntry *hPtr;
    Node *nodePtr;
    int isNew;
    int inode;

    /* Generate an unique serial number for this node.  */
    do {
	inode = treePtr->nextNode++;
	hPtr = Tcl_CreateHashEntry(&(treePtr->nodeTable),(char *)inode, 
		   &isNew);
    } while (!isNew);

    /* Create the node structure */
    nodePtr = (Node *) calloc(1, sizeof(Node));
    assert(nodePtr);
    nodePtr->inode = inode;
    if (name == NULL) {
	char string[200];

	sprintf(string, "node%d", inode);
	nodePtr->labelUid = Blt_GetUid(string);
    } else {
	nodePtr->labelUid = Blt_GetUid(name);
    }
    nodePtr->treePtr = treePtr;
    nodePtr->dataPtr = Blt_ChainCreate();
    Tcl_SetHashValue(hPtr, (ClientData)nodePtr);
    treePtr->nNodes++;
    return nodePtr;
}

static void
DeleteNode(nodePtr)
    Node *nodePtr;
{
    Tcl_HashEntry *hPtr;
    Blt_ChainLink *linkPtr;
    Datum *datumPtr;

    /*
     * Run through the list of data fields, deleting any entries
     * associated with this node.
     */
    for (linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	datumPtr = (Datum *) Blt_ChainGetValue(linkPtr);
	if (datumPtr->objPtr != NULL) {
	    Tcl_DecrRefCount(datumPtr->objPtr);
	}
	Blt_FreeUid(datumPtr->keyUid);
	free((char *)datumPtr);
    }
    Blt_ChainDestroy(nodePtr->dataPtr);

    /* Unlink the node from parent's list of siblings. */
    if (nodePtr->linkPtr != NULL) {
	Blt_ChainDeleteLink(nodePtr->parent->chainPtr, nodePtr->linkPtr);
    }
    nodePtr->treePtr->nNodes--;
    if (nodePtr->inode == (nodePtr->treePtr->nextNode - 1)) {
	nodePtr->treePtr->nextNode--;
    }
    hPtr = Tcl_FindHashEntry(&(nodePtr->treePtr->nodeTable), 
	     (char *)nodePtr->inode);
    assert(hPtr);
    Tcl_DeleteHashEntry(hPtr);
    Blt_FreeUid(nodePtr->labelUid);
    free((char *)nodePtr);
}

static TreeObject *
NewTreeObject(dataPtr, interp, treeName)
    TreeInterpData *dataPtr;
    Tcl_Interp *interp;
    char *treeName;
{
    TreeObject *treePtr;
    int isNew;

    treePtr = (TreeObject *)calloc(1, sizeof(TreeObject));
    if (treePtr == NULL) {
	Tcl_SetResult(interp, "can't allocate tree", TCL_STATIC);
	return NULL;
    }
    treePtr->interp = interp;
    treePtr->name = strdup(treeName);
    Tcl_InitHashTable(&(treePtr->nodeTable), TCL_ONE_WORD_KEYS);
    treePtr->depth = 1;
    treePtr->notifyFlags = 0;
    treePtr->root = NewNode(treePtr, treeName);
    treePtr->chainPtr = Blt_ChainCreate();
    treePtr->hashPtr = Tcl_CreateHashEntry(&(dataPtr->treeTable), treeName, 
	&isNew);
    Tcl_SetHashValue(treePtr->hashPtr, (char *)treePtr);
    return treePtr;
}

/*
 * ----------------------------------------------------------------------
 *
 * GetTreeObject --
 *
 *	Searches for the tree object associated by the name given.
 *
 * Results:
 *	Returns a pointer to the tree if found, otherwise NULL.
 *
 * ----------------------------------------------------------------------
 */
static TreeObject *
GetTreeObject(interp, name, flags)
    Tcl_Interp *interp;
    char *name;
    int flags;
{
    char *treeName;
    Tcl_DString dString;
    Tcl_Namespace *nsPtr;	/* Namespace associated with the tree object.
				 * If NULL, indicates to look in first the
				 * current namespace and then the global
				 * for the tree. */
    Tcl_HashEntry *hPtr;
    TreeInterpData *dataPtr;	/* Interpreter-specific data. */
    TreeObject *treePtr;

    treePtr = NULL;
    if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
	Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"", 
		(char *)NULL);
	return NULL;
    }
    dataPtr = GetTreeInterpData(interp);
    if (nsPtr != NULL) { 
	/* Search only in designated namespace. */
	name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
	hPtr = Tcl_FindHashEntry(&(dataPtr->treeTable), name);
	if (hPtr != NULL) {
	    treePtr = (TreeObject *)Tcl_GetHashValue(hPtr);
	}
    } else { 
	if (flags & NS_SEARCH_CURRENT) {
	    /* Look first in the current namespace. */
	    nsPtr = Tcl_GetCurrentNamespace(interp);
	    name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
	    hPtr = Tcl_FindHashEntry(&(dataPtr->treeTable), name);
	    if (hPtr != NULL) {
		treePtr = (TreeObject *)Tcl_GetHashValue(hPtr);
	    } 
	}
	if ((treePtr == NULL) && (flags & NS_SEARCH_GLOBAL)) {
	    nsPtr = Tcl_GetGlobalNamespace(interp);
	    name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
	    hPtr = Tcl_FindHashEntry(&(dataPtr->treeTable), name);
	    if (hPtr != NULL) {
		treePtr = (TreeObject *)Tcl_GetHashValue(hPtr);
	    }
	}
    }
    Tcl_DStringFree(&dString);
    return treePtr;
}

static void
ResetDepths(nodePtr, depth)
    Node *nodePtr;
    int depth;
{
    Blt_ChainLink *linkPtr;

    nodePtr->depth = depth;
    for (linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr); linkPtr != NULL; 
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	nodePtr = (Node *)Blt_ChainGetValue(linkPtr);
	ResetDepths(nodePtr, depth + 1);
    }
}

static void
TeardownTree(nodePtr)
    Node *nodePtr;
{
    Blt_ChainLink *linkPtr;

    if (nodePtr->chainPtr != NULL) {
	Blt_ChainLink *nextPtr;
	Node *childPtr;

	for (linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr); 
	     linkPtr != NULL; linkPtr = nextPtr) {
	    nextPtr = Blt_ChainNextLink(linkPtr);
	    childPtr = (Node *)Blt_ChainGetValue(linkPtr);
	    TeardownTree(childPtr);
	}
	Blt_ChainDestroy(nodePtr->chainPtr);
	nodePtr->chainPtr = NULL;
    }
    if (nodePtr->dataPtr != NULL) {
	Datum *datumPtr;
	/*
	 * Run through the list of data fields, decrementing the
	 * reference counts on all the Tcl objects associated with 
	 * this node.
	 */
	for (linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr);
	     linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	    datumPtr = (Datum *) Blt_ChainGetValue(linkPtr);
	    if (datumPtr->objPtr != NULL) {
		Tcl_DecrRefCount(datumPtr->objPtr);
	    }
	    Blt_FreeUid(datumPtr->keyUid);
	    free((char *)datumPtr);
	}
	Blt_ChainDestroy(nodePtr->dataPtr);
	nodePtr->dataPtr = NULL;
    }
    Blt_FreeUid(nodePtr->labelUid);
    free((char *)nodePtr);
}

static void
DestroyTreeObject(treePtr)
    TreeObject *treePtr;
{
    Blt_ChainLink *linkPtr;
    ClientToken *tokenPtr;

    treePtr->flags |= TREE_DESTROYED;
    treePtr->nNodes = 0;

    /* Remove the remaining clients. */
    for (linkPtr = Blt_ChainFirstLink(treePtr->chainPtr); linkPtr != NULL;
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	tokenPtr = (ClientToken *)Blt_ChainGetValue(linkPtr);
	Blt_ChainDestroy(tokenPtr->chainPtr);
	Blt_ChainDestroy(tokenPtr->tracePtr);
	free((char *)tokenPtr);
    }
    Blt_ChainDestroy(treePtr->chainPtr);

    TeardownTree(treePtr->root);

    Tcl_DeleteHashTable(&(treePtr->nodeTable));

    if (treePtr->hashPtr != NULL) {
	/* Remove the entry from the global tree table. */
	Tcl_DeleteHashEntry(treePtr->hashPtr); 
    }
    if (treePtr->name != NULL) {
	free(treePtr->name);
    }
    free((char *)treePtr);
}

/*
 * -----------------------------------------------------------------------
 *
 * TreeInterpDeleteProc --
 *
 *	This is called when the interpreter hosting the tree object
 *	is deleted from the interpreter.  
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Destroys all remaining trees.  In addition removes
 *	the hash table managing all vector names.
 *
 * ------------------------------------------------------------------------
 */
/* ARGSUSED */
static void
TreeInterpDeleteProc(clientData, interp)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
{
    TreeInterpData *dataPtr = (TreeInterpData *)clientData;
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    TreeObject *treePtr;
    
    for (hPtr = Tcl_FirstHashEntry(&(dataPtr->treeTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	treePtr = (TreeObject *)Tcl_GetHashValue(hPtr);
	treePtr->hashPtr = NULL;
	DestroyTreeObject(treePtr);
    }
    Tcl_DeleteHashTable(&(dataPtr->treeTable));
    Tcl_DeleteAssocData(interp, TREE_THREAD_KEY);
    free((char *)dataPtr);
}

static void
NotifyIdleProc(clientData)
    ClientData clientData;
{
    EventHandler *handlerPtr = (EventHandler *)clientData;
  
    handlerPtr->notifyPending = FALSE;
    handlerPtr->mask |= TREE_NOTIFY_ACTIVE;
    (*handlerPtr->proc) (handlerPtr->clientData, &(handlerPtr->event));
    handlerPtr->mask &= ~TREE_NOTIFY_ACTIVE;
}

static void
CheckEventHandlers(tokenPtr, clientPtr, eventPtr)
    ClientToken *tokenPtr, *clientPtr;
    Blt_TreeNotifyEvent *eventPtr;
{
    Blt_ChainLink *linkPtr, *nextPtr;
    EventHandler *handlerPtr;

    eventPtr->tree = clientPtr;
    for (linkPtr = Blt_ChainFirstLink(clientPtr->chainPtr); linkPtr != NULL; 
	 linkPtr = nextPtr) {
	nextPtr = Blt_ChainNextLink(linkPtr);
	handlerPtr = (EventHandler *)Blt_ChainGetValue(linkPtr);
	if ((handlerPtr->mask & TREE_NOTIFY_ACTIVE) ||
	    (handlerPtr->mask & eventPtr->type) == 0) {
	    continue;
	}
	if ((clientPtr == tokenPtr) && 
	    (handlerPtr->mask & TREE_NOTIFY_FOREIGN_ONLY)) {
	    continue;		/* Don't notify yourself. */
	}
	if (handlerPtr->mask & TREE_NOTIFY_WHENIDLE) {
	    if (!handlerPtr->notifyPending) {
		handlerPtr->notifyPending = TRUE;
		handlerPtr->event = *eventPtr;
		Tcl_DoWhenIdle(NotifyIdleProc, (ClientData)handlerPtr);
	    }
	} else {
	    handlerPtr->mask |= TREE_NOTIFY_ACTIVE;
	    (*handlerPtr->proc) (handlerPtr->clientData, eventPtr);
	    handlerPtr->mask &= ~TREE_NOTIFY_ACTIVE;
	}
    }
}

static void
NotifyClients(tokenPtr, treePtr, nodePtr, eventFlag)
    ClientToken *tokenPtr;
    TreeObject *treePtr;
    Node *nodePtr;
    int eventFlag;
{
    Blt_ChainLink *linkPtr;
    ClientToken *clientPtr;
    Blt_TreeNotifyEvent event;

    event.type = eventFlag;
    event.inode = nodePtr->inode;

    /* 
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    for (linkPtr = Blt_ChainFirstLink(treePtr->chainPtr);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	clientPtr = (ClientToken *)Blt_ChainGetValue(linkPtr);
	CheckEventHandlers(tokenPtr, clientPtr, &event);
    }
}


/* Public Routines */

Blt_TreeNode
Blt_TreeCreateNode(tokenPtr, parentPtr, name, pos)
    ClientToken *tokenPtr;
    Node *parentPtr;		/* Parent node where the new node will
				 * be inserted. */
    char *name;			/* Name of node. */
    int pos;			/* Position in the parent's list of children
				 * where to insert the new node. */
{
    TreeObject *treePtr = parentPtr->treePtr;
    Node *nodePtr;	/* Node to be inserted. */
    Blt_ChainLink *linkPtr;

    if (parentPtr->chainPtr == NULL) {
	/* 
	 * Create chains to hold children only as necessary.  We don't
	 * want to allocate extra storage for leaves (that have no
	 * children) when there can be many.  
	 */
	parentPtr->chainPtr = Blt_ChainCreate();
    }
    linkPtr = Blt_ChainNewLink();
    nodePtr = NewNode(treePtr, name);
    Blt_ChainSetValue(linkPtr, (ClientData)nodePtr);

    if ((pos == -1) || (pos >= Blt_ChainGetLength(parentPtr->chainPtr))) {
	Blt_ChainAppendLink(parentPtr->chainPtr, linkPtr);
    } else {
	Blt_ChainLink *beforePtr;

	beforePtr = Blt_ChainGetNthLink(parentPtr->chainPtr, pos);
	Blt_ChainLinkBefore(parentPtr->chainPtr, linkPtr, beforePtr);
    }
    nodePtr->depth = parentPtr->depth + 1;
    nodePtr->parent = parentPtr;
    nodePtr->linkPtr = linkPtr;

    /* 
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    NotifyClients(tokenPtr, treePtr, nodePtr, TREE_NOTIFY_CREATE);
    return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeMoveNode --
 *
 *	Move an entry into a new location in the hierarchy.
 *
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
int
Blt_TreeMoveNode(tokenPtr, nodePtr, parentPtr, beforePtr)
    ClientToken *tokenPtr;
    Node *nodePtr, *parentPtr, *beforePtr;
{
    TreeObject *treePtr = nodePtr->treePtr;
    int depth;
    
    if (nodePtr == beforePtr) {
	return TCL_ERROR;
    }
    if ((beforePtr != NULL) && (beforePtr->parent != parentPtr)) {
	return TCL_ERROR;
    }
    if (nodePtr->parent == NULL) {
	return TCL_ERROR;	/* Can't move root. */
    }
    /* Verify that the node isn't an ancestor of the new parent. */
    if (Blt_TreeIsAncestor(nodePtr, parentPtr)) {
	return TCL_ERROR;
    }
    Blt_ChainUnlinkLink(nodePtr->parent->chainPtr, nodePtr->linkPtr);
    if (parentPtr->chainPtr == NULL) {
	parentPtr->chainPtr = Blt_ChainCreate();
    }
    /* 
     * Relink the node as a child of the new parent.
     */
    if (beforePtr == NULL) {
	Blt_ChainLinkAfter(parentPtr->chainPtr, nodePtr->linkPtr, NULL);
    } else {
	Blt_ChainLinkBefore(parentPtr->chainPtr, nodePtr->linkPtr, 
		beforePtr->linkPtr);
    }
    nodePtr->parent = parentPtr;
    depth = parentPtr->depth + 1;
    if (nodePtr->depth != depth) {
	/* Descend the branch resetting the depths. */
	ResetDepths(nodePtr, depth);
    }
    /* 
     * Issue callbacks to each client indicating that a node has
     * been moved.
     */
    NotifyClients(tokenPtr, treePtr, nodePtr, TREE_NOTIFY_MOVE);
    return TCL_OK;
}

int
Blt_TreeDeleteNode(tokenPtr, nodePtr)
    ClientToken *tokenPtr;
    Node *nodePtr;
{
    TreeObject *treePtr = nodePtr->treePtr;
    Blt_ChainLink *linkPtr, *nextPtr;

    if (nodePtr->chainPtr != NULL) {
	Node *childPtr;

	/* In depth-first order, delete each descendant node. */
	for (linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr); 
	     linkPtr != NULL; linkPtr = nextPtr) {
	    nextPtr = Blt_ChainNextLink(linkPtr);
	    childPtr = (Node *)Blt_ChainGetValue(linkPtr);
	    childPtr->linkPtr = NULL; 
	    Blt_TreeDeleteNode(tokenPtr, childPtr);
	}
	Blt_ChainDestroy(nodePtr->chainPtr);
	nodePtr->chainPtr = NULL;
    }

    /* 
     * Issue callbacks to each client indicating that the node can
     * no longer be used.  
     */
    NotifyClients(tokenPtr, treePtr, nodePtr, TREE_NOTIFY_DELETE);

    /* Now remove the actual node. */
    DeleteNode(nodePtr);
    return TCL_OK;
}

Blt_TreeNode
Blt_TreeGetNode(tokenPtr, inode)
    ClientToken *tokenPtr;
    unsigned int inode;
{
    TreeObject *treePtr = tokenPtr->tree;
    Tcl_HashEntry *hPtr;

    hPtr = Tcl_FindHashEntry(&(treePtr->nodeTable), (char *)inode);
    if (hPtr != NULL) {
	return (Blt_TreeNode)Tcl_GetHashValue(hPtr);
    }
    return NULL;
}

Blt_TreeTrace
Blt_TreeCreateTrace(tokenPtr, nodePtr, keyPattern, mask, proc, clientData)
    ClientToken *tokenPtr;
    Node *nodePtr;
    char *keyPattern;
    unsigned int mask;
    Blt_TreeTraceProc *proc;
    ClientData clientData;
{
    TraceHandler *handlerPtr;

    handlerPtr = (TraceHandler *)malloc(sizeof (TraceHandler));
    assert(handlerPtr);
    handlerPtr->linkPtr = Blt_ChainAppend(tokenPtr->tracePtr, 
		(ClientData)handlerPtr);
    handlerPtr->keyPattern = strdup(keyPattern);
    handlerPtr->tokenPtr = tokenPtr;
    handlerPtr->proc = proc;
    handlerPtr->clientData = clientData;
    handlerPtr->mask = mask;
    handlerPtr->nodePtr = nodePtr;
    return (Blt_TreeTrace)handlerPtr;
}

void
Blt_TreeDeleteTrace(trace) 
    Blt_TreeTrace trace;
{
    TraceHandler *handlerPtr = (TraceHandler *)trace;

    Blt_ChainDeleteLink(handlerPtr->tokenPtr->tracePtr, handlerPtr->linkPtr);
    if (handlerPtr->keyPattern != NULL) {
	free(handlerPtr->keyPattern);
    }
    free((char *)handlerPtr);
}

void
Blt_TreeRelabelNode(tokenPtr, nodePtr, string)
    ClientToken *tokenPtr;
    Node *nodePtr;
    char *string;
{
    Blt_Uid labelUid;
    
    labelUid = Blt_GetUid(string);
    if (nodePtr->labelUid != NULL) {
	Blt_FreeUid(nodePtr->labelUid);
    }
    nodePtr->labelUid = labelUid;
    /* 
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    NotifyClients(tokenPtr, tokenPtr->tree, nodePtr, TREE_NOTIFY_RELABEL);
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeFindChild --
 *
 *	Searches for the named node in a parent's chain of siblings.  
 *
 *
 * Results:
 *	If found, the child node is returned, otherwise NULL.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreeFindChild(parentPtr, name)
    Node *parentPtr;
    char *name;
{
    Blt_Uid labelUid;
    
    labelUid = Blt_FindUid(name);
    if (labelUid != NULL) {
	Node *nodePtr;
	register Blt_ChainLink *linkPtr;

	for (linkPtr = Blt_ChainFirstLink(parentPtr->chainPtr); 
	     linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	    nodePtr = (Node *) Blt_ChainGetValue(linkPtr);
	    if (labelUid == nodePtr->labelUid) {
		return nodePtr;
	    }
	}
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreePrevNode --
 *
 *	Returns the "previous" node in the tree.  This node (in 
 *	depth-first order) is its parent, if the node has no siblings
 *	that are previous to it.  Otherwise it is the last descendant 
 *	of the last sibling.  In this case, descend the sibling's
 *	hierarchy, using the last child at any ancestor, with we
 *	we find a leaf.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreePrevNode(rootPtr, nodePtr)
    Node *rootPtr, *nodePtr;
{
    Blt_ChainLink *linkPtr;

    if (nodePtr == rootPtr) {
	return NULL;		/* The root is the first node. */
    }
    linkPtr = Blt_ChainPrevLink(nodePtr->linkPtr);
    if (linkPtr == NULL) {
	/* There are no siblings previous to this one, so pick the parent. */
	return nodePtr->parent;
    }
    /*
     * Traverse down the right-most thread, in order to select the
     * next entry.  Stop if we find a "closed" entry or reach a leaf.
     */
    nodePtr = (Node *)Blt_ChainGetValue(linkPtr);
    while ((linkPtr = Blt_ChainLastLink(nodePtr->chainPtr)) != NULL) {
	nodePtr = (Node *)Blt_ChainGetValue(linkPtr);
    }
    return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeNextNode --
 *
 *	Returns the "next" node in relation to the given node.  
 *	The next node (in depth-first order) is either the first 
 *	child of the given node the next sibling if the node has
 *	no children (the node is a leaf).  If the given node is the 
 *	last sibling, then try it's parent next sibling.  Continue
 *	until we either find a next sibling for some ancestor or 
 *	we reach the root node.  In this case the current node is 
 *	the last node in the tree.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreeNextNode(rootPtr, nodePtr)
    Node *rootPtr, *nodePtr;
{
    Blt_ChainLink *linkPtr;

    /* Pick the first sub-node. */
    linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr);
    if (linkPtr != NULL) {
	return (Blt_TreeNode)Blt_ChainGetValue(linkPtr);
    }
    /* 
     * Back up until we can find a level where we can pick a 
     * "next sibling".  For the last entry we'll thread our 
     * way back to the root.  
     */
    while (nodePtr != rootPtr) {
	linkPtr = Blt_ChainNextLink(nodePtr->linkPtr);
	if (linkPtr != NULL) {
	    return (Blt_TreeNode)Blt_ChainGetValue(linkPtr);
	}
	nodePtr = nodePtr->parent;
    }
    return NULL;		/* At root, no next node. */
}


int
Blt_TreeIsBefore(n1Ptr, n2Ptr)
    Node *n1Ptr, *n2Ptr;
{
    int depth;
    register int i;
    Blt_ChainLink *linkPtr;
    Node *nodePtr;

    if (n1Ptr == n2Ptr) {
	return FALSE;
    }
    depth = MIN(n1Ptr->depth, n2Ptr->depth);
    if (depth == 0) {		/* One of the nodes is root. */
	return (n1Ptr->parent == NULL);
    }
    /* 
     * Traverse back from the deepest node, until the both nodes are
     * at the same depth.  Check if the ancestor node found is the
     * other node.  
     */
    for (i = n1Ptr->depth; i > depth; i--) {
	n1Ptr = n1Ptr->parent;
    }
    if (n1Ptr == n2Ptr) {
	return FALSE;
    }
    for (i = n2Ptr->depth; i > depth; i--) {
	n2Ptr = n2Ptr->parent;
    }
    if (n2Ptr == n1Ptr) {
	return TRUE;
    }

    /* 
     * First find the mutual ancestor of both nodes.  Look at each
     * preceding ancestor level-by-level for both nodes.  Eventually
     * we'll find a node that's the parent of both ancestors.  Then
     * find the first ancestor in the parent's list of subnodes.  
     */
    for (i = depth; i > 0; i--) {
	if (n1Ptr->parent == n2Ptr->parent) {
	    break;
	}
	n1Ptr = n1Ptr->parent;
	n2Ptr = n2Ptr->parent;
    }
    for (linkPtr = Blt_ChainFirstLink(n1Ptr->parent->chainPtr); 
	 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	nodePtr = (Node *)Blt_ChainGetValue(linkPtr);
	if (nodePtr == n1Ptr) {
	    return TRUE;
	} else if (nodePtr == n2Ptr) {
	    return FALSE;
	}
    }
    assert(linkPtr != NULL);
    return FALSE;
}

static void
CallTraces(tokenPtr, treePtr, nodePtr, keyUid, flags)
    ClientToken *tokenPtr;	/* Client holding a reference to the
				 * tree.  If NULL, indicates that all
				 * handlers, including those of the
				 * caller are to be executed. */
    TreeObject *treePtr;	/* Tree that was changed.  Can't use
				 * tokenPtr, because it can be
				 * NULL. */
    Node *nodePtr;
    Blt_Uid keyUid;
    unsigned int flags;
{
    Blt_ChainLink *linkPtr;
    ClientToken *clientPtr;
    Blt_ChainLink *link2Ptr;
    TraceHandler *handlerPtr;	

    for(linkPtr = Blt_ChainFirstLink(treePtr->chainPtr); 
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	clientPtr = (ClientToken *)Blt_ChainGetValue(linkPtr);
	for(link2Ptr = Blt_ChainFirstLink(clientPtr->tracePtr); 
	    link2Ptr != NULL; link2Ptr = Blt_ChainNextLink(link2Ptr)) {
	    handlerPtr = (TraceHandler *)Blt_ChainGetValue(link2Ptr);
	    if (!Tcl_StringMatch(keyUid, handlerPtr->keyPattern)) {
		continue;
	    }
	    if ((clientPtr == tokenPtr) && 
		(handlerPtr->mask & TREE_TRACE_FOREIGN_ONLY)) {
		continue;
	    }
	    if (((handlerPtr->nodePtr == NULL) || 
		 (handlerPtr->nodePtr == nodePtr)) && 
		(handlerPtr->mask & flags)) {
		if ((*handlerPtr->proc) (handlerPtr->clientData, 
			 treePtr->interp, nodePtr, keyUid, flags) != TCL_OK) {
		    Tcl_BackgroundError(treePtr->interp);
		}
	    }
	}
    }
}

int
Blt_TreeGetValueByUid(tokenPtr, nodePtr, keyUid, objPtrPtr)
    ClientToken *tokenPtr;
    Node *nodePtr;
    Blt_Uid keyUid;
    Tcl_Obj **objPtrPtr;
{
    register Blt_ChainLink *linkPtr;
    register Datum *datumPtr;
    TreeObject *treePtr = nodePtr->treePtr;

    for (linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	datumPtr = (Datum *)Blt_ChainGetValue(linkPtr);
	if (datumPtr->keyUid == keyUid) {
	    *objPtrPtr = datumPtr->objPtr;
	    break;
	}
    }
    if (linkPtr != NULL) {
	if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	    CallTraces(tokenPtr, treePtr, nodePtr, keyUid, TREE_TRACE_READ);
	}
	return TCL_OK;
    }
    return TCL_ERROR;
}

int
Blt_TreeSetValueByUid(tokenPtr, nodePtr, keyUid, objPtr)
    ClientToken *tokenPtr;
    Node *nodePtr;		/* Node to be updated. */
    Blt_Uid keyUid;		/* Identifies the field key. */
    Tcl_Obj *objPtr;		/* New value of field. If NULL, field
				 * is deleted. */
{
    TreeObject *treePtr = nodePtr->treePtr;
    register Blt_ChainLink *linkPtr;
    Datum *datumPtr;
    int flags;

    datumPtr = NULL;		/* Suppress compiler warning. */
    linkPtr = NULL;
    /* See if a data field by the given name exists. */
    for (linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	datumPtr = (Datum *)Blt_ChainGetValue(linkPtr);
	if (datumPtr->keyUid == keyUid) {
	    break;
	}
    }
    flags = 0;
    if (objPtr == NULL) {	/* NULL Tcl_Obj: Delete field. */
	if (linkPtr != NULL) {
	    Blt_ChainDeleteLink(nodePtr->dataPtr, linkPtr);
	    flags |= TREE_TRACE_UNSET;
	}
    } else {
	if (linkPtr == NULL) {
	    /* Create a new one and append it to the node's chain. */
	    datumPtr = (Datum *)malloc(sizeof(Datum));
	    datumPtr->keyUid = Blt_GetUid(keyUid);
	    Tcl_IncrRefCount(objPtr);
	    Blt_ChainAppend(nodePtr->dataPtr, (ClientData)datumPtr); 
	    flags |= TREE_TRACE_CREATE;
	} else {
	    Tcl_IncrRefCount(objPtr);
	    Tcl_DecrRefCount(datumPtr->objPtr);
	}
	datumPtr->objPtr = objPtr;
	flags |= TREE_TRACE_WRITE;
    }
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	CallTraces(tokenPtr, treePtr, nodePtr, datumPtr->keyUid, flags);
    }
    if ((linkPtr != NULL) && (objPtr == NULL)) {
	Tcl_DecrRefCount(datumPtr->objPtr);
	Blt_FreeUid(datumPtr->keyUid);
	free((char *)datumPtr);
    }
    return TCL_OK;
}

int
Blt_TreeUnsetValueByUid(tokenPtr, nodePtr, keyUid)
    ClientToken *tokenPtr;
    Node *nodePtr;		/* Node to be updated. */
    Blt_Uid keyUid;		/* Name of field in node. */
{
    TreeObject *treePtr = nodePtr->treePtr;
    register Blt_ChainLink *linkPtr;
    Datum *datumPtr;

    datumPtr = NULL;		/* Suppress compiler warning. */
    for (linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	datumPtr = (Datum *)Blt_ChainGetValue(linkPtr);
	if (datumPtr->keyUid == keyUid) {
	    break;
	}
    }
    if (linkPtr == NULL) {
	return TCL_OK;		/* No value was already set. */
    }
    Blt_ChainDeleteLink(nodePtr->dataPtr, linkPtr);
    CallTraces(tokenPtr, treePtr, nodePtr, keyUid, TREE_TRACE_UNSET);
    Tcl_DecrRefCount(datumPtr->objPtr);
    Blt_FreeUid(datumPtr->keyUid);
    free((char *)datumPtr);
    return TCL_OK;
}

int
Blt_TreeGetValue(tokenPtr, nodePtr, key, objPtrPtr)
    ClientToken *tokenPtr;
    Node *nodePtr;
    char *key;			/* String identifying the field in node. */
    Tcl_Obj **objPtrPtr;
{
    Blt_Uid keyUid;
    int result;

    keyUid = Blt_GetUid(key);
    result = Blt_TreeGetValueByUid(tokenPtr, nodePtr, keyUid, objPtrPtr);
    Blt_FreeUid(keyUid);
    return result;
}

int
Blt_TreeSetValue(tokenPtr, nodePtr, key, objPtr)
    ClientToken *tokenPtr;
    Node *nodePtr;		/* Node to be updated. */
    char *key;			/* String identifying the field in node. */
    Tcl_Obj *objPtr;		/* New value of field. If NULL, field
				 * is deleted. */
{
    Blt_Uid keyUid;
    int result;

    keyUid = Blt_GetUid(key);
    result = Blt_TreeSetValueByUid(tokenPtr, nodePtr, keyUid, objPtr);
    Blt_FreeUid(keyUid);
    return result;
}

int
Blt_TreeUnsetValue(tokenPtr, nodePtr, key)
    ClientToken *tokenPtr;
    Node *nodePtr;		/* Node to be updated. */
    char *key;			/* String identifying the field in node. */
{
    Blt_Uid keyUid;
    int result;

    keyUid = Blt_GetUid(key);
    result = Blt_TreeUnsetValueByUid(tokenPtr, nodePtr, keyUid);
    Blt_FreeUid(keyUid);
    return result;
}

Blt_Uid
Blt_TreeFirstKey(nodePtr, cursorPtr)
    Node *nodePtr;
    Blt_TreeCursor *cursorPtr;
{
    register Blt_ChainLink *linkPtr;
    Datum *datumPtr;

    linkPtr = Blt_ChainFirstLink(nodePtr->dataPtr);
    if (linkPtr == NULL) {
	return NULL;
    }
    *cursorPtr = (Blt_TreeCursor)Blt_ChainNextLink(linkPtr);
    datumPtr = (Datum *)Blt_ChainGetValue(linkPtr);
    return datumPtr->keyUid;
}

Blt_Uid
Blt_TreeNextKey(cursorPtr)
    Blt_TreeCursor *cursorPtr;
{
    Blt_ChainLink *linkPtr = (Blt_ChainLink *)(*cursorPtr);
    Datum *datumPtr;

    if (linkPtr == NULL) {
	return NULL;
    }
    datumPtr = (Datum *)Blt_ChainGetValue(linkPtr);
    linkPtr = Blt_ChainNextLink(linkPtr);
    *cursorPtr = (Blt_TreeCursor)linkPtr;
    return datumPtr->keyUid;
}


Blt_TreeNode
Blt_TreeFirstChild(parentPtr)
    Node *parentPtr;
{
    if (parentPtr->chainPtr != NULL) {
	Blt_ChainLink *linkPtr;

	linkPtr = Blt_ChainFirstLink(parentPtr->chainPtr);
	if (linkPtr != NULL) {
	    return (Blt_TreeNode)Blt_ChainGetValue(linkPtr);
	}
    }
    return NULL;
}

Blt_TreeNode
Blt_TreeNextSibling(nodePtr)
    Node *nodePtr;
{
    if (nodePtr->linkPtr != NULL) {
	Blt_ChainLink *linkPtr;

	linkPtr = Blt_ChainNextLink(nodePtr->linkPtr);
	if (linkPtr != NULL) {
	    return (Blt_TreeNode)Blt_ChainGetValue(linkPtr);
	}
    }
    return NULL;
}

Blt_TreeNode
Blt_TreeLastChild(parentPtr)
    Node *parentPtr;
{
    if (parentPtr->chainPtr != NULL) {
	Blt_ChainLink *linkPtr;

	linkPtr = Blt_ChainLastLink(parentPtr->chainPtr);
	if (linkPtr != NULL) {
	    return (Blt_TreeNode) Blt_ChainGetValue(linkPtr);
	}
    }
    return NULL;
}

Blt_TreeNode
Blt_TreePrevSibling(nodePtr)
    Node *nodePtr;
{
    Blt_ChainLink *linkPtr;

    linkPtr = Blt_ChainPrevLink(nodePtr->linkPtr);
    if (linkPtr != NULL) {
	return (Blt_TreeNode)Blt_ChainGetValue(linkPtr);
    }
    return NULL;
}

int
Blt_TreeIsAncestor(n1Ptr, n2Ptr)
    Node *n1Ptr, *n2Ptr;
{
    if (n2Ptr != NULL) {
	n2Ptr = n2Ptr->parent;
	while (n2Ptr != NULL) {
	    if (n2Ptr == n1Ptr) {
		return TRUE;
	    }
	    n2Ptr = n2Ptr->parent;
	}
    }
    return FALSE;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeSortNode --
 *
 *	Sorts the subnodes at a given node.
 *
 * Results:
 *	Always returns TCL_OK.
 *
 *----------------------------------------------------------------------
 */
int
Blt_TreeSortNode(tokenPtr, rootPtr, proc)
    ClientToken *tokenPtr;
    Node *rootPtr;
    Blt_TreeCompareNodesProc *proc;
{
    Node **nodeArr;
    Node *nodePtr;
    Blt_ChainLink *linkPtr;
    int nNodes;
    register Node **p;

    nNodes = Blt_ChainGetLength(rootPtr->chainPtr);
    if (nNodes < 2) {
	return TCL_OK;
    }
    nodeArr = (Node **)malloc(nNodes * sizeof(Node *));
    if (nodeArr == NULL) {
	return TCL_ERROR;	/* Out of memory. */
    }
    for (p = nodeArr, linkPtr = Blt_ChainFirstLink(rootPtr->chainPtr); 
	 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr), p++) {
	*p = (Node *)Blt_ChainGetValue(linkPtr);
    }
    qsort((char *)nodeArr, nNodes, sizeof(Node *), (QSortCompareProc *)proc);
    for (p = nodeArr, linkPtr = Blt_ChainFirstLink(rootPtr->chainPtr); 
	 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr), p++) {
	nodePtr = *p;
	Blt_ChainSetValue(linkPtr, (ClientData)nodePtr);
	nodePtr->linkPtr = linkPtr;
    }
    free((char *)nodeArr);
    NotifyClients(tokenPtr, rootPtr->treePtr, rootPtr, TREE_NOTIFY_SORT);
    return TCL_OK;
}

#define TEST_RESULT(result) \
	switch (result) { \
	case TCL_CONTINUE: \
	    return TCL_OK; \
	case TCL_OK: \
	    break; \
	default: \
	    return (result); \
	}

int
Blt_TreeApply(nodePtr, proc, clientData)
    Node *nodePtr;		/* Root node of subtree. */
    Blt_TreeApplyProc *proc;	/* Procedure to call for each node. */
    ClientData clientData;	/* One-word of data passed when calling
				 * proc. */
{
    Blt_ChainLink *linkPtr, *nextPtr;
    Node *childPtr;
    int result;

    nextPtr = NULL;
    for (linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr); linkPtr != NULL; 
	linkPtr = nextPtr) {
	/* 
	 * Get the next link in the chain before calling
	 * Blt_TreeApply recursively.  This is because the 
	 * apply callback may delete the node and its link.  
	 */
	nextPtr = Blt_ChainNextLink(linkPtr);
	childPtr = (Node *)Blt_ChainGetValue(linkPtr);
	result = Blt_TreeApply(childPtr, proc, clientData);
	TEST_RESULT(result);
    }
    return (*proc) (nodePtr, clientData, TREE_POSTORDER);
}

int
Blt_TreeApplyDFS(nodePtr, proc, clientData, order)
    Node *nodePtr;		/* Root node of subtree. */
    Blt_TreeApplyProc *proc;	/* Procedure to call for each node. */
    ClientData clientData;	/* One-word of data passed when calling
				 * proc. */
    int order;			/* Order of traversal. */
{
    Blt_ChainLink *linkPtr, *nextPtr;
    Node *childPtr;
    int result;

    if (order & TREE_PREORDER) {
	result = (*proc) (nodePtr, clientData, TREE_PREORDER);
	TEST_RESULT(result);
    }
    linkPtr = Blt_ChainFirstLink(nodePtr->chainPtr);
    if (order & TREE_INORDER) {
	if (linkPtr != NULL) {
	    childPtr = (Node *)Blt_ChainGetValue(linkPtr);
	    result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
	    TEST_RESULT(result);
	    linkPtr = Blt_ChainNextLink(linkPtr);
	}
	result = (*proc) (nodePtr, clientData, TREE_INORDER);
	TEST_RESULT(result);
    }
    nextPtr = NULL;
    for (/* empty */; linkPtr != NULL; linkPtr = nextPtr) {
	/* 
	 * Get the next link in the chain before calling
	 * Blt_TreeApply recursively.  This is because the 
	 * apply callback may delete the node and its link.  
	 */
	nextPtr = Blt_ChainNextLink(linkPtr);
	childPtr = (Node *)Blt_ChainGetValue(linkPtr);
	result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
	TEST_RESULT(result);
    }
    if (order & TREE_POSTORDER) {
	return (*proc) (nodePtr, clientData, TREE_POSTORDER);
    }
    return TCL_OK;
}

int
Blt_TreeApplyBFS(nodePtr, proc, clientData)
    Node *nodePtr;		/* Root node of subtree. */
    Blt_TreeApplyProc *proc;	/* Procedure to call for each node. */
    ClientData clientData;	/* One-word of data passed when calling
				 * proc. */
{
    Blt_ChainLink *l1Ptr, *l2Ptr, *nextPtr;
    Blt_Chain *queuePtr;
    int result;
    Node *childPtr;

    queuePtr = Blt_ChainCreate();
    l1Ptr = Blt_ChainAppend(queuePtr, nodePtr);
    while (l1Ptr != NULL) {
	nodePtr = (Node *)Blt_ChainGetValue(l1Ptr);
	/* Add the children to the queue. */
	for (l2Ptr = Blt_ChainFirstLink(nodePtr->chainPtr); l2Ptr != NULL;
	     l2Ptr = Blt_ChainNextLink(l2Ptr)) {
	    childPtr = (Node *)Blt_ChainGetValue(l2Ptr);
	    Blt_ChainAppend(queuePtr, childPtr);
	}
	/* Process the node. */
	result = (*proc) (nodePtr, clientData, TREE_BREADTHFIRST);
	switch (result) { 
	case TCL_CONTINUE: 
	    Blt_ChainDestroy(queuePtr);
	    return TCL_OK; 
	case TCL_OK: 
	    break; 
	default: 
	    Blt_ChainDestroy(queuePtr);
	    return result; 
	}
	/* Remove the node from the queue. */
	nextPtr = Blt_ChainNextLink(l1Ptr);
	Blt_ChainDeleteLink(queuePtr, l1Ptr);
	l1Ptr = nextPtr;
    }
    Blt_ChainDestroy(queuePtr);
    return TCL_OK;
}


int
Blt_TreeCreate(interp, name)
    Tcl_Interp *interp;		/* Interpreter to report errors back to. */
    char *name;			/* Name of tree in namespace.  Tree
				 * must not already exist. */
{
    TreeObject *treePtr;
    TreeInterpData *dataPtr;
    Tcl_Namespace *nsPtr;
    char string[200];
    char *treeName;
    Tcl_DString dString;

    dataPtr = GetTreeInterpData(interp);
    if (name != NULL) {
	/* Check if this tree already exists the current namespace. */
	treePtr = GetTreeObject(interp, name, NS_SEARCH_CURRENT);
	if (treePtr != NULL) {
	    Tcl_AppendResult(interp, "a tree object \"", name,
			     "\" already exists", (char *)NULL);
	    return TCL_ERROR;
	}
    } else {
	/* Generate a unique tree name in the current namespace. */
	do  {
	    sprintf(string, "tree%d", dataPtr->nextId++);
	} while (GetTreeObject(interp, name, NS_SEARCH_CURRENT) != NULL);
	name = string;
    } 
    /* 
     * Tear apart and put back together the namespace-qualified name 
     * of the tree. This is to ensure that the naming is consistent.
     */ 
    treeName = name;
    if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
	Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"", 
		(char *)NULL);
	return TCL_ERROR;
    }
    if (nsPtr == NULL) {
	nsPtr = Tcl_GetCurrentNamespace(interp);
    }
    name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
    treePtr = NewTreeObject(dataPtr, interp, name);
    if (treePtr == NULL) {
	Tcl_AppendResult(interp, "can't allocate tree \"", name, "\"", 
		(char *)NULL);
	Tcl_DStringFree(&dString);
	return TCL_ERROR;
    }
    Tcl_DStringFree(&dString);
    return TCL_OK;
}

int
Blt_TreeGetToken(interp, name, tokenPtrPtr)
    Tcl_Interp *interp;		/* Interpreter to report errors back to. */
    char *name;			/* Name of tree in namespace. */
    ClientToken **tokenPtrPtr;
{
    ClientToken *tokenPtr;
    TreeObject *treePtr;

    treePtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
    if (treePtr == NULL) {
	Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"", 
		(char *)NULL);
	return TCL_ERROR;
    }
    tokenPtr = (ClientToken *)calloc(1, sizeof(ClientToken));
    if (tokenPtr == NULL) {
	Tcl_SetResult(interp, "can't allocate tree token", TCL_STATIC);
	return TCL_ERROR;
    }
    tokenPtr->magic = TREE_MAGIC;
    tokenPtr->linkPtr = Blt_ChainAppend(treePtr->chainPtr, 
	(ClientData)tokenPtr);
    tokenPtr->chainPtr = Blt_ChainCreate();
    tokenPtr->tracePtr = Blt_ChainCreate();
    tokenPtr->tree = treePtr;
    tokenPtr->root = treePtr->root;
    *tokenPtrPtr = tokenPtr;
    return TCL_OK;
}

void
Blt_TreeReleaseToken(tokenPtr)
    ClientToken *tokenPtr;
{
    TreeObject *treePtr;
    Blt_ChainLink *linkPtr;
    EventHandler *handlerPtr;

    if (tokenPtr->magic != TREE_MAGIC) {
	fprintf(stderr, "invalid tree object token 0x%lx\n", 
		(unsigned long)tokenPtr);
	return;
    }
    /* Remove any traces that may be set. */
    for (linkPtr = Blt_ChainFirstLink(tokenPtr->tracePtr); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	free((char *)Blt_ChainGetValue(linkPtr));
    }
    Blt_ChainDestroy(tokenPtr->tracePtr);
    /* And any event handlers. */
    for(linkPtr = Blt_ChainFirstLink(tokenPtr->chainPtr); linkPtr != NULL;
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	handlerPtr = (EventHandler *)Blt_ChainGetValue(linkPtr);
	if (handlerPtr->notifyPending) {
	    Tcl_CancelIdleCall(NotifyIdleProc, (ClientData)handlerPtr);
	}
	free((char *)handlerPtr);
    }
    Blt_ChainDestroy(tokenPtr->chainPtr);
    treePtr = tokenPtr->tree;
    if (treePtr != NULL) {
	/* Remove the client from the server's list */
	Blt_ChainDeleteLink(treePtr->chainPtr, tokenPtr->linkPtr);
	if (Blt_ChainGetLength(treePtr->chainPtr) == 0) {
	    DestroyTreeObject(treePtr);
	}
    }
    tokenPtr->magic = 0;
    free((char *)tokenPtr);
}

int
Blt_TreeExists(interp, name)
    Tcl_Interp *interp;		/* Interpreter to report errors back to. */
    char *name;			/* Name of tree in designated namespace. */
{
    return (GetTreeObject(interp, name, NS_SEARCH_BOTH) != NULL);
}

/*ARGSUSED*/
static int
SizeApplyProc(nodePtr, clientData, order)
    Node *nodePtr;		/* Not used. */
    ClientData clientData;
    int order;			/* Not used. */
{
    int *sumPtr = (int *)clientData;
    *sumPtr = *sumPtr + 1;
    return TCL_OK;
}

int
Blt_TreeSize(nodePtr)
    Node *nodePtr;
{
    int sum;

    sum = 0;
    Blt_TreeApply(nodePtr, SizeApplyProc, (ClientData)&sum);
    return sum;
}


void
Blt_TreeCreateEventHandler(tokenPtr, mask, proc, clientData)
    ClientToken *tokenPtr;
    unsigned int mask;
    Blt_TreeNotifyEventProc *proc;
    ClientData clientData;
{
    Blt_ChainLink *linkPtr;
    EventHandler *handlerPtr;

    handlerPtr = NULL;		/* Suppress compiler warning. */

    /* Check if the event is already handled. */
    for(linkPtr = Blt_ChainFirstLink(tokenPtr->chainPtr); linkPtr != NULL;
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	handlerPtr = (EventHandler *)Blt_ChainGetValue(linkPtr);
	if ((handlerPtr->proc == proc) && 
	    (handlerPtr->clientData == clientData)) {
	    break;
	}
    }
    if (linkPtr == NULL) {
	handlerPtr = (EventHandler *)malloc(sizeof (EventHandler));
	assert(handlerPtr);
	linkPtr = Blt_ChainAppend(tokenPtr->chainPtr, (ClientData)handlerPtr);
    }
    if (proc == NULL) {
	Blt_ChainDeleteLink(tokenPtr->chainPtr, linkPtr);
	free((char *)handlerPtr);
    } else {
	handlerPtr->proc = proc;
	handlerPtr->clientData = clientData;
	handlerPtr->mask = mask;
	handlerPtr->notifyPending = FALSE;
    }
}

void
Blt_TreeDeleteEventHandler(tokenPtr, mask, proc, clientData)
    ClientToken *tokenPtr;
    unsigned int mask;
    Blt_TreeNotifyEventProc *proc;
    ClientData clientData;
{
    Blt_ChainLink *linkPtr;
    EventHandler *handlerPtr;

    for(linkPtr = Blt_ChainFirstLink(tokenPtr->chainPtr); linkPtr != NULL;
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	handlerPtr = (EventHandler *)Blt_ChainGetValue(linkPtr);
	if ((handlerPtr->proc == proc) && (handlerPtr->mask == mask) &&
	    (handlerPtr->clientData == clientData)) {
	    if (handlerPtr->notifyPending) {
		Tcl_CancelIdleCall(NotifyIdleProc, (ClientData)handlerPtr);
	    }
	    Blt_ChainDeleteLink(tokenPtr->chainPtr, linkPtr);
	    free((char *)handlerPtr);
	    return;
	}
    }
}

#endif /* NO_TREE */
