util/src/TclTk/blt2.5/generic/bltTree.c

   1
   2 /*
   3  * bltTree.c --
   4  *
   5  * Copyright 1998-1999 Lucent Technologies, Inc.
   6  *
   7  * Permission to use, copy, modify, and distribute this software and
   8  * its documentation for any purpose and without fee is hereby
   9  * granted, provided that the above copyright notice appear in all
  10  * copies and that both that the copyright notice and warranty
  11  * disclaimer appear in supporting documentation, and that the names
  12  * of Lucent Technologies or any of their entities not be used in
  13  * advertising or publicity pertaining to distribution of the software
  14  * without specific, written prior permission.
  15  *
  16  * Lucent Technologies disclaims all warranties with regard to this
  17  * software, including all implied warranties of merchantability and
  18  * fitness.  In no event shall Lucent Technologies be liable for any
  19  * special, indirect or consequential damages or any damages
  20  * whatsoever resulting from loss of use, data or profits, whether in
  21  * an action of contract, negligence or other tortuous action, arising
  22  * out of or in connection with the use or performance of this
  23  * software.
  24  *
  25  *      The "tree" data object was created by George A. Howlett.
  26  *      Extensive cleanups and enhancements by Peter MacDonald.
  27  *
  28  */
  29
  30 #include "bltInt.h"
  31
  32 /* TODO:
  33  *      traces and notifiers should be in one list in tree object.
  34  *      notifier is always fired.
  35  *      incorporate first/next tag routines ?
  36  */
  37
  38
  39 #ifndef NO_TREE
  40
  41 #include "bltTree.h"
  42
  43
  44 static int IsTclDict(Tcl_Interp *interp,Tcl_Obj *objPtr) {
  45    static Tcl_ObjType *dictType = NULL;
  46
  47    if (dictType == NULL) {
  48         Tcl_Obj * obj;
  49         obj = Tcl_NewDictObj();
  50         dictType = obj->typePtr;
  51         Tcl_DecrRefCount(obj);
  52    }
  53    return (objPtr->typePtr == dictType);
  54 }
  55
  56 /* 2 = per-tree key, 1 for per-interp, 0 for global (original behavior). */
  57 int bltTreeUseLocalKeys = 0;
  58
  59 static Tcl_InterpDeleteProc TreeInterpDeleteProc;
  60 static Blt_TreeApplyProc SizeApplyProc;
  61 static Tcl_IdleProc NotifyIdleProc;
  62
  63 #define TREE_THREAD_KEY         "BLT Tree Data"
  64 #define TREE_MAGIC              ((unsigned int) 0x46170277)
  65 #define TREE_DESTROYED          (1<<0)
  66
  67 typedef struct Blt_TreeNodeStruct Node;
  68 typedef struct Blt_TreeClientStruct TreeClient;
  69 typedef struct Blt_TreeObjectStruct TreeObject;
  70 typedef struct Blt_TreeValueStruct Value;
  71
  72 /*
  73  * Blt_TreeValue --
  74  *
  75  *      Tree nodes contain heterogeneous data fields, represented as a
  76  *      chain of these structures.  Each field contains the key of the
  77  *      field (Blt_TreeKey) and the value (Tcl_Obj) containing the
  78  *      actual data representations.
  79  *
  80  */
  81 struct Blt_TreeValueStruct {
  82     Blt_TreeKey key;            /* String identifying the data field */
  83     Tcl_Obj *objPtr;            /* Data representation. */
  84     Blt_Tree owner;             /* Non-NULL if privately owned. */
  85     Blt_TreeValue next;         /* Next value in the chain. */
  86 };
  87
  88 #include <stdio.h>
  89 #include <string.h>
  90 /* The following header is required for LP64 compilation */
  91 #include <stdlib.h>
  92
  93 #include "bltHash.h"
  94
  95 static void TreeDestroyValues _ANSI_ARGS_((Blt_TreeNode node));
  96
  97 static Value *TreeFindValue _ANSI_ARGS_((Blt_TreeNode node,
  98         Blt_TreeKey key));
  99 static Value *TreeCreateValue _ANSI_ARGS_((Blt_TreeNode node,
 100         Blt_TreeKey key, int *newPtr));
 101
 102 static int TreeDeleteValue _ANSI_ARGS_((Blt_TreeNode node,
 103         Blt_TreeValue value));
 104
 105 static Value *TreeFirstValue _ANSI_ARGS_((Blt_TreeNode,
 106         Blt_TreeKeySearch *searchPtr));
 107
 108 static Value *TreeNextValue _ANSI_ARGS_((Blt_TreeKeySearch *srchPtr));
 109
 110 /*
 111  * When there are this many entries per bucket, on average, rebuild
 112  * the hash table to make it larger.
 113  */
 114
 115 #define REBUILD_MULTIPLIER      3
 116
 117 #define START_LOGSIZE           5 /* Initial hash table size is 32. */
 118 #define MAX_LIST_VALUES         21 /* Convert to hash table when node
 119                                     * value list gets bigger than this
 120                                     * many values. */
 121
 122 #if (SIZEOF_VOID_P == 8)
 123 #define RANDOM_INDEX(i)         HashOneWord(mask, downshift, i)
 124 #define BITSPERWORD             64
 125 #else
 126
 127 /*
 128  * The following macro takes a preliminary integer hash value and
 129  * produces an index into a hash tables bucket list.  The idea is
 130  * to make it so that preliminary values that are arbitrarily similar
 131  * will end up in different buckets.  The hash function was taken
 132  * from a random-number generator.
 133  */
 134 #define RANDOM_INDEX(i) \
 135     (((((long) (i))*1103515245) >> downshift) & mask)
 136 #define BITSPERWORD             32
 137 #endif
 138
 139 #define DOWNSHIFT_START         (BITSPERWORD - 2)
 140
 141 /*
 142  * Procedure prototypes for static procedures in this file:
 143  */
 144
 145
 146 #if (SIZEOF_VOID_P == 8)
 147 static Blt_Hash HashOneWord _ANSI_ARGS_((uint64_t mask, unsigned int downshift,
 148         CONST void *key));
 149
 150 #endif /* SIZEOF_VOID_P == 8 */
 151
 152 /*
 153  * The hash table below is used to keep track of all the Blt_TreeKeys
 154  * created so far.
 155  */
 156 static Blt_HashTable keyTable;
 157 static int keyTableInitialized = 0;
 158
 159 typedef struct {
 160     Blt_HashTable treeTable;    /* Table of trees. */
 161     unsigned int nextId;
 162     Tcl_Interp *interp;
 163     Blt_HashTable keyTable;
 164 } TreeInterpData;
 165
 166 typedef struct {
 167     Tcl_Interp *interp;
 168     ClientData clientData;
 169     Blt_TreeKey key;
 170     unsigned int mask;
 171     Blt_TreeNotifyEventProc *proc;
 172     Blt_TreeNotifyEvent event;
 173     int notifyPending;
 174 } EventHandler;
 175
 176 typedef struct {
 177     ClientData clientData;
 178     char *keyPattern;
 179     char *withTag;
 180     Node *nodePtr;
 181     unsigned int mask;
 182     Blt_TreeTraceProc *proc;
 183     TreeClient *clientPtr;
 184     Blt_ChainLink *linkPtr;
 185 } TraceHandler;
 186
 187 /*
 188  * --------------------------------------------------------------
 189  *
 190  * GetTreeInterpData --
 191  *
 192  *      Creates or retrieves data associated with tree data objects
 193  *      for a particular thread.  We're using Tcl_GetAssocData rather
 194  *      than the Tcl thread routines so BLT can work with pre-8.0
 195  *      Tcl versions that don't have thread support.
 196  *
 197  * Results:
 198  *      Returns a pointer to the tree interpreter data.
 199  *
 200  * --------------------------------------------------------------
 201  */
 202 static TreeInterpData *
 203 GetTreeInterpData(Tcl_Interp *interp)
 204 {
 205     Tcl_InterpDeleteProc *proc;
 206     TreeInterpData *dataPtr;
 207
 208     dataPtr = (TreeInterpData *)
 209         Tcl_GetAssocData(interp, TREE_THREAD_KEY, &proc);
 210     if (dataPtr == NULL) {
 211         dataPtr = Blt_Malloc(sizeof(TreeInterpData));
 212         assert(dataPtr);
 213         dataPtr->interp = interp;
 214         Tcl_SetAssocData(interp, TREE_THREAD_KEY, TreeInterpDeleteProc,
 215                  dataPtr);
 216         Blt_InitHashTable(&dataPtr->treeTable, BLT_STRING_KEYS);
 217         Blt_InitHashTable(&dataPtr->keyTable, BLT_STRING_KEYS);
 218     }
 219     return dataPtr;
 220 }
 221
 222 /*
 223  * --------------------------------------------------------------
 224  *
 225  * NewNode --
 226  *
 227  *      Creates a new node in the tree without installing it.  The
 228  *      number of nodes in the tree is incremented and a unique serial
 229  *      number is generated for the node.
 230  *
 231  *      Also, all nodes have a label.  If no label was provided (name
 232  *      is NULL) then automatically generate a serial number for the node.
 233  *
 234  * Results:
 235  *      Returns a pointer to the new node.
 236  *
 237  * --------------------------------------------------------------
 238  */
 239 static Node *
 240 NewNode(TreeObject *treeObjPtr, CONST char *name, int inode)
 241 {
 242     Node *nodePtr;
 243
 244     /* Create the node structure */
 245     nodePtr = Blt_PoolAllocItem(treeObjPtr->nodePool, sizeof(Node));
 246     nodePtr->inode = inode;
 247     nodePtr->treeObject = treeObjPtr;
 248     nodePtr->parent = NULL;
 249     nodePtr->depth = 0;
 250     nodePtr->flags = 0;
 251     nodePtr->next = nodePtr->prev = NULL;
 252     nodePtr->first = nodePtr->last = NULL;
 253     nodePtr->nChildren = 0;
 254     nodePtr->values = NULL;
 255     nodePtr->logSize = 0;
 256     nodePtr->nValues = 0;
 257     nodePtr->label = NULL;
 258     if (name != NULL) {
 259         nodePtr->label = Blt_TreeKeyGet(NULL, treeObjPtr, name);
 260     }
 261     treeObjPtr->nNodes++;
 262     return nodePtr;
 263 }
 264
 265 /*
 266  *----------------------------------------------------------------------
 267  *
 268  * ReleaseTagTable --
 269  *
 270  *----------------------------------------------------------------------
 271  */
 272 static void
 273 ReleaseTagTable(Blt_TreeTagTable *tablePtr)
 274 {
 275     tablePtr->refCount--;
 276     if (tablePtr->refCount <= 0) {
 277         Blt_HashEntry *hPtr;
 278         Blt_HashSearch cursor;
 279
 280         for(hPtr = Blt_FirstHashEntry(&tablePtr->tagTable, &cursor);
 281             hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
 282             Blt_TreeTagEntry *tPtr;
 283
 284             tPtr = Blt_GetHashValue(hPtr);
 285             Blt_DeleteHashTable(&tPtr->nodeTable);
 286             Blt_TreeTagRefDecr(tPtr);
 287         }
 288         Blt_DeleteHashTable(&tablePtr->tagTable);
 289         Blt_Free(tablePtr);
 290     }
 291 }
 292
 293 /*
 294  * ----------------------------------------------------------------------
 295  *
 296  * ResetDepths --
 297  *
 298  *      Called after moving a node, resets the depths of each node
 299  *      for the entire branch (node and it's decendants).
 300  *
 301  * Results:
 302  *      None.
 303  *
 304  * ----------------------------------------------------------------------
 305  */
 306 static void
 307 ResetDepths(
 308     Node *nodePtr,              /* Root node. */
 309     int depth)                  /* Depth of the node. */
 310 {
 311     nodePtr->depth = depth;
 312     /* Also reset the depth for each descendant node. */
 313     for (nodePtr = nodePtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
 314         ResetDepths(nodePtr, depth + 1);
 315     }
 316 }
 317
 318 /*
 319  *----------------------------------------------------------------------
 320  *
 321  * LinkBefore --
 322  *
 323  *      Inserts a link preceding a given link.
 324  *
 325  * Results:
 326  *      None.
 327  *
 328  *----------------------------------------------------------------------
 329  */
 330 static void
 331 LinkBefore(
 332     Node *parentPtr,    /* Parent to hold the new entry. */
 333     Node *nodePtr,      /* New node to be inserted. */
 334     Node *beforePtr)    /* Node to link before. */
 335 {
 336     if (parentPtr->first == NULL) {
 337         parentPtr->last = parentPtr->first = nodePtr;
 338     } else if (beforePtr == NULL) { /* Append onto the end of the chain */
 339         nodePtr->next = NULL;
 340         nodePtr->prev = parentPtr->last;
 341         parentPtr->last->next = nodePtr;
 342         parentPtr->last = nodePtr;
 343     } else {
 344         nodePtr->prev = beforePtr->prev;
 345         nodePtr->next = beforePtr;
 346         if (beforePtr == parentPtr->first) {
 347             parentPtr->first = nodePtr;
 348         } else {
 349             beforePtr->prev->next = nodePtr;
 350         }
 351         beforePtr->prev = nodePtr;
 352     }
 353     parentPtr->nChildren++;
 354     nodePtr->parent = parentPtr;
 355 }
 356
 357
 358 /*
 359  *----------------------------------------------------------------------
 360  *
 361  * UnlinkNode --
 362  *
 363  *      Unlinks a link from the chain. The link is not deallocated,
 364  *      but only removed from the chain.
 365  *
 366  * Results:
 367  *      None.
 368  *
 369  *----------------------------------------------------------------------
 370  */
 371 static void
 372 UnlinkNode(Node *nodePtr)
 373 {
 374     Node *parentPtr;
 375     int unlinked;               /* Indicates if the link is actually
 376                                  * removed from the chain. */
 377     parentPtr = nodePtr->parent;
 378     unlinked = FALSE;
 379     if (parentPtr->first == nodePtr) {
 380         parentPtr->first = nodePtr->next;
 381         unlinked = TRUE;
 382     }
 383     if (parentPtr->last == nodePtr) {
 384         parentPtr->last = nodePtr->prev;
 385         unlinked = TRUE;
 386     }
 387     if (nodePtr->next != NULL) {
 388         nodePtr->next->prev = nodePtr->prev;
 389         unlinked = TRUE;
 390     }
 391     if (nodePtr->prev != NULL) {
 392         nodePtr->prev->next = nodePtr->next;
 393         unlinked = TRUE;
 394     }
 395     if (unlinked) {
 396         parentPtr->nChildren--;
 397     }
 398     nodePtr->prev = nodePtr->next = nodePtr->parent = NULL;
 399 }
 400
 401 /*
 402  * --------------------------------------------------------------
 403  *
 404  * FreeNode --
 405  *
 406  *      Unlinks a given node from the tree, removes its data, and
 407  *      frees memory allocated to the node.
 408  *
 409  * Results:
 410  *      None.
 411  *
 412  * --------------------------------------------------------------
 413  */
 414 static void
 415 FreeNode(TreeObject *treeObjPtr, Node *nodePtr)
 416 {
 417     Blt_HashEntry *hPtr;
 418
 419     /*
 420      * Destroy any data fields associated with this node.
 421      */
 422     TreeDestroyValues(nodePtr);
 423     UnlinkNode(nodePtr);
 424     treeObjPtr->nNodes--;
 425     hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)nodePtr->inode);
 426     assert(hPtr);
 427     Blt_DeleteHashEntry(&treeObjPtr->nodeTable, hPtr);
 428     nodePtr->inode = -1;
 429     nodePtr->flags = 0;
 430     Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
 431 }
 432
 433 /*
 434  * --------------------------------------------------------------
 435  *
 436  * NewTreeObject --
 437  *
 438  *      Creates and initializes a new tree object. Trees always
 439  *      contain a root node, so one is allocated here.
 440  *
 441  * Results:
 442  *      Returns a pointer to the new tree object is successful, NULL
 443  *      otherwise.  If a tree can't be generated, interp->result will
 444  *      contain an error message.
 445  *
 446  * -------------------------------------------------------------- */
 447 static TreeObject *
 448 NewTreeObject(TreeInterpData *dataPtr, Tcl_Interp *interp, CONST char *treeName)
 449 {
 450     TreeObject *treeObjPtr;
 451     int isNew;
 452     Blt_HashEntry *hPtr;
 453
 454     treeObjPtr = Blt_Calloc(1, sizeof(TreeObject));
 455     if (treeObjPtr == NULL) {
 456         if (interp != NULL)
 457             Tcl_AppendResult(interp, "can't allocate tree", (char *)NULL);
 458         return NULL;
 459     }
 460     treeObjPtr->name = Blt_Strdup(treeName);
 461     treeObjPtr->interp = interp;
 462     treeObjPtr->valuePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
 463     treeObjPtr->nodePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
 464     treeObjPtr->clients = Blt_ChainCreate();
 465     treeObjPtr->depth = 1;
 466     treeObjPtr->flags = 0;
 467     treeObjPtr->maxKeyList = 0;
 468     if (bltTreeUseLocalKeys) {
 469         if (bltTreeUseLocalKeys>1) {
 470             treeObjPtr->interpKeyPtr = &treeObjPtr->keyTable;
 471         } else {
 472             treeObjPtr->interpKeyPtr = &dataPtr->keyTable;
 473         }
 474     }
 475     treeObjPtr->notifyFlags = 0;
 476     Blt_InitHashTable(&treeObjPtr->keyTable, BLT_STRING_KEYS);
 477     Blt_InitHashTableWithPool(&treeObjPtr->nodeTable, BLT_ONE_WORD_KEYS);
 478
 479     hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable, (char *)0, &isNew);
 480     treeObjPtr->root = NewNode(treeObjPtr, treeName, 0);
 481     Blt_SetHashValue(hPtr, treeObjPtr->root);
 482
 483     treeObjPtr->tablePtr = &dataPtr->treeTable;
 484     treeObjPtr->hashPtr = Blt_CreateHashEntry(treeObjPtr->tablePtr, treeName,
 485         &isNew);
 486     Blt_SetHashValue(treeObjPtr->hashPtr, treeObjPtr);
 487
 488     return treeObjPtr;
 489 }
 490
 491 static TreeObject *
 492 FindTreeInNamespace(
 493     TreeInterpData *dataPtr,    /* Interpreter-specific data. */
 494     Tcl_Namespace *nsPtr,
 495     CONST char *treeName)
 496 {
 497     Tcl_DString dString;
 498     char *name;
 499     Blt_HashEntry *hPtr;
 500
 501     name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
 502     hPtr = Blt_FindHashEntry(&dataPtr->treeTable, name);
 503     Tcl_DStringFree(&dString);
 504     if (hPtr != NULL) {
 505         return Blt_GetHashValue(hPtr);
 506     }
 507     return NULL;
 508 }
 509
 510 /*
 511  * ----------------------------------------------------------------------
 512  *
 513  * GetTreeObject --
 514  *
 515  *      Searches for the tree object associated by the name given.
 516  *
 517  * Results:
 518  *      Returns a pointer to the tree if found, otherwise NULL.
 519  *
 520  * ----------------------------------------------------------------------
 521  */
 522 static TreeObject *
 523 GetTreeObject(Tcl_Interp *interp, CONST char *name, int flags)
 524 {
 525     CONST char *treeName;
 526     Tcl_Namespace *nsPtr;       /* Namespace associated with the tree object.
 527                                  * If NULL, indicates to look in first the
 528                                  * current namespace and then the global
 529                                  * for the tree. */
 530     TreeInterpData *dataPtr;    /* Interpreter-specific data. */
 531     TreeObject *treeObjPtr;
 532
 533     treeObjPtr = NULL;
 534     if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
 535         if (interp != NULL)
 536             Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
 537                 (char *)NULL);
 538         return NULL;
 539     }
 540     dataPtr = GetTreeInterpData(interp);
 541     if (nsPtr != NULL) {
 542         treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
 543     } else {
 544         if (flags & NS_SEARCH_CURRENT) {
 545             /* Look first in the current namespace. */
 546             nsPtr = Tcl_GetCurrentNamespace(interp);
 547             treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
 548         }
 549         if ((treeObjPtr == NULL) && (flags & NS_SEARCH_GLOBAL)) {
 550             nsPtr = Tcl_GetGlobalNamespace(interp);
 551             treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
 552         }
 553     }
 554     return treeObjPtr;
 555 }
 556
 557 /*
 558  * ----------------------------------------------------------------------
 559  *
 560  * TeardownTree --
 561  *
 562  *      Destroys an entire branch.  This is a special purpose routine
 563  *      used to speed up the final clean up of the tree.
 564  *
 565  * Results:
 566  *      None.
 567  *
 568  * ----------------------------------------------------------------------
 569  */
 570 static void
 571 TeardownTree(TreeObject *treeObjPtr, Node *nodePtr)
 572 {
 573     if (nodePtr->first != NULL) {
 574         Node *childPtr, *nextPtr;
 575
 576         for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
 577             nextPtr = childPtr->next;
 578             TeardownTree(treeObjPtr, childPtr);
 579         }
 580     }
 581     if (nodePtr->values != NULL) {
 582         TreeDestroyValues(nodePtr);
 583     }
 584     Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
 585 }
 586
 587 static void
 588 DestroyTreeObject(char *treeObj)
 589 {
 590     Blt_ChainLink *linkPtr;
 591     TreeClient *clientPtr;
 592     TreeObject *treeObjPtr = (TreeObject*)treeObj;
 593
 594     if (treeObjPtr->flags & TREE_DESTROYED) return;
 595     treeObjPtr->flags |= TREE_DESTROYED;
 596     treeObjPtr->nNodes = 0;
 597
 598     /* Remove the remaining clients. */
 599     for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients); linkPtr != NULL;
 600         linkPtr = Blt_ChainNextLink(linkPtr)) {
 601         clientPtr = Blt_ChainGetValue(linkPtr);
 602         Blt_ChainDestroy(clientPtr->events);
 603         Blt_ChainDestroy(clientPtr->traces);
 604         Blt_Free(clientPtr);
 605     }
 606     Blt_ChainDestroy(treeObjPtr->clients);
 607
 608     TeardownTree(treeObjPtr, treeObjPtr->root);
 609     Blt_PoolDestroy(treeObjPtr->nodePool);
 610     Blt_PoolDestroy(treeObjPtr->valuePool);
 611     Blt_DeleteHashTable(&treeObjPtr->nodeTable);
 612     Blt_DeleteHashTable(&treeObjPtr->keyTable);
 613
 614     if (treeObjPtr->hashPtr != NULL) {
 615         /* Remove the entry from the global tree table. */
 616         Blt_DeleteHashEntry(treeObjPtr->tablePtr, treeObjPtr->hashPtr);
 617         if ((treeObjPtr->tablePtr->numEntries == 0) && (keyTableInitialized)) {
 618             keyTableInitialized = FALSE;
 619             Blt_DeleteHashTable(&keyTable);
 620         }
 621     }
 622     if (treeObjPtr->name != NULL) {
 623         Blt_Free(treeObjPtr->name);
 624     }
 625     Blt_Free(treeObjPtr);
 626 }
 627
 628 /*
 629  * -----------------------------------------------------------------------
 630  *
 631  * TreeInterpDeleteProc --
 632  *
 633  *      This is called when the interpreter hosting the tree object
 634  *      is deleted from the interpreter.
 635  *
 636  * Results:
 637  *      None.
 638  *
 639  * Side effects:
 640  *      Destroys all remaining trees and removes the hash table
 641  *      used to register tree names.
 642  *
 643  * ------------------------------------------------------------------------
 644  */
 645 /* ARGSUSED */
 646 static void
 647 TreeInterpDeleteProc(
 648     ClientData clientData,      /* Interpreter-specific data. */
 649     Tcl_Interp *interp)
 650 {
 651     TreeInterpData *dataPtr = clientData;
 652     Blt_HashEntry *hPtr;
 653     Blt_HashSearch cursor;
 654     TreeObject *treeObjPtr;
 655
 656     for (hPtr = Blt_FirstHashEntry(&dataPtr->treeTable, &cursor);
 657          hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
 658         treeObjPtr = (TreeObject *)Blt_GetHashValue(hPtr);
 659         treeObjPtr->hashPtr = NULL;
 660         treeObjPtr->delete = 1;
 661         Tcl_EventuallyFree(treeObjPtr, DestroyTreeObject);
 662          /*DestroyTreeObject(treeObjPtr); */
 663     }
 664     if (keyTableInitialized) {
 665         keyTableInitialized = FALSE;
 666         Blt_DeleteHashTable(&keyTable);
 667     }
 668     Blt_DeleteHashTable(&dataPtr->treeTable);
 669     Blt_DeleteHashTable(&dataPtr->keyTable);
 670     Tcl_DeleteAssocData(interp, TREE_THREAD_KEY);
 671     Blt_Free(dataPtr);
 672 }
 673
 674 /*
 675  *----------------------------------------------------------------------
 676  *
 677  * NotifyIdleProc --
 678  *
 679  *      Used to invoke event handler routines at some idle point.
 680  *      This routine is called from the Tcl event loop.  Errors
 681  *      generated by the event handler routines are backgrounded.
 682  *
 683  * Results:
 684  *      None.
 685  *
 686  *----------------------------------------------------------------------
 687  */
 688 static void
 689 NotifyIdleProc(ClientData clientData)
 690 {
 691     EventHandler *notifyPtr = clientData;
 692     int result;
 693
 694     notifyPtr->notifyPending = FALSE;
 695     notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
 696     result = (*notifyPtr->proc)(notifyPtr->clientData, &notifyPtr->event);
 697     notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
 698     if (result != TCL_OK) {
 699         Tcl_BackgroundError(notifyPtr->interp);
 700     }
 701 }
 702
 703 /*
 704  *----------------------------------------------------------------------
 705  *
 706  * CheckEventHandlers --
 707  *
 708  *      Traverses the list of client event callbacks and checks
 709  *      if one matches the given event.  A client may trigger an
 710  *      action that causes the tree to notify it.  The can be
 711  *      prevented by setting the TREE_NOTIFY_FOREIGN_ONLY bit in
 712  *      the event handler.
 713  *
 714  *      If a matching handler is found, a callback may be called either
 715  *      immediately or at the next idle time depending upon the
 716  *      TREE_NOTIFY_WHENIDLE bit.
 717  *
 718  *      Since a handler routine may trigger yet another call to
 719  *      itself, callbacks are ignored while the event handler is
 720  *      executing.
 721  *
 722  * Results:
 723  *      None.
 724  *
 725  *----------------------------------------------------------------------
 726  */
 727 static int
 728 CheckEventHandlers(
 729     TreeClient *clientPtr,
 730     int isSource,               /* Indicates if the client is the source
 731                                  * of the event. */
 732     Blt_TreeNotifyEvent *eventPtr)
 733 {
 734     Blt_ChainLink *linkPtr, *nextPtr;
 735     EventHandler *notifyPtr;
 736
 737     eventPtr->tree = clientPtr;
 738     for (linkPtr = Blt_ChainFirstLink(clientPtr->events);
 739         linkPtr != NULL; linkPtr = nextPtr) {
 740         nextPtr = Blt_ChainNextLink(linkPtr);
 741         notifyPtr = Blt_ChainGetValue(linkPtr);
 742         if ((notifyPtr->mask & TREE_NOTIFY_ACTIVE) ||
 743             (notifyPtr->mask & eventPtr->type) == 0) {
 744             continue;           /* Ignore callbacks that are generated
 745                                  * inside of a notify handler routine. */
 746         }
 747         if ((isSource) && (notifyPtr->mask & TREE_NOTIFY_FOREIGN_ONLY)) {
 748             continue;           /* Don't notify yourself. */
 749         }
 750         if (notifyPtr->mask & TREE_NOTIFY_WHENIDLE) {
 751             if (!notifyPtr->notifyPending) {
 752                 notifyPtr->notifyPending = TRUE;
 753                 notifyPtr->event = *eventPtr;
 754                 Tcl_DoWhenIdle(NotifyIdleProc, notifyPtr);
 755             }
 756         } else {
 757             int result;
 758
 759             notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
 760             result = (*notifyPtr->proc) (notifyPtr->clientData, eventPtr);
 761             notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
 762             if (result != TCL_OK) {
 763                 if (notifyPtr->mask & TREE_NOTIFY_BGERROR) {
 764                      Tcl_BackgroundError(notifyPtr->interp);
 765                 }
 766                 return result;
 767             }
 768         }
 769     }
 770     return TCL_OK;
 771 }
 772
 773 /*
 774  *----------------------------------------------------------------------
 775  *
 776  * NotifyClients --
 777  *
 778  *      Traverses the list of clients for a particular tree and
 779  *      notifies each client that an event occurred.  Clients
 780  *      indicate interest in a particular event through a bit
 781  *      flag.
 782  *
 783  *----------------------------------------------------------------------
 784  */
 785 static int
 786 NotifyClients(
 787     TreeClient *sourcePtr,
 788     TreeObject *treeObjPtr,
 789     Node *nodePtr,
 790     int eventFlag)
 791 {
 792     Blt_ChainLink *linkPtr;
 793     Blt_TreeNotifyEvent event;
 794     TreeClient *clientPtr;
 795     int isSource, result;
 796
 797     if (Tcl_InterpDeleted(treeObjPtr->interp) ||
 798             Tcl_InterpDeleted(sourcePtr->root->treeObject->interp)) {
 799         return TCL_OK;
 800     }
 801     event.type = eventFlag;
 802     event.inode = nodePtr->inode;
 803
 804     /*
 805      * Issue callbacks to each client indicating that a new node has
 806      * been created.
 807      */
 808     for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients);
 809         linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
 810         clientPtr = Blt_ChainGetValue(linkPtr);
 811         isSource = (clientPtr == sourcePtr);
 812         result = CheckEventHandlers(clientPtr, isSource, &event);
 813         if (result != TCL_OK) {
 814             return TCL_ERROR;
 815         }
 816         if (Blt_TreeNodeDeleted(nodePtr) || nodePtr->inode != event.inode) {
 817             return TCL_BREAK;
 818         }
 819      }
 820     return TCL_OK;
 821 }
 822
 823 static void
 824 FreeValue(Node *nodePtr, Value *valuePtr)
 825 {
 826     if (valuePtr->objPtr != NULL) {
 827         Tcl_DecrRefCount(valuePtr->objPtr);
 828     }
 829     Blt_PoolFreeItem(nodePtr->treeObject->valuePool, valuePtr);
 830 }
 831
 832 \f
 833 /* Public Routines */
 834 /*
 835  *----------------------------------------------------------------------
 836  *
 837  * Blt_TreeGetKey --
 838  *
 839  *      Given a string, returns a unique identifier for the string.
 840  *
 841  *----------------------------------------------------------------------
 842  */
 843 Blt_TreeKey
 844 Blt_TreeGetKey(string)
 845     CONST char *string;         /* String to convert. */
 846 {
 847     Blt_HashEntry *hPtr;
 848     int isNew;
 849
 850     if (!keyTableInitialized) {
 851         Blt_InitHashTable(&keyTable, BLT_STRING_KEYS);
 852         keyTableInitialized = 1;
 853     }
 854     hPtr = Blt_CreateHashEntry(&keyTable, string, &isNew);
 855     return (Blt_TreeKey)Blt_GetHashKey(&keyTable, hPtr);
 856 }
 857
 858 /*
 859 *----------------------------------------------------------------------
 860 *
 861 * Blt_TreeKeyGet --
 862 *
 863 *       tree-unique keys.
 864 *       TODO: use per-interp keyTable rather than global one.
 865 *
 866 *----------------------------------------------------------------------
 867 */
 868 Blt_TreeKey
 869 Blt_TreeKeyGet(interp, treeObjPtr, string)
 870     Tcl_Interp *interp;
 871     TreeObject *treeObjPtr;
 872     CONST char *string;         /* String to convert. */
 873 {
 874     Blt_HashTable *tablePtr;
 875     Blt_HashEntry *hPtr;
 876     int isNew;
 877
 878     tablePtr = NULL;
 879     if (treeObjPtr != NULL && treeObjPtr->interpKeyPtr != NULL) {
 880         tablePtr = treeObjPtr->interpKeyPtr;
 881     }
 882     if (tablePtr == NULL && interp != NULL && bltTreeUseLocalKeys != 0) {
 883         TreeInterpData *dataPtr;
 884         dataPtr = GetTreeInterpData(interp);
 885         tablePtr = &dataPtr->keyTable;
 886     }
 887     if (tablePtr == NULL) {
 888         return Blt_TreeGetKey(string);
 889     }
 890     hPtr = Blt_CreateHashEntry(tablePtr, string, &isNew);
 891     return (Blt_TreeKey)Blt_GetHashKey(tablePtr, hPtr);
 892 }
 893
 894 /* Clear the unmodified flag for node. */
 895 static void SetModified(Node *nodePtr)
 896 {
 897     nodePtr->flags &= ~TREE_NODE_UNMODIFIED;
 898     nodePtr->treeObject->flags &= ~TREE_UNMODIFIED;
 899 }
 900
 901 /*
 902  *----------------------------------------------------------------------
 903  *
 904  * Blt_TreeCreateNode --
 905  *
 906  *      Creates a new node in the given parent node.  The name and
 907  *      position in the parent are also provided.
 908  *
 909  *----------------------------------------------------------------------
 910  */
 911 Blt_TreeNode
 912 Blt_TreeCreateNode(
 913     TreeClient *clientPtr,      /* The tree client that is creating
 914                                  * this node.  If NULL, indicates to
 915                                  * trigger notify events on behalf of
 916                                  * the initiating client also. */
 917     Node *parentPtr,            /* Parent node where the new node will
 918                                  * be inserted. */
 919     CONST char *name,           /* Name of node. */
 920     int pos)                    /* Position in the parent's list of children
 921                                  * where to insert the new node. */
 922 {
 923     Blt_HashEntry *hPtr;
 924     Node *beforePtr;
 925     Node *nodePtr;      /* Node to be inserted. */
 926     TreeObject *treeObjPtr;
 927     int inode;
 928     int isNew;
 929
 930     treeObjPtr = parentPtr->treeObject;
 931
 932     /* Generate an unique serial number for this node.  */
 933     do {
 934         inode = treeObjPtr->nextInode++;
 935         hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode,
 936                    &isNew);
 937     } while (!isNew);
 938     nodePtr = NewNode(treeObjPtr, name, inode);
 939     Blt_SetHashValue(hPtr, nodePtr);
 940
 941     if ((pos == -1) || (pos >= (int)parentPtr->nChildren)) {
 942         beforePtr = NULL;
 943     } else {
 944         beforePtr = parentPtr->first;
 945         while ((pos > 0) && (beforePtr != NULL)) {
 946             pos--;
 947             beforePtr = beforePtr->next;
 948         }
 949     }
 950     LinkBefore(parentPtr, nodePtr, beforePtr);
 951     nodePtr->depth = parentPtr->depth + 1;
 952     /*
 953      * Issue callbacks to each client indicating that a new node has
 954      * been created.
 955      */
 956     if (NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE) != TCL_OK) {
 957         nodePtr->flags |= TREE_NODE_INSERT_FAIL;
 958         Blt_TreeDeleteNode(clientPtr, nodePtr);
 959         return NULL;
 960     }
 961     treeObjPtr->flags &= ~TREE_UNMODIFIED;
 962     return nodePtr;
 963 }
 964 /*
 965  *----------------------------------------------------------------------
 966  *
 967  * Blt_TreeInsertPost --
 968  *
 969  *      Trigger notify for -insert
 970  *
 971  *----------------------------------------------------------------------
 972  */
 973 Blt_TreeNode
 974 Blt_TreeInsertPost(
 975     TreeClient *clientPtr,      /* The tree client that is creating
 976                                  * this node.  If NULL, indicates to
 977                                  * trigger notify events on behalf of
 978                                  * the initiating client also. */
 979     Node *nodePtr)                  /*  node */
 980 {
 981     if (NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_INSERT) != TCL_OK) {
 982         nodePtr->flags |= TREE_NODE_INSERT_FAIL;
 983         Blt_TreeDeleteNode(clientPtr, nodePtr);
 984         return NULL;
 985     }
 986     return nodePtr;
 987 }
 988
 989 int
 990 Blt_TreeNotifyGet(
 991     TreeClient *clientPtr,      /* The tree client that is creating
 992                                  * this node.  If NULL, indicates to
 993                                  * trigger notify events on behalf of
 994                                  * the initiating client also. */
 995     Node *nodePtr)                  /*  node */
 996 {
 997     if (nodePtr->nValues != 0) return TCL_OK;
 998     return NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_GET);
 999 }
