blt2.5/generic/bltTree.c

/*
 * 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.
 *      Extensive cleanups and enhancements by Peter MacDonald.
 *
 */

#include "bltInt.h"

/* TODO:
 *	traces and notifiers should be in one list in tree object.
 *	notifier is always fired.
 *	incorporate first/next tag routines ?
 */


#ifndef NO_TREE

#include "bltTree.h"


static int IsTclDict(Tcl_Interp *interp,Tcl_Obj *objPtr) {
   static Tcl_ObjType *dictType = NULL;

   if (dictType == NULL) {
        Tcl_Obj * obj;
        obj = Tcl_NewDictObj();
        dictType = obj->typePtr;
        Tcl_DecrRefCount(obj);
   }
   return (objPtr->typePtr == dictType);
}

/* 2 = per-tree key, 1 for per-interp, 0 for global (original behavior). */
int bltTreeUseLocalKeys = 0;

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_TreeNodeStruct Node;
typedef struct Blt_TreeClientStruct TreeClient;
typedef struct Blt_TreeObjectStruct TreeObject;
typedef struct Blt_TreeValueStruct Value;

/*
 * Blt_TreeValue --
 *
 *	Tree nodes contain heterogeneous data fields, represented as a
 *	chain of these structures.  Each field contains the key of the
 *	field (Blt_TreeKey) and the value (Tcl_Obj) containing the
 *	actual data representations.
 *
 */
struct Blt_TreeValueStruct {
    Blt_TreeKey key;		/* String identifying the data field */
    Tcl_Obj *objPtr;		/* Data representation. */
    Blt_Tree owner;		/* Non-NULL if privately owned. */
    Blt_TreeValue next;		/* Next value in the chain. */
};

#include <stdio.h>
#include <string.h>
/* The following header is required for LP64 compilation */
#include <stdlib.h>

#include "bltHash.h"

static void TreeDestroyValues _ANSI_ARGS_((Blt_TreeNode node));

static Value *TreeFindValue _ANSI_ARGS_((Blt_TreeNode node,
	Blt_TreeKey key));
static Value *TreeCreateValue _ANSI_ARGS_((Blt_TreeNode node,
	Blt_TreeKey key, int *newPtr));

static int TreeDeleteValue _ANSI_ARGS_((Blt_TreeNode node,
	Blt_TreeValue value));

static Value *TreeFirstValue _ANSI_ARGS_((Blt_TreeNode,
	Blt_TreeKeySearch *searchPtr));

static Value *TreeNextValue _ANSI_ARGS_((Blt_TreeKeySearch *srchPtr));

/*
 * When there are this many entries per bucket, on average, rebuild
 * the hash table to make it larger.
 */

#define REBUILD_MULTIPLIER	3

#define START_LOGSIZE		5 /* Initial hash table size is 32. */
#define MAX_LIST_VALUES		21 /* Convert to hash table when node
				    * value list gets bigger than this
				    * many values. */

#if (SIZEOF_VOID_P == 8)
#define RANDOM_INDEX(i)		HashOneWord(mask, downshift, i)
#define BITSPERWORD		64
#else

/*
 * The following macro takes a preliminary integer hash value and
 * produces an index into a hash tables bucket list.  The idea is
 * to make it so that preliminary values that are arbitrarily similar
 * will end up in different buckets.  The hash function was taken
 * from a random-number generator.
 */
#define RANDOM_INDEX(i) \
    (((((long) (i))*1103515245) >> downshift) & mask)
#define BITSPERWORD		32
#endif

#define DOWNSHIFT_START		(BITSPERWORD - 2)

/*
 * Procedure prototypes for static procedures in this file:
 */


#if (SIZEOF_VOID_P == 8)
static Blt_Hash HashOneWord _ANSI_ARGS_((uint64_t mask, unsigned int downshift,
	CONST void *key));

#endif /* SIZEOF_VOID_P == 8 */

/*
 * The hash table below is used to keep track of all the Blt_TreeKeys
 * created so far.
 */
static Blt_HashTable keyTable;
static int keyTableInitialized = 0;

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

typedef struct {
    Tcl_Interp *interp;
    ClientData clientData;
    Blt_TreeKey key;
    unsigned int mask;
    Blt_TreeNotifyEventProc *proc;
    Blt_TreeNotifyEvent event;
    int notifyPending;
} EventHandler;

typedef struct {
    ClientData clientData;
    char *keyPattern;
    char *withTag;
    Node *nodePtr;
    unsigned int mask;
    Blt_TreeTraceProc *proc;
    TreeClient *clientPtr;
    Blt_ChainLink *linkPtr;
} TraceHandler;

/*
 * --------------------------------------------------------------
 *
 * GetTreeInterpData --
 *
 *	Creates or retrieves data associated with tree data objects
 *	for a particular thread.  We're using Tcl_GetAssocData rather
 *	than the Tcl thread routines so BLT can work with pre-8.0
 *	Tcl versions that don't have thread support.
 *
 * Results:
 *	Returns a pointer to the tree interpreter data.
 *
 * --------------------------------------------------------------
 */
static TreeInterpData *
GetTreeInterpData(Tcl_Interp *interp)
{
    Tcl_InterpDeleteProc *proc;
    TreeInterpData *dataPtr;

    dataPtr = (TreeInterpData *)
	Tcl_GetAssocData(interp, TREE_THREAD_KEY, &proc);
    if (dataPtr == NULL) {
	dataPtr = Blt_Malloc(sizeof(TreeInterpData));
	assert(dataPtr);
	dataPtr->interp = interp;
	Tcl_SetAssocData(interp, TREE_THREAD_KEY, TreeInterpDeleteProc,
		 dataPtr);
	Blt_InitHashTable(&dataPtr->treeTable, BLT_STRING_KEYS);
	Blt_InitHashTable(&dataPtr->keyTable, BLT_STRING_KEYS);
    }
    return dataPtr;
}

/*
 * --------------------------------------------------------------
 *
 * NewNode --
 *
 *	Creates a new node in the tree without installing it.  The
 *	number of nodes in the tree is incremented and a unique serial
 *	number is generated for the node.
 *
 *	Also, all nodes have a label.  If no label was provided (name
 *	is NULL) then automatically generate a serial number for the node.
 *
 * Results:
 *	Returns a pointer to the new node.
 *
 * --------------------------------------------------------------
 */
static Node *
NewNode(TreeObject *treeObjPtr, CONST char *name, int inode)
{
    Node *nodePtr;

    /* Create the node structure */
    nodePtr = Blt_PoolAllocItem(treeObjPtr->nodePool, sizeof(Node));
    nodePtr->inode = inode;
    nodePtr->treeObject = treeObjPtr;
    nodePtr->parent = NULL;
    nodePtr->depth = 0;
    nodePtr->flags = 0;
    nodePtr->next = nodePtr->prev = NULL;
    nodePtr->first = nodePtr->last = NULL;
    nodePtr->nChildren = 0;
    nodePtr->values = NULL;
    nodePtr->logSize = 0;
    nodePtr->nValues = 0;
    nodePtr->label = NULL;
    if (name != NULL) {
	nodePtr->label = Blt_TreeKeyGet(NULL, treeObjPtr, name);
    }
    treeObjPtr->nNodes++;
    return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * ReleaseTagTable --
 *
 *----------------------------------------------------------------------
 */
static void
ReleaseTagTable(Blt_TreeTagTable *tablePtr)
{
    tablePtr->refCount--;
    if (tablePtr->refCount <= 0) {
	Blt_HashEntry *hPtr;
	Blt_HashSearch cursor;

	for(hPtr = Blt_FirstHashEntry(&tablePtr->tagTable, &cursor);
	    hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
	    Blt_TreeTagEntry *tPtr;

	    tPtr = Blt_GetHashValue(hPtr);
	    Blt_DeleteHashTable(&tPtr->nodeTable);
	    Blt_TreeTagRefDecr(tPtr);
	}
	Blt_DeleteHashTable(&tablePtr->tagTable);
	Blt_Free(tablePtr);
    }
}

/*
 * ----------------------------------------------------------------------
 *
 * ResetDepths --
 *
 *	Called after moving a node, resets the depths of each node
 *	for the entire branch (node and it's decendants).
 *
 * Results:
 *	None.
 *
 * ----------------------------------------------------------------------
 */
static void
ResetDepths(
    Node *nodePtr,		/* Root node. */
    int depth)			/* Depth of the node. */
{
    nodePtr->depth = depth;
    /* Also reset the depth for each descendant node. */
    for (nodePtr = nodePtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
	ResetDepths(nodePtr, depth + 1);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * LinkBefore --
 *
 *	Inserts a link preceding a given link.
 *
 * Results:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static void
LinkBefore(
    Node *parentPtr,	/* Parent to hold the new entry. */
    Node *nodePtr,	/* New node to be inserted. */
    Node *beforePtr)	/* Node to link before. */
{
    if (parentPtr->first == NULL) {
	parentPtr->last = parentPtr->first = nodePtr;
    } else if (beforePtr == NULL) { /* Append onto the end of the chain */
	nodePtr->next = NULL;
	nodePtr->prev = parentPtr->last;
	parentPtr->last->next = nodePtr;
	parentPtr->last = nodePtr;
    } else {
	nodePtr->prev = beforePtr->prev;
	nodePtr->next = beforePtr;
	if (beforePtr == parentPtr->first) {
	    parentPtr->first = nodePtr;
	} else {
	    beforePtr->prev->next = nodePtr;
	}
	beforePtr->prev = nodePtr;
    }
    parentPtr->nChildren++;
    nodePtr->parent = parentPtr;
}


/*
 *----------------------------------------------------------------------
 *
 * UnlinkNode --
 *
 *	Unlinks a link from the chain. The link is not deallocated,
 *	but only removed from the chain.
 *
 * Results:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static void
UnlinkNode(Node *nodePtr)
{
    Node *parentPtr;
    int unlinked;		/* Indicates if the link is actually
				 * removed from the chain. */
    parentPtr = nodePtr->parent;
    unlinked = FALSE;
    if (parentPtr->first == nodePtr) {
	parentPtr->first = nodePtr->next;
	unlinked = TRUE;
    }
    if (parentPtr->last == nodePtr) {
	parentPtr->last = nodePtr->prev;
	unlinked = TRUE;
    }
    if (nodePtr->next != NULL) {
	nodePtr->next->prev = nodePtr->prev;
	unlinked = TRUE;
    }
    if (nodePtr->prev != NULL) {
	nodePtr->prev->next = nodePtr->next;
	unlinked = TRUE;
    }
    if (unlinked) {
	parentPtr->nChildren--;
    }
    nodePtr->prev = nodePtr->next = nodePtr->parent = NULL;
}

/*
 * --------------------------------------------------------------
 *
 * FreeNode --
 *
 *	Unlinks a given node from the tree, removes its data, and
 *	frees memory allocated to the node.
 *
 * Results:
 *	None.
 *
 * --------------------------------------------------------------
 */
static void
FreeNode(TreeObject *treeObjPtr, Node *nodePtr)
{
    Blt_HashEntry *hPtr;

    /*
     * Destroy any data fields associated with this node.
     */
    TreeDestroyValues(nodePtr);
    UnlinkNode(nodePtr);
    treeObjPtr->nNodes--;
    hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)nodePtr->inode);
    assert(hPtr);
    Blt_DeleteHashEntry(&treeObjPtr->nodeTable, hPtr);
    nodePtr->inode = -1;
    nodePtr->flags = 0;
    Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
}

/*
 * --------------------------------------------------------------
 *
 * NewTreeObject --
 *
 *	Creates and initializes a new tree object. Trees always
 *	contain a root node, so one is allocated here.
 *
 * Results:
 *	Returns a pointer to the new tree object is successful, NULL
 *	otherwise.  If a tree can't be generated, interp->result will
 *	contain an error message.
 *
 * -------------------------------------------------------------- */
static TreeObject *
NewTreeObject(TreeInterpData *dataPtr, Tcl_Interp *interp, CONST char *treeName)
{
    TreeObject *treeObjPtr;
    int isNew;
    Blt_HashEntry *hPtr;

    treeObjPtr = Blt_Calloc(1, sizeof(TreeObject));
    if (treeObjPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't allocate tree", (char *)NULL);
	return NULL;
    }
    treeObjPtr->name = Blt_Strdup(treeName);
    treeObjPtr->interp = interp;
    treeObjPtr->valuePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
    treeObjPtr->nodePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
    treeObjPtr->clients = Blt_ChainCreate();
    treeObjPtr->depth = 1;
    treeObjPtr->flags = 0;
    treeObjPtr->maxKeyList = 0;
    if (bltTreeUseLocalKeys) {
        if (bltTreeUseLocalKeys>1) {
            treeObjPtr->interpKeyPtr = &treeObjPtr->keyTable;
        } else {
            treeObjPtr->interpKeyPtr = &dataPtr->keyTable;
        }
    }
    treeObjPtr->notifyFlags = 0;
    Blt_InitHashTable(&treeObjPtr->keyTable, BLT_STRING_KEYS);
    Blt_InitHashTableWithPool(&treeObjPtr->nodeTable, BLT_ONE_WORD_KEYS);

    hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable, (char *)0, &isNew);
    treeObjPtr->root = NewNode(treeObjPtr, treeName, 0);
    Blt_SetHashValue(hPtr, treeObjPtr->root);

    treeObjPtr->tablePtr = &dataPtr->treeTable;
    treeObjPtr->hashPtr = Blt_CreateHashEntry(treeObjPtr->tablePtr, treeName,
	&isNew);
    Blt_SetHashValue(treeObjPtr->hashPtr, treeObjPtr);

    return treeObjPtr;
}

