source: trunk/kitgen/8.x/blt/generic/bltTree.c@ 180

Last change on this file since 180 was 175, checked in by demin, 12 years ago

initial commit
File size: 78.8 KB
RevLine 
[175]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 */
27
28#include "bltInt.h"
29
30/* TODO:
31 * traces and notifiers should be in one list in tree object.
32 * notifier is always fired.
33 * incorporate first/next tag routines ?
34 */
35
36
37#ifndef NO_TREE
38
39#include "bltTree.h"
40
41static Tcl_InterpDeleteProc TreeInterpDeleteProc;
42static Blt_TreeApplyProc SizeApplyProc;
43static Tcl_IdleProc NotifyIdleProc;
44
45#define TREE_THREAD_KEY "BLT Tree Data"
46#define TREE_MAGIC ((unsigned int) 0x46170277)
47#define TREE_DESTROYED (1<<0)
48
49typedef struct Blt_TreeNodeStruct Node;
50typedef struct Blt_TreeClientStruct TreeClient;
51typedef struct Blt_TreeObjectStruct TreeObject;
52typedef struct Blt_TreeValueStruct Value;
53
54/*
55 * Blt_TreeValue --
56 *
57 * Tree nodes contain heterogeneous data fields, represented as a
58 * chain of these structures. Each field contains the key of the
59 * field (Blt_TreeKey) and the value (Tcl_Obj) containing the
60 * actual data representations.
61 *
62 */
63struct Blt_TreeValueStruct {
64 Blt_TreeKey key; /* String identifying the data field */
65 Tcl_Obj *objPtr; /* Data representation. */
66 Blt_Tree owner; /* Non-NULL if privately owned. */
67 Blt_TreeValue next; /* Next value in the chain. */
68};
69
70#include <stdio.h>
71#include <string.h>
72/* The following header is required for LP64 compilation */
73#include <stdlib.h>
74
75#include "bltHash.h"
76
77static void TreeDestroyValues _ANSI_ARGS_((Blt_TreeNode node));
78
79static Value *TreeFindValue _ANSI_ARGS_((Blt_TreeNode node,
80 Blt_TreeKey key));
81static Value *TreeCreateValue _ANSI_ARGS_((Blt_TreeNode node,
82 Blt_TreeKey key, int *newPtr));
83
84static int TreeDeleteValue _ANSI_ARGS_((Blt_TreeNode node,
85 Blt_TreeValue value));
86
87static Value *TreeFirstValue _ANSI_ARGS_((Blt_TreeNode,
88 Blt_TreeKeySearch *searchPtr));
89
90static Value *TreeNextValue _ANSI_ARGS_((Blt_TreeKeySearch *srchPtr));
91
92/*
93 * When there are this many entries per bucket, on average, rebuild
94 * the hash table to make it larger.
95 */
96
97#define REBUILD_MULTIPLIER 3
98
99#if (SIZEOF_VOID_P == 8)
100#define RANDOM_INDEX(i) HashOneWord(mask, downshift, i)
101#define BITSPERWORD 64
102#else
103
104#define START_LOGSIZE 5 /* Initial hash table size is 32. */
105#define MAX_LIST_VALUES 20 /* Convert to hash table when node
106 * value list gets bigger than this
107 * many values. */
108
109/*
110 * The following macro takes a preliminary integer hash value and
111 * produces an index into a hash tables bucket list. The idea is
112 * to make it so that preliminary values that are arbitrarily similar
113 * will end up in different buckets. The hash function was taken
114 * from a random-number generator.
115 */
116#define RANDOM_INDEX(i) \
117 (((((long) (i))*1103515245) >> downshift) & mask)
118#define BITSPERWORD 32
119#endif
120
121#define DOWNSHIFT_START (BITSPERWORD - 2)
122
123/*
124 * Procedure prototypes for static procedures in this file:
125 */
126
127
128#if (SIZEOF_VOID_P == 8)
129static Blt_Hash HashOneWord _ANSI_ARGS_((uint64_t mask, unsigned int downshift,
130 CONST void *key));
131
132#endif /* SIZEOF_VOID_P == 8 */
133
134/*
135 * The hash table below is used to keep track of all the Blt_TreeKeys
136 * created so far.
137 */
138static Blt_HashTable keyTable;
139static int keyTableInitialized = 0;
140
141typedef struct {
142 Blt_HashTable treeTable; /* Table of trees. */
143 unsigned int nextId;
144 Tcl_Interp *interp;
145} TreeInterpData;
146
147typedef struct {
148 Tcl_Interp *interp;
149 ClientData clientData;
150 Blt_TreeKey key;
151 unsigned int mask;
152 Blt_TreeNotifyEventProc *proc;
153 Blt_TreeNotifyEvent event;
154 int notifyPending;
155} EventHandler;
156
157typedef struct {
158 ClientData clientData;
159 char *keyPattern;
160 char *withTag;
161 Node *nodePtr;
162 unsigned int mask;
163 Blt_TreeTraceProc *proc;
164 TreeClient *clientPtr;
165 Blt_ChainLink *linkPtr;
166} TraceHandler;
167
168/*
169 * --------------------------------------------------------------
170 *
171 * GetTreeInterpData --
172 *
173 * Creates or retrieves data associated with tree data objects
174 * for a particular thread. We're using Tcl_GetAssocData rather
175 * than the Tcl thread routines so BLT can work with pre-8.0
176 * Tcl versions that don't have thread support.
177 *
178 * Results:
179 * Returns a pointer to the tree interpreter data.
180 *
181 * --------------------------------------------------------------
182 */
183static TreeInterpData *
184GetTreeInterpData(Tcl_Interp *interp)
185{
186 Tcl_InterpDeleteProc *proc;
187 TreeInterpData *dataPtr;
188
189 dataPtr = (TreeInterpData *)
190 Tcl_GetAssocData(interp, TREE_THREAD_KEY, &proc);
191 if (dataPtr == NULL) {
192 dataPtr = Blt_Malloc(sizeof(TreeInterpData));
193 assert(dataPtr);
194 dataPtr->interp = interp;
195 Tcl_SetAssocData(interp, TREE_THREAD_KEY, TreeInterpDeleteProc,
196 dataPtr);
197 Blt_InitHashTable(&dataPtr->treeTable, BLT_STRING_KEYS);
198 }
199 return dataPtr;
200}
201
202/*
203 * --------------------------------------------------------------
204 *
205 * NewNode --
206 *
207 * Creates a new node in the tree without installing it. The
208 * number of nodes in the tree is incremented and a unique serial
209 * number is generated for the node.
210 *
211 * Also, all nodes have a label. If no label was provided (name
212 * is NULL) then automatically generate one in the form "nodeN"
213 * where N is the serial number of the node.
214 *
215 * Results:
216 * Returns a pointer to the new node.
217 *
218 * --------------------------------------------------------------
219 */
220static Node *
221NewNode(TreeObject *treeObjPtr, CONST char *name, int inode)
222{
223 Node *nodePtr;
224
225 /* Create the node structure */
226 nodePtr = Blt_PoolAllocItem(treeObjPtr->nodePool, sizeof(Node));
227 nodePtr->inode = inode;
228 nodePtr->treeObject = treeObjPtr;
229 nodePtr->parent = NULL;
230 nodePtr->depth = 0;
231 nodePtr->flags = 0;
232 nodePtr->next = nodePtr->prev = NULL;
233 nodePtr->first = nodePtr->last = NULL;
234 nodePtr->nChildren = 0;
235 nodePtr->values = NULL;
236 nodePtr->logSize = 0;
237 nodePtr->nValues = 0;
238 nodePtr->label = NULL;
239 if (name != NULL) {
240 nodePtr->label = Blt_TreeGetKey(name);
241 }
242 treeObjPtr->nNodes++;
243 return nodePtr;
244}
245
246/*
247 *----------------------------------------------------------------------
248 *
249 * ReleaseTagTable --
250 *
251 *----------------------------------------------------------------------
252 */
253static void
254ReleaseTagTable(Blt_TreeTagTable *tablePtr)
255{
256 tablePtr->refCount--;
257 if (tablePtr->refCount <= 0) {
258 Blt_HashEntry *hPtr;
259 Blt_HashSearch cursor;
260
261 for(hPtr = Blt_FirstHashEntry(&tablePtr->tagTable, &cursor);
262 hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
263 Blt_TreeTagEntry *tPtr;
264
265 tPtr = Blt_GetHashValue(hPtr);
266 Blt_DeleteHashTable(&tPtr->nodeTable);
267 Blt_Free(tPtr);
268 }
269 Blt_DeleteHashTable(&tablePtr->tagTable);
270 Blt_Free(tablePtr);
271 }
272}
273
274/*
275 * ----------------------------------------------------------------------
276 *
277 * ResetDepths --
278 *
279 * Called after moving a node, resets the depths of each node
280 * for the entire branch (node and it's decendants).
281 *
282 * Results:
283 * None.
284 *
285 * ----------------------------------------------------------------------
286 */
287static void
288ResetDepths(
289 Node *nodePtr, /* Root node. */
290 int depth) /* Depth of the node. */
291{
292 nodePtr->depth = depth;
293 /* Also reset the depth for each descendant node. */
294 for (nodePtr = nodePtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
295 ResetDepths(nodePtr, depth + 1);
296 }
297}
298
299/*
300 *----------------------------------------------------------------------
301 *
302 * LinkBefore --
303 *
304 * Inserts a link preceding a given link.
305 *
306 * Results:
307 * None.
308 *
309 *----------------------------------------------------------------------
310 */
311static void
312LinkBefore(
313 Node *parentPtr, /* Parent to hold the new entry. */
314 Node *nodePtr, /* New node to be inserted. */
315 Node *beforePtr) /* Node to link before. */
316{
317 if (parentPtr->first == NULL) {
318 parentPtr->last = parentPtr->first = nodePtr;
319 } else if (beforePtr == NULL) { /* Append onto the end of the chain */
320 nodePtr->next = NULL;
321 nodePtr->prev = parentPtr->last;
322 parentPtr->last->next = nodePtr;
323 parentPtr->last = nodePtr;
324 } else {
325 nodePtr->prev = beforePtr->prev;
326 nodePtr->next = beforePtr;
327 if (beforePtr == parentPtr->first) {
328 parentPtr->first = nodePtr;
329 } else {
330 beforePtr->prev->next = nodePtr;
331 }
332 beforePtr->prev = nodePtr;
333 }
334 parentPtr->nChildren++;
335 nodePtr->parent = parentPtr;
336}
337
338
339/*
340 *----------------------------------------------------------------------
341 *
342 * UnlinkNode --
343 *
344 * Unlinks a link from the chain. The link is not deallocated,
345 * but only removed from the chain.
346 *
347 * Results:
348 * None.
349 *
350 *----------------------------------------------------------------------
351 */
352static void
353UnlinkNode(Node *nodePtr)
354{
355 Node *parentPtr;
356 int unlinked; /* Indicates if the link is actually
357 * removed from the chain. */
358 parentPtr = nodePtr->parent;
359 unlinked = FALSE;
360 if (parentPtr->first == nodePtr) {
361 parentPtr->first = nodePtr->next;
362 unlinked = TRUE;
363 }
364 if (parentPtr->last == nodePtr) {
365 parentPtr->last = nodePtr->prev;
366 unlinked = TRUE;
367 }
368 if (nodePtr->next != NULL) {
369 nodePtr->next->prev = nodePtr->prev;
370 unlinked = TRUE;
371 }
372 if (nodePtr->prev != NULL) {
373 nodePtr->prev->next = nodePtr->next;
374 unlinked = TRUE;
375 }
376 if (unlinked) {
377 parentPtr->nChildren--;
378 }
379 nodePtr->prev = nodePtr->next = NULL;
380}
381
382/*
383 * --------------------------------------------------------------
384 *
385 * FreeNode --
386 *
387 * Unlinks a given node from the tree, removes its data, and
388 * frees memory allocated to the node.
389 *
390 * Results:
391 * None.
392 *
393 * --------------------------------------------------------------
394 */
395static void
396FreeNode(TreeObject *treeObjPtr, Node *nodePtr)
397{
398 Blt_HashEntry *hPtr;
399
400 /*
401 * Destroy any data fields associated with this node.
402 */
403 TreeDestroyValues(nodePtr);
404 UnlinkNode(nodePtr);
405 treeObjPtr->nNodes--;
406 hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)nodePtr->inode);
407 assert(hPtr);
408 Blt_DeleteHashEntry(&treeObjPtr->nodeTable, hPtr);
409 Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
410}
411
412/*
413 * --------------------------------------------------------------
414 *
415 * NewTreeObject --
416 *
417 * Creates and initializes a new tree object. Trees always
418 * contain a root node, so one is allocated here.
419 *
420 * Results:
421 * Returns a pointer to the new tree object is successful, NULL
422 * otherwise. If a tree can't be generated, interp->result will
423 * contain an error message.
424 *
425 * -------------------------------------------------------------- */
426static TreeObject *
427NewTreeObject(TreeInterpData *dataPtr, Tcl_Interp *interp, CONST char *treeName)
428{
429 TreeObject *treeObjPtr;
430 int isNew;
431 Blt_HashEntry *hPtr;
432
433 treeObjPtr = Blt_Calloc(1, sizeof(TreeObject));
434 if (treeObjPtr == NULL) {
435 Tcl_AppendResult(interp, "can't allocate tree", (char *)NULL);
436 return NULL;
437 }
438 treeObjPtr->name = Blt_Strdup(treeName);
439 treeObjPtr->interp = interp;
440 treeObjPtr->valuePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
441 treeObjPtr->nodePool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
442 treeObjPtr->clients = Blt_ChainCreate();
443 treeObjPtr->depth = 1;
444 treeObjPtr->notifyFlags = 0;
445 Blt_InitHashTableWithPool(&treeObjPtr->nodeTable, BLT_ONE_WORD_KEYS);
446
447 hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable, (char *)0, &isNew);
448 treeObjPtr->root = NewNode(treeObjPtr, treeName, 0);
449 Blt_SetHashValue(hPtr, treeObjPtr->root);
450
451 treeObjPtr->tablePtr = &dataPtr->treeTable;
452 treeObjPtr->hashPtr = Blt_CreateHashEntry(treeObjPtr->tablePtr, treeName,
453 &isNew);
454 Blt_SetHashValue(treeObjPtr->hashPtr, treeObjPtr);
455
456 return treeObjPtr;
457}
458
459static TreeObject *
460FindTreeInNamespace(
461 TreeInterpData *dataPtr, /* Interpreter-specific data. */
462 Tcl_Namespace *nsPtr,
463 CONST char *treeName)
464{
465 Tcl_DString dString;
466 char *name;
467 Blt_HashEntry *hPtr;
468
469 name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
470 hPtr = Blt_FindHashEntry(&dataPtr->treeTable, name);
471 Tcl_DStringFree(&dString);
472 if (hPtr != NULL) {
473 return Blt_GetHashValue(hPtr);
474 }
475 return NULL;
476}
477
478/*
479 * ----------------------------------------------------------------------
480 *
481 * GetTreeObject --
482 *
483 * Searches for the tree object associated by the name given.
484 *
485 * Results:
486 * Returns a pointer to the tree if found, otherwise NULL.
487 *
488 * ----------------------------------------------------------------------
489 */
490static TreeObject *
491GetTreeObject(Tcl_Interp *interp, CONST char *name, int flags)
492{
493 CONST char *treeName;
494 Tcl_Namespace *nsPtr; /* Namespace associated with the tree object.
495 * If NULL, indicates to look in first the
496 * current namespace and then the global
497 * for the tree. */
498 TreeInterpData *dataPtr; /* Interpreter-specific data. */
499 TreeObject *treeObjPtr;
500
501 treeObjPtr = NULL;
502 if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
503 Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
504 (char *)NULL);
505 return NULL;
506 }
507 dataPtr = GetTreeInterpData(interp);
508 if (nsPtr != NULL) {
509 treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
510 } else {
511 if (flags & NS_SEARCH_CURRENT) {
512 /* Look first in the current namespace. */
513 nsPtr = Tcl_GetCurrentNamespace(interp);
514 treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
515 }
516 if ((treeObjPtr == NULL) && (flags & NS_SEARCH_GLOBAL)) {
517 nsPtr = Tcl_GetGlobalNamespace(interp);
518 treeObjPtr = FindTreeInNamespace(dataPtr, nsPtr, treeName);
519 }
520 }
521 return treeObjPtr;
522}
523
524/*
525 * ----------------------------------------------------------------------
526 *
527 * TeardownTree --
528 *
529 * Destroys an entire branch. This is a special purpose routine
530 * used to speed up the final clean up of the tree.
531 *
532 * Results:
533 * None.
534 *
535 * ----------------------------------------------------------------------
536 */
537static void
538TeardownTree(TreeObject *treeObjPtr, Node *nodePtr)
539{
540 if (nodePtr->first != NULL) {
541 Node *childPtr, *nextPtr;
542
543 for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
544 nextPtr = childPtr->next;
545 TeardownTree(treeObjPtr, childPtr);
546 }
547 }
548 if (nodePtr->values != NULL) {
549 TreeDestroyValues(nodePtr);
550 }
551 Blt_PoolFreeItem(treeObjPtr->nodePool, (char *)nodePtr);
552}
553
554static void
555DestroyTreeObject(TreeObject *treeObjPtr)
556{
557 Blt_ChainLink *linkPtr;
558 TreeClient *clientPtr;
559
560 treeObjPtr->flags |= TREE_DESTROYED;
561 treeObjPtr->nNodes = 0;
562
563 /* Remove the remaining clients. */
564 for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients); linkPtr != NULL;
565 linkPtr = Blt_ChainNextLink(linkPtr)) {
566 clientPtr = Blt_ChainGetValue(linkPtr);
567 Blt_ChainDestroy(clientPtr->events);
568 Blt_ChainDestroy(clientPtr->traces);
569 Blt_Free(clientPtr);
570 }
571 Blt_ChainDestroy(treeObjPtr->clients);
572
573 TeardownTree(treeObjPtr, treeObjPtr->root);
574 Blt_PoolDestroy(treeObjPtr->nodePool);
575 Blt_PoolDestroy(treeObjPtr->valuePool);
576 Blt_DeleteHashTable(&treeObjPtr->nodeTable);
577
578 if (treeObjPtr->hashPtr != NULL) {
579 /* Remove the entry from the global tree table. */
580 Blt_DeleteHashEntry(treeObjPtr->tablePtr, treeObjPtr->hashPtr);
581 if ((treeObjPtr->tablePtr->numEntries == 0) && (keyTableInitialized)) {
582 keyTableInitialized = FALSE;
583 Blt_DeleteHashTable(&keyTable);
584 }
585 }
586 if (treeObjPtr->name != NULL) {
587 Blt_Free(treeObjPtr->name);
588 }
589 Blt_Free(treeObjPtr);
590}
591
592/*
593 * -----------------------------------------------------------------------
594 *
595 * TreeInterpDeleteProc --
596 *
597 * This is called when the interpreter hosting the tree object
598 * is deleted from the interpreter.
599 *
600 * Results:
601 * None.
602 *
603 * Side effects:
604 * Destroys all remaining trees and removes the hash table
605 * used to register tree names.
606 *
607 * ------------------------------------------------------------------------
608 */
609/* ARGSUSED */
610static void
611TreeInterpDeleteProc(
612 ClientData clientData, /* Interpreter-specific data. */
613 Tcl_Interp *interp)
614{
615 TreeInterpData *dataPtr = clientData;
616 Blt_HashEntry *hPtr;
617 Blt_HashSearch cursor;
618 TreeObject *treeObjPtr;
619
620 for (hPtr = Blt_FirstHashEntry(&dataPtr->treeTable, &cursor);
621 hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
622 treeObjPtr = (TreeObject *)Blt_GetHashValue(hPtr);
623 treeObjPtr->hashPtr = NULL;
624 DestroyTreeObject(treeObjPtr);
625 }
626 if (keyTableInitialized) {
627 keyTableInitialized = FALSE;
628 Blt_DeleteHashTable(&keyTable);
629 }
630 Blt_DeleteHashTable(&dataPtr->treeTable);
631 Tcl_DeleteAssocData(interp, TREE_THREAD_KEY);
632 Blt_Free(dataPtr);
633}
634
635/*
636 *----------------------------------------------------------------------
637 *
638 * NotifyIdleProc --
639 *
640 * Used to invoke event handler routines at some idle point.
641 * This routine is called from the Tcl event loop. Errors
642 * generated by the event handler routines are backgrounded.
643 *
644 * Results:
645 * None.
646 *
647 *----------------------------------------------------------------------
648 */
649static void
650NotifyIdleProc(ClientData clientData)
651{
652 EventHandler *notifyPtr = clientData;
653 int result;
654
655 notifyPtr->notifyPending = FALSE;
656 notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
657 result = (*notifyPtr->proc)(notifyPtr->clientData, &notifyPtr->event);
658 notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
659 if (result != TCL_OK) {
660 Tcl_BackgroundError(notifyPtr->interp);
661 }
662}
663
664/*
665 *----------------------------------------------------------------------
666 *
667 * CheckEventHandlers --
668 *
669 * Traverses the list of client event callbacks and checks
670 * if one matches the given event. A client may trigger an
671 * action that causes the tree to notify it. The can be
672 * prevented by setting the TREE_NOTIFY_FOREIGN_ONLY bit in
673 * the event handler.
674 *
675 * If a matching handler is found, a callback may be called either
676 * immediately or at the next idle time depending upon the
677 * TREE_NOTIFY_WHENIDLE bit.
678 *
679 * Since a handler routine may trigger yet another call to
680 * itself, callbacks are ignored while the event handler is
681 * executing.
682 *
683 * Results:
684 * None.
685 *
686 *----------------------------------------------------------------------
687 */
688static void
689CheckEventHandlers(
690 TreeClient *clientPtr,
691 int isSource, /* Indicates if the client is the source
692 * of the event. */
693 Blt_TreeNotifyEvent *eventPtr)
694{
695 Blt_ChainLink *linkPtr, *nextPtr;
696 EventHandler *notifyPtr;
697
698 eventPtr->tree = clientPtr;
699 for (linkPtr = Blt_ChainFirstLink(clientPtr->events);
700 linkPtr != NULL; linkPtr = nextPtr) {
701 nextPtr = Blt_ChainNextLink(linkPtr);
702 notifyPtr = Blt_ChainGetValue(linkPtr);
703 if ((notifyPtr->mask & TREE_NOTIFY_ACTIVE) ||
704 (notifyPtr->mask & eventPtr->type) == 0) {
705 continue; /* Ignore callbacks that are generated
706 * inside of a notify handler routine. */
707 }
708 if ((isSource) && (notifyPtr->mask & TREE_NOTIFY_FOREIGN_ONLY)) {
709 continue; /* Don't notify yourself. */
710 }
711 if (notifyPtr->mask & TREE_NOTIFY_WHENIDLE) {
712 if (!notifyPtr->notifyPending) {
713 notifyPtr->notifyPending = TRUE;
714 notifyPtr->event = *eventPtr;
715 Tcl_DoWhenIdle(NotifyIdleProc, notifyPtr);
716 }
717 } else {
718 int result;
719
720 notifyPtr->mask |= TREE_NOTIFY_ACTIVE;
721 result = (*notifyPtr->proc) (notifyPtr->clientData, eventPtr);
722 notifyPtr->mask &= ~TREE_NOTIFY_ACTIVE;
723 if (result != TCL_OK) {
724 Tcl_BackgroundError(notifyPtr->interp);
725 }
726 }
727 }
728}
729
730/*
731 *----------------------------------------------------------------------
732 *
733 * NotifyClients --
734 *
735 * Traverses the list of clients for a particular tree and
736 * notifies each client that an event occurred. Clients
737 * indicate interest in a particular event through a bit
738 * flag.
739 *
740 *----------------------------------------------------------------------
741 */
742static void
743NotifyClients(
744 TreeClient *sourcePtr,
745 TreeObject *treeObjPtr,
746 Node *nodePtr,
747 int eventFlag)
748{
749 Blt_ChainLink *linkPtr;
750 Blt_TreeNotifyEvent event;
751 TreeClient *clientPtr;
752 int isSource;
753
754 event.type = eventFlag;
755 event.inode = nodePtr->inode;
756
757 /*
758 * Issue callbacks to each client indicating that a new node has
759 * been created.
760 */
761 for (linkPtr = Blt_ChainFirstLink(treeObjPtr->clients);
762 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
763 clientPtr = Blt_ChainGetValue(linkPtr);
764 isSource = (clientPtr == sourcePtr);
765 CheckEventHandlers(clientPtr, isSource, &event);
766 }
767}
768
769static void
770FreeValue(Node *nodePtr, Value *valuePtr)
771{
772 if (valuePtr->objPtr != NULL) {
773 Tcl_DecrRefCount(valuePtr->objPtr);
774 }
775 Blt_PoolFreeItem(nodePtr->treeObject->valuePool, valuePtr);
776}
777
778
779
780/* Public Routines */
781/*
782 *----------------------------------------------------------------------
783 *
784 * Blt_TreeGetKey --
785 *
786 * Given a string, returns a unique identifier for the string.
787 *
788 *----------------------------------------------------------------------
789 */
790Blt_TreeKey
791Blt_TreeGetKey(string)
792 CONST char *string; /* String to convert. */
793{
794 Blt_HashEntry *hPtr;
795 int isNew;
796
797 if (!keyTableInitialized) {
798 Blt_InitHashTable(&keyTable, BLT_STRING_KEYS);
799 keyTableInitialized = 1;
800 }
801 hPtr = Blt_CreateHashEntry(&keyTable, string, &isNew);
802 return (Blt_TreeKey)Blt_GetHashKey(&keyTable, hPtr);
803}
804
805
806/*
807 *----------------------------------------------------------------------
808 *
809 * Blt_TreeCreateNode --
810 *
811 * Creates a new node in the given parent node. The name and
812 * position in the parent are also provided.
813 *
814 *----------------------------------------------------------------------
815 */
816Blt_TreeNode
817Blt_TreeCreateNode(
818 TreeClient *clientPtr, /* The tree client that is creating
819 * this node. If NULL, indicates to
820 * trigger notify events on behalf of
821 * the initiating client also. */
822 Node *parentPtr, /* Parent node where the new node will
823 * be inserted. */
824 CONST char *name, /* Name of node. */
825 int pos) /* Position in the parent's list of children
826 * where to insert the new node. */
827{
828 Blt_HashEntry *hPtr;
829 Node *beforePtr;
830 Node *nodePtr; /* Node to be inserted. */
831 TreeObject *treeObjPtr;
832 int inode;
833 int isNew;
834
835 treeObjPtr = parentPtr->treeObject;
836
837 /* Generate an unique serial number for this node. */
838 do {
839 inode = treeObjPtr->nextInode++;
840 hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode,
841 &isNew);
842 } while (!isNew);
843 nodePtr = NewNode(treeObjPtr, name, inode);
844 Blt_SetHashValue(hPtr, nodePtr);
845
846 if ((pos == -1) || (pos >= (int)parentPtr->nChildren)) {
847 beforePtr = NULL;
848 } else {
849 beforePtr = parentPtr->first;
850 while ((pos > 0) && (beforePtr != NULL)) {
851 pos--;
852 beforePtr = beforePtr->next;
853 }
854 }
855 LinkBefore(parentPtr, nodePtr, beforePtr);
856 nodePtr->depth = parentPtr->depth + 1;
857 /*
858 * Issue callbacks to each client indicating that a new node has
859 * been created.
860 */
861 NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE);
862 return nodePtr;
863}
864
865/*
866 *----------------------------------------------------------------------
867 *
868 * Blt_TreeCreateNodeWithId --
869 *
870 * Like Blt_TreeCreateNode, but provides a specific id to use
871 * for the node. If the tree already contains a node by that
872 * id, NULL is returned.
873 *
874 *----------------------------------------------------------------------
875 */
876Blt_TreeNode
877Blt_TreeCreateNodeWithId(
878 TreeClient *clientPtr,
879 Node *parentPtr, /* Parent node where the new node will
880 * be inserted. */
881 CONST char *name, /* Name of node. */
882 int inode, /* Requested id of the new node. If a
883 * node by this id already exists in the
884 * tree, no node is created. */
885 int position) /* Position in the parent's list of children
886 * where to insert the new node. */
887{
888 Blt_HashEntry *hPtr;
889 Node *beforePtr;
890 Node *nodePtr; /* Node to be inserted. */
891 TreeObject *treeObjPtr;
892 int isNew;
893
894 treeObjPtr = parentPtr->treeObject;
895 hPtr = Blt_CreateHashEntry(&treeObjPtr->nodeTable,(char *)inode, &isNew);
896 if (!isNew) {
897 return NULL;
898 }
899 nodePtr = NewNode(treeObjPtr, name, inode);
900 Blt_SetHashValue(hPtr, nodePtr);
901
902 if ((position == -1) || (position >= (int)parentPtr->nChildren)) {
903 beforePtr = NULL;
904 } else {
905 beforePtr = parentPtr->first;
906 while ((position > 0) && (beforePtr != NULL)) {
907 position--;
908 beforePtr = beforePtr->next;
909 }
910 }
911 LinkBefore(parentPtr, nodePtr, beforePtr);
912 nodePtr->depth = parentPtr->depth + 1;
913 /*
914 * Issue callbacks to each client indicating that a new node has
915 * been created.
916 */
917 NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_CREATE);
918 return nodePtr;
919}
920
921/*
922 *----------------------------------------------------------------------
923 *
924 * Blt_TreeMoveNode --
925 *
926 * Move an entry into a new location in the hierarchy.
927 *
928 *----------------------------------------------------------------------
929 */
930/*ARGSUSED*/
931int
932Blt_TreeMoveNode(
933 TreeClient *clientPtr,
934 Node *nodePtr,
935 Node *parentPtr,
936 Node *beforePtr)
937{
938 TreeObject *treeObjPtr = nodePtr->treeObject;
939 int newDepth;
940
941 if (nodePtr == beforePtr) {
942 return TCL_ERROR;
943 }
944 if ((beforePtr != NULL) && (beforePtr->parent != parentPtr)) {
945 return TCL_ERROR;
946 }
947 if (nodePtr->parent == NULL) {
948 return TCL_ERROR; /* Can't move root. */
949 }
950 /* Verify that the node isn't an ancestor of the new parent. */
951 if (Blt_TreeIsAncestor(nodePtr, parentPtr)) {
952 return TCL_ERROR;
953 }
954 UnlinkNode(nodePtr);
955 /*
956 * Relink the node as a child of the new parent.
957 */
958 LinkBefore(parentPtr, nodePtr, beforePtr);
959 newDepth = parentPtr->depth + 1;
960 if (nodePtr->depth != newDepth) {
961 /* Reset the depths of all descendant nodes. */
962 ResetDepths(nodePtr, newDepth);
963 }
964
965 /*
966 * Issue callbacks to each client indicating that a node has
967 * been moved.
968 */
969 NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_MOVE);
970 return TCL_OK;
971}
972
973int
974Blt_TreeDeleteNode(TreeClient *clientPtr, Node *nodePtr)
975{
976 TreeObject *treeObjPtr = nodePtr->treeObject;
977 Node *childPtr, *nextPtr;
978
979 /* In depth-first order, delete each descendant node. */
980 for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
981 nextPtr = childPtr->next;
982 Blt_TreeDeleteNode(clientPtr, childPtr);
983 }
984 /*
985 * Issue callbacks to each client indicating that the node can
986 * no longer be used.
987 */
988 NotifyClients(clientPtr, treeObjPtr, nodePtr, TREE_NOTIFY_DELETE);
989
990 /* Now remove the actual node. */
991 FreeNode(treeObjPtr, nodePtr);
992 return TCL_OK;
993}
994
995Blt_TreeNode
996Blt_TreeGetNode(TreeClient *clientPtr, unsigned int inode)
997{
998 TreeObject *treeObjPtr = clientPtr->treeObject;
999 Blt_HashEntry *hPtr;
1000
1001 hPtr = Blt_FindHashEntry(&treeObjPtr->nodeTable, (char *)inode);
1002 if (hPtr != NULL) {
1003 return (Blt_TreeNode)Blt_GetHashValue(hPtr);
1004 }
1005 return NULL;
1006}
1007
1008Blt_TreeTrace
1009Blt_TreeCreateTrace(
1010 TreeClient *clientPtr,
1011 Node *nodePtr,
1012 CONST char *keyPattern,
1013 CONST char *tagName,
1014 unsigned int mask,
1015 Blt_TreeTraceProc *proc,
1016 ClientData clientData)
1017{
1018 TraceHandler *tracePtr;
1019
1020 tracePtr = Blt_Calloc(1, sizeof (TraceHandler));
1021 assert(tracePtr);
1022 tracePtr->linkPtr = Blt_ChainAppend(clientPtr->traces, tracePtr);
1023 if (keyPattern != NULL) {
1024 tracePtr->keyPattern = Blt_Strdup(keyPattern);
1025 }
1026 if (tagName != NULL) {
1027 tracePtr->withTag = Blt_Strdup(tagName);
1028 }
1029 tracePtr->clientPtr = clientPtr;
1030 tracePtr->proc = proc;
1031 tracePtr->clientData = clientData;
1032 tracePtr->mask = mask;
1033 tracePtr->nodePtr = nodePtr;
1034 return (Blt_TreeTrace)tracePtr;
1035}
1036
1037void
1038Blt_TreeDeleteTrace(Blt_TreeTrace trace)
1039{
1040 TraceHandler *tracePtr = (TraceHandler *)trace;
1041
1042 Blt_ChainDeleteLink(tracePtr->clientPtr->traces, tracePtr->linkPtr);
1043 if (tracePtr->keyPattern != NULL) {
1044 Blt_Free(tracePtr->keyPattern);
1045 }
1046 if (tracePtr->withTag != NULL) {
1047 Blt_Free(tracePtr->withTag);
1048 }
1049 Blt_Free(tracePtr);
1050}
1051
1052void
1053Blt_TreeRelabelNode(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
1054{
1055 nodePtr->label = Blt_TreeGetKey(string);
1056 /*
1057 * Issue callbacks to each client indicating that a new node has
1058 * been created.
1059 */
1060 NotifyClients(clientPtr, clientPtr->treeObject, nodePtr,
1061 TREE_NOTIFY_RELABEL);
1062}
1063
1064void
1065Blt_TreeRelabelNode2(Node *nodePtr, CONST char *string)
1066{
1067 nodePtr->label = Blt_TreeGetKey(string);
1068}
1069
1070/*
1071 *----------------------------------------------------------------------
1072 *
1073 * Blt_TreeFindChild --
1074 *
1075 * Searches for the named node in a parent's chain of siblings.
1076 *
1077 *
1078 * Results:
1079 * If found, the child node is returned, otherwise NULL.
1080 *
1081 *----------------------------------------------------------------------
1082 */
1083Blt_TreeNode
1084Blt_TreeFindChild(Node *parentPtr, CONST char *string)
1085{
1086 Blt_TreeKey label;
1087 register Node *nodePtr;
1088
1089 label = Blt_TreeGetKey(string);
1090 for (nodePtr = parentPtr->first; nodePtr != NULL; nodePtr = nodePtr->next) {
1091 if (label == nodePtr->label) {
1092 return nodePtr;
1093 }
1094 }
1095 return NULL;
1096}
1097
1098/*
1099 *----------------------------------------------------------------------
1100 *
1101 * Blt_TreeNodePosition --
1102 *
1103 * Returns the position of the node in its parent's list of
1104 * children. The root's position is 0.
1105 *
1106 *----------------------------------------------------------------------
1107 */
1108int
1109Blt_TreeNodePosition(Node *nodePtr)
1110{
1111 Node *parentPtr;
1112 int count;
1113
1114 count = 0;
1115 parentPtr = nodePtr->parent;
1116 if (parentPtr != NULL) {
1117 Node *childPtr;
1118
1119 for (childPtr = parentPtr->first; childPtr != NULL;
1120 childPtr = childPtr->next) {
1121 if (nodePtr == childPtr) {
1122 break;
1123 }
1124 count++;
1125 }
1126 }
1127 return count;
1128}
1129
1130
1131/*
1132 *----------------------------------------------------------------------
1133 *
1134 * Blt_TreePrevNode --
1135 *
1136 * Returns the "previous" node in the tree. This node (in
1137 * depth-first order) is its parent, if the node has no siblings
1138 * that are previous to it. Otherwise it is the last descendant
1139 * of the last sibling. In this case, descend the sibling's
1140 * hierarchy, using the last child at any ancestor, with we
1141 * we find a leaf.
1142 *
1143 *----------------------------------------------------------------------
1144 */
1145Blt_TreeNode
1146Blt_TreePrevNode(Node *rootPtr, Node *nodePtr)
1147{
1148 Node *prevPtr;
1149
1150 if (nodePtr == rootPtr) {
1151 return NULL; /* The root is the first node. */
1152 }
1153 prevPtr = nodePtr->prev;
1154 if (prevPtr == NULL) {
1155 /* There are no siblings previous to this one, so pick the parent. */
1156 return nodePtr->parent;
1157 }
1158 /*
1159 * Traverse down the right-most thread, in order to select the
1160 * next entry. Stop when we reach a leaf.
1161 */
1162 nodePtr = prevPtr;
1163 while ((prevPtr = nodePtr->last) != NULL) {
1164 nodePtr = prevPtr;
1165 }
1166 return nodePtr;
1167}
1168
1169/*
1170 *----------------------------------------------------------------------
1171 *
1172 * Blt_TreeNextNode --
1173 *
1174 * Returns the "next" node in relation to the given node.
1175 * The next node (in depth-first order) is either the first
1176 * child of the given node the next sibling if the node has
1177 * no children (the node is a leaf). If the given node is the
1178 * last sibling, then try it's parent next sibling. Continue
1179 * until we either find a next sibling for some ancestor or
1180 * we reach the root node. In this case the current node is
1181 * the last node in the tree.
1182 *
1183 *----------------------------------------------------------------------
1184 */
1185Blt_TreeNode
1186Blt_TreeNextNode(Node *rootPtr, Node *nodePtr)
1187{
1188 Node *nextPtr;
1189
1190 /* Pick the first sub-node. */
1191 nextPtr = nodePtr->first;
1192 if (nextPtr != NULL) {
1193 return nextPtr;
1194 }
1195 /*
1196 * Back up until we can find a level where we can pick a
1197 * "next sibling". For the last entry we'll thread our
1198 * way back to the root.
1199 */
1200 while (nodePtr != rootPtr) {
1201 nextPtr = nodePtr->next;
1202 if (nextPtr != NULL) {
1203 return nextPtr;
1204 }
1205 nodePtr = nodePtr->parent;
1206 }
1207 return NULL; /* At root, no next node. */
1208}
1209
1210
1211int
1212Blt_TreeIsBefore(Node *n1Ptr, Node *n2Ptr)
1213{
1214 int depth;
1215 register int i;
1216 Node *nodePtr;
1217
1218 if (n1Ptr == n2Ptr) {
1219 return FALSE;
1220 }
1221 depth = MIN(n1Ptr->depth, n2Ptr->depth);
1222 if (depth == 0) { /* One of the nodes is root. */
1223 return (n1Ptr->parent == NULL);
1224 }
1225 /*
1226 * Traverse back from the deepest node, until both nodes are at
1227 * the same depth. Check if this ancestor node is the same for
1228 * both nodes.
1229 */
1230 for (i = n1Ptr->depth; i > depth; i--) {
1231 n1Ptr = n1Ptr->parent;
1232 }
1233 if (n1Ptr == n2Ptr) {
1234 return FALSE;
1235 }
1236 for (i = n2Ptr->depth; i > depth; i--) {
1237 n2Ptr = n2Ptr->parent;
1238 }
1239 if (n2Ptr == n1Ptr) {
1240 return TRUE;
1241 }
1242
1243 /*
1244 * First find the mutual ancestor of both nodes. Look at each
1245 * preceding ancestor level-by-level for both nodes. Eventually
1246 * we'll find a node that's the parent of both ancestors. Then
1247 * find the first ancestor in the parent's list of subnodes.
1248 */
1249 for (i = depth; i > 0; i--) {
1250 if (n1Ptr->parent == n2Ptr->parent) {
1251 break;
1252 }
1253 n1Ptr = n1Ptr->parent;
1254 n2Ptr = n2Ptr->parent;
1255 }
1256 for (nodePtr = n1Ptr->parent->first; nodePtr != NULL;
1257 nodePtr = nodePtr->next) {
1258 if (nodePtr == n1Ptr) {
1259 return TRUE;
1260 } else if (nodePtr == n2Ptr) {
1261 return FALSE;
1262 }
1263 }
1264 return FALSE;
1265}
1266
1267static void
1268CallTraces(
1269 Tcl_Interp *interp,
1270 TreeClient *sourcePtr, /* Client holding a reference to the
1271 * tree. If NULL, indicates to
1272 * execute all handlers, including
1273 * those of the caller. */
1274 TreeObject *treeObjPtr, /* Tree that was changed. */
1275 Node *nodePtr, /* Node that received the event. */
1276 Blt_TreeKey key,
1277 unsigned int flags)
1278{
1279 Blt_ChainLink *l1Ptr, *l2Ptr;
1280 TreeClient *clientPtr;
1281 TraceHandler *tracePtr;
1282
1283 for(l1Ptr = Blt_ChainFirstLink(treeObjPtr->clients);
1284 l1Ptr != NULL; l1Ptr = Blt_ChainNextLink(l1Ptr)) {
1285 clientPtr = Blt_ChainGetValue(l1Ptr);
1286 for(l2Ptr = Blt_ChainFirstLink(clientPtr->traces);
1287 l2Ptr != NULL; l2Ptr = Blt_ChainNextLink(l2Ptr)) {
1288 tracePtr = Blt_ChainGetValue(l2Ptr);
1289 if ((tracePtr->keyPattern != NULL) &&
1290 (!Tcl_StringMatch(key, tracePtr->keyPattern))) {
1291 continue; /* Key pattern doesn't match. */
1292 }
1293 if ((tracePtr->withTag != NULL) &&
1294 (!Blt_TreeHasTag(clientPtr, nodePtr, tracePtr->withTag))) {
1295 continue; /* Doesn't have the tag. */
1296 }
1297 if ((tracePtr->mask & flags) == 0) {
1298 continue; /* Flags don't match. */
1299 }
1300 if ((clientPtr == sourcePtr) &&
1301 (tracePtr->mask & TREE_TRACE_FOREIGN_ONLY)) {
1302 continue; /* This client initiated the trace. */
1303 }
1304 if ((tracePtr->nodePtr != NULL) && (tracePtr->nodePtr != nodePtr)) {
1305 continue; /* Nodes don't match. */
1306 }
1307 nodePtr->flags |= TREE_TRACE_ACTIVE;
1308 if ((*tracePtr->proc) (tracePtr->clientData, treeObjPtr->interp,
1309 nodePtr, key, flags) != TCL_OK) {
1310 if (interp != NULL) {
1311 Tcl_BackgroundError(interp);
1312 }
1313 }
1314 nodePtr->flags &= ~TREE_TRACE_ACTIVE;
1315 }
1316 }
1317}
1318
1319static Value *
1320GetTreeValue(
1321 Tcl_Interp *interp,
1322 TreeClient *clientPtr,
1323 Node *nodePtr,
1324 Blt_TreeKey key)
1325{
1326 register Value *valuePtr;
1327
1328 valuePtr = TreeFindValue(nodePtr, key);
1329 if (valuePtr == NULL) {
1330 if (interp != NULL) {
1331 Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1332 (char *)NULL);
1333 }
1334 return NULL;
1335 }
1336 if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1337 if (interp != NULL) {
1338 Tcl_AppendResult(interp, "can't access private field \"",
1339 key, "\"", (char *)NULL);
1340 }
1341 return NULL;
1342 }
1343 return valuePtr;
1344}
1345
1346int
1347Blt_TreePrivateValue(
1348 Tcl_Interp *interp,
1349 TreeClient *clientPtr,
1350 Node *nodePtr,
1351 Blt_TreeKey key)
1352{
1353 Value *valuePtr;
1354
1355 valuePtr = TreeFindValue(nodePtr, key);
1356 if (valuePtr == NULL) {
1357 if (interp != NULL) {
1358 Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1359 (char *)NULL);
1360 }
1361 return TCL_ERROR;
1362 }
1363 valuePtr->owner = clientPtr;
1364 return TCL_OK;
1365}
1366
1367int
1368Blt_TreePublicValue(
1369 Tcl_Interp *interp,
1370 TreeClient *clientPtr,
1371 Node *nodePtr,
1372 Blt_TreeKey key)
1373{
1374 Value *valuePtr;
1375
1376 valuePtr = TreeFindValue(nodePtr, key);
1377 if (valuePtr == NULL) {
1378 if (interp != NULL) {
1379 Tcl_AppendResult(interp, "can't find field \"", key, "\"",
1380 (char *)NULL);
1381 }
1382 return TCL_ERROR;
1383 }
1384 if (valuePtr->owner != clientPtr) {
1385 if (interp != NULL) {
1386 Tcl_AppendResult(interp, "not the owner of \"", key, "\"",
1387 (char *)NULL);
1388 }
1389 return TCL_ERROR;
1390 }
1391 valuePtr->owner = NULL;
1392 return TCL_OK;
1393}
1394
1395int
1396Blt_TreeValueExistsByKey(clientPtr, nodePtr, key)
1397 TreeClient *clientPtr;
1398 Node *nodePtr;
1399 Blt_TreeKey key;
1400{
1401 register Value *valuePtr;
1402
1403 valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
1404 if (valuePtr == NULL) {
1405 return FALSE;
1406 }
1407 return TRUE;
1408}
1409
1410int
1411Blt_TreeGetValueByKey(
1412 Tcl_Interp *interp,
1413 TreeClient *clientPtr,
1414 Node *nodePtr,
1415 Blt_TreeKey key,
1416 Tcl_Obj **objPtrPtr)
1417{
1418 register Value *valuePtr;
1419 TreeObject *treeObjPtr = nodePtr->treeObject;
1420
1421 valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
1422 if (valuePtr == NULL) {
1423 return TCL_ERROR;
1424 }
1425 *objPtrPtr = valuePtr->objPtr;
1426 if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1427 CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key,
1428 TREE_TRACE_READ);
1429 }
1430 return TCL_OK;
1431}
1432
1433int
1434Blt_TreeSetValueByKey(
1435 Tcl_Interp *interp,
1436 TreeClient *clientPtr,
1437 Node *nodePtr, /* Node to be updated. */
1438 Blt_TreeKey key, /* Identifies the field key. */
1439 Tcl_Obj *objPtr) /* New value of field. */
1440{
1441 TreeObject *treeObjPtr = nodePtr->treeObject;
1442 Value *valuePtr;
1443 unsigned int flags;
1444 int isNew;
1445
1446 assert(objPtr != NULL);
1447 valuePtr = TreeCreateValue(nodePtr, key, &isNew);
1448 if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1449 if (interp != NULL) {
1450 Tcl_AppendResult(interp, "can't set private field \"",
1451 key, "\"", (char *)NULL);
1452 }
1453 return TCL_ERROR;
1454 }
1455 if (objPtr != valuePtr->objPtr) {
1456 Tcl_IncrRefCount(objPtr);
1457 if (valuePtr->objPtr != NULL) {
1458 Tcl_DecrRefCount(valuePtr->objPtr);
1459 }
1460 valuePtr->objPtr = objPtr;
1461 }
1462 flags = TREE_TRACE_WRITE;
1463 if (isNew) {
1464 flags |= TREE_TRACE_CREATE;
1465 }
1466 if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
1467 CallTraces(interp, clientPtr, treeObjPtr, nodePtr, valuePtr->key,
1468 flags);
1469 }
1470 return TCL_OK;
1471}
1472
1473int
1474Blt_TreeUnsetValueByKey(
1475 Tcl_Interp *interp,
1476 TreeClient *clientPtr,
1477 Node *nodePtr, /* Node to be updated. */
1478 Blt_TreeKey key) /* Name of field in node. */
1479{
1480 TreeObject *treeObjPtr = nodePtr->treeObject;
1481 Value *valuePtr;
1482
1483 valuePtr = TreeFindValue(nodePtr, key);
1484 if (valuePtr == NULL) {
1485 return TCL_OK; /* It's okay to unset values that don't
1486 * exist in the node. */
1487 }
1488 if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1489 if (interp != NULL) {
1490 Tcl_AppendResult(interp, "can't unset private field \"",
1491 key, "\"", (char *)NULL);
1492 }
1493 return TCL_ERROR;
1494 }
1495 TreeDeleteValue(nodePtr, valuePtr);
1496 CallTraces(interp, clientPtr, treeObjPtr, nodePtr, key, TREE_TRACE_UNSET);
1497 return TCL_OK;
1498}
1499
1500static int
1501ParseParentheses(
1502 Tcl_Interp *interp,
1503 CONST char *string,
1504 char **leftPtr,
1505 char **rightPtr)
1506{
1507 register char *p;
1508 char *left, *right;
1509
1510 left = right = NULL;
1511 for (p = (char *)string; *p != '\0'; p++) {
1512 if (*p == '(') {
1513 left = p;
1514 } else if (*p == ')') {
1515 right = p;
1516 }
1517 }
1518 if (left != right) {
1519 if (((left != NULL) && (right == NULL)) ||
1520 ((left == NULL) && (right != NULL)) ||
1521 (left > right) || (right != (p - 1))) {
1522 if (interp != NULL) {
1523 Tcl_AppendResult(interp, "bad array specification \"", string,
1524 "\"", (char *)NULL);
1525 }
1526 return TCL_ERROR;
1527 }
1528 }
1529 *leftPtr = left;
1530 *rightPtr = right;
1531 return TCL_OK;
1532}
1533
1534int
1535Blt_TreeGetValue(
1536 Tcl_Interp *interp,
1537 TreeClient *clientPtr,
1538 Node *nodePtr,
1539 CONST char *string, /* String identifying the field in node. */
1540 Tcl_Obj **objPtrPtr)
1541{
1542 char *left, *right;
1543 int result;
1544
1545 if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1546 return TCL_ERROR;
1547 }
1548 if (left != NULL) {
1549 *left = *right = '\0';
1550 result = Blt_TreeGetArrayValue(interp, clientPtr, nodePtr, string,
1551 left + 1, objPtrPtr);
1552 *left = '(', *right = ')';
1553 } else {
1554 result = Blt_TreeGetValueByKey(interp, clientPtr, nodePtr,
1555 Blt_TreeGetKey(string), objPtrPtr);
1556 }
1557 return result;
1558}
1559
1560int
1561Blt_TreeSetValue(
1562 Tcl_Interp *interp,
1563 TreeClient *clientPtr,
1564 Node *nodePtr, /* Node to be updated. */
1565 CONST char *string, /* String identifying the field in node. */
1566 Tcl_Obj *valueObjPtr) /* New value of field. If NULL, field
1567 * is deleted. */
1568{
1569 char *left, *right;
1570 int result;
1571
1572 if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1573 return TCL_ERROR;
1574 }
1575 if (left != NULL) {
1576 *left = *right = '\0';
1577 result = Blt_TreeSetArrayValue(interp, clientPtr, nodePtr, string,
1578 left + 1, valueObjPtr);
1579 *left = '(', *right = ')';
1580 } else {
1581 result = Blt_TreeSetValueByKey(interp, clientPtr, nodePtr,
1582 Blt_TreeGetKey(string), valueObjPtr);
1583 }
1584 return result;
1585}
1586
1587int
1588Blt_TreeUnsetValue(
1589 Tcl_Interp *interp,
1590 TreeClient *clientPtr,
1591 Node *nodePtr, /* Node to be updated. */
1592 CONST char *string) /* String identifying the field in node. */
1593{
1594 char *left, *right;
1595 int result;
1596
1597 if (ParseParentheses(interp, string, &left, &right) != TCL_OK) {
1598 return TCL_ERROR;
1599 }
1600 if (left != NULL) {
1601 *left = *right = '\0';
1602 result = Blt_TreeUnsetArrayValue(interp, clientPtr, nodePtr, string,
1603 left + 1);
1604 *left = '(', *right = ')';
1605 } else {
1606 result = Blt_TreeUnsetValueByKey(interp, clientPtr, nodePtr,
1607 Blt_TreeGetKey(string));
1608 }
1609 return result;
1610}
1611
1612int
1613Blt_TreeValueExists(TreeClient *clientPtr, Node *nodePtr, CONST char *string)
1614{
1615 char *left, *right;
1616 int result;
1617
1618 if (ParseParentheses((Tcl_Interp *)NULL, string, &left, &right) != TCL_OK) {
1619 return FALSE;
1620 }
1621 if (left != NULL) {
1622 *left = *right = '\0';
1623 result = Blt_TreeArrayValueExists(clientPtr, nodePtr, string, left + 1);
1624 *left = '(', *right = ')';
1625 } else {
1626 result = Blt_TreeValueExistsByKey(clientPtr, nodePtr,
1627 Blt_TreeGetKey(string));
1628 }
1629 return result;
1630}
1631
1632Blt_TreeKey
1633Blt_TreeFirstKey(
1634 TreeClient *clientPtr,
1635 Node *nodePtr,
1636 Blt_TreeKeySearch *iterPtr)
1637{
1638 Value *valuePtr;
1639
1640 valuePtr = TreeFirstValue(nodePtr, iterPtr);
1641 if (valuePtr == NULL) {
1642 return NULL;
1643 }
1644 while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1645 valuePtr = TreeNextValue(iterPtr);
1646 if (valuePtr == NULL) {
1647 return NULL;
1648 }
1649 }
1650 return valuePtr->key;
1651}
1652
1653Blt_TreeKey
1654Blt_TreeNextKey(TreeClient *clientPtr, Blt_TreeKeySearch *iterPtr)
1655{
1656 Value *valuePtr;
1657
1658 valuePtr = TreeNextValue(iterPtr);
1659 if (valuePtr == NULL) {
1660 return NULL;
1661 }
1662 while ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
1663 valuePtr = TreeNextValue(iterPtr);
1664 if (valuePtr == NULL) {
1665 return NULL;
1666 }
1667 }
1668 return valuePtr->key;
1669}
1670
1671int
1672Blt_TreeIsAncestor(Node *n1Ptr, Node *n2Ptr)
1673{
1674 if (n2Ptr != NULL) {
1675 n2Ptr = n2Ptr->parent;
1676 while (n2Ptr != NULL) {
1677 if (n2Ptr == n1Ptr) {
1678 return TRUE;
1679 }
1680 n2Ptr = n2Ptr->parent;
1681 }
1682 }
1683 return FALSE;
1684}
1685
1686/*
1687 *----------------------------------------------------------------------
1688 *
1689 * Blt_TreeSortNode --
1690 *
1691 * Sorts the subnodes at a given node.
1692 *
1693 * Results:
1694 * Always returns TCL_OK.
1695 *
1696 *----------------------------------------------------------------------
1697 */
1698int
1699Blt_TreeSortNode(
1700 TreeClient *clientPtr,
1701 Node *nodePtr,
1702 Blt_TreeCompareNodesProc *proc)
1703{
1704 Node **nodeArr;
1705 Node *childPtr;
1706 int nNodes;
1707 register Node **p;
1708
1709 nNodes = nodePtr->nChildren;
1710 if (nNodes < 2) {
1711 return TCL_OK;
1712 }
1713 nodeArr = Blt_Malloc((nNodes + 1) * sizeof(Node *));
1714 if (nodeArr == NULL) {
1715 return TCL_ERROR; /* Out of memory. */
1716 }
1717 for (p = nodeArr, childPtr = nodePtr->first; childPtr != NULL;
1718 childPtr = childPtr->next, p++) {
1719 *p = childPtr;
1720 }
1721 *p = NULL;
1722
1723 qsort((char *)nodeArr, nNodes, sizeof(Node *), (QSortCompareProc *)proc);
1724 for (p = nodeArr; *p != NULL; p++) {
1725 UnlinkNode(*p);
1726 LinkBefore(nodePtr, *p, (Blt_TreeNode)NULL);
1727 }
1728 Blt_Free(nodeArr);
1729 NotifyClients(clientPtr, nodePtr->treeObject, nodePtr, TREE_NOTIFY_SORT);
1730 return TCL_OK;
1731}
1732
1733#define TEST_RESULT(result) \
1734 switch (result) { \
1735 case TCL_CONTINUE: \
1736 return TCL_OK; \
1737 case TCL_OK: \
1738 break; \
1739 default: \
1740 return (result); \
1741 }
1742
1743int
1744Blt_TreeApply(
1745 Node *nodePtr, /* Root node of subtree. */
1746 Blt_TreeApplyProc *proc, /* Procedure to call for each node. */
1747 ClientData clientData) /* One-word of data passed when calling
1748 * proc. */
1749{
1750 Node *childPtr, *nextPtr;
1751 int result;
1752
1753 for (childPtr = nodePtr->first; childPtr != NULL; childPtr = nextPtr) {
1754
1755 /*
1756 * Get the next link in the chain before calling Blt_TreeApply
1757 * recursively. This is because the apply callback may delete
1758 * the node and its link.
1759 */
1760
1761 nextPtr = childPtr->next;
1762 result = Blt_TreeApply(childPtr, proc, clientData);
1763 TEST_RESULT(result);
1764 }
1765 return (*proc) (nodePtr, clientData, TREE_POSTORDER);
1766}
1767
1768int
1769Blt_TreeApplyDFS(
1770 Node *nodePtr, /* Root node of subtree. */
1771 Blt_TreeApplyProc *proc, /* Procedure to call for each node. */
1772 ClientData clientData, /* One-word of data passed when calling
1773 * proc. */
1774 int order) /* Order of traversal. */
1775{
1776 Node *childPtr, *nextPtr;
1777 int result;
1778
1779 if (order & TREE_PREORDER) {
1780 result = (*proc) (nodePtr, clientData, TREE_PREORDER);
1781 TEST_RESULT(result);
1782 }
1783 childPtr = nodePtr->first;
1784 if (order & TREE_INORDER) {
1785 if (childPtr != NULL) {
1786 result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
1787 TEST_RESULT(result);
1788 childPtr = childPtr->next;
1789 }
1790 result = (*proc) (nodePtr, clientData, TREE_INORDER);
1791 TEST_RESULT(result);
1792 }
1793 for (/* empty */; childPtr != NULL; childPtr = nextPtr) {
1794 /*
1795 * Get the next link in the chain before calling
1796 * Blt_TreeApply recursively. This is because the
1797 * apply callback may delete the node and its link.
1798 */
1799 nextPtr = childPtr->next;
1800 result = Blt_TreeApplyDFS(childPtr, proc, clientData, order);
1801 TEST_RESULT(result);
1802 }
1803 if (order & TREE_POSTORDER) {
1804 return (*proc) (nodePtr, clientData, TREE_POSTORDER);
1805 }
1806 return TCL_OK;
1807}
1808
1809int
1810Blt_TreeApplyBFS(nodePtr, proc, clientData)
1811 Node *nodePtr; /* Root node of subtree. */
1812 Blt_TreeApplyProc *proc; /* Procedure to call for each node. */
1813 ClientData clientData; /* One-word of data passed when calling
1814 * proc. */
1815{
1816 Blt_Chain *queuePtr;
1817 Blt_ChainLink *linkPtr, *nextPtr;
1818 Node *childPtr;
1819 int result;
1820
1821 queuePtr = Blt_ChainCreate();
1822 linkPtr = Blt_ChainAppend(queuePtr, nodePtr);
1823 while (linkPtr != NULL) {
1824 nodePtr = Blt_ChainGetValue(linkPtr);
1825 /* Add the children to the queue. */
1826 for (childPtr = nodePtr->first; childPtr != NULL;
1827 childPtr = childPtr->next) {
1828 Blt_ChainAppend(queuePtr, childPtr);
1829 }
1830 /* Process the node. */
1831 result = (*proc) (nodePtr, clientData, TREE_BREADTHFIRST);
1832 switch (result) {
1833 case TCL_CONTINUE:
1834 Blt_ChainDestroy(queuePtr);
1835 return TCL_OK;
1836 case TCL_OK:
1837 break;
1838 default:
1839 Blt_ChainDestroy(queuePtr);
1840 return result;
1841 }
1842 /* Remove the node from the queue. */
1843 nextPtr = Blt_ChainNextLink(linkPtr);
1844 Blt_ChainDeleteLink(queuePtr, linkPtr);
1845 linkPtr = nextPtr;
1846 }
1847 Blt_ChainDestroy(queuePtr);
1848 return TCL_OK;
1849}
1850
1851static TreeClient *
1852NewTreeClient(TreeObject *treeObjPtr)
1853{
1854 TreeClient *clientPtr;
1855
1856 clientPtr = Blt_Calloc(1, sizeof(TreeClient));
1857 if (clientPtr != NULL) {
1858 Blt_TreeTagTable *tablePtr;
1859
1860 clientPtr->magic = TREE_MAGIC;
1861 clientPtr->linkPtr = Blt_ChainAppend(treeObjPtr->clients, clientPtr);
1862 clientPtr->events = Blt_ChainCreate();
1863 clientPtr->traces = Blt_ChainCreate();
1864 clientPtr->treeObject = treeObjPtr;
1865 clientPtr->root = treeObjPtr->root;
1866 tablePtr = Blt_Malloc(sizeof(Blt_TreeTagTable));
1867 Blt_InitHashTable(&tablePtr->tagTable, BLT_STRING_KEYS);
1868 tablePtr->refCount = 1;
1869 clientPtr->tagTablePtr = tablePtr;
1870 }
1871 return clientPtr;
1872}
1873
1874int
1875Blt_TreeCreate(
1876 Tcl_Interp *interp, /* Interpreter to report errors back to. */
1877 CONST char *name, /* Name of tree in namespace. Tree
1878 * must not already exist. */
1879 TreeClient **clientPtrPtr) /* (out) Client token of newly created
1880 * tree. Releasing the token will
1881 * free the tree. If NULL, no token
1882 * is generated. */
1883{
1884 Tcl_DString dString;
1885 Tcl_Namespace *nsPtr;
1886 TreeInterpData *dataPtr;
1887 TreeObject *treeObjPtr;
1888 CONST char *treeName;
1889 char string[200];
1890
1891 dataPtr = GetTreeInterpData(interp);
1892 if (name != NULL) {
1893 /* Check if this tree already exists the current namespace. */
1894 treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_CURRENT);
1895 if (treeObjPtr != NULL) {
1896 Tcl_AppendResult(interp, "a tree object \"", name,
1897 "\" already exists", (char *)NULL);
1898 return TCL_ERROR;
1899 }
1900 } else {
1901 /* Generate a unique tree name in the current namespace. */
1902 do {
1903 sprintf(string, "tree%d", dataPtr->nextId++);
1904 } while (GetTreeObject(interp, name, NS_SEARCH_CURRENT) != NULL);
1905 name = string;
1906 }
1907 /*
1908 * Tear apart and put back together the namespace-qualified name
1909 * of the tree. This is to ensure that naming is consistent.
1910 */
1911 treeName = name;
1912 if (Blt_ParseQualifiedName(interp, name, &nsPtr, &treeName) != TCL_OK) {
1913 Tcl_AppendResult(interp, "can't find namespace in \"", name, "\"",
1914 (char *)NULL);
1915 return TCL_ERROR;
1916 }
1917 if (nsPtr == NULL) {
1918 /*
1919 * Note: Unlike Tcl_CreateCommand, an unqualified name
1920 * doesn't imply the global namespace, but the current one.
1921 */
1922 nsPtr = Tcl_GetCurrentNamespace(interp);
1923 }
1924 name = Blt_GetQualifiedName(nsPtr, treeName, &dString);
1925 treeObjPtr = NewTreeObject(dataPtr, interp, name);
1926 if (treeObjPtr == NULL) {
1927 Tcl_AppendResult(interp, "can't allocate tree \"", name, "\"",
1928 (char *)NULL);
1929 Tcl_DStringFree(&dString);
1930 return TCL_ERROR;
1931 }
1932 Tcl_DStringFree(&dString);
1933 if (clientPtrPtr != NULL) {
1934 TreeClient *clientPtr;
1935
1936 clientPtr = NewTreeClient(treeObjPtr);
1937 if (clientPtr == NULL) {
1938 Tcl_AppendResult(interp, "can't allocate tree token",(char *)NULL);
1939 return TCL_ERROR;
1940 }
1941 *clientPtrPtr = clientPtr;
1942 }
1943 return TCL_OK;
1944}
1945
1946int
1947Blt_TreeGetToken(
1948 Tcl_Interp *interp, /* Interpreter to report errors back to. */
1949 CONST char *name, /* Name of tree in namespace. */
1950 TreeClient **clientPtrPtr)
1951{
1952 TreeClient *clientPtr;
1953 TreeObject *treeObjPtr;
1954
1955 treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
1956 if (treeObjPtr == NULL) {
1957 Tcl_AppendResult(interp, "can't find a tree object \"", name, "\"",
1958 (char *)NULL);
1959 return TCL_ERROR;
1960 }
1961 clientPtr = NewTreeClient(treeObjPtr);
1962 if (clientPtr == NULL) {
1963 Tcl_AppendResult(interp, "can't allocate token for tree \"",
1964 name, "\"", (char *)NULL);
1965 return TCL_ERROR;
1966 }
1967 *clientPtrPtr = clientPtr;
1968 return TCL_OK;
1969}
1970
1971void
1972Blt_TreeReleaseToken(TreeClient *clientPtr)
1973{
1974 TreeObject *treeObjPtr;
1975 Blt_ChainLink *linkPtr;
1976 EventHandler *notifyPtr;
1977 TraceHandler *tracePtr;
1978
1979 if (clientPtr->magic != TREE_MAGIC) {
1980 fprintf(stderr, "invalid tree object token 0x%lx\n",
1981 (unsigned long)clientPtr);
1982 return;
1983 }
1984 /* Remove any traces that may be set. */
1985 for (linkPtr = Blt_ChainFirstLink(clientPtr->traces); linkPtr != NULL;
1986 linkPtr = Blt_ChainNextLink(linkPtr)) {
1987 tracePtr = Blt_ChainGetValue(linkPtr);
1988 if (tracePtr->keyPattern != NULL) {
1989 Blt_Free(tracePtr->keyPattern);
1990 }
1991 Blt_Free(tracePtr);
1992 }
1993 Blt_ChainDestroy(clientPtr->traces);
1994 /* And any event handlers. */
1995 for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
1996 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
1997 notifyPtr = Blt_ChainGetValue(linkPtr);
1998 if (notifyPtr->notifyPending) {
1999 Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
2000 }
2001 Blt_Free(notifyPtr);
2002 }
2003 if (clientPtr->tagTablePtr != NULL) {
2004 ReleaseTagTable(clientPtr->tagTablePtr);
2005 }
2006 Blt_ChainDestroy(clientPtr->events);
2007 treeObjPtr = clientPtr->treeObject;
2008 if (treeObjPtr != NULL) {
2009 /* Remove the client from the server's list */
2010 Blt_ChainDeleteLink(treeObjPtr->clients, clientPtr->linkPtr);
2011 if (Blt_ChainGetLength(treeObjPtr->clients) == 0) {
2012 DestroyTreeObject(treeObjPtr);
2013 }
2014 }
2015 clientPtr->magic = 0;
2016 Blt_Free(clientPtr);
2017}
2018
2019int
2020Blt_TreeExists(interp, name)
2021 Tcl_Interp *interp; /* Interpreter to report errors back to. */
2022 CONST char *name; /* Name of tree in designated namespace. */
2023{
2024 TreeObject *treeObjPtr;
2025
2026 treeObjPtr = GetTreeObject(interp, name, NS_SEARCH_BOTH);
2027 if (treeObjPtr == NULL) {
2028 Tcl_ResetResult(interp);
2029 return 0;
2030 }
2031 return 1;
2032}
2033
2034/*ARGSUSED*/
2035static int
2036SizeApplyProc(
2037 Node *nodePtr, /* Not used. */
2038 ClientData clientData,
2039 int order) /* Not used. */
2040{
2041 int *sumPtr = clientData;
2042 *sumPtr = *sumPtr + 1;
2043 return TCL_OK;
2044}
2045
2046int
2047Blt_TreeSize(Node *nodePtr)
2048{
2049 int sum;
2050
2051 sum = 0;
2052 Blt_TreeApply(nodePtr, SizeApplyProc, &sum);
2053 return sum;
2054}
2055
2056
2057void
2058Blt_TreeCreateEventHandler(
2059 TreeClient *clientPtr,
2060 unsigned int mask,
2061 Blt_TreeNotifyEventProc *proc,
2062 ClientData clientData)
2063{
2064 Blt_ChainLink *linkPtr;
2065 EventHandler *notifyPtr;
2066
2067 notifyPtr = NULL; /* Suppress compiler warning. */
2068
2069 /* Check if the event is already handled. */
2070 for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
2071 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
2072 notifyPtr = Blt_ChainGetValue(linkPtr);
2073 if ((notifyPtr->proc == proc) &&
2074 (notifyPtr->mask == mask) &&
2075 (notifyPtr->clientData == clientData)) {
2076 break;
2077 }
2078 }
2079 if (linkPtr == NULL) {
2080 notifyPtr = Blt_Malloc(sizeof (EventHandler));
2081 assert(notifyPtr);
2082 linkPtr = Blt_ChainAppend(clientPtr->events, notifyPtr);
2083 }
2084 if (proc == NULL) {
2085 Blt_ChainDeleteLink(clientPtr->events, linkPtr);
2086 Blt_Free(notifyPtr);
2087 } else {
2088 notifyPtr->proc = proc;
2089 notifyPtr->clientData = clientData;
2090 notifyPtr->mask = mask;
2091 notifyPtr->notifyPending = FALSE;
2092 notifyPtr->interp = clientPtr->treeObject->interp;
2093 }
2094}
2095
2096void
2097Blt_TreeDeleteEventHandler(
2098 TreeClient *clientPtr,
2099 unsigned int mask,
2100 Blt_TreeNotifyEventProc *proc,
2101 ClientData clientData)
2102{
2103 Blt_ChainLink *linkPtr;
2104 EventHandler *notifyPtr;
2105
2106 for(linkPtr = Blt_ChainFirstLink(clientPtr->events);
2107 linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
2108 notifyPtr = Blt_ChainGetValue(linkPtr);
2109 if ((notifyPtr->proc == proc) && (notifyPtr->mask == mask) &&
2110 (notifyPtr->clientData == clientData)) {
2111 if (notifyPtr->notifyPending) {
2112 Tcl_CancelIdleCall(NotifyIdleProc, notifyPtr);
2113 }
2114 Blt_ChainDeleteLink(clientPtr->events, linkPtr);
2115 Blt_Free(notifyPtr);
2116 return;
2117 }
2118 }
2119}
2120
2121/*
2122 *----------------------------------------------------------------------
2123 *
2124 * Blt_TreeNodePath --
2125 *
2126 *----------------------------------------------------------------------
2127 */
2128char *
2129Blt_TreeNodePath(Node *nodePtr, Tcl_DString *resultPtr)
2130{
2131 char **nameArr; /* Used to stack the component names. */
2132 char *staticSpace[64];
2133 int nLevels;
2134 register int i;
2135
2136 nLevels = nodePtr->depth;
2137 if (nLevels > 64) {
2138 nameArr = Blt_Malloc(nLevels * sizeof(char *));
2139 assert(nameArr);
2140 } else {
2141 nameArr = staticSpace;
2142 }
2143 for (i = nLevels - 1; i >= 0; i--) {
2144 /* Save the name of each ancestor in the name array.
2145 * Note that we ignore the root. */
2146 nameArr[i] = nodePtr->label;
2147 nodePtr = nodePtr->parent;
2148 }
2149 /* Append each the names in the array. */
2150 Tcl_DStringInit(resultPtr);
2151 for (i = 0; i < nLevels; i++) {
2152 Tcl_DStringAppendElement(resultPtr, nameArr[i]);
2153 }
2154 if (nameArr != staticSpace) {
2155 Blt_Free(nameArr);
2156 }
2157 return Tcl_DStringValue(resultPtr);
2158}
2159
2160int
2161Blt_TreeArrayValueExists(
2162 TreeClient *clientPtr,
2163 Node *nodePtr,
2164 CONST char *arrayName,
2165 CONST char *elemName)
2166{
2167 Blt_TreeKey key;
2168 Blt_HashEntry *hPtr;
2169 Blt_HashTable *tablePtr;
2170 register Value *valuePtr;
2171
2172 key = Blt_TreeGetKey(arrayName);
2173 valuePtr = GetTreeValue((Tcl_Interp *)NULL, clientPtr, nodePtr, key);
2174 if (valuePtr == NULL) {
2175 return FALSE;
2176 }
2177 if (Tcl_IsShared(valuePtr->objPtr)) {
2178 Tcl_DecrRefCount(valuePtr->objPtr);
2179 valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2180 Tcl_IncrRefCount(valuePtr->objPtr);
2181 }
2182 if (Blt_GetArrayFromObj((Tcl_Interp *)NULL, valuePtr->objPtr, &tablePtr)
2183 != TCL_OK) {
2184 return FALSE;
2185 }
2186 hPtr = Blt_FindHashEntry(tablePtr, elemName);
2187 return (hPtr != NULL);
2188}
2189
2190int
2191Blt_TreeGetArrayValue(
2192 Tcl_Interp *interp,
2193 TreeClient *clientPtr,
2194 Node *nodePtr,
2195 CONST char *arrayName,
2196 CONST char *elemName,
2197 Tcl_Obj **valueObjPtrPtr)
2198{
2199 Blt_TreeKey key;
2200 Blt_HashEntry *hPtr;
2201 Blt_HashTable *tablePtr;
2202 register Value *valuePtr;
2203
2204 key = Blt_TreeGetKey(arrayName);
2205 valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
2206 if (valuePtr == NULL) {
2207 return TCL_ERROR;
2208 }
2209 if (Tcl_IsShared(valuePtr->objPtr)) {
2210 Tcl_DecrRefCount(valuePtr->objPtr);
2211 valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2212 Tcl_IncrRefCount(valuePtr->objPtr);
2213 }
2214 if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2215 return TCL_ERROR;
2216 }
2217 hPtr = Blt_FindHashEntry(tablePtr, elemName);
2218 if (hPtr == NULL) {
2219 if (interp != NULL) {
2220 Tcl_AppendResult(interp, "can't find \"", arrayName, "(",
2221 elemName, ")\"", (char *)NULL);
2222 }
2223 return TCL_ERROR;
2224 }
2225 *valueObjPtrPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
2226
2227 /* Reading any element of the array can cause a trace to fire. */
2228 if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2229 CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr, key,
2230 TREE_TRACE_READ);
2231 }
2232 return TCL_OK;
2233}
2234
2235int
2236Blt_TreeSetArrayValue(
2237 Tcl_Interp *interp,
2238 TreeClient *clientPtr,
2239 Node *nodePtr, /* Node to be updated. */
2240 CONST char *arrayName,
2241 CONST char *elemName,
2242 Tcl_Obj *valueObjPtr) /* New value of element. */
2243{
2244 Blt_TreeKey key;
2245 Blt_HashEntry *hPtr;
2246 Blt_HashTable *tablePtr;
2247 register Value *valuePtr;
2248 unsigned int flags;
2249 int isNew;
2250
2251 assert(valueObjPtr != NULL);
2252
2253 /*
2254 * Search for the array in the list of data fields. If one
2255 * doesn't exist, create it.
2256 */
2257 key = Blt_TreeGetKey(arrayName);
2258 valuePtr = TreeCreateValue(nodePtr, key, &isNew);
2259 if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
2260 if (interp != NULL) {
2261 Tcl_AppendResult(interp, "can't set private field \"",
2262 key, "\"", (char *)NULL);
2263 }
2264 return TCL_ERROR;
2265 }
2266 flags = TREE_TRACE_WRITE;
2267 if (isNew) {
2268 valuePtr->objPtr = Blt_NewArrayObj(0, (Tcl_Obj **)NULL);
2269 Tcl_IncrRefCount(valuePtr->objPtr);
2270 flags |= TREE_TRACE_CREATE;
2271 } else if (Tcl_IsShared(valuePtr->objPtr)) {
2272 Tcl_DecrRefCount(valuePtr->objPtr);
2273 valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2274 Tcl_IncrRefCount(valuePtr->objPtr);
2275 }
2276 if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2277 return TCL_ERROR;
2278 }
2279 Tcl_InvalidateStringRep(valuePtr->objPtr);
2280 hPtr = Blt_CreateHashEntry(tablePtr, elemName, &isNew);
2281 assert(hPtr);
2282
2283 Tcl_IncrRefCount(valueObjPtr);
2284 if (!isNew) {
2285 Tcl_Obj *oldValueObjPtr;
2286
2287 /* An element by the same name already exists. Decrement the
2288 * reference count of the old value. */
2289
2290 oldValueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
2291 if (oldValueObjPtr != NULL) {
2292 Tcl_DecrRefCount(oldValueObjPtr);
2293 }
2294 }
2295 Blt_SetHashValue(hPtr, valueObjPtr);
2296
2297 /*
2298 * We don't handle traces on a per array element basis. Setting
2299 * any element can fire traces for the value.
2300 */
2301 if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2302 CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
2303 valuePtr->key, flags);
2304 }
2305 return TCL_OK;
2306}
2307
2308int
2309Blt_TreeUnsetArrayValue(
2310 Tcl_Interp *interp,
2311 TreeClient *clientPtr,
2312 Node *nodePtr, /* Node to be updated. */
2313 CONST char *arrayName,
2314 CONST char *elemName)
2315{
2316 Blt_TreeKey key; /* Name of field in node. */
2317 Blt_HashEntry *hPtr;
2318 Blt_HashTable *tablePtr;
2319 Tcl_Obj *valueObjPtr;
2320 Value *valuePtr;
2321
2322 key = Blt_TreeGetKey(arrayName);
2323 valuePtr = TreeFindValue(nodePtr, key);
2324 if (valuePtr == NULL) {
2325 return TCL_OK;
2326 }
2327 if ((valuePtr->owner != NULL) && (valuePtr->owner != clientPtr)) {
2328 if (interp != NULL) {
2329 Tcl_AppendResult(interp, "can't unset private field \"",
2330 key, "\"", (char *)NULL);
2331 }
2332 return TCL_ERROR;
2333 }
2334 if (Tcl_IsShared(valuePtr->objPtr)) {
2335 Tcl_DecrRefCount(valuePtr->objPtr);
2336 valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2337 Tcl_IncrRefCount(valuePtr->objPtr);
2338 }
2339 if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2340 return TCL_ERROR;
2341 }
2342 hPtr = Blt_FindHashEntry(tablePtr, elemName);
2343 if (hPtr == NULL) {
2344 return TCL_OK; /* Element doesn't exist, Ok. */
2345 }
2346 valueObjPtr = (Tcl_Obj *)Blt_GetHashValue(hPtr);
2347 Tcl_DecrRefCount(valueObjPtr);
2348 Blt_DeleteHashEntry(tablePtr, hPtr);
2349
2350 /*
2351 * Un-setting any element in the array can cause the trace on the value
2352 * to fire.
2353 */
2354 if (!(nodePtr->flags & TREE_TRACE_ACTIVE)) {
2355 CallTraces(interp, clientPtr, nodePtr->treeObject, nodePtr,
2356 valuePtr->key, TREE_TRACE_WRITE);
2357 }
2358 return TCL_OK;
2359}
2360
2361int
2362Blt_TreeArrayNames(
2363 Tcl_Interp *interp,
2364 TreeClient *clientPtr,
2365 Node *nodePtr,
2366 CONST char *arrayName,
2367 Tcl_Obj *listObjPtr)
2368{
2369 Blt_HashEntry *hPtr;
2370 Blt_HashSearch cursor;
2371 Blt_HashTable *tablePtr;
2372 Tcl_Obj *objPtr;
2373 Value *valuePtr;
2374 char *key;
2375
2376 key = Blt_TreeGetKey(arrayName);
2377 valuePtr = GetTreeValue(interp, clientPtr, nodePtr, key);
2378 if (valuePtr == NULL) {
2379 return TCL_ERROR;
2380 }
2381 if (Tcl_IsShared(valuePtr->objPtr)) {
2382 Tcl_DecrRefCount(valuePtr->objPtr);
2383 valuePtr->objPtr = Tcl_DuplicateObj(valuePtr->objPtr);
2384 Tcl_IncrRefCount(valuePtr->objPtr);
2385 }
2386 if (Blt_GetArrayFromObj(interp, valuePtr->objPtr, &tablePtr) != TCL_OK) {
2387 return TCL_ERROR;
2388 }
2389 tablePtr = (Blt_HashTable *)valuePtr->objPtr;
2390 for (hPtr = Blt_FirstHashEntry(tablePtr, &cursor); hPtr != NULL;
2391 hPtr = Blt_NextHashEntry(&cursor)) {
2392 objPtr = Tcl_NewStringObj(Blt_GetHashKey(tablePtr, hPtr), -1);
2393 Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
2394 }
2395 return TCL_OK;
2396}
2397
2398/*
2399 *----------------------------------------------------------------------
2400 *
2401 * Blt_TreeShareTagTable --
2402 *
2403 *----------------------------------------------------------------------
2404 */
2405int
2406Blt_TreeShareTagTable(
2407 TreeClient *sourcePtr,
2408 TreeClient *targetPtr)
2409{
2410 sourcePtr->tagTablePtr->refCount++;
2411 if (targetPtr->tagTablePtr != NULL) {
2412 ReleaseTagTable(targetPtr->tagTablePtr);
2413 }
2414 targetPtr->tagTablePtr = sourcePtr->tagTablePtr;
2415 return TCL_OK;
2416}
2417
2418int
2419Blt_TreeTagTableIsShared(TreeClient *clientPtr)
2420{
2421 return (clientPtr->tagTablePtr->refCount > 1);
2422}
2423
2424void
2425Blt_TreeClearTags(TreeClient *clientPtr, Blt_TreeNode node)
2426{
2427 Blt_HashEntry *hPtr, *h2Ptr;
2428 Blt_HashSearch cursor;
2429
2430 for (hPtr = Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, &cursor);
2431 hPtr != NULL; hPtr = Blt_NextHashEntry(&cursor)) {
2432 Blt_TreeTagEntry *tPtr;
2433
2434 tPtr = Blt_GetHashValue(hPtr);
2435 h2Ptr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
2436 if (h2Ptr != NULL) {
2437 Blt_DeleteHashEntry(&tPtr->nodeTable, h2Ptr);
2438 }
2439 }
2440}
2441
2442int
2443Blt_TreeHasTag(
2444 TreeClient *clientPtr,
2445 Blt_TreeNode node,
2446 CONST char *tagName)
2447{
2448 Blt_HashEntry *hPtr;
2449 Blt_TreeTagEntry *tPtr;
2450
2451 if (strcmp(tagName, "all") == 0) {
2452 return TRUE;
2453 }
2454 if ((strcmp(tagName, "root") == 0) &&
2455 (node == Blt_TreeRootNode(clientPtr))) {
2456 return TRUE;
2457 }
2458 hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
2459 if (hPtr == NULL) {
2460 return FALSE;
2461 }
2462 tPtr = Blt_GetHashValue(hPtr);
2463 hPtr = Blt_FindHashEntry(&tPtr->nodeTable, (char *)node);
2464 if (hPtr == NULL) {
2465 return FALSE;
2466 }
2467 return TRUE;
2468}
2469
2470void
2471Blt_TreeAddTag(
2472 TreeClient *clientPtr,
2473 Blt_TreeNode node,
2474 CONST char *tagName)
2475{
2476 int isNew;
2477 Blt_HashEntry *hPtr;
2478 Blt_HashTable *tablePtr;
2479 Blt_TreeTagEntry *tPtr;
2480
2481 if ((strcmp(tagName, "all") == 0) || (strcmp(tagName, "root") == 0)) {
2482 return;
2483 }
2484 tablePtr = &clientPtr->tagTablePtr->tagTable;
2485 hPtr = Blt_CreateHashEntry(tablePtr, tagName, &isNew);
2486 assert(hPtr);
2487 if (isNew) {
2488
2489 tPtr = Blt_Malloc(sizeof(Blt_TreeTagEntry));
2490 Blt_InitHashTable(&tPtr->nodeTable, BLT_ONE_WORD_KEYS);
2491 Blt_SetHashValue(hPtr, tPtr);
2492 tPtr->hashPtr = hPtr;
2493 tPtr->tagName = Blt_GetHashKey(tablePtr, hPtr);
2494 } else {
2495 tPtr = Blt_GetHashValue(hPtr);
2496 }
2497 hPtr = Blt_CreateHashEntry(&tPtr->nodeTable, (char *)node, &isNew);
2498 assert(hPtr);
2499 if (isNew) {
2500 Blt_SetHashValue(hPtr, node);
2501 }
2502}
2503
2504void
2505Blt_TreeForgetTag(TreeClient *clientPtr, CONST char *tagName)
2506{
2507 if ((strcmp(tagName, "all") != 0) && (strcmp(tagName, "root") != 0)) {
2508 Blt_HashEntry *hPtr;
2509
2510 hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
2511 if (hPtr != NULL) {
2512 Blt_TreeTagEntry *tPtr;
2513
2514 Blt_DeleteHashEntry(&clientPtr->tagTablePtr->tagTable, hPtr);
2515 tPtr = Blt_GetHashValue(hPtr);
2516 Blt_DeleteHashTable(&tPtr->nodeTable);
2517 Blt_Free(tPtr);
2518 }
2519 }
2520}
2521
2522/*
2523 *----------------------------------------------------------------------
2524 *
2525 * Blt_TreeTagHashTable --
2526 *
2527 *----------------------------------------------------------------------
2528 */
2529Blt_HashTable *
2530Blt_TreeTagHashTable(TreeClient *clientPtr, CONST char *tagName)
2531{
2532 Blt_HashEntry *hPtr;
2533
2534 hPtr = Blt_FindHashEntry(&clientPtr->tagTablePtr->tagTable, tagName);
2535 if (hPtr != NULL) {
2536 Blt_TreeTagEntry *tPtr;
2537
2538 tPtr = Blt_GetHashValue(hPtr);
2539 return &tPtr->nodeTable;
2540 }
2541 return NULL;
2542}
2543
2544Blt_HashEntry *
2545Blt_TreeFirstTag(TreeClient *clientPtr, Blt_HashSearch *cursorPtr)
2546{
2547 return Blt_FirstHashEntry(&clientPtr->tagTablePtr->tagTable, cursorPtr);
2548}
2549
2550#if (SIZEOF_VOID_P == 8)
2551/*
2552 *----------------------------------------------------------------------
2553 *
2554 * HashOneWord --
2555 *
2556 * Compute a one-word hash value of a 64-bit word, which then can
2557 * be used to generate a hash index.
2558 *
2559 * From Knuth, it's a multiplicative hash. Multiplies an unsigned
2560 * 64-bit value with the golden ratio (sqrt(5) - 1) / 2. The
2561 * downshift value is 64 - n, when n is the log2 of the size of
2562 * the hash table.
2563 *
2564 * Results:
2565 * The return value is a one-word summary of the information in
2566 * 64 bit word.
2567 *
2568 * Side effects:
2569 * None.
2570 *
2571 *----------------------------------------------------------------------
2572 */
2573static Blt_Hash
2574HashOneWord(
2575 uint64_t mask,
2576 unsigned int downshift,
2577 CONST void *key)
2578{
2579 uint64_t a0, a1;
2580 uint64_t y0, y1;
2581 uint64_t y2, y3;
2582 uint64_t p1, p2;
2583 uint64_t result;
2584
2585 /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
2586 a0 = (uint64_t)key & 0x00000000FFFFFFFF;
2587 a1 = (uint64_t)key >> 32;
2588
2589 y0 = a0 * 0x000000007f4a7c13;
2590 y1 = a0 * 0x000000009e3779b9;
2591 y2 = a1 * 0x000000007f4a7c13;
2592 y3 = a1 * 0x000000009e3779b9;
2593 y1 += y0 >> 32; /* Can't carry */
2594 y1 += y2; /* Might carry */
2595 if (y1 < y2) {
2596 y3 += (1LL << 32); /* Propagate */
2597 }
2598
2599 /* 128-bit product: p1 = loword, p2 = hiword */
2600 p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
2601 p2 = y3 + (y1 >> 32);
2602
2603 /* Left shift the value downward by the size of the table */
2604 if (downshift > 0) {
2605 if (downshift < 64) {
2606 result = ((p2 << (64 - downshift)) | (p1 >> (downshift & 63)));
2607 } else {
2608 result = p2 >> (downshift & 63);
2609 }
2610 } else {
2611 result = p1;
2612 }
2613 /* Finally mask off the high bits */
2614 return (Blt_Hash)(result & mask);
2615}
2616
2617#endif /* SIZEOF_VOID_P == 8 */
2618
2619/*
2620 *----------------------------------------------------------------------
2621 *
2622 * RebuildTable --
2623 *
2624 * This procedure is invoked when the ratio of entries to hash
2625 * buckets becomes too large. It creates a new table with a
2626 * larger bucket array and moves all of the entries into the
2627 * new table.
2628 *
2629 * Results:
2630 * None.
2631 *
2632 * Side effects:
2633 * Memory gets reallocated and entries get re-hashed to new
2634 * buckets.
2635 *
2636 *----------------------------------------------------------------------
2637 */
2638static void
2639RebuildTable(Node *nodePtr) /* Table to enlarge. */
2640{
2641 Value **newBucketPtr, **oldBuckets;
2642 register Value **bucketPtr, **endPtr;
2643 register Value *valuePtr, *nextPtr;
2644 unsigned int downshift;
2645 unsigned long mask;
2646 Value **buckets;
2647 size_t nBuckets;
2648
2649 oldBuckets = (Value **)nodePtr->values;
2650 nBuckets = (1 << nodePtr->logSize);
2651 endPtr = oldBuckets + nBuckets;
2652
2653 /*
2654 * Allocate and initialize the new bucket array, and set up
2655 * hashing constants for new array size.
2656 */
2657 nodePtr->logSize += 2;
2658 nBuckets = (1 << nodePtr->logSize);
2659 buckets = Blt_Calloc(nBuckets, sizeof(Value *));
2660
2661 /*
2662 * Move all of the existing entries into the new bucket array,
2663 * based on their hash values.
2664 */
2665 mask = nBuckets - 1;
2666 downshift = DOWNSHIFT_START - nodePtr->logSize;
2667 for (bucketPtr = oldBuckets; bucketPtr < endPtr; bucketPtr++) {
2668 for (valuePtr = *bucketPtr; valuePtr != NULL; valuePtr = nextPtr) {
2669 nextPtr = valuePtr->next;
2670 newBucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
2671 valuePtr->next = *newBucketPtr;
2672 *newBucketPtr = valuePtr;
2673 }
2674 }
2675 nodePtr->values = (Value *)buckets;
2676 Blt_Free(oldBuckets);
2677}
2678
2679static void
2680ConvertValues(Node *nodePtr)
2681{
2682 unsigned int nBuckets;
2683 Value **buckets;
2684 unsigned int mask;
2685 int downshift;
2686 Value *valuePtr, *nextPtr, **bucketPtr;
2687
2688 /*
2689 * Convert list of values into a hash table.
2690 */
2691 nodePtr->logSize = START_LOGSIZE;
2692 nBuckets = 1 << nodePtr->logSize;
2693 buckets = Blt_Calloc(nBuckets, sizeof(Value *));
2694 mask = nBuckets - 1;
2695 downshift = DOWNSHIFT_START - nodePtr->logSize;
2696 for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
2697 nextPtr = valuePtr->next;
2698 bucketPtr = buckets + RANDOM_INDEX(valuePtr->key);
2699 valuePtr->next = *bucketPtr;
2700 *bucketPtr = valuePtr;
2701 }
2702 nodePtr->values = (Value *)buckets;
2703}
2704
2705/*
2706 *----------------------------------------------------------------------
2707 *
2708 * TreeDeleteValue --
2709 *
2710 * Remove a single entry from a hash table.
2711 *
2712 * Results:
2713 * None.
2714 *
2715 * Side effects:
2716 * The entry given by entryPtr is deleted from its table and
2717 * should never again be used by the caller. It is up to the
2718 * caller to free the clientData field of the entry, if that
2719 * is relevant.
2720 *
2721 *----------------------------------------------------------------------
2722 */
2723static int
2724TreeDeleteValue(Node *nodePtr, Blt_TreeValue value)
2725{
2726 Value *valuePtr = value;
2727 register Value *prevPtr;
2728
2729 if (nodePtr->logSize > 0) {
2730 Value **bucketPtr;
2731 unsigned int downshift;
2732 unsigned long mask;
2733
2734 mask = (1 << nodePtr->logSize) - 1;
2735 downshift = DOWNSHIFT_START - nodePtr->logSize;
2736
2737 bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX(valuePtr->key);
2738 if (*bucketPtr == valuePtr) {
2739 *bucketPtr = valuePtr->next;
2740 } else {
2741 for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->next) {
2742 if (prevPtr == NULL) {
2743 return TCL_ERROR; /* Can't find value in hash bucket. */
2744 }
2745 if (prevPtr->next == valuePtr) {
2746 prevPtr->next = valuePtr->next;
2747 break;
2748 }
2749 }
2750 }
2751 } else {
2752 prevPtr = NULL;
2753 for (valuePtr = nodePtr->values; valuePtr != NULL;
2754 valuePtr = valuePtr->next) {
2755 if (valuePtr == value) {
2756 break;
2757 }
2758 prevPtr = valuePtr;
2759 }
2760 if (valuePtr == NULL) {
2761 return TCL_ERROR; /* Can't find value in list. */
2762 }
2763 if (prevPtr == NULL) {
2764 nodePtr->values = valuePtr->next;
2765 } else {
2766 prevPtr->next = valuePtr->next;
2767 }
2768 }
2769 nodePtr->nValues--;
2770 FreeValue(nodePtr, valuePtr);
2771 return TCL_OK;
2772}
2773
2774/*
2775 *----------------------------------------------------------------------
2776 *
2777 * TreeDestroyValues --
2778 *
2779 * Free up everything associated with a hash table except for
2780 * the record for the table itself.
2781 *
2782 * Results:
2783 * None.
2784 *
2785 * Side effects:
2786 * The hash table is no longer useable.
2787 *
2788 *----------------------------------------------------------------------
2789 */
2790static void
2791TreeDestroyValues(Node *nodePtr)
2792{
2793 register Value *valuePtr;
2794 Value *nextPtr;
2795
2796 /*
2797 * Free up all the entries in the table.
2798 */
2799 if (nodePtr->values != NULL) {
2800 return;
2801 }
2802 if (nodePtr->logSize > 0) {
2803 Value **buckets;
2804 int nBuckets;
2805 int i;
2806
2807 buckets = (Value **)nodePtr->values;
2808 nBuckets = (1 << nodePtr->logSize);
2809 for (i = 0; i < nBuckets; i++) {
2810 for (valuePtr = buckets[i]; valuePtr != NULL; valuePtr = nextPtr) {
2811 nextPtr = valuePtr->next;
2812 FreeValue(nodePtr, valuePtr);
2813 }
2814 }
2815 Blt_Free(buckets);
2816 } else {
2817 for (valuePtr = nodePtr->values; valuePtr != NULL; valuePtr = nextPtr) {
2818 nextPtr = valuePtr->next;
2819 FreeValue(nodePtr, valuePtr);
2820 }
2821 }
2822 nodePtr->values = NULL;
2823 nodePtr->nValues = 0;
2824 nodePtr->logSize = 0;
2825}
2826
2827/*
2828 *----------------------------------------------------------------------
2829 *
2830 * TreeFirstValue --
2831 *
2832 * Locate the first entry in a hash table and set up a record
2833 * that can be used to step through all the remaining entries
2834 * of the table.
2835 *
2836 * Results:
2837 * The return value is a pointer to the first value in tablePtr,
2838 * or NULL if tablePtr has no entries in it. The memory at
2839 * *searchPtr is initialized so that subsequent calls to
2840 * Blt_TreeNextValue will return all of the values in the table,
2841 * one at a time.
2842 *
2843 * Side effects:
2844 * None.
2845 *
2846 *----------------------------------------------------------------------
2847 */
2848static Value *
2849TreeFirstValue(
2850 Node *nodePtr,
2851 Blt_TreeKeySearch *searchPtr) /* Place to store information about
2852 * progress through the table. */
2853{
2854 searchPtr->node = nodePtr;
2855 searchPtr->nextIndex = 0;
2856 if (nodePtr->logSize > 0) {
2857 searchPtr->nextValue = NULL;
2858 } else {
2859 searchPtr->nextValue = nodePtr->values;
2860 }
2861 return TreeNextValue(searchPtr);
2862}
2863
2864/*
2865 *----------------------------------------------------------------------
2866 *
2867 * TreeNextValue --
2868 *
2869 * Once a hash table enumeration has been initiated by calling
2870 * Blt_TreeFirstValue, this procedure may be called to return
2871 * successive elements of the table.
2872 *
2873 * Results:
2874 * The return value is the next entry in the hash table being
2875 * enumerated, or NULL if the end of the table is reached.
2876 *
2877 * Side effects:
2878 * None.
2879 *
2880 *----------------------------------------------------------------------
2881 */
2882static Value *
2883TreeNextValue(
2884 Blt_TreeKeySearch *searchPtr) /* Place to store information about
2885 * progress through the table. Must
2886 * have been initialized by calling
2887 * Blt_TreeFirstValue. */
2888{
2889 Value *valuePtr;
2890
2891 if (searchPtr->node->logSize > 0) {
2892 size_t nBuckets;
2893 Value **buckets;
2894
2895 nBuckets = (1 << searchPtr->node->logSize);
2896 buckets = (Value **)searchPtr->node->values;
2897 while (searchPtr->nextValue == NULL) {
2898 if (searchPtr->nextIndex >= nBuckets) {
2899 return NULL;
2900 }
2901 searchPtr->nextValue = buckets[searchPtr->nextIndex];
2902 searchPtr->nextIndex++;
2903 }
2904 }
2905 valuePtr = searchPtr->nextValue;
2906 if (valuePtr != NULL) {
2907 searchPtr->nextValue = valuePtr->next;
2908 }
2909 return valuePtr;
2910}
2911
2912/*
2913 *----------------------------------------------------------------------
2914 *
2915 * TreeFindValue --
2916 *
2917 * Given a hash table with one-word keys, and a one-word key, find
2918 * the entry with a matching key.
2919 *
2920 * Results:
2921 * The return value is a token for the matching entry in the
2922 * hash table, or NULL if there was no matching entry.
2923 *
2924 * Side effects:
2925 * None.
2926 *
2927 *----------------------------------------------------------------------
2928 */
2929static Value *
2930TreeFindValue(
2931 Node *nodePtr,
2932 Blt_TreeKey key) /* Key to use to find matching entry. */
2933{
2934 register Value *valuePtr;
2935 Value *bucket;
2936
2937 if (nodePtr->logSize > 0) {
2938 unsigned int downshift;
2939 unsigned long mask;
2940
2941 mask = (1 << nodePtr->logSize) - 1;
2942 downshift = DOWNSHIFT_START - nodePtr->logSize;
2943 bucket = ((Value **)(nodePtr->values))[RANDOM_INDEX((void *)key)];
2944 } else {
2945 bucket = nodePtr->values; /* Single chain list. */
2946 }
2947 /*
2948 * Search all of the entries in the appropriate bucket.
2949 */
2950 for (valuePtr = bucket; valuePtr != NULL; valuePtr = valuePtr->next) {
2951 if (valuePtr->key == key) {
2952 return valuePtr;
2953 }
2954 }
2955 return NULL;
2956}
2957
2958/*
2959 *----------------------------------------------------------------------
2960 *
2961 * Blt_TreeCreateValue --
2962 *
2963 * Find the value with a matching key. If there is no matching
2964 * value, then create a new one.
2965 *
2966 * Results:
2967 * The return value is a pointer to the matching value. If this
2968 * is a newly-created value, then *newPtr will be set to a non-zero
2969 * value; otherwise *newPtr will be set to 0.
2970 *
2971 * Side effects:
2972 * A new value may be added to the hash table.
2973 *
2974 *----------------------------------------------------------------------
2975 */
2976static Value *
2977TreeCreateValue(
2978 Node *nodePtr,
2979 Blt_TreeKey key, /* Key to use to find or create matching
2980 * entry. */
2981 int *newPtr) /* Store info here telling whether a new
2982 * entry was created. */
2983{
2984 register Value *valuePtr;
2985
2986 /*
2987 * Check if there as so many values that storage should be
2988 * converted from a hash table instead of a list.
2989 */
2990 if ((nodePtr->logSize == 0) && (nodePtr->nValues > MAX_LIST_VALUES)) {
2991 ConvertValues(nodePtr);
2992 }
2993 if (nodePtr->logSize > 0) {
2994 Value **bucketPtr;
2995 size_t nBuckets;
2996 unsigned int downshift;
2997 unsigned long mask;
2998
2999 nBuckets = (1 << nodePtr->logSize);
3000 mask = nBuckets - 1;
3001 downshift = DOWNSHIFT_START - nodePtr->logSize;
3002 bucketPtr = (Value **)nodePtr->values + RANDOM_INDEX((void *)key);
3003
3004 *newPtr = FALSE;
3005 for (valuePtr = *bucketPtr; valuePtr != NULL;
3006 valuePtr = valuePtr->next) {
3007 if (valuePtr->key == key) {
3008 return valuePtr;
3009 }
3010 }
3011
3012 /* Value not found. Add a new value to the bucket. */
3013 *newPtr = TRUE;
3014 valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
3015 sizeof(Value));
3016 valuePtr->key = key;
3017 valuePtr->owner = NULL;
3018 valuePtr->next = *bucketPtr;
3019 valuePtr->objPtr = NULL;
3020 *bucketPtr = valuePtr;
3021 nodePtr->nValues++;
3022
3023 /*
3024 * If the table has exceeded a decent size, rebuild it with many
3025 * more buckets.
3026 */
3027 if ((unsigned int)nodePtr->nValues >= (nBuckets * 3)) {
3028 RebuildTable(nodePtr);
3029 }
3030 } else {
3031 Value *prevPtr;
3032
3033 prevPtr = NULL;
3034 *newPtr = FALSE;
3035 for (valuePtr = nodePtr->values; valuePtr != NULL;
3036 valuePtr = valuePtr->next) {
3037 if (valuePtr->key == key) {
3038 return valuePtr;
3039 }
3040 prevPtr = valuePtr;
3041 }
3042 /* Value not found. Add a new value to the list. */
3043 *newPtr = TRUE;
3044 valuePtr = Blt_PoolAllocItem(nodePtr->treeObject->valuePool,
3045 sizeof(Value));
3046 valuePtr->key = key;
3047 valuePtr->owner = NULL;
3048 valuePtr->next = NULL;
3049 valuePtr->objPtr = NULL;
3050 if (prevPtr == NULL) {
3051 nodePtr->values = valuePtr;
3052 } else {
3053 prevPtr->next = valuePtr;
3054 }
3055 nodePtr->nValues++;
3056 }
3057 return valuePtr;
3058}
3059
3060#endif /* NO_TREE */
Note: See TracBrowser for help on using the repository browser.