1000
1001 /*
1002  *----------------------------------------------------------------------
1003  *
1004  * Blt_TreeCreateNodeWithId --
1005  *
1006  *      Like Blt_TreeCreateNode, but provides a specific id to use
1007  *      for the node.  If the tree already contains a node by that
1008  *      id, NULL is returned.
1009  *
1010  *----------------------------------------------------------------------
1011  */
1012 Blt_TreeNode
1013 Blt_TreeCreateNodeWithId(
1014     TreeClient *clientPtr,
1015     Node *parentPtr,            /* Parent node where the new node will
1016                                  * be inserted. */
1017     CONST char *name,           /* Name of node. */
1018     unsigned int inode,/* Requested id of the new node. If a
1019                                  * node by this id already exists in the
1020                                  * tree, no node is created. */
1021     int position)               /* Position in the parent's list of children
1022                                  * where to insert the new node. */
1023 {
1024     Blt_HashEntry *hPtr;
1025     Node *beforePtr;
1026     Node *nodePtr;      /* Node to be inserted. */
1027     TreeObject *treeObjPtr;
1028     int isNew, result;
1029
1030     treeObjPtr = parentPtr->treeObject;
1031     hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode, &isNew);
1032     if (!isNew) {
1033         return NULL;
1034     }
1035     nodePtr = NewNode(treeObjPtr, name, inode);
1036     Blt_SetHashValue(hPtr, nodePtr);
1037
1038     if ((position == -1) || (position >= (int)parentPtr->nChildren)) {
1039         beforePtr = NULL;
1040     } else {
1041         beforePtr = parentPtr->first;
1042         while ((position > 0) && (beforePtr != NULL)) {
1043             position--;
1044             beforePtr = beforePtr->next;
1045         }
1046     }
1047     LinkBefore(parentPtr, nodePtr, beforePtr);
1048     nodePtr->depth = parentPtr->depth + 1;
1049     /*
1050      * Issue callbacks to each client indicating that a new node has
1051      * been created.
1052      */
1053      result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE);
1054      if (result != TCL_OK) {
1055          if (result != TCL_BREAK) {
1056              nodePtr->flags |= TREE_NODE_INSERT_FAIL;
1057              Blt_TreeDeleteNode(clientPtr, nodePtr);
1058          }
1059          return NULL;
1060      }
1061      treeObjPtr->flags &= ~TREE_UNMODIFIED;
1062      return nodePtr;
1063 }
1064
1065 /*
1066  *----------------------------------------------------------------------
1067  *
1068  * Blt_TreeMoveNode --
1069  *
1070  *      Move an entry into a new location in the hierarchy.
1071  *
1072  *----------------------------------------------------------------------
1073  */
1074 /*ARGSUSED*/
1075 int
1076 Blt_TreeMoveNode(
1077     TreeClient *clientPtr,
1078     Node *nodePtr,
1079     Node *parentPtr,
1080     Node *beforePtr)
1081 {
1082     TreeObject *treeObjPtr = nodePtr->treeObject;
1083     int newDepth, result;
1084
1085     if (nodePtr == beforePtr) {
1086         return TCL_ERROR;
1087     }
1088     if ((beforePtr != NULL) && (beforePtr->parent != parentPtr)) {
1089         return TCL_ERROR;
1090     }
1091     if (nodePtr->parent == NULL) {
1092         return TCL_ERROR;       /* Can't move root. */
1093     }
1094     /* Verify that the node isn't an ancestor of the new parent. */
1095     if (Blt_TreeIsAncestor(nodePtr, parentPtr)) {
1096         return TCL_ERROR;
1097     }
1098     /*
1099     * Issue callbacks to each client indicating that a node has
1100     * been moved.
1101     */
1102     if (NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_MOVE) != TCL_OK) {
1103         return TCL_ERROR;
1104     }
1105
1106     UnlinkNode(nodePtr);
1107     /*
1108      * Relink the node as a child of the new parent.
1109      */
1110     LinkBefore(parentPtr, nodePtr, beforePtr);
1111     newDepth = parentPtr->depth + 1;
1112     if (nodePtr->depth != newDepth) {
1113         /* Reset the depths of all descendant nodes. */
1114         ResetDepths(nodePtr, newDepth);
1115     }
1116     /*
1117     * Issue callbacks to each client indicating that a node has
1118     * been moved.
1119     */
1120     if ((result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_MOVEPOST)) != TCL_OK) {
1121         return result;
1122     }
1123
1124     return TCL_OK;
1125 }
1126
1127 int
1128 Blt_TreeDeleteNode(TreeClient *clientPtr, Node *nodePtr)
1129 {
1130     TreeObject *treeObjPtr = nodePtr->treeObject;
1131     Node *childPtr, *nextPtr;
1132     int result;
1133
1134     /*
1135     * Issue callbacks to each client indicating that the node can
1136     * no longer be used.
1137     */
1138     if (Blt_TreeNodeDeleted(nodePtr)) {
1139         return TCL_OK;
1140     }
1141     if ((nodePtr->flags & TREE_NODE_INSERT_FAIL) == 0 &&
1142         (result=NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_DELETE)) != TCL_OK) {
1143         return result;
1144     }
1145     nodePtr->flags &= ~TREE_NODE_FIXED_FIELDS;
1146
1147     /* In depth-first order, delete each descendant node. */
1148     for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
1149         nextPtr = childPtr->next;
1150         Blt_TreeDeleteNode(clientPtr, childPtr);
1151     }
1152
1153     /* Now remove the actual node. */
1154     FreeNode(treeObjPtr, nodePtr);
1155     if (treeObjPtr->nodeTable.numEntries <= 1) {
1156         treeObjPtr->nextInode = 1;
1157     }
1158     return TCL_OK;
1159 }
1160
1161 Blt_TreeNode
1162 Blt_TreeGetNode(TreeClient *clientPtr, unsigned int inode)
1163 {
1164     TreeObject *treeObjPtr = clientPtr->treeObject;
1165     Blt_HashEntry *hPtr;
1166
1167     hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)inode);
1168     if (hPtr != NULL) {
1169         return (Blt_TreeNode)Blt_GetHashValue(hPtr);
1170     }
1171     return NULL;
1172 }
1173
1174 /*
1175 static Node*
1176 GetNode(TreeObject *treeObjPtr, unsigned int inode)
1177 {
1178     Blt_HashEntry *hPtr;
1179
1180     hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)inode);
1181     if (hPtr != NULL) {
1182         return (Node*)Blt_GetHashValue(hPtr);
1183     }
1184     return NULL;
1185 }
1186 */
1187
1188 Blt_TreeTrace
1189 Blt_TreeCreateTrace(
1190     TreeClient *clientPtr,
1191     Node *nodePtr,
1192     CONST char *keyPattern,
1193     CONST char *tagName,
1194     unsigned int mask,
1195     Blt_TreeTraceProc *proc,
1196     ClientData clientData)
1197 {
1198     TraceHandler *tracePtr;
1199
1200     tracePtr = Blt_Calloc(1, sizeof (TraceHandler));
1201     assert(tracePtr);
1202     tracePtr->linkPtr = Blt_ChainAppend(clientPtr->traces, tracePtr);
1203     if (keyPattern != NULL) {
1204         tracePtr->keyPattern = Blt_Strdup(keyPattern);
1205     }
1206     if (tagName != NULL) {
1207         tracePtr->withTag = Blt_Strdup(tagName);
1208     }
1209     tracePtr->clientPtr = clientPtr;
1210     tracePtr->proc = proc;
1211     tracePtr->clientData = clientData;
1212     tracePtr->mask = mask;
1213     tracePtr->nodePtr = nodePtr;
1214     return (Blt_TreeTrace)tracePtr;
1215 }
1216
1217 void
1218 Blt_TreeDeleteTrace(Blt_TreeTrace trace)
1219 {
1220     TraceHandler *tracePtr = (TraceHandler *)trace;
1221
1222     Blt_ChainDeleteLink(tracePtr->clientPtr->traces, tracePtr->linkPtr);
1223     if (tracePtr->keyPattern != NULL) {
1224         Blt_Free(tracePtr->keyPattern);
1225     }
1226     if (tracePtr->withTag != NULL) {
1227         Blt_Free(tracePtr->withTag);
1228     }
1229     Blt_Free(tracePtr);
1230 }
1231
1232 int
1233 Blt_TreeRelabelNode(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
1234 {
1235     int result, inode;
1236     if ((result=NotifyClients(clientPtr, clientPtr->treeObject, nodePtr,
1237                   TREE_NOTIFY_RELABEL)) != TCL_OK) {
1238         return result;
1239     }
1240     nodePtr->label = Blt_TreeKeyGet(NULL, clientPtr->treeObject,string);
1241     /*
1242      * Issue callbacks to each client indicating that a new node has
1243      * been created.
1244      */
1245     SetModified(nodePtr);
1246     inode = nodePtr->inode;
1247     result = NotifyClients(clientPtr, clientPtr->treeObject, nodePtr,
1248                   TREE_NOTIFY_RELABELPOST);
1249     return result;
1250 }
1251
1252 int
1253 Blt_TreeNotifyAttach(TreeClient *clientPtr)
1254 {
1255     /* return NotifyClients(clientPtr, clientPtr->treeObject, clientPtr->root,
1256                   TREE_NOTIFY_ATTACH); */
1257     return TCL_OK;
1258 }
1259
1260
1261 int
1262 Blt_TreeRelabelNode2(Node *nodePtr, CONST char *string)
1263 {
1264     nodePtr->label = Blt_TreeKeyGet(NULL, nodePtr->treeObject,string);
1265     SetModified(nodePtr);
1266     return TCL_OK;
1267 }
1268
1269 /*
1270  *----------------------------------------------------------------------
1271  *
1272  * Blt_TreeFindChild --
1273  *
1274  *      Searches for the named node in a parent's chain of siblings.
1275  *
1276  *
1277  * Results:
1278  *      If found, the child node is returned, otherwise NULL.
1279  *
1280  *----------------------------------------------------------------------
1281  */
1282 Blt_TreeNode
1283 Blt_TreeFindChild(Node *parentPtr, CONST char *string)
1284 {
1285     Blt_TreeKey label;
1286     register Node *nodePtr;
1287
1288     label = Blt_TreeKeyGet(NULL, parentPtr->treeObject,string);
1289     for (nodePtr = parentPtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
1290         if (label == nodePtr->label) {
1291             return nodePtr;
1292         }
1293     }
1294     return NULL;
1295 }
1296 /*
1297  * Like Blt_TreeFindChild above, but looks forward firstN elements
1298  * from front, then falls back to reverse search starting from the end.
1299  * This speeds up insertion at the end of really long trees in treeview.
1300  * If firstN is < 0, just calls Blt_TreeFindChild.
1301  */
1302 Blt_TreeNode
1303 Blt_TreeFindChildRev(Node *parentPtr, CONST char *string, int firstN)
1304 {
1305     Blt_TreeKey label;
1306     register Node *nodePtr, *endNode;
1307     int n;
1308
1309     if (firstN<0) {
1310         return Blt_TreeFindChild(parentPtr, string);
1311     }
1312     label = Blt_TreeKeyGet(NULL, parentPtr->treeObject,string);
1313     for (nodePtr = parentPtr->first, n = 0;
1314         nodePtr != NULL && n < firstN;
1315         nodePtr = nodePtr->next, n++) {
1316         if (label == nodePtr->label) {
1317             return nodePtr;
1318         }
1319     }
1320     if (nodePtr == NULL) {
1321         return NULL;
1322     }
1323     endNode = nodePtr;
1324     for (nodePtr = parentPtr->last; nodePtr != NULL; nodePtr = nodePtr->prev) {
1325         if (label == nodePtr->label) {
1326             return nodePtr;
1327         }
1328         if (nodePtr == endNode) break;
1329     }
1330     return NULL;
1331 }
1332
1333 /*
1334  *----------------------------------------------------------------------
1335  *
1336  * Blt_TreeNodePosition --
1337  *
1338  *      Returns the position of the node in its parent's list of
1339  *      children.  The root's position is 0.
1340  *
1341  *----------------------------------------------------------------------
1342  */
1343 int
1344 Blt_TreeNodePosition(Node *nodePtr)
1345 {
1346     Node *parentPtr;
1347     int count;
1348
1349     count = 0;
1350     parentPtr = nodePtr->parent;
1351     if (parentPtr != NULL) {
1352         Node *childPtr;
1353
1354         for (childPtr = parentPtr->first; childPtr != NULL;
1355              childPtr = childPtr->next) {
1356             if (nodePtr == childPtr) {
1357                 break;
1358             }
1359             count++;
1360         }
1361     }
1362     return count;
1363 }
1364
1365
1366 /*
1367  *----------------------------------------------------------------------
1368  *
1369  * Blt_TreePrevNode --
1370  *
1371  *      Returns the "previous" node in the tree.  This node (in
1372  *      depth-first order) is its parent, if the node has no siblings
1373  *      that are previous to it.  Otherwise it is the last descendant
1374  *      of the last sibling.  In this case, descend the sibling's
1375  *      hierarchy, using the last child at any ancestor, with we
1376  *      we find a leaf.
1377  *
1378  *----------------------------------------------------------------------
1379  */
1380 Blt_TreeNode
1381 Blt_TreePrevNode(Node *rootPtr, Node *nodePtr)
1382 {
1383     Node *prevPtr;
1384
1385     if (nodePtr == rootPtr) {
1386         return NULL;            /* The root is the first node. */
1387     }
1388     prevPtr = nodePtr->prev;
1389     if (prevPtr == NULL) {
1390         /* There are no siblings previous to this one, so pick the parent. */
1391         return nodePtr->parent;
1392     }
1393     /*
1394      * Traverse down the right-most thread, in order to select the
1395      * next entry.  Stop when we reach a leaf.
1396      */
1397     nodePtr = prevPtr;
1398     while ((prevPtr = nodePtr->last) != NULL) {
1399         nodePtr = prevPtr;
1400     }
1401     return nodePtr;
1402 }
1403
1404 /*
1405  *----------------------------------------------------------------------
1406  *
1407  * Blt_TreeNextNode --
1408  *
1409  *      Returns the "next" node in relation to the given node.
1410  *      The next node (in depth-first order) is either the first
1411  *      child of the given node the next sibling if the node has
1412  *      no children (the node is a leaf).  If the given node is the
1413  *      last sibling, then try it's parent next sibling.  Continue
1414  *      until we either find a next sibling for some ancestor or
1415  *      we reach the root node.  In this case the current node is
1416  *      the last node in the tree.
1417  *
1418  *----------------------------------------------------------------------
1419  */
1420 Blt_TreeNode
1421 Blt_TreeNextNode(Node *rootPtr, Node *nodePtr)
1422 {
1423     Node *nextPtr;
1424
1425     /* Pick the first sub-node. */
1426     nextPtr = nodePtr->first;
1427     if (nextPtr != NULL) {
1428         return nextPtr;
1429     }
1430     /*
1431      * Back up until we can find a level where we can pick a
1432      * "next sibling".  For the last entry we'll thread our
1433      * way back to the root.
1434      */
1435     while (nodePtr != rootPtr) {
1436         nextPtr = nodePtr->next;
1437         if (nextPtr != NULL) {
1438             return nextPtr;
1439         }
1440         nodePtr = nodePtr->parent;
1441     }
1442     return NULL;                /* At root, no next node. */
1443 }
1444
1445
1446 int
1447 Blt_TreeIsBefore(Node *n1Ptr, Node *n2Ptr)
1448 {
1449     int depth;
1450     register int i;
1451     Node *nodePtr;
1452
1453     if (n1Ptr == n2Ptr) {
1454         return FALSE;
1455     }
1456     depth = MIN(n1Ptr->depth, n2Ptr->depth);
1457     if (depth == 0) {           /* One of the nodes is root. */
1458         return (n1Ptr->parent == NULL);
1459     }
1460     /*
1461      * Traverse back from the deepest node, until both nodes are at
1462      * the same depth.  Check if this ancestor node is the same for
1463      * both nodes.
1464      */
1465     for (i = n1Ptr->depth; i > depth; i--) {
1466         n1Ptr = n1Ptr->parent;
1467     }
1468     if (n1Ptr == n2Ptr) {
1469         return FALSE;
1470     }
1471     for (i = n2Ptr->depth; i > depth; i--) {
1472         n2Ptr = n2Ptr->parent;
1473     }
1474     if (n2Ptr == n1Ptr) {
1475         return TRUE;
1476     }
1477
1478     /*
1479      * First find the mutual ancestor of both nodes.  Look at each
1480      * preceding ancestor level-by-level for both nodes.  Eventually
1481      * we'll find a node that's the parent of both ancestors.  Then
1482      * find the first ancestor in the parent's list of subnodes.
1483      */
1484     for (i = depth; i > 0; i--) {
1485         if (n1Ptr->parent == n2Ptr->parent) {
1486             break;
1487         }
1488         n1Ptr = n1Ptr->parent;
1489         n2Ptr = n2Ptr->parent;
1490     }
1491     for (nodePtr = n1Ptr->parent->first; nodePtr != NULL;
1492          nodePtr = nodePtr->next) {
1493         if (nodePtr == n1Ptr) {
1494             return TRUE;
1495         } else if (nodePtr == n2Ptr) {
1496             return FALSE;
1497         }
1498     }
1499     return FALSE;
1500 }
1501
1502 static int
1503 CallTraces(
1504     Tcl_Interp *interp,
1505     TreeClient *sourcePtr,      /* Client holding a reference to the
1506                                  * tree.  If NULL, indicates to
1507                                  * execute all handlers, including
1508                                  * those of the caller. */
1509     TreeObject *treeObjPtr,     /* Tree that was changed. */
1510     Node *nodePtr,              /* Node that received the event. */
1511     Blt_TreeKey key,
1512     unsigned int flags,
1513     int *cnt)
1514 {
1515     Blt_ChainLink *l1Ptr, *l2Ptr;
1516     TreeClient *clientPtr;
1517     TraceHandler *tracePtr;
1518     unsigned int inode = nodePtr->inode;
1519     int result;
1520
1521     for(l1Ptr = Blt_ChainFirstLink(treeObjPtr->clients);
1522         l1Ptr != NULL; l1Ptr = Blt_ChainNextLink(l1Ptr)) {
1523         clientPtr = Blt_ChainGetValue(l1Ptr);
1524         for(l2Ptr = Blt_ChainFirstLink(clientPtr->traces);
1525             l2Ptr != NULL; l2Ptr = Blt_ChainNextLink(l2Ptr)) {
1526             tracePtr = Blt_ChainGetValue(l2Ptr);
1527             if ((tracePtr->mask & flags) == 0) {
1528                 continue;       /* Flags don't match. */
1529             }
1530             if ((clientPtr == sourcePtr) &&
1531                 (tracePtr->mask & TREE_TRACE_FOREIGN_ONLY)) {
1532                 continue;       /* This client initiated the trace. */
1533             }
1534             if ((tracePtr->nodePtr != NULL) && (tracePtr->nodePtr != nodePtr)) {
1535                 continue;       /* Nodes don't match. */
1536             }
1537             if ((tracePtr->keyPattern != NULL) &&
1538                 (!Tcl_StringMatch(key, tracePtr->keyPattern))) {
1539                 continue;       /* Key pattern doesn't match. */
1540             }
1541             if ((tracePtr->withTag != NULL) &&
1542                 (!Blt_TreeHasTag(clientPtr, nodePtr, tracePtr->withTag))) {
1543                 continue;       /* Doesn't have the tag. */
1544             }
1545             nodePtr->flags |= TREE_TRACE_ACTIVE;
1546             *cnt += 1;
1547
1548             Tcl_Preserve(treeObjPtr);
1549             result = (*tracePtr->proc) (tracePtr->clientData, treeObjPtr->interp,
1550                 nodePtr, key, flags);
1551             if (result != TCL_OK) {
1552                 Tcl_Release(treeObjPtr);
1553                 if ((tracePtr->mask & TREE_TRACE_BGERROR) && interp != NULL) {
1554                     Tcl_BackgroundError(interp);
1555                 } else {
1556                     nodePtr->flags &= ~TREE_TRACE_ACTIVE;
1557                     return TCL_ERROR;
1558                 }
1559             }
1560              nodePtr->flags &= ~TREE_TRACE_ACTIVE;
1561              if (Blt_TreeNodeDeleted(nodePtr) || nodePtr->inode != inode) {
1562                  Tcl_Release(treeObjPtr);
1563                  return TCL_ERROR;
1564             }
1565             if (treeObjPtr->delete) {
1566                  Tcl_Release(treeObjPtr);
1567                  if (interp != NULL) {
1568                      Tcl_AppendResult(interp, "tree deleted", 0);
1569                  }
1570                  return TCL_ERROR;
1571             }
1572             Tcl_Release(treeObjPtr);
1573             /* nodePtr = GetNode(treeObjPtr, inode);
1574             if (nodePtr == NULL) {
1575                 if (interp != NULL) {
1576                     Tcl_AppendResult(interp, "node deleted", 0);
1577                 }
1578                 return TCL_ERROR;
1579             }*/
1580         }
1581     }
1582     return TCL_OK;
1583 }
1584
1585 static Value *
1586 GetTreeValue(
1587     Tcl_Interp *interp,
1588     TreeClient *clientPtr,
1589     Node *nodePtr,
1590     Blt_TreeKey key)
1591 {
1592     register Value *valuePtr;
1593
1594     valuePtr = TreeFindValue(nodePtr, key);
1595     if (valuePtr == NULL) {
1596         if (interp != NULL) {
1597             Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1598                              (char *)NULL);
1599         }
1600         return NULL;
1601     }
1602     if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1603         if (interp != NULL) {
1604             Tcl_AppendResult(interp, "can't access private field \"",
1605                              key, "\"", (char *)NULL);
1606         }
1607         return NULL;
1608     }
1609     return valuePtr;
1610 }
1611
1612 int
1613 Blt_TreePrivateValue(
1614     Tcl_Interp *interp,
1615     TreeClient *clientPtr,
1616     Node *nodePtr,
1617     Blt_TreeKey key)
1618 {
1619     Value *valuePtr;
1620
1621     valuePtr = TreeFindValue(nodePtr, key);
1622     if (valuePtr == NULL) {
1623         if (interp != NULL) {
1624             Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1625                              (char *)NULL);
1626         }
1627         return TCL_ERROR;
1628     }
1629     valuePtr->owner = clientPtr;
1630     return TCL_OK;
1631 }
1632
1633 int
1634 Blt_TreePublicValue(
1635     Tcl_Interp *interp,
1636     TreeClient *clientPtr,
1637     Node *nodePtr,
1638     Blt_TreeKey key)
1639 {
1640     Value *valuePtr;
1641
1642     valuePtr = TreeFindValue(nodePtr, key);
1643     if (valuePtr == NULL) {
1644         if (interp != NULL) {
1645             Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1646                              (char *)NULL);
1647         }
1648         return TCL_ERROR;
1649     }
1650     if (valuePtr->owner != clientPtr) {
1651         if (interp != NULL) {
1652             Tcl_AppendResult(interp, "not the owner of \"", key, "\"",
1653                      (char *)NULL);
1654         }
1655         return TCL_ERROR;
1656     }
1657     valuePtr->owner = NULL;
1658     return TCL_OK;
1659 }
1660
1661 int
1662 Blt_TreeValueExistsByKey(clientPtr, nodePtr, key)
1663     TreeClient *clientPtr;
1664     Node *nodePtr;
1665     Blt_TreeKey key;
1666 {
1667     register Value *valuePtr;
1668     int cnt;
1669     TreeObject *treeObjPtr = nodePtr->treeObject;
1670     Tcl_Interp *interp = treeObjPtr->interp;
1671
1672     valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
1673     if (valuePtr == NULL && (!(nodePtr->flags & TREE_TRACE_ACTIVE))) {
1674         if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
1675             TREE_TRACE_EXISTS, &cnt) != TCL_OK) {
1676             Tcl_ResetResult(interp);
1677         } else {
1678             valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
1679         }
1680     }
1681     if (valuePtr == NULL) {
1682         return FALSE;
1683     }
1684     return TRUE;
1685 }
1686
1687 int
1688 Blt_TreeGetValueByKey(
1689     Tcl_Interp *interp,
1690     TreeClient *clientPtr,
1691     Node *nodePtr,
1692     Blt_TreeKey key,
1693     Tcl_Obj **objPtrPtr)
1694 {
1695     register Value *valuePtr;
1696     TreeObject *treeObjPtr = nodePtr->treeObject;
1697     int cnt = 0;
1698
1699     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1700         if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
1701                    TREE_TRACE_READ, &cnt) != TCL_OK) {
1702             return TCL_ERROR;
1703         }
1704     }
1705     valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
1706     if (valuePtr == NULL) {
1707         return TCL_ERROR;
1708     }
1709     *objPtrPtr = valuePtr->objPtr;
1710     return TCL_OK;
1711 }
1712
1713 int
1714 bltTreeGetValueByKey(
1715     Tcl_Interp *interp,
1716     TreeClient *clientPtr,
1717     Node *nodePtr,
1718     Blt_TreeKey key,
1719     Value** valuePtrPtr)
1720 {
1721     register Value *valuePtr;
1722     TreeObject *treeObjPtr = nodePtr->treeObject;
1723     int cnt = 0;
1724
1725     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1726         if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
1727                    TREE_TRACE_READ, &cnt) != TCL_OK) {
1728             return TCL_ERROR;
1729         }
1730     }
1731     valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
1732     if (valuePtr == NULL) {
1733         return TCL_ERROR;
1734     }
1735     *valuePtrPtr = valuePtr;
1736     return TCL_OK;
1737 }
1738
1739 static void
1740 UpdateOldValue(
1741     TreeClient *clientPtr,
1742     Tcl_Obj *objPtr)
1743 {
1744     if (clientPtr->oldValue != NULL) {
1745         Tcl_DecrRefCount(clientPtr->oldValue);
1746     }
1747     clientPtr->oldValue = objPtr;
1748 }
1749
1750 void
1751 Blt_TreeOldValue(
1752     Tcl_Interp *interp,
1753     TreeClient *clientPtr,
1754     Tcl_Obj **oldPtr,
1755     Tcl_Obj *newPtr)
1756 {
1757     if (newPtr) {
1758         if (clientPtr->oldValue != NULL) {
1759             Tcl_DecrRefCount(clientPtr->oldValue);
1760         }
1761         clientPtr->oldValue = newPtr;
1762         Tcl_IncrRefCount(clientPtr->oldValue);
1763     } else if (oldPtr != NULL) {
1764         *oldPtr = clientPtr->oldValue;
1765     }
1766 }
1767
1768 int
1769 Blt_TreeSetValueByKey(
1770     Tcl_Interp *interp,
1771     TreeClient *clientPtr,
1772     Node *nodePtr,              /* Node to be updated. */
1773     Blt_TreeKey key,            /* Identifies the field key. */
1774     Tcl_Obj *objPtr)            /* New value of field. */
1775 {
1776     TreeObject *treeObjPtr;
1777     Value *valuePtr;
1778     unsigned int flags;
1779     int isNew = 0, cnt = 0;
1780
1781     if (nodePtr == NULL) {
1782         return TCL_ERROR;
1783     }
1784     treeObjPtr = nodePtr->treeObject;
1785     assert(objPtr != NULL);
1786     if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
1787         valuePtr = TreeFindValue(nodePtr, key);
1788         if (valuePtr == NULL) {
1789             if (interp != NULL) {
1790                 Tcl_AppendResult(interp, "fixed field \"", key, "\"",
1791                     (char *)NULL);
1792             }
1793             return TCL_ERROR;
1794         }
1795     } else {
1796         valuePtr = TreeCreateValue(nodePtr, key, &isNew);
1797     }
1798     if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1799         if (interp != NULL) {
1800             Tcl_AppendResult(interp, "can't set private field \"",
1801                              key, "\"", (char *)NULL);
1802         }
1803         return TCL_ERROR;
1804     }
1805     SetModified(nodePtr);
1806     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1807         UpdateOldValue(clientPtr, valuePtr->objPtr);
1808         valuePtr->objPtr = NULL;
1809     }
1810     if (objPtr != valuePtr->objPtr) {
1811         Tcl_IncrRefCount(objPtr);
1812         if (valuePtr->objPtr != NULL) {
1813             Tcl_DecrRefCount(valuePtr->objPtr);
1814         }
1815         valuePtr->objPtr = objPtr;
1816     }
1817     flags = TREE_TRACE_WRITE;
1818     if (isNew) {
1819         flags |= TREE_TRACE_CREATE;
1820     }
1821     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1822         return CallTraces(interp, clientPtr, treeObjPtr, nodePtr, valuePtr->key,
1823                 flags, &cnt);
1824     }
1825     return TCL_OK;
1826 }
1827
1828 int
1829 Blt_TreeUnsetValueByKey(
1830     Tcl_Interp *interp,
1831     TreeClient *clientPtr,
1832     Node *nodePtr,              /* Node to be updated. */
1833     Blt_TreeKey key)            /* Name of field in node. */
1834 {
1835     TreeObject *treeObjPtr = nodePtr->treeObject;
1836     Value *valuePtr;
1837     int cnt = 0;
1838
1839     if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
1840         if (interp != NULL) {
1841             Tcl_AppendResult(interp, "fixed field", 0);
1842         }
1843         return TCL_ERROR;
1844     }
1845     valuePtr = TreeFindValue(nodePtr, key);
1846     if (valuePtr == NULL) {
1847         return TCL_OK;          /* It's okay to unset values that don't
1848                                  * exist in the node. */
1849     }
1850     if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1851         if (interp != NULL) {
1852             Tcl_AppendResult(interp, "can't unset private field \"",
1853                              key, "\"", (char *)NULL);
1854         }
1855         return TCL_ERROR;
1856     }
1857     SetModified(nodePtr);
1858     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1859         UpdateOldValue(clientPtr, valuePtr->objPtr);
1860         valuePtr->objPtr = NULL;
1861     }
1862     TreeDeleteValue(nodePtr, valuePtr);
1863     return CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key, TREE_TRACE_UNSET, &cnt);
1864 }
1865
1866 static int
1867 ParseParentheses(
1868     Tcl_Interp *interp,
1869     CONST char *string,
1870     char **leftPtr,
1871     char **rightPtr)
1872 {
1873     register char *p;
1874     char *left, *right;
1875
1876     left = right = NULL;
1877     for (p = (char *)string; *p != '\0'; p++) {
1878         if (*p == '(') {
1879             left = p;
1880         } else if (*p == ')') {
1881             right = p;
1882         }
1883     }
1884     if (left != right) {
1885         if (((left != NULL) && (right == NULL)) ||
1886             ((left == NULL) && (right != NULL)) ||
1887             (left > right) || (right != (p - 1))) {
1888             if (interp != NULL) {
1889                 Tcl_AppendResult(interp, "bad array specification \"", string,
1890                              "\"", (char *)NULL);
1891             }
1892             return TCL_ERROR;
1893         }
1894     }
1895     *leftPtr = left;
1896     *rightPtr = right;
1897     return TCL_OK;
1898 }
1899
1900 int
1901 Blt_TreeGetValue(
1902     Tcl_Interp *interp,
1903     TreeClient *clientPtr,
1904     Node *nodePtr,
1905     CONST char *string,         /* String identifying the field in node. */
1906     Tcl_Obj **objPtrPtr)
1907 {
1908     char *left, *right;
1909     int result;
1910
1911     if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1912         return TCL_ERROR;
1913     }
1914     if (left != NULL) {
1915         Tcl_DString kStr, iStr;
1916         Tcl_DStringInit(&kStr);
1917         Tcl_DStringInit(&iStr);
1918         Tcl_DStringAppend(&kStr, left+1, right-left-1);
1919         Tcl_DStringAppend(&iStr, string, left-string);
1920         result = Blt_TreeGetArrayValue(interp, clientPtr, nodePtr,
1921            Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), objPtrPtr);
1922         Tcl_DStringFree(&kStr);
1923         Tcl_DStringFree(&iStr);
1924     } else {
1925         result = Blt_TreeGetValueByKey(interp, clientPtr, nodePtr,
1926                 Blt_TreeKeyGet(NULL, clientPtr->treeObject,string), objPtrPtr);
1927     }
1928     return result;
1929 }
1930
1931 int
1932 Blt_TreeSetValue(
1933     Tcl_Interp *interp,
1934     TreeClient *clientPtr,
1935     Node *nodePtr,              /* Node to be updated. */
1936     CONST char *string,         /* String identifying the field in node. */
1937     Tcl_Obj *valueObjPtr)       /* New value of field. If NULL, field
1938                                  * is deleted. */
1939 {
1940     char *left, *right;
1941     int result;
1942
1943     if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
1944         return Blt_TreeUpdateValue( interp, clientPtr, nodePtr, string, valueObjPtr);
1945     }
1946     if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1947         return TCL_ERROR;
1948     }
1949     if (left != NULL) {
1950         Tcl_DString kStr, iStr;
1951         Tcl_DStringInit(&kStr);
1952         Tcl_DStringInit(&iStr);
1953         Tcl_DStringAppend(&kStr, left+1, right-left-1);
1954         Tcl_DStringAppend(&iStr, string, left-string);
1955         result = Blt_TreeSetArrayValue(interp, clientPtr, nodePtr,
1956            Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), valueObjPtr);
1957         Tcl_DStringFree(&kStr);
1958         Tcl_DStringFree(&iStr);
1959     } else {
1960         result = Blt_TreeSetValueByKey(interp, clientPtr, nodePtr,
1961                                Blt_TreeKeyGet(NULL, clientPtr->treeObject,string), valueObjPtr);
1962     }
1963     return result;
1964 }
1965
1966 int
1967 Blt_TreeUpdateValue(
1968     Tcl_Interp *interp,
1969     TreeClient *clientPtr,
1970     Node *nodePtr,              /* Node to be updated. */
1971     CONST char *string,         /* String identifying the field in node. */
1972     Tcl_Obj *valueObjPtr)       /* New value of field. If NULL, field
1973                                  * is deleted. */
1974 {
1975     char *left, *right;
1976     int result;
1977     Blt_TreeKey key;
1978
1979     if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1980         return TCL_ERROR;
1981     }
1982     if (left != NULL) {
1983         Tcl_DString kStr, iStr;
1984         Tcl_DStringInit(&kStr);
1985         Tcl_DStringInit(&iStr);
1986         Tcl_DStringAppend(&kStr, left+1, right-left-1);
1987         Tcl_DStringAppend(&iStr, string, left-string);
1988         result = Blt_TreeUpdateArrayValue(interp, clientPtr, nodePtr,
1989            Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr), valueObjPtr);
1990         Tcl_DStringFree(&kStr);
1991         Tcl_DStringFree(&iStr);
1992     } else {
1993         key = Blt_TreeKeyGet(NULL, clientPtr->treeObject,string);
1994         if (GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key) == NULL) {
1995             if (interp != NULL) {
1996                 Tcl_AppendResult(interp, "unknown key: ", string, 0);
1997             }
1998             return TCL_ERROR;
1999         }
2000         result = Blt_TreeSetValueByKey(interp, clientPtr, nodePtr,
2001             key, valueObjPtr);
2002     }
2003     return result;
2004 }
2005
2006 int
2007 Blt_TreeUnsetValue(
2008     Tcl_Interp *interp,
2009     TreeClient *clientPtr,
2010     Node *nodePtr,              /* Node to be updated. */
2011     CONST char *string)         /* String identifying the field in node. */
2012 {
2013     char *left, *right;
2014     int result;
2015
2016     if (nodePtr->flags & TREE_NODE_FIXED_FIELDS) {
2017         if (interp != NULL) {
2018             Tcl_AppendResult(interp, "fixed field", 0);
2019         }
2020         return TCL_ERROR;
2021     }
2022     if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
2023         return TCL_ERROR;
2024     }
2025     if (left != NULL) {
2026         Tcl_DString kStr, iStr;
2027         Tcl_DStringInit(&kStr);
2028         Tcl_DStringInit(&iStr);
2029         Tcl_DStringAppend(&kStr, left+1, right-left-1);
2030         Tcl_DStringAppend(&iStr, string, left-string);
2031         result = Blt_TreeUnsetArrayValue(interp, clientPtr, nodePtr,
2032            Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr));
2033         Tcl_DStringFree(&kStr);
2034         Tcl_DStringFree(&iStr);
2035     } else {
2036         result = Blt_TreeUnsetValueByKey(interp, clientPtr, nodePtr,
2037                 Blt_TreeKeyGet(NULL, clientPtr->treeObject,string));
2038     }
2039     return result;
2040 }
2041
2042 int
2043 Blt_TreeValueExists(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
2044 {
2045     char *left, *right;
2046     int result;
2047
2048     if (ParseParentheses((Tcl_Interp *)NULL, string, &left, &right) != TCL_OK) {
2049         return FALSE;
2050     }
2051     if (left != NULL) {
2052         Tcl_DString kStr, iStr;
2053         Tcl_DStringInit(&kStr);
2054         Tcl_DStringInit(&iStr);
2055         Tcl_DStringAppend(&kStr, left+1, right-left-1);
2056         Tcl_DStringAppend(&iStr, string, left-string);
2057         result = Blt_TreeArrayValueExists(clientPtr, nodePtr,
2058            Tcl_DStringValue(&iStr), Tcl_DStringValue(&kStr));
2059         Tcl_DStringFree(&kStr);
2060         Tcl_DStringFree(&iStr);
2061     } else {
2062         result = Blt_TreeValueExistsByKey(clientPtr, nodePtr,
2063                 Blt_TreeKeyGet(NULL, clientPtr->treeObject,string));
2064     }
2065     return result;
2066 }
2067
2068 Blt_TreeKey
2069 Blt_TreeFirstKey(
2070     TreeClient *clientPtr,
2071     Node *nodePtr,
2072     Blt_TreeKeySearch *iterPtr)
2073 {
2074     Value *valuePtr;
2075
2076     valuePtr = TreeFirstValue(nodePtr, iterPtr);
2077     if (valuePtr == NULL) {
2078         return NULL;
2079     }
2080     while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
2081         valuePtr = TreeNextValue(iterPtr);
2082         if (valuePtr == NULL) {
2083             return NULL;
2084         }
2085     }
2086     return valuePtr->key;
2087 }
2088
2089 Blt_TreeKey
2090 Blt_TreeNextKey(TreeClient *clientPtr, Blt_TreeKeySearch *iterPtr)
2091 {
2092     Value *valuePtr;
2093
2094     valuePtr = TreeNextValue(iterPtr);
2095     if (valuePtr == NULL) {
2096         return NULL;
2097     }
2098     while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
2099         valuePtr = TreeNextValue(iterPtr);
2100         if (valuePtr == NULL) {
2101             return NULL;
2102         }
2103     }
2104     return valuePtr->key;
2105 }
2106
2107 int Blt_TreeCountKeys(TreeClient *clientPtr, Node *nodePtr) {
2108     int cnt = 0;
2109     Blt_TreeKey key;
2110     Blt_TreeKeySearch cursor;
2111
2112
2113     for (key = Blt_TreeFirstKey(clientPtr, nodePtr, &cursor); key != NULL;
2114         key = Blt_TreeNextKey(clientPtr, &cursor)) {
2115         cnt++;
2116     }
2117     return cnt;
2118 }
2119
2120
2121 int
2122 Blt_TreeIsAncestor(Node *n1Ptr, Node *n2Ptr)
2123 {
2124     if (n2Ptr != NULL) {
2125         n2Ptr = n2Ptr->parent;
2126         while (n2Ptr != NULL) {
2127             if (n2Ptr == n1Ptr) {
2128                 return TRUE;
2129             }
2130             n2Ptr = n2Ptr->parent;
2131         }
2132     }
2133     return FALSE;
2134 }
2135
2136 /*
2137  *----------------------------------------------------------------------
2138  *
2139  * Blt_TreeSortNode --
2140  *
2141  *      Sorts the subnodes at a given node.
2142  *
2143  * Results:
2144  *      Always returns TCL_OK.
2145  *
2146  *----------------------------------------------------------------------
2147  */
2148 int
2149 Blt_TreeSortNode(
2150     TreeClient *clientPtr,
2151     Node *nodePtr,
2152     Blt_TreeCompareNodesProc *proc)
2153 {
2154     Node **nodeArr;
2155     Node *childPtr;
2156     int nNodes;
2157     register Node **p;
2158
2159     nNodes = nodePtr->nChildren;
2160     if (nNodes < 2) {
2161         return TCL_OK;
2162     }
2163     nodeArr = Blt_Malloc((nNodes + 1) * sizeof(Node *));
2164     if (nodeArr == NULL) {
2165         return TCL_ERROR;       /* Out of memory. */
2166     }
2167     for (p = nodeArr, childPtr = nodePtr->first; childPtr != NULL;
2168          childPtr = childPtr->next, p++) {
2169         *p = childPtr;
2170     }
2171     *p = NULL;
2172
2173     qsort((char *)nodeArr, nNodes, sizeof(Node *), (QSortCompareProc *)proc);
2174     for (p = nodeArr; *p != NULL; p++) {
2175         UnlinkNode(*p);
2176         LinkBefore(nodePtr, *p, (Blt_TreeNode)NULL);
2177     }
2178     Blt_Free(nodeArr);
2179     return NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_SORT);
2180 }
2181
2182 #define TEST_RESULT(result) \
2183         switch (result) { \
2184         case TCL_CONTINUE: \
2185             return TCL_OK; \
2186         case TCL_OK: \
2187             break; \
2188         default: \
2189             return (result); \
2190         }
2191
2192 int
2193 Blt_TreeApply(
2194     Node *nodePtr,              /* Root node of subtree. */
2195     Blt_TreeApplyProc *proc,    /* Procedure to call for each node. */
2196     ClientData clientData)      /* One-word of data passed when calling
2197                                  * proc. */
2198 {
2199     Node *childPtr, *nextPtr;
2200     int result;
2201
2202     for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
2203
2204         /*
2205          * Get the next link in the chain before calling Blt_TreeApply
2206          * recursively.  This is because the apply callback may delete
2207          * the node and its link.
2208          */
2209
2210         nextPtr = childPtr->next;
2211         if (Blt_TreeNodeDeleted(childPtr)) return TCL_OK;
2212         result = Blt_TreeApply(childPtr, proc, clientData);
2213         TEST_RESULT(result);
2214     }
2215     if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
2216     return (*proc) (nodePtr, clientData, TREE_POSTORDER);
2217 }
2218
2219 int
2220 Blt_TreeApplyDFS(
2221     Node *nodePtr,              /* Root node of subtree. */
2222     Blt_TreeApplyProc *proc,    /* Procedure to call for each node. */
2223     ClientData clientData,      /* One-word of data passed when calling
2224                                  * proc. */
2225     int order)                  /* Order of traversal. */
2226 {
2227     Node *childPtr, *nextPtr;
2228     int result;
2229
2230     if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
2231     if (order & TREE_PREORDER) {
2232         result = (*proc) (nodePtr, clientData, TREE_PREORDER);
2233         TEST_RESULT(result);
2234     }
2235     childPtr = nodePtr->first;
2236     if (order & TREE_INORDER) {
2237         if (childPtr != NULL) {
2238             result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
2239             TEST_RESULT(result);
2240             childPtr = childPtr->next;
2241         }
2242         result = (*proc) (nodePtr, clientData, TREE_INORDER);
2243         TEST_RESULT(result);
2244     }
2245     for (/* empty */; childPtr != NULL; childPtr = nextPtr) {
2246         /*
2247          * Get the next link in the chain before calling
2248          * Blt_TreeApply recursively.  This is because the
2249          * apply callback may delete the node and its link.
2250          */
2251         nextPtr = childPtr->next;
2252         if (Blt_TreeNodeDeleted(childPtr)) break;
2253         result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
2254         TEST_RESULT(result);
2255     }
2256     if (Blt_TreeNodeDeleted(nodePtr)) return TCL_OK;
2257     if (order & TREE_POSTORDER) {
2258         return (*proc) (nodePtr, clientData, TREE_POSTORDER);
2259     }
2260     return TCL_OK;
2261 }
2262
2263 int
2264 Blt_TreeApplyBFS(nodePtr, proc, clientData)
2265     Node *nodePtr;              /* Root node of subtree. */
2266     Blt_TreeApplyProc *proc;    /* Procedure to call for each node. */
2267     ClientData clientData;      /* One-word of data passed when calling
2268                                  * proc. */
2269 {
2270     Blt_Chain *queuePtr;
2271     Blt_ChainLink *linkPtr, *nextPtr;
2272     Node *childPtr;
2273     int result;
2274
2275     queuePtr = Blt_ChainCreate();
2276     linkPtr = Blt_ChainAppend(queuePtr, nodePtr);
2277     while (linkPtr != NULL) {
2278         nodePtr = Blt_ChainGetValue(linkPtr);
2279         /* Add the children to the queue. */
2280         for (childPtr = nodePtr->first; childPtr != NULL;
2281              childPtr = childPtr->next) {
2282             Blt_ChainAppend(queuePtr, childPtr);
2283         }
2284         if (Blt_TreeNodeDeleted(nodePtr)) break;
2285         /* Process the node. */
2286         result = (*proc) (nodePtr, clientData, TREE_BREADTHFIRST);
2287         switch (result) {
2288         case TCL_CONTINUE:
2289             Blt_ChainDestroy(queuePtr);
2290             return TCL_OK;
2291         case TCL_OK:
2292             break;
2293         default:
2294             Blt_ChainDestroy(queuePtr);
2295             return result;
2296         }
2297         /* Remove the node from the queue. */
2298         nextPtr = Blt_ChainNextLink(linkPtr);
2299         Blt_ChainDeleteLink(queuePtr, linkPtr);
2300         linkPtr = nextPtr;
2301     }
2302     Blt_ChainDestroy(queuePtr);
2303     return TCL_OK;
2304 }
2305
2306 static TreeClient *
2307 NewTreeClient(TreeObject *treeObjPtr, int sharetags)
2308 {
2309     TreeClient *clientPtr;
2310
2311     clientPtr = Blt_Calloc(1, sizeof(TreeClient));
2312     if (clientPtr != NULL) {
2313         Blt_TreeTagTable *tablePtr;
2314         int hascl = (treeObjPtr->clients->headPtr != NULL);
2315
2316         clientPtr->magic = TREE_MAGIC;
2317         clientPtr->linkPtr = Blt_ChainAppend(treeObjPtr->clients, clientPtr);
2318         clientPtr->events = Blt_ChainCreate();
2319         clientPtr->traces = Blt_ChainCreate();
2320         clientPtr->treeObject = treeObjPtr;
2321         clientPtr->root = treeObjPtr->root;
2322         if (sharetags && hascl) {
2323              TreeClient *ctPtr;
2324              ctPtr = Blt_ChainGetValue(treeObjPtr->clients->headPtr);
2325              if (ctPtr && ctPtr->tagTablePtr) {
2326                  clientPtr->tagTablePtr = ctPtr->tagTablePtr;
2327                  clientPtr->tagTablePtr->refCount++;
2328              }
2329          }
2330          if (clientPtr->tagTablePtr == NULL) {
2331              tablePtr = Blt_Malloc(sizeof(Blt_TreeTagTable));
2332              Blt_InitHashTable(&tablePtr->tagTable, BLT_STRING_KEYS);
2333              tablePtr->refCount = 1;
2334              clientPtr->tagTablePtr = tablePtr;
2335          }
2336     }
2337     return clientPtr;
2338 }
2339
2340 int
2341 Blt_TreeCreate(
2342     Tcl_Interp *interp,         /* Interpreter to report errors back to. */
2343     CONST char *name,           /* Name of tree in namespace.  Tree
2344                                  * must not already exist. */
2345     TreeClient **clientPtrPtr)  /* (out) Client token of newly created
2346                                  * tree.  Releasing the token will
2347                                  * free the tree.  If NULL, no token
2348                                  * is generated. */
2349
2350 {
2351     Tcl_DString dString;
2352     Tcl_Namespace *nsPtr;
2353     TreeInterpData *dataPtr;
2354     TreeObject *treeObjPtr;
2355     CONST char *treeName;
2356     char string[200];
2357
2358     dataPtr = GetTreeInterpData(interp);
2359     if (name != NULL) {
2360         /* Check if this tree already exists the current namespace. */
2361         treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_CURRENT);
2362         if (treeObjPtr != NULL) {
2363             if (interp != NULL)
2364                Tcl_AppendResult(interp, "a tree object \"", name,
2365                              "\" already exists", (char *)NULL);
2366             return TCL_ERROR;
2367         }
2368     } else {
2369         /* Generate a unique tree name in the current namespace. */
2370         do  {
2371             sprintf(string, "tree%d", dataPtr->nextId++);
2372         } while (GetTreeObject(interp, string, NS_SEARCH_CURRENT) != NULL);
2373         name = string;
2374     }
2375     /*
2376      * Tear apart and put back together the namespace-qualified name
2377      * of the tree. This is to ensure that naming is consistent.
2378      */
2379     treeName = name;
2380     if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
2381         if (interp != NULL)
2382            Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
2383                 (char *)NULL);
2384         return TCL_ERROR;
2385     }
2386     if (nsPtr == NULL) {
2387         /*
2388          * Note: Unlike Tcl_CreateCommand, an unqualified name
2389          * doesn't imply the global namespace, but the current one.
2390          */
2391         nsPtr = Tcl_GetCurrentNamespace(interp);
2392     }
2393     name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
2394     treeObjPtr = NewTreeObject(dataPtr, interp, name);
2395     if (treeObjPtr == NULL) {
2396         if (interp != NULL)
2397             Tcl_AppendResult(interp, "can't allocate tree \"", name, "\"",
2398                 (char *)NULL);
2399         Tcl_DStringFree(&dString);
2400         return TCL_ERROR;
2401     }
2402     Tcl_DStringFree(&dString);
2403     if (clientPtrPtr != NULL) {
2404         TreeClient *clientPtr;
2405
2406         clientPtr = NewTreeClient(treeObjPtr, 0);
2407         if (clientPtr == NULL) {
2408             if (interp != NULL)
2409                Tcl_AppendResult(interp, "can't allocate tree token",(char *)NULL);
2410             return TCL_ERROR;
2411         }
2412         *clientPtrPtr = clientPtr;
2413     }
2414     return TCL_OK;
2415 }
2416
2417 int
2418 Blt_TreeGetToken(
2419     Tcl_Interp *interp,         /* Interpreter to report errors back to. */
2420     CONST char *name,           /* Name of tree in namespace. */
2421     TreeClient **clientPtrPtr)
2422 {
2423     TreeClient *clientPtr;
2424     TreeObject *treeObjPtr;
2425
2426     treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
2427     if (treeObjPtr == NULL) {
2428         if (interp != NULL)
2429             Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"",
2430                          (char *)NULL);
2431         return TCL_ERROR;
2432     }
2433     clientPtr = NewTreeClient(treeObjPtr, 0);
2434     if (clientPtr == NULL) {
2435         if (interp != NULL)
2436             Tcl_AppendResult(interp, "can't allocate token for tree \"",
2437                          name, "\"", (char *)NULL);
2438         return TCL_ERROR;
2439     }
2440     *clientPtrPtr = clientPtr;
2441     return TCL_OK;
2442 }
2443
2444 int
2445 Blt_TreeGetTokenTag(
2446     Tcl_Interp *interp,         /* Interpreter to report errors back to. */
2447     CONST char *name,           /* Name of tree in namespace. */
2448     TreeClient **clientPtrPtr)
2449 {
2450     TreeClient *clientPtr;
2451     TreeObject *treeObjPtr;
2452
2453     treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
2454     if (treeObjPtr == NULL) {
2455         if (interp != NULL)
2456             Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"",
2457                          (char *)NULL);
2458         return TCL_ERROR;
2459     }
2460     clientPtr = NewTreeClient(treeObjPtr, 1);
2461     if (clientPtr == NULL) {
2462         if (interp != NULL)
2463             Tcl_AppendResult(interp, "can't allocate token for tree \"",
2464                          name, "\"", (char *)NULL);
2465         return TCL_ERROR;
2466     }
2467     *clientPtrPtr = clientPtr;
2468     return TCL_OK;
2469 }
2470
2471 void
2472 Blt_TreeReleaseToken(TreeClient *clientPtr)
2473 {
2474     TreeObject *treeObjPtr;
2475     Blt_ChainLink *linkPtr;
2476     EventHandler *notifyPtr;
2477     TraceHandler *tracePtr;
2478
2479     if (clientPtr->magic != TREE_MAGIC) {
2480         fprintf(stderr, "invalid tree object token 0x%lx\n",
2481                 (unsigned long)clientPtr);
2482         return;
2483     }
2484     /* Remove any traces that may be set. */
2485     for (linkPtr = Blt_ChainFirstLink(clientPtr->traces); linkPtr != NULL;
2486          linkPtr = Blt_ChainNextLink(linkPtr)) {
2487         tracePtr = Blt_ChainGetValue(linkPtr);
2488         if (tracePtr->keyPattern != NULL) {
2489             Blt_Free(tracePtr->keyPattern);
2490         }
2491         Blt_Free(tracePtr);
2492     }
2493     Blt_ChainDestroy(clientPtr->traces);
2494     /* And any event handlers. */
2495     for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
2496         linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
2497         notifyPtr = Blt_ChainGetValue(linkPtr);
2498         if (notifyPtr->notifyPending) {
2499             Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
2500         }
2501         Blt_Free(notifyPtr);
2502     }
2503     if (clientPtr->tagTablePtr != NULL) {
2504         ReleaseTagTable(clientPtr->tagTablePtr);
2505     }
2506     Blt_ChainDestroy(clientPtr->events);
2507     treeObjPtr = clientPtr->treeObject;
2508     if (treeObjPtr != NULL) {
2509         /* Remove the client from the server's list */
2510         Blt_ChainDeleteLink(treeObjPtr->clients, clientPtr->linkPtr);
2511         if (Blt_ChainGetLength(treeObjPtr->clients) == 0) {
2512             treeObjPtr->delete = 1;
2513             Tcl_EventuallyFree(treeObjPtr, DestroyTreeObject);
2514             /* DestroyTreeObject(treeObjPtr); */
2515         }
2516     }
2517     clientPtr->magic = 0;
2518     Blt_Free(clientPtr);
2519 }
2520
2521 int
2522 Blt_TreeExists(interp, name)
2523     Tcl_Interp *interp;         /* Interpreter to report errors back to. */
2524     CONST char *name;           /* Name of tree in designated namespace. */
2525 {
2526     TreeObject *treeObjPtr;
2527
2528     treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
2529     if (treeObjPtr == NULL) {
2530         Tcl_ResetResult(interp);
2531         return 0;
2532     }
2533     return 1;
2534 }
2535
2536 /*ARGSUSED*/
2537 static int
2538 SizeApplyProc(
2539     Node *nodePtr,              /* Not used. */
2540     ClientData clientData,
2541     int order)                  /* Not used. */
2542 {
2543     int *sumPtr = clientData;
2544     *sumPtr = *sumPtr + 1;
2545     return TCL_OK;
2546 }
2547
2548 int
2549 Blt_TreeSize(Node *nodePtr)
2550 {
2551     int sum;
2552
2553     sum = 0;
2554     Blt_TreeApply(nodePtr, SizeApplyProc, &sum);
2555     return sum;
2556 }
2557
2558
2559 void
2560 Blt_TreeCreateEventHandler(
2561     TreeClient *clientPtr,
2562     unsigned int mask,
2563     Blt_TreeNotifyEventProc *proc,
2564     ClientData clientData)
2565 {
2566     Blt_ChainLink *linkPtr;
2567     EventHandler *notifyPtr;
2568
2569     notifyPtr = NULL;           /* Suppress compiler warning. */
2570
2571     /* Check if the event is already handled. */
2572     for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
2573         linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
2574         notifyPtr = Blt_ChainGetValue(linkPtr);
2575         if ((notifyPtr->proc == proc) &&
2576             (notifyPtr->mask == mask) &&
2577             (notifyPtr->clientData == clientData)) {
2578             break;
2579         }
2580     }
2581     if (linkPtr == NULL) {
2582         notifyPtr = Blt_Malloc(sizeof (EventHandler));
2583         assert(notifyPtr);
2584         linkPtr = Blt_ChainAppend(clientPtr->events, notifyPtr);
2585     }
2586     if (proc == NULL) {
2587         Blt_ChainDeleteLink(clientPtr->events, linkPtr);
2588         Blt_Free(notifyPtr);
2589     } else {
2590         notifyPtr->proc = proc;
2591         notifyPtr->clientData = clientData;
2592         notifyPtr->mask = mask;
2593         notifyPtr->notifyPending = FALSE;
2594         notifyPtr->interp = clientPtr->treeObject->interp;
2595     }
2596 }
2597
2598 void
2599 Blt_TreeDeleteEventHandler(
2600     TreeClient *clientPtr,
2601     unsigned int mask,
2602     Blt_TreeNotifyEventProc *proc,
2603     ClientData clientData)
2604 {
2605     Blt_ChainLink *linkPtr;
2606     EventHandler *notifyPtr;
2607
2608     if (!clientPtr) return;
2609     for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
2610         linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
2611         notifyPtr = Blt_ChainGetValue(linkPtr);
2612         if ((notifyPtr->proc == proc) && (notifyPtr->mask == mask) &&
2613             (notifyPtr->clientData == clientData)) {
2614             if (notifyPtr->notifyPending) {
2615                 Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
2616             }
2617             Blt_ChainDeleteLink(clientPtr->events, linkPtr);
2618             Blt_Free(notifyPtr);
2619             return;
2620         }
2621     }
2622 }
2623
2624 /*
2625  *----------------------------------------------------------------------
2626  *
2627  * Blt_TreeNodePath --
2628  *
2629  *----------------------------------------------------------------------
2630  */
2631 char *
2632 Blt_TreeNodePath(Node *nodePtr, Tcl_DString *resultPtr)
2633 {
2634     char **nameArr;             /* Used to stack the component names. */
2635     char *staticSpace[64];
2636     int nLevels;
2637     register int i;
2638
2639     nLevels = nodePtr->depth;
2640     if (nLevels > 64) {
2641         nameArr = Blt_Malloc(nLevels * sizeof(char *));
2642         assert(nameArr);
2643     } else {
2644         nameArr = staticSpace;
2645     }
2646     for (i = nLevels - 1; i >= 0; i--) {
2647         /* Save the name of each ancestor in the name array.
2648          * Note that we ignore the root. */
2649         nameArr[i] = nodePtr->label;
2650         nodePtr = nodePtr->parent;
2651     }
2652     /* Append each the names in the array. */
2653     Tcl_DStringInit(resultPtr);
2654     for (i = 0; i < nLevels; i++) {
2655         Tcl_DStringAppendElement(resultPtr, nameArr[i]);
2656     }
2657     if (nameArr != staticSpace) {
2658         Blt_Free(nameArr);
2659     }
2660     return Tcl_DStringValue(resultPtr);
2661 }
2662
2663 char *
2664 Blt_TreeNodePathStr(Node *nodePtr, Tcl_DString *resultPtr, char *prefix, char *delim)
2665 {
2666     char **nameArr;             /* Used to stack the component names. */
2667     char *staticSpace[64];
2668     int nLevels;
2669     register int i;
2670
2671     nLevels = nodePtr->depth;
2672     if (nLevels > 64) {
2673         nameArr = Blt_Malloc(nLevels * sizeof(char *));
2674         assert(nameArr);
2675     } else {
2676         nameArr = staticSpace;
2677     }
2678     for (i = nLevels - 1; i >= 0; i--) {
2679         /* Save the name of each ancestor in the name array.
2680          * Note that we ignore the root. */
2681         nameArr[i] = nodePtr->label;
2682         nodePtr = nodePtr->parent;
2683     }
2684     /* Append each of the names in the array. */
2685     Tcl_DStringInit(resultPtr);
2686     if (prefix != NULL) {
2687         Tcl_DStringAppend(resultPtr, prefix, -1);
2688     }
2689     for (i = 0; i < nLevels; i++) {
2690         if (i > 0 && delim != NULL) {
2691             Tcl_DStringAppend(resultPtr, delim, -1);
2692         }
2693         Tcl_DStringAppend(resultPtr, nameArr[i], -1);
2694     }
2695     if (nameArr != staticSpace) {
2696         Blt_Free(nameArr);
2697     }
2698     return Tcl_DStringValue(resultPtr);
2699 }
2700
2701 int
2702 Blt_TreeArrayValueExists(
2703     TreeClient *clientPtr,
2704     Node *nodePtr,
2705     CONST char *arrayName,
2706     CONST char *elemName)
2707 {
2708     Blt_TreeKey key;
2709     Blt_HashEntry *hPtr;
2710     Blt_HashTable *tablePtr;
2711     register Value *valuePtr;
2712     int cnt;
2713     TreeObject *treeObjPtr = nodePtr->treeObject;
2714     Tcl_Interp *interp = treeObjPtr->interp;
2715
2716     key = Blt_TreeKeyGet(NULL, clientPtr->treeObject,arrayName);
2717
2718     valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
2719     if (valuePtr == NULL && (!(nodePtr->flags & TREE_TRACE_ACTIVE))) {
2720         if (CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
2721             TREE_TRACE_EXISTS, &cnt) != TCL_OK) {
2722                 Tcl_ResetResult(interp);
2723             } else {
2724                 valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
2725             }
2726     }
2727     if (valuePtr == NULL) {
2728         return FALSE;
2729     }
2730     if (IsTclDict(interp, valuePtr->objPtr)) {
2731         /* Preserve type if this was a dict */
2732         int result;
2733         Tcl_Obj *keyPtr, *valueObjPtr = NULL;
2734
2735         keyPtr = Tcl_NewStringObj(elemName, -1);
2736         Tcl_IncrRefCount(keyPtr);
2737         result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valueObjPtr);
2738         Tcl_DecrRefCount(keyPtr);
2739         if (result != TCL_OK) {
2740             return FALSE;
2741         }
2742         if (valueObjPtr == NULL) {
2743             return FALSE;
2744         }
2745         return TRUE;
2746     }
2747
2748     if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
2749         Tcl_DecrRefCount(valuePtr->objPtr);
2750         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2751         Tcl_IncrRefCount(valuePtr->objPtr);
2752     }
2753     if (Blt_GetArrayFromObj((Tcl_Interp *)NULL, valuePtr->objPtr, &tablePtr)
2754         != TCL_OK) {
2755         return FALSE;
2756     }
2757     hPtr = Blt_FindHashEntry(tablePtr, elemName);
2758     return (hPtr != NULL);
2759 }
2760
2761 int
2762 Blt_TreeGetArrayValue(
2763     Tcl_Interp *interp,
2764     TreeClient *clientPtr,
2765     Node *nodePtr,
2766     CONST char *arrayName,
2767     CONST char *elemName,
2768     Tcl_Obj **valueObjPtrPtr)
2769 {
2770     Blt_TreeKey key;
2771     Blt_HashEntry *hPtr;
2772     Blt_HashTable *tablePtr;
2773     register Value *valuePtr;
2774     int cnt = 0;
2775
2776     key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
2777
2778     /* Reading any element of the array can cause a trace to fire. */
2779     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2780         if (CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr, key,
2781             TREE_TRACE_READ, &cnt) != TCL_OK) {
2782                 return TCL_ERROR;
2783         }
2784     }
2785     valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
2786     if (valuePtr == NULL) {
2787         return TCL_ERROR;
2788     }
2789     if (IsTclDict(interp, valuePtr->objPtr)) {
2790         /* Preserve type if this was a dict */
2791         int result;
2792         Tcl_Obj *keyPtr;
2793         keyPtr = Tcl_NewStringObj(elemName, -1);
2794         Tcl_IncrRefCount(keyPtr);
2795         result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, valueObjPtrPtr);
2796         Tcl_DecrRefCount(keyPtr);
2797         if (result != TCL_OK) {
2798             return result;
2799         }
2800         if (*valueObjPtrPtr == NULL) {
2801             if (interp != NULL) {
2802                 Tcl_AppendResult(interp, "can't find \"", arrayName, "(",
2803                     elemName, ")\"", (char *)NULL);
2804             }
2805             return TCL_ERROR;
2806         }
2807         return TCL_OK;
2808     }
2809     if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
2810         Tcl_DecrRefCount(valuePtr->objPtr);
2811         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2812         Tcl_IncrRefCount(valuePtr->objPtr);
2813     }
2814     if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2815         return TCL_ERROR;
2816     }
2817     hPtr = Blt_FindHashEntry(tablePtr, elemName);
2818     if (hPtr == NULL) {
2819         if (interp != NULL) {
2820             Tcl_AppendResult(interp, "can't find \"", arrayName, "(",
2821                              elemName, ")\"", (char *)NULL);
2822         }
2823         return TCL_ERROR;
2824     }
2825
2826     *valueObjPtrPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
2827     return TCL_OK;
2828 }
2829
2830 static int
2831 TreeSetArrayValue(
2832     Tcl_Interp *interp,
2833     TreeClient *clientPtr,
2834     Node *nodePtr,              /* Node to be updated. */
2835     CONST char *arrayName,
2836     CONST char *elemName,
2837     Tcl_Obj *valueObjPtr,       /* New value of element. */
2838     int create)           /* Create the node key if required. */
2839 {
2840     Blt_TreeKey key;
2841     Blt_HashEntry *hPtr;
2842     Blt_HashTable *tablePtr;
2843     register Value *valuePtr;
2844     unsigned int flags;
2845     int isNew, cnt = 0;
2846
2847     assert(valueObjPtr != NULL);
2848
2849     /*
2850      * Search for the array in the list of data fields.  If one
2851      * doesn't exist, create it.
2852      */
2853     key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
2854     valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
2855     if (valuePtr == NULL && create == 0) {
2856         return TCL_ERROR;
2857     }
2858     if (valuePtr == NULL) {
2859         if ((nodePtr->flags & TREE_NODE_FIXED_FIELDS)) {
2860             return TCL_ERROR;
2861         }
2862         valuePtr = TreeCreateValue(nodePtr, key, &isNew);
2863         isNew = 1;
2864     } else {
2865         isNew = 0;
2866     }
2867     if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
2868         if (interp != NULL) {
2869             Tcl_AppendResult(interp, "can't set private field \"",
2870                              key, "\"", (char *)NULL);
2871         }
2872         return TCL_ERROR;
2873     }
2874     flags = TREE_TRACE_WRITE;
2875     if (isNew) {
2876         valuePtr->objPtr = Blt_NewArrayObj(0, (Tcl_Obj **)NULL);
2877         Tcl_IncrRefCount(valuePtr->objPtr);
2878         flags |= TREE_TRACE_CREATE;
2879
2880      } else if (Tcl_IsShared(valuePtr->objPtr)) {
2881         Tcl_DecrRefCount(valuePtr->objPtr);
2882         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2883         Tcl_IncrRefCount(valuePtr->objPtr);
2884     }
2885
2886     if ((clientPtr->treeObject->flags & TREE_DICT_KEYS) &&
2887         IsTclDict(interp, valuePtr->objPtr)) {
2888         int dSiz;
2889
2890         if (Tcl_DictObjSize(interp, valuePtr->objPtr, &dSiz) != TCL_OK) {
2891             return TCL_ERROR;
2892         }
2893     }
2894     if (IsTclDict(interp, valuePtr->objPtr)) {
2895         /* Preserve type if this was a dict */
2896         int result;
2897         Tcl_Obj *keyPtr, *valObjPtr;
2898
2899         keyPtr = Tcl_NewStringObj(elemName, -1);
2900         Tcl_IncrRefCount(keyPtr);
2901         if (!create) {
2902             result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valObjPtr);
2903             if (result != TCL_OK || valObjPtr == NULL) {
2904                 Tcl_AppendResult(interp, "can't find field: ", elemName, 0);
2905                 Tcl_DecrRefCount(keyPtr);
2906                 return TCL_ERROR;
2907             }
2908         }
2909         result = Tcl_DictObjPut(interp, valuePtr->objPtr, keyPtr, valueObjPtr);
2910         Tcl_DecrRefCount(keyPtr);
2911         if (result != TCL_OK) {
2912             return result;
2913         }
2914         goto finishset;
2915     }
2916
2917
2918     if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2919         return TCL_ERROR;
2920     }
2921     Tcl_InvalidateStringRep(valuePtr->objPtr);
2922     if (create) {
2923         hPtr = Blt_CreateHashEntry(tablePtr, elemName, &isNew);
2924         assert(hPtr);
2925     } else {
2926         hPtr = Blt_FindHashEntry(tablePtr, elemName);
2927         if (hPtr == NULL) {
2928             if (interp != NULL) {
2929                 Tcl_AppendResult(interp, "can't find array field: ", elemName, 0);
2930             }
2931             return TCL_ERROR;
2932         }
2933         isNew = 0;
2934     }
2935
2936     SetModified(nodePtr);
2937     Tcl_IncrRefCount(valueObjPtr);
2938     if (!isNew) {
2939         Tcl_Obj *oldValueObjPtr;
2940
2941         /* An element by the same name already exists. Decrement the
2942          * reference count of the old value. */
2943
2944         oldValueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
2945         if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2946             UpdateOldValue(clientPtr, oldValueObjPtr);
2947             oldValueObjPtr = NULL;
2948         }
2949         if (oldValueObjPtr != NULL) {
2950             Tcl_DecrRefCount(oldValueObjPtr);
2951         }
2952     } else {
2953         if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2954             UpdateOldValue(clientPtr, NULL);
2955         }
2956     }
2957     Blt_SetHashValue(hPtr, valueObjPtr);
2958
2959 finishset:
2960     /*
2961      * We don't handle traces on a per array element basis.  Setting
2962      * any element can fire traces for the value.
2963      */
2964     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2965         return CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
2966                 valuePtr->key, flags, &cnt);
2967     }
2968     return TCL_OK;
2969 }
2970
2971 int
2972 Blt_TreeSetArrayValue(
2973     Tcl_Interp *interp,
2974     TreeClient *clientPtr,
2975     Node *nodePtr,              /* Node to be updated. */
2976     CONST char *arrayName,
2977     CONST char *elemName,
2978     Tcl_Obj *valueObjPtr)       /* New value of element. */
2979 {
2980     return TreeSetArrayValue(interp, clientPtr, nodePtr, arrayName, elemName, valueObjPtr, 1);
2981 }
2982
2983 int
2984 Blt_TreeUpdateArrayValue(
2985     Tcl_Interp *interp,
2986     TreeClient *clientPtr,
2987     Node *nodePtr,              /* Node to be updated. */
2988     CONST char *arrayName,
2989     CONST char *elemName,
2990     Tcl_Obj *valueObjPtr)       /* New value of element. */
2991 {
2992     return TreeSetArrayValue(interp, clientPtr, nodePtr, arrayName, elemName, valueObjPtr, 0);
2993 }
2994
2995 int
2996 Blt_TreeUnsetArrayValue(
2997     Tcl_Interp *interp,
2998     TreeClient *clientPtr,
2999     Node *nodePtr,              /* Node to be updated. */
3000     CONST char *arrayName,
3001     CONST char *elemName)
3002 {
3003     Blt_TreeKey key;            /* Name of field in node. */
3004     Blt_HashEntry *hPtr;
3005     Blt_HashTable *tablePtr;
3006     Tcl_Obj *valueObjPtr;
3007     Value *valuePtr;
3008     int cnt = 0;
3009
3010     key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
3011     valuePtr = TreeFindValue(nodePtr, key);
3012     if (valuePtr == NULL) {
3013         return TCL_OK;
3014     }
3015     if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
3016         if (interp != NULL) {
3017             Tcl_AppendResult(interp, "can't unset private field \"",
3018                              key, "\"", (char *)NULL);
3019         }
3020         return TCL_ERROR;
3021     }
3022
3023     if (Tcl_IsShared(valuePtr->objPtr)) {
3024         Tcl_DecrRefCount(valuePtr->objPtr);
3025         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
3026         Tcl_IncrRefCount(valuePtr->objPtr);
3027     }
3028
3029     if (IsTclDict(interp, valuePtr->objPtr)) {
3030         /* Preserve type if this was a dict */
3031         int result;
3032         Tcl_Obj *keyPtr;
3033         keyPtr = Tcl_NewStringObj(elemName, -1);
3034         Tcl_IncrRefCount(keyPtr);
3035         result = Tcl_DictObjRemove(interp, valuePtr->objPtr, keyPtr);
3036         Tcl_DecrRefCount(keyPtr);
3037         if (result != TCL_OK) {
3038             return result;
3039         }
3040         goto finishrm;
3041     }
3042
3043     if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
3044         return TCL_ERROR;
3045     }
3046     hPtr = Blt_FindHashEntry(tablePtr, elemName);
3047     if (hPtr == NULL) {
3048         goto finishrm; /* Element doesn't exist, Ok. */
3049     }
3050     SetModified(nodePtr);
3051     valueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
3052     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
3053         UpdateOldValue(clientPtr, valueObjPtr);
3054     } else {
3055         Tcl_DecrRefCount(valueObjPtr);
3056     }
3057     Blt_DeleteHashEntry(tablePtr, hPtr);
3058     Tcl_InvalidateStringRep(valuePtr->objPtr);
3059
3060 finishrm:
3061     /*
3062      * Un-setting any element in the array can cause the trace on the value
3063      * to fire.
3064      */
3065     if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
3066         return CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
3067                 valuePtr->key, TREE_TRACE_WRITE, &cnt);
3068     }
3069     return TCL_OK;
3070 }
3071
3072 int
3073 Blt_TreeArrayNames(
3074     Tcl_Interp *interp,
3075     TreeClient *clientPtr,
3076     Node *nodePtr,
3077     CONST char *arrayName,
3078     Tcl_Obj *listObjPtr,
3079     CONST char *pattern)
3080 {
3081     Blt_HashEntry *hPtr;
3082     Blt_HashSearch cursor;
3083     Blt_HashTable *tablePtr;
3084     Tcl_Obj *objPtr;
3085     Value *valuePtr;
3086     char *key;
3087
3088     key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
3089     valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
3090     if (valuePtr == NULL) {
3091         return TCL_ERROR;
3092     }
3093     if (IsTclDict(interp, valuePtr->objPtr)) {
3094         /* Preserve type if this was a dict */
3095
3096         Tcl_DictSearch search;
3097         Tcl_Obj *keyPtr;
3098         int done;
3099
3100         Tcl_DictObjFirst(NULL, valuePtr->objPtr, &search, &keyPtr, NULL, &done);
3101         for (; !done ; Tcl_DictObjNext(&search, &keyPtr, NULL, &done)) {
3102             if (!pattern || Tcl_StringMatch(Tcl_GetString(keyPtr), pattern)) {
3103                 Tcl_ListObjAppendElement(NULL, listObjPtr, keyPtr);
3104             }
3105         }
3106         Tcl_DictObjDone(&search);
3107         return TCL_OK;
3108     }
3109
3110     if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
3111         Tcl_DecrRefCount(valuePtr->objPtr);
3112         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
3113         Tcl_IncrRefCount(valuePtr->objPtr);
3114     }
3115     if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
3116         return TCL_ERROR;
3117     }
3118     /*tablePtr = (Blt_HashTable *)valuePtr->objPtr; */
3119     for (hPtr = Blt_FirstHashEntry(tablePtr, &cursor); hPtr != NULL;
3120          hPtr = Blt_NextHashEntry(&cursor)) {
3121          char *str;
3122
3123          str = Blt_GetHashKey(tablePtr, hPtr);
3124          if (pattern == NULL || Tcl_StringMatch(str, pattern)) {
3125              objPtr = Tcl_NewStringObj(str, -1);
3126              Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
3127          }
3128     }
3129     return TCL_OK;
3130 }
3131
3132 int
3133 Blt_TreeArrayValues(
3134     Tcl_Interp *interp,
3135     TreeClient *clientPtr,
3136     Node *nodePtr,
3137     CONST char *arrayName,
3138     Tcl_Obj *listObjPtr,
3139     int names)
3140 {
3141     Blt_HashEntry *hPtr;
3142     Blt_HashSearch cursor;
3143     Blt_HashTable *tablePtr;
3144     Tcl_Obj *objPtr;
3145     Value *valuePtr;
3146     char *key;
3147
3148     key = Blt_TreeKeyGet(interp, clientPtr->treeObject,arrayName);
3149     if ( bltTreeGetValueByKey(interp, clientPtr, nodePtr, key, &valuePtr) != TCL_OK) {
3150         return TCL_ERROR;
3151     }
3152     if (IsTclDict(interp, valuePtr->objPtr)) {
3153         /* Preserve type if this was a dict */
3154
3155         Tcl_DictSearch search;
3156         Tcl_Obj *keyPtr;
3157         int done;
3158         int result;
3159
3160         Tcl_DictObjFirst(NULL, valuePtr->objPtr, &search, &keyPtr, NULL, &done);
3161         for (; !done ; Tcl_DictObjNext(&search, &keyPtr, NULL, &done)) {
3162             Tcl_Obj *valueObjPtr;
3163             if (names) {
3164                 Tcl_ListObjAppendElement(NULL, listObjPtr, keyPtr);
3165             }
3166
3167             valueObjPtr = NULL;
3168             result = Tcl_DictObjGet(interp, valuePtr->objPtr, keyPtr, &valueObjPtr);
3169             if (result != TCL_OK) {
3170                 continue;
3171             }
3172             if (valueObjPtr == NULL) {
3173                 valueObjPtr = Tcl_NewStringObj("",-1);
3174             }
3175             Tcl_ListObjAppendElement(NULL, listObjPtr, valueObjPtr);
3176         }
3177         Tcl_DictObjDone(&search);
3178         return TCL_OK;
3179     }
3180     if (Blt_IsArrayObj(valuePtr->objPtr) == 0 && Tcl_IsShared(valuePtr->objPtr)) {
3181         Tcl_DecrRefCount(valuePtr->objPtr);
3182         valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
3183         Tcl_IncrRefCount(valuePtr->objPtr);
3184     }
3185     if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
3186         return TCL_ERROR;
3187     }
3188     /*tablePtr = (Blt_HashTable *)valuePtr->objPtr; */
3189     for (hPtr = Blt_FirstHashEntry(tablePtr, &cursor); hPtr != NULL;
3190          hPtr = Blt_NextHashEntry(&cursor)) {
3191         if (names) {
3192              Tcl_ListObjAppendElement(interp, listObjPtr,
3193                 Tcl_NewStringObj( Blt_GetHashKey(tablePtr, hPtr), -1));
3194         }
3195         objPtr = Blt_GetHashValue(hPtr);
3196         Tcl_ListObjAppendElement(interp, listObjPtr, objPtr?objPtr:Tcl_NewStringObj("",-1));
3197     }
3198     return TCL_OK;
3199 }
3200
3201
3202 /*
3203  *----------------------------------------------------------------------
3204  *
3205  * Blt_TreeShareTagTable --
3206  *
3207  *----------------------------------------------------------------------
3208  */
3209 int
3210 Blt_TreeShareTagTable(
3211     TreeClient *sourcePtr,
3212     TreeClient *targetPtr)
3213 {
3214     sourcePtr->tagTablePtr->refCount++;
3215     if (targetPtr->tagTablePtr != NULL) {
3216         ReleaseTagTable(targetPtr->tagTablePtr);
3217     }
3218     targetPtr->tagTablePtr = sourcePtr->tagTablePtr;
3219     return TCL_OK;
3220 }
3221
3222 int
3223 Blt_TreeTagTableIsShared(TreeClient *clientPtr)
3224 {
3225     return (clientPtr->tagTablePtr->refCount > 1);
3226 }
3227
3228 void
3229 Blt_TreeClearTags(TreeClient *clientPtr, Blt_TreeNode node)
3230 {
3231     Blt_HashEntry *hPtr, *h2Ptr;
3232     Blt_HashSearch cursor;
3233
3234     for (hPtr = Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, &cursor);
3235         hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
3236         Blt_TreeTagEntry *tPtr;
3237
3238         tPtr = Blt_GetHashValue(hPtr);
3239         h2Ptr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
3240         if (h2Ptr != NULL) {
3241              SetModified(node);
3242              Blt_DeleteHashEntry(&tPtr->nodeTable, h2Ptr);
3243         }
3244     }
3245 }
3246
3247 int
3248 Blt_TreeHasTag(
3249     TreeClient *clientPtr,
3250     Blt_TreeNode node,
3251     CONST char *tagName)
3252 {
3253     Blt_HashEntry *hPtr;
3254     Blt_TreeTagEntry *tPtr;
3255
3256     if (strcmp(tagName, "all") == 0) {
3257         return TRUE;
3258     }
3259     if (strcmp(tagName, "nonroot") == 0) {
3260         return TRUE;
3261     }
3262     if (strcmp(tagName, "rootchildren") == 0) {
3263         return TRUE;
3264     }
3265     if ((strcmp(tagName, "root") == 0) &&
3266         (node == Blt_TreeRootNode(clientPtr))) {
3267         return TRUE;
3268     }
3269     hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
3270     if (hPtr == NULL) {
3271         return FALSE;
3272     }
3273     tPtr = Blt_GetHashValue(hPtr);
3274     hPtr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
3275     if (hPtr == NULL) {
3276         return FALSE;
3277     }
3278     return TRUE;
3279 }
3280
3281 int
3282 Blt_TreeAddTag(
3283     TreeClient *clientPtr,
3284     Blt_TreeNode node,
3285     CONST char *tagName)
3286 {
3287     int isNew, isNewN, cnt = 0, flags;
3288     Blt_HashEntry *hPtr;
3289     Blt_HashTable *tablePtr;
3290     Blt_TreeTagEntry *tPtr;
3291     Tcl_Interp *interp = clientPtr->treeObject->interp;
3292
3293     if ((strcmp(tagName, "all") == 0) || (strcmp(tagName, "root") == 0)
3294         || (strcmp(tagName, "nonroot") == 0) || (strcmp(tagName, "rootchildren") == 0)) {
3295         Tcl_AppendResult(interp, "reserved tag", 0);
3296         return TCL_ERROR;
3297     }
3298     tablePtr = &clientPtr->tagTablePtr->tagTable;
3299     hPtr = Blt_CreateHashEntry(tablePtr, tagName, &isNewN);
3300     assert(hPtr);
3301     if (isNewN) {
3302
3303         tPtr = Blt_Calloc(sizeof(Blt_TreeTagEntry), 1);
3304         Blt_InitHashTable(&tPtr->nodeTable, BLT_ONE_WORD_KEYS);
3305         Blt_SetHashValue(hPtr, tPtr);
3306         tPtr->hashPtr = hPtr;
3307         tPtr->tagName = Blt_GetHashKey(tablePtr, hPtr);
3308         Blt_TreeTagRefIncr(tPtr);
3309      } else {
3310         tPtr = Blt_GetHashValue(hPtr);
3311     }
3312     if (node == NULL) {
3313         return TCL_OK;
3314     }
3315     if (!(node->flags & TREE_TRACE_ACTIVE)) {
3316         int result;
3317         flags = TREE_TRACE_TAGADD;
3318         if (tPtr->nodeTable.numEntries > 0) {
3319             flags |= TREE_TRACE_TAGMULTIPLE;
3320         }
3321         result = CallTraces(interp, clientPtr, node->treeObject, node, tagName,
3322             flags, &cnt);
3323         if (result == TCL_BREAK) {
3324             return TCL_OK;
3325         }
3326         if (result != TCL_OK) {
3327             return result;
3328         }
3329     }
3330     hPtr = Blt_CreateHashEntry(&tPtr->nodeTable, (char *)node, &isNew);
3331     assert(hPtr);
3332     if (isNew) {
3333         SetModified(node);
3334         Blt_SetHashValue(hPtr, node);
3335     }
3336     return TCL_OK;
3337 }
3338
3339 /* Trigger tag delete traces. */
3340 int
3341 Blt_TreeTagDelTrace(
3342     TreeClient *clientPtr,
3343     Blt_TreeNode node,
3344     CONST char *tagName)
3345 {
3346     Tcl_Interp *interp = clientPtr->treeObject->interp;
3347     int cnt;
3348
3349     if (!(node->flags & TREE_TRACE_ACTIVE)) {
3350         return CallTraces(interp, clientPtr, node->treeObject, node, tagName,
3351             (TREE_TRACE_TAGDELETE), &cnt);
3352     }
3353     return TCL_OK;
3354 }
3355
3356 int
3357 Blt_TreeForgetTag(TreeClient *clientPtr, CONST char *tagName)
3358 {
3359     Blt_HashEntry *hPtr;
3360     if ((strcmp(tagName, "all") == 0) || (strcmp(tagName, "root") == 0)
3361        || (strcmp(tagName, "nonroot") == 0)
3362        || (strcmp(tagName, "rootchildren") == 0)) {
3363        return TCL_OK;
3364     }
3365
3366     hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
3367     if (hPtr != NULL) {
3368         Blt_TreeTagEntry *tPtr;
3369         Blt_TreeNode node;
3370         Blt_HashSearch cursor;
3371
3372         Blt_DeleteHashEntry(&clientPtr->tagTablePtr->tagTable, hPtr);
3373         tPtr = Blt_GetHashValue(hPtr);
3374         for (hPtr = Blt_FirstHashEntry(&tPtr->nodeTable, &cursor);
3375             hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
3376
3377             node = Blt_GetHashKey(&tPtr->nodeTable, hPtr);
3378             if (Blt_TreeTagDelTrace(clientPtr, node, tagName) != TCL_OK) {
3379                 return TCL_ERROR;
3380             }
3381             SetModified(node);
3382         }
3383         Blt_DeleteHashTable(&tPtr->nodeTable);
3384         Blt_TreeTagRefDecr(tPtr);
3385     }
3386     return TCL_OK;
3387 }
3388
3389 /*
3390  *----------------------------------------------------------------------
3391  *
3392  * Blt_TreeTagHashTable --
3393  *
3394  *----------------------------------------------------------------------
3395  */
3396 Blt_HashTable *
3397 Blt_TreeTagHashTable(TreeClient *clientPtr, CONST char *tagName)
3398 {
3399     Blt_HashEntry *hPtr;
3400
3401     hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
3402     if (hPtr != NULL) {
3403         Blt_TreeTagEntry *tPtr;
3404
3405         tPtr = Blt_GetHashValue(hPtr);
3406         return &tPtr->nodeTable;
3407     }
3408     return NULL;
3409 }
3410
3411 Blt_TreeTagEntry *
3412 Blt_TreeTagHashEntry(TreeClient *clientPtr, CONST char *tagName)
3413 {
3414     Blt_HashEntry *hPtr;
3415
3416     hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
3417     if (hPtr != NULL) {
3418         Blt_TreeTagEntry *tPtr;
3419
3420         tPtr = Blt_GetHashValue(hPtr);
3421         return tPtr;
3422     }
3423     return NULL;
3424 }
3425
3426 Blt_HashEntry *
3427 Blt_TreeFirstTag(TreeClient *clientPtr, Blt_HashSearch *cursorPtr)
3428 {
3429     return Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, cursorPtr);
3430 }
3431
3432 #if (SIZEOF_VOID_P == 8)
3433 /*
3434  *----------------------------------------------------------------------
3435  *
3436  * HashOneWord --
3437  *
3438  *      Compute a one-word hash value of a 64-bit word, which then can
3439  *      be used to generate a hash index.
3440  *
3441  *      From Knuth, it's a multiplicative hash.  Multiplies an unsigned
3442  *      64-bit value with the golden ratio (sqrt(5) - 1) / 2.  The
3443  *      downshift value is 64 - n, when n is the log2 of the size of
3444  *      the hash table.
3445  *
3446  * Results:
3447  *      The return value is a one-word summary of the information in
3448  *      64 bit word.
3449  *
3450  * Side effects:
3451  *      None.
3452  *
3453  *----------------------------------------------------------------------
3454  */
3455 static Blt_Hash
3456 HashOneWord(
3457     uint64_t mask,
3458     unsigned int downshift,
3459     CONST void *key)
3460 {
3461     uint64_t a0, a1;
3462     uint64_t y0, y1;
3463     uint64_t y2, y3;
3464     uint64_t p1, p2;
3465     uint64_t result;
3466
3467     /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
3468     a0 = (uint64_t)key & 0x00000000FFFFFFFF;
3469     a1 = (uint64_t)key >> 32;
3470
3471     y0 = a0 * 0x000000007f4a7c13;
3472     y1 = a0 * 0x000000009e3779b9;
3473     y2 = a1 * 0x000000007f4a7c13;
3474     y3 = a1 * 0x000000009e3779b9;
3475     y1 += y0 >> 32;             /* Can't carry */
3476     y1 += y2;                   /* Might carry */
3477     if (y1 < y2) {
3478         y3 += (1LL << 32);      /* Propagate */
3479     }
3480
3481     /* 128-bit product: p1 = loword, p2 = hiword */
3482     p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
3483     p2 = y3 + (y1 >> 32);
3484
3485     /* Left shift the value downward by the size of the table */
3486     if (downshift > 0) {
3487         if (downshift < 64) {
3488             result = ((p2 << (64 - downshift)) | (p1 >> (downshift & 63)));
3489         } else {
3490             result = p2 >> (downshift & 63);
3491         }
3492     } else {
3493         result = p1;
3494     }
3495     /* Finally mask off the high bits */
3496     return (Blt_Hash)(result & mask);
3497 }
3498
3499 #endif /* SIZEOF_VOID_P == 8 */
3500
3501 /*
3502  *----------------------------------------------------------------------
3503  *
3504  * RebuildTable --
3505  *
3506  *      This procedure is invoked when the ratio of entries to hash
3507  *      buckets becomes too large.  It creates a new table with a
3508  *      larger bucket array and moves all of the entries into the
3509  *      new table.
3510  *
3511  * Results:
3512  *      None.
3513  *
3514  * Side effects:
3515  *      Memory gets reallocated and entries get re-hashed to new
3516  *      buckets.
3517  *
3518  *----------------------------------------------------------------------
3519  */
3520 static void
3521 RebuildTable(Node *nodePtr)             /* Table to enlarge. */
3522 {
3523     Value **newBucketPtr, **oldBuckets;
3524     register Value **bucketPtr, **endPtr;
3525     register Value *valuePtr, *nextPtr;
3526     unsigned int downshift;
3527     unsigned long mask;
3528     Value **buckets;
3529     size_t nBuckets;
3530
3531     oldBuckets = (Value **)nodePtr->values;
3532     nBuckets = (1 << nodePtr->logSize);
3533     endPtr = oldBuckets + nBuckets;
3534
3535     /*
3536      * Allocate and initialize the new bucket array, and set up
3537      * hashing constants for new array size.
3538      */
3539     nodePtr->logSize += 2;
3540     nBuckets = (1 << nodePtr->logSize);
3541     buckets = Blt_Calloc(nBuckets, sizeof(Value *));
3542
3543     /*
3544      * Move all of the existing entries into the new bucket array,
3545      * based on their hash values.
3546      */
3547     mask = nBuckets - 1;
3548     downshift = DOWNSHIFT_START - nodePtr->logSize;
3549     for (bucketPtr = oldBuckets; bucketPtr < endPtr; bucketPtr++) {
3550         for (valuePtr = *bucketPtr; valuePtr != NULL; valuePtr = nextPtr) {
3551             nextPtr = valuePtr->next;
3552             newBucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
3553             valuePtr->next = *newBucketPtr;
3554             *newBucketPtr = valuePtr;
3555         }
3556     }
3557     nodePtr->values = (Value *)buckets;
3558     Blt_Free(oldBuckets);
3559 }
3560
3561 static void
3562 ConvertValues(Node *nodePtr)
3563 {
3564     unsigned int nBuckets;
3565     Value **buckets;
3566     unsigned int mask;
3567     int downshift;
3568     Value *valuePtr, *nextPtr, **bucketPtr;
3569
3570     /*
3571      * Convert list of values into a hash table.
3572      */
3573     nodePtr->logSize = START_LOGSIZE;
3574     nBuckets = 1 << nodePtr->logSize;
3575     buckets = Blt_Calloc(nBuckets, sizeof(Value *));
3576     mask = nBuckets - 1;
3577     downshift = DOWNSHIFT_START - nodePtr->logSize;
3578     for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
3579         nextPtr = valuePtr->next;
3580         bucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
3581         valuePtr->next = *bucketPtr;
3582         *bucketPtr = valuePtr;
3583     }
3584     nodePtr->values = (Value *)buckets;
3585 }
3586
3587 /*
3588  *----------------------------------------------------------------------
3589  *
3590  * TreeDeleteValue --
3591  *
3592  *      Remove a single entry from a hash table.
3593  *
3594  * Results:
3595  *      None.
3596  *
3597  * Side effects:
3598  *      The entry given by entryPtr is deleted from its table and
3599  *      should never again be used by the caller.  It is up to the
3600  *      caller to free the clientData field of the entry, if that
3601  *      is relevant.
3602  *
3603  *----------------------------------------------------------------------
3604  */
3605 static int
3606 TreeDeleteValue(Node *nodePtr, Blt_TreeValue value)
3607 {
3608     Value *valuePtr = value;
3609     register Value *prevPtr;
3610
3611     if (nodePtr->logSize > 0) {
3612         Value **bucketPtr;
3613         unsigned int downshift;
3614         unsigned long mask;
3615
3616         mask = (1 << nodePtr->logSize) - 1;
3617         downshift = DOWNSHIFT_START - nodePtr->logSize;
3618
3619         bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX(valuePtr->key);
3620         if (*bucketPtr == valuePtr) {
3621             *bucketPtr = valuePtr->next;
3622         } else {
3623             for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->next) {
3624                 if (prevPtr == NULL) {
3625                     return TCL_ERROR; /* Can't find value in hash bucket. */
3626                 }
3627                 if (prevPtr->next == valuePtr) {
3628                     prevPtr->next = valuePtr->next;
3629                     break;
3630                 }
3631             }
3632         }
3633     } else {
3634         prevPtr = NULL;
3635         for (valuePtr = nodePtr->values; valuePtr != NULL;
3636              valuePtr = valuePtr->next) {
3637             if (valuePtr == value) {
3638                 break;
3639             }
3640             prevPtr = valuePtr;
3641         }
3642         if (valuePtr == NULL) {
3643             return TCL_ERROR;   /* Can't find value in list. */
3644         }
3645         if (prevPtr == NULL) {
3646             nodePtr->values = valuePtr->next;
3647         } else {
3648             prevPtr->next = valuePtr->next;
3649         }
3650     }
3651     nodePtr->nValues--;
3652     FreeValue(nodePtr, valuePtr);
3653     return TCL_OK;
3654 }
3655
3656 /*
3657  *----------------------------------------------------------------------
3658  *
3659  * TreeDestroyValues --
3660  *
3661  *      Free up everything associated with a hash table except for
3662  *      the record for the table itself.
3663  *
3664  * Results:
3665  *      None.
3666  *
3667  * Side effects:
3668  *      The hash table is no longer useable.
3669  *
3670  *----------------------------------------------------------------------
3671  */
3672 static void
3673 TreeDestroyValues(Node *nodePtr)
3674 {
3675     register Value *valuePtr;
3676     Value *nextPtr;
3677
3678     /*
3679      * Free up all the entries in the table.
3680      */
3681     if (nodePtr->values == NULL) {
3682         return;
3683     }
3684     if (nodePtr->logSize > 0) {
3685         Value **buckets;
3686         int nBuckets;
3687         int i;
3688
3689         buckets = (Value **)nodePtr->values;
3690         nBuckets = (1 << nodePtr->logSize);
3691         for (i = 0; i < nBuckets; i++) {
3692             for (valuePtr = buckets[i]; valuePtr != NULL; valuePtr = nextPtr) {
3693                 nextPtr = valuePtr->next;
3694                 FreeValue(nodePtr, valuePtr);
3695             }
3696         }
3697         Blt_Free(buckets);
3698     } else {
3699         for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
3700             nextPtr = valuePtr->next;
3701             FreeValue(nodePtr, valuePtr);
3702         }
3703     }
3704     nodePtr->values = NULL;
3705     nodePtr->nValues = 0;
3706     nodePtr->logSize = 0;
3707 }
3708
3709 /*
3710  *----------------------------------------------------------------------
3711  *
3712  * TreeFirstValue --
3713  *
3714  *      Locate the first entry in a hash table and set up a record
3715  *      that can be used to step through all the remaining entries
3716  *      of the table.
3717  *
3718  * Results:
3719  *      The return value is a pointer to the first value in tablePtr,
3720  *      or NULL if tablePtr has no entries in it.  The memory at
3721  *      *searchPtr is initialized so that subsequent calls to
3722  *      Blt_TreeNextValue will return all of the values in the table,
3723  *      one at a time.
3724  *
3725  * Side effects:
3726  *      None.
3727  *
3728  *----------------------------------------------------------------------
3729  */
3730 static Value *
3731 TreeFirstValue(
3732     Node *nodePtr,
3733     Blt_TreeKeySearch *searchPtr) /* Place to store information about
3734                                    * progress through the table. */
3735 {
3736     searchPtr->node = nodePtr;
3737     searchPtr->nextIndex = 0;
3738     searchPtr->cnt = 1;
3739     if (nodePtr->logSize > 0) {
3740         searchPtr->nextValue = NULL;
3741     } else {
3742         searchPtr->nextValue = nodePtr->values;
3743     }
3744     return TreeNextValue(searchPtr);
3745 }
3746
3747 /*
3748  *----------------------------------------------------------------------
3749  *
3750  * TreeNextValue --
3751  *
3752  *      Once a hash table enumeration has been initiated by calling
3753  *      Blt_TreeFirstValue, this procedure may be called to return
3754  *      successive elements of the table.
3755  *
3756  * Results:
3757  *      The return value is the next entry in the hash table being
3758  *      enumerated, or NULL if the end of the table is reached.
3759  *
3760  * Side effects:
3761  *      None.
3762  *
3763  *----------------------------------------------------------------------
3764  */
3765 static Value *
3766 TreeNextValue(
3767     Blt_TreeKeySearch *searchPtr) /* Place to store information about
3768                                    * progress through the table.  Must
3769                                    * have been initialized by calling
3770                                    * Blt_TreeFirstValue. */
3771 {
3772     Value *valuePtr;
3773
3774     if (searchPtr->node->logSize > 0) {
3775         size_t nBuckets;
3776         Value **buckets;
3777
3778         nBuckets = (1 << searchPtr->node->logSize);
3779         buckets = (Value **)searchPtr->node->values;
3780         while (searchPtr->nextValue == NULL) {
3781             if (searchPtr->nextIndex >= nBuckets) {
3782                 return NULL;
3783             }
3784             searchPtr->nextValue = buckets[searchPtr->nextIndex];
3785             searchPtr->nextIndex++;
3786         }
3787     }
3788     searchPtr->cnt++;
3789     /* Sanity check. */
3790     if (searchPtr->cnt>100000000) return NULL;
3791     valuePtr = searchPtr->nextValue;
3792     if (valuePtr != NULL) {
3793         searchPtr->nextValue = valuePtr->next;
3794     }
3795     return valuePtr;
3796 }
3797
3798 /*
3799  *----------------------------------------------------------------------
3800  *
3801  * TreeFindValue --
3802  *
3803  *      Given a hash table with one-word keys, and a one-word key, find
3804  *      the entry with a matching key.
3805  *
3806  * Results:
3807  *      The return value is a token for the matching entry in the
3808  *      hash table, or NULL if there was no matching entry.
3809  *
3810  * Side effects:
3811  *      None.
3812  *
3813  *----------------------------------------------------------------------
3814  */
3815 static Value *
3816 TreeFindValue(
3817     Node *nodePtr,
3818     Blt_TreeKey key)            /* Key to use to find matching entry. */
3819 {
3820     register Value *valuePtr;
3821     Value *bucket;
3822
3823     if (nodePtr->logSize > 0) {
3824         unsigned int downshift;
3825         unsigned long mask;
3826
3827         mask = (1 << nodePtr->logSize) - 1;
3828         downshift = DOWNSHIFT_START - nodePtr->logSize;
3829         bucket = ((Value **)(nodePtr->values))[RANDOM_INDEX((void *)key)];
3830     } else {
3831         bucket = nodePtr->values; /* Single chain list. */
3832     }
3833     /*
3834      * Search all of the entries in the appropriate bucket.
3835      */
3836     for (valuePtr = bucket; valuePtr != NULL; valuePtr = valuePtr->next) {
3837         if (valuePtr->key == key) {
3838             return valuePtr;
3839         }
3840     }
3841     return NULL;
3842 }
3843
3844 /*
3845  *----------------------------------------------------------------------
3846  *
3847  * Blt_TreeCreateValue --
3848  *
3849  *      Find the value with a matching key.  If there is no matching
3850  *      value, then create a new one.
3851  *
3852  * Results:
3853  *      The return value is a pointer to the matching value.  If this
3854  *      is a newly-created value, then *newPtr will be set to a non-zero
3855  *      value;  otherwise *newPtr will be set to 0.
3856  *
3857  * Side effects:
3858  *      A new value may be added to the hash table.
3859  *
3860  *----------------------------------------------------------------------
3861  */
3862 static Value *
3863 TreeCreateValue(
3864     Node *nodePtr,
3865     Blt_TreeKey key,            /* Key to use to find or create matching
3866                                  * entry. */
3867     int *newPtr)                /* Store info here telling whether a new
3868                                  * entry was created. */
3869 {
3870     register Value *valuePtr;
3871     TreeObject *treeObjPtr = nodePtr->treeObject;
3872     int maxVals;
3873
3874     if (treeObjPtr->maxKeyList>0) {
3875         maxVals = treeObjPtr->maxKeyList;
3876     } else {
3877         maxVals = MAX_LIST_VALUES;
3878     }
3879     /*
3880      * Check if there as so many values that storage should be
3881      * converted from a hash table instead of a list.
3882      */
3883     if ((nodePtr->logSize == 0) && (nodePtr->nValues >= maxVals)) {
3884         ConvertValues(nodePtr);
3885     }
3886     if (nodePtr->logSize > 0) {
3887         Value **bucketPtr;
3888         size_t nBuckets;
3889         unsigned int downshift;
3890         unsigned long mask;
3891
3892         nBuckets = (1 << nodePtr->logSize);
3893         mask = nBuckets - 1;
3894         downshift = DOWNSHIFT_START - nodePtr->logSize;
3895         bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX((void *)key);
3896
3897         *newPtr = FALSE;
3898         for (valuePtr = *bucketPtr; valuePtr != NULL;
3899              valuePtr = valuePtr->next) {
3900             if (valuePtr->key == key) {
3901                 return valuePtr;
3902             }
3903         }
3904
3905         /* Value not found. Add a new value to the bucket. */
3906         *newPtr = TRUE;
3907         valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
3908                 sizeof(Value));
3909         valuePtr->key = key;
3910         valuePtr->owner = NULL;
3911         valuePtr->next = *bucketPtr;
3912         valuePtr->objPtr = NULL;
3913         *bucketPtr = valuePtr;
3914         nodePtr->nValues++;
3915
3916         /*
3917          * If the table has exceeded a decent size, rebuild it with many
3918          * more buckets.
3919          */
3920         if ((unsigned int)nodePtr->nValues >= (nBuckets * 3)) {
3921             RebuildTable(nodePtr);
3922         }
3923     } else {
3924         Value *prevPtr;
3925
3926         prevPtr = NULL;
3927         *newPtr = FALSE;
3928         for (valuePtr = nodePtr->values; valuePtr != NULL;
3929              valuePtr = valuePtr->next) {
3930             if (valuePtr->key == key) {
3931                 return valuePtr;
3932             }
3933             prevPtr = valuePtr;
3934         }
3935         /* Value not found. Add a new value to the list. */
3936         *newPtr = TRUE;
3937         valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
3938                 sizeof(Value));
3939         valuePtr->key = key;
3940         valuePtr->owner = NULL;
3941         valuePtr->next = NULL;
3942         valuePtr->objPtr = NULL;
3943         if (prevPtr == NULL) {
3944             nodePtr->values = valuePtr;
3945         } else {
3946             prevPtr->next = valuePtr;
3947         }
3948         nodePtr->nValues++;
3949     }
3950     return valuePtr;
3951 }
3952
3953
3954 Blt_TreeNode Blt_TreeEndNode (Blt_TreeNode node,
3955     unsigned int nodeFlags) {
3956     /* TODO: finish. */
3957     return NULL;
3958 }
3959
3960 #undef Blt_TreeFirstChild
3961 #undef Blt_TreeLastChild
3962 #undef Blt_TreeNextSibling
3963 #undef Blt_TreePrevSibling
3964 #undef Blt_TreeChangeRoot
3965
3966 Blt_TreeNode Blt_TreeFirstChild (Blt_TreeNode parent) {
3967     return parent->first;
3968 }
3969
3970 Blt_TreeNode Blt_TreeNextSibling (Blt_TreeNode node) {
3971     return (node == NULL ? NULL : node->next);
3972 }
3973
3974 Blt_TreeNode Blt_TreeLastChild (Blt_TreeNode parent) {
3975     return parent->last;
3976 }
3977
3978 Blt_TreeNode Blt_TreePrevSibling (Blt_TreeNode node) {
3979     return (node == NULL ? NULL : node->prev);
3980 }
3981
3982 Blt_TreeNode Blt_TreeChangeRoot (Blt_Tree tree, Blt_TreeNode node) {
3983     tree->root = node;
3984     return node;
3985 }
3986
3987 #endif /* NO_TREE */