+++ /dev/null
-
-/*
- * 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, ¬ifyPtr->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);
-}
-
-\f
-/* 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)
-{
- char **nameArr; /* Used to stack the component names. */
- 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)
-{
- char **nameArr; /* Used to stack the component names. */
- 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;
- 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;
- 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 */
OSDN Git Service