static TreeObject *
FindTreeInNamespace(
    TreeInterpData *dataPtr,	/* Interpreter-specific data. */
    Tcl_Namespace *nsPtr,
    CONST char *treeName)
{
    Tcl_DString dString;
    char *name;
    Blt_HashEntry *hPtr;

    name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
    hPtr = Blt_FindHashEntry(&dataPtr->treeTable, name);
    Tcl_DStringFree(&dString);
    if (hPtr != NULL) {
	return Blt_GetHashValue(hPtr);
    }
    return NULL;
}

/*
 * ----------------------------------------------------------------------
 *
 * 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(Tcl_Interp *interp, CONST char *name, int flags)
{
    CONST char *treeName;
    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. */
    TreeInterpData *dataPtr;	/* Interpreter-specific data. */
    TreeObject *treeObjPtr;

    treeObjPtr = NULL;
    if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
		(char *)NULL);
	return NULL;
    }
    dataPtr = GetTreeInterpData(interp);
    if (nsPtr != NULL) {
	treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
    } else {
	if (flags & NS_SEARCH_CURRENT) {
	    /* Look first in the current namespace. */
	    nsPtr = Tcl_GetCurrentNamespace(interp);
	    treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
	}
	if ((treeObjPtr == NULL) && (flags & NS_SEARCH_GLOBAL)) {
	    nsPtr = Tcl_GetGlobalNamespace(interp);
	    treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
	}
    }
    return treeObjPtr;
}

/*
 * ----------------------------------------------------------------------
 *
 * TeardownTree --
 *
 *	Destroys an entire branch.  This is a special purpose routine
 *	used to speed up the final clean up of the tree.
 *
 * Results:
 *	None.
 *
 * ----------------------------------------------------------------------
 */
static void
TeardownTree(TreeObject *treeObjPtr, Node *nodePtr)
{
    if (nodePtr->first != NULL) {
	Node *childPtr, *nextPtr;

	for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
	    nextPtr = childPtr->next;
	    TeardownTree(treeObjPtr, childPtr);
	}
    }
    if (nodePtr->values != NULL) {
	TreeDestroyValues(nodePtr);
    }
    Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
}

static void
DestroyTreeObject(char *treeObj)
{
    Blt_ChainLink *linkPtr;
    TreeClient *clientPtr;
    TreeObject *treeObjPtr = (TreeObject*)treeObj;

    if (treeObjPtr->flags & TREE_DESTROYED) return;
    treeObjPtr->flags |= TREE_DESTROYED;
    treeObjPtr->nNodes = 0;

    /* Remove the remaining clients. */
    for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients); linkPtr != NULL;
	linkPtr = Blt_ChainNextLink(linkPtr)) {
	clientPtr = Blt_ChainGetValue(linkPtr);
	Blt_ChainDestroy(clientPtr->events);
	Blt_ChainDestroy(clientPtr->traces);
	Blt_Free(clientPtr);
    }
    Blt_ChainDestroy(treeObjPtr->clients);

    TeardownTree(treeObjPtr, treeObjPtr->root);
    Blt_PoolDestroy(treeObjPtr->nodePool);
    Blt_PoolDestroy(treeObjPtr->valuePool);
    Blt_DeleteHashTable(&treeObjPtr->nodeTable);
    Blt_DeleteHashTable(&treeObjPtr->keyTable);

    if (treeObjPtr->hashPtr != NULL) {
	/* Remove the entry from the global tree table. */
	Blt_DeleteHashEntry(treeObjPtr->tablePtr, treeObjPtr->hashPtr);
	if ((treeObjPtr->tablePtr->numEntries == 0) && (keyTableInitialized)) {
	    keyTableInitialized = FALSE;
	    Blt_DeleteHashTable(&keyTable);
	}
    }
    if (treeObjPtr->name != NULL) {
	Blt_Free(treeObjPtr->name);
    }
    Blt_Free(treeObjPtr);
}

/*
 * -----------------------------------------------------------------------
 *
 * TreeInterpDeleteProc --
 *
 *	This is called when the interpreter hosting the tree object
 *	is deleted from the interpreter.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Destroys all remaining trees and removes the hash table
 *	used to register tree names.
 *
 * ------------------------------------------------------------------------
 */
/* ARGSUSED */
static void
TreeInterpDeleteProc(
    ClientData clientData,	/* Interpreter-specific data. */
    Tcl_Interp *interp)
{
    TreeInterpData *dataPtr = clientData;
    Blt_HashEntry *hPtr;
    Blt_HashSearch cursor;
    TreeObject *treeObjPtr;

    for (hPtr = Blt_FirstHashEntry(&dataPtr->treeTable, &cursor);
	 hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
	treeObjPtr = (TreeObject *)Blt_GetHashValue(hPtr);
	treeObjPtr->hashPtr = NULL;
	treeObjPtr->delete = 1;
        Tcl_EventuallyFree(treeObjPtr, DestroyTreeObject);
         /*DestroyTreeObject(treeObjPtr); */
    }
    if (keyTableInitialized) {
	keyTableInitialized = FALSE;
	Blt_DeleteHashTable(&keyTable);
    }
    Blt_DeleteHashTable(&dataPtr->treeTable);
    Blt_DeleteHashTable(&dataPtr->keyTable);
    Tcl_DeleteAssocData(interp, TREE_THREAD_KEY);
    Blt_Free(dataPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyIdleProc --
 *
 *	Used to invoke event handler routines at some idle point.
 *	This routine is called from the Tcl event loop.  Errors
 *	generated by the event handler routines are backgrounded.
 *
 * Results:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static void
NotifyIdleProc(ClientData clientData)
{
    EventHandler *notifyPtr = clientData;
    int result;

    notifyPtr->notifyPending = FALSE;
    notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
    result = (*notifyPtr->proc)(notifyPtr->clientData, &notifyPtr->event);
    notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
    if (result != TCL_OK) {
	Tcl_BackgroundError(notifyPtr->interp);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * CheckEventHandlers --
 *
 *	Traverses the list of client event callbacks and checks
 *	if one matches the given event.  A client may trigger an
 *	action that causes the tree to notify it.  The can be
 *	prevented by setting the TREE_NOTIFY_FOREIGN_ONLY bit in
 *	the event handler.
 *
 *	If a matching handler is found, a callback may be called either
 *	immediately or at the next idle time depending upon the
 *	TREE_NOTIFY_WHENIDLE bit.
 *
 *	Since a handler routine may trigger yet another call to
 *	itself, callbacks are ignored while the event handler is
 *	executing.
 *
 * Results:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static int
CheckEventHandlers(
    TreeClient *clientPtr,
    int isSource,		/* Indicates if the client is the source
				 * of the event. */
    Blt_TreeNotifyEvent *eventPtr)
{
    Blt_ChainLink *linkPtr, *nextPtr;
    EventHandler *notifyPtr;

    eventPtr->tree = clientPtr;
    for (linkPtr = Blt_ChainFirstLink(clientPtr->events);
	linkPtr != NULL; linkPtr = nextPtr) {
	nextPtr = Blt_ChainNextLink(linkPtr);
	notifyPtr = Blt_ChainGetValue(linkPtr);
	if ((notifyPtr->mask & TREE_NOTIFY_ACTIVE) ||
	    (notifyPtr->mask & eventPtr->type) == 0) {
	    continue;		/* Ignore callbacks that are generated
				 * inside of a notify handler routine. */
	}
	if ((isSource) && (notifyPtr->mask & TREE_NOTIFY_FOREIGN_ONLY)) {
	    continue;		/* Don't notify yourself. */
	}
	if (notifyPtr->mask & TREE_NOTIFY_WHENIDLE) {
	    if (!notifyPtr->notifyPending) {
		notifyPtr->notifyPending = TRUE;
		notifyPtr->event = *eventPtr;
		Tcl_DoWhenIdle(NotifyIdleProc, notifyPtr);
	    }
	} else {
	    int result;

	    notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
	    result = (*notifyPtr->proc) (notifyPtr->clientData, eventPtr);
	    notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
	    if (result != TCL_OK) {
	        if (notifyPtr->mask & TREE_NOTIFY_BGERROR) {
		     Tcl_BackgroundError(notifyPtr->interp);
		}
	        return result;
	    }
	}
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyClients --
 *
 *	Traverses the list of clients for a particular tree and
 *	notifies each client that an event occurred.  Clients
 *	indicate interest in a particular event through a bit
 *	flag.
 *
 *----------------------------------------------------------------------
 */
static int
NotifyClients(
    TreeClient *sourcePtr,
    TreeObject *treeObjPtr,
    Node *nodePtr,
    int eventFlag)
{
    Blt_ChainLink *linkPtr;
    Blt_TreeNotifyEvent event;
    TreeClient *clientPtr;
    int isSource, result;

    if (Tcl_InterpDeleted(treeObjPtr->interp) ||
            Tcl_InterpDeleted(sourcePtr->root->treeObject->interp)) {
        return TCL_OK;
    }
    event.type = eventFlag;
    event.inode = nodePtr->inode;

    /*
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	clientPtr = Blt_ChainGetValue(linkPtr);
	isSource = (clientPtr == sourcePtr);
	result = CheckEventHandlers(clientPtr, isSource, &event);
	if (result != TCL_OK) {
	    return TCL_ERROR;
	}
        if (Blt_TreeNodeDeleted(nodePtr) || nodePtr->inode != event.inode) {
            return TCL_BREAK;
        }
     }
    return TCL_OK;
}

static void
FreeValue(Node *nodePtr, Value *valuePtr)
{
    if (valuePtr->objPtr != NULL) {
	Tcl_DecrRefCount(valuePtr->objPtr);
    }
    Blt_PoolFreeItem(nodePtr->treeObject->valuePool, valuePtr);
}


/* Public Routines */
/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeGetKey --
 *
 *	Given a string, returns a unique identifier for the string.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeKey
Blt_TreeGetKey(string)
    CONST char *string;		/* String to convert. */
{
    Blt_HashEntry *hPtr;
    int isNew;

    if (!keyTableInitialized) {
	Blt_InitHashTable(&keyTable, BLT_STRING_KEYS);
	keyTableInitialized = 1;
    }
    hPtr = Blt_CreateHashEntry(&keyTable, string, &isNew);
    return (Blt_TreeKey)Blt_GetHashKey(&keyTable, hPtr);
}

/*
*----------------------------------------------------------------------
*
* Blt_TreeKeyGet --
*
*	tree-unique keys.
*       TODO: use per-interp keyTable rather than global one.
*
*----------------------------------------------------------------------
*/
Blt_TreeKey
Blt_TreeKeyGet(interp, treeObjPtr, string)
    Tcl_Interp *interp;
    TreeObject *treeObjPtr;
    CONST char *string;		/* String to convert. */
{
    Blt_HashTable *tablePtr;
    Blt_HashEntry *hPtr;
    int isNew;

    tablePtr = NULL;
    if (treeObjPtr != NULL && treeObjPtr->interpKeyPtr != NULL) {
        tablePtr = treeObjPtr->interpKeyPtr;
    }
    if (tablePtr == NULL && interp != NULL && bltTreeUseLocalKeys != 0) {
        TreeInterpData *dataPtr;
        dataPtr = GetTreeInterpData(interp);
        tablePtr = &dataPtr->keyTable;
    }
    if (tablePtr == NULL) {
        return Blt_TreeGetKey(string);
    }
    hPtr = Blt_CreateHashEntry(tablePtr, string, &isNew);
    return (Blt_TreeKey)Blt_GetHashKey(tablePtr, hPtr);
}

/* Clear the unmodified flag for node. */
static void SetModified(Node *nodePtr)
{
    nodePtr->flags &= ~TREE_NODE_UNMODIFIED;
    nodePtr->treeObject->flags &= ~TREE_UNMODIFIED;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeCreateNode --
 *
 *	Creates a new node in the given parent node.  The name and
 *	position in the parent are also provided.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreeCreateNode(
    TreeClient *clientPtr,	/* The tree client that is creating
				 * this node.  If NULL, indicates to
				 * trigger notify events on behalf of
				 * the initiating client also. */
    Node *parentPtr,		/* Parent node where the new node will
				 * be inserted. */
    CONST char *name,		/* Name of node. */
    int pos)			/* Position in the parent's list of children
				 * where to insert the new node. */
{
    Blt_HashEntry *hPtr;
    Node *beforePtr;
    Node *nodePtr;	/* Node to be inserted. */
    TreeObject *treeObjPtr;
    int inode;
    int isNew;

    treeObjPtr = parentPtr->treeObject;

    /* Generate an unique serial number for this node.  */
    do {
	inode = treeObjPtr->nextInode++;
	hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode,
		   &isNew);
    } while (!isNew);
    nodePtr = NewNode(treeObjPtr, name, inode);
    Blt_SetHashValue(hPtr, nodePtr);

    if ((pos == -1) || (pos >= (int)parentPtr->nChildren)) {
	beforePtr = NULL;
    } else {
	beforePtr = parentPtr->first;
	while ((pos > 0) && (beforePtr != NULL)) {
	    pos--;
	    beforePtr = beforePtr->next;
	}
    }
    LinkBefore(parentPtr, nodePtr, beforePtr);
    nodePtr->depth = parentPtr->depth + 1;
    /*
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    if (NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE) != TCL_OK) {
        nodePtr->flags |= TREE_NODE_INSERT_FAIL;
        Blt_TreeDeleteNode(clientPtr, nodePtr);
        return NULL;
    }
    treeObjPtr->flags &= ~TREE_UNMODIFIED;
    return nodePtr;
}
/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeInsertPost --
 *
 *	Trigger notify for -insert
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreeInsertPost(
    TreeClient *clientPtr,	/* The tree client that is creating
				 * this node.  If NULL, indicates to
				 * trigger notify events on behalf of
				 * the initiating client also. */
    Node *nodePtr)		    /*  node */
{
    if (NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_INSERT) != TCL_OK) {
        nodePtr->flags |= TREE_NODE_INSERT_FAIL;
        Blt_TreeDeleteNode(clientPtr, nodePtr);
        return NULL;
    }
    return nodePtr;
}

int
Blt_TreeNotifyGet(
    TreeClient *clientPtr,	/* The tree client that is creating
				 * this node.  If NULL, indicates to
				 * trigger notify events on behalf of
				 * the initiating client also. */
    Node *nodePtr)		    /*  node */
{
    if (nodePtr->nValues != 0) return TCL_OK;
    return NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_GET);
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeCreateNodeWithId --
 *
 *	Like Blt_TreeCreateNode, but provides a specific id to use
 *	for the node.  If the tree already contains a node by that
 *	id, NULL is returned.
 *
 *----------------------------------------------------------------------
 */
Blt_TreeNode
Blt_TreeCreateNodeWithId(
    TreeClient *clientPtr,
    Node *parentPtr,		/* Parent node where the new node will
				 * be inserted. */
    CONST char *name,		/* Name of node. */
    unsigned int inode,/* Requested id of the new node. If a
				 * node by this id already exists in the
				 * tree, no node is created. */
    int position)		/* Position in the parent's list of children
				 * where to insert the new node. */
{
    Blt_HashEntry *hPtr;
    Node *beforePtr;
    Node *nodePtr;	/* Node to be inserted. */
    TreeObject *treeObjPtr;
    int isNew, result;

    treeObjPtr = parentPtr->treeObject;
    hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode, &isNew);
    if (!isNew) {
	return NULL;
    }
    nodePtr = NewNode(treeObjPtr, name, inode);
    Blt_SetHashValue(hPtr, nodePtr);

    if ((position == -1) || (position >= (int)parentPtr->nChildren)) {
	beforePtr = NULL;
    } else {
	beforePtr = parentPtr->first;
	while ((position > 0) && (beforePtr != NULL)) {
	    position--;
	    beforePtr = beforePtr->next;
	}
    }
    LinkBefore(parentPtr, nodePtr, beforePtr);
    nodePtr->depth = parentPtr->depth + 1;
    /*
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
     result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE);
     if (result != TCL_OK) {
         if (result != TCL_BREAK) {
             nodePtr->flags |= TREE_NODE_INSERT_FAIL;
             Blt_TreeDeleteNode(clientPtr, nodePtr);
         }
         return NULL;
     }
     treeObjPtr->flags &= ~TREE_UNMODIFIED;
     return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeMoveNode --
 *
 *	Move an entry into a new location in the hierarchy.
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
int
Blt_TreeMoveNode(
    TreeClient *clientPtr,
    Node *nodePtr,
    Node *parentPtr,
    Node *beforePtr)
{
    TreeObject *treeObjPtr = nodePtr->treeObject;
    int newDepth, result;

    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;
    }
    /*
    * Issue callbacks to each client indicating that a node has
    * been moved.
    */
    if (NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_MOVE) != TCL_OK) {
        return TCL_ERROR;
    }

    UnlinkNode(nodePtr);
    /*
     * Relink the node as a child of the new parent.
     */
    LinkBefore(parentPtr, nodePtr, beforePtr);
    newDepth = parentPtr->depth + 1;
    if (nodePtr->depth != newDepth) {
	/* Reset the depths of all descendant nodes. */
	ResetDepths(nodePtr, newDepth);
    }
    /*
    * Issue callbacks to each client indicating that a node has
    * been moved.
    */
    if ((result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_MOVEPOST)) != TCL_OK) {
        return result;
    }

    return TCL_OK;
}

int
Blt_TreeDeleteNode(TreeClient *clientPtr, Node *nodePtr)
{
    TreeObject *treeObjPtr = nodePtr->treeObject;
    Node *childPtr, *nextPtr;
    int result;

    /*
    * Issue callbacks to each client indicating that the node can
    * no longer be used.
    */
    if (Blt_TreeNodeDeleted(nodePtr)) {
        return TCL_OK;
    }
    if ((nodePtr->flags & TREE_NODE_INSERT_FAIL) == 0 &&
        (result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_DELETE)) != TCL_OK) {
        return result;
    }
    nodePtr->flags &= ~TREE_NODE_FIXED_FIELDS;

    /* In depth-first order, delete each descendant node. */
    for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
	nextPtr = childPtr->next;
	Blt_TreeDeleteNode(clientPtr, childPtr);
    }

    /* Now remove the actual node. */
    FreeNode(treeObjPtr, nodePtr);
    if (treeObjPtr->nodeTable.numEntries <= 1) {
        treeObjPtr->nextInode = 1;
    }
    return TCL_OK;
}

Blt_TreeNode
Blt_TreeGetNode(TreeClient *clientPtr, unsigned int inode)
{
    TreeObject *treeObjPtr = clientPtr->treeObject;
    Blt_HashEntry *hPtr;

    hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)inode);
    if (hPtr != NULL) {
	return (Blt_TreeNode)Blt_GetHashValue(hPtr);
    }
    return NULL;
}

