]> git.zerfleddert.de Git - micropolis/blob - src/tk/tktxbtre.c
src/sim/makefile: Micropolis build fixes for recent macOS
[micropolis] / src / tk / tktxbtre.c
1 /*
2 * tkTextBTree.c --
3 *
4 * This file contains code that manages the B-tree representation
5 * of text for Tk's text widget. The B-tree holds both the text
6 * and tag information related to the text.
7 *
8 * Copyright 1992 Regents of the University of California
9 * Permission to use, copy, modify, and distribute this
10 * software and its documentation for any purpose and without
11 * fee is hereby granted, provided that this copyright
12 * notice appears in all copies. The University of California
13 * makes no representations about the suitability of this
14 * software for any purpose. It is provided "as is" without
15 * express or implied warranty.
16 */
17
18 #ifndef lint
19 static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTextBTree.c,v 1.16 92/08/17 09:13:58 ouster Exp $ SPRITE (Berkeley)";
20 #endif /* not lint */
21
22 #include "tkint.h"
23 #include "tkconfig.h"
24 #include "tktext.h"
25
26
27 /*
28 * The data structure below keeps summary information about one tag as part
29 * of the tag information in a node.
30 */
31
32 typedef struct Summary {
33 TkTextTag *tagPtr; /* Handle for tag. */
34 int toggleCount; /* Number of transitions into or
35 * out of this tag that occur in
36 * the subtree rooted at this node. */
37 struct Summary *nextPtr; /* Next in list of all tags for same
38 * node, or NULL if at end of list. */
39 } Summary;
40
41 /*
42 * The data structure below defines a node in the B-tree representing
43 * all of the lines in a text widget.
44 */
45
46 typedef struct Node {
47 struct Node *parentPtr; /* Pointer to parent node, or NULL if
48 * this is the root. */
49 struct Node *nextPtr; /* Next in list of children of the
50 * same parent node, or NULL for end
51 * of list. */
52 Summary *summaryPtr; /* First in malloc-ed list of info
53 * about tags in this subtree (NULL if
54 * no tag info in the subtree). */
55 int level; /* Level of this node in the B-tree.
56 * 0 refers to the bottom of the tree
57 * (children are lines, not nodes). */
58 union { /* First in linked list of children. */
59 struct Node *nodePtr; /* Used if level > 0. */
60 TkTextLine *linePtr; /* Used if level == 0. */
61 } children;
62 int numChildren; /* Number of children of this node. */
63 int numLines; /* Total number of lines (leaves) in
64 * the subtree rooted here. */
65 } Node;
66
67 /*
68 * Upper and lower bounds on how many children a node may have:
69 * rebalance when either of these limits is exceeded. MAX_CHILDREN
70 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
71 */
72
73 #define MAX_CHILDREN 12
74 #define MIN_CHILDREN 6
75
76 /*
77 * The data structure below defines an entire B-tree.
78 */
79
80 typedef struct BTree {
81 Node *rootPtr; /* Pointer to root of B-tree. */
82 } BTree;
83
84 /*
85 * The structure below is used to pass information between
86 * TkBTreeGetTags and IncCount:
87 */
88
89 typedef struct TagInfo {
90 int numTags; /* Number of tags for which there
91 * is currently information in
92 * tags and counts. */
93 int arraySize; /* Number of entries allocated for
94 * tags and counts. */
95 TkTextTag **tagPtrs; /* Array of tags seen so far.
96 * Malloc-ed. */
97 int *counts; /* Toggle count (so far) for each
98 * entry in tags. Malloc-ed. */
99 } TagInfo;
100
101 /*
102 * Macro to compute the space needed for a line that holds n non-null
103 * characters:
104 */
105
106 #define LINE_SIZE(n) ((unsigned) (sizeof(TkTextLine) - 3 + (n)))
107
108 /*
109 * Variable that indicates whether to enable consistency checks for
110 * debugging.
111 */
112
113 int tkBTreeDebug = 0;
114
115 /*
116 * Forward declarations for procedures defined in this file:
117 */
118
119 static void AddToggleToLine _ANSI_ARGS_((TkTextLine *linePtr,
120 int index, TkTextTag *tagPtr));
121 static void ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
122 TkTextTag *tagPtr, int delta));
123 static void CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
124 static void DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
125 static void DestroyNode _ANSI_ARGS_((Node *nodePtr));
126 static void IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc,
127 TagInfo *tagInfoPtr));
128 static void Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
129 static void RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
130 \f
131 /*
132 *----------------------------------------------------------------------
133 *
134 * TkBTreeCreate --
135 *
136 * This procedure is called to create a new text B-tree.
137 *
138 * Results:
139 * The return value is a pointer to a new B-tree containing
140 * one line with nothing but a newline character.
141 *
142 * Side effects:
143 * Memory is allocated and initialized.
144 *
145 *----------------------------------------------------------------------
146 */
147
148 TkTextBTree
149 TkBTreeCreate()
150 {
151 register BTree *treePtr;
152 register Node *rootPtr;
153 register TkTextLine *linePtr;
154
155 rootPtr = (Node *) ckalloc(sizeof(Node));
156 linePtr = (TkTextLine *) ckalloc(LINE_SIZE(1));
157 rootPtr->parentPtr = NULL;
158 rootPtr->nextPtr = NULL;
159 rootPtr->summaryPtr = NULL;
160 rootPtr->level = 0;
161 rootPtr->children.linePtr = linePtr;
162 rootPtr->numChildren = 1;
163 rootPtr->numLines = 1;
164
165 linePtr->parentPtr = rootPtr;
166 linePtr->nextPtr = NULL;
167 linePtr->annotPtr = NULL;
168 linePtr->numBytes = 1;
169 linePtr->bytes[0] = '\n';
170 linePtr->bytes[1] = 0;
171
172 treePtr = (BTree *) ckalloc(sizeof(BTree));
173 treePtr->rootPtr = rootPtr;
174
175 return (TkTextBTree) treePtr;
176 }
177 \f
178 /*
179 *----------------------------------------------------------------------
180 *
181 * TkBTreeDestroy --
182 *
183 * Delete a B-tree, recycling all of the storage it contains.
184 *
185 * Results:
186 * The tree given by treePtr is deleted. TreePtr should never
187 * again be used.
188 *
189 * Side effects:
190 * Memory is freed.
191 *
192 *----------------------------------------------------------------------
193 */
194
195 void
196 TkBTreeDestroy(tree)
197 TkTextBTree tree; /* Pointer to tree to delete. */
198 {
199 BTree *treePtr = (BTree *) tree;
200
201 DestroyNode(treePtr->rootPtr);
202 ckfree((char *) treePtr);
203 }
204 \f
205 /*
206 *----------------------------------------------------------------------
207 *
208 * DestroyNode --
209 *
210 * This is a recursive utility procedure used during the deletion
211 * of a B-tree.
212 *
213 * Results:
214 * None.
215 *
216 * Side effects:
217 * All the storage for nodePtr and its descendants is freed.
218 *
219 *----------------------------------------------------------------------
220 */
221
222 static void
223 DestroyNode(nodePtr)
224 register Node *nodePtr;
225 {
226 if (nodePtr->level == 0) {
227 register TkTextLine *curPtr, *nextLinePtr;
228 register TkAnnotation *annotPtr, *nextAnnotPtr;
229
230 for (curPtr = nodePtr->children.linePtr; curPtr != NULL; ) {
231 nextLinePtr = curPtr->nextPtr;
232 for (annotPtr = curPtr->annotPtr; annotPtr != NULL; ) {
233 nextAnnotPtr = annotPtr->nextPtr;
234 if (annotPtr->type == TK_ANNOT_TOGGLE) {
235 ckfree((char *) annotPtr);
236 }
237 annotPtr = nextAnnotPtr;
238 }
239 ckfree((char *) curPtr);
240 curPtr = nextLinePtr;
241 }
242 } else {
243 register Node *curPtr, *nextPtr;
244
245 for (curPtr = nodePtr->children.nodePtr; curPtr != NULL; ) {
246 nextPtr = curPtr->nextPtr;
247 DestroyNode(curPtr);
248 curPtr = nextPtr;
249 }
250 }
251 DeleteSummaries(nodePtr->summaryPtr);
252 ckfree((char *) nodePtr);
253 }
254 \f
255 /*
256 *----------------------------------------------------------------------
257 *
258 * DeleteSummaries --
259 *
260 * Free up all of the memory in a list of tag summaries associated
261 * with a node.
262 *
263 * Results:
264 * None.
265 *
266 * Side effects:
267 * Storage is released.
268 *
269 *----------------------------------------------------------------------
270 */
271
272 static void
273 DeleteSummaries(summaryPtr)
274 register Summary *summaryPtr; /* First in list of node's tag
275 * summaries. */
276 {
277 register Summary *nextPtr;
278 while (summaryPtr != NULL) {
279 nextPtr = summaryPtr->nextPtr;
280 ckfree((char *) summaryPtr);
281 summaryPtr = nextPtr;
282 }
283 }
284 \f
285 /*
286 *----------------------------------------------------------------------
287 *
288 * TkBTreeInsertChars --
289 *
290 * Insert characters at a given position in a B-tree.
291 *
292 * Results:
293 * None.
294 *
295 * Side effects:
296 * NumBytes characters are added to the B-tree at the given
297 * character position. This can cause the structure of the
298 * B-tree to change.
299 *
300 *----------------------------------------------------------------------
301 */
302
303 void
304 TkBTreeInsertChars(tree, linePtr, ch, string)
305 TkTextBTree tree; /* B-tree in which to insert. */
306 register TkTextLine *linePtr; /* Pointer to line in which to
307 * insert. */
308 int ch; /* Index of character before which
309 * to insert. Must not be after
310 * last character in line.*/
311 char *string; /* Pointer to bytes to insert (may
312 * contain newlines, must be null-
313 * terminated). */
314 {
315 BTree *treePtr = (BTree *) tree;
316 register Node *nodePtr;
317 register TkAnnotation *annotPtr;
318 TkTextLine *prevPtr;
319 int newChunkLength; /* # chars in current line being
320 * inserted. */
321 register char *eol; /* Pointer to last character in
322 * current line being inserted. */
323 int changeToLineCount; /* Counts change to total number of
324 * lines in file. */
325 TkAnnotation *afterPtr; /* List of annotations that occur
326 * at or after the insertion point
327 * in the line of the insertion. */
328 int prefixLength, suffixLength, totalLength;
329 register TkTextLine *newPtr;
330
331 /*
332 * Find the line just before the one where the insertion will occur
333 * but with the same parent node (if there is one). This is needed
334 * so we can replace the insertion line with a new one. Remove this
335 * line from the list for its parent, since it's going to be discarded
336 * when we're all done).
337 */
338
339 nodePtr = linePtr->parentPtr;
340 prevPtr = nodePtr->children.linePtr;
341 if (prevPtr == linePtr) {
342 prevPtr = NULL;
343 nodePtr->children.linePtr = linePtr->nextPtr;
344 } else {
345 for ( ; prevPtr->nextPtr != linePtr; prevPtr = prevPtr->nextPtr) {
346 /* Empty loop body. */
347 }
348 prevPtr->nextPtr = linePtr->nextPtr;
349 }
350
351 /*
352 * Break up the annotations for the insertion line into two pieces:
353 * those before the insertion point, and those at or after the insertion
354 * point.
355 */
356
357 afterPtr = NULL;
358 if ((linePtr->annotPtr != NULL) && (linePtr->annotPtr->ch >= ch)) {
359 afterPtr = linePtr->annotPtr;
360 linePtr->annotPtr = NULL;
361 } else {
362 for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
363 annotPtr = annotPtr->nextPtr) {
364 if ((annotPtr->nextPtr != NULL)
365 && (annotPtr->nextPtr->ch >= ch)) {
366 afterPtr = annotPtr->nextPtr;
367 annotPtr->nextPtr = NULL;
368 break;
369 }
370 }
371 }
372
373 /*
374 * Chop the string up into lines and insert each line individually.
375 */
376
377 changeToLineCount = -1;
378 prefixLength = ch;
379 while (1) {
380 for (newChunkLength = 0, eol = string; *eol != 0; eol++) {
381 newChunkLength++;
382 if (*eol == '\n') {
383 break;
384 }
385 }
386
387 /*
388 * Create a new line consisting of up to three parts: a prefix
389 * from linePtr, some material from string, and a suffix from
390 * linePtr.
391 */
392
393 if ((newChunkLength == 0) || (*eol != '\n')) {
394 suffixLength = linePtr->numBytes - ch;
395 } else {
396 suffixLength = 0;
397 }
398 totalLength = prefixLength + newChunkLength + suffixLength;
399 newPtr = (TkTextLine *) ckalloc(LINE_SIZE(totalLength));
400 newPtr->parentPtr = nodePtr;
401 if (prevPtr == NULL) {
402 newPtr->nextPtr = nodePtr->children.linePtr;
403 nodePtr->children.linePtr = newPtr;
404 } else {
405 newPtr->nextPtr = prevPtr->nextPtr;
406 prevPtr->nextPtr = newPtr;
407 }
408 if (linePtr->annotPtr != NULL) {
409 newPtr->annotPtr = linePtr->annotPtr;
410 for (annotPtr = newPtr->annotPtr; annotPtr != NULL;
411 annotPtr = annotPtr->nextPtr) {
412 annotPtr->linePtr = newPtr;
413 }
414 linePtr->annotPtr = NULL;
415 } else {
416 newPtr->annotPtr = NULL;
417 }
418 newPtr->numBytes = totalLength;
419 if (prefixLength != 0) {
420 memcpy((VOID *) newPtr->bytes, (VOID *) linePtr->bytes,
421 prefixLength);
422 }
423 if (newChunkLength != 0) {
424 memcpy((VOID *) (newPtr->bytes + prefixLength), (VOID *) string,
425 newChunkLength);
426 }
427 if (suffixLength != 0) {
428 memcpy((VOID *) (newPtr->bytes + prefixLength + newChunkLength),
429 (VOID *) (linePtr->bytes + ch), suffixLength);
430 }
431 newPtr->bytes[totalLength] = 0;
432 changeToLineCount += 1;
433
434 /*
435 * Quit after the suffix has been output (there is always at least
436 * one character of suffix: the newline). Before jumping out of the
437 * loop, put back the annotations that pertain to the suffix.
438 * Careful! If no newlines were inserted, there could already be
439 * annotations at the beginning of the line; add back to the end.
440 */
441
442 if (suffixLength != 0) {
443 if (newPtr->annotPtr == NULL) {
444 newPtr->annotPtr = afterPtr;
445 } else {
446 for (annotPtr = newPtr->annotPtr; annotPtr->nextPtr != NULL;
447 annotPtr = annotPtr->nextPtr) {
448 /* Empty loop body. */
449 }
450 annotPtr->nextPtr = afterPtr;
451 }
452 for (annotPtr = afterPtr; annotPtr != NULL;
453 annotPtr = annotPtr->nextPtr) {
454 annotPtr->linePtr = newPtr;
455 annotPtr->ch += prefixLength+newChunkLength-ch;
456 }
457 break;
458 }
459
460 /*
461 * Advance to insert the next line chunk.
462 */
463
464 string += newChunkLength;
465 prefixLength = 0;
466 prevPtr = newPtr;
467 }
468
469 /*
470 * Increment the line counts in all the parent nodes of the insertion
471 * point, then rebalance the tree if necessary.
472 */
473
474 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
475 nodePtr->numLines += changeToLineCount;
476 }
477 nodePtr = linePtr->parentPtr;
478 nodePtr->numChildren += changeToLineCount;
479 if (nodePtr->numChildren > MAX_CHILDREN) {
480 Rebalance(treePtr, nodePtr);
481 }
482
483 ckfree((char *) linePtr);
484 if (tkBTreeDebug) {
485 TkBTreeCheck(tree);
486 }
487 }
488 \f
489 /*
490 *----------------------------------------------------------------------
491 *
492 * TkBTreeDeleteChars --
493 *
494 * Delete a range of characters from a B-tree.
495 *
496 * Results:
497 * None.
498 *
499 * Side effects:
500 * Information is deleted from the B-tree. This can cause the
501 * internal structure of the B-tree to change. Note: the two
502 * lines given by line1Ptr and line2Ptr will be replaced with
503 * a single line containing the undeleted parts of the original
504 * lines. This could potentially result in an empty line;
505 * normally the caller should adjust the deletion range to prevent
506 * this sort of behavior.
507 *
508 *----------------------------------------------------------------------
509 */
510
511 void
512 TkBTreeDeleteChars(tree, line1Ptr, ch1, line2Ptr, ch2)
513 TkTextBTree tree; /* B-tree in which to delete. */
514 register TkTextLine *line1Ptr; /* Line containing first character
515 * to delete. */
516 int ch1; /* Index within linePtr1 of first
517 * character to delete. */
518 register TkTextLine *line2Ptr; /* Line containing character just
519 * after last one to delete. */
520 int ch2; /* Index within linePtr2 of character
521 * just after last one to delete. */
522 {
523 BTree *treePtr = (BTree *) tree;
524 TkTextLine *linePtr, *nextPtr, *prevLinePtr;
525 Node *nodePtr, *parentPtr, *nextNodePtr;
526 TkAnnotation *annotPtr, *annotPtr2;
527 int ch;
528 int linesDeleted; /* Counts lines deleted from current
529 * level-0 node. */
530
531 /*
532 * Work through the tree deleting all of the lines between line1Ptr
533 * and line2Ptr (but don't delete line1Ptr or line2Ptr yet). Also
534 * delete any nodes in the B-tree that become empty because of
535 * this process.
536 */
537
538 linePtr = line1Ptr->nextPtr;
539 nodePtr = line1Ptr->parentPtr;
540 if (line1Ptr == line2Ptr) {
541 goto middleLinesDeleted;
542 }
543 while (1) {
544
545 /*
546 * Delete all relevant lines within the same level-0 node.
547 */
548
549 linesDeleted = 0;
550 while ((linePtr != line2Ptr) && (linePtr != NULL)) {
551 /*
552 * Move any annotations in this line to the end of the
553 * deletion range. If both the starting and ending toggle
554 * for a tagged range get moved, they'll cancel each other
555 * automatically and be dropped, which is the right behavior.
556 */
557
558 for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
559 annotPtr = annotPtr2) {
560 if (annotPtr->type == TK_ANNOT_TOGGLE) {
561 AddToggleToLine(line2Ptr, ch2, annotPtr->info.tagPtr);
562 ChangeNodeToggleCount(nodePtr, annotPtr->info.tagPtr, -1);
563 annotPtr2 = annotPtr->nextPtr;
564 ckfree((char *) annotPtr);
565 } else {
566 annotPtr2 = annotPtr->nextPtr;
567 TkBTreeRemoveAnnotation(annotPtr);
568 annotPtr->linePtr = line2Ptr;
569 annotPtr->ch = ch2;
570 TkBTreeAddAnnotation(annotPtr);
571 }
572 }
573 nextPtr = linePtr->nextPtr;
574 ckfree((char *) linePtr);
575 linesDeleted++;
576 linePtr = nextPtr;
577 }
578 if (nodePtr == line1Ptr->parentPtr) {
579 line1Ptr->nextPtr = linePtr;
580 } else {
581 nodePtr->children.linePtr = linePtr;
582 }
583 for (parentPtr = nodePtr; parentPtr != NULL;
584 parentPtr = parentPtr->parentPtr) {
585 parentPtr->numLines -= linesDeleted;
586 }
587 nodePtr->numChildren -= linesDeleted;
588 if (linePtr == line2Ptr) {
589 break;
590 }
591
592 /*
593 * Find the next level-0 node to visit, and its first line (but
594 * remember the current node so we can come back to delete it if
595 * it's empty).
596 */
597
598 nextNodePtr = nodePtr;
599 while (nextNodePtr->nextPtr == NULL) {
600 nextNodePtr = nextNodePtr->parentPtr;
601 }
602 nextNodePtr = nextNodePtr->nextPtr;
603 while (nextNodePtr->level > 0) {
604 nextNodePtr = nextNodePtr->children.nodePtr;
605 }
606 linePtr = nextNodePtr->children.linePtr;
607
608 /*
609 * Now go back to the node we just left and delete it if
610 * it's empty, along with any of its ancestors that are
611 * empty. It may seem funny to go back like this, but it's
612 * simpler to find the next place to visit before modifying
613 * the tree structure.
614 */
615
616 while (nodePtr->numChildren == 0) {
617 parentPtr = nodePtr->parentPtr;
618 if (parentPtr->children.nodePtr == nodePtr) {
619 parentPtr->children.nodePtr = nodePtr->nextPtr;
620 } else {
621 Node *prevPtr;
622
623 for (prevPtr = parentPtr->children.nodePtr;
624 prevPtr->nextPtr != nodePtr;
625 prevPtr = prevPtr->nextPtr) {
626 }
627 prevPtr->nextPtr = nodePtr->nextPtr;
628 }
629 parentPtr->numChildren--;
630 DeleteSummaries(nodePtr->summaryPtr);
631 ckfree((char *) nodePtr);
632 nodePtr = parentPtr;
633 }
634 nodePtr = nextNodePtr;
635 }
636
637 /*
638 * Make a new line that consists of the first part of the first
639 * line of the deletion range and the last part of the last line
640 * of the deletion range.
641 */
642
643 middleLinesDeleted:
644 nodePtr = line1Ptr->parentPtr;
645 linePtr = (TkTextLine *) ckalloc(LINE_SIZE(ch1 + line2Ptr->numBytes - ch2));
646 linePtr->parentPtr = nodePtr;
647 linePtr->nextPtr = line1Ptr->nextPtr;
648 linePtr->annotPtr = NULL;
649 linePtr->numBytes = ch1 + line2Ptr->numBytes - ch2;
650 if (ch1 != 0) {
651 memcpy((VOID *) linePtr->bytes, (VOID *) line1Ptr->bytes, ch1);
652 }
653 strcpy(linePtr->bytes + ch1, line2Ptr->bytes + ch2);
654
655 /*
656 * Process the annotations for the starting and ending lines. Enter
657 * a new annotation on linePtr (the joined line) for each of these
658 * annotations, then delete the originals. The code below is a little
659 * tricky (e.g. the "break" in the first loop) to handle the case where
660 * the starting and ending lines are the same.
661 */
662
663 for (annotPtr = line1Ptr->annotPtr; annotPtr != NULL;
664 annotPtr = line1Ptr->annotPtr) {
665 if (annotPtr->ch <= ch1) {
666 ch = annotPtr->ch;
667 } else {
668 if (line1Ptr == line2Ptr) {
669 break;
670 }
671 ch = ch1;
672 }
673 line1Ptr->annotPtr = annotPtr->nextPtr;
674 if (annotPtr->type == TK_ANNOT_TOGGLE) {
675 AddToggleToLine(linePtr, ch, annotPtr->info.tagPtr);
676 ChangeNodeToggleCount(line1Ptr->parentPtr, annotPtr->info.tagPtr,
677 -1);
678 ckfree((char *) annotPtr);
679 } else {
680 annotPtr->linePtr = linePtr;
681 annotPtr->ch = ch;
682 TkBTreeAddAnnotation(annotPtr);
683 }
684 }
685 for (annotPtr = line2Ptr->annotPtr; annotPtr != NULL;
686 annotPtr = line2Ptr->annotPtr) {
687 if (annotPtr->ch >= ch2) {
688 ch = annotPtr->ch - ch2 + ch1;
689 } else {
690 ch = ch1;
691 }
692 line2Ptr->annotPtr = annotPtr->nextPtr;
693 if (annotPtr->type == TK_ANNOT_TOGGLE) {
694 AddToggleToLine(linePtr, ch, annotPtr->info.tagPtr);
695 ChangeNodeToggleCount(line2Ptr->parentPtr, annotPtr->info.tagPtr,
696 -1);
697 ckfree((char *) annotPtr);
698 } else {
699 annotPtr->linePtr = linePtr;
700 annotPtr->ch = ch;
701 TkBTreeAddAnnotation(annotPtr);
702 }
703 }
704
705 /*
706 * Delete the original starting and stopping lines (don't forget
707 * that the annotations have already been deleted) and insert the
708 * new line in place of line1Ptr.
709 */
710
711 nodePtr = line1Ptr->parentPtr;
712 if (nodePtr->children.linePtr == line1Ptr) {
713 nodePtr->children.linePtr = linePtr;
714 } else {
715 for (prevLinePtr = nodePtr->children.linePtr;
716 prevLinePtr->nextPtr != line1Ptr;
717 prevLinePtr = prevLinePtr->nextPtr) {
718 /* Empty loop body. */
719 }
720 prevLinePtr->nextPtr = linePtr;
721 }
722 ckfree((char *) line1Ptr);
723 nodePtr = line2Ptr->parentPtr;
724 if (line2Ptr != line1Ptr) {
725 if (nodePtr->children.linePtr == line2Ptr) {
726 nodePtr->children.linePtr = line2Ptr->nextPtr;
727 } else {
728 for (prevLinePtr = nodePtr->children.linePtr;
729 prevLinePtr->nextPtr != line2Ptr;
730 prevLinePtr = prevLinePtr->nextPtr) {
731 /* Empty loop body. */
732 }
733 prevLinePtr->nextPtr = line2Ptr->nextPtr;
734 }
735 ckfree((char *) line2Ptr);
736 for (parentPtr = nodePtr; parentPtr != NULL;
737 parentPtr = parentPtr->parentPtr) {
738 parentPtr->numLines--;
739 }
740 nodePtr->numChildren--;
741 }
742
743 /*
744 * Rebalance the tree, starting from each of the endpoints of the
745 * deletion range. This code is a tricky, because the act of
746 * rebalancing the parent of one endpoint can cause the parent of
747 * the other endpoint to be reallocated. The only thing it's safe
748 * to hold onto is a pointer to a line. Thus, rebalance line2Ptr's
749 * parent first, then use linePtr find the second parent to rebalance
750 * second.
751 */
752
753 if (nodePtr != linePtr->parentPtr) {
754 Rebalance(treePtr, nodePtr);
755 }
756 Rebalance(treePtr, linePtr->parentPtr);
757 if (tkBTreeDebug) {
758 TkBTreeCheck(tree);
759 }
760 }
761 \f
762 /*
763 *----------------------------------------------------------------------
764 *
765 * TkBTreeTag --
766 *
767 * Turn a given tag on or off for a given range of characters in
768 * a B-tree of text.
769 *
770 * Results:
771 * None.
772 *
773 * Side effects:
774 * The given tag is added to the given range of characters
775 * in the tree or removed from all those characters, depending
776 * on the "add" argument.
777 *
778 *----------------------------------------------------------------------
779 */
780
781 void
782 TkBTreeTag(tree, line1, ch1, line2, ch2, tagPtr, add)
783 TkTextBTree tree; /* B-tree in which to add tag
784 * information. */
785 int line1, ch1; /* Position of first character to
786 * tag. */
787 int line2, ch2; /* Position of character just after
788 * last one to tag. */
789 TkTextTag *tagPtr; /* Tag to associate with the range
790 * of characters. */
791 int add; /* One means add tag to the given
792 * range of characters; zero means
793 * remove the tag from the range. */
794 {
795 BTree *treePtr = (BTree *) tree;
796 register TkTextLine *line1Ptr, *line2Ptr;
797 TkTextSearch search;
798 int oldState;
799
800 /*
801 * Find the lines containing the first and last characters to be tagged,
802 * and adjust the starting and stopping locations if they don't already
803 * point within lines. If the range would have started or stopped at the
804 * end of a line, round it up to the beginning of the next line (right
805 * now this restriction keeps the final newline from being tagged).
806 */
807
808 if (line1 < 0) {
809 line1 = 0;
810 ch1 = 0;
811 }
812 line1Ptr = TkBTreeFindLine(tree, line1);
813 if (line1Ptr == NULL) {
814 return;
815 }
816 if (ch1 >= line1Ptr->numBytes) {
817 TkTextLine *nextLinePtr;
818
819 nextLinePtr = TkBTreeNextLine(line1Ptr);
820 if (nextLinePtr == NULL) {
821 return;
822 } else {
823 line1Ptr = nextLinePtr;
824 line1++;
825 ch1 = 0;
826 }
827 }
828 if (line2 < 0) {
829 return;
830 }
831 line2Ptr = TkBTreeFindLine(tree, line2);
832 if (line2Ptr == NULL) {
833 line2Ptr = TkBTreeFindLine(tree, treePtr->rootPtr->numLines-1);
834 ch2 = line2Ptr->numBytes-1;
835 }
836 if (ch2 >= line2Ptr->numBytes) {
837 TkTextLine *nextLinePtr;
838
839 nextLinePtr = TkBTreeNextLine(line2Ptr);
840 if (nextLinePtr == NULL) {
841 ch2 = line2Ptr->numBytes-1;
842 } else {
843 line2Ptr = nextLinePtr;
844 line2++;
845 ch2 = 0;
846 }
847 }
848
849 /*
850 * See if the tag is already present or absent at the start of the
851 * range. If the state doesn't already match what we want then add
852 * a toggle there.
853 */
854
855 oldState = TkBTreeCharTagged(line1Ptr, ch1, tagPtr);
856 if ((add != 0) ^ oldState) {
857 AddToggleToLine(line1Ptr, ch1, tagPtr);
858 }
859
860 /*
861 * Scan the range of characters covered by the change and delete
862 * any existing tag transitions except those on the first and
863 * last characters. Keep track of whether the old state just before
864 * the last character (not including any tags on it) is what we
865 * want now; if not, then add a tag toggle there.
866 */
867
868 TkBTreeStartSearch(tree, line1, ch1+1, line2, ch2, tagPtr, &search);
869 while (TkBTreeNextTag(&search)) {
870 if ((search.linePtr == line2Ptr) && (search.ch1 == ch2)) {
871 break;
872 }
873 oldState ^= 1;
874 AddToggleToLine(search.linePtr, search.ch1, tagPtr);
875 }
876 if ((add != 0) ^ oldState) {
877 AddToggleToLine(line2Ptr, ch2, tagPtr);
878 }
879
880 if (tkBTreeDebug) {
881 TkBTreeCheck(tree);
882 }
883 }
884 \f
885 /*
886 *----------------------------------------------------------------------
887 *
888 * TkBTreeAddAnnotation --
889 *
890 * Given a filled in annotation, this procedure links it into
891 * a B-tree structure so that it will track changes to the B-tree.
892 *
893 * Results:
894 * None.
895 *
896 * Side effects:
897 * AnnotPtr will be linked into its tree. Note: the storage for
898 * annotPtr is assumed to have been malloc'ed by the caller.
899 *
900 *----------------------------------------------------------------------
901 */
902
903 /* ARGSUSED */
904 void
905 TkBTreeAddAnnotation(annotPtr)
906 TkAnnotation *annotPtr; /* Pointer to annotation. The caller must
907 * have filled in all the fields except the
908 * "nextPtr" field. The type should NOT be
909 * TK_ANNOT_TOGGLE; these annotations are
910 * managed by the TkBTreeTag procedure. */
911 {
912 register TkAnnotation *annotPtr2, *prevPtr;
913
914 for (prevPtr = NULL, annotPtr2 = annotPtr->linePtr->annotPtr;
915 annotPtr2 != NULL;
916 prevPtr = annotPtr2, annotPtr2 = annotPtr2->nextPtr) {
917 if (annotPtr2->ch > annotPtr->ch) {
918 break;
919 }
920 }
921 if (prevPtr == NULL) {
922 annotPtr->nextPtr = annotPtr->linePtr->annotPtr;
923 annotPtr->linePtr->annotPtr = annotPtr;
924 } else {
925 annotPtr->nextPtr = prevPtr->nextPtr;
926 prevPtr->nextPtr = annotPtr;
927 }
928 }
929 \f
930 /*
931 *----------------------------------------------------------------------
932 *
933 * TkBTreeRemoveAnnotation --
934 *
935 * This procedure unlinks an annotation from a B-tree so that
936 * the annotation will no longer be managed by the B-tree code.
937 *
938 * Results:
939 * None.
940 *
941 * Side effects:
942 * AnnotPtr will be unlinked from its tree. Note: it is up to the
943 * caller to free the storage for annotPtr, if that is desired.
944 *
945 *----------------------------------------------------------------------
946 */
947
948 /* ARGSUSED */
949 void
950 TkBTreeRemoveAnnotation(annotPtr)
951 TkAnnotation *annotPtr; /* Pointer to annotation, which must
952 * have been linked into tree by a previous
953 * call to TkBTreeAddAnnotation. */
954 {
955 register TkAnnotation *prevPtr;
956
957 if (annotPtr->linePtr->annotPtr == annotPtr) {
958 annotPtr->linePtr->annotPtr = annotPtr->nextPtr;
959 } else {
960 for (prevPtr = annotPtr->linePtr->annotPtr;
961 /* BUG: fixed by dhopkins, prevPtr was null!
962 prevPtr->nextPtr != annotPtr;
963 */
964 (prevPtr != NULL) && (prevPtr->nextPtr != annotPtr);
965 prevPtr = prevPtr->nextPtr) {
966 /* Empty loop body. */
967 }
968 if (prevPtr != NULL) { /* Bullet proofing by dhopkins */
969 prevPtr->nextPtr = annotPtr->nextPtr;
970 }
971 }
972 }
973 \f
974 /*
975 *----------------------------------------------------------------------
976 *
977 * TkBTreeFindLine --
978 *
979 * Find a particular line in a B-tree based on its line number.
980 *
981 * Results:
982 * The return value is a pointer to the line structure for the
983 * line whose index is "line", or NULL if no such line exists.
984 *
985 * Side effects:
986 * None.
987 *
988 *----------------------------------------------------------------------
989 */
990
991 TkTextLine *
992 TkBTreeFindLine(tree, line)
993 TkTextBTree tree; /* B-tree in which to find line. */
994 int line; /* Index of desired line. */
995 {
996 BTree *treePtr = (BTree *) tree;
997 register Node *nodePtr;
998 register TkTextLine *linePtr;
999 int linesLeft;
1000
1001 nodePtr = treePtr->rootPtr;
1002 linesLeft = line;
1003 if ((line < 0) || (line >= nodePtr->numLines)) {
1004 return NULL;
1005 }
1006
1007 /*
1008 * Work down through levels of the tree until a node is found at
1009 * level 0.
1010 */
1011
1012 while (nodePtr->level != 0) {
1013 for (nodePtr = nodePtr->children.nodePtr;
1014 nodePtr->numLines <= linesLeft;
1015 nodePtr = nodePtr->nextPtr) {
1016 if (nodePtr == NULL) {
1017 panic("TkBTreeFindLine ran out of nodes");
1018 }
1019 linesLeft -= nodePtr->numLines;
1020 }
1021 }
1022
1023 /*
1024 * Work through the lines attached to the level-0 node.
1025 */
1026
1027 for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
1028 linePtr = linePtr->nextPtr) {
1029 if (linePtr == NULL) {
1030 panic("TkBTreeFindLine ran out of lines");
1031 }
1032 linesLeft -= 1;
1033 }
1034 return linePtr;
1035 }
1036 \f
1037 /*
1038 *----------------------------------------------------------------------
1039 *
1040 * TkBTreeNextLine --
1041 *
1042 * Given an existing line in a B-tree, this procedure locates the
1043 * next line in the B-tree. This procedure is used for scanning
1044 * through the B-tree.
1045 *
1046 * Results:
1047 * The return value is a pointer to the line that immediately
1048 * follows linePtr, or NULL if there is no such line.
1049 *
1050 * Side effects:
1051 * None.
1052 *
1053 *----------------------------------------------------------------------
1054 */
1055
1056 TkTextLine *
1057 TkBTreeNextLine(linePtr)
1058 register TkTextLine *linePtr; /* Pointer to existing line in
1059 * B-tree. */
1060 {
1061 register Node *nodePtr;
1062
1063 if (linePtr->nextPtr != NULL) {
1064 return linePtr->nextPtr;
1065 }
1066
1067 /*
1068 * This was the last line associated with the particular parent node.
1069 * Search up the tree for the next node, then search down from that
1070 * node to find the first line,
1071 */
1072
1073 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
1074 if (nodePtr->nextPtr != NULL) {
1075 nodePtr = nodePtr->nextPtr;
1076 break;
1077 }
1078 if (nodePtr->parentPtr == NULL) {
1079 return (TkTextLine *) NULL;
1080 }
1081 }
1082 while (nodePtr->level > 0) {
1083 nodePtr = nodePtr->children.nodePtr;
1084 }
1085 return nodePtr->children.linePtr;
1086 }
1087 \f
1088 /*
1089 *----------------------------------------------------------------------
1090 *
1091 * TkBTreeLineIndex --
1092 *
1093 * Given a pointer to a line in a B-tree, return the numerical
1094 * index of that line.
1095 *
1096 * Results:
1097 * The result is the index of linePtr within the tree, where 0
1098 * corresponds to the first line in the tree.
1099 *
1100 * Side effects:
1101 * None.
1102 *
1103 *----------------------------------------------------------------------
1104 */
1105
1106 int
1107 TkBTreeLineIndex(linePtr)
1108 TkTextLine *linePtr; /* Pointer to existing line in
1109 * B-tree. */
1110 {
1111 register TkTextLine *linePtr2;
1112 register Node *nodePtr, *parentPtr, *nodePtr2;
1113 int index;
1114
1115 /*
1116 * First count how many lines precede this one in its level-0
1117 * node.
1118 */
1119
1120 nodePtr = linePtr->parentPtr;
1121 index = 0;
1122 for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
1123 linePtr2 = linePtr2->nextPtr) {
1124 if (linePtr2 == NULL) {
1125 panic("TkBTreeLineIndex couldn't find line");
1126 }
1127 index += 1;
1128 }
1129
1130 /*
1131 * Now work up through the levels of the tree one at a time,
1132 * counting how many lines are in nodes preceding the current
1133 * node.
1134 */
1135
1136 for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
1137 nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
1138 for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
1139 nodePtr2 = nodePtr2->nextPtr) {
1140 if (nodePtr2 == NULL) {
1141 panic("TkBTreeLineIndex couldn't find node");
1142 }
1143 index += nodePtr2->numLines;
1144 }
1145 }
1146 return index;
1147 }
1148 \f
1149 /*
1150 *----------------------------------------------------------------------
1151 *
1152 * TkBTreeStartSearch --
1153 *
1154 * This procedure sets up a search for tag transitions involving
1155 * a given tag (or all tags) in a given range of the text.
1156 *
1157 * Results:
1158 * None.
1159 *
1160 * Side effects:
1161 * The information at *searchPtr is set up so that subsequent calls
1162 * to TkBTreeNextTag will return information about the locations of
1163 * tag transitions. Note that TkBTreeNextTag must be called to get
1164 * the first transition.
1165 *
1166 *----------------------------------------------------------------------
1167 */
1168
1169 void
1170 TkBTreeStartSearch(tree, line1, ch1, line2, ch2, tagPtr, searchPtr)
1171 TkTextBTree tree; /* Tree to search. */
1172 int line1, ch1; /* Character position at which to * start search (tags at this position
1173 * will be returned). */
1174 int line2, ch2; /* Character position at which to * stop search (tags at this position
1175 * will be returned). */
1176 TkTextTag *tagPtr; /* Tag to search for. NULL means
1177 * search for any tag. */
1178 register TkTextSearch *searchPtr; /* Where to store information about
1179 * search's progress. */
1180 {
1181 register TkAnnotation *annotPtr;
1182
1183 searchPtr->tree = tree;
1184 if (line1 < 0) {
1185 searchPtr->line1 = 0;
1186 searchPtr->ch1 = 0;
1187 } else {
1188 searchPtr->line1 = line1;
1189 searchPtr->ch1 = ch1;
1190 }
1191 searchPtr->line2 = line2;
1192 searchPtr->ch2 = ch2;
1193 searchPtr->tagPtr = tagPtr;
1194 searchPtr->allTags = (tagPtr == NULL);
1195
1196 searchPtr->linePtr = TkBTreeFindLine(searchPtr->tree, searchPtr->line1);
1197 if (searchPtr->linePtr == NULL) {
1198 searchPtr->line1 = searchPtr->line2;
1199 searchPtr->ch1 = searchPtr->ch2;
1200 searchPtr->annotPtr = NULL;
1201 } else {
1202 for (annotPtr = searchPtr->linePtr->annotPtr;
1203 (annotPtr != NULL) && (annotPtr->ch < ch1);
1204 annotPtr = annotPtr->nextPtr) {
1205 /* Empty loop body. */
1206 }
1207 searchPtr->annotPtr = annotPtr;
1208 }
1209 }
1210 \f
1211 /*
1212 *----------------------------------------------------------------------
1213 *
1214 * TkBTreeNextTag --
1215 *
1216 * Once a tag search has begun, successive calls to this procedure
1217 * return successive tag toggles. Note: it is NOT SAFE to call this
1218 * procedure if characters have been inserted into or deleted from
1219 * the B-tree since the call to TkBTreeStartSearch.
1220 *
1221 * Results:
1222 * The return value is 1 if another toggle was found that met the
1223 * criteria specified in the call to TkBTreeStartSearch. 0 is
1224 * returned if no more matching tag transitions were found.
1225 *
1226 * Side effects:
1227 * Information in *searchPtr is modified to update the state of the
1228 * search and indicate where the next tag toggle is located.
1229 *
1230 *----------------------------------------------------------------------
1231 */
1232
1233 int
1234 TkBTreeNextTag(searchPtr)
1235 register TkTextSearch *searchPtr; /* Information about search in
1236 * progress; must have been set up by
1237 * call to TkBTreeStartSearch. */
1238 {
1239 register TkAnnotation *annotPtr;
1240 register Node *nodePtr;
1241 register Summary *summaryPtr;
1242
1243 if (searchPtr->linePtr == NULL) {
1244 return 0;
1245 }
1246
1247 /*
1248 * The outermost loop iterates over lines that may potentially contain
1249 * a relevant tag transition, starting from the current line and tag.
1250 */
1251
1252 while (1) {
1253 /*
1254 * See if there are more tags on the current line that are relevant.
1255 */
1256
1257 for (annotPtr = searchPtr->annotPtr; annotPtr != NULL;
1258 annotPtr = annotPtr->nextPtr) {
1259 if ((annotPtr->type == TK_ANNOT_TOGGLE)
1260 && (searchPtr->allTags
1261 || (annotPtr->info.tagPtr == searchPtr->tagPtr))) {
1262 if ((searchPtr->line1 == searchPtr->line2)
1263 && (annotPtr->ch > searchPtr->ch2)) {
1264 goto searchOver;
1265 }
1266 searchPtr->tagPtr = annotPtr->info.tagPtr;
1267 searchPtr->ch1 = annotPtr->ch;
1268 searchPtr->annotPtr = annotPtr->nextPtr;
1269 return 1;
1270 }
1271 }
1272
1273 /*
1274 * See if there are more lines associated with the current parent
1275 * node. If so, go back to the top of the loop to search the next
1276 * one of them.
1277 */
1278
1279 if (searchPtr->line1 >= searchPtr->line2) {
1280 goto searchOver;
1281 }
1282 searchPtr->line1++;
1283 if (searchPtr->linePtr->nextPtr != NULL) {
1284 searchPtr->linePtr = searchPtr->linePtr->nextPtr;
1285 searchPtr->annotPtr = searchPtr->linePtr->annotPtr;
1286 continue;
1287 }
1288
1289 /*
1290 * Search across and up through the B-tree's node hierarchy looking
1291 * for the next node that has a relevant tag transition somewhere in
1292 * its subtree. Be sure to update the current line number as we
1293 * skip over large chunks of lines.
1294 */
1295
1296 nodePtr = searchPtr->linePtr->parentPtr;
1297 while (1) {
1298 while (nodePtr->nextPtr == NULL) {
1299 if (nodePtr->parentPtr == NULL) {
1300 goto searchOver;
1301 }
1302 nodePtr = nodePtr->parentPtr;
1303 }
1304 nodePtr = nodePtr->nextPtr;
1305 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1306 summaryPtr = summaryPtr->nextPtr) {
1307 if ((searchPtr->allTags) ||
1308 (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1309 goto gotNodeWithTag;
1310 }
1311 }
1312 searchPtr->line1 += nodePtr->numLines;
1313 }
1314
1315 /*
1316 * At this point we've found a subtree that has a relevant tag
1317 * transition. Now search down (and across) through that subtree
1318 * to find the first level-0 node that has a relevant tag transition.
1319 */
1320
1321 gotNodeWithTag:
1322 while (nodePtr->level > 0) {
1323 for (nodePtr = nodePtr->children.nodePtr; ;
1324 nodePtr = nodePtr->nextPtr) {
1325 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1326 summaryPtr = summaryPtr->nextPtr) {
1327 if ((searchPtr->allTags)
1328 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1329 goto nextChild;
1330 }
1331 }
1332 searchPtr->line1 += nodePtr->numLines;
1333 if (nodePtr->nextPtr == NULL) {
1334 panic("TkBTreeNextTag found incorrect tag summary info.");
1335 }
1336 }
1337 nextChild:
1338 continue;
1339 }
1340
1341 /*
1342 * Now we're down to a level-0 node that contains a line that contains
1343 * a relevant tag transition. Set up line information and go back to
1344 * the beginning of the loop to search through lines.
1345 */
1346
1347 searchPtr->linePtr = nodePtr->children.linePtr;
1348 searchPtr->annotPtr = searchPtr->linePtr->annotPtr;
1349 if (searchPtr->line1 > searchPtr->line2) {
1350 goto searchOver;
1351 }
1352 continue;
1353 }
1354
1355 searchOver:
1356 searchPtr->line1 = searchPtr->line2;
1357 searchPtr->ch1 = searchPtr->ch2;
1358 searchPtr->annotPtr = NULL;
1359 searchPtr->linePtr = NULL;
1360 return 0;
1361 }
1362 \f
1363 /*
1364 *----------------------------------------------------------------------
1365 *
1366 * TkBTreeCheck --
1367 *
1368 * This procedure runs a set of consistency checks over a B-tree
1369 * and panics if any inconsistencies are found.
1370 *
1371 * Results:
1372 * None.
1373 *
1374 * Side effects:
1375 * If a structural defect is found, the procedure panics with an
1376 * error message.
1377 *
1378 *----------------------------------------------------------------------
1379 */
1380
1381 void
1382 TkBTreeCheck(tree)
1383 TkTextBTree tree; /* Tree to check. */
1384 {
1385 BTree *treePtr = (BTree *) tree;
1386 register Summary *summaryPtr;
1387
1388 /*
1389 * Make sure that overall there is an even count of tag transitions
1390 * for the whole text.
1391 */
1392
1393 for (summaryPtr = treePtr->rootPtr->summaryPtr; summaryPtr != NULL;
1394 summaryPtr = summaryPtr->nextPtr) {
1395 if (summaryPtr->toggleCount & 1) {
1396 panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
1397 summaryPtr->tagPtr->name, summaryPtr->toggleCount);
1398 }
1399 }
1400
1401 /*
1402 * Call a recursive procedure to do all of the rest of the checks.
1403 */
1404
1405 CheckNodeConsistency(treePtr->rootPtr);
1406 }
1407 \f
1408 /*
1409 *----------------------------------------------------------------------
1410 *
1411 * Rebalance --
1412 *
1413 * This procedure is called when a node of a B-tree appears to be
1414 * out of balance (too many children, or too few). It rebalances
1415 * that node and all of its ancestors in the tree.
1416 *
1417 * Results:
1418 * None.
1419 *
1420 * Side effects:
1421 * The internal structure of treePtr may change.
1422 *
1423 *----------------------------------------------------------------------
1424 */
1425
1426 static void
1427 Rebalance(treePtr, nodePtr)
1428 BTree *treePtr; /* Tree that is being rebalanced. */
1429 register Node *nodePtr; /* Node that may be out of balance. */
1430 {
1431 /*
1432 * Loop over the entire ancestral chain of the node, working up
1433 * through the tree one node at a time until the root node has
1434 * been processed.
1435 */
1436
1437 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
1438 register Node *newPtr, *childPtr;
1439 register TkTextLine *linePtr;
1440 int i;
1441
1442 /*
1443 * Check to see if the node has too many children. If it does,
1444 * then split off all but the first MIN_CHILDREN into a separate
1445 * node following the original one. Then repeat until the
1446 * node has a decent size.
1447 */
1448
1449 if (nodePtr->numChildren > MAX_CHILDREN) {
1450 while (1) {
1451 /*
1452 * If the node being split is the root node, then make a
1453 * new root node above it first.
1454 */
1455
1456 if (nodePtr->parentPtr == NULL) {
1457 newPtr = (Node *) ckalloc(sizeof(Node));
1458 newPtr->parentPtr = NULL;
1459 newPtr->nextPtr = NULL;
1460 newPtr->summaryPtr = NULL;
1461 newPtr->level = nodePtr->level + 1;
1462 newPtr->children.nodePtr = nodePtr;
1463 newPtr->numChildren = 1;
1464 newPtr->numLines = nodePtr->numLines;
1465 RecomputeNodeCounts(newPtr);
1466 treePtr->rootPtr = newPtr;
1467 }
1468 newPtr = (Node *) ckalloc(sizeof(Node));
1469 newPtr->parentPtr = nodePtr->parentPtr;
1470 newPtr->nextPtr = nodePtr->nextPtr;
1471 nodePtr->nextPtr = newPtr;
1472 newPtr->summaryPtr = NULL;
1473 newPtr->level = nodePtr->level;
1474 newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
1475 if (nodePtr->level == 0) {
1476 for (i = MIN_CHILDREN-1,
1477 linePtr = nodePtr->children.linePtr;
1478 i > 0; i--, linePtr = linePtr->nextPtr) {
1479 /* Empty loop body. */
1480 }
1481 newPtr->children.linePtr = linePtr->nextPtr;
1482 linePtr->nextPtr = NULL;
1483 } else {
1484 for (i = MIN_CHILDREN-1,
1485 childPtr = nodePtr->children.nodePtr;
1486 i > 0; i--, childPtr = childPtr->nextPtr) {
1487 /* Empty loop body. */
1488 }
1489 newPtr->children.nodePtr = childPtr->nextPtr;
1490 childPtr->nextPtr = NULL;
1491 }
1492 RecomputeNodeCounts(nodePtr);
1493 nodePtr->parentPtr->numChildren++;
1494 nodePtr = newPtr;
1495 if (nodePtr->numChildren <= MAX_CHILDREN) {
1496 RecomputeNodeCounts(nodePtr);
1497 break;
1498 }
1499 }
1500 }
1501
1502 while (nodePtr->numChildren < MIN_CHILDREN) {
1503 register Node *otherPtr;
1504 Node *halfwayNodePtr = NULL; /* Initialization needed only */
1505 TkTextLine *halfwayLinePtr = NULL; /* to prevent cc warnings. */
1506 int totalChildren, firstChildren, i;
1507
1508 /*
1509 * Too few children for this node. If this is the root,
1510 * it's OK for it to have less than MIN_CHILDREN children
1511 * as long as it's got at least two. If it has only one
1512 * (and isn't at level 0), then chop the root node out of
1513 * the tree and use its child as the new root.
1514 */
1515
1516 if (nodePtr->parentPtr == NULL) {
1517 if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
1518 treePtr->rootPtr = nodePtr->children.nodePtr;
1519 treePtr->rootPtr->parentPtr = NULL;
1520 DeleteSummaries(nodePtr->summaryPtr);
1521 ckfree((char *) nodePtr);
1522 }
1523 return;
1524 }
1525
1526 /*
1527 * Not the root. Make sure that there are siblings to
1528 * balance with.
1529 */
1530
1531 if (nodePtr->parentPtr->numChildren < 2) {
1532 Rebalance(treePtr, nodePtr->parentPtr);
1533 continue;
1534 }
1535
1536 /*
1537 * Find a sibling to borrow from, and arrange for nodePtr to
1538 * be the earlier of the pair.
1539 */
1540
1541 if (nodePtr->nextPtr == NULL) {
1542 for (otherPtr = nodePtr->parentPtr->children.nodePtr;
1543 otherPtr->nextPtr != nodePtr;
1544 otherPtr = otherPtr->nextPtr) {
1545 /* Empty loop body. */
1546 }
1547 nodePtr = otherPtr;
1548 }
1549 otherPtr = nodePtr->nextPtr;
1550
1551 /*
1552 * We're going to either merge the two siblings together
1553 * into one node or redivide the children among them to
1554 * balance their loads. As preparation, join their two
1555 * child lists into a single list and remember the half-way
1556 * point in the list.
1557 */
1558
1559 totalChildren = nodePtr->numChildren + otherPtr->numChildren;
1560 firstChildren = totalChildren/2;
1561 if (nodePtr->children.nodePtr == NULL) {
1562 nodePtr->children = otherPtr->children;
1563 } else if (nodePtr->level == 0) {
1564 register TkTextLine *linePtr;
1565
1566 for (linePtr = nodePtr->children.linePtr, i = 1;
1567 linePtr->nextPtr != NULL;
1568 linePtr = linePtr->nextPtr, i++) {
1569 if (i == firstChildren) {
1570 halfwayLinePtr = linePtr;
1571 }
1572 }
1573 linePtr->nextPtr = otherPtr->children.linePtr;
1574 while (i <= firstChildren) {
1575 halfwayLinePtr = linePtr;
1576 linePtr = linePtr->nextPtr;
1577 i++;
1578 }
1579 } else {
1580 register Node *childPtr;
1581
1582 for (childPtr = nodePtr->children.nodePtr, i = 1;
1583 childPtr->nextPtr != NULL;
1584 childPtr = childPtr->nextPtr, i++) {
1585 if (i <= firstChildren) {
1586 if (i == firstChildren) {
1587 halfwayNodePtr = childPtr;
1588 }
1589 }
1590 }
1591 childPtr->nextPtr = otherPtr->children.nodePtr;
1592 while (i <= firstChildren) {
1593 halfwayNodePtr = childPtr;
1594 childPtr = childPtr->nextPtr;
1595 i++;
1596 }
1597 }
1598
1599 /*
1600 * If the two siblings can simply be merged together, do it.
1601 */
1602
1603 if (totalChildren < MAX_CHILDREN) {
1604 RecomputeNodeCounts(nodePtr);
1605 nodePtr->nextPtr = otherPtr->nextPtr;
1606 nodePtr->parentPtr->numChildren--;
1607 DeleteSummaries(otherPtr->summaryPtr);
1608 ckfree((char *) otherPtr);
1609 continue;
1610 }
1611
1612 /*
1613 * The siblings can't be merged, so just divide their
1614 * children evenly between them.
1615 */
1616
1617 if (nodePtr->level == 0) {
1618 otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
1619 halfwayLinePtr->nextPtr = NULL;
1620 } else {
1621 otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
1622 halfwayNodePtr->nextPtr = NULL;
1623 }
1624 RecomputeNodeCounts(nodePtr);
1625 RecomputeNodeCounts(otherPtr);
1626 }
1627 }
1628 }
1629 \f
1630 /*
1631 *----------------------------------------------------------------------
1632 *
1633 * RecomputeNodeCounts --
1634 *
1635 * This procedure is called to recompute all the counts in a node
1636 * (tags, child information, etc.) by scaning the information in
1637 * its descendants. This procedure is called during rebalancing
1638 * when a node's child structure has changed.
1639 *
1640 * Results:
1641 * None.
1642 *
1643 * Side effects:
1644 * The tag counts for nodePtr are modified to reflect its current
1645 * child structure, as are its numChildren and numLines fields.
1646 * Also, all of the children's parentPtr fields are made to point
1647 * to nodePtr.
1648 *
1649 *----------------------------------------------------------------------
1650 */
1651
1652 static void
1653 RecomputeNodeCounts(nodePtr)
1654 register Node *nodePtr; /* Node whose tag summary information
1655 * must be recomputed. */
1656 {
1657 register Summary *summaryPtr, *summaryPtr2;
1658 register Node *childPtr;
1659 register TkTextLine *linePtr;
1660 register TkAnnotation *annotPtr;
1661
1662 /*
1663 * Zero out all the existing counts for the node, but don't delete
1664 * the existing Summary records (most of them will probably be reused).
1665 */
1666
1667 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1668 summaryPtr = summaryPtr->nextPtr) {
1669 summaryPtr->toggleCount = 0;
1670 }
1671 nodePtr->numChildren = 0;
1672 nodePtr->numLines = 0;
1673
1674 /*
1675 * Scan through the children, adding the childrens' tag counts into
1676 * the node's tag counts and adding new Summarys to the node if
1677 * necessary.
1678 */
1679
1680 if (nodePtr->level == 0) {
1681 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
1682 linePtr = linePtr->nextPtr) {
1683 nodePtr->numChildren++;
1684 nodePtr->numLines++;
1685 linePtr->parentPtr = nodePtr;
1686 for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
1687 annotPtr = annotPtr->nextPtr) {
1688 if (annotPtr->type != TK_ANNOT_TOGGLE) {
1689 continue;
1690 }
1691 for (summaryPtr = nodePtr->summaryPtr; ;
1692 summaryPtr = summaryPtr->nextPtr) {
1693 if (summaryPtr == NULL) {
1694 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
1695 summaryPtr->tagPtr = annotPtr->info.tagPtr;
1696 summaryPtr->toggleCount = 1;
1697 summaryPtr->nextPtr = nodePtr->summaryPtr;
1698 nodePtr->summaryPtr = summaryPtr;
1699 break;
1700 }
1701 if (summaryPtr->tagPtr == annotPtr->info.tagPtr) {
1702 summaryPtr->toggleCount++;
1703 break;
1704 }
1705 }
1706 }
1707 }
1708 } else {
1709 for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
1710 childPtr = childPtr->nextPtr) {
1711 nodePtr->numChildren++;
1712 nodePtr->numLines += childPtr->numLines;
1713 childPtr->parentPtr = nodePtr;
1714 for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
1715 summaryPtr2 = summaryPtr2->nextPtr) {
1716 for (summaryPtr = nodePtr->summaryPtr; ;
1717 summaryPtr = summaryPtr->nextPtr) {
1718 if (summaryPtr == NULL) {
1719 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
1720 summaryPtr->tagPtr = summaryPtr2->tagPtr;
1721 summaryPtr->toggleCount = summaryPtr2->toggleCount;
1722 summaryPtr->nextPtr = nodePtr->summaryPtr;
1723 nodePtr->summaryPtr = summaryPtr;
1724 break;
1725 }
1726 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
1727 summaryPtr->toggleCount += summaryPtr2->toggleCount;
1728 break;
1729 }
1730 }
1731 }
1732 }
1733 }
1734
1735 /*
1736 * Scan through the node's tag records again and delete any Summary
1737 * records that still have a zero count.
1738 */
1739
1740 summaryPtr2 = NULL;
1741 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
1742 if (summaryPtr->toggleCount > 0) {
1743 summaryPtr2 = summaryPtr;
1744 summaryPtr = summaryPtr->nextPtr;
1745 continue;
1746 }
1747 if (summaryPtr2 != NULL) {
1748 summaryPtr2->nextPtr = summaryPtr->nextPtr;
1749 ckfree((char *) summaryPtr);
1750 summaryPtr = summaryPtr2->nextPtr;
1751 } else {
1752 nodePtr->summaryPtr = summaryPtr->nextPtr;
1753 ckfree((char *) summaryPtr);
1754 summaryPtr = nodePtr->summaryPtr;
1755 }
1756 }
1757 }
1758 \f
1759 /*
1760 *----------------------------------------------------------------------
1761 *
1762 * AddToggleToLine --
1763 *
1764 * Insert a tag transition at a particular point in a particular
1765 * line.
1766 *
1767 * Results:
1768 * None.
1769 *
1770 * Side effects:
1771 * LinePtr and all its ancestors in the B-tree stucture are modified
1772 * to indicate the presence of a transition (either on or off) on
1773 * tag at the given place in the given line.
1774 *
1775 *----------------------------------------------------------------------
1776 */
1777
1778 static void
1779 AddToggleToLine(linePtr, index, tagPtr)
1780 TkTextLine *linePtr; /* Line within which to add
1781 * transition. */
1782 int index; /* Character before which to
1783 * add transition. */
1784 TkTextTag *tagPtr; /* Information about tag. */
1785 {
1786 register TkAnnotation *annotPtr, *prevPtr;
1787 int delta = 1;
1788
1789 /*
1790 * Find the position where the toggle should be inserted into
1791 * the array (just after prevPtr), and see if there is already
1792 * a toggle at exactly the point where we're going to insert a
1793 * new toggle. If so then the two toggles cancel; just delete
1794 * the existing toggle.
1795 */
1796
1797 for (prevPtr = NULL, annotPtr = linePtr->annotPtr; annotPtr != NULL;
1798 prevPtr = annotPtr, annotPtr = annotPtr->nextPtr) {
1799 if (annotPtr->ch > index) {
1800 break;
1801 }
1802 if ((annotPtr->type == TK_ANNOT_TOGGLE)
1803 && (annotPtr->ch == index)
1804 && (annotPtr->info.tagPtr == tagPtr)) {
1805 if (prevPtr == NULL) {
1806 linePtr->annotPtr = annotPtr->nextPtr;
1807 } else {
1808 prevPtr->nextPtr = annotPtr->nextPtr;
1809 }
1810 ckfree((char *) annotPtr);
1811 delta = -1;
1812 goto updateNodes;
1813 }
1814 }
1815
1816 /*
1817 * Create a new toggle and insert it into the list.
1818 */
1819
1820 annotPtr = (TkAnnotation *) ckalloc(sizeof(TkAnnotation));
1821 annotPtr->type = TK_ANNOT_TOGGLE;
1822 annotPtr->linePtr = linePtr;
1823 annotPtr->ch = index;
1824 annotPtr->info.tagPtr = tagPtr;
1825 if (prevPtr == NULL) {
1826 annotPtr->nextPtr = linePtr->annotPtr;
1827 linePtr->annotPtr = annotPtr;
1828 } else {
1829 annotPtr->nextPtr = prevPtr->nextPtr;
1830 prevPtr->nextPtr = annotPtr;
1831 }
1832
1833 /*
1834 * Update all the nodes above this line to reflect the change in
1835 * toggle structure.
1836 */
1837
1838 updateNodes:
1839 ChangeNodeToggleCount(linePtr->parentPtr, tagPtr, delta);
1840 }
1841 \f
1842 /*
1843 *----------------------------------------------------------------------
1844 *
1845 * ChangeNodeToggleCount --
1846 *
1847 * This procedure increments or decrements the toggle count for
1848 * a particular tag in a particular node and all its ancestors.
1849 *
1850 * Results:
1851 * None.
1852 *
1853 * Side effects:
1854 * The toggle count for tag is adjusted up or down by "delta" in
1855 * nodePtr.
1856 *
1857 *----------------------------------------------------------------------
1858 */
1859
1860 static void
1861 ChangeNodeToggleCount(nodePtr, tagPtr, delta)
1862 register Node *nodePtr; /* Node whose toggle count for a tag
1863 * must be changed. */
1864 TkTextTag *tagPtr; /* Information about tag. */
1865 int delta; /* Amount to add to current toggle
1866 * count for tag (may be negative). */
1867 {
1868 register Summary *summaryPtr, *prevPtr;
1869
1870 /*
1871 * Iterate over the node and all of its ancestors.
1872 */
1873
1874 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
1875 /*
1876 * See if there's already an entry for this tag for this node. If so,
1877 * perhaps all we have to do is adjust its count.
1878 */
1879
1880 for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
1881 summaryPtr != NULL;
1882 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
1883 if (summaryPtr->tagPtr != tagPtr) {
1884 continue;
1885 }
1886 summaryPtr->toggleCount += delta;
1887 if (summaryPtr->toggleCount > 0) {
1888 goto nextAncestor;
1889 }
1890 if (summaryPtr->toggleCount < 0) {
1891 panic("ChangeNodeToggleCount: negative toggle count");
1892 }
1893
1894 /*
1895 * Zero count; must remove this tag from the list.
1896 */
1897
1898 if (prevPtr == NULL) {
1899 nodePtr->summaryPtr = summaryPtr->nextPtr;
1900 } else {
1901 prevPtr->nextPtr = summaryPtr->nextPtr;
1902 }
1903 ckfree((char *) summaryPtr);
1904 goto nextAncestor;
1905 }
1906
1907 /*
1908 * This tag isn't in the list. Add a new entry to the list.
1909 */
1910
1911 if (delta < 0) {
1912 panic("ChangeNodeToggleCount: negative delta, no tag entry");
1913 }
1914 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
1915 summaryPtr->tagPtr = tagPtr;
1916 summaryPtr->toggleCount = delta;
1917 summaryPtr->nextPtr = nodePtr->summaryPtr;
1918 nodePtr->summaryPtr = summaryPtr;
1919
1920 nextAncestor:
1921 continue;
1922 }
1923 }
1924 \f
1925 /*
1926 *----------------------------------------------------------------------
1927 *
1928 * TkBTreeCharTagged --
1929 *
1930 * Determine whether a particular character has a particular tag.
1931 *
1932 * Results:
1933 * The return value is 1 if the given tag is in effect at the
1934 * character given by linePtr and ch, and 0 otherwise.
1935 *
1936 * Side effects:
1937 * None.
1938 *
1939 *----------------------------------------------------------------------
1940 */
1941
1942 int
1943 TkBTreeCharTagged(linePtr, ch, tagPtr)
1944 TkTextLine *linePtr; /* Line containing character of
1945 * interest. */
1946 int ch; /* Index of character in linePtr. */
1947 TkTextTag *tagPtr; /* Tag of interest. */
1948 {
1949 register Node *nodePtr;
1950 register TkTextLine *siblingLinePtr;
1951 int toggles;
1952
1953 /*
1954 * Count the number of toggles for the tag at the line level (i.e.
1955 * in all the sibling lines that precede this one, plus in this line
1956 * up to the character of interest.
1957 */
1958
1959 toggles = 0;
1960 for (siblingLinePtr = linePtr->parentPtr->children.linePtr; ;
1961 siblingLinePtr = siblingLinePtr->nextPtr) {
1962 register TkAnnotation *annotPtr;
1963
1964 for (annotPtr = siblingLinePtr->annotPtr;
1965 (annotPtr != NULL) && ((siblingLinePtr != linePtr)
1966 || (annotPtr->ch <= ch));
1967 annotPtr = annotPtr->nextPtr) {
1968 if ((annotPtr->type == TK_ANNOT_TOGGLE)
1969 && (annotPtr->info.tagPtr == tagPtr)) {
1970 toggles++;
1971 }
1972 }
1973 if (siblingLinePtr == linePtr) {
1974 break;
1975 }
1976 }
1977
1978 /*
1979 * For each node in the ancestry of this line, count the number of
1980 * toggles of the given tag in siblings that precede that node.
1981 */
1982
1983 for (nodePtr = linePtr->parentPtr; nodePtr->parentPtr != NULL;
1984 nodePtr = nodePtr->parentPtr) {
1985 register Node *siblingPtr;
1986 register Summary *summaryPtr;
1987
1988 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
1989 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
1990 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
1991 summaryPtr = summaryPtr->nextPtr) {
1992 if (summaryPtr->tagPtr == tagPtr) {
1993 toggles += summaryPtr->toggleCount;
1994 }
1995 }
1996 }
1997 }
1998
1999 /*
2000 * An odd number of toggles means that the tag is present at the
2001 * given point.
2002 */
2003
2004 return toggles & 1;
2005 }
2006 \f
2007 /*
2008 *----------------------------------------------------------------------
2009 *
2010 * TkBTreeGetTags --
2011 *
2012 * Return information about all of the tags that are associated
2013 * with a particular character in a B-tree of text.
2014 *
2015 * Results:
2016 * The return value is a malloc-ed array containing pointers to
2017 * information for each of the tags that is associated with
2018 * the character at the position given by linePtr and ch. The
2019 * word at *numTagsPtr is filled in with the number of pointers
2020 * in the array. It is up to the caller to free the array by
2021 * passing it to free. If there are no tags at the given character
2022 * then a NULL pointer is returned and *numTagsPtr will be set to 0.
2023 *
2024 * Side effects:
2025 * None.
2026 *
2027 *----------------------------------------------------------------------
2028 */
2029
2030 /* ARGSUSED */
2031 TkTextTag **
2032 TkBTreeGetTags(tree, linePtr, ch, numTagsPtr)
2033 TkTextBTree tree; /* Tree to check. */
2034 TkTextLine *linePtr; /* Line containing character of interest. */
2035 int ch; /* Index within linePtr of character for
2036 * which tag information is wanted. */
2037 int *numTagsPtr; /* Store number of tags found at this
2038 * location. */
2039 {
2040 register Node *nodePtr;
2041 register TkTextLine *siblingLinePtr;
2042 int src, dst;
2043 TagInfo tagInfo;
2044 #define NUM_TAG_INFOS 10
2045
2046 tagInfo.numTags = 0;
2047 tagInfo.arraySize = NUM_TAG_INFOS;
2048 tagInfo.tagPtrs = (TkTextTag **) ckalloc((unsigned)
2049 NUM_TAG_INFOS*sizeof(TkTextTag *));
2050 tagInfo.counts = (int *) ckalloc((unsigned)
2051 NUM_TAG_INFOS*sizeof(int));
2052
2053 /*
2054 * Record tag toggles at the line level (i.e. in all the sibling
2055 * lines that precede this one, plus in this line up to the character
2056 * of interest.
2057 */
2058
2059 for (siblingLinePtr = linePtr->parentPtr->children.linePtr; ;
2060 siblingLinePtr = siblingLinePtr->nextPtr) {
2061 register TkAnnotation *annotPtr;
2062
2063 for (annotPtr = siblingLinePtr->annotPtr;
2064 (annotPtr != NULL) && ((siblingLinePtr != linePtr)
2065 || (annotPtr->ch <= ch));
2066 annotPtr = annotPtr->nextPtr) {
2067 if (annotPtr->type == TK_ANNOT_TOGGLE) {
2068 IncCount(annotPtr->info.tagPtr, 1, &tagInfo);
2069 }
2070 }
2071 if (siblingLinePtr == linePtr) {
2072 break;
2073 }
2074 }
2075
2076 /*
2077 * For each node in the ancestry of this line, record tag toggles
2078 * for all siblings that precede that node.
2079 */
2080
2081 for (nodePtr = linePtr->parentPtr; nodePtr->parentPtr != NULL;
2082 nodePtr = nodePtr->parentPtr) {
2083 register Node *siblingPtr;
2084 register Summary *summaryPtr;
2085
2086 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
2087 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
2088 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
2089 summaryPtr = summaryPtr->nextPtr) {
2090 IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount, &tagInfo);
2091 }
2092 }
2093 }
2094
2095 /*
2096 * Go through the tag information and squash out all of the tags
2097 * that have even toggle counts (these tags exist before the point
2098 * of interest, but not at the desired character itself).
2099 */
2100
2101 for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
2102 if (tagInfo.counts[src] & 1) {
2103 tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
2104 dst++;
2105 }
2106 }
2107 *numTagsPtr = dst;
2108 ckfree((char *) tagInfo.counts);
2109 if (dst == 0) {
2110 ckfree((char *) tagInfo.tagPtrs);
2111 return NULL;
2112 }
2113 return tagInfo.tagPtrs;
2114 }
2115 \f
2116 /*
2117 *----------------------------------------------------------------------
2118 *
2119 * IncCount --
2120 *
2121 * This is a utility procedure used by TkBTreeGetTags. It
2122 * increments the count for a particular tag, adding a new
2123 * entry for that tag if there wasn't one previously.
2124 *
2125 * Results:
2126 * None.
2127 *
2128 * Side effects:
2129 * The information at *tagInfoPtr may be modified, and the arrays
2130 * may be reallocated to make them larger.
2131 *
2132 *----------------------------------------------------------------------
2133 */
2134
2135 static void
2136 IncCount(tagPtr, inc, tagInfoPtr)
2137 TkTextTag *tagPtr; /* Handle for tag. */
2138 int inc; /* Amount by which to increment tag count. */
2139 TagInfo *tagInfoPtr; /* Holds cumulative information about tags;
2140 * increment count here. */
2141 {
2142 register TkTextTag **tagPtrPtr;
2143 int count;
2144
2145 for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
2146 count > 0; tagPtrPtr++, count--) {
2147 if (*tagPtrPtr == tagPtr) {
2148 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
2149 return;
2150 }
2151 }
2152
2153 /*
2154 * There isn't currently an entry for this tag, so we have to
2155 * make a new one. If the arrays are full, then enlarge the
2156 * arrays first.
2157 */
2158
2159 if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
2160 TkTextTag **newTags;
2161 int *newCounts, newSize;
2162
2163 newSize = 2*tagInfoPtr->arraySize;
2164 newTags = (TkTextTag **) ckalloc((unsigned)
2165 (newSize*sizeof(TkTextTag *)));
2166 memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
2167 tagInfoPtr->arraySize * sizeof(TkTextTag *));
2168 ckfree((char *) tagInfoPtr->tagPtrs);
2169 tagInfoPtr->tagPtrs = newTags;
2170 newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
2171 memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
2172 tagInfoPtr->arraySize * sizeof(int));
2173 ckfree((char *) tagInfoPtr->counts);
2174 tagInfoPtr->counts = newCounts;
2175 tagInfoPtr->arraySize = newSize;
2176 }
2177
2178 tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
2179 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
2180 tagInfoPtr->numTags++;
2181 }
2182 \f
2183 /*
2184 *----------------------------------------------------------------------
2185 *
2186 * CheckNodeConsistency --
2187 *
2188 * This procedure is called as part of consistency checking for
2189 * B-trees: it checks several aspects of a node and also runs
2190 * checks recursively on the node's children.
2191 *
2192 * Results:
2193 * None.
2194 *
2195 * Side effects:
2196 * If anything suspicious is found in the tree structure, the
2197 * procedure panics.
2198 *
2199 *----------------------------------------------------------------------
2200 */
2201
2202 static void
2203 CheckNodeConsistency(nodePtr)
2204 register Node *nodePtr; /* Node whose subtree should be
2205 * checked. */
2206 {
2207 register Node *childNodePtr;
2208 register Summary *summaryPtr, *summaryPtr2;
2209 register TkAnnotation *annotPtr;
2210 register TkTextLine *linePtr;
2211 register char *p;
2212 int numChildren, numLines, toggleCount, minChildren, index, numBytes;
2213
2214 if (nodePtr->parentPtr != NULL) {
2215 minChildren = MIN_CHILDREN;
2216 } else if (nodePtr->level > 0) {
2217 minChildren = 2;
2218 } else {
2219 minChildren = 1;
2220 }
2221 if ((nodePtr->numChildren < minChildren)
2222 || (nodePtr->numChildren > MAX_CHILDREN)) {
2223 panic("CheckNodeConsistency found bad child count (%d)",
2224 nodePtr->numChildren);
2225 }
2226
2227 numChildren = 0;
2228 numLines = 0;
2229 if (nodePtr->level == 0) {
2230 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
2231 linePtr = linePtr->nextPtr) {
2232 if (linePtr->parentPtr != nodePtr) {
2233 panic("CheckNodeConsistency found line that %s",
2234 "didn't point to parent");
2235 }
2236 for (p = linePtr->bytes, numBytes = 0; *p != 0; p++, numBytes++) {
2237 if ((*p == '\n') && (numBytes != linePtr->numBytes-1)) {
2238 panic("CheckNodeConsistency found line with extra newline");
2239 }
2240 }
2241 if (numBytes != linePtr->numBytes) {
2242 panic("CheckNodeConsistency found line with bad numBytes");
2243 }
2244 if (linePtr->bytes[numBytes-1] != '\n') {
2245 panic("CheckNodeConsistency found line with no newline");
2246 }
2247 index = 0;
2248 for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
2249 annotPtr = annotPtr->nextPtr) {
2250 if (annotPtr->ch < index) {
2251 panic("CheckNodeConsistency found %s (%d %d)",
2252 "out-of-order tag indices", index,
2253 annotPtr->ch);
2254 }
2255 index = annotPtr->ch;
2256 if (annotPtr->type == TK_ANNOT_TOGGLE) {
2257 for (summaryPtr = nodePtr->summaryPtr; ;
2258 summaryPtr = summaryPtr->nextPtr) {
2259 if (summaryPtr == NULL) {
2260 panic("CheckNodeConsistency found line %s",
2261 "tag with no node tag: %s",
2262 summaryPtr->tagPtr->name);
2263 }
2264 if (summaryPtr->tagPtr == annotPtr->info.tagPtr) {
2265 break;
2266 }
2267 }
2268 }
2269 }
2270 numChildren++;
2271 numLines++;
2272 }
2273 } else {
2274 for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
2275 childNodePtr = childNodePtr->nextPtr) {
2276 CheckNodeConsistency(childNodePtr);
2277 for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
2278 summaryPtr = summaryPtr->nextPtr) {
2279 for (summaryPtr2 = nodePtr->summaryPtr; ;
2280 summaryPtr2 = summaryPtr2->nextPtr) {
2281 if (summaryPtr2 == NULL) {
2282 panic("CheckNodeConsistency found %s (%s)",
2283 "node tag with no parent tag",
2284 summaryPtr->tagPtr->name);
2285 }
2286 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
2287 break;
2288 }
2289 }
2290 }
2291 numChildren++;
2292 numLines += childNodePtr->numLines;
2293 if (childNodePtr->parentPtr != nodePtr) {
2294 panic("CheckNodeConsistency found node that %s",
2295 "didn't point to parent");
2296 }
2297 if (childNodePtr->level != (nodePtr->level-1)) {
2298 panic("CheckNodeConsistency found level mismatch (%d %d)",
2299 nodePtr->level, childNodePtr->level);
2300 }
2301 }
2302 }
2303 if (numChildren != nodePtr->numChildren) {
2304 panic("CheckNodeConsistency found mismatch in numChildren (%d %d)",
2305 numChildren, nodePtr->numChildren);
2306 }
2307 if (numLines != nodePtr->numLines) {
2308 panic("CheckNodeConsistency found mismatch in numLines (%d %d)",
2309 numLines, nodePtr->numLines);
2310 }
2311
2312 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
2313 summaryPtr = summaryPtr->nextPtr) {
2314 toggleCount = 0;
2315 if (nodePtr->level == 0) {
2316 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
2317 linePtr = linePtr->nextPtr) {
2318 for (annotPtr = linePtr->annotPtr; annotPtr != NULL;
2319 annotPtr = annotPtr->nextPtr) {
2320 if (annotPtr->info.tagPtr == summaryPtr->tagPtr) {
2321 toggleCount++;
2322 }
2323 }
2324 }
2325 } else {
2326 for (childNodePtr = nodePtr->children.nodePtr;
2327 childNodePtr != NULL;
2328 childNodePtr = childNodePtr->nextPtr) {
2329 for (summaryPtr2 = childNodePtr->summaryPtr;
2330 summaryPtr2 != NULL;
2331 summaryPtr2 = summaryPtr2->nextPtr) {
2332 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2333 toggleCount += summaryPtr2->toggleCount;
2334 }
2335 }
2336 }
2337 }
2338 if (toggleCount != summaryPtr->toggleCount) {
2339 panic("CheckNodeConsistency found mismatch in toggleCount (%d %d)",
2340 toggleCount, summaryPtr->toggleCount);
2341 }
2342 for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
2343 summaryPtr2 = summaryPtr2->nextPtr) {
2344 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2345 panic("CheckNodeConsistency found duplicated node tag: %s",
2346 summaryPtr->tagPtr->name);
2347 }
2348 }
2349 }
2350 }
2351 \f
2352 /*
2353 *----------------------------------------------------------------------
2354 *
2355 * TkBTreeNumLines --
2356 *
2357 * This procedure returns a count of the number of lines of
2358 * text present in a given B-tree.
2359 *
2360 * Results:
2361 * The return value is a count of the number of lines in tree.
2362 *
2363 * Side effects:
2364 * None.
2365 *
2366 *----------------------------------------------------------------------
2367 */
2368
2369 int
2370 TkBTreeNumLines(tree)
2371 TkTextBTree tree; /* Information about tree. */
2372 {
2373 BTree *treePtr = (BTree *) tree;
2374 return treePtr->rootPtr->numLines;
2375 }
Impressum, Datenschutz