/[dtapublic]/to_be_filed/sf_code/esrgpcpj/shared/tk_base/tktextbtree.c
ViewVC logotype

Contents of /to_be_filed/sf_code/esrgpcpj/shared/tk_base/tktextbtree.c

Parent Directory Parent Directory | Revision Log Revision Log


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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25