/*
static Node*
GetNode(TreeObject *treeObjPtr, unsigned int inode)
{
    Blt_HashEntry *hPtr;

    hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)inode);
    if (hPtr != NULL) {
	return (Node*)Blt_GetHashValue(hPtr);
    }
    return NULL;
}
*/

Blt_TreeTrace
Blt_TreeCreateTrace(
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *keyPattern,
    CONST char *tagName,
    unsigned int mask,
    Blt_TreeTraceProc *proc,
    ClientData clientData)
{
    TraceHandler *tracePtr;

    tracePtr = Blt_Calloc(1, sizeof (TraceHandler));
    assert(tracePtr);
    tracePtr->linkPtr = Blt_ChainAppend(clientPtr->traces, tracePtr);
    if (keyPattern != NULL) {
	tracePtr->keyPattern = Blt_Strdup(keyPattern);
    }
    if (tagName != NULL) {
	tracePtr->withTag = Blt_Strdup(tagName);
    }
    tracePtr->clientPtr = clientPtr;
    tracePtr->proc = proc;
    tracePtr->clientData = clientData;
    tracePtr->mask = mask;
    tracePtr->nodePtr = nodePtr;
    return (Blt_TreeTrace)tracePtr;
}

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

    Blt_ChainDeleteLink(tracePtr->clientPtr->traces, tracePtr->linkPtr);
    if (tracePtr->keyPattern != NULL) {
	Blt_Free(tracePtr->keyPattern);
    }
    if (tracePtr->withTag != NULL) {
	Blt_Free(tracePtr->withTag);
    }
    Blt_Free(tracePtr);
}

int
Blt_TreeRelabelNode(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
{
    int result, inode;
    if ((result=NotifyClients(clientPtr, clientPtr->treeObject, nodePtr,
		  TREE_NOTIFY_RELABEL)) != TCL_OK) {
	return result;
    }
    nodePtr->label = Blt_TreeKeyGet(NULL, clientPtr->treeObject,string);
    /*
     * Issue callbacks to each client indicating that a new node has
     * been created.
     */
    SetModified(nodePtr);
    inode = nodePtr->inode;
    result = NotifyClients(clientPtr, clientPtr->treeObject, nodePtr,
		  TREE_NOTIFY_RELABELPOST);
    return result;
}

int
Blt_TreeNotifyAttach(TreeClient *clientPtr)
{
    /* return NotifyClients(clientPtr, clientPtr->treeObject, clientPtr->root,
		  TREE_NOTIFY_ATTACH); */
    return TCL_OK;
}


int
Blt_TreeRelabelNode2(Node *nodePtr, CONST char *string)
{
    nodePtr->label = Blt_TreeKeyGet(NULL, nodePtr->treeObject,string);
    SetModified(nodePtr);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * 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(Node *parentPtr, CONST char *string)
{
    Blt_TreeKey label;
    register Node *nodePtr;

    label = Blt_TreeKeyGet(NULL, parentPtr->treeObject,string);
    for (nodePtr = parentPtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
	if (label == nodePtr->label) {
	    return nodePtr;
	}
    }
    return NULL;
}
/*
 * Like Blt_TreeFindChild above, but looks forward firstN elements
 * from front, then falls back to reverse search starting from the end.
 * This speeds up insertion at the end of really long trees in treeview.
 * If firstN is < 0, just calls Blt_TreeFindChild.
 */
Blt_TreeNode
Blt_TreeFindChildRev(Node *parentPtr, CONST char *string, int firstN)
{
    Blt_TreeKey label;
    register Node *nodePtr, *endNode;
    int n;

    if (firstN<0) {
        return Blt_TreeFindChild(parentPtr, string);
    }
    label = Blt_TreeKeyGet(NULL, parentPtr->treeObject,string);
    for (nodePtr = parentPtr->first, n = 0;
        nodePtr != NULL && n < firstN;
        nodePtr = nodePtr->next, n++) {
        if (label == nodePtr->label) {
            return nodePtr;
        }
    }
    if (nodePtr == NULL) {
        return NULL;
    }
    endNode = nodePtr;
    for (nodePtr = parentPtr->last; nodePtr != NULL; nodePtr = nodePtr->prev) {
	if (label == nodePtr->label) {
	    return nodePtr;
	}
	if (nodePtr == endNode) break;
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeNodePosition --
 *
 *	Returns the position of the node in its parent's list of
 *	children.  The root's position is 0.
 *
 *----------------------------------------------------------------------
 */
int
Blt_TreeNodePosition(Node *nodePtr)
{
    Node *parentPtr;
    int count;

    count = 0;
    parentPtr = nodePtr->parent;
    if (parentPtr != NULL) {
	Node *childPtr;

	for (childPtr = parentPtr->first; childPtr != NULL;
	     childPtr = childPtr->next) {
	    if (nodePtr == childPtr) {
		break;
	    }
	    count++;
	}
    }
    return count;
}


/*
 *----------------------------------------------------------------------
 *
 * 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(Node *rootPtr, Node *nodePtr)
{
    Node *prevPtr;

    if (nodePtr == rootPtr) {
	return NULL;		/* The root is the first node. */
    }
    prevPtr = nodePtr->prev;
    if (prevPtr == 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 when we reach a leaf.
     */
    nodePtr = prevPtr;
    while ((prevPtr = nodePtr->last) != NULL) {
	nodePtr = prevPtr;
    }
    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(Node *rootPtr, Node *nodePtr)
{
    Node *nextPtr;

    /* Pick the first sub-node. */
    nextPtr = nodePtr->first;
    if (nextPtr != NULL) {
	return nextPtr;
    }
    /*
     * 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) {
	nextPtr = nodePtr->next;
	if (nextPtr != NULL) {
	    return nextPtr;
	}
	nodePtr = nodePtr->parent;
    }
    return NULL;		/* At root, no next node. */
}


int
Blt_TreeIsBefore(Node *n1Ptr, Node *n2Ptr)
{
    int depth;
    register int i;
    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 both nodes are at
     * the same depth.  Check if this ancestor node is the same for
     * both nodes.
     */
    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 (nodePtr = n1Ptr->parent->first; nodePtr != NULL;
	 nodePtr = nodePtr->next) {
	if (nodePtr == n1Ptr) {
	    return TRUE;
	} else if (nodePtr == n2Ptr) {
	    return FALSE;
	}
    }
    return FALSE;
}

static int
CallTraces(
    Tcl_Interp *interp,
    TreeClient *sourcePtr,	/* Client holding a reference to the
				 * tree.  If NULL, indicates to
				 * execute all handlers, including
				 * those of the caller. */
    TreeObject *treeObjPtr,	/* Tree that was changed. */
    Node *nodePtr,		/* Node that received the event. */
    Blt_TreeKey key,
    unsigned int flags,
    int *cnt)
{
    Blt_ChainLink *l1Ptr, *l2Ptr;
    TreeClient *clientPtr;
    TraceHandler *tracePtr;
    unsigned int inode = nodePtr->inode;
    int result;

    for(l1Ptr = Blt_ChainFirstLink(treeObjPtr->clients);
	l1Ptr != NULL; l1Ptr = Blt_ChainNextLink(l1Ptr)) {
	clientPtr = Blt_ChainGetValue(l1Ptr);
	for(l2Ptr = Blt_ChainFirstLink(clientPtr->traces);
	    l2Ptr != NULL; l2Ptr = Blt_ChainNextLink(l2Ptr)) {
	    tracePtr = Blt_ChainGetValue(l2Ptr);
	    if ((tracePtr->mask & flags) == 0) {
		continue;	/* Flags don't match. */
	    }
	    if ((clientPtr == sourcePtr) &&
		(tracePtr->mask & TREE_TRACE_FOREIGN_ONLY)) {
		continue;	/* This client initiated the trace. */
	    }
	    if ((tracePtr->nodePtr != NULL) && (tracePtr->nodePtr != nodePtr)) {
		continue;	/* Nodes don't match. */
	    }
	    if ((tracePtr->keyPattern != NULL) &&
		(!Tcl_StringMatch(key, tracePtr->keyPattern))) {
		continue;	/* Key pattern doesn't match. */
	    }
	    if ((tracePtr->withTag != NULL) &&
		(!Blt_TreeHasTag(clientPtr, nodePtr, tracePtr->withTag))) {
		continue;	/* Doesn't have the tag. */
	    }
	    nodePtr->flags |= TREE_TRACE_ACTIVE;
	    *cnt += 1;

	    Tcl_Preserve(treeObjPtr);
	    result = (*tracePtr->proc) (tracePtr->clientData, treeObjPtr->interp,
		nodePtr, key, flags);
            if (result != TCL_OK) {
	        Tcl_Release(treeObjPtr);
                if ((tracePtr->mask & TREE_TRACE_BGERROR) && interp != NULL) {
                    Tcl_BackgroundError(interp);
                } else {
                    nodePtr->flags &= ~TREE_TRACE_ACTIVE;
                    return TCL_ERROR;
                }
	    }
             nodePtr->flags &= ~TREE_TRACE_ACTIVE;
             if (Blt_TreeNodeDeleted(nodePtr) || nodePtr->inode != inode) {
                 Tcl_Release(treeObjPtr);
                 return TCL_ERROR;
	    }
	    if (treeObjPtr->delete) {
                 Tcl_Release(treeObjPtr);
                 if (interp != NULL) {
                     Tcl_AppendResult(interp, "tree deleted", 0);
                 }
                 return TCL_ERROR;
            }
            Tcl_Release(treeObjPtr);
	    /* nodePtr = GetNode(treeObjPtr, inode);
            if (nodePtr == NULL) {
                if (interp != NULL) {
                    Tcl_AppendResult(interp, "node deleted", 0);
                }
                return TCL_ERROR;
            }*/
	}
    }
    return TCL_OK;
}

static Value *
GetTreeValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKey key)
{
    register Value *valuePtr;

    valuePtr = TreeFindValue(nodePtr, key);
    if (valuePtr == NULL) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't find field \"", key, "\"",
			     (char *)NULL);
	}
	return NULL;
    }
    if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't access private field \"",
			     key, "\"", (char *)NULL);
	}
	return NULL;
    }
    return valuePtr;
}

