1/* 2 * tkTextBTree.c -- 3 * 4 * This file contains code that manages the B-tree representation 5 * of text for Tk's text widget and implements character and 6 * toggle segment types. 7 * 8 * Copyright (c) 1992-1994 The Regents of the University of California. 9 * Copyright (c) 1994-1995 Sun Microsystems, Inc. 10 * 11 * See the file "license.terms" for information on usage and redistribution 12 * of this file, and for a DISCLAIMER OF ALL WARRANTIES. 13 * 14 * RCS: @(#) $Id: tkTextBTree.c,v 1.6.2.3 2006/09/10 17:07:35 das Exp $ 15 */ 16 17#include "tkInt.h" 18#include "tkPort.h" 19#include "tkText.h" 20 21/* 22 * The data structure below keeps summary information about one tag as part 23 * of the tag information in a node. 24 */ 25 26typedef struct Summary { 27 TkTextTag *tagPtr; /* Handle for tag. */ 28 int toggleCount; /* Number of transitions into or 29 * out of this tag that occur in 30 * the subtree rooted at this node. */ 31 struct Summary *nextPtr; /* Next in list of all tags for same 32 * node, or NULL if at end of list. */ 33} Summary; 34 35/* 36 * The data structure below defines a node in the B-tree. 37 */ 38 39typedef struct Node { 40 struct Node *parentPtr; /* Pointer to parent node, or NULL if 41 * this is the root. */ 42 struct Node *nextPtr; /* Next in list of siblings with the 43 * same parent node, or NULL for end 44 * of list. */ 45 Summary *summaryPtr; /* First in malloc-ed list of info 46 * about tags in this subtree (NULL if 47 * no tag info in the subtree). */ 48 int level; /* Level of this node in the B-tree. 49 * 0 refers to the bottom of the tree 50 * (children are lines, not nodes). */ 51 union { /* First in linked list of children. */ 52 struct Node *nodePtr; /* Used if level > 0. */ 53 TkTextLine *linePtr; /* Used if level == 0. */ 54 } children; 55 int numChildren; /* Number of children of this node. */ 56 int numLines; /* Total number of lines (leaves) in 57 * the subtree rooted here. */ 58} Node; 59 60/* 61 * Upper and lower bounds on how many children a node may have: 62 * rebalance when either of these limits is exceeded. MAX_CHILDREN 63 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2. 64 */ 65 66#define MAX_CHILDREN 12 67#define MIN_CHILDREN 6 68 69/* 70 * The data structure below defines an entire B-tree. 71 */ 72 73typedef struct BTree { 74 Node *rootPtr; /* Pointer to root of B-tree. */ 75 TkText *textPtr; /* Used to find tagTable in consistency 76 * checking code */ 77} BTree; 78 79/* 80 * The structure below is used to pass information between 81 * TkBTreeGetTags and IncCount: 82 */ 83 84typedef struct TagInfo { 85 int numTags; /* Number of tags for which there 86 * is currently information in 87 * tags and counts. */ 88 int arraySize; /* Number of entries allocated for 89 * tags and counts. */ 90 TkTextTag **tagPtrs; /* Array of tags seen so far. 91 * Malloc-ed. */ 92 int *counts; /* Toggle count (so far) for each 93 * entry in tags. Malloc-ed. */ 94} TagInfo; 95 96/* 97 * Variable that indicates whether to enable consistency checks for 98 * debugging. 99 */ 100 101int tkBTreeDebug = 0; 102 103/* 104 * Macros that determine how much space to allocate for new segments: 105 */ 106 107#define CSEG_SIZE(chars) ((unsigned) (Tk_Offset(TkTextSegment, body) \ 108 + 1 + (chars))) 109#define TSEG_SIZE ((unsigned) (Tk_Offset(TkTextSegment, body) \ 110 + sizeof(TkTextToggle))) 111 112/* 113 * Forward declarations for procedures defined in this file: 114 */ 115 116static void ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr, 117 TkTextTag *tagPtr, int delta)); 118static void CharCheckProc _ANSI_ARGS_((TkTextSegment *segPtr, 119 TkTextLine *linePtr)); 120static int CharDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr, 121 TkTextLine *linePtr, int treeGone)); 122static TkTextSegment * CharCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr, 123 TkTextLine *linePtr)); 124static TkTextSegment * CharSplitProc _ANSI_ARGS_((TkTextSegment *segPtr, 125 int index)); 126static void CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr)); 127static void CleanupLine _ANSI_ARGS_((TkTextLine *linePtr)); 128static void DeleteSummaries _ANSI_ARGS_((Summary *tagPtr)); 129static void DestroyNode _ANSI_ARGS_((Node *nodePtr)); 130static TkTextSegment * FindTagEnd _ANSI_ARGS_((TkTextBTree tree, 131 TkTextTag *tagPtr, TkTextIndex *indexPtr)); 132static void IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc, 133 TagInfo *tagInfoPtr)); 134static void Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr)); 135static void RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr)); 136static TkTextSegment * SplitSeg _ANSI_ARGS_((TkTextIndex *indexPtr)); 137static void ToggleCheckProc _ANSI_ARGS_((TkTextSegment *segPtr, 138 TkTextLine *linePtr)); 139static TkTextSegment * ToggleCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr, 140 TkTextLine *linePtr)); 141static int ToggleDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr, 142 TkTextLine *linePtr, int treeGone)); 143static void ToggleLineChangeProc _ANSI_ARGS_((TkTextSegment *segPtr, 144 TkTextLine *linePtr)); 145static TkTextSegment * FindTagStart _ANSI_ARGS_((TkTextBTree tree, 146 TkTextTag *tagPtr, TkTextIndex *indexPtr)); 147 148/* 149 * Type record for character segments: 150 */ 151 152Tk_SegType tkTextCharType = { 153 "character", /* name */ 154 0, /* leftGravity */ 155 CharSplitProc, /* splitProc */ 156 CharDeleteProc, /* deleteProc */ 157 CharCleanupProc, /* cleanupProc */ 158 (Tk_SegLineChangeProc *) NULL, /* lineChangeProc */ 159 TkTextCharLayoutProc, /* layoutProc */ 160 CharCheckProc /* checkProc */ 161}; 162 163/* 164 * Type record for segments marking the beginning of a tagged 165 * range: 166 */ 167 168Tk_SegType tkTextToggleOnType = { 169 "toggleOn", /* name */ 170 0, /* leftGravity */ 171 (Tk_SegSplitProc *) NULL, /* splitProc */ 172 ToggleDeleteProc, /* deleteProc */ 173 ToggleCleanupProc, /* cleanupProc */ 174 ToggleLineChangeProc, /* lineChangeProc */ 175 (Tk_SegLayoutProc *) NULL, /* layoutProc */ 176 ToggleCheckProc /* checkProc */ 177}; 178 179/* 180 * Type record for segments marking the end of a tagged 181 * range: 182 */ 183 184Tk_SegType tkTextToggleOffType = { 185 "toggleOff", /* name */ 186 1, /* leftGravity */ 187 (Tk_SegSplitProc *) NULL, /* splitProc */ 188 ToggleDeleteProc, /* deleteProc */ 189 ToggleCleanupProc, /* cleanupProc */ 190 ToggleLineChangeProc, /* lineChangeProc */ 191 (Tk_SegLayoutProc *) NULL, /* layoutProc */ 192 ToggleCheckProc /* checkProc */ 193}; 194 195/* 196 *---------------------------------------------------------------------- 197 * 198 * TkBTreeCreate -- 199 * 200 * This procedure is called to create a new text B-tree. 201 * 202 * Results: 203 * The return value is a pointer to a new B-tree containing 204 * one line with nothing but a newline character. 205 * 206 * Side effects: 207 * Memory is allocated and initialized. 208 * 209 *---------------------------------------------------------------------- 210 */ 211 212TkTextBTree 213TkBTreeCreate(textPtr) 214 TkText *textPtr; 215{ 216 register BTree *treePtr; 217 register Node *rootPtr; 218 register TkTextLine *linePtr, *linePtr2; 219 register TkTextSegment *segPtr; 220 221 /* 222 * The tree will initially have two empty lines. The second line 223 * isn't actually part of the tree's contents, but its presence 224 * makes several operations easier. The tree will have one node, 225 * which is also the root of the tree. 226 */ 227 228 rootPtr = (Node *) ckalloc(sizeof(Node)); 229 linePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine)); 230 linePtr2 = (TkTextLine *) ckalloc(sizeof(TkTextLine)); 231 rootPtr->parentPtr = NULL; 232 rootPtr->nextPtr = NULL; 233 rootPtr->summaryPtr = NULL; 234 rootPtr->level = 0; 235 rootPtr->children.linePtr = linePtr; 236 rootPtr->numChildren = 2; 237 rootPtr->numLines = 2; 238 239 linePtr->parentPtr = rootPtr; 240 linePtr->nextPtr = linePtr2; 241 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1)); 242 linePtr->segPtr = segPtr; 243 segPtr->typePtr = &tkTextCharType; 244 segPtr->nextPtr = NULL; 245 segPtr->size = 1; 246 segPtr->body.chars[0] = '\n'; 247 segPtr->body.chars[1] = 0; 248 249 linePtr2->parentPtr = rootPtr; 250 linePtr2->nextPtr = NULL; 251 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1)); 252 linePtr2->segPtr = segPtr; 253 segPtr->typePtr = &tkTextCharType; 254 segPtr->nextPtr = NULL; 255 segPtr->size = 1; 256 segPtr->body.chars[0] = '\n'; 257 segPtr->body.chars[1] = 0; 258 259 treePtr = (BTree *) ckalloc(sizeof(BTree)); 260 treePtr->rootPtr = rootPtr; 261 treePtr->textPtr = textPtr; 262 263 return (TkTextBTree) treePtr; 264} 265 266/* 267 *---------------------------------------------------------------------- 268 * 269 * TkBTreeDestroy -- 270 * 271 * Delete a B-tree, recycling all of the storage it contains. 272 * 273 * Results: 274 * The tree given by treePtr is deleted. TreePtr should never 275 * again be used. 276 * 277 * Side effects: 278 * Memory is freed. 279 * 280 *---------------------------------------------------------------------- 281 */ 282 283void 284TkBTreeDestroy(tree) 285 TkTextBTree tree; /* Pointer to tree to delete. */ 286{ 287 BTree *treePtr = (BTree *) tree; 288 289 DestroyNode(treePtr->rootPtr); 290 ckfree((char *) treePtr); 291} 292 293/* 294 *---------------------------------------------------------------------- 295 * 296 * DestroyNode -- 297 * 298 * This is a recursive utility procedure used during the deletion 299 * of a B-tree. 300 * 301 * Results: 302 * None. 303 * 304 * Side effects: 305 * All the storage for nodePtr and its descendants is freed. 306 * 307 *---------------------------------------------------------------------- 308 */ 309 310static void 311DestroyNode(nodePtr) 312 register Node *nodePtr; 313{ 314 if (nodePtr->level == 0) { 315 TkTextLine *linePtr; 316 TkTextSegment *segPtr; 317 318 while (nodePtr->children.linePtr != NULL) { 319 linePtr = nodePtr->children.linePtr; 320 nodePtr->children.linePtr = linePtr->nextPtr; 321 while (linePtr->segPtr != NULL) { 322 segPtr = linePtr->segPtr; 323 linePtr->segPtr = segPtr->nextPtr; 324 (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1); 325 } 326 ckfree((char *) linePtr); 327 } 328 } else { 329 register Node *childPtr; 330 331 while (nodePtr->children.nodePtr != NULL) { 332 childPtr = nodePtr->children.nodePtr; 333 nodePtr->children.nodePtr = childPtr->nextPtr; 334 DestroyNode(childPtr); 335 } 336 } 337 DeleteSummaries(nodePtr->summaryPtr); 338 ckfree((char *) nodePtr); 339} 340 341/* 342 *---------------------------------------------------------------------- 343 * 344 * DeleteSummaries -- 345 * 346 * Free up all of the memory in a list of tag summaries associated 347 * with a node. 348 * 349 * Results: 350 * None. 351 * 352 * Side effects: 353 * Storage is released. 354 * 355 *---------------------------------------------------------------------- 356 */ 357 358static void 359DeleteSummaries(summaryPtr) 360 register Summary *summaryPtr; /* First in list of node's tag 361 * summaries. */ 362{ 363 register Summary *nextPtr; 364 while (summaryPtr != NULL) { 365 nextPtr = summaryPtr->nextPtr; 366 ckfree((char *) summaryPtr); 367 summaryPtr = nextPtr; 368 } 369} 370 371/* 372 *---------------------------------------------------------------------- 373 * 374 * TkBTreeInsertChars -- 375 * 376 * Insert characters at a given position in a B-tree. 377 * 378 * Results: 379 * None. 380 * 381 * Side effects: 382 * Characters are added to the B-tree at the given position. 383 * If the string contains newlines, new lines will be added, 384 * which could cause the structure of the B-tree to change. 385 * 386 *---------------------------------------------------------------------- 387 */ 388 389void 390TkBTreeInsertChars(indexPtr, string) 391 register TkTextIndex *indexPtr; /* Indicates where to insert text. 392 * When the procedure returns, this 393 * index is no longer valid because 394 * of changes to the segment 395 * structure. */ 396 CONST char *string; /* Pointer to bytes to insert (may 397 * contain newlines, must be null- 398 * terminated). */ 399{ 400 register Node *nodePtr; 401 register TkTextSegment *prevPtr; /* The segment just before the first 402 * new segment (NULL means new segment 403 * is at beginning of line). */ 404 TkTextSegment *curPtr; /* Current segment; new characters 405 * are inserted just after this one. 406 * NULL means insert at beginning of 407 * line. */ 408 TkTextLine *linePtr; /* Current line (new segments are 409 * added to this line). */ 410 register TkTextSegment *segPtr; 411 TkTextLine *newLinePtr; 412 int chunkSize; /* # characters in current chunk. */ 413 register CONST char *eol; /* Pointer to character just after last 414 * one in current chunk. */ 415 int changeToLineCount; /* Counts change to total number of 416 * lines in file. */ 417 418 prevPtr = SplitSeg(indexPtr); 419 linePtr = indexPtr->linePtr; 420 curPtr = prevPtr; 421 422 /* 423 * Chop the string up into lines and create a new segment for 424 * each line, plus a new line for the leftovers from the 425 * previous line. 426 */ 427 428 changeToLineCount = 0; 429 while (*string != 0) { 430 for (eol = string; *eol != 0; eol++) { 431 if (*eol == '\n') { 432 eol++; 433 break; 434 } 435 } 436 chunkSize = eol-string; 437 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(chunkSize)); 438 segPtr->typePtr = &tkTextCharType; 439 if (curPtr == NULL) { 440 segPtr->nextPtr = linePtr->segPtr; 441 linePtr->segPtr = segPtr; 442 } else { 443 segPtr->nextPtr = curPtr->nextPtr; 444 curPtr->nextPtr = segPtr; 445 } 446 segPtr->size = chunkSize; 447 strncpy(segPtr->body.chars, string, (size_t) chunkSize); 448 segPtr->body.chars[chunkSize] = 0; 449 450 if (eol[-1] != '\n') { 451 break; 452 } 453 454 /* 455 * The chunk ended with a newline, so create a new TkTextLine 456 * and move the remainder of the old line to it. 457 */ 458 459 newLinePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine)); 460 newLinePtr->parentPtr = linePtr->parentPtr; 461 newLinePtr->nextPtr = linePtr->nextPtr; 462 linePtr->nextPtr = newLinePtr; 463 newLinePtr->segPtr = segPtr->nextPtr; 464 segPtr->nextPtr = NULL; 465 linePtr = newLinePtr; 466 curPtr = NULL; 467 changeToLineCount++; 468 469 string = eol; 470 } 471 472 /* 473 * Cleanup the starting line for the insertion, plus the ending 474 * line if it's different. 475 */ 476 477 CleanupLine(indexPtr->linePtr); 478 if (linePtr != indexPtr->linePtr) { 479 CleanupLine(linePtr); 480 } 481 482 /* 483 * Increment the line counts in all the parent nodes of the insertion 484 * point, then rebalance the tree if necessary. 485 */ 486 487 for (nodePtr = linePtr->parentPtr ; nodePtr != NULL; 488 nodePtr = nodePtr->parentPtr) { 489 nodePtr->numLines += changeToLineCount; 490 } 491 nodePtr = linePtr->parentPtr; 492 nodePtr->numChildren += changeToLineCount; 493 if (nodePtr->numChildren > MAX_CHILDREN) { 494 Rebalance((BTree *) indexPtr->tree, nodePtr); 495 } 496 497 if (tkBTreeDebug) { 498 TkBTreeCheck(indexPtr->tree); 499 } 500} 501 502/* 503 *-------------------------------------------------------------- 504 * 505 * SplitSeg -- 506 * 507 * This procedure is called before adding or deleting 508 * segments. It does three things: (a) it finds the segment 509 * containing indexPtr; (b) if there are several such 510 * segments (because some segments have zero length) then 511 * it picks the first segment that does not have left 512 * gravity; (c) if the index refers to the middle of 513 * a segment then it splits the segment so that the 514 * index now refers to the beginning of a segment. 515 * 516 * Results: 517 * The return value is a pointer to the segment just 518 * before the segment corresponding to indexPtr (as 519 * described above). If the segment corresponding to 520 * indexPtr is the first in its line then the return 521 * value is NULL. 522 * 523 * Side effects: 524 * The segment referred to by indexPtr is split unless 525 * indexPtr refers to its first character. 526 * 527 *-------------------------------------------------------------- 528 */ 529 530static TkTextSegment * 531SplitSeg(indexPtr) 532 TkTextIndex *indexPtr; /* Index identifying position 533 * at which to split a segment. */ 534{ 535 TkTextSegment *prevPtr, *segPtr; 536 int count; 537 538 for (count = indexPtr->byteIndex, prevPtr = NULL, 539 segPtr = indexPtr->linePtr->segPtr; segPtr != NULL; 540 count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) { 541 if (segPtr->size > count) { 542 if (count == 0) { 543 return prevPtr; 544 } 545 segPtr = (*segPtr->typePtr->splitProc)(segPtr, count); 546 if (prevPtr == NULL) { 547 indexPtr->linePtr->segPtr = segPtr; 548 } else { 549 prevPtr->nextPtr = segPtr; 550 } 551 return segPtr; 552 } else if ((segPtr->size == 0) && (count == 0) 553 && !segPtr->typePtr->leftGravity) { 554 return prevPtr; 555 } 556 } 557 panic("SplitSeg reached end of line!"); 558 return NULL; 559} 560 561/* 562 *-------------------------------------------------------------- 563 * 564 * CleanupLine -- 565 * 566 * This procedure is called after modifications have been 567 * made to a line. It scans over all of the segments in 568 * the line, giving each a chance to clean itself up, e.g. 569 * by merging with the following segments, updating internal 570 * information, etc. 571 * 572 * Results: 573 * None. 574 * 575 * Side effects: 576 * Depends on what the segment-specific cleanup procedures do. 577 * 578 *-------------------------------------------------------------- 579 */ 580 581static void 582CleanupLine(linePtr) 583 TkTextLine *linePtr; /* Line to be cleaned up. */ 584{ 585 TkTextSegment *segPtr, **prevPtrPtr; 586 int anyChanges; 587 588 /* 589 * Make a pass over all of the segments in the line, giving each 590 * a chance to clean itself up. This could potentially change 591 * the structure of the line, e.g. by merging two segments 592 * together or having two segments cancel themselves; if so, 593 * then repeat the whole process again, since the first structure 594 * change might make other structure changes possible. Repeat 595 * until eventually there are no changes. 596 */ 597 598 while (1) { 599 anyChanges = 0; 600 for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr; 601 segPtr != NULL; 602 prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) { 603 if (segPtr->typePtr->cleanupProc != NULL) { 604 *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr); 605 if (segPtr != *prevPtrPtr) { 606 anyChanges = 1; 607 } 608 } 609 } 610 if (!anyChanges) { 611 break; 612 } 613 } 614} 615 616/* 617 *---------------------------------------------------------------------- 618 * 619 * TkBTreeDeleteChars -- 620 * 621 * Delete a range of characters from a B-tree. The caller 622 * must make sure that the final newline of the B-tree is 623 * never deleted. 624 * 625 * Results: 626 * None. 627 * 628 * Side effects: 629 * Information is deleted from the B-tree. This can cause the 630 * internal structure of the B-tree to change. Note: because 631 * of changes to the B-tree structure, the indices pointed 632 * to by index1Ptr and index2Ptr should not be used after this 633 * procedure returns. 634 * 635 *---------------------------------------------------------------------- 636 */ 637 638void 639TkBTreeDeleteChars(index1Ptr, index2Ptr) 640 register TkTextIndex *index1Ptr; /* Indicates first character that is 641 * to be deleted. */ 642 register TkTextIndex *index2Ptr; /* Indicates character just after the 643 * last one that is to be deleted. */ 644{ 645 TkTextSegment *prevPtr; /* The segment just before the start 646 * of the deletion range. */ 647 TkTextSegment *lastPtr; /* The segment just after the end 648 * of the deletion range. */ 649 TkTextSegment *segPtr, *nextPtr; 650 TkTextLine *curLinePtr; 651 Node *curNodePtr, *nodePtr; 652 653 /* 654 * Tricky point: split at index2Ptr first; otherwise the split 655 * at index2Ptr may invalidate segPtr and/or prevPtr. 656 */ 657 658 lastPtr = SplitSeg(index2Ptr); 659 if (lastPtr != NULL) { 660 lastPtr = lastPtr->nextPtr; 661 } else { 662 lastPtr = index2Ptr->linePtr->segPtr; 663 } 664 prevPtr = SplitSeg(index1Ptr); 665 if (prevPtr != NULL) { 666 segPtr = prevPtr->nextPtr; 667 prevPtr->nextPtr = lastPtr; 668 } else { 669 segPtr = index1Ptr->linePtr->segPtr; 670 index1Ptr->linePtr->segPtr = lastPtr; 671 } 672 673 /* 674 * Delete all of the segments between prevPtr and lastPtr. 675 */ 676 677 curLinePtr = index1Ptr->linePtr; 678 curNodePtr = curLinePtr->parentPtr; 679 while (segPtr != lastPtr) { 680 if (segPtr == NULL) { 681 TkTextLine *nextLinePtr; 682 683 /* 684 * We just ran off the end of a line. First find the 685 * next line, then go back to the old line and delete it 686 * (unless it's the starting line for the range). 687 */ 688 689 nextLinePtr = TkBTreeNextLine(curLinePtr); 690 if (curLinePtr != index1Ptr->linePtr) { 691 if (curNodePtr == index1Ptr->linePtr->parentPtr) { 692 index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr; 693 } else { 694 curNodePtr->children.linePtr = curLinePtr->nextPtr; 695 } 696 for (nodePtr = curNodePtr; nodePtr != NULL; 697 nodePtr = nodePtr->parentPtr) { 698 nodePtr->numLines--; 699 } 700 curNodePtr->numChildren--; 701 ckfree((char *) curLinePtr); 702 } 703 curLinePtr = nextLinePtr; 704 segPtr = curLinePtr->segPtr; 705 706 /* 707 * If the node is empty then delete it and its parents, 708 * recursively upwards until a non-empty node is found. 709 */ 710 711 while (curNodePtr->numChildren == 0) { 712 Node *parentPtr; 713 714 parentPtr = curNodePtr->parentPtr; 715 if (parentPtr->children.nodePtr == curNodePtr) { 716 parentPtr->children.nodePtr = curNodePtr->nextPtr; 717 } else { 718 Node *prevNodePtr = parentPtr->children.nodePtr; 719 while (prevNodePtr->nextPtr != curNodePtr) { 720 prevNodePtr = prevNodePtr->nextPtr; 721 } 722 prevNodePtr->nextPtr = curNodePtr->nextPtr; 723 } 724 parentPtr->numChildren--; 725 ckfree((char *) curNodePtr); 726 curNodePtr = parentPtr; 727 } 728 curNodePtr = curLinePtr->parentPtr; 729 continue; 730 } 731 732 nextPtr = segPtr->nextPtr; 733 if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) { 734 /* 735 * This segment refuses to die. Move it to prevPtr and 736 * advance prevPtr if the segment has left gravity. 737 */ 738 739 if (prevPtr == NULL) { 740 segPtr->nextPtr = index1Ptr->linePtr->segPtr; 741 index1Ptr->linePtr->segPtr = segPtr; 742 } else { 743 segPtr->nextPtr = prevPtr->nextPtr; 744 prevPtr->nextPtr = segPtr; 745 } 746 if (segPtr->typePtr->leftGravity) { 747 prevPtr = segPtr; 748 } 749 } 750 segPtr = nextPtr; 751 } 752 753 /* 754 * If the beginning and end of the deletion range are in different 755 * lines, join the two lines together and discard the ending line. 756 */ 757 758 if (index1Ptr->linePtr != index2Ptr->linePtr) { 759 TkTextLine *prevLinePtr; 760 761 for (segPtr = lastPtr; segPtr != NULL; 762 segPtr = segPtr->nextPtr) { 763 if (segPtr->typePtr->lineChangeProc != NULL) { 764 (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr); 765 } 766 } 767 curNodePtr = index2Ptr->linePtr->parentPtr; 768 for (nodePtr = curNodePtr; nodePtr != NULL; 769 nodePtr = nodePtr->parentPtr) { 770 nodePtr->numLines--; 771 } 772 curNodePtr->numChildren--; 773 prevLinePtr = curNodePtr->children.linePtr; 774 if (prevLinePtr == index2Ptr->linePtr) { 775 curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr; 776 } else { 777 while (prevLinePtr->nextPtr != index2Ptr->linePtr) { 778 prevLinePtr = prevLinePtr->nextPtr; 779 } 780 prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr; 781 } 782 ckfree((char *) index2Ptr->linePtr); 783 Rebalance((BTree *) index2Ptr->tree, curNodePtr); 784 } 785 786 /* 787 * Cleanup the segments in the new line. 788 */ 789 790 CleanupLine(index1Ptr->linePtr); 791 792 /* 793 * Lastly, rebalance the first node of the range. 794 */ 795 796 Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr); 797 if (tkBTreeDebug) { 798 TkBTreeCheck(index1Ptr->tree); 799 } 800} 801 802/* 803 *---------------------------------------------------------------------- 804 * 805 * TkBTreeFindLine -- 806 * 807 * Find a particular line in a B-tree based on its line number. 808 * 809 * Results: 810 * The return value is a pointer to the line structure for the 811 * line whose index is "line", or NULL if no such line exists. 812 * 813 * Side effects: 814 * None. 815 * 816 *---------------------------------------------------------------------- 817 */ 818 819TkTextLine * 820TkBTreeFindLine(tree, line) 821 TkTextBTree tree; /* B-tree in which to find line. */ 822 int line; /* Index of desired line. */ 823{ 824 BTree *treePtr = (BTree *) tree; 825 register Node *nodePtr; 826 register TkTextLine *linePtr; 827 int linesLeft; 828 829 nodePtr = treePtr->rootPtr; 830 linesLeft = line; 831 if ((line < 0) || (line >= nodePtr->numLines)) { 832 return NULL; 833 } 834 835 /* 836 * Work down through levels of the tree until a node is found at 837 * level 0. 838 */ 839 840 while (nodePtr->level != 0) { 841 for (nodePtr = nodePtr->children.nodePtr; 842 nodePtr->numLines <= linesLeft; 843 nodePtr = nodePtr->nextPtr) { 844 if (nodePtr == NULL) { 845 panic("TkBTreeFindLine ran out of nodes"); 846 } 847 linesLeft -= nodePtr->numLines; 848 } 849 } 850 851 /* 852 * Work through the lines attached to the level-0 node. 853 */ 854 855 for (linePtr = nodePtr->children.linePtr; linesLeft > 0; 856 linePtr = linePtr->nextPtr) { 857 if (linePtr == NULL) { 858 panic("TkBTreeFindLine ran out of lines"); 859 } 860 linesLeft -= 1; 861 } 862 return linePtr; 863} 864 865/* 866 *---------------------------------------------------------------------- 867 * 868 * TkBTreeNextLine -- 869 * 870 * Given an existing line in a B-tree, this procedure locates the 871 * next line in the B-tree. This procedure is used for scanning 872 * through the B-tree. 873 * 874 * Results: 875 * The return value is a pointer to the line that immediately 876 * follows linePtr, or NULL if there is no such line. 877 * 878 * Side effects: 879 * None. 880 * 881 *---------------------------------------------------------------------- 882 */ 883 884TkTextLine * 885TkBTreeNextLine(linePtr) 886 register TkTextLine *linePtr; /* Pointer to existing line in 887 * B-tree. */ 888{ 889 register Node *nodePtr; 890 891 if (linePtr->nextPtr != NULL) { 892 return linePtr->nextPtr; 893 } 894 895 /* 896 * This was the last line associated with the particular parent node. 897 * Search up the tree for the next node, then search down from that 898 * node to find the first line. 899 */ 900 901 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) { 902 if (nodePtr->nextPtr != NULL) { 903 nodePtr = nodePtr->nextPtr; 904 break; 905 } 906 if (nodePtr->parentPtr == NULL) { 907 return (TkTextLine *) NULL; 908 } 909 } 910 while (nodePtr->level > 0) { 911 nodePtr = nodePtr->children.nodePtr; 912 } 913 return nodePtr->children.linePtr; 914} 915 916/* 917 *---------------------------------------------------------------------- 918 * 919 * TkBTreePreviousLine -- 920 * 921 * Given an existing line in a B-tree, this procedure locates the 922 * previous line in the B-tree. This procedure is used for scanning 923 * through the B-tree in the reverse direction. 924 * 925 * Results: 926 * The return value is a pointer to the line that immediately 927 * preceeds linePtr, or NULL if there is no such line. 928 * 929 * Side effects: 930 * None. 931 * 932 *---------------------------------------------------------------------- 933 */ 934 935TkTextLine * 936TkBTreePreviousLine(linePtr) 937 register TkTextLine *linePtr; /* Pointer to existing line in 938 * B-tree. */ 939{ 940 register Node *nodePtr; 941 register Node *node2Ptr; 942 register TkTextLine *prevPtr; 943 944 /* 945 * Find the line under this node just before the starting line. 946 */ 947 prevPtr = linePtr->parentPtr->children.linePtr; /* First line at leaf */ 948 while (prevPtr != linePtr) { 949 if (prevPtr->nextPtr == linePtr) { 950 return prevPtr; 951 } 952 prevPtr = prevPtr->nextPtr; 953 if (prevPtr == (TkTextLine *) NULL) { 954 panic("TkBTreePreviousLine ran out of lines"); 955 } 956 } 957 958 /* 959 * This was the first line associated with the particular parent node. 960 * Search up the tree for the previous node, then search down from that 961 * node to find its last line. 962 */ 963 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) { 964 if (nodePtr == (Node *) NULL || nodePtr->parentPtr == (Node *) NULL) { 965 return (TkTextLine *) NULL; 966 } 967 if (nodePtr != nodePtr->parentPtr->children.nodePtr) { 968 break; 969 } 970 } 971 for (node2Ptr = nodePtr->parentPtr->children.nodePtr; ; 972 node2Ptr = node2Ptr->children.nodePtr) { 973 while (node2Ptr->nextPtr != nodePtr) { 974 node2Ptr = node2Ptr->nextPtr; 975 } 976 if (node2Ptr->level == 0) { 977 break; 978 } 979 nodePtr = (Node *)NULL; 980 } 981 for (prevPtr = node2Ptr->children.linePtr ; ; prevPtr = prevPtr->nextPtr) { 982 if (prevPtr->nextPtr == (TkTextLine *) NULL) { 983 return prevPtr; 984 } 985 } 986} 987 988/* 989 *---------------------------------------------------------------------- 990 * 991 * TkBTreeLineIndex -- 992 * 993 * Given a pointer to a line in a B-tree, return the numerical 994 * index of that line. 995 * 996 * Results: 997 * The result is the index of linePtr within the tree, where 0 998 * corresponds to the first line in the tree. 999 * 1000 * Side effects: 1001 * None. 1002 * 1003 *---------------------------------------------------------------------- 1004 */ 1005 1006int 1007TkBTreeLineIndex(linePtr) 1008 TkTextLine *linePtr; /* Pointer to existing line in 1009 * B-tree. */ 1010{ 1011 register TkTextLine *linePtr2; 1012 register Node *nodePtr, *parentPtr, *nodePtr2; 1013 int index; 1014 1015 /* 1016 * First count how many lines precede this one in its level-0 1017 * node. 1018 */ 1019 1020 nodePtr = linePtr->parentPtr; 1021 index = 0; 1022 for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr; 1023 linePtr2 = linePtr2->nextPtr) { 1024 if (linePtr2 == NULL) { 1025 panic("TkBTreeLineIndex couldn't find line"); 1026 } 1027 index += 1; 1028 } 1029 1030 /* 1031 * Now work up through the levels of the tree one at a time, 1032 * counting how many lines are in nodes preceding the current 1033 * node. 1034 */ 1035 1036 for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL; 1037 nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) { 1038 for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr; 1039 nodePtr2 = nodePtr2->nextPtr) { 1040 if (nodePtr2 == NULL) { 1041 panic("TkBTreeLineIndex couldn't find node"); 1042 } 1043 index += nodePtr2->numLines; 1044 } 1045 } 1046 return index; 1047} 1048 1049/* 1050 *---------------------------------------------------------------------- 1051 * 1052 * TkBTreeLinkSegment -- 1053 * 1054 * This procedure adds a new segment to a B-tree at a given 1055 * location. 1056 * 1057 * Results: 1058 * None. 1059 * 1060 * Side effects: 1061 * SegPtr will be linked into its tree. 1062 * 1063 *---------------------------------------------------------------------- 1064 */ 1065 1066 /* ARGSUSED */ 1067void 1068TkBTreeLinkSegment(segPtr, indexPtr) 1069 TkTextSegment *segPtr; /* Pointer to new segment to be added to 1070 * B-tree. Should be completely initialized 1071 * by caller except for nextPtr field. */ 1072 TkTextIndex *indexPtr; /* Where to add segment: it gets linked 1073 * in just before the segment indicated 1074 * here. */ 1075{ 1076 register TkTextSegment *prevPtr; 1077 1078 prevPtr = SplitSeg(indexPtr); 1079 if (prevPtr == NULL) { 1080 segPtr->nextPtr = indexPtr->linePtr->segPtr; 1081 indexPtr->linePtr->segPtr = segPtr; 1082 } else { 1083 segPtr->nextPtr = prevPtr->nextPtr; 1084 prevPtr->nextPtr = segPtr; 1085 } 1086 CleanupLine(indexPtr->linePtr); 1087 if (tkBTreeDebug) { 1088 TkBTreeCheck(indexPtr->tree); 1089 } 1090} 1091 1092/* 1093 *---------------------------------------------------------------------- 1094 * 1095 * TkBTreeUnlinkSegment -- 1096 * 1097 * This procedure unlinks a segment from its line in a B-tree. 1098 * 1099 * Results: 1100 * None. 1101 * 1102 * Side effects: 1103 * SegPtr will be unlinked from linePtr. The segment itself 1104 * isn't modified by this procedure. 1105 * 1106 *---------------------------------------------------------------------- 1107 */ 1108 1109 /* ARGSUSED */ 1110void 1111TkBTreeUnlinkSegment(tree, segPtr, linePtr) 1112 TkTextBTree tree; /* Tree containing segment. */ 1113 TkTextSegment *segPtr; /* Segment to be unlinked. */ 1114 TkTextLine *linePtr; /* Line that currently contains 1115 * segment. */ 1116{ 1117 register TkTextSegment *prevPtr; 1118 1119 if (linePtr->segPtr == segPtr) { 1120 linePtr->segPtr = segPtr->nextPtr; 1121 } else { 1122 for (prevPtr = linePtr->segPtr; prevPtr->nextPtr != segPtr; 1123 prevPtr = prevPtr->nextPtr) { 1124 /* Empty loop body. */ 1125 } 1126 prevPtr->nextPtr = segPtr->nextPtr; 1127 } 1128 CleanupLine(linePtr); 1129} 1130 1131/* 1132 *---------------------------------------------------------------------- 1133 * 1134 * TkBTreeTag -- 1135 * 1136 * Turn a given tag on or off for a given range of characters in 1137 * a B-tree of text. 1138 * 1139 * Results: 1140 * None. 1141 * 1142 * Side effects: 1143 * The given tag is added to the given range of characters 1144 * in the tree or removed from all those characters, depending 1145 * on the "add" argument. The structure of the btree is modified 1146 * enough that index1Ptr and index2Ptr are no longer valid after 1147 * this procedure returns, and the indexes may be modified by 1148 * this procedure. 1149 * 1150 *---------------------------------------------------------------------- 1151 */ 1152 1153void 1154TkBTreeTag(index1Ptr, index2Ptr, tagPtr, add) 1155 register TkTextIndex *index1Ptr; /* Indicates first character in 1156 * range. */ 1157 register TkTextIndex *index2Ptr; /* Indicates character just after the 1158 * last one in range. */ 1159 TkTextTag *tagPtr; /* Tag to add or remove. */ 1160 int add; /* One means add tag to the given 1161 * range of characters; zero means 1162 * remove the tag from the range. */ 1163{ 1164 TkTextSegment *segPtr, *prevPtr; 1165 TkTextSearch search; 1166 TkTextLine *cleanupLinePtr; 1167 int oldState; 1168 int changed; 1169 1170 /* 1171 * See whether the tag is present at the start of the range. If 1172 * the state doesn't already match what we want then add a toggle 1173 * there. 1174 */ 1175 1176 oldState = TkBTreeCharTagged(index1Ptr, tagPtr); 1177 if ((add != 0) ^ oldState) { 1178 segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE); 1179 segPtr->typePtr = (add) ? &tkTextToggleOnType : &tkTextToggleOffType; 1180 prevPtr = SplitSeg(index1Ptr); 1181 if (prevPtr == NULL) { 1182 segPtr->nextPtr = index1Ptr->linePtr->segPtr; 1183 index1Ptr->linePtr->segPtr = segPtr; 1184 } else { 1185 segPtr->nextPtr = prevPtr->nextPtr; 1186 prevPtr->nextPtr = segPtr; 1187 } 1188 segPtr->size = 0; 1189 segPtr->body.toggle.tagPtr = tagPtr; 1190 segPtr->body.toggle.inNodeCounts = 0; 1191 } 1192 1193 /* 1194 * Scan the range of characters and delete any internal tag 1195 * transitions. Keep track of what the old state was at the end 1196 * of the range, and add a toggle there if it's needed. 1197 */ 1198 1199 TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search); 1200 cleanupLinePtr = index1Ptr->linePtr; 1201 while (TkBTreeNextTag(&search)) { 1202 oldState ^= 1; 1203 segPtr = search.segPtr; 1204 prevPtr = search.curIndex.linePtr->segPtr; 1205 if (prevPtr == segPtr) { 1206 search.curIndex.linePtr->segPtr = segPtr->nextPtr; 1207 } else { 1208 while (prevPtr->nextPtr != segPtr) { 1209 prevPtr = prevPtr->nextPtr; 1210 } 1211 prevPtr->nextPtr = segPtr->nextPtr; 1212 } 1213 if (segPtr->body.toggle.inNodeCounts) { 1214 ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr, 1215 segPtr->body.toggle.tagPtr, -1); 1216 segPtr->body.toggle.inNodeCounts = 0; 1217 changed = 1; 1218 } else { 1219 changed = 0; 1220 } 1221 ckfree((char *) segPtr); 1222 1223 /* 1224 * The code below is a bit tricky. After deleting a toggle 1225 * we eventually have to call CleanupLine, in order to allow 1226 * character segments to be merged together. To do this, we 1227 * remember in cleanupLinePtr a line that needs to be 1228 * cleaned up, but we don't clean it up until we've moved 1229 * on to a different line. That way the cleanup process 1230 * won't goof up segPtr. 1231 */ 1232 1233 if (cleanupLinePtr != search.curIndex.linePtr) { 1234 CleanupLine(cleanupLinePtr); 1235 cleanupLinePtr = search.curIndex.linePtr; 1236 } 1237 /* 1238 * Quick hack. ChangeNodeToggleCount may move the tag's root 1239 * location around and leave the search in the void. This resets 1240 * the search. 1241 */ 1242 if (changed) { 1243 TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search); 1244 } 1245 } 1246 if ((add != 0) ^ oldState) { 1247 segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE); 1248 segPtr->typePtr = (add) ? &tkTextToggleOffType : &tkTextToggleOnType; 1249 prevPtr = SplitSeg(index2Ptr); 1250 if (prevPtr == NULL) { 1251 segPtr->nextPtr = index2Ptr->linePtr->segPtr; 1252 index2Ptr->linePtr->segPtr = segPtr; 1253 } else { 1254 segPtr->nextPtr = prevPtr->nextPtr; 1255 prevPtr->nextPtr = segPtr; 1256 } 1257 segPtr->size = 0; 1258 segPtr->body.toggle.tagPtr = tagPtr; 1259 segPtr->body.toggle.inNodeCounts = 0; 1260 } 1261 1262 /* 1263 * Cleanup cleanupLinePtr and the last line of the range, if 1264 * these are different. 1265 */ 1266 1267 CleanupLine(cleanupLinePtr); 1268 if (cleanupLinePtr != index2Ptr->linePtr) { 1269 CleanupLine(index2Ptr->linePtr); 1270 } 1271 1272 if (tkBTreeDebug) { 1273 TkBTreeCheck(index1Ptr->tree); 1274 } 1275} 1276 1277/* 1278 *---------------------------------------------------------------------- 1279 * 1280 * ChangeNodeToggleCount -- 1281 * 1282 * This procedure increments or decrements the toggle count for 1283 * a particular tag in a particular node and all its ancestors 1284 * up to the per-tag root node. 1285 * 1286 * Results: 1287 * None. 1288 * 1289 * Side effects: 1290 * The toggle count for tag is adjusted up or down by "delta" in 1291 * nodePtr. This routine maintains the tagRootPtr that identifies 1292 * the root node for the tag, moving it up or down the tree as needed. 1293 * 1294 *---------------------------------------------------------------------- 1295 */ 1296 1297static void 1298ChangeNodeToggleCount(nodePtr, tagPtr, delta) 1299 register Node *nodePtr; /* Node whose toggle count for a tag 1300 * must be changed. */ 1301 TkTextTag *tagPtr; /* Information about tag. */ 1302 int delta; /* Amount to add to current toggle 1303 * count for tag (may be negative). */ 1304{ 1305 register Summary *summaryPtr, *prevPtr; 1306 register Node *node2Ptr; 1307 int rootLevel; /* Level of original tag root */ 1308 1309 tagPtr->toggleCount += delta; 1310 if (tagPtr->tagRootPtr == (Node *) NULL) { 1311 tagPtr->tagRootPtr = nodePtr; 1312 return; 1313 } 1314 1315 /* 1316 * Note the level of the existing root for the tag so we can detect 1317 * if it needs to be moved because of the toggle count change. 1318 */ 1319 1320 rootLevel = tagPtr->tagRootPtr->level; 1321 1322 /* 1323 * Iterate over the node and its ancestors up to the tag root, adjusting 1324 * summary counts at each node and moving the tag's root upwards if 1325 * necessary. 1326 */ 1327 1328 for ( ; nodePtr != tagPtr->tagRootPtr; nodePtr = nodePtr->parentPtr) { 1329 /* 1330 * See if there's already an entry for this tag for this node. If so, 1331 * perhaps all we have to do is adjust its count. 1332 */ 1333 1334 for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr; 1335 summaryPtr != NULL; 1336 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) { 1337 if (summaryPtr->tagPtr == tagPtr) { 1338 break; 1339 } 1340 } 1341 if (summaryPtr != NULL) { 1342 summaryPtr->toggleCount += delta; 1343 if (summaryPtr->toggleCount > 0 && 1344 summaryPtr->toggleCount < tagPtr->toggleCount) { 1345 continue; 1346 } 1347 if (summaryPtr->toggleCount != 0) { 1348 /* 1349 * Should never find a node with max toggle count at this 1350 * point (there shouldn't have been a summary entry in the 1351 * first place). 1352 */ 1353 1354 panic("ChangeNodeToggleCount: bad toggle count (%d) max (%d)", 1355 summaryPtr->toggleCount, tagPtr->toggleCount); 1356 } 1357 1358 /* 1359 * Zero toggle count; must remove this tag from the list. 1360 */ 1361 1362 if (prevPtr == NULL) { 1363 nodePtr->summaryPtr = summaryPtr->nextPtr; 1364 } else { 1365 prevPtr->nextPtr = summaryPtr->nextPtr; 1366 } 1367 ckfree((char *) summaryPtr); 1368 } else { 1369 /* 1370 * This tag isn't currently in the summary information list. 1371 */ 1372 1373 if (rootLevel == nodePtr->level) { 1374 1375 /* 1376 * The old tag root is at the same level in the tree as this 1377 * node, but it isn't at this node. Move the tag root up 1378 * a level, in the hopes that it will now cover this node 1379 * as well as the old root (if not, we'll move it up again 1380 * the next time through the loop). To push it up one level 1381 * we copy the original toggle count into the summary 1382 * information at the old root and change the root to its 1383 * parent node. 1384 */ 1385 1386 Node *rootNodePtr = tagPtr->tagRootPtr; 1387 summaryPtr = (Summary *) ckalloc(sizeof(Summary)); 1388 summaryPtr->tagPtr = tagPtr; 1389 summaryPtr->toggleCount = tagPtr->toggleCount - delta; 1390 summaryPtr->nextPtr = rootNodePtr->summaryPtr; 1391 rootNodePtr->summaryPtr = summaryPtr; 1392 rootNodePtr = rootNodePtr->parentPtr; 1393 rootLevel = rootNodePtr->level; 1394 tagPtr->tagRootPtr = rootNodePtr; 1395 } 1396 summaryPtr = (Summary *) ckalloc(sizeof(Summary)); 1397 summaryPtr->tagPtr = tagPtr; 1398 summaryPtr->toggleCount = delta; 1399 summaryPtr->nextPtr = nodePtr->summaryPtr; 1400 nodePtr->summaryPtr = summaryPtr; 1401 } 1402 } 1403 1404 /* 1405 * If we've decremented the toggle count, then it may be necessary 1406 * to push the tag root down one or more levels. 1407 */ 1408 1409 if (delta >= 0) { 1410 return; 1411 } 1412 if (tagPtr->toggleCount == 0) { 1413 tagPtr->tagRootPtr = (Node *) NULL; 1414 return; 1415 } 1416 nodePtr = tagPtr->tagRootPtr; 1417 while (nodePtr->level > 0) { 1418 /* 1419 * See if a single child node accounts for all of the tag's 1420 * toggles. If so, push the root down one level. 1421 */ 1422 1423 for (node2Ptr = nodePtr->children.nodePtr; 1424 node2Ptr != (Node *)NULL ; 1425 node2Ptr = node2Ptr->nextPtr) { 1426 for (prevPtr = NULL, summaryPtr = node2Ptr->summaryPtr; 1427 summaryPtr != NULL; 1428 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) { 1429 if (summaryPtr->tagPtr == tagPtr) { 1430 break; 1431 } 1432 } 1433 if (summaryPtr == NULL) { 1434 continue; 1435 } 1436 if (summaryPtr->toggleCount != tagPtr->toggleCount) { 1437 /* 1438 * No node has all toggles, so the root is still valid. 1439 */ 1440 1441 return; 1442 } 1443 1444 /* 1445 * This node has all the toggles, so push down the root. 1446 */ 1447 1448 if (prevPtr == NULL) { 1449 node2Ptr->summaryPtr = summaryPtr->nextPtr; 1450 } else { 1451 prevPtr->nextPtr = summaryPtr->nextPtr; 1452 } 1453 ckfree((char *) summaryPtr); 1454 tagPtr->tagRootPtr = node2Ptr; 1455 break; 1456 } 1457 nodePtr = tagPtr->tagRootPtr; 1458 } 1459} 1460 1461/* 1462 *---------------------------------------------------------------------- 1463 * 1464 * FindTagStart -- 1465 * 1466 * Find the start of the first range of a tag. 1467 * 1468 * Results: 1469 * The return value is a pointer to the first tag toggle segment 1470 * for the tag. This can be either a tagon or tagoff segments because 1471 * of the way TkBTreeAdd removes a tag. 1472 * Sets *indexPtr to be the index of the tag toggle. 1473 * 1474 * Side effects: 1475 * None. 1476 * 1477 *---------------------------------------------------------------------- 1478 */ 1479 1480static TkTextSegment * 1481FindTagStart(tree, tagPtr, indexPtr) 1482 TkTextBTree tree; /* Tree to search within */ 1483 TkTextTag *tagPtr; /* Tag to search for. */ 1484 TkTextIndex *indexPtr; /* Return - index information */ 1485{ 1486 register Node *nodePtr; 1487 register TkTextLine *linePtr; 1488 register TkTextSegment *segPtr; 1489 register Summary *summaryPtr; 1490 int offset; 1491 1492 nodePtr = tagPtr->tagRootPtr; 1493 if (nodePtr == (Node *) NULL) { 1494 return NULL; 1495 } 1496 1497 /* 1498 * Search from the root of the subtree that contains the tag down 1499 * to the level 0 node. 1500 */ 1501 1502 while (nodePtr->level > 0) { 1503 for (nodePtr = nodePtr->children.nodePtr ; nodePtr != (Node *) NULL; 1504 nodePtr = nodePtr->nextPtr) { 1505 for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL; 1506 summaryPtr = summaryPtr->nextPtr) { 1507 if (summaryPtr->tagPtr == tagPtr) { 1508 goto gotNodeWithTag; 1509 } 1510 } 1511 } 1512 gotNodeWithTag: 1513 continue; 1514 } 1515 1516 /* 1517 * Work through the lines attached to the level-0 node. 1518 */ 1519 1520 for (linePtr = nodePtr->children.linePtr; linePtr != (TkTextLine *) NULL; 1521 linePtr = linePtr->nextPtr) { 1522 for (offset = 0, segPtr = linePtr->segPtr ; segPtr != NULL; 1523 offset += segPtr->size, segPtr = segPtr->nextPtr) { 1524 if (((segPtr->typePtr == &tkTextToggleOnType) 1525 || (segPtr->typePtr == &tkTextToggleOffType)) 1526 && (segPtr->body.toggle.tagPtr == tagPtr)) { 1527 /* 1528 * It is possible that this is a tagoff tag, but that 1529 * gets cleaned up later. 1530 */ 1531 indexPtr->tree = tree; 1532 indexPtr->linePtr = linePtr; 1533 indexPtr->byteIndex = offset; 1534 return segPtr; 1535 } 1536 } 1537 } 1538 return NULL; 1539} 1540 1541/* 1542 *---------------------------------------------------------------------- 1543 * 1544 * FindTagEnd -- 1545 * 1546 * Find the end of the last range of a tag. 1547 * 1548 * Results: 1549 * The return value is a pointer to the last tag toggle segment 1550 * for the tag. This can be either a tagon or tagoff segments because 1551 * of the way TkBTreeAdd removes a tag. 1552 * Sets *indexPtr to be the index of the tag toggle. 1553 * 1554 * Side effects: 1555 * None. 1556 * 1557 *---------------------------------------------------------------------- 1558 */ 1559 1560static TkTextSegment * 1561FindTagEnd(tree, tagPtr, indexPtr) 1562 TkTextBTree tree; /* Tree to search within */ 1563 TkTextTag *tagPtr; /* Tag to search for. */ 1564 TkTextIndex *indexPtr; /* Return - index information */ 1565{ 1566 register Node *nodePtr, *lastNodePtr; 1567 register TkTextLine *linePtr ,*lastLinePtr; 1568 register TkTextSegment *segPtr, *lastSegPtr, *last2SegPtr; 1569 register Summary *summaryPtr; 1570 int lastoffset, lastoffset2, offset; 1571 1572 nodePtr = tagPtr->tagRootPtr; 1573 if (nodePtr == (Node *) NULL) { 1574 return NULL; 1575 } 1576 1577 /* 1578 * Search from the root of the subtree that contains the tag down 1579 * to the level 0 node. 1580 */ 1581 1582 while (nodePtr->level > 0) { 1583 for (lastNodePtr = NULL, nodePtr = nodePtr->children.nodePtr ; 1584 nodePtr != (Node *) NULL; nodePtr = nodePtr->nextPtr) { 1585 for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL; 1586 summaryPtr = summaryPtr->nextPtr) { 1587 if (summaryPtr->tagPtr == tagPtr) { 1588 lastNodePtr = nodePtr; 1589 break; 1590 } 1591 } 1592 } 1593 nodePtr = lastNodePtr; 1594 } 1595 1596 /* 1597 * Work through the lines attached to the level-0 node. 1598 */ 1599 last2SegPtr = NULL; 1600 lastoffset2 = 0; 1601 lastoffset = 0; 1602 for (lastLinePtr = NULL, linePtr = nodePtr->children.linePtr; 1603 linePtr != (TkTextLine *) NULL; linePtr = linePtr->nextPtr) { 1604 for (offset = 0, lastSegPtr = NULL, segPtr = linePtr->segPtr ; 1605 segPtr != NULL; 1606 offset += segPtr->size, segPtr = segPtr->nextPtr) { 1607 if (((segPtr->typePtr == &tkTextToggleOnType) 1608 || (segPtr->typePtr == &tkTextToggleOffType)) 1609 && (segPtr->body.toggle.tagPtr == tagPtr)) { 1610 lastSegPtr = segPtr; 1611 lastoffset = offset; 1612 } 1613 } 1614 if (lastSegPtr != NULL) { 1615 lastLinePtr = linePtr; 1616 last2SegPtr = lastSegPtr; 1617 lastoffset2 = lastoffset; 1618 } 1619 } 1620 indexPtr->tree = tree; 1621 indexPtr->linePtr = lastLinePtr; 1622 indexPtr->byteIndex = lastoffset2; 1623 return last2SegPtr; 1624} 1625 1626/* 1627 *---------------------------------------------------------------------- 1628 * 1629 * TkBTreeStartSearch -- 1630 * 1631 * This procedure sets up a search for tag transitions involving 1632 * a given tag (or all tags) in a given range of the text. 1633 * 1634 * Results: 1635 * None. 1636 * 1637 * Side effects: 1638 * The information at *searchPtr is set up so that subsequent calls 1639 * to TkBTreeNextTag or TkBTreePrevTag will return information about the 1640 * locations of tag transitions. Note that TkBTreeNextTag or 1641 * TkBTreePrevTag must be called to get the first transition. 1642 * Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not 1643 * guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be 1644 * greater than that if *index1Ptr is less than the first tag transition. 1645 * 1646 *---------------------------------------------------------------------- 1647 */ 1648 1649void 1650TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, searchPtr) 1651 TkTextIndex *index1Ptr; /* Search starts here. Tag toggles 1652 * at this position will not be 1653 * returned. */ 1654 TkTextIndex *index2Ptr; /* Search stops here. Tag toggles 1655 * at this position *will* be 1656 * returned. */ 1657 TkTextTag *tagPtr; /* Tag to search for. NULL means 1658 * search for any tag. */ 1659 register TkTextSearch *searchPtr; /* Where to store information about 1660 * search's progress. */ 1661{ 1662 int offset; 1663 TkTextIndex index0; /* First index of the tag */ 1664 TkTextSegment *seg0Ptr; /* First segment of the tag */ 1665 1666 /* 1667 * Find the segment that contains the first toggle for the tag. This 1668 * may become the starting point in the search. 1669 */ 1670 1671 seg0Ptr = FindTagStart(index1Ptr->tree, tagPtr, &index0); 1672 if (seg0Ptr == (TkTextSegment *) NULL) { 1673 /* 1674 * Even though there are no toggles, the display code still 1675 * uses the search curIndex, so initialize that anyway. 1676 */ 1677 1678 searchPtr->linesLeft = 0; 1679 searchPtr->curIndex = *index1Ptr; 1680 searchPtr->segPtr = NULL; 1681 searchPtr->nextPtr = NULL; 1682 return; 1683 } 1684 if (TkTextIndexCmp(index1Ptr, &index0) < 0) { 1685 /* 1686 * Adjust start of search up to the first range of the tag 1687 */ 1688 1689 searchPtr->curIndex = index0; 1690 searchPtr->segPtr = NULL; 1691 searchPtr->nextPtr = seg0Ptr; /* Will be returned by NextTag */ 1692 index1Ptr = &index0; 1693 } else { 1694 searchPtr->curIndex = *index1Ptr; 1695 searchPtr->segPtr = NULL; 1696 searchPtr->nextPtr = TkTextIndexToSeg(index1Ptr, &offset); 1697 searchPtr->curIndex.byteIndex -= offset; 1698 } 1699 searchPtr->lastPtr = TkTextIndexToSeg(index2Ptr, (int *) NULL); 1700 searchPtr->tagPtr = tagPtr; 1701 searchPtr->linesLeft = TkBTreeLineIndex(index2Ptr->linePtr) + 1 1702 - TkBTreeLineIndex(index1Ptr->linePtr); 1703 searchPtr->allTags = (tagPtr == NULL); 1704 if (searchPtr->linesLeft == 1) { 1705 /* 1706 * Starting and stopping segments are in the same line; mark the 1707 * search as over immediately if the second segment is before the 1708 * first. A search does not return a toggle at the very start of 1709 * the range, unless the range is artificially moved up to index0. 1710 */ 1711 if (((index1Ptr == &index0) && 1712 (index1Ptr->byteIndex > index2Ptr->byteIndex)) || 1713 ((index1Ptr != &index0) && 1714 (index1Ptr->byteIndex >= index2Ptr->byteIndex))) { 1715 searchPtr->linesLeft = 0; 1716 } 1717 } 1718} 1719 1720/* 1721 *---------------------------------------------------------------------- 1722 * 1723 * TkBTreeStartSearchBack -- 1724 * 1725 * This procedure sets up a search backwards for tag transitions involving 1726 * a given tag (or all tags) in a given range of the text. In the 1727 * normal case the first index (*index1Ptr) is beyond the second 1728 * index (*index2Ptr). 1729 * 1730 * 1731 * Results: 1732 * None. 1733 * 1734 * Side effects: 1735 * The information at *searchPtr is set up so that subsequent calls 1736 * to TkBTreePrevTag will return information about the 1737 * locations of tag transitions. Note that TkBTreePrevTag must be called 1738 * to get the first transition. 1739 * Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not 1740 * guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be 1741 * less than that if *index1Ptr is greater than the last tag transition. 1742 * 1743 *---------------------------------------------------------------------- 1744 */ 1745 1746void 1747TkBTreeStartSearchBack(index1Ptr, index2Ptr, tagPtr, searchPtr) 1748 TkTextIndex *index1Ptr; /* Search starts here. Tag toggles 1749 * at this position will not be 1750 * returned. */ 1751 TkTextIndex *index2Ptr; /* Search stops here. Tag toggles 1752 * at this position *will* be 1753 * returned. */ 1754 TkTextTag *tagPtr; /* Tag to search for. NULL means 1755 * search for any tag. */ 1756 register TkTextSearch *searchPtr; /* Where to store information about 1757 * search's progress. */ 1758{ 1759 int offset; 1760 TkTextIndex index0; /* Last index of the tag */ 1761 TkTextIndex backOne; /* One character before starting index */ 1762 TkTextSegment *seg0Ptr; /* Last segment of the tag */ 1763 1764 /* 1765 * Find the segment that contains the last toggle for the tag. This 1766 * may become the starting point in the search. 1767 */ 1768 1769 seg0Ptr = FindTagEnd(index1Ptr->tree, tagPtr, &index0); 1770 if (seg0Ptr == (TkTextSegment *) NULL) { 1771 /* 1772 * Even though there are no toggles, the display code still 1773 * uses the search curIndex, so initialize that anyway. 1774 */ 1775 1776 searchPtr->linesLeft = 0; 1777 searchPtr->curIndex = *index1Ptr; 1778 searchPtr->segPtr = NULL; 1779 searchPtr->nextPtr = NULL; 1780 return; 1781 } 1782 1783 /* 1784 * Adjust the start of the search so it doesn't find any tag toggles 1785 * that are right at the index specified by the user. 1786 */ 1787 1788 if (TkTextIndexCmp(index1Ptr, &index0) > 0) { 1789 searchPtr->curIndex = index0; 1790 index1Ptr = &index0; 1791 } else { 1792 TkTextIndexBackChars(index1Ptr, 1, &searchPtr->curIndex); 1793 } 1794 searchPtr->segPtr = NULL; 1795 searchPtr->nextPtr = TkTextIndexToSeg(&searchPtr->curIndex, &offset); 1796 searchPtr->curIndex.byteIndex -= offset; 1797 1798 /* 1799 * Adjust the end of the search so it does find toggles that are right 1800 * at the second index specified by the user. 1801 */ 1802 1803 if ((TkBTreeLineIndex(index2Ptr->linePtr) == 0) && 1804 (index2Ptr->byteIndex == 0)) { 1805 backOne = *index2Ptr; 1806 searchPtr->lastPtr = NULL; /* Signals special case for 1.0 */ 1807 } else { 1808 TkTextIndexBackChars(index2Ptr, 1, &backOne); 1809 searchPtr->lastPtr = TkTextIndexToSeg(&backOne, (int *) NULL); 1810 } 1811 searchPtr->tagPtr = tagPtr; 1812 searchPtr->linesLeft = TkBTreeLineIndex(index1Ptr->linePtr) + 1 1813 - TkBTreeLineIndex(backOne.linePtr); 1814 searchPtr->allTags = (tagPtr == NULL); 1815 if (searchPtr->linesLeft == 1) { 1816 /* 1817 * Starting and stopping segments are in the same line; mark the 1818 * search as over immediately if the second segment is after the 1819 * first. 1820 */ 1821 1822 if (index1Ptr->byteIndex <= backOne.byteIndex) { 1823 searchPtr->linesLeft = 0; 1824 } 1825 } 1826} 1827 1828/* 1829 *---------------------------------------------------------------------- 1830 * 1831 * TkBTreeNextTag -- 1832 * 1833 * Once a tag search has begun, successive calls to this procedure 1834 * return successive tag toggles. Note: it is NOT SAFE to call this 1835 * procedure if characters have been inserted into or deleted from 1836 * the B-tree since the call to TkBTreeStartSearch. 1837 * 1838 * Results: 1839 * The return value is 1 if another toggle was found that met the 1840 * criteria specified in the call to TkBTreeStartSearch; in this 1841 * case searchPtr->curIndex gives the toggle's position and 1842 * searchPtr->curTagPtr points to its segment. 0 is returned if 1843 * no more matching tag transitions were found; in this case 1844 * searchPtr->curIndex is the same as searchPtr->stopIndex. 1845 * 1846 * Side effects: 1847 * Information in *searchPtr is modified to update the state of the 1848 * search and indicate where the next tag toggle is located. 1849 * 1850 *---------------------------------------------------------------------- 1851 */ 1852 1853int 1854TkBTreeNextTag(searchPtr) 1855 register TkTextSearch *searchPtr; /* Information about search in 1856 * progress; must have been set up by 1857 * call to TkBTreeStartSearch. */ 1858{ 1859 register TkTextSegment *segPtr; 1860 register Node *nodePtr; 1861 register Summary *summaryPtr; 1862 1863 if (searchPtr->linesLeft <= 0) { 1864 goto searchOver; 1865 } 1866 1867 /* 1868 * The outermost loop iterates over lines that may potentially contain 1869 * a relevant tag transition, starting from the current segment in 1870 * the current line. 1871 */ 1872 1873 segPtr = searchPtr->nextPtr; 1874 while (1) { 1875 /* 1876 * Check for more tags on the current line. 1877 */ 1878 1879 for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) { 1880 if (segPtr == searchPtr->lastPtr) { 1881 goto searchOver; 1882 } 1883 if (((segPtr->typePtr == &tkTextToggleOnType) 1884 || (segPtr->typePtr == &tkTextToggleOffType)) 1885 && (searchPtr->allTags 1886 || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) { 1887 searchPtr->segPtr = segPtr; 1888 searchPtr->nextPtr = segPtr->nextPtr; 1889 searchPtr->tagPtr = segPtr->body.toggle.tagPtr; 1890 return 1; 1891 } 1892 searchPtr->curIndex.byteIndex += segPtr->size; 1893 } 1894 1895 /* 1896 * See if there are more lines associated with the current parent 1897 * node. If so, go back to the top of the loop to search the next 1898 * one. 1899 */ 1900 1901 nodePtr = searchPtr->curIndex.linePtr->parentPtr; 1902 searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr; 1903 searchPtr->linesLeft--; 1904 if (searchPtr->linesLeft <= 0) { 1905 goto searchOver; 1906 } 1907 if (searchPtr->curIndex.linePtr != NULL) { 1908 segPtr = searchPtr->curIndex.linePtr->segPtr; 1909 searchPtr->curIndex.byteIndex = 0; 1910 continue; 1911 } 1912 if (nodePtr == searchPtr->tagPtr->tagRootPtr) { 1913 goto searchOver; 1914 } 1915 1916 /* 1917 * Search across and up through the B-tree's node hierarchy looking 1918 * for the next node that has a relevant tag transition somewhere in 1919 * its subtree. Be sure to update linesLeft as we skip over large 1920 * chunks of lines. 1921 */ 1922 1923 while (1) { 1924 while (nodePtr->nextPtr == NULL) { 1925 if (nodePtr->parentPtr == NULL || 1926 nodePtr->parentPtr == searchPtr->tagPtr->tagRootPtr) { 1927 goto searchOver; 1928 } 1929 nodePtr = nodePtr->parentPtr; 1930 } 1931 nodePtr = nodePtr->nextPtr; 1932 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 1933 summaryPtr = summaryPtr->nextPtr) { 1934 if ((searchPtr->allTags) || 1935 (summaryPtr->tagPtr == searchPtr->tagPtr)) { 1936 goto gotNodeWithTag; 1937 } 1938 } 1939 searchPtr->linesLeft -= nodePtr->numLines; 1940 } 1941 1942 /* 1943 * At this point we've found a subtree that has a relevant tag 1944 * transition. Now search down (and across) through that subtree 1945 * to find the first level-0 node that has a relevant tag transition. 1946 */ 1947 1948 gotNodeWithTag: 1949 while (nodePtr->level > 0) { 1950 for (nodePtr = nodePtr->children.nodePtr; ; 1951 nodePtr = nodePtr->nextPtr) { 1952 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 1953 summaryPtr = summaryPtr->nextPtr) { 1954 if ((searchPtr->allTags) 1955 || (summaryPtr->tagPtr == searchPtr->tagPtr)) { 1956 goto nextChild; 1957 } 1958 } 1959 searchPtr->linesLeft -= nodePtr->numLines; 1960 if (nodePtr->nextPtr == NULL) { 1961 panic("TkBTreeNextTag found incorrect tag summary info."); 1962 } 1963 } 1964 nextChild: 1965 continue; 1966 } 1967 1968 /* 1969 * Now we're down to a level-0 node that contains a line that contains 1970 * a relevant tag transition. Set up line information and go back to 1971 * the beginning of the loop to search through lines. 1972 */ 1973 1974 searchPtr->curIndex.linePtr = nodePtr->children.linePtr; 1975 searchPtr->curIndex.byteIndex = 0; 1976 segPtr = searchPtr->curIndex.linePtr->segPtr; 1977 if (searchPtr->linesLeft <= 0) { 1978 goto searchOver; 1979 } 1980 continue; 1981 } 1982 1983 searchOver: 1984 searchPtr->linesLeft = 0; 1985 searchPtr->segPtr = NULL; 1986 return 0; 1987} 1988 1989/* 1990 *---------------------------------------------------------------------- 1991 * 1992 * TkBTreePrevTag -- 1993 * 1994 * Once a tag search has begun, successive calls to this procedure 1995 * return successive tag toggles in the reverse direction. 1996 * Note: it is NOT SAFE to call this 1997 * procedure if characters have been inserted into or deleted from 1998 * the B-tree since the call to TkBTreeStartSearch. 1999 * 2000 * Results: 2001 * The return value is 1 if another toggle was found that met the 2002 * criteria specified in the call to TkBTreeStartSearch; in this 2003 * case searchPtr->curIndex gives the toggle's position and 2004 * searchPtr->curTagPtr points to its segment. 0 is returned if 2005 * no more matching tag transitions were found; in this case 2006 * searchPtr->curIndex is the same as searchPtr->stopIndex. 2007 * 2008 * Side effects: 2009 * Information in *searchPtr is modified to update the state of the 2010 * search and indicate where the next tag toggle is located. 2011 * 2012 *---------------------------------------------------------------------- 2013 */ 2014 2015int 2016TkBTreePrevTag(searchPtr) 2017 register TkTextSearch *searchPtr; /* Information about search in 2018 * progress; must have been set up by 2019 * call to TkBTreeStartSearch. */ 2020{ 2021 register TkTextSegment *segPtr, *prevPtr; 2022 register TkTextLine *linePtr, *prevLinePtr; 2023 register Node *nodePtr, *node2Ptr, *prevNodePtr; 2024 register Summary *summaryPtr; 2025 int byteIndex; 2026 int pastLast; /* Saw last marker during scan */ 2027 int linesSkipped; 2028 2029 if (searchPtr->linesLeft <= 0) { 2030 goto searchOver; 2031 } 2032 2033 /* 2034 * The outermost loop iterates over lines that may potentially contain 2035 * a relevant tag transition, starting from the current segment in 2036 * the current line. "nextPtr" is maintained as the last segment in 2037 * a line that we can look at. 2038 */ 2039 2040 while (1) { 2041 /* 2042 * Check for the last toggle before the current segment on this line. 2043 */ 2044 byteIndex = 0; 2045 if (searchPtr->lastPtr == NULL) { 2046 /* 2047 * Search back to the very beginning, so pastLast is irrelevent. 2048 */ 2049 pastLast = 1; 2050 } else { 2051 pastLast = 0; 2052 } 2053 for (prevPtr = NULL, segPtr = searchPtr->curIndex.linePtr->segPtr ; 2054 segPtr != NULL && segPtr != searchPtr->nextPtr; 2055 segPtr = segPtr->nextPtr) { 2056 if (((segPtr->typePtr == &tkTextToggleOnType) 2057 || (segPtr->typePtr == &tkTextToggleOffType)) 2058 && (searchPtr->allTags 2059 || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) { 2060 prevPtr = segPtr; 2061 searchPtr->curIndex.byteIndex = byteIndex; 2062 } 2063 if (segPtr == searchPtr->lastPtr) { 2064 prevPtr = NULL; /* Segments earlier than last don't count */ 2065 pastLast = 1; 2066 } 2067 byteIndex += segPtr->size; 2068 } 2069 if (prevPtr != NULL) { 2070 if (searchPtr->linesLeft == 1 && !pastLast) { 2071 /* 2072 * We found a segment that is before the stopping index. 2073 * Note that it is OK if prevPtr == lastPtr. 2074 */ 2075 goto searchOver; 2076 } 2077 searchPtr->segPtr = prevPtr; 2078 searchPtr->nextPtr = prevPtr; 2079 searchPtr->tagPtr = prevPtr->body.toggle.tagPtr; 2080 return 1; 2081 } 2082 2083 searchPtr->linesLeft--; 2084 if (searchPtr->linesLeft <= 0) { 2085 goto searchOver; 2086 } 2087 2088 /* 2089 * See if there are more lines associated with the current parent 2090 * node. If so, go back to the top of the loop to search the previous 2091 * one. 2092 */ 2093 2094 nodePtr = searchPtr->curIndex.linePtr->parentPtr; 2095 for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr; 2096 linePtr != NULL && linePtr != searchPtr->curIndex.linePtr; 2097 prevLinePtr = linePtr, linePtr = linePtr->nextPtr) { 2098 /* empty loop body */ ; 2099 } 2100 if (prevLinePtr != NULL) { 2101 searchPtr->curIndex.linePtr = prevLinePtr; 2102 searchPtr->nextPtr = NULL; 2103 continue; 2104 } 2105 if (nodePtr == searchPtr->tagPtr->tagRootPtr) { 2106 goto searchOver; 2107 } 2108 2109 /* 2110 * Search across and up through the B-tree's node hierarchy looking 2111 * for the previous node that has a relevant tag transition somewhere in 2112 * its subtree. The search and line counting is trickier with/out 2113 * back pointers. We'll scan all the nodes under a parent up to 2114 * the current node, searching all of them for tag state. The last 2115 * one we find, if any, is recorded in prevNodePtr, and any nodes 2116 * past prevNodePtr that don't have tag state increment linesSkipped. 2117 */ 2118 2119 while (1) { 2120 for (prevNodePtr = NULL, linesSkipped = 0, 2121 node2Ptr = nodePtr->parentPtr->children.nodePtr ; 2122 node2Ptr != nodePtr; node2Ptr = node2Ptr->nextPtr) { 2123 for (summaryPtr = node2Ptr->summaryPtr; summaryPtr != NULL; 2124 summaryPtr = summaryPtr->nextPtr) { 2125 if ((searchPtr->allTags) || 2126 (summaryPtr->tagPtr == searchPtr->tagPtr)) { 2127 prevNodePtr = node2Ptr; 2128 linesSkipped = 0; 2129 goto keepLooking; 2130 } 2131 } 2132 linesSkipped += node2Ptr->numLines; 2133 2134 keepLooking: 2135 continue; 2136 } 2137 if (prevNodePtr != NULL) { 2138 nodePtr = prevNodePtr; 2139 searchPtr->linesLeft -= linesSkipped; 2140 goto gotNodeWithTag; 2141 } 2142 nodePtr = nodePtr->parentPtr; 2143 if (nodePtr->parentPtr == NULL || 2144 nodePtr == searchPtr->tagPtr->tagRootPtr) { 2145 goto searchOver; 2146 } 2147 } 2148 2149 /* 2150 * At this point we've found a subtree that has a relevant tag 2151 * transition. Now search down (and across) through that subtree 2152 * to find the last level-0 node that has a relevant tag transition. 2153 */ 2154 2155 gotNodeWithTag: 2156 while (nodePtr->level > 0) { 2157 for (linesSkipped = 0, prevNodePtr = NULL, 2158 nodePtr = nodePtr->children.nodePtr; nodePtr != NULL ; 2159 nodePtr = nodePtr->nextPtr) { 2160 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 2161 summaryPtr = summaryPtr->nextPtr) { 2162 if ((searchPtr->allTags) 2163 || (summaryPtr->tagPtr == searchPtr->tagPtr)) { 2164 prevNodePtr = nodePtr; 2165 linesSkipped = 0; 2166 goto keepLooking2; 2167 } 2168 } 2169 linesSkipped += nodePtr->numLines; 2170 2171 keepLooking2: 2172 continue; 2173 } 2174 if (prevNodePtr == NULL) { 2175 panic("TkBTreePrevTag found incorrect tag summary info."); 2176 } 2177 searchPtr->linesLeft -= linesSkipped; 2178 nodePtr = prevNodePtr; 2179 } 2180 2181 /* 2182 * Now we're down to a level-0 node that contains a line that contains 2183 * a relevant tag transition. Set up line information and go back to 2184 * the beginning of the loop to search through lines. We start with 2185 * the last line below the node. 2186 */ 2187 2188 for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr; 2189 linePtr != NULL ; 2190 prevLinePtr = linePtr, linePtr = linePtr->nextPtr) { 2191 /* empty loop body */ ; 2192 } 2193 searchPtr->curIndex.linePtr = prevLinePtr; 2194 searchPtr->curIndex.byteIndex = 0; 2195 if (searchPtr->linesLeft <= 0) { 2196 goto searchOver; 2197 } 2198 continue; 2199 } 2200 2201 searchOver: 2202 searchPtr->linesLeft = 0; 2203 searchPtr->segPtr = NULL; 2204 return 0; 2205} 2206 2207/* 2208 *---------------------------------------------------------------------- 2209 * 2210 * TkBTreeCharTagged -- 2211 * 2212 * Determine whether a particular character has a particular tag. 2213 * 2214 * Results: 2215 * The return value is 1 if the given tag is in effect at the 2216 * character given by linePtr and ch, and 0 otherwise. 2217 * 2218 * Side effects: 2219 * None. 2220 * 2221 *---------------------------------------------------------------------- 2222 */ 2223 2224int 2225TkBTreeCharTagged(indexPtr, tagPtr) 2226 TkTextIndex *indexPtr; /* Indicates a character position at 2227 * which to check for a tag. */ 2228 TkTextTag *tagPtr; /* Tag of interest. */ 2229{ 2230 register Node *nodePtr; 2231 register TkTextLine *siblingLinePtr; 2232 register TkTextSegment *segPtr; 2233 TkTextSegment *toggleSegPtr; 2234 int toggles, index; 2235 2236 /* 2237 * Check for toggles for the tag in indexPtr's line but before 2238 * indexPtr. If there is one, its type indicates whether or 2239 * not the character is tagged. 2240 */ 2241 2242 toggleSegPtr = NULL; 2243 for (index = 0, segPtr = indexPtr->linePtr->segPtr; 2244 (index + segPtr->size) <= indexPtr->byteIndex; 2245 index += segPtr->size, segPtr = segPtr->nextPtr) { 2246 if (((segPtr->typePtr == &tkTextToggleOnType) 2247 || (segPtr->typePtr == &tkTextToggleOffType)) 2248 && (segPtr->body.toggle.tagPtr == tagPtr)) { 2249 toggleSegPtr = segPtr; 2250 } 2251 } 2252 if (toggleSegPtr != NULL) { 2253 return (toggleSegPtr->typePtr == &tkTextToggleOnType); 2254 } 2255 2256 /* 2257 * No toggle in this line. Look for toggles for the tag in lines 2258 * that are predecessors of indexPtr->linePtr but under the same 2259 * level-0 node. 2260 */ 2261 2262 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr; 2263 siblingLinePtr != indexPtr->linePtr; 2264 siblingLinePtr = siblingLinePtr->nextPtr) { 2265 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL; 2266 segPtr = segPtr->nextPtr) { 2267 if (((segPtr->typePtr == &tkTextToggleOnType) 2268 || (segPtr->typePtr == &tkTextToggleOffType)) 2269 && (segPtr->body.toggle.tagPtr == tagPtr)) { 2270 toggleSegPtr = segPtr; 2271 } 2272 } 2273 } 2274 if (toggleSegPtr != NULL) { 2275 return (toggleSegPtr->typePtr == &tkTextToggleOnType); 2276 } 2277 2278 /* 2279 * No toggle in this node. Scan upwards through the ancestors of 2280 * this node, counting the number of toggles of the given tag in 2281 * siblings that precede that node. 2282 */ 2283 2284 toggles = 0; 2285 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL; 2286 nodePtr = nodePtr->parentPtr) { 2287 register Node *siblingPtr; 2288 register Summary *summaryPtr; 2289 2290 for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 2291 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) { 2292 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL; 2293 summaryPtr = summaryPtr->nextPtr) { 2294 if (summaryPtr->tagPtr == tagPtr) { 2295 toggles += summaryPtr->toggleCount; 2296 } 2297 } 2298 } 2299 if (nodePtr == tagPtr->tagRootPtr) { 2300 break; 2301 } 2302 } 2303 2304 /* 2305 * An odd number of toggles means that the tag is present at the 2306 * given point. 2307 */ 2308 2309 return toggles & 1; 2310} 2311 2312/* 2313 *---------------------------------------------------------------------- 2314 * 2315 * TkBTreeGetTags -- 2316 * 2317 * Return information about all of the tags that are associated 2318 * with a particular character in a B-tree of text. 2319 * 2320 * Results: 2321 * The return value is a malloc-ed array containing pointers to 2322 * information for each of the tags that is associated with 2323 * the character at the position given by linePtr and ch. The 2324 * word at *numTagsPtr is filled in with the number of pointers 2325 * in the array. It is up to the caller to free the array by 2326 * passing it to free. If there are no tags at the given character 2327 * then a NULL pointer is returned and *numTagsPtr will be set to 0. 2328 * 2329 * Side effects: 2330 * None. 2331 * 2332 *---------------------------------------------------------------------- 2333 */ 2334 2335 /* ARGSUSED */ 2336TkTextTag ** 2337TkBTreeGetTags(indexPtr, numTagsPtr) 2338 TkTextIndex *indexPtr; /* Indicates a particular position in 2339 * the B-tree. */ 2340 int *numTagsPtr; /* Store number of tags found at this 2341 * location. */ 2342{ 2343 register Node *nodePtr; 2344 register TkTextLine *siblingLinePtr; 2345 register TkTextSegment *segPtr; 2346 int src, dst, index; 2347 TagInfo tagInfo; 2348#define NUM_TAG_INFOS 10 2349 2350 tagInfo.numTags = 0; 2351 tagInfo.arraySize = NUM_TAG_INFOS; 2352 tagInfo.tagPtrs = (TkTextTag **) ckalloc((unsigned) 2353 NUM_TAG_INFOS*sizeof(TkTextTag *)); 2354 tagInfo.counts = (int *) ckalloc((unsigned) 2355 NUM_TAG_INFOS*sizeof(int)); 2356 2357 /* 2358 * Record tag toggles within the line of indexPtr but preceding 2359 * indexPtr. 2360 */ 2361 2362 for (index = 0, segPtr = indexPtr->linePtr->segPtr; 2363 (index + segPtr->size) <= indexPtr->byteIndex; 2364 index += segPtr->size, segPtr = segPtr->nextPtr) { 2365 if ((segPtr->typePtr == &tkTextToggleOnType) 2366 || (segPtr->typePtr == &tkTextToggleOffType)) { 2367 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo); 2368 } 2369 } 2370 2371 /* 2372 * Record toggles for tags in lines that are predecessors of 2373 * indexPtr->linePtr but under the same level-0 node. 2374 */ 2375 2376 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr; 2377 siblingLinePtr != indexPtr->linePtr; 2378 siblingLinePtr = siblingLinePtr->nextPtr) { 2379 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL; 2380 segPtr = segPtr->nextPtr) { 2381 if ((segPtr->typePtr == &tkTextToggleOnType) 2382 || (segPtr->typePtr == &tkTextToggleOffType)) { 2383 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo); 2384 } 2385 } 2386 } 2387 2388 /* 2389 * For each node in the ancestry of this line, record tag toggles 2390 * for all siblings that precede that node. 2391 */ 2392 2393 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL; 2394 nodePtr = nodePtr->parentPtr) { 2395 register Node *siblingPtr; 2396 register Summary *summaryPtr; 2397 2398 for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 2399 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) { 2400 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL; 2401 summaryPtr = summaryPtr->nextPtr) { 2402 if (summaryPtr->toggleCount & 1) { 2403 IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount, 2404 &tagInfo); 2405 } 2406 } 2407 } 2408 } 2409 2410 /* 2411 * Go through the tag information and squash out all of the tags 2412 * that have even toggle counts (these tags exist before the point 2413 * of interest, but not at the desired character itself). 2414 */ 2415 2416 for (src = 0, dst = 0; src < tagInfo.numTags; src++) { 2417 if (tagInfo.counts[src] & 1) { 2418 tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src]; 2419 dst++; 2420 } 2421 } 2422 *numTagsPtr = dst; 2423 ckfree((char *) tagInfo.counts); 2424 if (dst == 0) { 2425 ckfree((char *) tagInfo.tagPtrs); 2426 return NULL; 2427 } 2428 return tagInfo.tagPtrs; 2429} 2430 2431/* 2432 *---------------------------------------------------------------------- 2433 * 2434 * TkTextIsElided -- 2435 * 2436 * Special case to just return information about elided attribute. 2437 * Specialized from TkBTreeGetTags(indexPtr, numTagsPtr) 2438 * and GetStyle(textPtr, indexPtr). 2439 * Just need to keep track of invisibility settings for each priority, 2440 * pick highest one active at end 2441 * 2442 * Results: 2443 * Returns whether this text should be elided or not. 2444 * 2445 * Side effects: 2446 * None. 2447 * 2448 *---------------------------------------------------------------------- 2449 */ 2450 2451 /* ARGSUSED */ 2452int 2453TkTextIsElided(textPtr, indexPtr) 2454 TkText *textPtr; /* Overall information about text widget. */ 2455 TkTextIndex *indexPtr; /* The character in the text for which 2456 * display information is wanted. */ 2457{ 2458#define LOTSA_TAGS 1000 2459 int elide = 0; /* if nobody says otherwise, it's visible */ 2460 2461 int deftagCnts[LOTSA_TAGS]; 2462 int *tagCnts = deftagCnts; 2463 TkTextTag *deftagPtrs[LOTSA_TAGS]; 2464 TkTextTag **tagPtrs = deftagPtrs; 2465 int numTags = textPtr->numTags; 2466 register Node *nodePtr; 2467 register TkTextLine *siblingLinePtr; 2468 register TkTextSegment *segPtr; 2469 register TkTextTag *tagPtr = NULL; /* silence gcc 4 warning */ 2470 register int i, index; 2471 2472 /* almost always avoid malloc, so stay out of system calls */ 2473 if (LOTSA_TAGS < numTags) { 2474 tagCnts = (int *)ckalloc((unsigned)sizeof(int) * numTags); 2475 tagPtrs = (TkTextTag **)ckalloc((unsigned)sizeof(TkTextTag *) * numTags); 2476 } 2477 2478 for (i=0; i<numTags; i++) { 2479 tagCnts[i] = 0; 2480 } 2481 2482 /* 2483 * Record tag toggles within the line of indexPtr but preceding 2484 * indexPtr. 2485 */ 2486 2487 for (index = 0, segPtr = indexPtr->linePtr->segPtr; 2488 (index + segPtr->size) <= indexPtr->byteIndex; 2489 index += segPtr->size, segPtr = segPtr->nextPtr) { 2490 if ((segPtr->typePtr == &tkTextToggleOnType) 2491 || (segPtr->typePtr == &tkTextToggleOffType)) { 2492 tagPtr = segPtr->body.toggle.tagPtr; 2493 if (tagPtr->elideString != NULL) { 2494 tagPtrs[tagPtr->priority] = tagPtr; 2495 tagCnts[tagPtr->priority]++; 2496 } 2497 } 2498 } 2499 2500 /* 2501 * Record toggles for tags in lines that are predecessors of 2502 * indexPtr->linePtr but under the same level-0 node. 2503 */ 2504 2505 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr; 2506 siblingLinePtr != indexPtr->linePtr; 2507 siblingLinePtr = siblingLinePtr->nextPtr) { 2508 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL; 2509 segPtr = segPtr->nextPtr) { 2510 if ((segPtr->typePtr == &tkTextToggleOnType) 2511 || (segPtr->typePtr == &tkTextToggleOffType)) { 2512 tagPtr = segPtr->body.toggle.tagPtr; 2513 if (tagPtr->elideString != NULL) { 2514 tagPtrs[tagPtr->priority] = tagPtr; 2515 tagCnts[tagPtr->priority]++; 2516 } 2517 } 2518 } 2519 } 2520 2521 /* 2522 * For each node in the ancestry of this line, record tag toggles 2523 * for all siblings that precede that node. 2524 */ 2525 2526 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL; 2527 nodePtr = nodePtr->parentPtr) { 2528 register Node *siblingPtr; 2529 register Summary *summaryPtr; 2530 2531 for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 2532 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) { 2533 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL; 2534 summaryPtr = summaryPtr->nextPtr) { 2535 if (summaryPtr->toggleCount & 1) { 2536 tagPtr = summaryPtr->tagPtr; 2537 if (tagPtr->elideString != NULL) { 2538 tagPtrs[tagPtr->priority] = tagPtr; 2539 tagCnts[tagPtr->priority] += summaryPtr->toggleCount; 2540 } 2541 } 2542 } 2543 } 2544 } 2545 2546 /* 2547 * Now traverse from highest priority to lowest, 2548 * take elided value from first odd count (= on) 2549 */ 2550 2551 for (i = numTags-1; i >=0; i--) { 2552 if (tagCnts[i] & 1) { 2553 /* who would make the selection elided? */ 2554 if ( 2555#ifndef MAC_OSX_TK 2556 !TkpAlwaysShowSelection(textPtr->tkwin) 2557#else 2558 /* Don't show inactive selection in disabled widgets. */ 2559 textPtr->state == TK_STATE_DISABLED 2560#endif 2561 && (tagPtr == textPtr->selTagPtr) 2562 && !(textPtr->flags & GOT_FOCUS)) { 2563 continue; 2564 } 2565 elide = tagPtrs[i]->elide; 2566 break; 2567 } 2568 } 2569 2570 if (LOTSA_TAGS < numTags) { 2571 ckfree((char *) tagCnts); 2572 ckfree((char *) tagPtrs); 2573 } 2574 2575 return elide; 2576} 2577 2578/* 2579 *---------------------------------------------------------------------- 2580 * 2581 * IncCount -- 2582 * 2583 * This is a utility procedure used by TkBTreeGetTags. It 2584 * increments the count for a particular tag, adding a new 2585 * entry for that tag if there wasn't one previously. 2586 * 2587 * Results: 2588 * None. 2589 * 2590 * Side effects: 2591 * The information at *tagInfoPtr may be modified, and the arrays 2592 * may be reallocated to make them larger. 2593 * 2594 *---------------------------------------------------------------------- 2595 */ 2596 2597static void 2598IncCount(tagPtr, inc, tagInfoPtr) 2599 TkTextTag *tagPtr; /* Handle for tag. */ 2600 int inc; /* Amount by which to increment tag count. */ 2601 TagInfo *tagInfoPtr; /* Holds cumulative information about tags; 2602 * increment count here. */ 2603{ 2604 register TkTextTag **tagPtrPtr; 2605 int count; 2606 2607 for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags; 2608 count > 0; tagPtrPtr++, count--) { 2609 if (*tagPtrPtr == tagPtr) { 2610 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc; 2611 return; 2612 } 2613 } 2614 2615 /* 2616 * There isn't currently an entry for this tag, so we have to 2617 * make a new one. If the arrays are full, then enlarge the 2618 * arrays first. 2619 */ 2620 2621 if (tagInfoPtr->numTags == tagInfoPtr->arraySize) { 2622 TkTextTag **newTags; 2623 int *newCounts, newSize; 2624 2625 newSize = 2*tagInfoPtr->arraySize; 2626 newTags = (TkTextTag **) ckalloc((unsigned) 2627 (newSize*sizeof(TkTextTag *))); 2628 memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs, 2629 tagInfoPtr->arraySize * sizeof(TkTextTag *)); 2630 ckfree((char *) tagInfoPtr->tagPtrs); 2631 tagInfoPtr->tagPtrs = newTags; 2632 newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int))); 2633 memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts, 2634 tagInfoPtr->arraySize * sizeof(int)); 2635 ckfree((char *) tagInfoPtr->counts); 2636 tagInfoPtr->counts = newCounts; 2637 tagInfoPtr->arraySize = newSize; 2638 } 2639 2640 tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr; 2641 tagInfoPtr->counts[tagInfoPtr->numTags] = inc; 2642 tagInfoPtr->numTags++; 2643} 2644 2645/* 2646 *---------------------------------------------------------------------- 2647 * 2648 * TkBTreeCheck -- 2649 * 2650 * This procedure runs a set of consistency checks over a B-tree 2651 * and panics if any inconsistencies are found. 2652 * 2653 * Results: 2654 * None. 2655 * 2656 * Side effects: 2657 * If a structural defect is found, the procedure panics with an 2658 * error message. 2659 * 2660 *---------------------------------------------------------------------- 2661 */ 2662 2663void 2664TkBTreeCheck(tree) 2665 TkTextBTree tree; /* Tree to check. */ 2666{ 2667 BTree *treePtr = (BTree *) tree; 2668 register Summary *summaryPtr; 2669 register Node *nodePtr; 2670 register TkTextLine *linePtr; 2671 register TkTextSegment *segPtr; 2672 register TkTextTag *tagPtr; 2673 Tcl_HashEntry *entryPtr; 2674 Tcl_HashSearch search; 2675 int count; 2676 2677 /* 2678 * Make sure that the tag toggle counts and the tag root pointers are OK. 2679 */ 2680 for (entryPtr = Tcl_FirstHashEntry(&treePtr->textPtr->tagTable, &search); 2681 entryPtr != NULL ; entryPtr = Tcl_NextHashEntry(&search)) { 2682 tagPtr = (TkTextTag *) Tcl_GetHashValue(entryPtr); 2683 nodePtr = tagPtr->tagRootPtr; 2684 if (nodePtr == (Node *) NULL) { 2685 if (tagPtr->toggleCount != 0) { 2686 panic("TkBTreeCheck found \"%s\" with toggles (%d) but no root", 2687 tagPtr->name, tagPtr->toggleCount); 2688 } 2689 continue; /* no ranges for the tag */ 2690 } else if (tagPtr->toggleCount == 0) { 2691 panic("TkBTreeCheck found root for \"%s\" with no toggles", 2692 tagPtr->name); 2693 } else if (tagPtr->toggleCount & 1) { 2694 panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)", 2695 tagPtr->name, tagPtr->toggleCount); 2696 } 2697 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 2698 summaryPtr = summaryPtr->nextPtr) { 2699 if (summaryPtr->tagPtr == tagPtr) { 2700 panic("TkBTreeCheck found root node with summary info"); 2701 } 2702 } 2703 count = 0; 2704 if (nodePtr->level > 0) { 2705 for (nodePtr = nodePtr->children.nodePtr ; nodePtr != NULL ; 2706 nodePtr = nodePtr->nextPtr) { 2707 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 2708 summaryPtr = summaryPtr->nextPtr) { 2709 if (summaryPtr->tagPtr == tagPtr) { 2710 count += summaryPtr->toggleCount; 2711 } 2712 } 2713 } 2714 } else { 2715 for (linePtr = nodePtr->children.linePtr ; linePtr != NULL ; 2716 linePtr = linePtr->nextPtr) { 2717 for (segPtr = linePtr->segPtr; segPtr != NULL; 2718 segPtr = segPtr->nextPtr) { 2719 if ((segPtr->typePtr == &tkTextToggleOnType || 2720 segPtr->typePtr == &tkTextToggleOffType) && 2721 segPtr->body.toggle.tagPtr == tagPtr) { 2722 count++; 2723 } 2724 } 2725 } 2726 } 2727 if (count != tagPtr->toggleCount) { 2728 panic("TkBTreeCheck toggleCount (%d) wrong for \"%s\" should be (%d)", 2729 tagPtr->toggleCount, tagPtr->name, count); 2730 } 2731 } 2732 2733 /* 2734 * Call a recursive procedure to do the main body of checks. 2735 */ 2736 2737 nodePtr = treePtr->rootPtr; 2738 CheckNodeConsistency(treePtr->rootPtr); 2739 2740 /* 2741 * Make sure that there are at least two lines in the text and 2742 * that the last line has no characters except a newline. 2743 */ 2744 2745 if (nodePtr->numLines < 2) { 2746 panic("TkBTreeCheck: less than 2 lines in tree"); 2747 } 2748 while (nodePtr->level > 0) { 2749 nodePtr = nodePtr->children.nodePtr; 2750 while (nodePtr->nextPtr != NULL) { 2751 nodePtr = nodePtr->nextPtr; 2752 } 2753 } 2754 linePtr = nodePtr->children.linePtr; 2755 while (linePtr->nextPtr != NULL) { 2756 linePtr = linePtr->nextPtr; 2757 } 2758 segPtr = linePtr->segPtr; 2759 while ((segPtr->typePtr == &tkTextToggleOffType) 2760 || (segPtr->typePtr == &tkTextRightMarkType) 2761 || (segPtr->typePtr == &tkTextLeftMarkType)) { 2762 /* 2763 * It's OK to toggle a tag off in the last line, but 2764 * not to start a new range. It's also OK to have marks 2765 * in the last line. 2766 */ 2767 2768 segPtr = segPtr->nextPtr; 2769 } 2770 if (segPtr->typePtr != &tkTextCharType) { 2771 panic("TkBTreeCheck: last line has bogus segment type"); 2772 } 2773 if (segPtr->nextPtr != NULL) { 2774 panic("TkBTreeCheck: last line has too many segments"); 2775 } 2776 if (segPtr->size != 1) { 2777 panic("TkBTreeCheck: last line has wrong # characters: %d", 2778 segPtr->size); 2779 } 2780 if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) { 2781 panic("TkBTreeCheck: last line had bad value: %s", 2782 segPtr->body.chars); 2783 } 2784} 2785 2786/* 2787 *---------------------------------------------------------------------- 2788 * 2789 * CheckNodeConsistency -- 2790 * 2791 * This procedure is called as part of consistency checking for 2792 * B-trees: it checks several aspects of a node and also runs 2793 * checks recursively on the node's children. 2794 * 2795 * Results: 2796 * None. 2797 * 2798 * Side effects: 2799 * If anything suspicious is found in the tree structure, the 2800 * procedure panics. 2801 * 2802 *---------------------------------------------------------------------- 2803 */ 2804 2805static void 2806CheckNodeConsistency(nodePtr) 2807 register Node *nodePtr; /* Node whose subtree should be 2808 * checked. */ 2809{ 2810 register Node *childNodePtr; 2811 register Summary *summaryPtr, *summaryPtr2; 2812 register TkTextLine *linePtr; 2813 register TkTextSegment *segPtr; 2814 int numChildren, numLines, toggleCount, minChildren; 2815 2816 if (nodePtr->parentPtr != NULL) { 2817 minChildren = MIN_CHILDREN; 2818 } else if (nodePtr->level > 0) { 2819 minChildren = 2; 2820 } else { 2821 minChildren = 1; 2822 } 2823 if ((nodePtr->numChildren < minChildren) 2824 || (nodePtr->numChildren > MAX_CHILDREN)) { 2825 panic("CheckNodeConsistency: bad child count (%d)", 2826 nodePtr->numChildren); 2827 } 2828 2829 numChildren = 0; 2830 numLines = 0; 2831 if (nodePtr->level == 0) { 2832 for (linePtr = nodePtr->children.linePtr; linePtr != NULL; 2833 linePtr = linePtr->nextPtr) { 2834 if (linePtr->parentPtr != nodePtr) { 2835 panic("CheckNodeConsistency: line doesn't point to parent"); 2836 } 2837 if (linePtr->segPtr == NULL) { 2838 panic("CheckNodeConsistency: line has no segments"); 2839 } 2840 for (segPtr = linePtr->segPtr; segPtr != NULL; 2841 segPtr = segPtr->nextPtr) { 2842 if (segPtr->typePtr->checkProc != NULL) { 2843 (*segPtr->typePtr->checkProc)(segPtr, linePtr); 2844 } 2845 if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity) 2846 && (segPtr->nextPtr != NULL) 2847 && (segPtr->nextPtr->size == 0) 2848 && (segPtr->nextPtr->typePtr->leftGravity)) { 2849 panic("CheckNodeConsistency: wrong segment order for gravity"); 2850 } 2851 if ((segPtr->nextPtr == NULL) 2852 && (segPtr->typePtr != &tkTextCharType)) { 2853 panic("CheckNodeConsistency: line ended with wrong type"); 2854 } 2855 } 2856 numChildren++; 2857 numLines++; 2858 } 2859 } else { 2860 for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL; 2861 childNodePtr = childNodePtr->nextPtr) { 2862 if (childNodePtr->parentPtr != nodePtr) { 2863 panic("CheckNodeConsistency: node doesn't point to parent"); 2864 } 2865 if (childNodePtr->level != (nodePtr->level-1)) { 2866 panic("CheckNodeConsistency: level mismatch (%d %d)", 2867 nodePtr->level, childNodePtr->level); 2868 } 2869 CheckNodeConsistency(childNodePtr); 2870 for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL; 2871 summaryPtr = summaryPtr->nextPtr) { 2872 for (summaryPtr2 = nodePtr->summaryPtr; ; 2873 summaryPtr2 = summaryPtr2->nextPtr) { 2874 if (summaryPtr2 == NULL) { 2875 if (summaryPtr->tagPtr->tagRootPtr == nodePtr) { 2876 break; 2877 } 2878 panic("CheckNodeConsistency: node tag \"%s\" not %s", 2879 summaryPtr->tagPtr->name, 2880 "present in parent summaries"); 2881 } 2882 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) { 2883 break; 2884 } 2885 } 2886 } 2887 numChildren++; 2888 numLines += childNodePtr->numLines; 2889 } 2890 } 2891 if (numChildren != nodePtr->numChildren) { 2892 panic("CheckNodeConsistency: mismatch in numChildren (%d %d)", 2893 numChildren, nodePtr->numChildren); 2894 } 2895 if (numLines != nodePtr->numLines) { 2896 panic("CheckNodeConsistency: mismatch in numLines (%d %d)", 2897 numLines, nodePtr->numLines); 2898 } 2899 2900 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 2901 summaryPtr = summaryPtr->nextPtr) { 2902 if (summaryPtr->tagPtr->toggleCount == summaryPtr->toggleCount) { 2903 panic("CheckNodeConsistency: found unpruned root for \"%s\"", 2904 summaryPtr->tagPtr->name); 2905 } 2906 toggleCount = 0; 2907 if (nodePtr->level == 0) { 2908 for (linePtr = nodePtr->children.linePtr; linePtr != NULL; 2909 linePtr = linePtr->nextPtr) { 2910 for (segPtr = linePtr->segPtr; segPtr != NULL; 2911 segPtr = segPtr->nextPtr) { 2912 if ((segPtr->typePtr != &tkTextToggleOnType) 2913 && (segPtr->typePtr != &tkTextToggleOffType)) { 2914 continue; 2915 } 2916 if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) { 2917 toggleCount ++; 2918 } 2919 } 2920 } 2921 } else { 2922 for (childNodePtr = nodePtr->children.nodePtr; 2923 childNodePtr != NULL; 2924 childNodePtr = childNodePtr->nextPtr) { 2925 for (summaryPtr2 = childNodePtr->summaryPtr; 2926 summaryPtr2 != NULL; 2927 summaryPtr2 = summaryPtr2->nextPtr) { 2928 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) { 2929 toggleCount += summaryPtr2->toggleCount; 2930 } 2931 } 2932 } 2933 } 2934 if (toggleCount != summaryPtr->toggleCount) { 2935 panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)", 2936 toggleCount, summaryPtr->toggleCount); 2937 } 2938 for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL; 2939 summaryPtr2 = summaryPtr2->nextPtr) { 2940 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) { 2941 panic("CheckNodeConsistency: duplicated node tag: %s", 2942 summaryPtr->tagPtr->name); 2943 } 2944 } 2945 } 2946} 2947 2948/* 2949 *---------------------------------------------------------------------- 2950 * 2951 * Rebalance -- 2952 * 2953 * This procedure is called when a node of a B-tree appears to be 2954 * out of balance (too many children, or too few). It rebalances 2955 * that node and all of its ancestors in the tree. 2956 * 2957 * Results: 2958 * None. 2959 * 2960 * Side effects: 2961 * The internal structure of treePtr may change. 2962 * 2963 *---------------------------------------------------------------------- 2964 */ 2965 2966static void 2967Rebalance(treePtr, nodePtr) 2968 BTree *treePtr; /* Tree that is being rebalanced. */ 2969 register Node *nodePtr; /* Node that may be out of balance. */ 2970{ 2971 /* 2972 * Loop over the entire ancestral chain of the node, working up 2973 * through the tree one node at a time until the root node has 2974 * been processed. 2975 */ 2976 2977 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) { 2978 register Node *newPtr, *childPtr; 2979 register TkTextLine *linePtr; 2980 int i; 2981 2982 /* 2983 * Check to see if the node has too many children. If it does, 2984 * then split off all but the first MIN_CHILDREN into a separate 2985 * node following the original one. Then repeat until the 2986 * node has a decent size. 2987 */ 2988 2989 if (nodePtr->numChildren > MAX_CHILDREN) { 2990 while (1) { 2991 /* 2992 * If the node being split is the root node, then make a 2993 * new root node above it first. 2994 */ 2995 2996 if (nodePtr->parentPtr == NULL) { 2997 newPtr = (Node *) ckalloc(sizeof(Node)); 2998 newPtr->parentPtr = NULL; 2999 newPtr->nextPtr = NULL; 3000 newPtr->summaryPtr = NULL; 3001 newPtr->level = nodePtr->level + 1; 3002 newPtr->children.nodePtr = nodePtr; 3003 newPtr->numChildren = 1; 3004 newPtr->numLines = nodePtr->numLines; 3005 RecomputeNodeCounts(newPtr); 3006 treePtr->rootPtr = newPtr; 3007 } 3008 newPtr = (Node *) ckalloc(sizeof(Node)); 3009 newPtr->parentPtr = nodePtr->parentPtr; 3010 newPtr->nextPtr = nodePtr->nextPtr; 3011 nodePtr->nextPtr = newPtr; 3012 newPtr->summaryPtr = NULL; 3013 newPtr->level = nodePtr->level; 3014 newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN; 3015 if (nodePtr->level == 0) { 3016 for (i = MIN_CHILDREN-1, 3017 linePtr = nodePtr->children.linePtr; 3018 i > 0; i--, linePtr = linePtr->nextPtr) { 3019 /* Empty loop body. */ 3020 } 3021 newPtr->children.linePtr = linePtr->nextPtr; 3022 linePtr->nextPtr = NULL; 3023 } else { 3024 for (i = MIN_CHILDREN-1, 3025 childPtr = nodePtr->children.nodePtr; 3026 i > 0; i--, childPtr = childPtr->nextPtr) { 3027 /* Empty loop body. */ 3028 } 3029 newPtr->children.nodePtr = childPtr->nextPtr; 3030 childPtr->nextPtr = NULL; 3031 } 3032 RecomputeNodeCounts(nodePtr); 3033 nodePtr->parentPtr->numChildren++; 3034 nodePtr = newPtr; 3035 if (nodePtr->numChildren <= MAX_CHILDREN) { 3036 RecomputeNodeCounts(nodePtr); 3037 break; 3038 } 3039 } 3040 } 3041 3042 while (nodePtr->numChildren < MIN_CHILDREN) { 3043 register Node *otherPtr; 3044 Node *halfwayNodePtr = NULL; /* Initialization needed only */ 3045 TkTextLine *halfwayLinePtr = NULL; /* to prevent cc warnings. */ 3046 int totalChildren, firstChildren, i; 3047 3048 /* 3049 * Too few children for this node. If this is the root then, 3050 * it's OK for it to have less than MIN_CHILDREN children 3051 * as long as it's got at least two. If it has only one 3052 * (and isn't at level 0), then chop the root node out of 3053 * the tree and use its child as the new root. 3054 */ 3055 3056 if (nodePtr->parentPtr == NULL) { 3057 if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) { 3058 treePtr->rootPtr = nodePtr->children.nodePtr; 3059 treePtr->rootPtr->parentPtr = NULL; 3060 DeleteSummaries(nodePtr->summaryPtr); 3061 ckfree((char *) nodePtr); 3062 } 3063 return; 3064 } 3065 3066 /* 3067 * Not the root. Make sure that there are siblings to 3068 * balance with. 3069 */ 3070 3071 if (nodePtr->parentPtr->numChildren < 2) { 3072 Rebalance(treePtr, nodePtr->parentPtr); 3073 continue; 3074 } 3075 3076 /* 3077 * Find a sibling neighbor to borrow from, and arrange for 3078 * nodePtr to be the earlier of the pair. 3079 */ 3080 3081 if (nodePtr->nextPtr == NULL) { 3082 for (otherPtr = nodePtr->parentPtr->children.nodePtr; 3083 otherPtr->nextPtr != nodePtr; 3084 otherPtr = otherPtr->nextPtr) { 3085 /* Empty loop body. */ 3086 } 3087 nodePtr = otherPtr; 3088 } 3089 otherPtr = nodePtr->nextPtr; 3090 3091 /* 3092 * We're going to either merge the two siblings together 3093 * into one node or redivide the children among them to 3094 * balance their loads. As preparation, join their two 3095 * child lists into a single list and remember the half-way 3096 * point in the list. 3097 */ 3098 3099 totalChildren = nodePtr->numChildren + otherPtr->numChildren; 3100 firstChildren = totalChildren/2; 3101 if (nodePtr->children.nodePtr == NULL) { 3102 nodePtr->children = otherPtr->children; 3103 otherPtr->children.nodePtr = NULL; 3104 otherPtr->children.linePtr = NULL; 3105 } 3106 if (nodePtr->level == 0) { 3107 register TkTextLine *linePtr; 3108 3109 for (linePtr = nodePtr->children.linePtr, i = 1; 3110 linePtr->nextPtr != NULL; 3111 linePtr = linePtr->nextPtr, i++) { 3112 if (i == firstChildren) { 3113 halfwayLinePtr = linePtr; 3114 } 3115 } 3116 linePtr->nextPtr = otherPtr->children.linePtr; 3117 while (i <= firstChildren) { 3118 halfwayLinePtr = linePtr; 3119 linePtr = linePtr->nextPtr; 3120 i++; 3121 } 3122 } else { 3123 register Node *childPtr; 3124 3125 for (childPtr = nodePtr->children.nodePtr, i = 1; 3126 childPtr->nextPtr != NULL; 3127 childPtr = childPtr->nextPtr, i++) { 3128 if (i <= firstChildren) { 3129 if (i == firstChildren) { 3130 halfwayNodePtr = childPtr; 3131 } 3132 } 3133 } 3134 childPtr->nextPtr = otherPtr->children.nodePtr; 3135 while (i <= firstChildren) { 3136 halfwayNodePtr = childPtr; 3137 childPtr = childPtr->nextPtr; 3138 i++; 3139 } 3140 } 3141 3142 /* 3143 * If the two siblings can simply be merged together, do it. 3144 */ 3145 3146 if (totalChildren <= MAX_CHILDREN) { 3147 RecomputeNodeCounts(nodePtr); 3148 nodePtr->nextPtr = otherPtr->nextPtr; 3149 nodePtr->parentPtr->numChildren--; 3150 DeleteSummaries(otherPtr->summaryPtr); 3151 ckfree((char *) otherPtr); 3152 continue; 3153 } 3154 3155 /* 3156 * The siblings can't be merged, so just divide their 3157 * children evenly between them. 3158 */ 3159 3160 if (nodePtr->level == 0) { 3161 otherPtr->children.linePtr = halfwayLinePtr->nextPtr; 3162 halfwayLinePtr->nextPtr = NULL; 3163 } else { 3164 otherPtr->children.nodePtr = halfwayNodePtr->nextPtr; 3165 halfwayNodePtr->nextPtr = NULL; 3166 } 3167 RecomputeNodeCounts(nodePtr); 3168 RecomputeNodeCounts(otherPtr); 3169 } 3170 } 3171} 3172 3173/* 3174 *---------------------------------------------------------------------- 3175 * 3176 * RecomputeNodeCounts -- 3177 * 3178 * This procedure is called to recompute all the counts in a node 3179 * (tags, child information, etc.) by scanning the information in 3180 * its descendants. This procedure is called during rebalancing 3181 * when a node's child structure has changed. 3182 * 3183 * Results: 3184 * None. 3185 * 3186 * Side effects: 3187 * The tag counts for nodePtr are modified to reflect its current 3188 * child structure, as are its numChildren and numLines fields. 3189 * Also, all of the childrens' parentPtr fields are made to point 3190 * to nodePtr. 3191 * 3192 *---------------------------------------------------------------------- 3193 */ 3194 3195static void 3196RecomputeNodeCounts(nodePtr) 3197 register Node *nodePtr; /* Node whose tag summary information 3198 * must be recomputed. */ 3199{ 3200 register Summary *summaryPtr, *summaryPtr2; 3201 register Node *childPtr; 3202 register TkTextLine *linePtr; 3203 register TkTextSegment *segPtr; 3204 TkTextTag *tagPtr; 3205 3206 /* 3207 * Zero out all the existing counts for the node, but don't delete 3208 * the existing Summary records (most of them will probably be reused). 3209 */ 3210 3211 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; 3212 summaryPtr = summaryPtr->nextPtr) { 3213 summaryPtr->toggleCount = 0; 3214 } 3215 nodePtr->numChildren = 0; 3216 nodePtr->numLines = 0; 3217 3218 /* 3219 * Scan through the children, adding the childrens' tag counts into 3220 * the node's tag counts and adding new Summary structures if 3221 * necessary. 3222 */ 3223 3224 if (nodePtr->level == 0) { 3225 for (linePtr = nodePtr->children.linePtr; linePtr != NULL; 3226 linePtr = linePtr->nextPtr) { 3227 nodePtr->numChildren++; 3228 nodePtr->numLines++; 3229 linePtr->parentPtr = nodePtr; 3230 for (segPtr = linePtr->segPtr; segPtr != NULL; 3231 segPtr = segPtr->nextPtr) { 3232 if (((segPtr->typePtr != &tkTextToggleOnType) 3233 && (segPtr->typePtr != &tkTextToggleOffType)) 3234 || !(segPtr->body.toggle.inNodeCounts)) { 3235 continue; 3236 } 3237 tagPtr = segPtr->body.toggle.tagPtr; 3238 for (summaryPtr = nodePtr->summaryPtr; ; 3239 summaryPtr = summaryPtr->nextPtr) { 3240 if (summaryPtr == NULL) { 3241 summaryPtr = (Summary *) ckalloc(sizeof(Summary)); 3242 summaryPtr->tagPtr = tagPtr; 3243 summaryPtr->toggleCount = 1; 3244 summaryPtr->nextPtr = nodePtr->summaryPtr; 3245 nodePtr->summaryPtr = summaryPtr; 3246 break; 3247 } 3248 if (summaryPtr->tagPtr == tagPtr) { 3249 summaryPtr->toggleCount++; 3250 break; 3251 } 3252 } 3253 } 3254 } 3255 } else { 3256 for (childPtr = nodePtr->children.nodePtr; childPtr != NULL; 3257 childPtr = childPtr->nextPtr) { 3258 nodePtr->numChildren++; 3259 nodePtr->numLines += childPtr->numLines; 3260 childPtr->parentPtr = nodePtr; 3261 for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL; 3262 summaryPtr2 = summaryPtr2->nextPtr) { 3263 for (summaryPtr = nodePtr->summaryPtr; ; 3264 summaryPtr = summaryPtr->nextPtr) { 3265 if (summaryPtr == NULL) { 3266 summaryPtr = (Summary *) ckalloc(sizeof(Summary)); 3267 summaryPtr->tagPtr = summaryPtr2->tagPtr; 3268 summaryPtr->toggleCount = summaryPtr2->toggleCount; 3269 summaryPtr->nextPtr = nodePtr->summaryPtr; 3270 nodePtr->summaryPtr = summaryPtr; 3271 break; 3272 } 3273 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) { 3274 summaryPtr->toggleCount += summaryPtr2->toggleCount; 3275 break; 3276 } 3277 } 3278 } 3279 } 3280 } 3281 3282 /* 3283 * Scan through the node's tag records again and delete any Summary 3284 * records that still have a zero count, or that have all the toggles. 3285 * The node with the children that account for all the tags toggles 3286 * have no summary information, and they become the tagRootPtr for the tag. 3287 */ 3288 3289 summaryPtr2 = NULL; 3290 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) { 3291 if (summaryPtr->toggleCount > 0 && 3292 summaryPtr->toggleCount < summaryPtr->tagPtr->toggleCount) { 3293 if (nodePtr->level == summaryPtr->tagPtr->tagRootPtr->level) { 3294 /* 3295 * The tag's root node split and some toggles left. 3296 * The tag root must move up a level. 3297 */ 3298 summaryPtr->tagPtr->tagRootPtr = nodePtr->parentPtr; 3299 } 3300 summaryPtr2 = summaryPtr; 3301 summaryPtr = summaryPtr->nextPtr; 3302 continue; 3303 } 3304 if (summaryPtr->toggleCount == summaryPtr->tagPtr->toggleCount) { 3305 /* 3306 * A node merge has collected all the toggles under one node. 3307 * Push the root down to this level. 3308 */ 3309 summaryPtr->tagPtr->tagRootPtr = nodePtr; 3310 } 3311 if (summaryPtr2 != NULL) { 3312 summaryPtr2->nextPtr = summaryPtr->nextPtr; 3313 ckfree((char *) summaryPtr); 3314 summaryPtr = summaryPtr2->nextPtr; 3315 } else { 3316 nodePtr->summaryPtr = summaryPtr->nextPtr; 3317 ckfree((char *) summaryPtr); 3318 summaryPtr = nodePtr->summaryPtr; 3319 } 3320 } 3321} 3322 3323/* 3324 *---------------------------------------------------------------------- 3325 * 3326 * TkBTreeNumLines -- 3327 * 3328 * This procedure returns a count of the number of lines of 3329 * text present in a given B-tree. 3330 * 3331 * Results: 3332 * The return value is a count of the number of usable lines 3333 * in tree (i.e. it doesn't include the dummy line that is just 3334 * used to mark the end of the tree). 3335 * 3336 * Side effects: 3337 * None. 3338 * 3339 *---------------------------------------------------------------------- 3340 */ 3341 3342int 3343TkBTreeNumLines(tree) 3344 TkTextBTree tree; /* Information about tree. */ 3345{ 3346 BTree *treePtr = (BTree *) tree; 3347 return treePtr->rootPtr->numLines - 1; 3348} 3349 3350/* 3351 *-------------------------------------------------------------- 3352 * 3353 * CharSplitProc -- 3354 * 3355 * This procedure implements splitting for character segments. 3356 * 3357 * Results: 3358 * The return value is a pointer to a chain of two segments 3359 * that have the same characters as segPtr except split 3360 * among the two segments. 3361 * 3362 * Side effects: 3363 * Storage for segPtr is freed. 3364 * 3365 *-------------------------------------------------------------- 3366 */ 3367 3368static TkTextSegment * 3369CharSplitProc(segPtr, index) 3370 TkTextSegment *segPtr; /* Pointer to segment to split. */ 3371 int index; /* Position within segment at which 3372 * to split. */ 3373{ 3374 TkTextSegment *newPtr1, *newPtr2; 3375 3376 newPtr1 = (TkTextSegment *) ckalloc(CSEG_SIZE(index)); 3377 newPtr2 = (TkTextSegment *) ckalloc( 3378 CSEG_SIZE(segPtr->size - index)); 3379 newPtr1->typePtr = &tkTextCharType; 3380 newPtr1->nextPtr = newPtr2; 3381 newPtr1->size = index; 3382 strncpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index); 3383 newPtr1->body.chars[index] = 0; 3384 newPtr2->typePtr = &tkTextCharType; 3385 newPtr2->nextPtr = segPtr->nextPtr; 3386 newPtr2->size = segPtr->size - index; 3387 strcpy(newPtr2->body.chars, segPtr->body.chars + index); 3388 ckfree((char*) segPtr); 3389 return newPtr1; 3390} 3391 3392/* 3393 *-------------------------------------------------------------- 3394 * 3395 * CharCleanupProc -- 3396 * 3397 * This procedure merges adjacent character segments into 3398 * a single character segment, if possible. 3399 * 3400 * Results: 3401 * The return value is a pointer to the first segment in 3402 * the (new) list of segments that used to start with segPtr. 3403 * 3404 * Side effects: 3405 * Storage for the segments may be allocated and freed. 3406 * 3407 *-------------------------------------------------------------- 3408 */ 3409 3410 /* ARGSUSED */ 3411static TkTextSegment * 3412CharCleanupProc(segPtr, linePtr) 3413 TkTextSegment *segPtr; /* Pointer to first of two adjacent 3414 * segments to join. */ 3415 TkTextLine *linePtr; /* Line containing segments (not 3416 * used). */ 3417{ 3418 TkTextSegment *segPtr2, *newPtr; 3419 3420 segPtr2 = segPtr->nextPtr; 3421 if ((segPtr2 == NULL) || (segPtr2->typePtr != &tkTextCharType)) { 3422 return segPtr; 3423 } 3424 newPtr = (TkTextSegment *) ckalloc(CSEG_SIZE( 3425 segPtr->size + segPtr2->size)); 3426 newPtr->typePtr = &tkTextCharType; 3427 newPtr->nextPtr = segPtr2->nextPtr; 3428 newPtr->size = segPtr->size + segPtr2->size; 3429 strcpy(newPtr->body.chars, segPtr->body.chars); 3430 strcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars); 3431 ckfree((char*) segPtr); 3432 ckfree((char*) segPtr2); 3433 return newPtr; 3434} 3435 3436/* 3437 *-------------------------------------------------------------- 3438 * 3439 * CharDeleteProc -- 3440 * 3441 * This procedure is invoked to delete a character segment. 3442 * 3443 * Results: 3444 * Always returns 0 to indicate that the segment was deleted. 3445 * 3446 * Side effects: 3447 * Storage for the segment is freed. 3448 * 3449 *-------------------------------------------------------------- 3450 */ 3451 3452 /* ARGSUSED */ 3453static int 3454CharDeleteProc(segPtr, linePtr, treeGone) 3455 TkTextSegment *segPtr; /* Segment to delete. */ 3456 TkTextLine *linePtr; /* Line containing segment. */ 3457 int treeGone; /* Non-zero means the entire tree is 3458 * being deleted, so everything must 3459 * get cleaned up. */ 3460{ 3461 ckfree((char*) segPtr); 3462 return 0; 3463} 3464 3465/* 3466 *-------------------------------------------------------------- 3467 * 3468 * CharCheckProc -- 3469 * 3470 * This procedure is invoked to perform consistency checks 3471 * on character segments. 3472 * 3473 * Results: 3474 * None. 3475 * 3476 * Side effects: 3477 * If the segment isn't inconsistent then the procedure 3478 * panics. 3479 * 3480 *-------------------------------------------------------------- 3481 */ 3482 3483 /* ARGSUSED */ 3484static void 3485CharCheckProc(segPtr, linePtr) 3486 TkTextSegment *segPtr; /* Segment to check. */ 3487 TkTextLine *linePtr; /* Line containing segment. */ 3488{ 3489 /* 3490 * Make sure that the segment contains the number of 3491 * characters indicated by its header, and that the last 3492 * segment in a line ends in a newline. Also make sure 3493 * that there aren't ever two character segments adjacent 3494 * to each other: they should be merged together. 3495 */ 3496 3497 if (segPtr->size <= 0) { 3498 panic("CharCheckProc: segment has size <= 0"); 3499 } 3500 if (strlen(segPtr->body.chars) != (size_t) segPtr->size) { 3501 panic("CharCheckProc: segment has wrong size"); 3502 } 3503 if (segPtr->nextPtr == NULL) { 3504 if (segPtr->body.chars[segPtr->size-1] != '\n') { 3505 panic("CharCheckProc: line doesn't end with newline"); 3506 } 3507 } else { 3508 if (segPtr->nextPtr->typePtr == &tkTextCharType) { 3509 panic("CharCheckProc: adjacent character segments weren't merged"); 3510 } 3511 } 3512} 3513 3514/* 3515 *-------------------------------------------------------------- 3516 * 3517 * ToggleDeleteProc -- 3518 * 3519 * This procedure is invoked to delete toggle segments. 3520 * 3521 * Results: 3522 * Returns 1 to indicate that the segment may not be deleted, 3523 * unless the entire B-tree is going away. 3524 * 3525 * Side effects: 3526 * If the tree is going away then the toggle's memory is 3527 * freed; otherwise the toggle counts in nodes above the 3528 * segment get updated. 3529 * 3530 *-------------------------------------------------------------- 3531 */ 3532 3533static int 3534ToggleDeleteProc(segPtr, linePtr, treeGone) 3535 TkTextSegment *segPtr; /* Segment to check. */ 3536 TkTextLine *linePtr; /* Line containing segment. */ 3537 int treeGone; /* Non-zero means the entire tree is 3538 * being deleted, so everything must 3539 * get cleaned up. */ 3540{ 3541 if (treeGone) { 3542 ckfree((char *) segPtr); 3543 return 0; 3544 } 3545 3546 /* 3547 * This toggle is in the middle of a range of characters that's 3548 * being deleted. Refuse to die. We'll be moved to the end of 3549 * the deleted range and our cleanup procedure will be called 3550 * later. Decrement node toggle counts here, and set a flag 3551 * so we'll re-increment them in the cleanup procedure. 3552 */ 3553 3554 if (segPtr->body.toggle.inNodeCounts) { 3555 ChangeNodeToggleCount(linePtr->parentPtr, 3556 segPtr->body.toggle.tagPtr, -1); 3557 segPtr->body.toggle.inNodeCounts = 0; 3558 } 3559 return 1; 3560} 3561 3562/* 3563 *-------------------------------------------------------------- 3564 * 3565 * ToggleCleanupProc -- 3566 * 3567 * This procedure is called when a toggle is part of a line that's 3568 * been modified in some way. It's invoked after the 3569 * modifications are complete. 3570 * 3571 * Results: 3572 * The return value is the head segment in a new list 3573 * that is to replace the tail of the line that used to 3574 * start at segPtr. This allows the procedure to delete 3575 * or modify segPtr. 3576 * 3577 * Side effects: 3578 * Toggle counts in the nodes above the new line will be 3579 * updated if they're not already. Toggles may be collapsed 3580 * if there are duplicate toggles at the same position. 3581 * 3582 *-------------------------------------------------------------- 3583 */ 3584 3585static TkTextSegment * 3586ToggleCleanupProc(segPtr, linePtr) 3587 TkTextSegment *segPtr; /* Segment to check. */ 3588 TkTextLine *linePtr; /* Line that now contains segment. */ 3589{ 3590 TkTextSegment *segPtr2, *prevPtr; 3591 int counts; 3592 3593 /* 3594 * If this is a toggle-off segment, look ahead through the next 3595 * segments to see if there's a toggle-on segment for the same tag 3596 * before any segments with non-zero size. If so then the two 3597 * toggles cancel each other; remove them both. 3598 */ 3599 3600 if (segPtr->typePtr == &tkTextToggleOffType) { 3601 for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr; 3602 (segPtr2 != NULL) && (segPtr2->size == 0); 3603 prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) { 3604 if (segPtr2->typePtr != &tkTextToggleOnType) { 3605 continue; 3606 } 3607 if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) { 3608 continue; 3609 } 3610 counts = segPtr->body.toggle.inNodeCounts 3611 + segPtr2->body.toggle.inNodeCounts; 3612 if (counts != 0) { 3613 ChangeNodeToggleCount(linePtr->parentPtr, 3614 segPtr->body.toggle.tagPtr, -counts); 3615 } 3616 prevPtr->nextPtr = segPtr2->nextPtr; 3617 ckfree((char *) segPtr2); 3618 segPtr2 = segPtr->nextPtr; 3619 ckfree((char *) segPtr); 3620 return segPtr2; 3621 } 3622 } 3623 3624 if (!segPtr->body.toggle.inNodeCounts) { 3625 ChangeNodeToggleCount(linePtr->parentPtr, 3626 segPtr->body.toggle.tagPtr, 1); 3627 segPtr->body.toggle.inNodeCounts = 1; 3628 } 3629 return segPtr; 3630} 3631 3632/* 3633 *-------------------------------------------------------------- 3634 * 3635 * ToggleLineChangeProc -- 3636 * 3637 * This procedure is invoked when a toggle segment is about 3638 * to move from one line to another. 3639 * 3640 * Results: 3641 * None. 3642 * 3643 * Side effects: 3644 * Toggle counts are decremented in the nodes above the line. 3645 * 3646 *-------------------------------------------------------------- 3647 */ 3648 3649static void 3650ToggleLineChangeProc(segPtr, linePtr) 3651 TkTextSegment *segPtr; /* Segment to check. */ 3652 TkTextLine *linePtr; /* Line that used to contain segment. */ 3653{ 3654 if (segPtr->body.toggle.inNodeCounts) { 3655 ChangeNodeToggleCount(linePtr->parentPtr, 3656 segPtr->body.toggle.tagPtr, -1); 3657 segPtr->body.toggle.inNodeCounts = 0; 3658 } 3659} 3660 3661/* 3662 *-------------------------------------------------------------- 3663 * 3664 * ToggleCheckProc -- 3665 * 3666 * This procedure is invoked to perform consistency checks 3667 * on toggle segments. 3668 * 3669 * Results: 3670 * None. 3671 * 3672 * Side effects: 3673 * If a consistency problem is found the procedure panics. 3674 * 3675 *-------------------------------------------------------------- 3676 */ 3677 3678static void 3679ToggleCheckProc(segPtr, linePtr) 3680 TkTextSegment *segPtr; /* Segment to check. */ 3681 TkTextLine *linePtr; /* Line containing segment. */ 3682{ 3683 register Summary *summaryPtr; 3684 int needSummary; 3685 3686 if (segPtr->size != 0) { 3687 panic("ToggleCheckProc: segment had non-zero size"); 3688 } 3689 if (!segPtr->body.toggle.inNodeCounts) { 3690 panic("ToggleCheckProc: toggle counts not updated in nodes"); 3691 } 3692 needSummary = (segPtr->body.toggle.tagPtr->tagRootPtr != linePtr->parentPtr); 3693 for (summaryPtr = linePtr->parentPtr->summaryPtr; ; 3694 summaryPtr = summaryPtr->nextPtr) { 3695 if (summaryPtr == NULL) { 3696 if (needSummary) { 3697 panic("ToggleCheckProc: tag not present in node"); 3698 } else { 3699 break; 3700 } 3701 } 3702 if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) { 3703 if (!needSummary) { 3704 panic("ToggleCheckProc: tag present in root node summary"); 3705 } 3706 break; 3707 } 3708 } 3709} 3710 3711/* 3712 *---------------------------------------------------------------------- 3713 * 3714 * TkBTreeCharsInLine -- 3715 * 3716 * This procedure returns a count of the number of characters 3717 * in a given line. 3718 * 3719 * Results: 3720 * The return value is the character count for linePtr. 3721 * 3722 * Side effects: 3723 * None. 3724 * 3725 *---------------------------------------------------------------------- 3726 */ 3727 3728int 3729TkBTreeCharsInLine(linePtr) 3730 TkTextLine *linePtr; /* Line whose characters should be 3731 * counted. */ 3732{ 3733 TkTextSegment *segPtr; 3734 int count; 3735 3736 count = 0; 3737 for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) { 3738 if (segPtr->typePtr == &tkTextCharType) { 3739 count += Tcl_NumUtfChars(segPtr->body.chars, segPtr->size); 3740 } else { 3741 count += segPtr->size; 3742 } 3743 } 3744 return count; 3745} 3746 3747int 3748TkBTreeBytesInLine(linePtr) 3749 TkTextLine *linePtr; /* Line whose characters should be 3750 * counted. */ 3751{ 3752 TkTextSegment *segPtr; 3753 int count; 3754 3755 count = 0; 3756 for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) { 3757 count += segPtr->size; 3758 } 3759 return count; 3760} 3761