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