int
Blt_TreePrivateValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKey key)
{
    Value *valuePtr;

    valuePtr = TreeFindValue(nodePtr, key);
    if (valuePtr == NULL) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't find field \"", key, "\"",
			     (char *)NULL);
	}
	return TCL_ERROR;
    }
    valuePtr->owner = clientPtr;
    return TCL_OK;
}

int
Blt_TreePublicValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKey key)
{
    Value *valuePtr;

    valuePtr = TreeFindValue(nodePtr, key);
    if (valuePtr == NULL) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't find field \"", key, "\"",
			     (char *)NULL);
	}
	return TCL_ERROR;
    }
    if (valuePtr->owner != clientPtr) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "not the owner of \"", key, "\"",
		     (char *)NULL);
	}
	return TCL_ERROR;
    }
    valuePtr->owner = NULL;
    return TCL_OK;
}

int
Blt_TreeValueExistsByKey(clientPtr, nodePtr, key)
    TreeClient *clientPtr;
    Node *nodePtr;
    Blt_TreeKey key;
{
    register Value *valuePtr;
    int cnt;
    TreeObject *treeObjPtr = nodePtr->treeObject;
    Tcl_Interp *interp = treeObjPtr->interp;

    valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
    if (valuePtr == NULL && (!(nodePtr->flags & TREE_TRACE_ACTIVE))) {
        if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
            TREE_TRACE_EXISTS, &cnt) != TCL_OK) {
            Tcl_ResetResult(interp);
        } else {
            valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
        }
    }
    if (valuePtr == NULL) {
	return FALSE;
    }
    return TRUE;
}

int
Blt_TreeGetValueByKey(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKey key,
    Tcl_Obj **objPtrPtr)
{
    register Value *valuePtr;
    TreeObject *treeObjPtr = nodePtr->treeObject;
    int cnt = 0;

    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
		   TREE_TRACE_READ, &cnt) != TCL_OK) {
	    return TCL_ERROR;
        }
    }
    valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
    if (valuePtr == NULL) {
        return TCL_ERROR;
    }
    *objPtrPtr = valuePtr->objPtr;
    return TCL_OK;
}

int
bltTreeGetValueByKey(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKey key,
    Value** valuePtrPtr)
{
    register Value *valuePtr;
    TreeObject *treeObjPtr = nodePtr->treeObject;
    int cnt = 0;

    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
		   TREE_TRACE_READ, &cnt) != TCL_OK) {
	    return TCL_ERROR;
        }
    }
    valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
    if (valuePtr == NULL) {
        return TCL_ERROR;
    }
    *valuePtrPtr = valuePtr;
    return TCL_OK;
}

static void
UpdateOldValue(
    TreeClient *clientPtr,
    Tcl_Obj *objPtr)
{
    if (clientPtr->oldValue != NULL) {
        Tcl_DecrRefCount(clientPtr->oldValue);
    }
    clientPtr->oldValue = objPtr;
}

void
Blt_TreeOldValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Tcl_Obj **oldPtr,
    Tcl_Obj *newPtr)
{
    if (newPtr) {
        if (clientPtr->oldValue != NULL) {
            Tcl_DecrRefCount(clientPtr->oldValue);
        }
        clientPtr->oldValue = newPtr;
        Tcl_IncrRefCount(clientPtr->oldValue);
    } else if (oldPtr != NULL) {
        *oldPtr = clientPtr->oldValue;
    }
}

int
Blt_TreeSetValueByKey(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    Blt_TreeKey key,		/* Identifies the field key. */
    Tcl_Obj *objPtr)		/* New value of field. */
{
    TreeObject *treeObjPtr;
    Value *valuePtr;
    unsigned int flags;
    int isNew = 0, cnt = 0;

    if (nodePtr == NULL) {
        return TCL_ERROR;
    }
    treeObjPtr = nodePtr->treeObject;
    assert(objPtr != NULL);
    if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
        valuePtr = TreeFindValue(nodePtr, key);
        if (valuePtr == NULL) {
            if (interp != NULL) {
                Tcl_AppendResult(interp, "fixed field \"", key, "\"",
                    (char *)NULL);
            }
            return TCL_ERROR;
        }
    } else {
        valuePtr = TreeCreateValue(nodePtr, key, &isNew);
    }
    if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't set private field \"",
			     key, "\"", (char *)NULL);
	}
	return TCL_ERROR;
    }
    SetModified(nodePtr);
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
        UpdateOldValue(clientPtr, valuePtr->objPtr);
        valuePtr->objPtr = NULL;
    }
    if (objPtr != valuePtr->objPtr) {
	Tcl_IncrRefCount(objPtr);
	if (valuePtr->objPtr != NULL) {
	    Tcl_DecrRefCount(valuePtr->objPtr);
	}
	valuePtr->objPtr = objPtr;
    }
    flags = TREE_TRACE_WRITE;
    if (isNew) {
	flags |= TREE_TRACE_CREATE;
    }
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	return CallTraces(interp, clientPtr, treeObjPtr, nodePtr, valuePtr->key,
		flags, &cnt);
    }
    return TCL_OK;
}

int
Blt_TreeUnsetValueByKey(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    Blt_TreeKey key)		/* Name of field in node. */
{
    TreeObject *treeObjPtr = nodePtr->treeObject;
    Value *valuePtr;
    int cnt = 0;

    if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
        if (interp != NULL) {
            Tcl_AppendResult(interp, "fixed field", 0);
        }
        return TCL_ERROR;
    }
    valuePtr = TreeFindValue(nodePtr, key);
    if (valuePtr == NULL) {
	return TCL_OK;		/* It's okay to unset values that don't
				 * exist in the node. */
    }
    if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't unset private field \"",
			     key, "\"", (char *)NULL);
	}
	return TCL_ERROR;
    }
    SetModified(nodePtr);
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
        UpdateOldValue(clientPtr, valuePtr->objPtr);
        valuePtr->objPtr = NULL;
    }
    TreeDeleteValue(nodePtr, valuePtr);
    return CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key, TREE_TRACE_UNSET, &cnt);
}

static int
ParseParentheses(
    Tcl_Interp *interp,
    CONST char *string,
    char **leftPtr,
    char **rightPtr)
{
    register char *p;
    char *left, *right;

    left = right = NULL;
    for (p = (char *)string; *p != '\0'; p++) {
	if (*p == '(') {
	    left = p;
	} else if (*p == ')') {
	    right = p;
	}
    }
    if (left != right) {
	if (((left != NULL) && (right == NULL)) ||
	    ((left == NULL) && (right != NULL)) ||
	    (left > right) || (right != (p - 1))) {
	    if (interp != NULL) {
		Tcl_AppendResult(interp, "bad array specification \"", string,
			     "\"", (char *)NULL);
	    }
	    return TCL_ERROR;
	}
    }
    *leftPtr = left;
    *rightPtr = right;
    return TCL_OK;
}

int
Blt_TreeGetValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *string,		/* String identifying the field in node. */
    Tcl_Obj **objPtrPtr)
{
    char *left, *right;
    int result;

    if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
	return TCL_ERROR;
    }
    if (left != NULL) {
        Tcl_DString kStr, iStr;
        Tcl_DStringInit(&kStr);
        Tcl_DStringInit(&iStr);
        Tcl_DStringAppend(&kStr, left+1, right-left-1);
        Tcl_DStringAppend(&iStr, string, left-string);
	result = Blt_TreeGetArrayValue(interp, clientPtr, nodePtr,
	   Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), objPtrPtr);
	Tcl_DStringFree(&kStr);
	Tcl_DStringFree(&iStr);
    } else {
	result = Blt_TreeGetValueByKey(interp, clientPtr, nodePtr,
		Blt_TreeKeyGet(NULL, clientPtr->treeObject,string), objPtrPtr);
    }
    return result;
}

int
Blt_TreeSetValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *string,		/* String identifying the field in node. */
    Tcl_Obj *valueObjPtr)	/* New value of field. If NULL, field
				 * is deleted. */
{
    char *left, *right;
    int result;

    if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
        return Blt_TreeUpdateValue( interp, clientPtr, nodePtr, string, valueObjPtr);
    }
    if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
	return TCL_ERROR;
    }
    if (left != NULL) {
        Tcl_DString kStr, iStr;
        Tcl_DStringInit(&kStr);
        Tcl_DStringInit(&iStr);
        Tcl_DStringAppend(&kStr, left+1, right-left-1);
        Tcl_DStringAppend(&iStr, string, left-string);
        result = Blt_TreeSetArrayValue(interp, clientPtr, nodePtr,
	   Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), valueObjPtr);
	Tcl_DStringFree(&kStr);
	Tcl_DStringFree(&iStr);
    } else {
	result = Blt_TreeSetValueByKey(interp, clientPtr, nodePtr,
			       Blt_TreeKeyGet(NULL, clientPtr->treeObject,string), valueObjPtr);
    }
    return result;
}

int
Blt_TreeUpdateValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *string,		/* String identifying the field in node. */
    Tcl_Obj *valueObjPtr)	/* New value of field. If NULL, field
				 * is deleted. */
{
    char *left, *right;
    int result;
    Blt_TreeKey key;

    if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
	return TCL_ERROR;
    }
    if (left != NULL) {
        Tcl_DString kStr, iStr;
        Tcl_DStringInit(&kStr);
        Tcl_DStringInit(&iStr);
        Tcl_DStringAppend(&kStr, left+1, right-left-1);
        Tcl_DStringAppend(&iStr, string, left-string);
        result = Blt_TreeUpdateArrayValue(interp, clientPtr, nodePtr,
	   Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), valueObjPtr);
	Tcl_DStringFree(&kStr);
	Tcl_DStringFree(&iStr);
    } else {
        key = Blt_TreeKeyGet(NULL, clientPtr->treeObject,string);
        if (GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key) == NULL) {
            if (interp != NULL) {
                Tcl_AppendResult(interp, "unknown key: ", string, 0);
            }
            return TCL_ERROR;
        }
        result = Blt_TreeSetValueByKey(interp, clientPtr, nodePtr,
            key, valueObjPtr);
    }
    return result;
}

