4 * This file contains code that manages the B-tree representation
5 * of text for Ck's text widget and implements character and
6 * toggle segment types.
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 * Copyright (c) 1995 Christian Werner
12 * See the file "license.terms" for information on usage and redistribution
13 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
21 * The data structure below keeps summary information about one tag as part
22 * of the tag information in a node.
25 typedef struct Summary {
26 CkTextTag *tagPtr; /* Handle for tag. */
27 int toggleCount; /* Number of transitions into or
28 * out of this tag that occur in
29 * the subtree rooted at this node. */
30 struct Summary *nextPtr; /* Next in list of all tags for same
31 * node, or NULL if at end of list. */
35 * The data structure below defines a node in the B-tree.
39 struct Node *parentPtr; /* Pointer to parent node, or NULL if
40 * this is the root. */
41 struct Node *nextPtr; /* Next in list of siblings with the
42 * same parent node, or NULL for end
44 Summary *summaryPtr; /* First in malloc-ed list of info
45 * about tags in this subtree (NULL if
46 * no tag info in the subtree). */
47 int level; /* Level of this node in the B-tree.
48 * 0 refers to the bottom of the tree
49 * (children are lines, not nodes). */
50 union { /* First in linked list of children. */
51 struct Node *nodePtr; /* Used if level > 0. */
52 CkTextLine *linePtr; /* Used if level == 0. */
54 int numChildren; /* Number of children of this node. */
55 int numLines; /* Total number of lines (leaves) in
56 * the subtree rooted here. */
60 * Upper and lower bounds on how many children a node may have:
61 * rebalance when either of these limits is exceeded. MAX_CHILDREN
62 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
65 #define MAX_CHILDREN 12
66 #define MIN_CHILDREN 6
69 * The data structure below defines an entire B-tree.
72 typedef struct BTree {
73 Node *rootPtr; /* Pointer to root of B-tree. */
77 * The structure below is used to pass information between
78 * CkBTreeGetTags and IncCount:
81 typedef struct TagInfo {
82 int numTags; /* Number of tags for which there
83 * is currently information in
85 int arraySize; /* Number of entries allocated for
87 CkTextTag **tagPtrs; /* Array of tags seen so far.
89 int *counts; /* Toggle count (so far) for each
90 * entry in tags. Malloc-ed. */
94 * Variable that indicates whether to enable consistency checks for
101 * Macros that determine how much space to allocate for new segments:
104 #define CSEG_SIZE(chars) ((unsigned) (Ck_Offset(CkTextSegment, body) \
106 #define TSEG_SIZE ((unsigned) (Ck_Offset(CkTextSegment, body) \
107 + sizeof(CkTextToggle)))
110 * Forward declarations for procedures defined in this file:
113 static void ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
114 CkTextTag *tagPtr, int delta));
115 static void CharCheckProc _ANSI_ARGS_((CkTextSegment *segPtr,
116 CkTextLine *linePtr));
117 static int CharDeleteProc _ANSI_ARGS_((CkTextSegment *segPtr,
118 CkTextLine *linePtr, int treeGone));
119 static CkTextSegment * CharCleanupProc _ANSI_ARGS_((CkTextSegment *segPtr,
120 CkTextLine *linePtr));
121 static CkTextSegment * CharSplitProc _ANSI_ARGS_((CkTextSegment *segPtr,
123 static void CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
124 static void CleanupLine _ANSI_ARGS_((CkTextLine *linePtr));
125 static void DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
126 static void DestroyNode _ANSI_ARGS_((Node *nodePtr));
127 static void IncCount _ANSI_ARGS_((CkTextTag *tagPtr, int inc,
128 TagInfo *tagInfoPtr));
129 static void Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
130 static void RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
131 static CkTextSegment * SplitSeg _ANSI_ARGS_((CkTextIndex *indexPtr));
132 static void ToggleCheckProc _ANSI_ARGS_((CkTextSegment *segPtr,
133 CkTextLine *linePtr));
134 static CkTextSegment * ToggleCleanupProc _ANSI_ARGS_((CkTextSegment *segPtr,
135 CkTextLine *linePtr));
136 static int ToggleDeleteProc _ANSI_ARGS_((CkTextSegment *segPtr,
137 CkTextLine *linePtr, int treeGone));
138 static void ToggleLineChangeProc _ANSI_ARGS_((CkTextSegment *segPtr,
139 CkTextLine *linePtr));
142 * Type record for character segments:
145 Ck_SegType ckTextCharType = {
146 "character", /* name */
148 CharSplitProc, /* splitProc */
149 CharDeleteProc, /* deleteProc */
150 CharCleanupProc, /* cleanupProc */
151 (Ck_SegLineChangeProc *) NULL, /* lineChangeProc */
152 CkTextCharLayoutProc, /* layoutProc */
153 CharCheckProc /* checkProc */
157 * Type record for segments marking the beginning of a tagged
161 Ck_SegType ckTextToggleOnType = {
162 "toggleOn", /* name */
164 (Ck_SegSplitProc *) NULL, /* splitProc */
165 ToggleDeleteProc, /* deleteProc */
166 ToggleCleanupProc, /* cleanupProc */
167 ToggleLineChangeProc, /* lineChangeProc */
168 (Ck_SegLayoutProc *) NULL, /* layoutProc */
169 ToggleCheckProc /* checkProc */
173 * Type record for segments marking the end of a tagged
177 Ck_SegType ckTextToggleOffType = {
178 "toggleOff", /* name */
180 (Ck_SegSplitProc *) NULL, /* splitProc */
181 ToggleDeleteProc, /* deleteProc */
182 ToggleCleanupProc, /* cleanupProc */
183 ToggleLineChangeProc, /* lineChangeProc */
184 (Ck_SegLayoutProc *) NULL, /* layoutProc */
185 ToggleCheckProc /* checkProc */
189 *----------------------------------------------------------------------
193 * This procedure is called to create a new text B-tree.
196 * The return value is a pointer to a new B-tree containing
197 * one line with nothing but a newline character.
200 * Memory is allocated and initialized.
202 *----------------------------------------------------------------------
208 register BTree *treePtr;
209 register Node *rootPtr;
210 register CkTextLine *linePtr, *linePtr2;
211 register CkTextSegment *segPtr;
214 * The tree will initially have two empty lines. The second line
215 * isn't actually part of the tree's contents, but its presence
216 * makes several operations easier. The tree will have one node,
217 * which is also the root of the tree.
220 rootPtr = (Node *) ckalloc(sizeof(Node));
221 linePtr = (CkTextLine *) ckalloc(sizeof(CkTextLine));
222 linePtr2 = (CkTextLine *) ckalloc(sizeof(CkTextLine));
223 rootPtr->parentPtr = NULL;
224 rootPtr->nextPtr = NULL;
225 rootPtr->summaryPtr = NULL;
227 rootPtr->children.linePtr = linePtr;
228 rootPtr->numChildren = 2;
229 rootPtr->numLines = 2;
231 linePtr->parentPtr = rootPtr;
232 linePtr->nextPtr = linePtr2;
233 segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(1));
234 linePtr->segPtr = segPtr;
235 segPtr->typePtr = &ckTextCharType;
236 segPtr->nextPtr = NULL;
238 segPtr->body.chars[0] = '\n';
239 segPtr->body.chars[1] = 0;
241 linePtr2->parentPtr = rootPtr;
242 linePtr2->nextPtr = NULL;
243 segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(1));
244 linePtr2->segPtr = segPtr;
245 segPtr->typePtr = &ckTextCharType;
246 segPtr->nextPtr = NULL;
248 segPtr->body.chars[0] = '\n';
249 segPtr->body.chars[1] = 0;
251 treePtr = (BTree *) ckalloc(sizeof(BTree));
252 treePtr->rootPtr = rootPtr;
254 return (CkTextBTree) treePtr;
258 *----------------------------------------------------------------------
262 * Delete a B-tree, recycling all of the storage it contains.
265 * The tree given by treePtr is deleted. TreePtr should never
271 *----------------------------------------------------------------------
276 CkTextBTree tree; /* Pointer to tree to delete. */
278 BTree *treePtr = (BTree *) tree;
280 DestroyNode(treePtr->rootPtr);
281 ckfree((char *) treePtr);
285 *----------------------------------------------------------------------
289 * This is a recursive utility procedure used during the deletion
296 * All the storage for nodePtr and its descendants is freed.
298 *----------------------------------------------------------------------
303 register Node *nodePtr;
305 if (nodePtr->level == 0) {
307 CkTextSegment *segPtr;
309 while (nodePtr->children.linePtr != NULL) {
310 linePtr = nodePtr->children.linePtr;
311 nodePtr->children.linePtr = linePtr->nextPtr;
312 while (linePtr->segPtr != NULL) {
313 segPtr = linePtr->segPtr;
314 linePtr->segPtr = segPtr->nextPtr;
315 (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
317 ckfree((char *) linePtr);
320 register Node *childPtr;
322 while (nodePtr->children.nodePtr != NULL) {
323 childPtr = nodePtr->children.nodePtr;
324 nodePtr->children.nodePtr = childPtr->nextPtr;
325 DestroyNode(childPtr);
328 DeleteSummaries(nodePtr->summaryPtr);
329 ckfree((char *) nodePtr);
333 *----------------------------------------------------------------------
337 * Free up all of the memory in a list of tag summaries associated
344 * Storage is released.
346 *----------------------------------------------------------------------
350 DeleteSummaries(summaryPtr)
351 register Summary *summaryPtr; /* First in list of node's tag
354 register Summary *nextPtr;
355 while (summaryPtr != NULL) {
356 nextPtr = summaryPtr->nextPtr;
357 ckfree((char *) summaryPtr);
358 summaryPtr = nextPtr;
363 *----------------------------------------------------------------------
365 * CkBTreeInsertChars --
367 * Insert characters at a given position in a B-tree.
373 * Characters are added to the B-tree at the given position.
374 * If the string contains newlines, new lines will be added,
375 * which could cause the structure of the B-tree to change.
377 *----------------------------------------------------------------------
381 CkBTreeInsertChars(indexPtr, string)
382 register CkTextIndex *indexPtr; /* Indicates where to insert text.
383 * When the procedure returns, this
384 * index is no longer valid because
385 * of changes to the segment
387 char *string; /* Pointer to bytes to insert (may
388 * contain newlines, must be null-
391 register Node *nodePtr;
392 register CkTextSegment *prevPtr; /* The segment just before the first
393 * new segment (NULL means new segment
394 * is at beginning of line). */
395 CkTextSegment *curPtr; /* Current segment; new characters
396 * are inserted just after this one.
397 * NULL means insert at beginning of
399 CkTextLine *linePtr; /* Current line (new segments are
400 * added to this line). */
401 register CkTextSegment *segPtr;
402 CkTextLine *newLinePtr;
403 int chunkSize; /* # characters in current chunk. */
404 register char *eol; /* Pointer to character just after last
405 * one in current chunk. */
406 int changeToLineCount; /* Counts change to total number of
409 prevPtr = SplitSeg(indexPtr);
410 linePtr = indexPtr->linePtr;
414 * Chop the string up into lines and create a new segment for
415 * each line, plus a new line for the leftovers from the
419 changeToLineCount = 0;
420 while (*string != 0) {
421 for (eol = string; *eol != 0; eol++) {
427 chunkSize = eol-string;
428 segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
429 segPtr->typePtr = &ckTextCharType;
430 if (curPtr == NULL) {
431 segPtr->nextPtr = linePtr->segPtr;
432 linePtr->segPtr = segPtr;
434 segPtr->nextPtr = curPtr->nextPtr;
435 curPtr->nextPtr = segPtr;
437 segPtr->size = chunkSize;
438 strncpy(segPtr->body.chars, string, (size_t) chunkSize);
439 segPtr->body.chars[chunkSize] = 0;
442 if (eol[-1] != '\n') {
447 * The chunk ended with a newline, so create a new CkTextLine
448 * and move the remainder of the old line to it.
451 newLinePtr = (CkTextLine *) ckalloc(sizeof(CkTextLine));
452 newLinePtr->parentPtr = linePtr->parentPtr;
453 newLinePtr->nextPtr = linePtr->nextPtr;
454 linePtr->nextPtr = newLinePtr;
455 newLinePtr->segPtr = segPtr->nextPtr;
456 segPtr->nextPtr = NULL;
457 linePtr = newLinePtr;
465 * Cleanup the starting line for the insertion, plus the ending
466 * line if it's different.
469 CleanupLine(indexPtr->linePtr);
470 if (linePtr != indexPtr->linePtr) {
471 CleanupLine(linePtr);
475 * Increment the line counts in all the parent nodes of the insertion
476 * point, then rebalance the tree if necessary.
479 for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
480 nodePtr = nodePtr->parentPtr) {
481 nodePtr->numLines += changeToLineCount;
483 nodePtr = linePtr->parentPtr;
484 nodePtr->numChildren += changeToLineCount;
485 if (nodePtr->numChildren > MAX_CHILDREN) {
486 Rebalance((BTree *) indexPtr->tree, nodePtr);
490 CkBTreeCheck(indexPtr->tree);
495 *--------------------------------------------------------------
499 * This procedure is called before adding or deleting
500 * segments. It does three things: (a) it finds the segment
501 * containing indexPtr; (b) if there are several such
502 * segments (because some segments have zero length) then
503 * it picks the first segment that does not have left
504 * gravity; (c) if the index refers to the middle of
505 * a segment then it splits the segment so that the
506 * index now refers to the beginning of a segment.
509 * The return value is a pointer to the segment just
510 * before the segment corresponding to indexPtr (as
511 * described above). If the segment corresponding to
512 * indexPtr is the first in its line then the return
516 * The segment referred to by indexPtr is split unless
517 * indexPtr refers to its first character.
519 *--------------------------------------------------------------
522 static CkTextSegment *
524 CkTextIndex *indexPtr; /* Index identifying position
525 * at which to split a segment. */
527 CkTextSegment *prevPtr, *segPtr;
530 for (count = indexPtr->charIndex, prevPtr = NULL,
531 segPtr = indexPtr->linePtr->segPtr; segPtr != NULL;
532 count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) {
533 if (segPtr->size > count) {
537 segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
538 if (prevPtr == NULL) {
539 indexPtr->linePtr->segPtr = segPtr;
541 prevPtr->nextPtr = segPtr;
544 } else if ((segPtr->size == 0) && (count == 0)
545 && !segPtr->typePtr->leftGravity) {
549 panic("SplitSeg reached end of line!");
554 *--------------------------------------------------------------
558 * This procedure is called after modifications have been
559 * made to a line. It scans over all of the segments in
560 * the line, giving each a chance to clean itself up, e.g.
561 * by merging with the following segments, updating internal
568 * Depends on what the segment-specific cleanup procedures do.
570 *--------------------------------------------------------------
575 CkTextLine *linePtr; /* Line to be cleaned up. */
577 CkTextSegment *segPtr, **prevPtrPtr;
581 * Make a pass over all of the segments in the line, giving each
582 * a chance to clean itself up. This could potentially change
583 * the structure of the line, e.g. by merging two segments
584 * together or having two segments cancel themselves; if so,
585 * then repeat the whole process again, since the first structure
586 * change might make other structure changes possible. Repeat
587 * until eventually there are no changes.
592 for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
594 prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
595 if (segPtr->typePtr->cleanupProc != NULL) {
596 *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
597 if (segPtr != *prevPtrPtr) {
609 *----------------------------------------------------------------------
611 * CkBTreeDeleteChars --
613 * Delete a range of characters from a B-tree. The caller
614 * must make sure that the final newline of the B-tree is
621 * Information is deleted from the B-tree. This can cause the
622 * internal structure of the B-tree to change. Note: because
623 * of changes to the B-tree structure, the indices pointed
624 * to by index1Ptr and index2Ptr should not be used after this
627 *----------------------------------------------------------------------
631 CkBTreeDeleteChars(index1Ptr, index2Ptr)
632 register CkTextIndex *index1Ptr; /* Indicates first character that is
634 register CkTextIndex *index2Ptr; /* Indicates character just after the
635 * last one that is to be deleted. */
637 CkTextSegment *prevPtr; /* The segment just before the start
638 * of the deletion range. */
639 CkTextSegment *lastPtr; /* The segment just after the end
640 * of the deletion range. */
641 CkTextSegment *segPtr, *nextPtr;
642 CkTextLine *curLinePtr;
643 Node *curNodePtr, *nodePtr;
646 * Tricky point: split at index2Ptr first; otherwise the split
647 * at index2Ptr may invalidate segPtr and/or prevPtr.
650 lastPtr = SplitSeg(index2Ptr);
651 if (lastPtr != NULL) {
652 lastPtr = lastPtr->nextPtr;
654 lastPtr = index2Ptr->linePtr->segPtr;
656 prevPtr = SplitSeg(index1Ptr);
657 if (prevPtr != NULL) {
658 segPtr = prevPtr->nextPtr;
659 prevPtr->nextPtr = lastPtr;
661 segPtr = index1Ptr->linePtr->segPtr;
662 index1Ptr->linePtr->segPtr = lastPtr;
666 * Delete all of the segments between prevPtr and lastPtr.
669 curLinePtr = index1Ptr->linePtr;
670 curNodePtr = curLinePtr->parentPtr;
671 while (segPtr != lastPtr) {
672 if (segPtr == NULL) {
673 CkTextLine *nextLinePtr;
676 * We just ran off the end of a line. First find the
677 * next line, then go back to the old line and delete it
678 * (unless it's the starting line for the range).
681 nextLinePtr = CkBTreeNextLine(curLinePtr);
682 if (curLinePtr != index1Ptr->linePtr) {
683 if (curNodePtr == index1Ptr->linePtr->parentPtr) {
684 index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
686 curNodePtr->children.linePtr = curLinePtr->nextPtr;
688 for (nodePtr = curNodePtr; nodePtr != NULL;
689 nodePtr = nodePtr->parentPtr) {
692 curNodePtr->numChildren--;
693 ckfree((char *) curLinePtr);
695 curLinePtr = nextLinePtr;
696 segPtr = curLinePtr->segPtr;
699 * If the node is empty then delete it and its parents,
700 * recursively upwards until a non-empty node is found.
703 while (curNodePtr->numChildren == 0) {
706 parentPtr = curNodePtr->parentPtr;
707 if (parentPtr->children.nodePtr == curNodePtr) {
708 parentPtr->children.nodePtr = curNodePtr->nextPtr;
710 Node *prevNodePtr = parentPtr->children.nodePtr;
711 while (prevNodePtr->nextPtr != curNodePtr) {
712 prevNodePtr = prevNodePtr->nextPtr;
714 prevNodePtr->nextPtr = curNodePtr->nextPtr;
716 parentPtr->numChildren--;
717 ckfree((char *) curNodePtr);
718 curNodePtr = parentPtr;
720 curNodePtr = curLinePtr->parentPtr;
724 nextPtr = segPtr->nextPtr;
725 if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
727 * This segment refuses to die. Move it to prevPtr and
728 * advance prevPtr if the segment has left gravity.
731 if (prevPtr == NULL) {
732 segPtr->nextPtr = index1Ptr->linePtr->segPtr;
733 index1Ptr->linePtr->segPtr = segPtr;
735 segPtr->nextPtr = prevPtr->nextPtr;
736 prevPtr->nextPtr = segPtr;
738 if (segPtr->typePtr->leftGravity) {
746 * If the beginning and end of the deletion range are in different
747 * lines, join the two lines together and discard the ending line.
750 if (index1Ptr->linePtr != index2Ptr->linePtr) {
751 CkTextLine *prevLinePtr;
753 for (segPtr = lastPtr; segPtr != NULL;
754 segPtr = segPtr->nextPtr) {
755 if (segPtr->typePtr->lineChangeProc != NULL) {
756 (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
759 curNodePtr = index2Ptr->linePtr->parentPtr;
760 for (nodePtr = curNodePtr; nodePtr != NULL;
761 nodePtr = nodePtr->parentPtr) {
764 curNodePtr->numChildren--;
765 prevLinePtr = curNodePtr->children.linePtr;
766 if (prevLinePtr == index2Ptr->linePtr) {
767 curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
769 while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
770 prevLinePtr = prevLinePtr->nextPtr;
772 prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
774 ckfree((char *) index2Ptr->linePtr);
775 Rebalance((BTree *) index2Ptr->tree, curNodePtr);
779 * Cleanup the segments in the new line.
782 CleanupLine(index1Ptr->linePtr);
785 * Lastly, rebalance the first node of the range.
788 Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
790 CkBTreeCheck(index1Ptr->tree);
795 *----------------------------------------------------------------------
799 * Find a particular line in a B-tree based on its line number.
802 * The return value is a pointer to the line structure for the
803 * line whose index is "line", or NULL if no such line exists.
808 *----------------------------------------------------------------------
812 CkBTreeFindLine(tree, line)
813 CkTextBTree tree; /* B-tree in which to find line. */
814 int line; /* Index of desired line. */
816 BTree *treePtr = (BTree *) tree;
817 register Node *nodePtr;
818 register CkTextLine *linePtr;
821 nodePtr = treePtr->rootPtr;
823 if ((line < 0) || (line >= nodePtr->numLines)) {
828 * Work down through levels of the tree until a node is found at
832 while (nodePtr->level != 0) {
833 for (nodePtr = nodePtr->children.nodePtr;
834 nodePtr->numLines <= linesLeft;
835 nodePtr = nodePtr->nextPtr) {
836 if (nodePtr == NULL) {
837 panic("CkBTreeFindLine ran out of nodes");
839 linesLeft -= nodePtr->numLines;
844 * Work through the lines attached to the level-0 node.
847 for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
848 linePtr = linePtr->nextPtr) {
849 if (linePtr == NULL) {
850 panic("CkBTreeFindLine ran out of lines");
858 *----------------------------------------------------------------------
862 * Given an existing line in a B-tree, this procedure locates the
863 * next line in the B-tree. This procedure is used for scanning
864 * through the B-tree.
867 * The return value is a pointer to the line that immediately
868 * follows linePtr, or NULL if there is no such line.
873 *----------------------------------------------------------------------
877 CkBTreeNextLine(linePtr)
878 register CkTextLine *linePtr; /* Pointer to existing line in
881 register Node *nodePtr;
883 if (linePtr->nextPtr != NULL) {
884 return linePtr->nextPtr;
888 * This was the last line associated with the particular parent node.
889 * Search up the tree for the next node, then search down from that
890 * node to find the first line,
893 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
894 if (nodePtr->nextPtr != NULL) {
895 nodePtr = nodePtr->nextPtr;
898 if (nodePtr->parentPtr == NULL) {
899 return (CkTextLine *) NULL;
902 while (nodePtr->level > 0) {
903 nodePtr = nodePtr->children.nodePtr;
905 return nodePtr->children.linePtr;
909 *----------------------------------------------------------------------
911 * CkBTreeLineIndex --
913 * Given a pointer to a line in a B-tree, return the numerical
914 * index of that line.
917 * The result is the index of linePtr within the tree, where 0
918 * corresponds to the first line in the tree.
923 *----------------------------------------------------------------------
927 CkBTreeLineIndex(linePtr)
928 CkTextLine *linePtr; /* Pointer to existing line in
931 register CkTextLine *linePtr2;
932 register Node *nodePtr, *parentPtr, *nodePtr2;
936 * First count how many lines precede this one in its level-0
940 nodePtr = linePtr->parentPtr;
942 for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
943 linePtr2 = linePtr2->nextPtr) {
944 if (linePtr2 == NULL) {
945 panic("CkBTreeLineIndex couldn't find line");
951 * Now work up through the levels of the tree one at a time,
952 * counting how many lines are in nodes preceding the current
956 for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
957 nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
958 for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
959 nodePtr2 = nodePtr2->nextPtr) {
960 if (nodePtr2 == NULL) {
961 panic("CkBTreeLineIndex couldn't find node");
963 index += nodePtr2->numLines;
970 *----------------------------------------------------------------------
972 * CkBTreeLinkSegment --
974 * This procedure adds a new segment to a B-tree at a given
981 * SegPtr will be linked into its tree.
983 *----------------------------------------------------------------------
988 CkBTreeLinkSegment(segPtr, indexPtr)
989 CkTextSegment *segPtr; /* Pointer to new segment to be added to
990 * B-tree. Should be completely initialized
991 * by caller except for nextPtr field. */
992 CkTextIndex *indexPtr; /* Where to add segment: it gets linked
993 * in just before the segment indicated
996 register CkTextSegment *prevPtr;
998 prevPtr = SplitSeg(indexPtr);
999 if (prevPtr == NULL) {
1000 segPtr->nextPtr = indexPtr->linePtr->segPtr;
1001 indexPtr->linePtr->segPtr = segPtr;
1003 segPtr->nextPtr = prevPtr->nextPtr;
1004 prevPtr->nextPtr = segPtr;
1006 CleanupLine(indexPtr->linePtr);
1008 CkBTreeCheck(indexPtr->tree);
1013 *----------------------------------------------------------------------
1015 * CkBTreeUnlinkSegment --
1017 * This procedure unlinks a segment from its line in a B-tree.
1023 * SegPtr will be unlinked from linePtr. The segment itself
1024 * isn't modified by this procedure.
1026 *----------------------------------------------------------------------
1031 CkBTreeUnlinkSegment(tree, segPtr, linePtr)
1032 CkTextBTree tree; /* Tree containing segment. */
1033 CkTextSegment *segPtr; /* Segment to be unlinked. */
1034 CkTextLine *linePtr; /* Line that currently contains
1037 register CkTextSegment *prevPtr;
1039 if (linePtr->segPtr == segPtr) {
1040 linePtr->segPtr = segPtr->nextPtr;
1042 for (prevPtr = linePtr->segPtr; prevPtr->nextPtr != segPtr;
1043 prevPtr = prevPtr->nextPtr) {
1044 /* Empty loop body. */
1046 prevPtr->nextPtr = segPtr->nextPtr;
1048 CleanupLine(linePtr);
1052 *----------------------------------------------------------------------
1056 * Turn a given tag on or off for a given range of characters in
1063 * The given tag is added to the given range of characters
1064 * in the tree or removed from all those characters, depending
1065 * on the "add" argument. The structure of the btree is modified
1066 * enough that index1Ptr and index2Ptr are no longer valid after
1067 * this procedure returns, and the indexes may be modified by
1070 *----------------------------------------------------------------------
1074 CkBTreeTag(index1Ptr, index2Ptr, tagPtr, add)
1075 register CkTextIndex *index1Ptr; /* Indicates first character in
1077 register CkTextIndex *index2Ptr; /* Indicates character just after the
1078 * last one in range. */
1079 CkTextTag *tagPtr; /* Tag to add or remove. */
1080 int add; /* One means add tag to the given
1081 * range of characters; zero means
1082 * remove the tag from the range. */
1084 CkTextSegment *segPtr, *prevPtr;
1085 CkTextSearch search;
1086 CkTextLine *cleanupLinePtr;
1090 * See whether the tag is present at the start of the range. If
1091 * the state doesn't already match what we want then add a toggle
1095 oldState = CkBTreeCharTagged(index1Ptr, tagPtr);
1096 if ((add != 0) ^ oldState) {
1097 segPtr = (CkTextSegment *) ckalloc(TSEG_SIZE);
1098 segPtr->typePtr = (add) ? &ckTextToggleOnType : &ckTextToggleOffType;
1099 prevPtr = SplitSeg(index1Ptr);
1100 if (prevPtr == NULL) {
1101 segPtr->nextPtr = index1Ptr->linePtr->segPtr;
1102 index1Ptr->linePtr->segPtr = segPtr;
1104 segPtr->nextPtr = prevPtr->nextPtr;
1105 prevPtr->nextPtr = segPtr;
1108 segPtr->body.toggle.tagPtr = tagPtr;
1109 segPtr->body.toggle.inNodeCounts = 0;
1113 * Scan the range of characters and delete any internal tag
1114 * transitions. Keep track of what the old state was at the end
1115 * of the range, and add a toggle there if it's needed.
1118 CkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
1119 cleanupLinePtr = index1Ptr->linePtr;
1120 while (CkBTreeNextTag(&search)) {
1122 segPtr = search.segPtr;
1123 prevPtr = search.curIndex.linePtr->segPtr;
1124 if (prevPtr == segPtr) {
1125 search.curIndex.linePtr->segPtr = segPtr->nextPtr;
1127 while (prevPtr->nextPtr != segPtr) {
1128 prevPtr = prevPtr->nextPtr;
1130 prevPtr->nextPtr = segPtr->nextPtr;
1132 if (segPtr->body.toggle.inNodeCounts) {
1133 ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr,
1134 segPtr->body.toggle.tagPtr, -1);
1135 segPtr->body.toggle.inNodeCounts = 0;
1137 ckfree((char *) segPtr);
1140 * The code below is a bit tricky. After deleting a toggle
1141 * we eventually have to call CleanupLine, in order to allow
1142 * character segments to be merged together. To do this, we
1143 * remember in cleanupLinePtr a line that needs to be
1144 * cleaned up, but we don't clean it up until we've moved
1145 * on to a different line. That way the cleanup process
1146 * won't goof up segPtr.
1149 if (cleanupLinePtr != search.curIndex.linePtr) {
1150 CleanupLine(cleanupLinePtr);
1151 cleanupLinePtr = search.curIndex.linePtr;
1154 if ((add != 0) ^ oldState) {
1155 segPtr = (CkTextSegment *) ckalloc(TSEG_SIZE);
1156 segPtr->typePtr = (add) ? &ckTextToggleOffType : &ckTextToggleOnType;
1157 prevPtr = SplitSeg(index2Ptr);
1158 if (prevPtr == NULL) {
1159 segPtr->nextPtr = index2Ptr->linePtr->segPtr;
1160 index2Ptr->linePtr->segPtr = segPtr;
1162 segPtr->nextPtr = prevPtr->nextPtr;
1163 prevPtr->nextPtr = segPtr;
1166 segPtr->body.toggle.tagPtr = tagPtr;
1167 segPtr->body.toggle.inNodeCounts = 0;
1171 * Cleanup cleanupLinePtr and the last line of the range, if
1172 * these are different.
1175 CleanupLine(cleanupLinePtr);
1176 if (cleanupLinePtr != index2Ptr->linePtr) {
1177 CleanupLine(index2Ptr->linePtr);
1181 CkBTreeCheck(index1Ptr->tree);
1186 *----------------------------------------------------------------------
1188 * ChangeNodeToggleCount --
1190 * This procedure increments or decrements the toggle count for
1191 * a particular tag in a particular node and all its ancestors.
1197 * The toggle count for tag is adjusted up or down by "delta" in
1200 *----------------------------------------------------------------------
1204 ChangeNodeToggleCount(nodePtr, tagPtr, delta)
1205 register Node *nodePtr; /* Node whose toggle count for a tag
1206 * must be changed. */
1207 CkTextTag *tagPtr; /* Information about tag. */
1208 int delta; /* Amount to add to current toggle
1209 * count for tag (may be negative). */
1211 register Summary *summaryPtr, *prevPtr;
1214 * Iterate over the node and all of its ancestors.
1217 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
1219 * See if there's already an entry for this tag for this node. If so,
1220 * perhaps all we have to do is adjust its count.
1223 for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
1225 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
1226 if (summaryPtr->tagPtr != tagPtr) {
1229 summaryPtr->toggleCount += delta;
1230 if (summaryPtr->toggleCount > 0) {
1233 if (summaryPtr->toggleCount < 0) {
1234 panic("ChangeNodeToggleCount: negative toggle count");
1238 * Zero count; must remove this tag from the list.
1241 if (prevPtr == NULL) {
1242 nodePtr->summaryPtr = summaryPtr->nextPtr;
1244 prevPtr->nextPtr = summaryPtr->nextPtr;
1246 ckfree((char *) summaryPtr);
1251 * This tag isn't in the list. Add a new entry to the list.
1255 panic("ChangeNodeToggleCount: negative delta, no tag entry");
1257 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
1258 summaryPtr->tagPtr = tagPtr;
1259 summaryPtr->toggleCount = delta;
1260 summaryPtr->nextPtr = nodePtr->summaryPtr;
1261 nodePtr->summaryPtr = summaryPtr;
1269 *----------------------------------------------------------------------
1271 * CkBTreeStartSearch --
1273 * This procedure sets up a search for tag transitions involving
1274 * a given tag (or all tags) in a given range of the text.
1280 * The information at *searchPtr is set up so that subsequent calls
1281 * to CkBTreeNextTag will return information about the locations of
1282 * tag transitions. Note that CkBTreeNextTag must be called to get
1283 * the first transition.
1285 *----------------------------------------------------------------------
1289 CkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, searchPtr)
1290 CkTextIndex *index1Ptr; /* Search starts here. Tag toggles
1291 * at this position will not be
1293 CkTextIndex *index2Ptr; /* Search stops here. Tag toggles
1294 * at this position *will* be
1296 CkTextTag *tagPtr; /* Tag to search for. NULL means
1297 * search for any tag. */
1298 register CkTextSearch *searchPtr; /* Where to store information about
1299 * search's progress. */
1303 searchPtr->curIndex = *index1Ptr;
1304 searchPtr->segPtr = NULL;
1305 searchPtr->nextPtr = CkTextIndexToSeg(index1Ptr, &offset);
1306 searchPtr->curIndex.charIndex -= offset;
1307 searchPtr->lastPtr = CkTextIndexToSeg(index2Ptr, (int *) NULL);
1308 searchPtr->tagPtr = tagPtr;
1309 searchPtr->linesLeft = CkBTreeLineIndex(index2Ptr->linePtr) + 1
1310 - CkBTreeLineIndex(index1Ptr->linePtr);
1311 searchPtr->allTags = (tagPtr == NULL);
1312 if (searchPtr->linesLeft == 1) {
1314 * Starting and stopping segments are in the same line; mark the
1315 * search as over immediately if the second segment is before the
1319 if (index1Ptr->charIndex >= index2Ptr->charIndex) {
1320 searchPtr->linesLeft = 0;
1326 *----------------------------------------------------------------------
1330 * Once a tag search has begun, successive calls to this procedure
1331 * return successive tag toggles. Note: it is NOT SAFE to call this
1332 * procedure if characters have been inserted into or deleted from
1333 * the B-tree since the call to CkBTreeStartSearch.
1336 * The return value is 1 if another toggle was found that met the
1337 * criteria specified in the call to CkBTreeStartSearch; in this
1338 * case searchPtr->curIndex gives the toggle's position and
1339 * searchPtr->curTagPtr points to its segment. 0 is returned if
1340 * no more matching tag transitions were found; in this case
1341 * searchPtr->curIndex is the same as searchPtr->stopIndex.
1344 * Information in *searchPtr is modified to update the state of the
1345 * search and indicate where the next tag toggle is located.
1347 *----------------------------------------------------------------------
1351 CkBTreeNextTag(searchPtr)
1352 register CkTextSearch *searchPtr; /* Information about search in
1353 * progress; must have been set up by
1354 * call to CkBTreeStartSearch. */
1356 register CkTextSegment *segPtr;
1357 register Node *nodePtr;
1358 register Summary *summaryPtr;
1360 if (searchPtr->linesLeft <= 0) {
1365 * The outermost loop iterates over lines that may potentially contain
1366 * a relevant tag transition, starting from the current segment in
1370 segPtr = searchPtr->nextPtr;
1373 * Check for more tags on the current line.
1376 for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) {
1377 if (segPtr == searchPtr->lastPtr) {
1380 if (((segPtr->typePtr == &ckTextToggleOnType)
1381 || (segPtr->typePtr == &ckTextToggleOffType))
1382 && (searchPtr->allTags
1383 || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
1384 searchPtr->segPtr = segPtr;
1385 searchPtr->nextPtr = segPtr->nextPtr;
1386 searchPtr->tagPtr = segPtr->body.toggle.tagPtr;
1389 searchPtr->curIndex.charIndex += segPtr->size;
1393 * See if there are more lines associated with the current parent
1394 * node. If so, go back to the top of the loop to search the next
1398 nodePtr = searchPtr->curIndex.linePtr->parentPtr;
1399 searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr;
1400 searchPtr->linesLeft--;
1401 if (searchPtr->linesLeft <= 0) {
1404 if (searchPtr->curIndex.linePtr != NULL) {
1405 segPtr = searchPtr->curIndex.linePtr->segPtr;
1406 searchPtr->curIndex.charIndex = 0;
1411 * Search across and up through the B-tree's node hierarchy looking
1412 * for the next node that has a relevant tag transition somewhere in
1413 * its subtree. Be sure to update linesLeft as we skip over large
1418 while (nodePtr->nextPtr == NULL) {
1419 if (nodePtr->parentPtr == NULL) {
1422 nodePtr = nodePtr->parentPtr;
1424 nodePtr = nodePtr->nextPtr;
1425 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1426 summaryPtr = summaryPtr->nextPtr) {
1427 if ((searchPtr->allTags) ||
1428 (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1429 goto gotNodeWithTag;
1432 searchPtr->linesLeft -= nodePtr->numLines;
1436 * At this point we've found a subtree that has a relevant tag
1437 * transition. Now search down (and across) through that subtree
1438 * to find the first level-0 node that has a relevant tag transition.
1442 while (nodePtr->level > 0) {
1443 for (nodePtr = nodePtr->children.nodePtr; ;
1444 nodePtr = nodePtr->nextPtr) {
1445 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1446 summaryPtr = summaryPtr->nextPtr) {
1447 if ((searchPtr->allTags)
1448 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1452 searchPtr->linesLeft -= nodePtr->numLines;
1453 if (nodePtr->nextPtr == NULL) {
1454 panic("CkBTreeNextTag found incorrect tag summary info.");
1462 * Now we're down to a level-0 node that contains a line that contains
1463 * a relevant tag transition. Set up line information and go back to
1464 * the beginning of the loop to search through lines.
1467 searchPtr->curIndex.linePtr = nodePtr->children.linePtr;
1468 searchPtr->curIndex.charIndex = 0;
1469 segPtr = searchPtr->curIndex.linePtr->segPtr;
1470 if (searchPtr->linesLeft <= 0) {
1477 searchPtr->linesLeft = 0;
1478 searchPtr->segPtr = NULL;
1483 *----------------------------------------------------------------------
1485 * CkBTreeCharTagged --
1487 * Determine whether a particular character has a particular tag.
1490 * The return value is 1 if the given tag is in effect at the
1491 * character given by linePtr and ch, and 0 otherwise.
1496 *----------------------------------------------------------------------
1500 CkBTreeCharTagged(indexPtr, tagPtr)
1501 CkTextIndex *indexPtr; /* Indicates a character position at
1502 * which to check for a tag. */
1503 CkTextTag *tagPtr; /* Tag of interest. */
1505 register Node *nodePtr;
1506 register CkTextLine *siblingLinePtr;
1507 register CkTextSegment *segPtr;
1508 CkTextSegment *toggleSegPtr;
1512 * Check for toggles for the tag in indexPtr's line but before
1513 * indexPtr. If there is one, its type indicates whether or
1514 * not the character is tagged.
1517 toggleSegPtr = NULL;
1518 for (index = 0, segPtr = indexPtr->linePtr->segPtr;
1519 (index + segPtr->size) <= indexPtr->charIndex;
1520 index += segPtr->size, segPtr = segPtr->nextPtr) {
1521 if (((segPtr->typePtr == &ckTextToggleOnType)
1522 || (segPtr->typePtr == &ckTextToggleOffType))
1523 && (segPtr->body.toggle.tagPtr == tagPtr)) {
1524 toggleSegPtr = segPtr;
1527 if (toggleSegPtr != NULL) {
1528 return (toggleSegPtr->typePtr == &ckTextToggleOnType);
1532 * No toggle in this line. Look for toggles for the tag in lines
1533 * that are predecessors of indexPtr->linePtr but under the same
1538 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
1539 siblingLinePtr != indexPtr->linePtr;
1540 siblingLinePtr = siblingLinePtr->nextPtr) {
1541 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
1542 segPtr = segPtr->nextPtr) {
1543 if (((segPtr->typePtr == &ckTextToggleOnType)
1544 || (segPtr->typePtr == &ckTextToggleOffType))
1545 && (segPtr->body.toggle.tagPtr == tagPtr)) {
1546 toggleSegPtr = segPtr;
1550 if (toggleSegPtr != NULL) {
1551 return (toggleSegPtr->typePtr == &ckTextToggleOnType);
1555 * No toggle in this node. Scan upwards through the ancestors of
1556 * this node, counting the number of toggles of the given tag in
1557 * siblings that precede that node.
1561 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
1562 nodePtr = nodePtr->parentPtr) {
1563 register Node *siblingPtr;
1564 register Summary *summaryPtr;
1566 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
1567 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
1568 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
1569 summaryPtr = summaryPtr->nextPtr) {
1570 if (summaryPtr->tagPtr == tagPtr) {
1571 toggles += summaryPtr->toggleCount;
1578 * An odd number of toggles means that the tag is present at the
1586 *----------------------------------------------------------------------
1590 * Return information about all of the tags that are associated
1591 * with a particular character in a B-tree of text.
1594 * The return value is a malloc-ed array containing pointers to
1595 * information for each of the tags that is associated with
1596 * the character at the position given by linePtr and ch. The
1597 * word at *numTagsPtr is filled in with the number of pointers
1598 * in the array. It is up to the caller to free the array by
1599 * passing it to free. If there are no tags at the given character
1600 * then a NULL pointer is returned and *numTagsPtr will be set to 0.
1605 *----------------------------------------------------------------------
1610 CkBTreeGetTags(indexPtr, numTagsPtr)
1611 CkTextIndex *indexPtr; /* Indicates a particular position in
1613 int *numTagsPtr; /* Store number of tags found at this
1616 register Node *nodePtr;
1617 register CkTextLine *siblingLinePtr;
1618 register CkTextSegment *segPtr;
1619 int src, dst, index;
1621 #define NUM_TAG_INFOS 10
1623 tagInfo.numTags = 0;
1624 tagInfo.arraySize = NUM_TAG_INFOS;
1625 tagInfo.tagPtrs = (CkTextTag **) ckalloc((unsigned)
1626 NUM_TAG_INFOS*sizeof(CkTextTag *));
1627 tagInfo.counts = (int *) ckalloc((unsigned)
1628 NUM_TAG_INFOS*sizeof(int));
1631 * Record tag toggles within the line of indexPtr but preceding
1635 for (index = 0, segPtr = indexPtr->linePtr->segPtr;
1636 (index + segPtr->size) <= indexPtr->charIndex;
1637 index += segPtr->size, segPtr = segPtr->nextPtr) {
1638 if ((segPtr->typePtr == &ckTextToggleOnType)
1639 || (segPtr->typePtr == &ckTextToggleOffType)) {
1640 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
1645 * Record toggles for tags in lines that are predecessors of
1646 * indexPtr->linePtr but under the same level-0 node.
1649 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
1650 siblingLinePtr != indexPtr->linePtr;
1651 siblingLinePtr = siblingLinePtr->nextPtr) {
1652 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
1653 segPtr = segPtr->nextPtr) {
1654 if ((segPtr->typePtr == &ckTextToggleOnType)
1655 || (segPtr->typePtr == &ckTextToggleOffType)) {
1656 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
1662 * For each node in the ancestry of this line, record tag toggles
1663 * for all siblings that precede that node.
1666 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
1667 nodePtr = nodePtr->parentPtr) {
1668 register Node *siblingPtr;
1669 register Summary *summaryPtr;
1671 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
1672 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
1673 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
1674 summaryPtr = summaryPtr->nextPtr) {
1675 if (summaryPtr->toggleCount & 1) {
1676 IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount,
1684 * Go through the tag information and squash out all of the tags
1685 * that have even toggle counts (these tags exist before the point
1686 * of interest, but not at the desired character itself).
1689 for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
1690 if (tagInfo.counts[src] & 1) {
1691 tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
1696 ckfree((char *) tagInfo.counts);
1698 ckfree((char *) tagInfo.tagPtrs);
1701 return tagInfo.tagPtrs;
1705 *----------------------------------------------------------------------
1709 * This is a utility procedure used by CkBTreeGetTags. It
1710 * increments the count for a particular tag, adding a new
1711 * entry for that tag if there wasn't one previously.
1717 * The information at *tagInfoPtr may be modified, and the arrays
1718 * may be reallocated to make them larger.
1720 *----------------------------------------------------------------------
1724 IncCount(tagPtr, inc, tagInfoPtr)
1725 CkTextTag *tagPtr; /* Handle for tag. */
1726 int inc; /* Amount by which to increment tag count. */
1727 TagInfo *tagInfoPtr; /* Holds cumulative information about tags;
1728 * increment count here. */
1730 register CkTextTag **tagPtrPtr;
1733 for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
1734 count > 0; tagPtrPtr++, count--) {
1735 if (*tagPtrPtr == tagPtr) {
1736 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
1742 * There isn't currently an entry for this tag, so we have to
1743 * make a new one. If the arrays are full, then enlarge the
1747 if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
1748 CkTextTag **newTags;
1749 int *newCounts, newSize;
1751 newSize = 2*tagInfoPtr->arraySize;
1752 newTags = (CkTextTag **) ckalloc((unsigned)
1753 (newSize*sizeof(CkTextTag *)));
1754 memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
1755 tagInfoPtr->arraySize * sizeof(CkTextTag *));
1756 ckfree((char *) tagInfoPtr->tagPtrs);
1757 tagInfoPtr->tagPtrs = newTags;
1758 newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
1759 memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
1760 tagInfoPtr->arraySize * sizeof(int));
1761 ckfree((char *) tagInfoPtr->counts);
1762 tagInfoPtr->counts = newCounts;
1763 tagInfoPtr->arraySize = newSize;
1766 tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
1767 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
1768 tagInfoPtr->numTags++;
1772 *----------------------------------------------------------------------
1776 * This procedure runs a set of consistency checks over a B-tree
1777 * and panics if any inconsistencies are found.
1783 * If a structural defect is found, the procedure panics with an
1786 *----------------------------------------------------------------------
1791 CkTextBTree tree; /* Tree to check. */
1793 BTree *treePtr = (BTree *) tree;
1794 register Summary *summaryPtr;
1795 register Node *nodePtr;
1796 register CkTextLine *linePtr;
1797 register CkTextSegment *segPtr;
1800 * Make sure that overall there is an even count of tag transitions
1801 * for the whole tree.
1804 for (summaryPtr = treePtr->rootPtr->summaryPtr; summaryPtr != NULL;
1805 summaryPtr = summaryPtr->nextPtr) {
1806 if (summaryPtr->toggleCount & 1) {
1807 panic("CkBTreeCheck found odd toggle count for \"%s\" (%d)",
1808 summaryPtr->tagPtr->name, summaryPtr->toggleCount);
1813 * Call a recursive procedure to do the main body of checks.
1816 nodePtr = treePtr->rootPtr;
1817 CheckNodeConsistency(treePtr->rootPtr);
1820 * Make sure that there are at least two lines in the text and
1821 * that the last line has no characters except a newline.
1824 if (nodePtr->numLines < 2) {
1825 panic("CkBTreeCheck: less than 2 lines in tree");
1827 while (nodePtr->level > 0) {
1828 nodePtr = nodePtr->children.nodePtr;
1829 while (nodePtr->nextPtr != NULL) {
1830 nodePtr = nodePtr->nextPtr;
1833 linePtr = nodePtr->children.linePtr;
1834 while (linePtr->nextPtr != NULL) {
1835 linePtr = linePtr->nextPtr;
1837 segPtr = linePtr->segPtr;
1838 while ((segPtr->typePtr == &ckTextToggleOffType)
1839 || (segPtr->typePtr == &ckTextRightMarkType)
1840 || (segPtr->typePtr == &ckTextLeftMarkType)) {
1842 * It's OK to toggle a tag off in the last line, but
1843 * not to start a new range. It's also OK to have marks
1847 segPtr = segPtr->nextPtr;
1849 if (segPtr->typePtr != &ckTextCharType) {
1850 panic("CkBTreeCheck: last line has bogus segment type");
1852 if (segPtr->nextPtr != NULL) {
1853 panic("CkBTreeCheck: last line has too many segments");
1855 if (segPtr->size != 1) {
1856 panic("CkBTreeCheck: last line has wrong # characters: %d",
1859 if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) {
1860 panic("CkBTreeCheck: last line had bad value: %s",
1861 segPtr->body.chars);
1866 *----------------------------------------------------------------------
1868 * CheckNodeConsistency --
1870 * This procedure is called as part of consistency checking for
1871 * B-trees: it checks several aspects of a node and also runs
1872 * checks recursively on the node's children.
1878 * If anything suspicious is found in the tree structure, the
1881 *----------------------------------------------------------------------
1885 CheckNodeConsistency(nodePtr)
1886 register Node *nodePtr; /* Node whose subtree should be
1889 register Node *childNodePtr;
1890 register Summary *summaryPtr, *summaryPtr2;
1891 register CkTextLine *linePtr;
1892 register CkTextSegment *segPtr;
1893 int numChildren, numLines, toggleCount, minChildren;
1895 if (nodePtr->parentPtr != NULL) {
1896 minChildren = MIN_CHILDREN;
1897 } else if (nodePtr->level > 0) {
1902 if ((nodePtr->numChildren < minChildren)
1903 || (nodePtr->numChildren > MAX_CHILDREN)) {
1904 panic("CheckNodeConsistency: bad child count (%d)",
1905 nodePtr->numChildren);
1910 if (nodePtr->level == 0) {
1911 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
1912 linePtr = linePtr->nextPtr) {
1913 if (linePtr->parentPtr != nodePtr) {
1914 panic("CheckNodeConsistency: line doesn't point to parent");
1916 if (linePtr->segPtr == NULL) {
1917 panic("CheckNodeConsistency: line has no segments");
1919 for (segPtr = linePtr->segPtr; segPtr != NULL;
1920 segPtr = segPtr->nextPtr) {
1921 if (segPtr->typePtr->checkProc != NULL) {
1922 (*segPtr->typePtr->checkProc)(segPtr, linePtr);
1924 if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity)
1925 && (segPtr->nextPtr != NULL)
1926 && (segPtr->nextPtr->size == 0)
1927 && (segPtr->nextPtr->typePtr->leftGravity)) {
1928 panic("CheckNodeConsistency: wrong segment order for gravity");
1930 if ((segPtr->nextPtr == NULL)
1931 && (segPtr->typePtr != &ckTextCharType)) {
1932 panic("CheckNodeConsistency: line ended with wrong type");
1939 for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
1940 childNodePtr = childNodePtr->nextPtr) {
1941 if (childNodePtr->parentPtr != nodePtr) {
1942 panic("CheckNodeConsistency: node doesn't point to parent");
1944 if (childNodePtr->level != (nodePtr->level-1)) {
1945 panic("CheckNodeConsistency: level mismatch (%d %d)",
1946 nodePtr->level, childNodePtr->level);
1948 CheckNodeConsistency(childNodePtr);
1949 for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
1950 summaryPtr = summaryPtr->nextPtr) {
1951 for (summaryPtr2 = nodePtr->summaryPtr; ;
1952 summaryPtr2 = summaryPtr2->nextPtr) {
1953 if (summaryPtr2 == NULL) {
1954 panic("CheckNodeConsistency: node tag \"%s\" not %s",
1955 summaryPtr->tagPtr->name,
1956 "present in parent summaries");
1958 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
1964 numLines += childNodePtr->numLines;
1967 if (numChildren != nodePtr->numChildren) {
1968 panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
1969 numChildren, nodePtr->numChildren);
1971 if (numLines != nodePtr->numLines) {
1972 panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
1973 numLines, nodePtr->numLines);
1976 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1977 summaryPtr = summaryPtr->nextPtr) {
1979 if (nodePtr->level == 0) {
1980 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
1981 linePtr = linePtr->nextPtr) {
1982 for (segPtr = linePtr->segPtr; segPtr != NULL;
1983 segPtr = segPtr->nextPtr) {
1984 if ((segPtr->typePtr != &ckTextToggleOnType)
1985 && (segPtr->typePtr != &ckTextToggleOffType)) {
1988 if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) {
1994 for (childNodePtr = nodePtr->children.nodePtr;
1995 childNodePtr != NULL;
1996 childNodePtr = childNodePtr->nextPtr) {
1997 for (summaryPtr2 = childNodePtr->summaryPtr;
1998 summaryPtr2 != NULL;
1999 summaryPtr2 = summaryPtr2->nextPtr) {
2000 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2001 toggleCount += summaryPtr2->toggleCount;
2006 if (toggleCount != summaryPtr->toggleCount) {
2007 panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
2008 toggleCount, summaryPtr->toggleCount);
2010 for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
2011 summaryPtr2 = summaryPtr2->nextPtr) {
2012 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2013 panic("CheckNodeConsistency: duplicated node tag: %s",
2014 summaryPtr->tagPtr->name);
2021 *----------------------------------------------------------------------
2025 * This procedure is called when a node of a B-tree appears to be
2026 * out of balance (too many children, or too few). It rebalances
2027 * that node and all of its ancestors in the tree.
2033 * The internal structure of treePtr may change.
2035 *----------------------------------------------------------------------
2039 Rebalance(treePtr, nodePtr)
2040 BTree *treePtr; /* Tree that is being rebalanced. */
2041 register Node *nodePtr; /* Node that may be out of balance. */
2044 * Loop over the entire ancestral chain of the node, working up
2045 * through the tree one node at a time until the root node has
2049 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
2050 register Node *newPtr, *childPtr;
2051 register CkTextLine *linePtr;
2055 * Check to see if the node has too many children. If it does,
2056 * then split off all but the first MIN_CHILDREN into a separate
2057 * node following the original one. Then repeat until the
2058 * node has a decent size.
2061 if (nodePtr->numChildren > MAX_CHILDREN) {
2064 * If the node being split is the root node, then make a
2065 * new root node above it first.
2068 if (nodePtr->parentPtr == NULL) {
2069 newPtr = (Node *) ckalloc(sizeof(Node));
2070 newPtr->parentPtr = NULL;
2071 newPtr->nextPtr = NULL;
2072 newPtr->summaryPtr = NULL;
2073 newPtr->level = nodePtr->level + 1;
2074 newPtr->children.nodePtr = nodePtr;
2075 newPtr->numChildren = 1;
2076 newPtr->numLines = nodePtr->numLines;
2077 RecomputeNodeCounts(newPtr);
2078 treePtr->rootPtr = newPtr;
2080 newPtr = (Node *) ckalloc(sizeof(Node));
2081 newPtr->parentPtr = nodePtr->parentPtr;
2082 newPtr->nextPtr = nodePtr->nextPtr;
2083 nodePtr->nextPtr = newPtr;
2084 newPtr->summaryPtr = NULL;
2085 newPtr->level = nodePtr->level;
2086 newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
2087 if (nodePtr->level == 0) {
2088 for (i = MIN_CHILDREN-1,
2089 linePtr = nodePtr->children.linePtr;
2090 i > 0; i--, linePtr = linePtr->nextPtr) {
2091 /* Empty loop body. */
2093 newPtr->children.linePtr = linePtr->nextPtr;
2094 linePtr->nextPtr = NULL;
2096 for (i = MIN_CHILDREN-1,
2097 childPtr = nodePtr->children.nodePtr;
2098 i > 0; i--, childPtr = childPtr->nextPtr) {
2099 /* Empty loop body. */
2101 newPtr->children.nodePtr = childPtr->nextPtr;
2102 childPtr->nextPtr = NULL;
2104 RecomputeNodeCounts(nodePtr);
2105 nodePtr->parentPtr->numChildren++;
2107 if (nodePtr->numChildren <= MAX_CHILDREN) {
2108 RecomputeNodeCounts(nodePtr);
2114 while (nodePtr->numChildren < MIN_CHILDREN) {
2115 register Node *otherPtr;
2116 Node *halfwayNodePtr = NULL; /* Initialization needed only */
2117 CkTextLine *halfwayLinePtr = NULL; /* to prevent cc warnings. */
2118 int totalChildren, firstChildren, i;
2121 * Too few children for this node. If this is the root then,
2122 * it's OK for it to have less than MIN_CHILDREN children
2123 * as long as it's got at least two. If it has only one
2124 * (and isn't at level 0), then chop the root node out of
2125 * the tree and use its child as the new root.
2128 if (nodePtr->parentPtr == NULL) {
2129 if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
2130 treePtr->rootPtr = nodePtr->children.nodePtr;
2131 treePtr->rootPtr->parentPtr = NULL;
2132 DeleteSummaries(nodePtr->summaryPtr);
2133 ckfree((char *) nodePtr);
2139 * Not the root. Make sure that there are siblings to
2143 if (nodePtr->parentPtr->numChildren < 2) {
2144 Rebalance(treePtr, nodePtr->parentPtr);
2149 * Find a sibling neighbor to borrow from, and arrange for
2150 * nodePtr to be the earlier of the pair.
2153 if (nodePtr->nextPtr == NULL) {
2154 for (otherPtr = nodePtr->parentPtr->children.nodePtr;
2155 otherPtr->nextPtr != nodePtr;
2156 otherPtr = otherPtr->nextPtr) {
2157 /* Empty loop body. */
2161 otherPtr = nodePtr->nextPtr;
2164 * We're going to either merge the two siblings together
2165 * into one node or redivide the children among them to
2166 * balance their loads. As preparation, join their two
2167 * child lists into a single list and remember the half-way
2168 * point in the list.
2171 totalChildren = nodePtr->numChildren + otherPtr->numChildren;
2172 firstChildren = totalChildren/2;
2173 if (nodePtr->children.nodePtr == NULL) {
2174 nodePtr->children = otherPtr->children;
2175 otherPtr->children.nodePtr = NULL;
2176 otherPtr->children.linePtr = NULL;
2178 if (nodePtr->level == 0) {
2179 register CkTextLine *linePtr;
2181 for (linePtr = nodePtr->children.linePtr, i = 1;
2182 linePtr->nextPtr != NULL;
2183 linePtr = linePtr->nextPtr, i++) {
2184 if (i == firstChildren) {
2185 halfwayLinePtr = linePtr;
2188 linePtr->nextPtr = otherPtr->children.linePtr;
2189 while (i <= firstChildren) {
2190 halfwayLinePtr = linePtr;
2191 linePtr = linePtr->nextPtr;
2195 register Node *childPtr;
2197 for (childPtr = nodePtr->children.nodePtr, i = 1;
2198 childPtr->nextPtr != NULL;
2199 childPtr = childPtr->nextPtr, i++) {
2200 if (i <= firstChildren) {
2201 if (i == firstChildren) {
2202 halfwayNodePtr = childPtr;
2206 childPtr->nextPtr = otherPtr->children.nodePtr;
2207 while (i <= firstChildren) {
2208 halfwayNodePtr = childPtr;
2209 childPtr = childPtr->nextPtr;
2215 * If the two siblings can simply be merged together, do it.
2218 if (totalChildren <= MAX_CHILDREN) {
2219 RecomputeNodeCounts(nodePtr);
2220 nodePtr->nextPtr = otherPtr->nextPtr;
2221 nodePtr->parentPtr->numChildren--;
2222 DeleteSummaries(otherPtr->summaryPtr);
2223 ckfree((char *) otherPtr);
2228 * The siblings can't be merged, so just divide their
2229 * children evenly between them.
2232 if (nodePtr->level == 0) {
2233 otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
2234 halfwayLinePtr->nextPtr = NULL;
2236 otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
2237 halfwayNodePtr->nextPtr = NULL;
2239 RecomputeNodeCounts(nodePtr);
2240 RecomputeNodeCounts(otherPtr);
2246 *----------------------------------------------------------------------
2248 * RecomputeNodeCounts --
2250 * This procedure is called to recompute all the counts in a node
2251 * (tags, child information, etc.) by scanning the information in
2252 * its descendants. This procedure is called during rebalancing
2253 * when a node's child structure has changed.
2259 * The tag counts for nodePtr are modified to reflect its current
2260 * child structure, as are its numChildren and numLines fields.
2261 * Also, all of the childrens' parentPtr fields are made to point
2264 *----------------------------------------------------------------------
2268 RecomputeNodeCounts(nodePtr)
2269 register Node *nodePtr; /* Node whose tag summary information
2270 * must be recomputed. */
2272 register Summary *summaryPtr, *summaryPtr2;
2273 register Node *childPtr;
2274 register CkTextLine *linePtr;
2275 register CkTextSegment *segPtr;
2279 * Zero out all the existing counts for the node, but don't delete
2280 * the existing Summary records (most of them will probably be reused).
2283 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
2284 summaryPtr = summaryPtr->nextPtr) {
2285 summaryPtr->toggleCount = 0;
2287 nodePtr->numChildren = 0;
2288 nodePtr->numLines = 0;
2291 * Scan through the children, adding the childrens' tag counts into
2292 * the node's tag counts and adding new Summary structures if
2296 if (nodePtr->level == 0) {
2297 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
2298 linePtr = linePtr->nextPtr) {
2299 nodePtr->numChildren++;
2300 nodePtr->numLines++;
2301 linePtr->parentPtr = nodePtr;
2302 for (segPtr = linePtr->segPtr; segPtr != NULL;
2303 segPtr = segPtr->nextPtr) {
2304 if (((segPtr->typePtr != &ckTextToggleOnType)
2305 && (segPtr->typePtr != &ckTextToggleOffType))
2306 || !(segPtr->body.toggle.inNodeCounts)) {
2309 tagPtr = segPtr->body.toggle.tagPtr;
2310 for (summaryPtr = nodePtr->summaryPtr; ;
2311 summaryPtr = summaryPtr->nextPtr) {
2312 if (summaryPtr == NULL) {
2313 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2314 summaryPtr->tagPtr = tagPtr;
2315 summaryPtr->toggleCount = 1;
2316 summaryPtr->nextPtr = nodePtr->summaryPtr;
2317 nodePtr->summaryPtr = summaryPtr;
2320 if (summaryPtr->tagPtr == tagPtr) {
2321 summaryPtr->toggleCount++;
2328 for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
2329 childPtr = childPtr->nextPtr) {
2330 nodePtr->numChildren++;
2331 nodePtr->numLines += childPtr->numLines;
2332 childPtr->parentPtr = nodePtr;
2333 for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
2334 summaryPtr2 = summaryPtr2->nextPtr) {
2335 for (summaryPtr = nodePtr->summaryPtr; ;
2336 summaryPtr = summaryPtr->nextPtr) {
2337 if (summaryPtr == NULL) {
2338 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2339 summaryPtr->tagPtr = summaryPtr2->tagPtr;
2340 summaryPtr->toggleCount = summaryPtr2->toggleCount;
2341 summaryPtr->nextPtr = nodePtr->summaryPtr;
2342 nodePtr->summaryPtr = summaryPtr;
2345 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
2346 summaryPtr->toggleCount += summaryPtr2->toggleCount;
2355 * Scan through the node's tag records again and delete any Summary
2356 * records that still have a zero count.
2360 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
2361 if (summaryPtr->toggleCount > 0) {
2362 summaryPtr2 = summaryPtr;
2363 summaryPtr = summaryPtr->nextPtr;
2366 if (summaryPtr2 != NULL) {
2367 summaryPtr2->nextPtr = summaryPtr->nextPtr;
2368 ckfree((char *) summaryPtr);
2369 summaryPtr = summaryPtr2->nextPtr;
2371 nodePtr->summaryPtr = summaryPtr->nextPtr;
2372 ckfree((char *) summaryPtr);
2373 summaryPtr = nodePtr->summaryPtr;
2379 *----------------------------------------------------------------------
2381 * CkBTreeNumLines --
2383 * This procedure returns a count of the number of lines of
2384 * text present in a given B-tree.
2387 * The return value is a count of the number of usable lines
2388 * in tree (i.e. it doesn't include the dummy line that is just
2389 * used to mark the end of the tree).
2394 *----------------------------------------------------------------------
2398 CkBTreeNumLines(tree)
2399 CkTextBTree tree; /* Information about tree. */
2401 BTree *treePtr = (BTree *) tree;
2402 return treePtr->rootPtr->numLines - 1;
2406 *--------------------------------------------------------------
2410 * This procedure implements splitting for character segments.
2413 * The return value is a pointer to a chain of two segments
2414 * that have the same characters as segPtr except split
2415 * among the two segments.
2418 * Storage for segPtr is freed.
2420 *--------------------------------------------------------------
2423 static CkTextSegment *
2424 CharSplitProc(segPtr, index)
2425 CkTextSegment *segPtr; /* Pointer to segment to split. */
2426 int index; /* Position within segment at which
2429 CkTextSegment *newPtr1, *newPtr2;
2431 newPtr1 = (CkTextSegment *) ckalloc(CSEG_SIZE(index));
2432 newPtr2 = (CkTextSegment *) ckalloc(
2433 CSEG_SIZE(segPtr->size - index));
2434 newPtr1->typePtr = &ckTextCharType;
2435 newPtr1->nextPtr = newPtr2;
2436 newPtr1->size = index;
2437 strncpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index);
2438 newPtr1->body.chars[index] = 0;
2439 newPtr2->typePtr = &ckTextCharType;
2440 newPtr2->nextPtr = segPtr->nextPtr;
2441 newPtr2->size = segPtr->size - index;
2442 strcpy(newPtr2->body.chars, segPtr->body.chars + index);
2443 ckfree((char*) segPtr);
2448 *--------------------------------------------------------------
2450 * CharCleanupProc --
2452 * This procedure merges adjacent character segments into
2453 * a single character segment, if possible.
2456 * The return value is a pointer to the first segment in
2457 * the (new) list of segments that used to start with segPtr.
2460 * Storage for the segments may be allocated and freed.
2462 *--------------------------------------------------------------
2466 static CkTextSegment *
2467 CharCleanupProc(segPtr, linePtr)
2468 CkTextSegment *segPtr; /* Pointer to first of two adjacent
2469 * segments to join. */
2470 CkTextLine *linePtr; /* Line containing segments (not
2473 CkTextSegment *segPtr2, *newPtr;
2475 segPtr2 = segPtr->nextPtr;
2476 if ((segPtr2 == NULL) || (segPtr2->typePtr != &ckTextCharType)) {
2479 newPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(
2480 segPtr->size + segPtr2->size));
2481 newPtr->typePtr = &ckTextCharType;
2482 newPtr->nextPtr = segPtr2->nextPtr;
2483 newPtr->size = segPtr->size + segPtr2->size;
2484 strcpy(newPtr->body.chars, segPtr->body.chars);
2485 strcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars);
2486 ckfree((char*) segPtr);
2487 ckfree((char*) segPtr2);
2492 *--------------------------------------------------------------
2496 * This procedure is invoked to delete a character segment.
2499 * Always returns 0 to indicate that the segment was deleted.
2502 * Storage for the segment is freed.
2504 *--------------------------------------------------------------
2509 CharDeleteProc(segPtr, linePtr, treeGone)
2510 CkTextSegment *segPtr; /* Segment to delete. */
2511 CkTextLine *linePtr; /* Line containing segment. */
2512 int treeGone; /* Non-zero means the entire tree is
2513 * being deleted, so everything must
2514 * get cleaned up. */
2516 ckfree((char*) segPtr);
2521 *--------------------------------------------------------------
2525 * This procedure is invoked to perform consistency checks
2526 * on character segments.
2532 * If the segment isn't inconsistent then the procedure
2535 *--------------------------------------------------------------
2540 CharCheckProc(segPtr, linePtr)
2541 CkTextSegment *segPtr; /* Segment to check. */
2542 CkTextLine *linePtr; /* Line containing segment. */
2545 * Make sure that the segment contains the number of
2546 * characters indicated by its header, and that the last
2547 * segment in a line ends in a newline. Also make sure
2548 * that there aren't ever two character segments adjacent
2549 * to each other: they should be merged together.
2552 if (segPtr->size <= 0) {
2553 panic("CharCheckProc: segment has size <= 0");
2555 if ((int) strlen(segPtr->body.chars) != segPtr->size) {
2556 panic("CharCheckProc: segment has wrong size");
2558 if (segPtr->nextPtr == NULL) {
2559 if (segPtr->body.chars[segPtr->size-1] != '\n') {
2560 panic("CharCheckProc: line doesn't end with newline");
2563 if (segPtr->nextPtr->typePtr == &ckTextCharType) {
2564 panic("CharCheckProc: adjacent character segments weren't merged");
2570 *--------------------------------------------------------------
2572 * ToggleDeleteProc --
2574 * This procedure is invoked to delete toggle segments.
2577 * Returns 1 to indicate that the segment may not be deleted,
2578 * unless the entire B-tree is going away.
2581 * If the tree is going away then the toggle's memory is
2582 * freed; otherwise the toggle counts in nodes above the
2583 * segment get updated.
2585 *--------------------------------------------------------------
2589 ToggleDeleteProc(segPtr, linePtr, treeGone)
2590 CkTextSegment *segPtr; /* Segment to check. */
2591 CkTextLine *linePtr; /* Line containing segment. */
2592 int treeGone; /* Non-zero means the entire tree is
2593 * being deleted, so everything must
2594 * get cleaned up. */
2597 ckfree((char *) segPtr);
2602 * This toggle is in the middle of a range of characters that's
2603 * being deleted. Refuse to die. We'll be moved to the end of
2604 * the deleted range and our cleanup procedure will be called
2605 * later. Decrement node toggle counts here, and set a flag
2606 * so we'll re-increment them in the cleanup procedure.
2609 if (segPtr->body.toggle.inNodeCounts) {
2610 ChangeNodeToggleCount(linePtr->parentPtr,
2611 segPtr->body.toggle.tagPtr, -1);
2612 segPtr->body.toggle.inNodeCounts = 0;
2618 *--------------------------------------------------------------
2620 * ToggleCleanupProc --
2622 * This procedure when a toggle is part of a line that's
2623 * been modified in some way. It's invoked after the
2624 * modifications are complete.
2627 * The return value is the head segment in a new list
2628 * that is to replace the tail of the line that used to
2629 * start at segPtr. This allows the procedure to delete
2633 * Toggle counts in the nodes above the new line will be
2634 * updated if they're not already. Toggles may be collapsed
2635 * if there are duplicate toggles at the same position.
2637 *--------------------------------------------------------------
2640 static CkTextSegment *
2641 ToggleCleanupProc(segPtr, linePtr)
2642 CkTextSegment *segPtr; /* Segment to check. */
2643 CkTextLine *linePtr; /* Line that now contains segment. */
2645 CkTextSegment *segPtr2, *prevPtr;
2649 * If this is a toggle-off segment, look ahead through the next
2650 * segments to see if there's a toggle-on segment for the same tag
2651 * before any segments with non-zero size. If so then the two
2652 * toggles cancel each other; remove them both.
2655 if (segPtr->typePtr == &ckTextToggleOffType) {
2656 for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr;
2657 (segPtr2 != NULL) && (segPtr2->size == 0);
2658 prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) {
2659 if (segPtr2->typePtr != &ckTextToggleOnType) {
2662 if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) {
2665 counts = segPtr->body.toggle.inNodeCounts
2666 + segPtr2->body.toggle.inNodeCounts;
2668 ChangeNodeToggleCount(linePtr->parentPtr,
2669 segPtr->body.toggle.tagPtr, -counts);
2671 prevPtr->nextPtr = segPtr2->nextPtr;
2672 ckfree((char *) segPtr2);
2673 segPtr2 = segPtr->nextPtr;
2674 ckfree((char *) segPtr);
2679 if (!segPtr->body.toggle.inNodeCounts) {
2680 ChangeNodeToggleCount(linePtr->parentPtr,
2681 segPtr->body.toggle.tagPtr, 1);
2682 segPtr->body.toggle.inNodeCounts = 1;
2688 *--------------------------------------------------------------
2690 * ToggleLineChangeProc --
2692 * This procedure is invoked when a toggle segment is about
2693 * to move from one line to another.
2699 * Toggle counts are decremented in the nodes above the line.
2701 *--------------------------------------------------------------
2705 ToggleLineChangeProc(segPtr, linePtr)
2706 CkTextSegment *segPtr; /* Segment to check. */
2707 CkTextLine *linePtr; /* Line that used to contain segment. */
2709 if (segPtr->body.toggle.inNodeCounts) {
2710 ChangeNodeToggleCount(linePtr->parentPtr,
2711 segPtr->body.toggle.tagPtr, -1);
2712 segPtr->body.toggle.inNodeCounts = 0;
2717 *--------------------------------------------------------------
2719 * ToggleCheckProc --
2721 * This procedure is invoked to perform consistency checks
2722 * on toggle segments.
2728 * If a consistency problem is found the procedure panics.
2730 *--------------------------------------------------------------
2734 ToggleCheckProc(segPtr, linePtr)
2735 CkTextSegment *segPtr; /* Segment to check. */
2736 CkTextLine *linePtr; /* Line containing segment. */
2738 register Summary *summaryPtr;
2740 if (segPtr->size != 0) {
2741 panic("ToggleCheckProc: segment had non-zero size");
2743 if (!segPtr->body.toggle.inNodeCounts) {
2744 panic("ToggleCheckProc: toggle counts not updated in nodes");
2746 for (summaryPtr = linePtr->parentPtr->summaryPtr; ;
2747 summaryPtr = summaryPtr->nextPtr) {
2748 if (summaryPtr == NULL) {
2749 panic("ToggleCheckProc: tag not present in node");
2751 if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) {
2758 *----------------------------------------------------------------------
2760 * CkBTreeCharsInLine --
2762 * This procedure returns a count of the number of characters
2766 * The return value is the character count for linePtr.
2771 *----------------------------------------------------------------------
2775 CkBTreeCharsInLine(linePtr)
2776 CkTextLine *linePtr; /* Line whose characters should be
2779 CkTextSegment *segPtr;
2783 for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
2784 if (segPtr->typePtr == &ckTextCharType) {
2785 count += Tcl_NumUtfChars(segPtr->body.chars, segPtr->size);
2787 count += segPtr->size;
2791 for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
2792 count += segPtr->size;