int
Blt_TreeUnsetValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *string)		/* String identifying the field in node. */
{
    char *left, *right;
    int result;

    if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
        if (interp != NULL) {
            Tcl_AppendResult(interp, "fixed field", 0);
        }
        return TCL_ERROR;
    }
    if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
	return TCL_ERROR;
    }
    if (left != NULL) {
        Tcl_DString kStr, iStr;
        Tcl_DStringInit(&kStr);
        Tcl_DStringInit(&iStr);
        Tcl_DStringAppend(&kStr, left+1, right-left-1);
        Tcl_DStringAppend(&iStr, string, left-string);
        result = Blt_TreeUnsetArrayValue(interp, clientPtr, nodePtr,
	   Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr));
	Tcl_DStringFree(&kStr);
	Tcl_DStringFree(&iStr);
    } else {
	result = Blt_TreeUnsetValueByKey(interp, clientPtr, nodePtr,
		Blt_TreeKeyGet(NULL, clientPtr->treeObject,string));
    }
    return result;
}

int
Blt_TreeValueExists(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
{
    char *left, *right;
    int result;

    if (ParseParentheses((Tcl_Interp *)NULL, string, &left, &right) != TCL_OK) {
	return FALSE;
    }
    if (left != NULL) {
        Tcl_DString kStr, iStr;
        Tcl_DStringInit(&kStr);
        Tcl_DStringInit(&iStr);
        Tcl_DStringAppend(&kStr, left+1, right-left-1);
        Tcl_DStringAppend(&iStr, string, left-string);
        result = Blt_TreeArrayValueExists(clientPtr, nodePtr,
	   Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr));
	Tcl_DStringFree(&kStr);
	Tcl_DStringFree(&iStr);
    } else {
	result = Blt_TreeValueExistsByKey(clientPtr, nodePtr,
		Blt_TreeKeyGet(NULL, clientPtr->treeObject,string));
    }
    return result;
}

Blt_TreeKey
Blt_TreeFirstKey(
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeKeySearch *iterPtr)
{
    Value *valuePtr;

    valuePtr = TreeFirstValue(nodePtr, iterPtr);
    if (valuePtr == NULL) {
	return NULL;
    }
    while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	valuePtr = TreeNextValue(iterPtr);
	if (valuePtr == NULL) {
	    return NULL;
	}
    }
    return valuePtr->key;
}

Blt_TreeKey
Blt_TreeNextKey(TreeClient *clientPtr, Blt_TreeKeySearch *iterPtr)
{
    Value *valuePtr;

    valuePtr = TreeNextValue(iterPtr);
    if (valuePtr == NULL) {
	return NULL;
    }
    while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	valuePtr = TreeNextValue(iterPtr);
	if (valuePtr == NULL) {
	    return NULL;
	}
    }
    return valuePtr->key;
}

int Blt_TreeCountKeys(TreeClient *clientPtr, Node *nodePtr) {
    int cnt = 0;
    Blt_TreeKey key;
    Blt_TreeKeySearch cursor;


    for (key = Blt_TreeFirstKey(clientPtr, nodePtr, &cursor); key != NULL;
        key = Blt_TreeNextKey(clientPtr, &cursor)) {
        cnt++;
    }
    return cnt;
}


int
Blt_TreeIsAncestor(Node *n1Ptr, Node *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(
    TreeClient *clientPtr,
    Node *nodePtr,
    Blt_TreeCompareNodesProc *proc)
{
    Node **nodeArr;
    Node *childPtr;
    int nNodes;
    register Node **p;

    nNodes = nodePtr->nChildren;
    if (nNodes < 2) {
	return TCL_OK;
    }
    nodeArr = Blt_Malloc((nNodes + 1) * sizeof(Node *));
    if (nodeArr == NULL) {
	return TCL_ERROR;	/* Out of memory. */
    }
    for (p = nodeArr, childPtr = nodePtr->first; childPtr != NULL;
	 childPtr = childPtr->next, p++) {
	*p = childPtr;
    }
    *p = NULL;

    qsort((char *)nodeArr, nNodes, sizeof(Node *), (QSortCompareProc *)proc);
    for (p = nodeArr; *p != NULL; p++) {
	UnlinkNode(*p);
	LinkBefore(nodePtr, *p, (Blt_TreeNode)NULL);
    }
    Blt_Free(nodeArr);
    return NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_SORT);
}

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

int
Blt_TreeApply(
    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. */
{
    Node *childPtr, *nextPtr;
    int result;

    for (childPtr = nodePtr->first; childPtr != NULL; childPtr = 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 = childPtr->next;
        if (Blt_TreeNodeDeleted(childPtr)) return TCL_OK;
	result = Blt_TreeApply(childPtr, proc, clientData);
	TEST_RESULT(result);
    }
    if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
    return (*proc) (nodePtr, clientData, TREE_POSTORDER);
}

int
Blt_TreeApplyDFS(
    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. */
{
    Node *childPtr, *nextPtr;
    int result;

    if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
    if (order & TREE_PREORDER) {
	result = (*proc) (nodePtr, clientData, TREE_PREORDER);
	TEST_RESULT(result);
    }
    childPtr = nodePtr->first;
    if (order & TREE_INORDER) {
	if (childPtr != NULL) {
	    result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
	    TEST_RESULT(result);
	    childPtr = childPtr->next;
	}
	result = (*proc) (nodePtr, clientData, TREE_INORDER);
	TEST_RESULT(result);
    }
    for (/* empty */; childPtr != NULL; childPtr = 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 = childPtr->next;
	if (Blt_TreeNodeDeleted(childPtr)) break;
	result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
	TEST_RESULT(result);
    }
    if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
    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_Chain *queuePtr;
    Blt_ChainLink *linkPtr, *nextPtr;
    Node *childPtr;
    int result;

    queuePtr = Blt_ChainCreate();
    linkPtr = Blt_ChainAppend(queuePtr, nodePtr);
    while (linkPtr != NULL) {
	nodePtr = Blt_ChainGetValue(linkPtr);
	/* Add the children to the queue. */
	for (childPtr = nodePtr->first; childPtr != NULL;
	     childPtr = childPtr->next) {
	    Blt_ChainAppend(queuePtr, childPtr);
	}
	if (Blt_TreeNodeDeleted(nodePtr)) break;
	/* 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(linkPtr);
	Blt_ChainDeleteLink(queuePtr, linkPtr);
	linkPtr = nextPtr;
    }
    Blt_ChainDestroy(queuePtr);
    return TCL_OK;
}

static TreeClient *
NewTreeClient(TreeObject *treeObjPtr, int sharetags)
{
    TreeClient *clientPtr;

    clientPtr = Blt_Calloc(1, sizeof(TreeClient));
    if (clientPtr != NULL) {
	Blt_TreeTagTable *tablePtr;
	int hascl = (treeObjPtr->clients->headPtr != NULL);

	clientPtr->magic = TREE_MAGIC;
	clientPtr->linkPtr = Blt_ChainAppend(treeObjPtr->clients, clientPtr);
	clientPtr->events = Blt_ChainCreate();
	clientPtr->traces = Blt_ChainCreate();
	clientPtr->treeObject = treeObjPtr;
	clientPtr->root = treeObjPtr->root;
	if (sharetags && hascl) {
             TreeClient *ctPtr;
             ctPtr = Blt_ChainGetValue(treeObjPtr->clients->headPtr);
             if (ctPtr && ctPtr->tagTablePtr) {
                 clientPtr->tagTablePtr = ctPtr->tagTablePtr;
                 clientPtr->tagTablePtr->refCount++;
             }
         }
         if (clientPtr->tagTablePtr == NULL) {
             tablePtr = Blt_Malloc(sizeof(Blt_TreeTagTable));
             Blt_InitHashTable(&tablePtr->tagTable, BLT_STRING_KEYS);
             tablePtr->refCount = 1;
             clientPtr->tagTablePtr = tablePtr;
         }
    }
    return clientPtr;
}

int
Blt_TreeCreate(
    Tcl_Interp *interp,		/* Interpreter to report errors back to. */
    CONST char *name,		/* Name of tree in namespace.  Tree
				 * must not already exist. */
    TreeClient **clientPtrPtr)	/* (out) Client token of newly created
				 * tree.  Releasing the token will
				 * free the tree.  If NULL, no token
				 * is generated. */

{
    Tcl_DString dString;
    Tcl_Namespace *nsPtr;
    TreeInterpData *dataPtr;
    TreeObject *treeObjPtr;
    CONST char *treeName;
    char string[200];

    dataPtr = GetTreeInterpData(interp);
    if (name != NULL) {
	/* Check if this tree already exists the current namespace. */
	treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_CURRENT);
	if (treeObjPtr != NULL) {
            if (interp != 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, string, NS_SEARCH_CURRENT) != NULL);
	name = string;
    }
    /*
     * Tear apart and put back together the namespace-qualified name
     * of the tree. This is to ensure that naming is consistent.
     */
    treeName = name;
    if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
        if (interp != NULL)
	   Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
		(char *)NULL);
	return TCL_ERROR;
    }
    if (nsPtr == NULL) {
	/*
	 * Note: Unlike Tcl_CreateCommand, an unqualified name
	 * doesn't imply the global namespace, but the current one.
	 */
	nsPtr = Tcl_GetCurrentNamespace(interp);
    }
    name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
    treeObjPtr = NewTreeObject(dataPtr, interp, name);
    if (treeObjPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't allocate tree \"", name, "\"",
		(char *)NULL);
	Tcl_DStringFree(&dString);
	return TCL_ERROR;
    }
    Tcl_DStringFree(&dString);
    if (clientPtrPtr != NULL) {
	TreeClient *clientPtr;

	clientPtr = NewTreeClient(treeObjPtr, 0);
	if (clientPtr == NULL) {
            if (interp != NULL)
	       Tcl_AppendResult(interp, "can't allocate tree token",(char *)NULL);
	    return TCL_ERROR;
	}
	*clientPtrPtr = clientPtr;
    }
    return TCL_OK;
}

int
Blt_TreeGetToken(
    Tcl_Interp *interp,		/* Interpreter to report errors back to. */
    CONST char *name,		/* Name of tree in namespace. */
    TreeClient **clientPtrPtr)
{
    TreeClient *clientPtr;
    TreeObject *treeObjPtr;

    treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
    if (treeObjPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"",
			 (char *)NULL);
	return TCL_ERROR;
    }
    clientPtr = NewTreeClient(treeObjPtr, 0);
    if (clientPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't allocate token for tree \"",
			 name, "\"", (char *)NULL);
	return TCL_ERROR;
    }
    *clientPtrPtr = clientPtr;
    return TCL_OK;
}

int
Blt_TreeGetTokenTag(
    Tcl_Interp *interp,		/* Interpreter to report errors back to. */
    CONST char *name,		/* Name of tree in namespace. */
    TreeClient **clientPtrPtr)
{
    TreeClient *clientPtr;
    TreeObject *treeObjPtr;

    treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
    if (treeObjPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"",
			 (char *)NULL);
	return TCL_ERROR;
    }
    clientPtr = NewTreeClient(treeObjPtr, 1);
    if (clientPtr == NULL) {
        if (interp != NULL)
            Tcl_AppendResult(interp, "can't allocate token for tree \"",
			 name, "\"", (char *)NULL);
	return TCL_ERROR;
    }
    *clientPtrPtr = clientPtr;
    return TCL_OK;
}

void
Blt_TreeReleaseToken(TreeClient *clientPtr)
{
    TreeObject *treeObjPtr;
    Blt_ChainLink *linkPtr;
    EventHandler *notifyPtr;
    TraceHandler *tracePtr;

    if (clientPtr->magic != TREE_MAGIC) {
	fprintf(stderr, "invalid tree object token 0x%lx\n",
		(unsigned long)clientPtr);
	return;
    }
    /* Remove any traces that may be set. */
    for (linkPtr = Blt_ChainFirstLink(clientPtr->traces); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	tracePtr = Blt_ChainGetValue(linkPtr);
	if (tracePtr->keyPattern != NULL) {
	    Blt_Free(tracePtr->keyPattern);
	}
	Blt_Free(tracePtr);
    }
    Blt_ChainDestroy(clientPtr->traces);
    /* And any event handlers. */
    for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	notifyPtr = Blt_ChainGetValue(linkPtr);
	if (notifyPtr->notifyPending) {
	    Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
	}
	Blt_Free(notifyPtr);
    }
    if (clientPtr->tagTablePtr != NULL) {
	ReleaseTagTable(clientPtr->tagTablePtr);
    }
    Blt_ChainDestroy(clientPtr->events);
    treeObjPtr = clientPtr->treeObject;
    if (treeObjPtr != NULL) {
	/* Remove the client from the server's list */
	Blt_ChainDeleteLink(treeObjPtr->clients, clientPtr->linkPtr);
	if (Blt_ChainGetLength(treeObjPtr->clients) == 0) {
	    treeObjPtr->delete = 1;
            Tcl_EventuallyFree(treeObjPtr, DestroyTreeObject);
	    /* DestroyTreeObject(treeObjPtr); */
	}
    }
    clientPtr->magic = 0;
    Blt_Free(clientPtr);
}

int
Blt_TreeExists(interp, name)
    Tcl_Interp *interp;		/* Interpreter to report errors back to. */
    CONST char *name;		/* Name of tree in designated namespace. */
{
    TreeObject *treeObjPtr;

    treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
    if (treeObjPtr == NULL) {
	Tcl_ResetResult(interp);
	return 0;
    }
    return 1;
}

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

int
Blt_TreeSize(Node *nodePtr)
{
    int sum;

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


void
Blt_TreeCreateEventHandler(
    TreeClient *clientPtr,
    unsigned int mask,
    Blt_TreeNotifyEventProc *proc,
    ClientData clientData)
{
    Blt_ChainLink *linkPtr;
    EventHandler *notifyPtr;

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

    /* Check if the event is already handled. */
    for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	notifyPtr = Blt_ChainGetValue(linkPtr);
	if ((notifyPtr->proc == proc) &&
	    (notifyPtr->mask == mask) &&
	    (notifyPtr->clientData == clientData)) {
	    break;
	}
    }
    if (linkPtr == NULL) {
	notifyPtr = Blt_Malloc(sizeof (EventHandler));
	assert(notifyPtr);
	linkPtr = Blt_ChainAppend(clientPtr->events, notifyPtr);
    }
    if (proc == NULL) {
	Blt_ChainDeleteLink(clientPtr->events, linkPtr);
	Blt_Free(notifyPtr);
    } else {
	notifyPtr->proc = proc;
	notifyPtr->clientData = clientData;
	notifyPtr->mask = mask;
	notifyPtr->notifyPending = FALSE;
	notifyPtr->interp = clientPtr->treeObject->interp;
    }
}

void
Blt_TreeDeleteEventHandler(
    TreeClient *clientPtr,
    unsigned int mask,
    Blt_TreeNotifyEventProc *proc,
    ClientData clientData)
{
    Blt_ChainLink *linkPtr;
    EventHandler *notifyPtr;

    if (!clientPtr) return;
    for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
	linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	notifyPtr = Blt_ChainGetValue(linkPtr);
	if ((notifyPtr->proc == proc) && (notifyPtr->mask == mask) &&
	    (notifyPtr->clientData == clientData)) {
	    if (notifyPtr->notifyPending) {
		Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
	    }
	    Blt_ChainDeleteLink(clientPtr->events, linkPtr);
	    Blt_Free(notifyPtr);
	    return;
	}
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeNodePath --
 *
 *----------------------------------------------------------------------
 */
char *
Blt_TreeNodePath(Node *nodePtr, Tcl_DString *resultPtr)
{
    CONST char **nameArr;		/* Used to stack the component names. */
    CONST char *staticSpace[64];
    int nLevels;
    register int i;

    nLevels = nodePtr->depth;
    if (nLevels > 64) {
	nameArr = Blt_Malloc(nLevels * sizeof(char *));
	assert(nameArr);
    } else {
	nameArr = staticSpace;
    }
    for (i = nLevels - 1; i >= 0; i--) {
	/* Save the name of each ancestor in the name array.
	 * Note that we ignore the root. */
	nameArr[i] = nodePtr->label;
	nodePtr = nodePtr->parent;
    }
    /* Append each the names in the array. */
    Tcl_DStringInit(resultPtr);
    for (i = 0; i < nLevels; i++) {
	Tcl_DStringAppendElement(resultPtr, nameArr[i]);
    }
    if (nameArr != staticSpace) {
	Blt_Free(nameArr);
    }
    return Tcl_DStringValue(resultPtr);
}

char *
Blt_TreeNodePathStr(Node *nodePtr, Tcl_DString *resultPtr, char *prefix, char *delim)
{
    CONST char **nameArr;		/* Used to stack the component names. */
    CONST char *staticSpace[64];
    int nLevels;
    register int i;

    nLevels = nodePtr->depth;
    if (nLevels > 64) {
	nameArr = Blt_Malloc(nLevels * sizeof(char *));
	assert(nameArr);
    } else {
	nameArr = staticSpace;
    }
    for (i = nLevels - 1; i >= 0; i--) {
	/* Save the name of each ancestor in the name array.
	 * Note that we ignore the root. */
	nameArr[i] = nodePtr->label;
	nodePtr = nodePtr->parent;
    }
    /* Append each of the names in the array. */
    Tcl_DStringInit(resultPtr);
    if (prefix != NULL) {
        Tcl_DStringAppend(resultPtr, prefix, -1);
    }
    for (i = 0; i < nLevels; i++) {
        if (i > 0 && delim != NULL) {
            Tcl_DStringAppend(resultPtr, delim, -1);
        }
        Tcl_DStringAppend(resultPtr, nameArr[i], -1);
    }
    if (nameArr != staticSpace) {
	Blt_Free(nameArr);
    }
    return Tcl_DStringValue(resultPtr);
}

int
Blt_TreeArrayValueExists(
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *arrayName,
    CONST char *elemName)
{
    Blt_TreeKey key;
    Blt_HashEntry *hPtr;
    Blt_HashTable *tablePtr;
    register Value *valuePtr;
    int cnt;
    TreeObject *treeObjPtr = nodePtr->treeObject;
    Tcl_Interp *interp = treeObjPtr->interp;

    key = Blt_TreeKeyGet(NULL, clientPtr->treeObject,arrayName);

    valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
    if (valuePtr == NULL && (!(nodePtr->flags & TREE_TRACE_ACTIVE))) {
        if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
            TREE_TRACE_EXISTS, &cnt) != TCL_OK) {
                Tcl_ResetResult(interp);
            } else {
                valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
            }
    }
    if (valuePtr == NULL) {
	return FALSE;
    }
    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */
        int result;
        Tcl_Obj *keyPtr, *valueObjPtr = NULL;

        keyPtr = Tcl_NewStringObj(elemName, -1);
        Tcl_IncrRefCount(keyPtr);
        result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valueObjPtr);
        Tcl_DecrRefCount(keyPtr);
        if (result != TCL_OK) {
            return FALSE;
        }
        if (valueObjPtr == NULL) {
            return FALSE;
        }
        return TRUE;
    }

    if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }
    if (Blt_GetArrayFromObj((Tcl_Interp *)NULL, valuePtr->objPtr, &tablePtr)
	!= TCL_OK) {
	return FALSE;
    }
    hPtr = Blt_FindHashEntry(tablePtr, elemName);
    return (hPtr != NULL);
}

int
Blt_TreeGetArrayValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *arrayName,
    CONST char *elemName,
    Tcl_Obj **valueObjPtrPtr)
{
    Blt_TreeKey key;
    Blt_HashEntry *hPtr;
    Blt_HashTable *tablePtr;
    register Value *valuePtr;
    int cnt = 0;

    key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);

    /* Reading any element of the array can cause a trace to fire. */
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
        if (CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr, key,
            TREE_TRACE_READ, &cnt) != TCL_OK) {
                return TCL_ERROR;
        }
    }
    valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
    if (valuePtr == NULL) {
	return TCL_ERROR;
    }
    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */
        int result;
        Tcl_Obj *keyPtr;
        keyPtr = Tcl_NewStringObj(elemName, -1);
        Tcl_IncrRefCount(keyPtr);
        result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, valueObjPtrPtr);
        Tcl_DecrRefCount(keyPtr);
        if (result != TCL_OK) {
            return result;
        }
        if (*valueObjPtrPtr == NULL) {
            if (interp != NULL) {
                Tcl_AppendResult(interp, "can't find \"", arrayName, "(",
                    elemName, ")\"", (char *)NULL);
            }
            return TCL_ERROR;
        }
        return TCL_OK;
    }
    if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }
    if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    hPtr = Blt_FindHashEntry(tablePtr, elemName);
    if (hPtr == NULL) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't find \"", arrayName, "(",
			     elemName, ")\"", (char *)NULL);
	}
	return TCL_ERROR;
    }

    *valueObjPtrPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
    return TCL_OK;
}

static int
TreeSetArrayValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *arrayName,
    CONST char *elemName,
    Tcl_Obj *valueObjPtr,	/* New value of element. */
    int create)           /* Create the node key if required. */
{
    Blt_TreeKey key;
    Blt_HashEntry *hPtr;
    Blt_HashTable *tablePtr;
    register Value *valuePtr;
    unsigned int flags;
    int isNew, cnt = 0;

    assert(valueObjPtr != NULL);

    /*
     * Search for the array in the list of data fields.  If one
     * doesn't exist, create it.
     */
    key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
    valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
    if (valuePtr == NULL && create == 0) {
        return TCL_ERROR;
    }
    if (valuePtr == NULL) {
        if ((nodePtr->flags & TREE_NODE_FIXED_FIELDS)) {
            return TCL_ERROR;
        }
        valuePtr = TreeCreateValue(nodePtr, key, &isNew);
        isNew = 1;
    } else {
        isNew = 0;
    }
    if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't set private field \"",
			     key, "\"", (char *)NULL);
	}
	return TCL_ERROR;
    }
    flags = TREE_TRACE_WRITE;
    if (isNew) {
	valuePtr->objPtr = Blt_NewArrayObj(0, (Tcl_Obj **)NULL);
	Tcl_IncrRefCount(valuePtr->objPtr);
	flags |= TREE_TRACE_CREATE;

     } else if (Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }

    if ((clientPtr->treeObject->flags & TREE_DICT_KEYS) &&
        IsTclDict(interp, valuePtr->objPtr)) {
        int dSiz;

        if (Tcl_DictObjSize(interp, valuePtr->objPtr, &dSiz) != TCL_OK) {
            return TCL_ERROR;
        }
    }
    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */
        int result;
        Tcl_Obj *keyPtr, *valObjPtr;

        keyPtr = Tcl_NewStringObj(elemName, -1);
        Tcl_IncrRefCount(keyPtr);
        if (!create) {
            result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valObjPtr);
            if (result != TCL_OK || valObjPtr == NULL) {
                Tcl_AppendResult(interp, "can't find field: ", elemName, 0);
                Tcl_DecrRefCount(keyPtr);
                return TCL_ERROR;
            }
        }
        result = Tcl_DictObjPut(interp, valuePtr->objPtr, keyPtr, valueObjPtr);
        Tcl_DecrRefCount(keyPtr);
        if (result != TCL_OK) {
            return result;
        }
        goto finishset;
    }


    if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    Tcl_InvalidateStringRep(valuePtr->objPtr);
    if (create) {
        hPtr = Blt_CreateHashEntry(tablePtr, elemName, &isNew);
        assert(hPtr);
    } else {
        hPtr = Blt_FindHashEntry(tablePtr, elemName);
        if (hPtr == NULL) {
            if (interp != NULL) {
                Tcl_AppendResult(interp, "can't find array field: ", elemName, 0);
            }
            return TCL_ERROR;
        }
        isNew = 0;
    }

    SetModified(nodePtr);
    Tcl_IncrRefCount(valueObjPtr);
    if (!isNew) {
	Tcl_Obj *oldValueObjPtr;

	/* An element by the same name already exists. Decrement the
	 * reference count of the old value. */

	oldValueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
        if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
            UpdateOldValue(clientPtr, oldValueObjPtr);
            oldValueObjPtr = NULL;
        }
	if (oldValueObjPtr != NULL) {
	    Tcl_DecrRefCount(oldValueObjPtr);
	}
    } else {
        if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
            UpdateOldValue(clientPtr, NULL);
        }
    }
    Blt_SetHashValue(hPtr, valueObjPtr);

finishset:
    /*
     * We don't handle traces on a per array element basis.  Setting
     * any element can fire traces for the value.
     */
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	return CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
		valuePtr->key, flags, &cnt);
    }
    return TCL_OK;
}

int
Blt_TreeSetArrayValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *arrayName,
    CONST char *elemName,
    Tcl_Obj *valueObjPtr)	/* New value of element. */
{
    return TreeSetArrayValue(interp, clientPtr, nodePtr, arrayName, elemName, valueObjPtr, 1);
}

int
Blt_TreeUpdateArrayValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *arrayName,
    CONST char *elemName,
    Tcl_Obj *valueObjPtr)	/* New value of element. */
{
    return TreeSetArrayValue(interp, clientPtr, nodePtr, arrayName, elemName, valueObjPtr, 0);
}

int
Blt_TreeUnsetArrayValue(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,		/* Node to be updated. */
    CONST char *arrayName,
    CONST char *elemName)
{
    Blt_TreeKey key;		/* Name of field in node. */
    Blt_HashEntry *hPtr;
    Blt_HashTable *tablePtr;
    Tcl_Obj *valueObjPtr;
    Value *valuePtr;
    int cnt = 0;

    key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
    valuePtr = TreeFindValue(nodePtr, key);
    if (valuePtr == NULL) {
	return TCL_OK;
    }
    if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
	if (interp != NULL) {
	    Tcl_AppendResult(interp, "can't unset private field \"",
			     key, "\"", (char *)NULL);
	}
	return TCL_ERROR;
    }

    if (Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }

    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */
        int result;
        Tcl_Obj *keyPtr;
        keyPtr = Tcl_NewStringObj(elemName, -1);
        Tcl_IncrRefCount(keyPtr);
        result = Tcl_DictObjRemove(interp, valuePtr->objPtr, keyPtr);
        Tcl_DecrRefCount(keyPtr);
        if (result != TCL_OK) {
            return result;
        }
        goto finishrm;
    }

    if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    hPtr = Blt_FindHashEntry(tablePtr, elemName);
    if (hPtr == NULL) {
        goto finishrm; /* Element doesn't exist, Ok. */
    }
    SetModified(nodePtr);
    valueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
        UpdateOldValue(clientPtr, valueObjPtr);
    } else {
        Tcl_DecrRefCount(valueObjPtr);
    }
    Blt_DeleteHashEntry(tablePtr, hPtr);
    Tcl_InvalidateStringRep(valuePtr->objPtr);

finishrm:
    /*
     * Un-setting any element in the array can cause the trace on the value
     * to fire.
     */
    if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
	return CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
		valuePtr->key, TREE_TRACE_WRITE, &cnt);
    }
    return TCL_OK;
}

int
Blt_TreeArrayNames(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *arrayName,
    Tcl_Obj *listObjPtr,
    CONST char *pattern)
{
    Blt_HashEntry *hPtr;
    Blt_HashSearch cursor;
    Blt_HashTable *tablePtr;
    Tcl_Obj *objPtr;
    Value *valuePtr;
    CONST char *key;

    key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
    valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
    if (valuePtr == NULL) {
	return TCL_ERROR;
    }
    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */

        Tcl_DictSearch search;
        Tcl_Obj *keyPtr;
        int done;

        Tcl_DictObjFirst(NULL, valuePtr->objPtr, &search, &keyPtr, NULL, &done);
        for (; !done ; Tcl_DictObjNext(&search, &keyPtr, NULL, &done)) {
            if (!pattern || Tcl_StringMatch(Tcl_GetString(keyPtr), pattern)) {
                Tcl_ListObjAppendElement(NULL, listObjPtr, keyPtr);
            }
        }
        Tcl_DictObjDone(&search);
        return TCL_OK;
    }

    if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }
    if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    /*tablePtr = (Blt_HashTable *)valuePtr->objPtr; */
    for (hPtr = Blt_FirstHashEntry(tablePtr, &cursor); hPtr != NULL;
	 hPtr = Blt_NextHashEntry(&cursor)) {
	 char *str;

	 str = Blt_GetHashKey(tablePtr, hPtr);
         if (pattern == NULL || Tcl_StringMatch(str, pattern)) {
             objPtr = Tcl_NewStringObj(str, -1);
             Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
         }
    }
    return TCL_OK;
}

int
Blt_TreeArrayValues(
    Tcl_Interp *interp,
    TreeClient *clientPtr,
    Node *nodePtr,
    CONST char *arrayName,
    Tcl_Obj *listObjPtr,
    int names)
{
    Blt_HashEntry *hPtr;
    Blt_HashSearch cursor;
    Blt_HashTable *tablePtr;
    Tcl_Obj *objPtr;
    Value *valuePtr;
    CONST char *key;

    key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
    if ( bltTreeGetValueByKey(interp, clientPtr, nodePtr, key, &valuePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    if (IsTclDict(interp, valuePtr->objPtr)) {
        /* Preserve type if this was a dict */

        Tcl_DictSearch search;
        Tcl_Obj *keyPtr;
        int done;
        int result;

        Tcl_DictObjFirst(NULL, valuePtr->objPtr, &search, &keyPtr, NULL, &done);
        for (; !done ; Tcl_DictObjNext(&search, &keyPtr, NULL, &done)) {
            Tcl_Obj *valueObjPtr;
            if (names) {
                Tcl_ListObjAppendElement(NULL, listObjPtr, keyPtr);
            }

            valueObjPtr = NULL;
            result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valueObjPtr);
            if (result != TCL_OK) {
                continue;
            }
            if (valueObjPtr == NULL) {
                valueObjPtr = Tcl_NewStringObj("",-1);
            }
            Tcl_ListObjAppendElement(NULL, listObjPtr, valueObjPtr);
        }
        Tcl_DictObjDone(&search);
        return TCL_OK;
    }
    if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
	Tcl_DecrRefCount(valuePtr->objPtr);
	valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
	Tcl_IncrRefCount(valuePtr->objPtr);
    }
    if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
	return TCL_ERROR;
    }
    /*tablePtr = (Blt_HashTable *)valuePtr->objPtr; */
    for (hPtr = Blt_FirstHashEntry(tablePtr, &cursor); hPtr != NULL;
	 hPtr = Blt_NextHashEntry(&cursor)) {
	if (names) {
             Tcl_ListObjAppendElement(interp, listObjPtr,
                Tcl_NewStringObj( Blt_GetHashKey(tablePtr, hPtr), -1));
        }
	objPtr = Blt_GetHashValue(hPtr);
	Tcl_ListObjAppendElement(interp, listObjPtr, objPtr?objPtr:Tcl_NewStringObj("",-1));
    }
    return TCL_OK;
}


/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeShareTagTable --
 *
 *----------------------------------------------------------------------
 */
int
Blt_TreeShareTagTable(
    TreeClient *sourcePtr,
    TreeClient *targetPtr)
{
    sourcePtr->tagTablePtr->refCount++;
    if (targetPtr->tagTablePtr != NULL) {
	ReleaseTagTable(targetPtr->tagTablePtr);
    }
    targetPtr->tagTablePtr = sourcePtr->tagTablePtr;
    return TCL_OK;
}

int
Blt_TreeTagTableIsShared(TreeClient *clientPtr)
{
    return (clientPtr->tagTablePtr->refCount > 1);
}

void
Blt_TreeClearTags(TreeClient *clientPtr, Blt_TreeNode node)
{
    Blt_HashEntry *hPtr, *h2Ptr;
    Blt_HashSearch cursor;

    for (hPtr = Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, &cursor);
	hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
	Blt_TreeTagEntry *tPtr;

	tPtr = Blt_GetHashValue(hPtr);
	h2Ptr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
	if (h2Ptr != NULL) {
             SetModified(node);
             Blt_DeleteHashEntry(&tPtr->nodeTable, h2Ptr);
	}
    }
}

int
Blt_TreeHasTag(
    TreeClient *clientPtr,
    Blt_TreeNode node,
    CONST char *tagName)
{
    Blt_HashEntry *hPtr;
    Blt_TreeTagEntry *tPtr;

    if (strcmp(tagName, "all") == 0) {
	return TRUE;
    }
    if (strcmp(tagName, "nonroot") == 0) {
        return TRUE;
    }
    if (strcmp(tagName, "rootchildren") == 0) {
        return TRUE;
    }
    if ((strcmp(tagName, "root") == 0) &&
	(node == Blt_TreeRootNode(clientPtr))) {
	return TRUE;
    }
    hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
    if (hPtr == NULL) {
	return FALSE;
    }
    tPtr = Blt_GetHashValue(hPtr);
    hPtr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
    if (hPtr == NULL) {
	return FALSE;
    }
    return TRUE;
}

int
Blt_TreeAddTag(
    TreeClient *clientPtr,
    Blt_TreeNode node,
    CONST char *tagName)
{
    int isNew, isNewN, cnt = 0, flags;
    Blt_HashEntry *hPtr;
    Blt_HashTable *tablePtr;
    Blt_TreeTagEntry *tPtr;
    Tcl_Interp *interp = clientPtr->treeObject->interp;

    if ((strcmp(tagName, "all") == 0) || (strcmp(tagName, "root") == 0)
        || (strcmp(tagName, "nonroot") == 0) || (strcmp(tagName, "rootchildren") == 0)) {
        Tcl_AppendResult(interp, "reserved tag", 0);
	return TCL_ERROR;
    }
    tablePtr = &clientPtr->tagTablePtr->tagTable;
    hPtr = Blt_CreateHashEntry(tablePtr, tagName, &isNewN);
    assert(hPtr);
    if (isNewN) {

	tPtr = Blt_Calloc(sizeof(Blt_TreeTagEntry), 1);
	Blt_InitHashTable(&tPtr->nodeTable, BLT_ONE_WORD_KEYS);
	Blt_SetHashValue(hPtr, tPtr);
	tPtr->hashPtr = hPtr;
	tPtr->tagName = Blt_GetHashKey(tablePtr, hPtr);
        Blt_TreeTagRefIncr(tPtr);
     } else {
	tPtr = Blt_GetHashValue(hPtr);
    }
    if (node == NULL) {
        return TCL_OK;
    }
    if (!(node->flags & TREE_TRACE_ACTIVE)) {
        int result;
        flags = TREE_TRACE_TAGADD;
        if (tPtr->nodeTable.numEntries > 0) {
            flags |= TREE_TRACE_TAGMULTIPLE;
        }
        result = CallTraces(interp, clientPtr, node->treeObject, node, tagName,
            flags, &cnt);
        if (result == TCL_BREAK) {
            return TCL_OK;
        }
        if (result != TCL_OK) {
            return result;
        }
    }
    hPtr = Blt_CreateHashEntry(&tPtr->nodeTable, (char *)node, &isNew);
    assert(hPtr);
    if (isNew) {
        SetModified(node);
        Blt_SetHashValue(hPtr, node);
    }
    return TCL_OK;
}

/* Trigger tag delete traces. */
int
Blt_TreeTagDelTrace(
    TreeClient *clientPtr,
    Blt_TreeNode node,
    CONST char *tagName)
{
    Tcl_Interp *interp = clientPtr->treeObject->interp;
    int cnt;

    if (!(node->flags & TREE_TRACE_ACTIVE)) {
        return CallTraces(interp, clientPtr, node->treeObject, node, tagName,
            (TREE_TRACE_TAGDELETE), &cnt);
    }
    return TCL_OK;
}

int
Blt_TreeForgetTag(TreeClient *clientPtr, CONST char *tagName)
{
    Blt_HashEntry *hPtr;
    if ((strcmp(tagName, "all") == 0) || (strcmp(tagName, "root") == 0)
       || (strcmp(tagName, "nonroot") == 0)
       || (strcmp(tagName, "rootchildren") == 0)) {
       return TCL_OK;
    }

    hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
    if (hPtr != NULL) {
        Blt_TreeTagEntry *tPtr;
        Blt_TreeNode node;
        Blt_HashSearch cursor;

        Blt_DeleteHashEntry(&clientPtr->tagTablePtr->tagTable, hPtr);
        tPtr = Blt_GetHashValue(hPtr);
        for (hPtr = Blt_FirstHashEntry(&tPtr->nodeTable, &cursor);
            hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {

            node = Blt_GetHashKey(&tPtr->nodeTable, hPtr);
            if (Blt_TreeTagDelTrace(clientPtr, node, tagName) != TCL_OK) {
                return TCL_ERROR;
            }
            SetModified(node);
        }
        Blt_DeleteHashTable(&tPtr->nodeTable);
        Blt_TreeTagRefDecr(tPtr);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeTagHashTable --
 *
 *----------------------------------------------------------------------
 */
Blt_HashTable *
Blt_TreeTagHashTable(TreeClient *clientPtr, CONST char *tagName)
{
    Blt_HashEntry *hPtr;

    hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
    if (hPtr != NULL) {
	Blt_TreeTagEntry *tPtr;

	tPtr = Blt_GetHashValue(hPtr);
	return &tPtr->nodeTable;
    }
    return NULL;
}

Blt_TreeTagEntry *
Blt_TreeTagHashEntry(TreeClient *clientPtr, CONST char *tagName)
{
    Blt_HashEntry *hPtr;

    hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
    if (hPtr != NULL) {
	Blt_TreeTagEntry *tPtr;

	tPtr = Blt_GetHashValue(hPtr);
	return tPtr;
    }
    return NULL;
}

Blt_HashEntry *
Blt_TreeFirstTag(TreeClient *clientPtr, Blt_HashSearch *cursorPtr)
{
    return Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, cursorPtr);
}

#if (SIZEOF_VOID_P == 8)
/*
 *----------------------------------------------------------------------
 *
 * HashOneWord --
 *
 *	Compute a one-word hash value of a 64-bit word, which then can
 *	be used to generate a hash index.
 *
 *	From Knuth, it's a multiplicative hash.  Multiplies an unsigned
 *	64-bit value with the golden ratio (sqrt(5) - 1) / 2.  The
 *	downshift value is 64 - n, when n is the log2 of the size of
 *	the hash table.
 *
 * Results:
 *	The return value is a one-word summary of the information in
 *	64 bit word.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static Blt_Hash
HashOneWord(
    uint64_t mask,
    unsigned int downshift,
    CONST void *key)
{
    uint64_t a0, a1;
    uint64_t y0, y1;
    uint64_t y2, y3;
    uint64_t p1, p2;
    uint64_t result;

    /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
    a0 = (uint64_t)key & 0x00000000FFFFFFFF;
    a1 = (uint64_t)key >> 32;

    y0 = a0 * 0x000000007f4a7c13;
    y1 = a0 * 0x000000009e3779b9;
    y2 = a1 * 0x000000007f4a7c13;
    y3 = a1 * 0x000000009e3779b9;
    y1 += y0 >> 32;		/* Can't carry */
    y1 += y2;			/* Might carry */
    if (y1 < y2) {
	y3 += (1LL << 32);	/* Propagate */
    }

    /* 128-bit product: p1 = loword, p2 = hiword */
    p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
    p2 = y3 + (y1 >> 32);

    /* Left shift the value downward by the size of the table */
    if (downshift > 0) {
	if (downshift < 64) {
	    result = ((p2 << (64 - downshift)) | (p1 >> (downshift & 63)));
	} else {
	    result = p2 >> (downshift & 63);
	}
    } else {
	result = p1;
    }
    /* Finally mask off the high bits */
    return (Blt_Hash)(result & mask);
}

#endif /* SIZEOF_VOID_P == 8 */

/*
 *----------------------------------------------------------------------
 *
 * RebuildTable --
 *
 *	This procedure is invoked when the ratio of entries to hash
 *	buckets becomes too large.  It creates a new table with a
 *	larger bucket array and moves all of the entries into the
 *	new table.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Memory gets reallocated and entries get re-hashed to new
 *	buckets.
 *
 *----------------------------------------------------------------------
 */
static void
RebuildTable(Node *nodePtr)		/* Table to enlarge. */
{
    Value **newBucketPtr, **oldBuckets;
    register Value **bucketPtr, **endPtr;
    register Value *valuePtr, *nextPtr;
    unsigned int downshift;
    unsigned long mask;
    Value **buckets;
    size_t nBuckets;

    oldBuckets = (Value **)nodePtr->values;
    nBuckets = (1 << nodePtr->logSize);
    endPtr = oldBuckets + nBuckets;

    /*
     * Allocate and initialize the new bucket array, and set up
     * hashing constants for new array size.
     */
    nodePtr->logSize += 2;
    nBuckets = (1 << nodePtr->logSize);
    buckets = Blt_Calloc(nBuckets, sizeof(Value *));

    /*
     * Move all of the existing entries into the new bucket array,
     * based on their hash values.
     */
    mask = nBuckets - 1;
    downshift = DOWNSHIFT_START - nodePtr->logSize;
    for (bucketPtr = oldBuckets; bucketPtr < endPtr; bucketPtr++) {
	for (valuePtr = *bucketPtr; valuePtr != NULL; valuePtr = nextPtr) {
	    nextPtr = valuePtr->next;
	    newBucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
	    valuePtr->next = *newBucketPtr;
	    *newBucketPtr = valuePtr;
	}
    }
    nodePtr->values = (Value *)buckets;
    Blt_Free(oldBuckets);
}

static void
ConvertValues(Node *nodePtr)
{
    unsigned int nBuckets;
    Value **buckets;
    unsigned int mask;
    int downshift;
    Value *valuePtr, *nextPtr, **bucketPtr;

    /*
     * Convert list of values into a hash table.
     */
    nodePtr->logSize = START_LOGSIZE;
    nBuckets = 1 << nodePtr->logSize;
    buckets = Blt_Calloc(nBuckets, sizeof(Value *));
    mask = nBuckets - 1;
    downshift = DOWNSHIFT_START - nodePtr->logSize;
    for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
	nextPtr = valuePtr->next;
	bucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
	valuePtr->next = *bucketPtr;
	*bucketPtr = valuePtr;
    }
    nodePtr->values = (Value *)buckets;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeDeleteValue --
 *
 *	Remove a single entry from a hash table.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The entry given by entryPtr is deleted from its table and
 *	should never again be used by the caller.  It is up to the
 *	caller to free the clientData field of the entry, if that
 *	is relevant.
 *
 *----------------------------------------------------------------------
 */
static int
TreeDeleteValue(Node *nodePtr, Blt_TreeValue value)
{
    Value *valuePtr = value;
    register Value *prevPtr;

    if (nodePtr->logSize > 0) {
	Value **bucketPtr;
	unsigned int downshift;
	unsigned long mask;

	mask = (1 << nodePtr->logSize) - 1;
	downshift = DOWNSHIFT_START - nodePtr->logSize;

	bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX(valuePtr->key);
	if (*bucketPtr == valuePtr) {
	    *bucketPtr = valuePtr->next;
	} else {
	    for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->next) {
		if (prevPtr == NULL) {
		    return TCL_ERROR; /* Can't find value in hash bucket. */
		}
		if (prevPtr->next == valuePtr) {
		    prevPtr->next = valuePtr->next;
		    break;
		}
	    }
	}
    } else {
	prevPtr = NULL;
	for (valuePtr = nodePtr->values; valuePtr != NULL;
	     valuePtr = valuePtr->next) {
	    if (valuePtr == value) {
		break;
	    }
	    prevPtr = valuePtr;
	}
	if (valuePtr == NULL) {
	    return TCL_ERROR;	/* Can't find value in list. */
	}
	if (prevPtr == NULL) {
	    nodePtr->values = valuePtr->next;
	} else {
	    prevPtr->next = valuePtr->next;
	}
    }
    nodePtr->nValues--;
    FreeValue(nodePtr, valuePtr);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeDestroyValues --
 *
 *	Free up everything associated with a hash table except for
 *	the record for the table itself.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The hash table is no longer useable.
 *
 *----------------------------------------------------------------------
 */
static void
TreeDestroyValues(Node *nodePtr)
{
    register Value *valuePtr;
    Value *nextPtr;

    /*
     * Free up all the entries in the table.
     */
    if (nodePtr->values == NULL) {
	return;
    }
    if (nodePtr->logSize > 0) {
	Value **buckets;
	int nBuckets;
	int i;

	buckets = (Value **)nodePtr->values;
	nBuckets = (1 << nodePtr->logSize);
	for (i = 0; i < nBuckets; i++) {
	    for (valuePtr = buckets[i]; valuePtr != NULL; valuePtr = nextPtr) {
		nextPtr = valuePtr->next;
		FreeValue(nodePtr, valuePtr);
	    }
	}
	Blt_Free(buckets);
    } else {
	for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
	    nextPtr = valuePtr->next;
	    FreeValue(nodePtr, valuePtr);
	}
    }
    nodePtr->values = NULL;
    nodePtr->nValues = 0;
    nodePtr->logSize = 0;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeFirstValue --
 *
 *	Locate the first entry in a hash table and set up a record
 *	that can be used to step through all the remaining entries
 *	of the table.
 *
 * Results:
 *	The return value is a pointer to the first value in tablePtr,
 *	or NULL if tablePtr has no entries in it.  The memory at
 *	*searchPtr is initialized so that subsequent calls to
 *	Blt_TreeNextValue will return all of the values in the table,
 *	one at a time.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static Value *
TreeFirstValue(
    Node *nodePtr,
    Blt_TreeKeySearch *searchPtr) /* Place to store information about
				   * progress through the table. */
{
    searchPtr->node = nodePtr;
    searchPtr->nextIndex = 0;
    searchPtr->cnt = 1;
    if (nodePtr->logSize > 0) {
	searchPtr->nextValue = NULL;
    } else {
	searchPtr->nextValue = nodePtr->values;
    }
    return TreeNextValue(searchPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * TreeNextValue --
 *
 *	Once a hash table enumeration has been initiated by calling
 *	Blt_TreeFirstValue, this procedure may be called to return
 *	successive elements of the table.
 *
 * Results:
 *	The return value is the next entry in the hash table being
 *	enumerated, or NULL if the end of the table is reached.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static Value *
TreeNextValue(
    Blt_TreeKeySearch *searchPtr) /* Place to store information about
				   * progress through the table.  Must
				   * have been initialized by calling
				   * Blt_TreeFirstValue. */
{
    Value *valuePtr;

    if (searchPtr->node->logSize > 0) {
	size_t nBuckets;
	Value **buckets;

	nBuckets = (1 << searchPtr->node->logSize);
	buckets = (Value **)searchPtr->node->values;
	while (searchPtr->nextValue == NULL) {
	    if (searchPtr->nextIndex >= nBuckets) {
		return NULL;
	    }
	    searchPtr->nextValue = buckets[searchPtr->nextIndex];
	    searchPtr->nextIndex++;
	}
    }
    searchPtr->cnt++;
    /* Sanity check. */
    if (searchPtr->cnt>100000000) return NULL;
    valuePtr = searchPtr->nextValue;
    if (valuePtr != NULL) {
        searchPtr->nextValue = valuePtr->next;
    }
    return valuePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeFindValue --
 *
 *	Given a hash table with one-word keys, and a one-word key, find
 *	the entry with a matching key.
 *
 * Results:
 *	The return value is a token for the matching entry in the
 *	hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */
static Value *
TreeFindValue(
    Node *nodePtr,
    Blt_TreeKey key)		/* Key to use to find matching entry. */
{
    register Value *valuePtr;
    Value *bucket;

    if (nodePtr->logSize > 0) {
	unsigned int downshift;
	unsigned long mask;

	mask = (1 << nodePtr->logSize) - 1;
	downshift = DOWNSHIFT_START - nodePtr->logSize;
	bucket = ((Value **)(nodePtr->values))[RANDOM_INDEX((void *)key)];
    } else {
	bucket = nodePtr->values; /* Single chain list. */
    }
    /*
     * Search all of the entries in the appropriate bucket.
     */
    for (valuePtr = bucket; valuePtr != NULL; valuePtr = valuePtr->next) {
	if (valuePtr->key == key) {
	    return valuePtr;
	}
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_TreeCreateValue --
 *
 *	Find the value with a matching key.  If there is no matching
 *	value, then create a new one.
 *
 * Results:
 *	The return value is a pointer to the matching value.  If this
 *	is a newly-created value, then *newPtr will be set to a non-zero
 *	value;  otherwise *newPtr will be set to 0.
 *
 * Side effects:
 *	A new value may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */
static Value *
TreeCreateValue(
    Node *nodePtr,
    Blt_TreeKey key,		/* Key to use to find or create matching
				 * entry. */
    int *newPtr)		/* Store info here telling whether a new
				 * entry was created. */
{
    register Value *valuePtr;
    TreeObject *treeObjPtr = nodePtr->treeObject;
    int maxVals;

    if (treeObjPtr->maxKeyList>0) {
        maxVals = treeObjPtr->maxKeyList;
    } else {
        maxVals = MAX_LIST_VALUES;
    }
    /*
     * Check if there as so many values that storage should be
     * converted from a hash table instead of a list.
     */
    if ((nodePtr->logSize == 0) && (nodePtr->nValues >= maxVals)) {
	ConvertValues(nodePtr);
    }
    if (nodePtr->logSize > 0) {
	Value **bucketPtr;
	size_t nBuckets;
	unsigned int downshift;
	unsigned long mask;

	nBuckets = (1 << nodePtr->logSize);
	mask = nBuckets - 1;
	downshift = DOWNSHIFT_START - nodePtr->logSize;
	bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX((void *)key);

	*newPtr = FALSE;
	for (valuePtr = *bucketPtr; valuePtr != NULL;
	     valuePtr = valuePtr->next) {
	    if (valuePtr->key == key) {
		return valuePtr;
	    }
	}

	/* Value not found. Add a new value to the bucket. */
	*newPtr = TRUE;
	valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
		sizeof(Value));
	valuePtr->key = key;
	valuePtr->owner = NULL;
	valuePtr->next = *bucketPtr;
	valuePtr->objPtr = NULL;
	*bucketPtr = valuePtr;
	nodePtr->nValues++;

	/*
	 * If the table has exceeded a decent size, rebuild it with many
	 * more buckets.
	 */
	if ((unsigned int)nodePtr->nValues >= (nBuckets * 3)) {
	    RebuildTable(nodePtr);
	}
    } else {
	Value *prevPtr;

	prevPtr = NULL;
	*newPtr = FALSE;
	for (valuePtr = nodePtr->values; valuePtr != NULL;
	     valuePtr = valuePtr->next) {
	    if (valuePtr->key == key) {
		return valuePtr;
	    }
	    prevPtr = valuePtr;
	}
	/* Value not found. Add a new value to the list. */
	*newPtr = TRUE;
	valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
		sizeof(Value));
	valuePtr->key = key;
	valuePtr->owner = NULL;
	valuePtr->next = NULL;
	valuePtr->objPtr = NULL;
	if (prevPtr == NULL) {
	    nodePtr->values = valuePtr;
	} else {
	    prevPtr->next = valuePtr;
	}
	nodePtr->nValues++;
    }
    return valuePtr;
}


Blt_TreeNode Blt_TreeEndNode (Blt_TreeNode node,
    unsigned int nodeFlags) {
    /* TODO: finish. */
    return NULL;
}

#undef Blt_TreeFirstChild
#undef Blt_TreeLastChild
#undef Blt_TreeNextSibling
#undef Blt_TreePrevSibling
#undef Blt_TreeChangeRoot

Blt_TreeNode Blt_TreeFirstChild (Blt_TreeNode parent) {
    return parent->first;
}

Blt_TreeNode Blt_TreeNextSibling (Blt_TreeNode node) {
    return (node == NULL ? NULL : node->next);
}

Blt_TreeNode Blt_TreeLastChild (Blt_TreeNode parent) {
    return parent->last;
}

Blt_TreeNode Blt_TreePrevSibling (Blt_TreeNode node) {
    return (node == NULL ? NULL : node->prev);
}

Blt_TreeNode Blt_TreeChangeRoot (Blt_Tree tree, Blt_TreeNode node) {
    tree->root = node;
    return node;
}

#endif /* NO_TREE */