summaryrefslogtreecommitdiffstats
path: root/generic/tkTextBTree.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tkTextBTree.c')
-rw-r--r--generic/tkTextBTree.c3594
1 files changed, 3594 insertions, 0 deletions
diff --git a/generic/tkTextBTree.c b/generic/tkTextBTree.c
new file mode 100644
index 0000000..2fd7deb
--- /dev/null
+++ b/generic/tkTextBTree.c
@@ -0,0 +1,3594 @@
+/*
+ * tkTextBTree.c --
+ *
+ * This file contains code that manages the B-tree representation
+ * of text for Tk's text widget and implements character and
+ * toggle segment types.
+ *
+ * Copyright (c) 1992-1994 The Regents of the University of California.
+ * Copyright (c) 1994-1995 Sun Microsystems, Inc.
+ *
+ * See the file "license.terms" for information on usage and redistribution
+ * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
+ *
+ * SCCS: @(#) tkTextBTree.c 1.37 97/04/25 16:52:00
+ */
+
+#include "tkInt.h"
+#include "tkPort.h"
+#include "tkText.h"
+
+/*
+ * The data structure below keeps summary information about one tag as part
+ * of the tag information in a node.
+ */
+
+typedef struct Summary {
+ TkTextTag *tagPtr; /* Handle for tag. */
+ int toggleCount; /* Number of transitions into or
+ * out of this tag that occur in
+ * the subtree rooted at this node. */
+ struct Summary *nextPtr; /* Next in list of all tags for same
+ * node, or NULL if at end of list. */
+} Summary;
+
+/*
+ * The data structure below defines a node in the B-tree.
+ */
+
+typedef struct Node {
+ struct Node *parentPtr; /* Pointer to parent node, or NULL if
+ * this is the root. */
+ struct Node *nextPtr; /* Next in list of siblings with the
+ * same parent node, or NULL for end
+ * of list. */
+ Summary *summaryPtr; /* First in malloc-ed list of info
+ * about tags in this subtree (NULL if
+ * no tag info in the subtree). */
+ int level; /* Level of this node in the B-tree.
+ * 0 refers to the bottom of the tree
+ * (children are lines, not nodes). */
+ union { /* First in linked list of children. */
+ struct Node *nodePtr; /* Used if level > 0. */
+ TkTextLine *linePtr; /* Used if level == 0. */
+ } children;
+ int numChildren; /* Number of children of this node. */
+ int numLines; /* Total number of lines (leaves) in
+ * the subtree rooted here. */
+} Node;
+
+/*
+ * Upper and lower bounds on how many children a node may have:
+ * rebalance when either of these limits is exceeded. MAX_CHILDREN
+ * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
+ */
+
+#define MAX_CHILDREN 12
+#define MIN_CHILDREN 6
+
+/*
+ * The data structure below defines an entire B-tree.
+ */
+
+typedef struct BTree {
+ Node *rootPtr; /* Pointer to root of B-tree. */
+ TkText *textPtr; /* Used to find tagTable in consistency
+ * checking code */
+} BTree;
+
+/*
+ * The structure below is used to pass information between
+ * TkBTreeGetTags and IncCount:
+ */
+
+typedef struct TagInfo {
+ int numTags; /* Number of tags for which there
+ * is currently information in
+ * tags and counts. */
+ int arraySize; /* Number of entries allocated for
+ * tags and counts. */
+ TkTextTag **tagPtrs; /* Array of tags seen so far.
+ * Malloc-ed. */
+ int *counts; /* Toggle count (so far) for each
+ * entry in tags. Malloc-ed. */
+} TagInfo;
+
+/*
+ * Variable that indicates whether to enable consistency checks for
+ * debugging.
+ */
+
+int tkBTreeDebug = 0;
+
+/*
+ * Macros that determine how much space to allocate for new segments:
+ */
+
+#define CSEG_SIZE(chars) ((unsigned) (Tk_Offset(TkTextSegment, body) \
+ + 1 + (chars)))
+#define TSEG_SIZE ((unsigned) (Tk_Offset(TkTextSegment, body) \
+ + sizeof(TkTextToggle)))
+
+/*
+ * Forward declarations for procedures defined in this file:
+ */
+
+static void ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
+ TkTextTag *tagPtr, int delta));
+static void CharCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr));
+static int CharDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr, int treeGone));
+static TkTextSegment * CharCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr));
+static TkTextSegment * CharSplitProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ int index));
+static void CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
+static void CleanupLine _ANSI_ARGS_((TkTextLine *linePtr));
+static void DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
+static void DestroyNode _ANSI_ARGS_((Node *nodePtr));
+static TkTextSegment * FindTagEnd _ANSI_ARGS_((TkTextBTree tree,
+ TkTextTag *tagPtr, TkTextIndex *indexPtr));
+static void IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc,
+ TagInfo *tagInfoPtr));
+static void Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
+static void RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
+static TkTextSegment * SplitSeg _ANSI_ARGS_((TkTextIndex *indexPtr));
+static void ToggleCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr));
+static TkTextSegment * ToggleCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr));
+static int ToggleDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr, int treeGone));
+static void ToggleLineChangeProc _ANSI_ARGS_((TkTextSegment *segPtr,
+ TkTextLine *linePtr));
+static TkTextSegment * FindTagStart _ANSI_ARGS_((TkTextBTree tree,
+ TkTextTag *tagPtr, TkTextIndex *indexPtr));
+
+/*
+ * Type record for character segments:
+ */
+
+Tk_SegType tkTextCharType = {
+ "character", /* name */
+ 0, /* leftGravity */
+ CharSplitProc, /* splitProc */
+ CharDeleteProc, /* deleteProc */
+ CharCleanupProc, /* cleanupProc */
+ (Tk_SegLineChangeProc *) NULL, /* lineChangeProc */
+ TkTextCharLayoutProc, /* layoutProc */
+ CharCheckProc /* checkProc */
+};
+
+/*
+ * Type record for segments marking the beginning of a tagged
+ * range:
+ */
+
+Tk_SegType tkTextToggleOnType = {
+ "toggleOn", /* name */
+ 0, /* leftGravity */
+ (Tk_SegSplitProc *) NULL, /* splitProc */
+ ToggleDeleteProc, /* deleteProc */
+ ToggleCleanupProc, /* cleanupProc */
+ ToggleLineChangeProc, /* lineChangeProc */
+ (Tk_SegLayoutProc *) NULL, /* layoutProc */
+ ToggleCheckProc /* checkProc */
+};
+
+/*
+ * Type record for segments marking the end of a tagged
+ * range:
+ */
+
+Tk_SegType tkTextToggleOffType = {
+ "toggleOff", /* name */
+ 1, /* leftGravity */
+ (Tk_SegSplitProc *) NULL, /* splitProc */
+ ToggleDeleteProc, /* deleteProc */
+ ToggleCleanupProc, /* cleanupProc */
+ ToggleLineChangeProc, /* lineChangeProc */
+ (Tk_SegLayoutProc *) NULL, /* layoutProc */
+ ToggleCheckProc /* checkProc */
+};
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeCreate --
+ *
+ * This procedure is called to create a new text B-tree.
+ *
+ * Results:
+ * The return value is a pointer to a new B-tree containing
+ * one line with nothing but a newline character.
+ *
+ * Side effects:
+ * Memory is allocated and initialized.
+ *
+ *----------------------------------------------------------------------
+ */
+
+TkTextBTree
+TkBTreeCreate(textPtr)
+ TkText *textPtr;
+{
+ register BTree *treePtr;
+ register Node *rootPtr;
+ register TkTextLine *linePtr, *linePtr2;
+ register TkTextSegment *segPtr;
+
+ /*
+ * The tree will initially have two empty lines. The second line
+ * isn't actually part of the tree's contents, but its presence
+ * makes several operations easier. The tree will have one node,
+ * which is also the root of the tree.
+ */
+
+ rootPtr = (Node *) ckalloc(sizeof(Node));
+ linePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
+ linePtr2 = (TkTextLine *) ckalloc(sizeof(TkTextLine));
+ rootPtr->parentPtr = NULL;
+ rootPtr->nextPtr = NULL;
+ rootPtr->summaryPtr = NULL;
+ rootPtr->level = 0;
+ rootPtr->children.linePtr = linePtr;
+ rootPtr->numChildren = 2;
+ rootPtr->numLines = 2;
+
+ linePtr->parentPtr = rootPtr;
+ linePtr->nextPtr = linePtr2;
+ segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
+ linePtr->segPtr = segPtr;
+ segPtr->typePtr = &tkTextCharType;
+ segPtr->nextPtr = NULL;
+ segPtr->size = 1;
+ segPtr->body.chars[0] = '\n';
+ segPtr->body.chars[1] = 0;
+
+ linePtr2->parentPtr = rootPtr;
+ linePtr2->nextPtr = NULL;
+ segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
+ linePtr2->segPtr = segPtr;
+ segPtr->typePtr = &tkTextCharType;
+ segPtr->nextPtr = NULL;
+ segPtr->size = 1;
+ segPtr->body.chars[0] = '\n';
+ segPtr->body.chars[1] = 0;
+
+ treePtr = (BTree *) ckalloc(sizeof(BTree));
+ treePtr->rootPtr = rootPtr;
+ treePtr->textPtr = textPtr;
+
+ return (TkTextBTree) treePtr;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeDestroy --
+ *
+ * Delete a B-tree, recycling all of the storage it contains.
+ *
+ * Results:
+ * The tree given by treePtr is deleted. TreePtr should never
+ * again be used.
+ *
+ * Side effects:
+ * Memory is freed.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeDestroy(tree)
+ TkTextBTree tree; /* Pointer to tree to delete. */
+{
+ BTree *treePtr = (BTree *) tree;
+
+ DestroyNode(treePtr->rootPtr);
+ ckfree((char *) treePtr);
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * DestroyNode --
+ *
+ * This is a recursive utility procedure used during the deletion
+ * of a B-tree.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * All the storage for nodePtr and its descendants is freed.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+DestroyNode(nodePtr)
+ register Node *nodePtr;
+{
+ if (nodePtr->level == 0) {
+ TkTextLine *linePtr;
+ TkTextSegment *segPtr;
+
+ while (nodePtr->children.linePtr != NULL) {
+ linePtr = nodePtr->children.linePtr;
+ nodePtr->children.linePtr = linePtr->nextPtr;
+ while (linePtr->segPtr != NULL) {
+ segPtr = linePtr->segPtr;
+ linePtr->segPtr = segPtr->nextPtr;
+ (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
+ }
+ ckfree((char *) linePtr);
+ }
+ } else {
+ register Node *childPtr;
+
+ while (nodePtr->children.nodePtr != NULL) {
+ childPtr = nodePtr->children.nodePtr;
+ nodePtr->children.nodePtr = childPtr->nextPtr;
+ DestroyNode(childPtr);
+ }
+ }
+ DeleteSummaries(nodePtr->summaryPtr);
+ ckfree((char *) nodePtr);
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * DeleteSummaries --
+ *
+ * Free up all of the memory in a list of tag summaries associated
+ * with a node.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * Storage is released.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+DeleteSummaries(summaryPtr)
+ register Summary *summaryPtr; /* First in list of node's tag
+ * summaries. */
+{
+ register Summary *nextPtr;
+ while (summaryPtr != NULL) {
+ nextPtr = summaryPtr->nextPtr;
+ ckfree((char *) summaryPtr);
+ summaryPtr = nextPtr;
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeInsertChars --
+ *
+ * Insert characters at a given position in a B-tree.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * Characters are added to the B-tree at the given position.
+ * If the string contains newlines, new lines will be added,
+ * which could cause the structure of the B-tree to change.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeInsertChars(indexPtr, string)
+ register TkTextIndex *indexPtr; /* Indicates where to insert text.
+ * When the procedure returns, this
+ * index is no longer valid because
+ * of changes to the segment
+ * structure. */
+ char *string; /* Pointer to bytes to insert (may
+ * contain newlines, must be null-
+ * terminated). */
+{
+ register Node *nodePtr;
+ register TkTextSegment *prevPtr; /* The segment just before the first
+ * new segment (NULL means new segment
+ * is at beginning of line). */
+ TkTextSegment *curPtr; /* Current segment; new characters
+ * are inserted just after this one.
+ * NULL means insert at beginning of
+ * line. */
+ TkTextLine *linePtr; /* Current line (new segments are
+ * added to this line). */
+ register TkTextSegment *segPtr;
+ TkTextLine *newLinePtr;
+ int chunkSize; /* # characters in current chunk. */
+ register char *eol; /* Pointer to character just after last
+ * one in current chunk. */
+ int changeToLineCount; /* Counts change to total number of
+ * lines in file. */
+
+ prevPtr = SplitSeg(indexPtr);
+ linePtr = indexPtr->linePtr;
+ curPtr = prevPtr;
+
+ /*
+ * Chop the string up into lines and create a new segment for
+ * each line, plus a new line for the leftovers from the
+ * previous line.
+ */
+
+ changeToLineCount = 0;
+ while (*string != 0) {
+ for (eol = string; *eol != 0; eol++) {
+ if (*eol == '\n') {
+ eol++;
+ break;
+ }
+ }
+ chunkSize = eol-string;
+ segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
+ segPtr->typePtr = &tkTextCharType;
+ if (curPtr == NULL) {
+ segPtr->nextPtr = linePtr->segPtr;
+ linePtr->segPtr = segPtr;
+ } else {
+ segPtr->nextPtr = curPtr->nextPtr;
+ curPtr->nextPtr = segPtr;
+ }
+ segPtr->size = chunkSize;
+ strncpy(segPtr->body.chars, string, (size_t) chunkSize);
+ segPtr->body.chars[chunkSize] = 0;
+
+ if (eol[-1] != '\n') {
+ break;
+ }
+
+ /*
+ * The chunk ended with a newline, so create a new TkTextLine
+ * and move the remainder of the old line to it.
+ */
+
+ newLinePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
+ newLinePtr->parentPtr = linePtr->parentPtr;
+ newLinePtr->nextPtr = linePtr->nextPtr;
+ linePtr->nextPtr = newLinePtr;
+ newLinePtr->segPtr = segPtr->nextPtr;
+ segPtr->nextPtr = NULL;
+ linePtr = newLinePtr;
+ curPtr = NULL;
+ changeToLineCount++;
+
+ string = eol;
+ }
+
+ /*
+ * Cleanup the starting line for the insertion, plus the ending
+ * line if it's different.
+ */
+
+ CleanupLine(indexPtr->linePtr);
+ if (linePtr != indexPtr->linePtr) {
+ CleanupLine(linePtr);
+ }
+
+ /*
+ * Increment the line counts in all the parent nodes of the insertion
+ * point, then rebalance the tree if necessary.
+ */
+
+ for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
+ nodePtr = nodePtr->parentPtr) {
+ nodePtr->numLines += changeToLineCount;
+ }
+ nodePtr = linePtr->parentPtr;
+ nodePtr->numChildren += changeToLineCount;
+ if (nodePtr->numChildren > MAX_CHILDREN) {
+ Rebalance((BTree *) indexPtr->tree, nodePtr);
+ }
+
+ if (tkBTreeDebug) {
+ TkBTreeCheck(indexPtr->tree);
+ }
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * SplitSeg --
+ *
+ * This procedure is called before adding or deleting
+ * segments. It does three things: (a) it finds the segment
+ * containing indexPtr; (b) if there are several such
+ * segments (because some segments have zero length) then
+ * it picks the first segment that does not have left
+ * gravity; (c) if the index refers to the middle of
+ * a segment then it splits the segment so that the
+ * index now refers to the beginning of a segment.
+ *
+ * Results:
+ * The return value is a pointer to the segment just
+ * before the segment corresponding to indexPtr (as
+ * described above). If the segment corresponding to
+ * indexPtr is the first in its line then the return
+ * value is NULL.
+ *
+ * Side effects:
+ * The segment referred to by indexPtr is split unless
+ * indexPtr refers to its first character.
+ *
+ *--------------------------------------------------------------
+ */
+
+static TkTextSegment *
+SplitSeg(indexPtr)
+ TkTextIndex *indexPtr; /* Index identifying position
+ * at which to split a segment. */
+{
+ TkTextSegment *prevPtr, *segPtr;
+ int count;
+
+ for (count = indexPtr->charIndex, prevPtr = NULL,
+ segPtr = indexPtr->linePtr->segPtr; segPtr != NULL;
+ count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) {
+ if (segPtr->size > count) {
+ if (count == 0) {
+ return prevPtr;
+ }
+ segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
+ if (prevPtr == NULL) {
+ indexPtr->linePtr->segPtr = segPtr;
+ } else {
+ prevPtr->nextPtr = segPtr;
+ }
+ return segPtr;
+ } else if ((segPtr->size == 0) && (count == 0)
+ && !segPtr->typePtr->leftGravity) {
+ return prevPtr;
+ }
+ }
+ panic("SplitSeg reached end of line!");
+ return NULL;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * CleanupLine --
+ *
+ * This procedure is called after modifications have been
+ * made to a line. It scans over all of the segments in
+ * the line, giving each a chance to clean itself up, e.g.
+ * by merging with the following segments, updating internal
+ * information, etc.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * Depends on what the segment-specific cleanup procedures do.
+ *
+ *--------------------------------------------------------------
+ */
+
+static void
+CleanupLine(linePtr)
+ TkTextLine *linePtr; /* Line to be cleaned up. */
+{
+ TkTextSegment *segPtr, **prevPtrPtr;
+ int anyChanges;
+
+ /*
+ * Make a pass over all of the segments in the line, giving each
+ * a chance to clean itself up. This could potentially change
+ * the structure of the line, e.g. by merging two segments
+ * together or having two segments cancel themselves; if so,
+ * then repeat the whole process again, since the first structure
+ * change might make other structure changes possible. Repeat
+ * until eventually there are no changes.
+ */
+
+ while (1) {
+ anyChanges = 0;
+ for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
+ segPtr != NULL;
+ prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
+ if (segPtr->typePtr->cleanupProc != NULL) {
+ *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
+ if (segPtr != *prevPtrPtr) {
+ anyChanges = 1;
+ }
+ }
+ }
+ if (!anyChanges) {
+ break;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeDeleteChars --
+ *
+ * Delete a range of characters from a B-tree. The caller
+ * must make sure that the final newline of the B-tree is
+ * never deleted.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * Information is deleted from the B-tree. This can cause the
+ * internal structure of the B-tree to change. Note: because
+ * of changes to the B-tree structure, the indices pointed
+ * to by index1Ptr and index2Ptr should not be used after this
+ * procedure returns.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeDeleteChars(index1Ptr, index2Ptr)
+ register TkTextIndex *index1Ptr; /* Indicates first character that is
+ * to be deleted. */
+ register TkTextIndex *index2Ptr; /* Indicates character just after the
+ * last one that is to be deleted. */
+{
+ TkTextSegment *prevPtr; /* The segment just before the start
+ * of the deletion range. */
+ TkTextSegment *lastPtr; /* The segment just after the end
+ * of the deletion range. */
+ TkTextSegment *segPtr, *nextPtr;
+ TkTextLine *curLinePtr;
+ Node *curNodePtr, *nodePtr;
+
+ /*
+ * Tricky point: split at index2Ptr first; otherwise the split
+ * at index2Ptr may invalidate segPtr and/or prevPtr.
+ */
+
+ lastPtr = SplitSeg(index2Ptr);
+ if (lastPtr != NULL) {
+ lastPtr = lastPtr->nextPtr;
+ } else {
+ lastPtr = index2Ptr->linePtr->segPtr;
+ }
+ prevPtr = SplitSeg(index1Ptr);
+ if (prevPtr != NULL) {
+ segPtr = prevPtr->nextPtr;
+ prevPtr->nextPtr = lastPtr;
+ } else {
+ segPtr = index1Ptr->linePtr->segPtr;
+ index1Ptr->linePtr->segPtr = lastPtr;
+ }
+
+ /*
+ * Delete all of the segments between prevPtr and lastPtr.
+ */
+
+ curLinePtr = index1Ptr->linePtr;
+ curNodePtr = curLinePtr->parentPtr;
+ while (segPtr != lastPtr) {
+ if (segPtr == NULL) {
+ TkTextLine *nextLinePtr;
+
+ /*
+ * We just ran off the end of a line. First find the
+ * next line, then go back to the old line and delete it
+ * (unless it's the starting line for the range).
+ */
+
+ nextLinePtr = TkBTreeNextLine(curLinePtr);
+ if (curLinePtr != index1Ptr->linePtr) {
+ if (curNodePtr == index1Ptr->linePtr->parentPtr) {
+ index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
+ } else {
+ curNodePtr->children.linePtr = curLinePtr->nextPtr;
+ }
+ for (nodePtr = curNodePtr; nodePtr != NULL;
+ nodePtr = nodePtr->parentPtr) {
+ nodePtr->numLines--;
+ }
+ curNodePtr->numChildren--;
+ ckfree((char *) curLinePtr);
+ }
+ curLinePtr = nextLinePtr;
+ segPtr = curLinePtr->segPtr;
+
+ /*
+ * If the node is empty then delete it and its parents,
+ * recursively upwards until a non-empty node is found.
+ */
+
+ while (curNodePtr->numChildren == 0) {
+ Node *parentPtr;
+
+ parentPtr = curNodePtr->parentPtr;
+ if (parentPtr->children.nodePtr == curNodePtr) {
+ parentPtr->children.nodePtr = curNodePtr->nextPtr;
+ } else {
+ Node *prevNodePtr = parentPtr->children.nodePtr;
+ while (prevNodePtr->nextPtr != curNodePtr) {
+ prevNodePtr = prevNodePtr->nextPtr;
+ }
+ prevNodePtr->nextPtr = curNodePtr->nextPtr;
+ }
+ parentPtr->numChildren--;
+ ckfree((char *) curNodePtr);
+ curNodePtr = parentPtr;
+ }
+ curNodePtr = curLinePtr->parentPtr;
+ continue;
+ }
+
+ nextPtr = segPtr->nextPtr;
+ if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
+ /*
+ * This segment refuses to die. Move it to prevPtr and
+ * advance prevPtr if the segment has left gravity.
+ */
+
+ if (prevPtr == NULL) {
+ segPtr->nextPtr = index1Ptr->linePtr->segPtr;
+ index1Ptr->linePtr->segPtr = segPtr;
+ } else {
+ segPtr->nextPtr = prevPtr->nextPtr;
+ prevPtr->nextPtr = segPtr;
+ }
+ if (segPtr->typePtr->leftGravity) {
+ prevPtr = segPtr;
+ }
+ }
+ segPtr = nextPtr;
+ }
+
+ /*
+ * If the beginning and end of the deletion range are in different
+ * lines, join the two lines together and discard the ending line.
+ */
+
+ if (index1Ptr->linePtr != index2Ptr->linePtr) {
+ TkTextLine *prevLinePtr;
+
+ for (segPtr = lastPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if (segPtr->typePtr->lineChangeProc != NULL) {
+ (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
+ }
+ }
+ curNodePtr = index2Ptr->linePtr->parentPtr;
+ for (nodePtr = curNodePtr; nodePtr != NULL;
+ nodePtr = nodePtr->parentPtr) {
+ nodePtr->numLines--;
+ }
+ curNodePtr->numChildren--;
+ prevLinePtr = curNodePtr->children.linePtr;
+ if (prevLinePtr == index2Ptr->linePtr) {
+ curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
+ } else {
+ while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
+ prevLinePtr = prevLinePtr->nextPtr;
+ }
+ prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
+ }
+ ckfree((char *) index2Ptr->linePtr);
+ Rebalance((BTree *) index2Ptr->tree, curNodePtr);
+ }
+
+ /*
+ * Cleanup the segments in the new line.
+ */
+
+ CleanupLine(index1Ptr->linePtr);
+
+ /*
+ * Lastly, rebalance the first node of the range.
+ */
+
+ Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
+ if (tkBTreeDebug) {
+ TkBTreeCheck(index1Ptr->tree);
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeFindLine --
+ *
+ * Find a particular line in a B-tree based on its line number.
+ *
+ * Results:
+ * The return value is a pointer to the line structure for the
+ * line whose index is "line", or NULL if no such line exists.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+TkTextLine *
+TkBTreeFindLine(tree, line)
+ TkTextBTree tree; /* B-tree in which to find line. */
+ int line; /* Index of desired line. */
+{
+ BTree *treePtr = (BTree *) tree;
+ register Node *nodePtr;
+ register TkTextLine *linePtr;
+ int linesLeft;
+
+ nodePtr = treePtr->rootPtr;
+ linesLeft = line;
+ if ((line < 0) || (line >= nodePtr->numLines)) {
+ return NULL;
+ }
+
+ /*
+ * Work down through levels of the tree until a node is found at
+ * level 0.
+ */
+
+ while (nodePtr->level != 0) {
+ for (nodePtr = nodePtr->children.nodePtr;
+ nodePtr->numLines <= linesLeft;
+ nodePtr = nodePtr->nextPtr) {
+ if (nodePtr == NULL) {
+ panic("TkBTreeFindLine ran out of nodes");
+ }
+ linesLeft -= nodePtr->numLines;
+ }
+ }
+
+ /*
+ * Work through the lines attached to the level-0 node.
+ */
+
+ for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
+ linePtr = linePtr->nextPtr) {
+ if (linePtr == NULL) {
+ panic("TkBTreeFindLine ran out of lines");
+ }
+ linesLeft -= 1;
+ }
+ return linePtr;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeNextLine --
+ *
+ * Given an existing line in a B-tree, this procedure locates the
+ * next line in the B-tree. This procedure is used for scanning
+ * through the B-tree.
+ *
+ * Results:
+ * The return value is a pointer to the line that immediately
+ * follows linePtr, or NULL if there is no such line.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+TkTextLine *
+TkBTreeNextLine(linePtr)
+ register TkTextLine *linePtr; /* Pointer to existing line in
+ * B-tree. */
+{
+ register Node *nodePtr;
+
+ if (linePtr->nextPtr != NULL) {
+ return linePtr->nextPtr;
+ }
+
+ /*
+ * This was the last line associated with the particular parent node.
+ * Search up the tree for the next node, then search down from that
+ * node to find the first line.
+ */
+
+ for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
+ if (nodePtr->nextPtr != NULL) {
+ nodePtr = nodePtr->nextPtr;
+ break;
+ }
+ if (nodePtr->parentPtr == NULL) {
+ return (TkTextLine *) NULL;
+ }
+ }
+ while (nodePtr->level > 0) {
+ nodePtr = nodePtr->children.nodePtr;
+ }
+ return nodePtr->children.linePtr;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreePreviousLine --
+ *
+ * Given an existing line in a B-tree, this procedure locates the
+ * previous line in the B-tree. This procedure is used for scanning
+ * through the B-tree in the reverse direction.
+ *
+ * Results:
+ * The return value is a pointer to the line that immediately
+ * preceeds linePtr, or NULL if there is no such line.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+TkTextLine *
+TkBTreePreviousLine(linePtr)
+ register TkTextLine *linePtr; /* Pointer to existing line in
+ * B-tree. */
+{
+ register Node *nodePtr;
+ register Node *node2Ptr;
+ register TkTextLine *prevPtr;
+
+ /*
+ * Find the line under this node just before the starting line.
+ */
+ prevPtr = linePtr->parentPtr->children.linePtr; /* First line at leaf */
+ while (prevPtr != linePtr) {
+ if (prevPtr->nextPtr == linePtr) {
+ return prevPtr;
+ }
+ prevPtr = prevPtr->nextPtr;
+ if (prevPtr == (TkTextLine *) NULL) {
+ panic("TkBTreePreviousLine ran out of lines");
+ }
+ }
+
+ /*
+ * This was the first line associated with the particular parent node.
+ * Search up the tree for the previous node, then search down from that
+ * node to find its last line.
+ */
+ for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
+ if (nodePtr == (Node *) NULL || nodePtr->parentPtr == (Node *) NULL) {
+ return (TkTextLine *) NULL;
+ }
+ if (nodePtr != nodePtr->parentPtr->children.nodePtr) {
+ break;
+ }
+ }
+ for (node2Ptr = nodePtr->parentPtr->children.nodePtr; ;
+ node2Ptr = node2Ptr->children.nodePtr) {
+ while (node2Ptr->nextPtr != nodePtr) {
+ node2Ptr = node2Ptr->nextPtr;
+ }
+ if (node2Ptr->level == 0) {
+ break;
+ }
+ nodePtr = (Node *)NULL;
+ }
+ for (prevPtr = node2Ptr->children.linePtr ; ; prevPtr = prevPtr->nextPtr) {
+ if (prevPtr->nextPtr == (TkTextLine *) NULL) {
+ return prevPtr;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeLineIndex --
+ *
+ * Given a pointer to a line in a B-tree, return the numerical
+ * index of that line.
+ *
+ * Results:
+ * The result is the index of linePtr within the tree, where 0
+ * corresponds to the first line in the tree.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreeLineIndex(linePtr)
+ TkTextLine *linePtr; /* Pointer to existing line in
+ * B-tree. */
+{
+ register TkTextLine *linePtr2;
+ register Node *nodePtr, *parentPtr, *nodePtr2;
+ int index;
+
+ /*
+ * First count how many lines precede this one in its level-0
+ * node.
+ */
+
+ nodePtr = linePtr->parentPtr;
+ index = 0;
+ for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
+ linePtr2 = linePtr2->nextPtr) {
+ if (linePtr2 == NULL) {
+ panic("TkBTreeLineIndex couldn't find line");
+ }
+ index += 1;
+ }
+
+ /*
+ * Now work up through the levels of the tree one at a time,
+ * counting how many lines are in nodes preceding the current
+ * node.
+ */
+
+ for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
+ nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
+ for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
+ nodePtr2 = nodePtr2->nextPtr) {
+ if (nodePtr2 == NULL) {
+ panic("TkBTreeLineIndex couldn't find node");
+ }
+ index += nodePtr2->numLines;
+ }
+ }
+ return index;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeLinkSegment --
+ *
+ * This procedure adds a new segment to a B-tree at a given
+ * location.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * SegPtr will be linked into its tree.
+ *
+ *----------------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+void
+TkBTreeLinkSegment(segPtr, indexPtr)
+ TkTextSegment *segPtr; /* Pointer to new segment to be added to
+ * B-tree. Should be completely initialized
+ * by caller except for nextPtr field. */
+ TkTextIndex *indexPtr; /* Where to add segment: it gets linked
+ * in just before the segment indicated
+ * here. */
+{
+ register TkTextSegment *prevPtr;
+
+ prevPtr = SplitSeg(indexPtr);
+ if (prevPtr == NULL) {
+ segPtr->nextPtr = indexPtr->linePtr->segPtr;
+ indexPtr->linePtr->segPtr = segPtr;
+ } else {
+ segPtr->nextPtr = prevPtr->nextPtr;
+ prevPtr->nextPtr = segPtr;
+ }
+ CleanupLine(indexPtr->linePtr);
+ if (tkBTreeDebug) {
+ TkBTreeCheck(indexPtr->tree);
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeUnlinkSegment --
+ *
+ * This procedure unlinks a segment from its line in a B-tree.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * SegPtr will be unlinked from linePtr. The segment itself
+ * isn't modified by this procedure.
+ *
+ *----------------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+void
+TkBTreeUnlinkSegment(tree, segPtr, linePtr)
+ TkTextBTree tree; /* Tree containing segment. */
+ TkTextSegment *segPtr; /* Segment to be unlinked. */
+ TkTextLine *linePtr; /* Line that currently contains
+ * segment. */
+{
+ register TkTextSegment *prevPtr;
+
+ if (linePtr->segPtr == segPtr) {
+ linePtr->segPtr = segPtr->nextPtr;
+ } else {
+ for (prevPtr = linePtr->segPtr; prevPtr->nextPtr != segPtr;
+ prevPtr = prevPtr->nextPtr) {
+ /* Empty loop body. */
+ }
+ prevPtr->nextPtr = segPtr->nextPtr;
+ }
+ CleanupLine(linePtr);
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeTag --
+ *
+ * Turn a given tag on or off for a given range of characters in
+ * a B-tree of text.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The given tag is added to the given range of characters
+ * in the tree or removed from all those characters, depending
+ * on the "add" argument. The structure of the btree is modified
+ * enough that index1Ptr and index2Ptr are no longer valid after
+ * this procedure returns, and the indexes may be modified by
+ * this procedure.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeTag(index1Ptr, index2Ptr, tagPtr, add)
+ register TkTextIndex *index1Ptr; /* Indicates first character in
+ * range. */
+ register TkTextIndex *index2Ptr; /* Indicates character just after the
+ * last one in range. */
+ TkTextTag *tagPtr; /* Tag to add or remove. */
+ int add; /* One means add tag to the given
+ * range of characters; zero means
+ * remove the tag from the range. */
+{
+ TkTextSegment *segPtr, *prevPtr;
+ TkTextSearch search;
+ TkTextLine *cleanupLinePtr;
+ int oldState;
+ int changed;
+
+ /*
+ * See whether the tag is present at the start of the range. If
+ * the state doesn't already match what we want then add a toggle
+ * there.
+ */
+
+ oldState = TkBTreeCharTagged(index1Ptr, tagPtr);
+ if ((add != 0) ^ oldState) {
+ segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
+ segPtr->typePtr = (add) ? &tkTextToggleOnType : &tkTextToggleOffType;
+ prevPtr = SplitSeg(index1Ptr);
+ if (prevPtr == NULL) {
+ segPtr->nextPtr = index1Ptr->linePtr->segPtr;
+ index1Ptr->linePtr->segPtr = segPtr;
+ } else {
+ segPtr->nextPtr = prevPtr->nextPtr;
+ prevPtr->nextPtr = segPtr;
+ }
+ segPtr->size = 0;
+ segPtr->body.toggle.tagPtr = tagPtr;
+ segPtr->body.toggle.inNodeCounts = 0;
+ }
+
+ /*
+ * Scan the range of characters and delete any internal tag
+ * transitions. Keep track of what the old state was at the end
+ * of the range, and add a toggle there if it's needed.
+ */
+
+ TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
+ cleanupLinePtr = index1Ptr->linePtr;
+ while (TkBTreeNextTag(&search)) {
+ oldState ^= 1;
+ segPtr = search.segPtr;
+ prevPtr = search.curIndex.linePtr->segPtr;
+ if (prevPtr == segPtr) {
+ search.curIndex.linePtr->segPtr = segPtr->nextPtr;
+ } else {
+ while (prevPtr->nextPtr != segPtr) {
+ prevPtr = prevPtr->nextPtr;
+ }
+ prevPtr->nextPtr = segPtr->nextPtr;
+ }
+ if (segPtr->body.toggle.inNodeCounts) {
+ ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr,
+ segPtr->body.toggle.tagPtr, -1);
+ segPtr->body.toggle.inNodeCounts = 0;
+ changed = 1;
+ } else {
+ changed = 0;
+ }
+ ckfree((char *) segPtr);
+
+ /*
+ * The code below is a bit tricky. After deleting a toggle
+ * we eventually have to call CleanupLine, in order to allow
+ * character segments to be merged together. To do this, we
+ * remember in cleanupLinePtr a line that needs to be
+ * cleaned up, but we don't clean it up until we've moved
+ * on to a different line. That way the cleanup process
+ * won't goof up segPtr.
+ */
+
+ if (cleanupLinePtr != search.curIndex.linePtr) {
+ CleanupLine(cleanupLinePtr);
+ cleanupLinePtr = search.curIndex.linePtr;
+ }
+ /*
+ * Quick hack. ChangeNodeToggleCount may move the tag's root
+ * location around and leave the search in the void. This resets
+ * the search.
+ */
+ if (changed) {
+ TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
+ }
+ }
+ if ((add != 0) ^ oldState) {
+ segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
+ segPtr->typePtr = (add) ? &tkTextToggleOffType : &tkTextToggleOnType;
+ prevPtr = SplitSeg(index2Ptr);
+ if (prevPtr == NULL) {
+ segPtr->nextPtr = index2Ptr->linePtr->segPtr;
+ index2Ptr->linePtr->segPtr = segPtr;
+ } else {
+ segPtr->nextPtr = prevPtr->nextPtr;
+ prevPtr->nextPtr = segPtr;
+ }
+ segPtr->size = 0;
+ segPtr->body.toggle.tagPtr = tagPtr;
+ segPtr->body.toggle.inNodeCounts = 0;
+ }
+
+ /*
+ * Cleanup cleanupLinePtr and the last line of the range, if
+ * these are different.
+ */
+
+ CleanupLine(cleanupLinePtr);
+ if (cleanupLinePtr != index2Ptr->linePtr) {
+ CleanupLine(index2Ptr->linePtr);
+ }
+
+ if (tkBTreeDebug) {
+ TkBTreeCheck(index1Ptr->tree);
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * ChangeNodeToggleCount --
+ *
+ * This procedure increments or decrements the toggle count for
+ * a particular tag in a particular node and all its ancestors
+ * up to the per-tag root node.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The toggle count for tag is adjusted up or down by "delta" in
+ * nodePtr. This routine maintains the tagRootPtr that identifies
+ * the root node for the tag, moving it up or down the tree as needed.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+ChangeNodeToggleCount(nodePtr, tagPtr, delta)
+ register Node *nodePtr; /* Node whose toggle count for a tag
+ * must be changed. */
+ TkTextTag *tagPtr; /* Information about tag. */
+ int delta; /* Amount to add to current toggle
+ * count for tag (may be negative). */
+{
+ register Summary *summaryPtr, *prevPtr;
+ register Node *node2Ptr;
+ int rootLevel; /* Level of original tag root */
+
+ tagPtr->toggleCount += delta;
+ if (tagPtr->tagRootPtr == (Node *) NULL) {
+ tagPtr->tagRootPtr = nodePtr;
+ return;
+ }
+
+ /*
+ * Note the level of the existing root for the tag so we can detect
+ * if it needs to be moved because of the toggle count change.
+ */
+
+ rootLevel = tagPtr->tagRootPtr->level;
+
+ /*
+ * Iterate over the node and its ancestors up to the tag root, adjusting
+ * summary counts at each node and moving the tag's root upwards if
+ * necessary.
+ */
+
+ for ( ; nodePtr != tagPtr->tagRootPtr; nodePtr = nodePtr->parentPtr) {
+ /*
+ * See if there's already an entry for this tag for this node. If so,
+ * perhaps all we have to do is adjust its count.
+ */
+
+ for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
+ summaryPtr != NULL;
+ prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ break;
+ }
+ }
+ if (summaryPtr != NULL) {
+ summaryPtr->toggleCount += delta;
+ if (summaryPtr->toggleCount > 0 &&
+ summaryPtr->toggleCount < tagPtr->toggleCount) {
+ continue;
+ }
+ if (summaryPtr->toggleCount != 0) {
+ /*
+ * Should never find a node with max toggle count at this
+ * point (there shouldn't have been a summary entry in the
+ * first place).
+ */
+
+ panic("ChangeNodeToggleCount: bad toggle count (%d) max (%d)",
+ summaryPtr->toggleCount, tagPtr->toggleCount);
+ }
+
+ /*
+ * Zero toggle count; must remove this tag from the list.
+ */
+
+ if (prevPtr == NULL) {
+ nodePtr->summaryPtr = summaryPtr->nextPtr;
+ } else {
+ prevPtr->nextPtr = summaryPtr->nextPtr;
+ }
+ ckfree((char *) summaryPtr);
+ } else {
+ /*
+ * This tag isn't currently in the summary information list.
+ */
+
+ if (rootLevel == nodePtr->level) {
+
+ /*
+ * The old tag root is at the same level in the tree as this
+ * node, but it isn't at this node. Move the tag root up
+ * a level, in the hopes that it will now cover this node
+ * as well as the old root (if not, we'll move it up again
+ * the next time through the loop). To push it up one level
+ * we copy the original toggle count into the summary
+ * information at the old root and change the root to its
+ * parent node.
+ */
+
+ Node *rootNodePtr = tagPtr->tagRootPtr;
+ summaryPtr = (Summary *) ckalloc(sizeof(Summary));
+ summaryPtr->tagPtr = tagPtr;
+ summaryPtr->toggleCount = tagPtr->toggleCount - delta;
+ summaryPtr->nextPtr = rootNodePtr->summaryPtr;
+ rootNodePtr->summaryPtr = summaryPtr;
+ rootNodePtr = rootNodePtr->parentPtr;
+ rootLevel = rootNodePtr->level;
+ tagPtr->tagRootPtr = rootNodePtr;
+ }
+ summaryPtr = (Summary *) ckalloc(sizeof(Summary));
+ summaryPtr->tagPtr = tagPtr;
+ summaryPtr->toggleCount = delta;
+ summaryPtr->nextPtr = nodePtr->summaryPtr;
+ nodePtr->summaryPtr = summaryPtr;
+ }
+ }
+
+ /*
+ * If we've decremented the toggle count, then it may be necessary
+ * to push the tag root down one or more levels.
+ */
+
+ if (delta >= 0) {
+ return;
+ }
+ if (tagPtr->toggleCount == 0) {
+ tagPtr->tagRootPtr = (Node *) NULL;
+ return;
+ }
+ nodePtr = tagPtr->tagRootPtr;
+ while (nodePtr->level > 0) {
+ /*
+ * See if a single child node accounts for all of the tag's
+ * toggles. If so, push the root down one level.
+ */
+
+ for (node2Ptr = nodePtr->children.nodePtr;
+ node2Ptr != (Node *)NULL ;
+ node2Ptr = node2Ptr->nextPtr) {
+ for (prevPtr = NULL, summaryPtr = node2Ptr->summaryPtr;
+ summaryPtr != NULL;
+ prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ break;
+ }
+ }
+ if (summaryPtr == NULL) {
+ continue;
+ }
+ if (summaryPtr->toggleCount != tagPtr->toggleCount) {
+ /*
+ * No node has all toggles, so the root is still valid.
+ */
+
+ return;
+ }
+
+ /*
+ * This node has all the toggles, so push down the root.
+ */
+
+ if (prevPtr == NULL) {
+ node2Ptr->summaryPtr = summaryPtr->nextPtr;
+ } else {
+ prevPtr->nextPtr = summaryPtr->nextPtr;
+ }
+ ckfree((char *) summaryPtr);
+ tagPtr->tagRootPtr = node2Ptr;
+ break;
+ }
+ nodePtr = tagPtr->tagRootPtr;
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * FindTagStart --
+ *
+ * Find the start of the first range of a tag.
+ *
+ * Results:
+ * The return value is a pointer to the first tag toggle segment
+ * for the tag. This can be either a tagon or tagoff segments because
+ * of the way TkBTreeAdd removes a tag.
+ * Sets *indexPtr to be the index of the tag toggle.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static TkTextSegment *
+FindTagStart(tree, tagPtr, indexPtr)
+ TkTextBTree tree; /* Tree to search within */
+ TkTextTag *tagPtr; /* Tag to search for. */
+ TkTextIndex *indexPtr; /* Return - index information */
+{
+ register Node *nodePtr;
+ register TkTextLine *linePtr;
+ register TkTextSegment *segPtr;
+ register Summary *summaryPtr;
+ int offset;
+
+ nodePtr = tagPtr->tagRootPtr;
+ if (nodePtr == (Node *) NULL) {
+ return NULL;
+ }
+
+ /*
+ * Search from the root of the subtree that contains the tag down
+ * to the level 0 node.
+ */
+
+ while (nodePtr->level > 0) {
+ for (nodePtr = nodePtr->children.nodePtr ; nodePtr != (Node *) NULL;
+ nodePtr = nodePtr->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ goto gotNodeWithTag;
+ }
+ }
+ }
+ gotNodeWithTag:
+ continue;
+ }
+
+ /*
+ * Work through the lines attached to the level-0 node.
+ */
+
+ for (linePtr = nodePtr->children.linePtr; linePtr != (TkTextLine *) NULL;
+ linePtr = linePtr->nextPtr) {
+ for (offset = 0, segPtr = linePtr->segPtr ; segPtr != NULL;
+ offset += segPtr->size, segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (segPtr->body.toggle.tagPtr == tagPtr)) {
+ /*
+ * It is possible that this is a tagoff tag, but that
+ * gets cleaned up later.
+ */
+ indexPtr->tree = tree;
+ indexPtr->linePtr = linePtr;
+ indexPtr->charIndex = offset;
+ return segPtr;
+ }
+ }
+ }
+ return NULL;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * FindTagEnd --
+ *
+ * Find the end of the last range of a tag.
+ *
+ * Results:
+ * The return value is a pointer to the last tag toggle segment
+ * for the tag. This can be either a tagon or tagoff segments because
+ * of the way TkBTreeAdd removes a tag.
+ * Sets *indexPtr to be the index of the tag toggle.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static TkTextSegment *
+FindTagEnd(tree, tagPtr, indexPtr)
+ TkTextBTree tree; /* Tree to search within */
+ TkTextTag *tagPtr; /* Tag to search for. */
+ TkTextIndex *indexPtr; /* Return - index information */
+{
+ register Node *nodePtr, *lastNodePtr;
+ register TkTextLine *linePtr ,*lastLinePtr;
+ register TkTextSegment *segPtr, *lastSegPtr, *last2SegPtr;
+ register Summary *summaryPtr;
+ int lastoffset, lastoffset2, offset;
+
+ nodePtr = tagPtr->tagRootPtr;
+ if (nodePtr == (Node *) NULL) {
+ return NULL;
+ }
+
+ /*
+ * Search from the root of the subtree that contains the tag down
+ * to the level 0 node.
+ */
+
+ while (nodePtr->level > 0) {
+ for (lastNodePtr = NULL, nodePtr = nodePtr->children.nodePtr ;
+ nodePtr != (Node *) NULL; nodePtr = nodePtr->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ lastNodePtr = nodePtr;
+ break;
+ }
+ }
+ }
+ nodePtr = lastNodePtr;
+ }
+
+ /*
+ * Work through the lines attached to the level-0 node.
+ */
+ last2SegPtr = NULL;
+ lastoffset2 = 0;
+ lastoffset = 0;
+ for (lastLinePtr = NULL, linePtr = nodePtr->children.linePtr;
+ linePtr != (TkTextLine *) NULL; linePtr = linePtr->nextPtr) {
+ for (offset = 0, lastSegPtr = NULL, segPtr = linePtr->segPtr ;
+ segPtr != NULL;
+ offset += segPtr->size, segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (segPtr->body.toggle.tagPtr == tagPtr)) {
+ lastSegPtr = segPtr;
+ lastoffset = offset;
+ }
+ }
+ if (lastSegPtr != NULL) {
+ lastLinePtr = linePtr;
+ last2SegPtr = lastSegPtr;
+ lastoffset2 = lastoffset;
+ }
+ }
+ indexPtr->tree = tree;
+ indexPtr->linePtr = lastLinePtr;
+ indexPtr->charIndex = lastoffset2;
+ return last2SegPtr;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeStartSearch --
+ *
+ * This procedure sets up a search for tag transitions involving
+ * a given tag (or all tags) in a given range of the text.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The information at *searchPtr is set up so that subsequent calls
+ * to TkBTreeNextTag or TkBTreePrevTag will return information about the
+ * locations of tag transitions. Note that TkBTreeNextTag or
+ * TkBTreePrevTag must be called to get the first transition.
+ * Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not
+ * guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be
+ * greater than that if *index1Ptr is less than the first tag transition.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, searchPtr)
+ TkTextIndex *index1Ptr; /* Search starts here. Tag toggles
+ * at this position will not be
+ * returned. */
+ TkTextIndex *index2Ptr; /* Search stops here. Tag toggles
+ * at this position *will* be
+ * returned. */
+ TkTextTag *tagPtr; /* Tag to search for. NULL means
+ * search for any tag. */
+ register TkTextSearch *searchPtr; /* Where to store information about
+ * search's progress. */
+{
+ int offset;
+ TkTextIndex index0; /* First index of the tag */
+ TkTextSegment *seg0Ptr; /* First segment of the tag */
+
+ /*
+ * Find the segment that contains the first toggle for the tag. This
+ * may become the starting point in the search.
+ */
+
+ seg0Ptr = FindTagStart(index1Ptr->tree, tagPtr, &index0);
+ if (seg0Ptr == (TkTextSegment *) NULL) {
+ /*
+ * Even though there are no toggles, the display code still
+ * uses the search curIndex, so initialize that anyway.
+ */
+
+ searchPtr->linesLeft = 0;
+ searchPtr->curIndex = *index1Ptr;
+ searchPtr->segPtr = NULL;
+ searchPtr->nextPtr = NULL;
+ return;
+ }
+ if (TkTextIndexCmp(index1Ptr, &index0) < 0) {
+ /*
+ * Adjust start of search up to the first range of the tag
+ */
+
+ searchPtr->curIndex = index0;
+ searchPtr->segPtr = NULL;
+ searchPtr->nextPtr = seg0Ptr; /* Will be returned by NextTag */
+ index1Ptr = &index0;
+ } else {
+ searchPtr->curIndex = *index1Ptr;
+ searchPtr->segPtr = NULL;
+ searchPtr->nextPtr = TkTextIndexToSeg(index1Ptr, &offset);
+ searchPtr->curIndex.charIndex -= offset;
+ }
+ searchPtr->lastPtr = TkTextIndexToSeg(index2Ptr, (int *) NULL);
+ searchPtr->tagPtr = tagPtr;
+ searchPtr->linesLeft = TkBTreeLineIndex(index2Ptr->linePtr) + 1
+ - TkBTreeLineIndex(index1Ptr->linePtr);
+ searchPtr->allTags = (tagPtr == NULL);
+ if (searchPtr->linesLeft == 1) {
+ /*
+ * Starting and stopping segments are in the same line; mark the
+ * search as over immediately if the second segment is before the
+ * first. A search does not return a toggle at the very start of
+ * the range, unless the range is artificially moved up to index0.
+ */
+ if (((index1Ptr == &index0) &&
+ (index1Ptr->charIndex > index2Ptr->charIndex)) ||
+ ((index1Ptr != &index0) &&
+ (index1Ptr->charIndex >= index2Ptr->charIndex))) {
+ searchPtr->linesLeft = 0;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeStartSearchBack --
+ *
+ * This procedure sets up a search backwards for tag transitions involving
+ * a given tag (or all tags) in a given range of the text. In the
+ * normal case the first index (*index1Ptr) is beyond the second
+ * index (*index2Ptr).
+ *
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The information at *searchPtr is set up so that subsequent calls
+ * to TkBTreePrevTag will return information about the
+ * locations of tag transitions. Note that TkBTreePrevTag must be called
+ * to get the first transition.
+ * Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not
+ * guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be
+ * less than that if *index1Ptr is greater than the last tag transition.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeStartSearchBack(index1Ptr, index2Ptr, tagPtr, searchPtr)
+ TkTextIndex *index1Ptr; /* Search starts here. Tag toggles
+ * at this position will not be
+ * returned. */
+ TkTextIndex *index2Ptr; /* Search stops here. Tag toggles
+ * at this position *will* be
+ * returned. */
+ TkTextTag *tagPtr; /* Tag to search for. NULL means
+ * search for any tag. */
+ register TkTextSearch *searchPtr; /* Where to store information about
+ * search's progress. */
+{
+ int offset;
+ TkTextIndex index0; /* Last index of the tag */
+ TkTextIndex backOne; /* One character before starting index */
+ TkTextSegment *seg0Ptr; /* Last segment of the tag */
+
+ /*
+ * Find the segment that contains the last toggle for the tag. This
+ * may become the starting point in the search.
+ */
+
+ seg0Ptr = FindTagEnd(index1Ptr->tree, tagPtr, &index0);
+ if (seg0Ptr == (TkTextSegment *) NULL) {
+ /*
+ * Even though there are no toggles, the display code still
+ * uses the search curIndex, so initialize that anyway.
+ */
+
+ searchPtr->linesLeft = 0;
+ searchPtr->curIndex = *index1Ptr;
+ searchPtr->segPtr = NULL;
+ searchPtr->nextPtr = NULL;
+ return;
+ }
+
+ /*
+ * Adjust the start of the search so it doesn't find any tag toggles
+ * that are right at the index specified by the user.
+ */
+
+ if (TkTextIndexCmp(index1Ptr, &index0) > 0) {
+ searchPtr->curIndex = index0;
+ index1Ptr = &index0;
+ } else {
+ TkTextIndexBackChars(index1Ptr, 1, &searchPtr->curIndex);
+ }
+ searchPtr->segPtr = NULL;
+ searchPtr->nextPtr = TkTextIndexToSeg(&searchPtr->curIndex, &offset);
+ searchPtr->curIndex.charIndex -= offset;
+
+ /*
+ * Adjust the end of the search so it does find toggles that are right
+ * at the second index specified by the user.
+ */
+
+ if ((TkBTreeLineIndex(index2Ptr->linePtr) == 0) &&
+ (index2Ptr->charIndex == 0)) {
+ backOne = *index2Ptr;
+ searchPtr->lastPtr = NULL; /* Signals special case for 1.0 */
+ } else {
+ TkTextIndexBackChars(index2Ptr, 1, &backOne);
+ searchPtr->lastPtr = TkTextIndexToSeg(&backOne, (int *) NULL);
+ }
+ searchPtr->tagPtr = tagPtr;
+ searchPtr->linesLeft = TkBTreeLineIndex(index1Ptr->linePtr) + 1
+ - TkBTreeLineIndex(backOne.linePtr);
+ searchPtr->allTags = (tagPtr == NULL);
+ if (searchPtr->linesLeft == 1) {
+ /*
+ * Starting and stopping segments are in the same line; mark the
+ * search as over immediately if the second segment is after the
+ * first.
+ */
+
+ if (index1Ptr->charIndex <= backOne.charIndex) {
+ searchPtr->linesLeft = 0;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeNextTag --
+ *
+ * Once a tag search has begun, successive calls to this procedure
+ * return successive tag toggles. Note: it is NOT SAFE to call this
+ * procedure if characters have been inserted into or deleted from
+ * the B-tree since the call to TkBTreeStartSearch.
+ *
+ * Results:
+ * The return value is 1 if another toggle was found that met the
+ * criteria specified in the call to TkBTreeStartSearch; in this
+ * case searchPtr->curIndex gives the toggle's position and
+ * searchPtr->curTagPtr points to its segment. 0 is returned if
+ * no more matching tag transitions were found; in this case
+ * searchPtr->curIndex is the same as searchPtr->stopIndex.
+ *
+ * Side effects:
+ * Information in *searchPtr is modified to update the state of the
+ * search and indicate where the next tag toggle is located.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreeNextTag(searchPtr)
+ register TkTextSearch *searchPtr; /* Information about search in
+ * progress; must have been set up by
+ * call to TkBTreeStartSearch. */
+{
+ register TkTextSegment *segPtr;
+ register Node *nodePtr;
+ register Summary *summaryPtr;
+
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+
+ /*
+ * The outermost loop iterates over lines that may potentially contain
+ * a relevant tag transition, starting from the current segment in
+ * the current line.
+ */
+
+ segPtr = searchPtr->nextPtr;
+ while (1) {
+ /*
+ * Check for more tags on the current line.
+ */
+
+ for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) {
+ if (segPtr == searchPtr->lastPtr) {
+ goto searchOver;
+ }
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (searchPtr->allTags
+ || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
+ searchPtr->segPtr = segPtr;
+ searchPtr->nextPtr = segPtr->nextPtr;
+ searchPtr->tagPtr = segPtr->body.toggle.tagPtr;
+ return 1;
+ }
+ searchPtr->curIndex.charIndex += segPtr->size;
+ }
+
+ /*
+ * See if there are more lines associated with the current parent
+ * node. If so, go back to the top of the loop to search the next
+ * one.
+ */
+
+ nodePtr = searchPtr->curIndex.linePtr->parentPtr;
+ searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr;
+ searchPtr->linesLeft--;
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+ if (searchPtr->curIndex.linePtr != NULL) {
+ segPtr = searchPtr->curIndex.linePtr->segPtr;
+ searchPtr->curIndex.charIndex = 0;
+ continue;
+ }
+ if (nodePtr == searchPtr->tagPtr->tagRootPtr) {
+ goto searchOver;
+ }
+
+ /*
+ * Search across and up through the B-tree's node hierarchy looking
+ * for the next node that has a relevant tag transition somewhere in
+ * its subtree. Be sure to update linesLeft as we skip over large
+ * chunks of lines.
+ */
+
+ while (1) {
+ while (nodePtr->nextPtr == NULL) {
+ if (nodePtr->parentPtr == NULL ||
+ nodePtr->parentPtr == searchPtr->tagPtr->tagRootPtr) {
+ goto searchOver;
+ }
+ nodePtr = nodePtr->parentPtr;
+ }
+ nodePtr = nodePtr->nextPtr;
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if ((searchPtr->allTags) ||
+ (summaryPtr->tagPtr == searchPtr->tagPtr)) {
+ goto gotNodeWithTag;
+ }
+ }
+ searchPtr->linesLeft -= nodePtr->numLines;
+ }
+
+ /*
+ * At this point we've found a subtree that has a relevant tag
+ * transition. Now search down (and across) through that subtree
+ * to find the first level-0 node that has a relevant tag transition.
+ */
+
+ gotNodeWithTag:
+ while (nodePtr->level > 0) {
+ for (nodePtr = nodePtr->children.nodePtr; ;
+ nodePtr = nodePtr->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if ((searchPtr->allTags)
+ || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
+ goto nextChild;
+ }
+ }
+ searchPtr->linesLeft -= nodePtr->numLines;
+ if (nodePtr->nextPtr == NULL) {
+ panic("TkBTreeNextTag found incorrect tag summary info.");
+ }
+ }
+ nextChild:
+ continue;
+ }
+
+ /*
+ * Now we're down to a level-0 node that contains a line that contains
+ * a relevant tag transition. Set up line information and go back to
+ * the beginning of the loop to search through lines.
+ */
+
+ searchPtr->curIndex.linePtr = nodePtr->children.linePtr;
+ searchPtr->curIndex.charIndex = 0;
+ segPtr = searchPtr->curIndex.linePtr->segPtr;
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+ continue;
+ }
+
+ searchOver:
+ searchPtr->linesLeft = 0;
+ searchPtr->segPtr = NULL;
+ return 0;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreePrevTag --
+ *
+ * Once a tag search has begun, successive calls to this procedure
+ * return successive tag toggles in the reverse direction.
+ * Note: it is NOT SAFE to call this
+ * procedure if characters have been inserted into or deleted from
+ * the B-tree since the call to TkBTreeStartSearch.
+ *
+ * Results:
+ * The return value is 1 if another toggle was found that met the
+ * criteria specified in the call to TkBTreeStartSearch; in this
+ * case searchPtr->curIndex gives the toggle's position and
+ * searchPtr->curTagPtr points to its segment. 0 is returned if
+ * no more matching tag transitions were found; in this case
+ * searchPtr->curIndex is the same as searchPtr->stopIndex.
+ *
+ * Side effects:
+ * Information in *searchPtr is modified to update the state of the
+ * search and indicate where the next tag toggle is located.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreePrevTag(searchPtr)
+ register TkTextSearch *searchPtr; /* Information about search in
+ * progress; must have been set up by
+ * call to TkBTreeStartSearch. */
+{
+ register TkTextSegment *segPtr, *prevPtr;
+ register TkTextLine *linePtr, *prevLinePtr;
+ register Node *nodePtr, *node2Ptr, *prevNodePtr;
+ register Summary *summaryPtr;
+ int charIndex;
+ int pastLast; /* Saw last marker during scan */
+ int linesSkipped;
+
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+
+ /*
+ * The outermost loop iterates over lines that may potentially contain
+ * a relevant tag transition, starting from the current segment in
+ * the current line. "nextPtr" is maintained as the last segment in
+ * a line that we can look at.
+ */
+
+ while (1) {
+ /*
+ * Check for the last toggle before the current segment on this line.
+ */
+ charIndex = 0;
+ if (searchPtr->lastPtr == NULL) {
+ /*
+ * Search back to the very beginning, so pastLast is irrelevent.
+ */
+ pastLast = 1;
+ } else {
+ pastLast = 0;
+ }
+ for (prevPtr = NULL, segPtr = searchPtr->curIndex.linePtr->segPtr ;
+ segPtr != NULL && segPtr != searchPtr->nextPtr;
+ segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (searchPtr->allTags
+ || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
+ prevPtr = segPtr;
+ searchPtr->curIndex.charIndex = charIndex;
+ }
+ if (segPtr == searchPtr->lastPtr) {
+ prevPtr = NULL; /* Segments earlier than last don't count */
+ pastLast = 1;
+ }
+ charIndex += segPtr->size;
+ }
+ if (prevPtr != NULL) {
+ if (searchPtr->linesLeft == 1 && !pastLast) {
+ /*
+ * We found a segment that is before the stopping index.
+ * Note that it is OK if prevPtr == lastPtr.
+ */
+ goto searchOver;
+ }
+ searchPtr->segPtr = prevPtr;
+ searchPtr->nextPtr = prevPtr;
+ searchPtr->tagPtr = prevPtr->body.toggle.tagPtr;
+ return 1;
+ }
+
+ searchPtr->linesLeft--;
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+
+ /*
+ * See if there are more lines associated with the current parent
+ * node. If so, go back to the top of the loop to search the previous
+ * one.
+ */
+
+ nodePtr = searchPtr->curIndex.linePtr->parentPtr;
+ for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr;
+ linePtr != NULL && linePtr != searchPtr->curIndex.linePtr;
+ prevLinePtr = linePtr, linePtr = linePtr->nextPtr) {
+ /* empty loop body */ ;
+ }
+ if (prevLinePtr != NULL) {
+ searchPtr->curIndex.linePtr = prevLinePtr;
+ searchPtr->nextPtr = NULL;
+ continue;
+ }
+ if (nodePtr == searchPtr->tagPtr->tagRootPtr) {
+ goto searchOver;
+ }
+
+ /*
+ * Search across and up through the B-tree's node hierarchy looking
+ * for the previous node that has a relevant tag transition somewhere in
+ * its subtree. The search and line counting is trickier with/out
+ * back pointers. We'll scan all the nodes under a parent up to
+ * the current node, searching all of them for tag state. The last
+ * one we find, if any, is recorded in prevNodePtr, and any nodes
+ * past prevNodePtr that don't have tag state increment linesSkipped.
+ */
+
+ while (1) {
+ for (prevNodePtr = NULL, linesSkipped = 0,
+ node2Ptr = nodePtr->parentPtr->children.nodePtr ;
+ node2Ptr != nodePtr; node2Ptr = node2Ptr->nextPtr) {
+ for (summaryPtr = node2Ptr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if ((searchPtr->allTags) ||
+ (summaryPtr->tagPtr == searchPtr->tagPtr)) {
+ prevNodePtr = node2Ptr;
+ linesSkipped = 0;
+ goto keepLooking;
+ }
+ }
+ linesSkipped += node2Ptr->numLines;
+
+ keepLooking:
+ continue;
+ }
+ if (prevNodePtr != NULL) {
+ nodePtr = prevNodePtr;
+ searchPtr->linesLeft -= linesSkipped;
+ goto gotNodeWithTag;
+ }
+ nodePtr = nodePtr->parentPtr;
+ if (nodePtr->parentPtr == NULL ||
+ nodePtr == searchPtr->tagPtr->tagRootPtr) {
+ goto searchOver;
+ }
+ }
+
+ /*
+ * At this point we've found a subtree that has a relevant tag
+ * transition. Now search down (and across) through that subtree
+ * to find the last level-0 node that has a relevant tag transition.
+ */
+
+ gotNodeWithTag:
+ while (nodePtr->level > 0) {
+ for (linesSkipped = 0, prevNodePtr = NULL,
+ nodePtr = nodePtr->children.nodePtr; nodePtr != NULL ;
+ nodePtr = nodePtr->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if ((searchPtr->allTags)
+ || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
+ prevNodePtr = nodePtr;
+ linesSkipped = 0;
+ goto keepLooking2;
+ }
+ }
+ linesSkipped += nodePtr->numLines;
+
+ keepLooking2:
+ continue;
+ }
+ if (prevNodePtr == NULL) {
+ panic("TkBTreePrevTag found incorrect tag summary info.");
+ }
+ searchPtr->linesLeft -= linesSkipped;
+ nodePtr = prevNodePtr;
+ }
+
+ /*
+ * Now we're down to a level-0 node that contains a line that contains
+ * a relevant tag transition. Set up line information and go back to
+ * the beginning of the loop to search through lines. We start with
+ * the last line below the node.
+ */
+
+ for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr;
+ linePtr != NULL ;
+ prevLinePtr = linePtr, linePtr = linePtr->nextPtr) {
+ /* empty loop body */ ;
+ }
+ searchPtr->curIndex.linePtr = prevLinePtr;
+ searchPtr->curIndex.charIndex = 0;
+ if (searchPtr->linesLeft <= 0) {
+ goto searchOver;
+ }
+ continue;
+ }
+
+ searchOver:
+ searchPtr->linesLeft = 0;
+ searchPtr->segPtr = NULL;
+ return 0;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeCharTagged --
+ *
+ * Determine whether a particular character has a particular tag.
+ *
+ * Results:
+ * The return value is 1 if the given tag is in effect at the
+ * character given by linePtr and ch, and 0 otherwise.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreeCharTagged(indexPtr, tagPtr)
+ TkTextIndex *indexPtr; /* Indicates a character position at
+ * which to check for a tag. */
+ TkTextTag *tagPtr; /* Tag of interest. */
+{
+ register Node *nodePtr;
+ register TkTextLine *siblingLinePtr;
+ register TkTextSegment *segPtr;
+ TkTextSegment *toggleSegPtr;
+ int toggles, index;
+
+ /*
+ * Check for toggles for the tag in indexPtr's line but before
+ * indexPtr. If there is one, its type indicates whether or
+ * not the character is tagged.
+ */
+
+ toggleSegPtr = NULL;
+ for (index = 0, segPtr = indexPtr->linePtr->segPtr;
+ (index + segPtr->size) <= indexPtr->charIndex;
+ index += segPtr->size, segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (segPtr->body.toggle.tagPtr == tagPtr)) {
+ toggleSegPtr = segPtr;
+ }
+ }
+ if (toggleSegPtr != NULL) {
+ return (toggleSegPtr->typePtr == &tkTextToggleOnType);
+ }
+
+ /*
+ * No toggle in this line. Look for toggles for the tag in lines
+ * that are predecessors of indexPtr->linePtr but under the same
+ * level-0 node.
+ */
+
+ for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
+ siblingLinePtr != indexPtr->linePtr;
+ siblingLinePtr = siblingLinePtr->nextPtr) {
+ for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType))
+ && (segPtr->body.toggle.tagPtr == tagPtr)) {
+ toggleSegPtr = segPtr;
+ }
+ }
+ }
+ if (toggleSegPtr != NULL) {
+ return (toggleSegPtr->typePtr == &tkTextToggleOnType);
+ }
+
+ /*
+ * No toggle in this node. Scan upwards through the ancestors of
+ * this node, counting the number of toggles of the given tag in
+ * siblings that precede that node.
+ */
+
+ toggles = 0;
+ for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
+ nodePtr = nodePtr->parentPtr) {
+ register Node *siblingPtr;
+ register Summary *summaryPtr;
+
+ for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
+ siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
+ for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ toggles += summaryPtr->toggleCount;
+ }
+ }
+ }
+ if (nodePtr == tagPtr->tagRootPtr) {
+ break;
+ }
+ }
+
+ /*
+ * An odd number of toggles means that the tag is present at the
+ * given point.
+ */
+
+ return toggles & 1;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeGetTags --
+ *
+ * Return information about all of the tags that are associated
+ * with a particular character in a B-tree of text.
+ *
+ * Results:
+ * The return value is a malloc-ed array containing pointers to
+ * information for each of the tags that is associated with
+ * the character at the position given by linePtr and ch. The
+ * word at *numTagsPtr is filled in with the number of pointers
+ * in the array. It is up to the caller to free the array by
+ * passing it to free. If there are no tags at the given character
+ * then a NULL pointer is returned and *numTagsPtr will be set to 0.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+TkTextTag **
+TkBTreeGetTags(indexPtr, numTagsPtr)
+ TkTextIndex *indexPtr; /* Indicates a particular position in
+ * the B-tree. */
+ int *numTagsPtr; /* Store number of tags found at this
+ * location. */
+{
+ register Node *nodePtr;
+ register TkTextLine *siblingLinePtr;
+ register TkTextSegment *segPtr;
+ int src, dst, index;
+ TagInfo tagInfo;
+#define NUM_TAG_INFOS 10
+
+ tagInfo.numTags = 0;
+ tagInfo.arraySize = NUM_TAG_INFOS;
+ tagInfo.tagPtrs = (TkTextTag **) ckalloc((unsigned)
+ NUM_TAG_INFOS*sizeof(TkTextTag *));
+ tagInfo.counts = (int *) ckalloc((unsigned)
+ NUM_TAG_INFOS*sizeof(int));
+
+ /*
+ * Record tag toggles within the line of indexPtr but preceding
+ * indexPtr.
+ */
+
+ for (index = 0, segPtr = indexPtr->linePtr->segPtr;
+ (index + segPtr->size) <= indexPtr->charIndex;
+ index += segPtr->size, segPtr = segPtr->nextPtr) {
+ if ((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType)) {
+ IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
+ }
+ }
+
+ /*
+ * Record toggles for tags in lines that are predecessors of
+ * indexPtr->linePtr but under the same level-0 node.
+ */
+
+ for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
+ siblingLinePtr != indexPtr->linePtr;
+ siblingLinePtr = siblingLinePtr->nextPtr) {
+ for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if ((segPtr->typePtr == &tkTextToggleOnType)
+ || (segPtr->typePtr == &tkTextToggleOffType)) {
+ IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
+ }
+ }
+ }
+
+ /*
+ * For each node in the ancestry of this line, record tag toggles
+ * for all siblings that precede that node.
+ */
+
+ for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
+ nodePtr = nodePtr->parentPtr) {
+ register Node *siblingPtr;
+ register Summary *summaryPtr;
+
+ for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
+ siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
+ for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->toggleCount & 1) {
+ IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount,
+ &tagInfo);
+ }
+ }
+ }
+ }
+
+ /*
+ * Go through the tag information and squash out all of the tags
+ * that have even toggle counts (these tags exist before the point
+ * of interest, but not at the desired character itself).
+ */
+
+ for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
+ if (tagInfo.counts[src] & 1) {
+ tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
+ dst++;
+ }
+ }
+ *numTagsPtr = dst;
+ ckfree((char *) tagInfo.counts);
+ if (dst == 0) {
+ ckfree((char *) tagInfo.tagPtrs);
+ return NULL;
+ }
+ return tagInfo.tagPtrs;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * IncCount --
+ *
+ * This is a utility procedure used by TkBTreeGetTags. It
+ * increments the count for a particular tag, adding a new
+ * entry for that tag if there wasn't one previously.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The information at *tagInfoPtr may be modified, and the arrays
+ * may be reallocated to make them larger.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+IncCount(tagPtr, inc, tagInfoPtr)
+ TkTextTag *tagPtr; /* Handle for tag. */
+ int inc; /* Amount by which to increment tag count. */
+ TagInfo *tagInfoPtr; /* Holds cumulative information about tags;
+ * increment count here. */
+{
+ register TkTextTag **tagPtrPtr;
+ int count;
+
+ for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
+ count > 0; tagPtrPtr++, count--) {
+ if (*tagPtrPtr == tagPtr) {
+ tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
+ return;
+ }
+ }
+
+ /*
+ * There isn't currently an entry for this tag, so we have to
+ * make a new one. If the arrays are full, then enlarge the
+ * arrays first.
+ */
+
+ if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
+ TkTextTag **newTags;
+ int *newCounts, newSize;
+
+ newSize = 2*tagInfoPtr->arraySize;
+ newTags = (TkTextTag **) ckalloc((unsigned)
+ (newSize*sizeof(TkTextTag *)));
+ memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
+ tagInfoPtr->arraySize * sizeof(TkTextTag *));
+ ckfree((char *) tagInfoPtr->tagPtrs);
+ tagInfoPtr->tagPtrs = newTags;
+ newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
+ memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
+ tagInfoPtr->arraySize * sizeof(int));
+ ckfree((char *) tagInfoPtr->counts);
+ tagInfoPtr->counts = newCounts;
+ tagInfoPtr->arraySize = newSize;
+ }
+
+ tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
+ tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
+ tagInfoPtr->numTags++;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeCheck --
+ *
+ * This procedure runs a set of consistency checks over a B-tree
+ * and panics if any inconsistencies are found.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * If a structural defect is found, the procedure panics with an
+ * error message.
+ *
+ *----------------------------------------------------------------------
+ */
+
+void
+TkBTreeCheck(tree)
+ TkTextBTree tree; /* Tree to check. */
+{
+ BTree *treePtr = (BTree *) tree;
+ register Summary *summaryPtr;
+ register Node *nodePtr;
+ register TkTextLine *linePtr;
+ register TkTextSegment *segPtr;
+ register TkTextTag *tagPtr;
+ Tcl_HashEntry *entryPtr;
+ Tcl_HashSearch search;
+ int count;
+
+ /*
+ * Make sure that the tag toggle counts and the tag root pointers are OK.
+ */
+ for (entryPtr = Tcl_FirstHashEntry(&treePtr->textPtr->tagTable, &search);
+ entryPtr != NULL ; entryPtr = Tcl_NextHashEntry(&search)) {
+ tagPtr = (TkTextTag *) Tcl_GetHashValue(entryPtr);
+ nodePtr = tagPtr->tagRootPtr;
+ if (nodePtr == (Node *) NULL) {
+ if (tagPtr->toggleCount != 0) {
+ panic("TkBTreeCheck found \"%s\" with toggles (%d) but no root",
+ tagPtr->name, tagPtr->toggleCount);
+ }
+ continue; /* no ranges for the tag */
+ } else if (tagPtr->toggleCount == 0) {
+ panic("TkBTreeCheck found root for \"%s\" with no toggles",
+ tagPtr->name);
+ } else if (tagPtr->toggleCount & 1) {
+ panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
+ tagPtr->name, tagPtr->toggleCount);
+ }
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ panic("TkBTreeCheck found root node with summary info");
+ }
+ }
+ count = 0;
+ if (nodePtr->level > 0) {
+ for (nodePtr = nodePtr->children.nodePtr ; nodePtr != NULL ;
+ nodePtr = nodePtr->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr == tagPtr) {
+ count += summaryPtr->toggleCount;
+ }
+ }
+ }
+ } else {
+ for (linePtr = nodePtr->children.linePtr ; linePtr != NULL ;
+ linePtr = linePtr->nextPtr) {
+ for (segPtr = linePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if ((segPtr->typePtr == &tkTextToggleOnType ||
+ segPtr->typePtr == &tkTextToggleOffType) &&
+ segPtr->body.toggle.tagPtr == tagPtr) {
+ count++;
+ }
+ }
+ }
+ }
+ if (count != tagPtr->toggleCount) {
+ panic("TkBTreeCheck toggleCount (%d) wrong for \"%s\" should be (%d)",
+ tagPtr->toggleCount, tagPtr->name, count);
+ }
+ }
+
+ /*
+ * Call a recursive procedure to do the main body of checks.
+ */
+
+ nodePtr = treePtr->rootPtr;
+ CheckNodeConsistency(treePtr->rootPtr);
+
+ /*
+ * Make sure that there are at least two lines in the text and
+ * that the last line has no characters except a newline.
+ */
+
+ if (nodePtr->numLines < 2) {
+ panic("TkBTreeCheck: less than 2 lines in tree");
+ }
+ while (nodePtr->level > 0) {
+ nodePtr = nodePtr->children.nodePtr;
+ while (nodePtr->nextPtr != NULL) {
+ nodePtr = nodePtr->nextPtr;
+ }
+ }
+ linePtr = nodePtr->children.linePtr;
+ while (linePtr->nextPtr != NULL) {
+ linePtr = linePtr->nextPtr;
+ }
+ segPtr = linePtr->segPtr;
+ while ((segPtr->typePtr == &tkTextToggleOffType)
+ || (segPtr->typePtr == &tkTextRightMarkType)
+ || (segPtr->typePtr == &tkTextLeftMarkType)) {
+ /*
+ * It's OK to toggle a tag off in the last line, but
+ * not to start a new range. It's also OK to have marks
+ * in the last line.
+ */
+
+ segPtr = segPtr->nextPtr;
+ }
+ if (segPtr->typePtr != &tkTextCharType) {
+ panic("TkBTreeCheck: last line has bogus segment type");
+ }
+ if (segPtr->nextPtr != NULL) {
+ panic("TkBTreeCheck: last line has too many segments");
+ }
+ if (segPtr->size != 1) {
+ panic("TkBTreeCheck: last line has wrong # characters: %d",
+ segPtr->size);
+ }
+ if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) {
+ panic("TkBTreeCheck: last line had bad value: %s",
+ segPtr->body.chars);
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * CheckNodeConsistency --
+ *
+ * This procedure is called as part of consistency checking for
+ * B-trees: it checks several aspects of a node and also runs
+ * checks recursively on the node's children.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * If anything suspicious is found in the tree structure, the
+ * procedure panics.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+CheckNodeConsistency(nodePtr)
+ register Node *nodePtr; /* Node whose subtree should be
+ * checked. */
+{
+ register Node *childNodePtr;
+ register Summary *summaryPtr, *summaryPtr2;
+ register TkTextLine *linePtr;
+ register TkTextSegment *segPtr;
+ int numChildren, numLines, toggleCount, minChildren;
+
+ if (nodePtr->parentPtr != NULL) {
+ minChildren = MIN_CHILDREN;
+ } else if (nodePtr->level > 0) {
+ minChildren = 2;
+ } else {
+ minChildren = 1;
+ }
+ if ((nodePtr->numChildren < minChildren)
+ || (nodePtr->numChildren > MAX_CHILDREN)) {
+ panic("CheckNodeConsistency: bad child count (%d)",
+ nodePtr->numChildren);
+ }
+
+ numChildren = 0;
+ numLines = 0;
+ if (nodePtr->level == 0) {
+ for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
+ linePtr = linePtr->nextPtr) {
+ if (linePtr->parentPtr != nodePtr) {
+ panic("CheckNodeConsistency: line doesn't point to parent");
+ }
+ if (linePtr->segPtr == NULL) {
+ panic("CheckNodeConsistency: line has no segments");
+ }
+ for (segPtr = linePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if (segPtr->typePtr->checkProc != NULL) {
+ (*segPtr->typePtr->checkProc)(segPtr, linePtr);
+ }
+ if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity)
+ && (segPtr->nextPtr != NULL)
+ && (segPtr->nextPtr->size == 0)
+ && (segPtr->nextPtr->typePtr->leftGravity)) {
+ panic("CheckNodeConsistency: wrong segment order for gravity");
+ }
+ if ((segPtr->nextPtr == NULL)
+ && (segPtr->typePtr != &tkTextCharType)) {
+ panic("CheckNodeConsistency: line ended with wrong type");
+ }
+ }
+ numChildren++;
+ numLines++;
+ }
+ } else {
+ for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
+ childNodePtr = childNodePtr->nextPtr) {
+ if (childNodePtr->parentPtr != nodePtr) {
+ panic("CheckNodeConsistency: node doesn't point to parent");
+ }
+ if (childNodePtr->level != (nodePtr->level-1)) {
+ panic("CheckNodeConsistency: level mismatch (%d %d)",
+ nodePtr->level, childNodePtr->level);
+ }
+ CheckNodeConsistency(childNodePtr);
+ for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ for (summaryPtr2 = nodePtr->summaryPtr; ;
+ summaryPtr2 = summaryPtr2->nextPtr) {
+ if (summaryPtr2 == NULL) {
+ if (summaryPtr->tagPtr->tagRootPtr == nodePtr) {
+ break;
+ }
+ panic("CheckNodeConsistency: node tag \"%s\" not %s",
+ summaryPtr->tagPtr->name,
+ "present in parent summaries");
+ }
+ if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
+ break;
+ }
+ }
+ }
+ numChildren++;
+ numLines += childNodePtr->numLines;
+ }
+ }
+ if (numChildren != nodePtr->numChildren) {
+ panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
+ numChildren, nodePtr->numChildren);
+ }
+ if (numLines != nodePtr->numLines) {
+ panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
+ numLines, nodePtr->numLines);
+ }
+
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr->tagPtr->toggleCount == summaryPtr->toggleCount) {
+ panic("CheckNodeConsistency: found unpruned root for \"%s\"",
+ summaryPtr->tagPtr->name);
+ }
+ toggleCount = 0;
+ if (nodePtr->level == 0) {
+ for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
+ linePtr = linePtr->nextPtr) {
+ for (segPtr = linePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if ((segPtr->typePtr != &tkTextToggleOnType)
+ && (segPtr->typePtr != &tkTextToggleOffType)) {
+ continue;
+ }
+ if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) {
+ toggleCount ++;
+ }
+ }
+ }
+ } else {
+ for (childNodePtr = nodePtr->children.nodePtr;
+ childNodePtr != NULL;
+ childNodePtr = childNodePtr->nextPtr) {
+ for (summaryPtr2 = childNodePtr->summaryPtr;
+ summaryPtr2 != NULL;
+ summaryPtr2 = summaryPtr2->nextPtr) {
+ if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
+ toggleCount += summaryPtr2->toggleCount;
+ }
+ }
+ }
+ }
+ if (toggleCount != summaryPtr->toggleCount) {
+ panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
+ toggleCount, summaryPtr->toggleCount);
+ }
+ for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
+ summaryPtr2 = summaryPtr2->nextPtr) {
+ if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
+ panic("CheckNodeConsistency: duplicated node tag: %s",
+ summaryPtr->tagPtr->name);
+ }
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * Rebalance --
+ *
+ * This procedure is called when a node of a B-tree appears to be
+ * out of balance (too many children, or too few). It rebalances
+ * that node and all of its ancestors in the tree.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The internal structure of treePtr may change.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+Rebalance(treePtr, nodePtr)
+ BTree *treePtr; /* Tree that is being rebalanced. */
+ register Node *nodePtr; /* Node that may be out of balance. */
+{
+ /*
+ * Loop over the entire ancestral chain of the node, working up
+ * through the tree one node at a time until the root node has
+ * been processed.
+ */
+
+ for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
+ register Node *newPtr, *childPtr;
+ register TkTextLine *linePtr;
+ int i;
+
+ /*
+ * Check to see if the node has too many children. If it does,
+ * then split off all but the first MIN_CHILDREN into a separate
+ * node following the original one. Then repeat until the
+ * node has a decent size.
+ */
+
+ if (nodePtr->numChildren > MAX_CHILDREN) {
+ while (1) {
+ /*
+ * If the node being split is the root node, then make a
+ * new root node above it first.
+ */
+
+ if (nodePtr->parentPtr == NULL) {
+ newPtr = (Node *) ckalloc(sizeof(Node));
+ newPtr->parentPtr = NULL;
+ newPtr->nextPtr = NULL;
+ newPtr->summaryPtr = NULL;
+ newPtr->level = nodePtr->level + 1;
+ newPtr->children.nodePtr = nodePtr;
+ newPtr->numChildren = 1;
+ newPtr->numLines = nodePtr->numLines;
+ RecomputeNodeCounts(newPtr);
+ treePtr->rootPtr = newPtr;
+ }
+ newPtr = (Node *) ckalloc(sizeof(Node));
+ newPtr->parentPtr = nodePtr->parentPtr;
+ newPtr->nextPtr = nodePtr->nextPtr;
+ nodePtr->nextPtr = newPtr;
+ newPtr->summaryPtr = NULL;
+ newPtr->level = nodePtr->level;
+ newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
+ if (nodePtr->level == 0) {
+ for (i = MIN_CHILDREN-1,
+ linePtr = nodePtr->children.linePtr;
+ i > 0; i--, linePtr = linePtr->nextPtr) {
+ /* Empty loop body. */
+ }
+ newPtr->children.linePtr = linePtr->nextPtr;
+ linePtr->nextPtr = NULL;
+ } else {
+ for (i = MIN_CHILDREN-1,
+ childPtr = nodePtr->children.nodePtr;
+ i > 0; i--, childPtr = childPtr->nextPtr) {
+ /* Empty loop body. */
+ }
+ newPtr->children.nodePtr = childPtr->nextPtr;
+ childPtr->nextPtr = NULL;
+ }
+ RecomputeNodeCounts(nodePtr);
+ nodePtr->parentPtr->numChildren++;
+ nodePtr = newPtr;
+ if (nodePtr->numChildren <= MAX_CHILDREN) {
+ RecomputeNodeCounts(nodePtr);
+ break;
+ }
+ }
+ }
+
+ while (nodePtr->numChildren < MIN_CHILDREN) {
+ register Node *otherPtr;
+ Node *halfwayNodePtr = NULL; /* Initialization needed only */
+ TkTextLine *halfwayLinePtr = NULL; /* to prevent cc warnings. */
+ int totalChildren, firstChildren, i;
+
+ /*
+ * Too few children for this node. If this is the root then,
+ * it's OK for it to have less than MIN_CHILDREN children
+ * as long as it's got at least two. If it has only one
+ * (and isn't at level 0), then chop the root node out of
+ * the tree and use its child as the new root.
+ */
+
+ if (nodePtr->parentPtr == NULL) {
+ if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
+ treePtr->rootPtr = nodePtr->children.nodePtr;
+ treePtr->rootPtr->parentPtr = NULL;
+ DeleteSummaries(nodePtr->summaryPtr);
+ ckfree((char *) nodePtr);
+ }
+ return;
+ }
+
+ /*
+ * Not the root. Make sure that there are siblings to
+ * balance with.
+ */
+
+ if (nodePtr->parentPtr->numChildren < 2) {
+ Rebalance(treePtr, nodePtr->parentPtr);
+ continue;
+ }
+
+ /*
+ * Find a sibling neighbor to borrow from, and arrange for
+ * nodePtr to be the earlier of the pair.
+ */
+
+ if (nodePtr->nextPtr == NULL) {
+ for (otherPtr = nodePtr->parentPtr->children.nodePtr;
+ otherPtr->nextPtr != nodePtr;
+ otherPtr = otherPtr->nextPtr) {
+ /* Empty loop body. */
+ }
+ nodePtr = otherPtr;
+ }
+ otherPtr = nodePtr->nextPtr;
+
+ /*
+ * We're going to either merge the two siblings together
+ * into one node or redivide the children among them to
+ * balance their loads. As preparation, join their two
+ * child lists into a single list and remember the half-way
+ * point in the list.
+ */
+
+ totalChildren = nodePtr->numChildren + otherPtr->numChildren;
+ firstChildren = totalChildren/2;
+ if (nodePtr->children.nodePtr == NULL) {
+ nodePtr->children = otherPtr->children;
+ otherPtr->children.nodePtr = NULL;
+ otherPtr->children.linePtr = NULL;
+ }
+ if (nodePtr->level == 0) {
+ register TkTextLine *linePtr;
+
+ for (linePtr = nodePtr->children.linePtr, i = 1;
+ linePtr->nextPtr != NULL;
+ linePtr = linePtr->nextPtr, i++) {
+ if (i == firstChildren) {
+ halfwayLinePtr = linePtr;
+ }
+ }
+ linePtr->nextPtr = otherPtr->children.linePtr;
+ while (i <= firstChildren) {
+ halfwayLinePtr = linePtr;
+ linePtr = linePtr->nextPtr;
+ i++;
+ }
+ } else {
+ register Node *childPtr;
+
+ for (childPtr = nodePtr->children.nodePtr, i = 1;
+ childPtr->nextPtr != NULL;
+ childPtr = childPtr->nextPtr, i++) {
+ if (i <= firstChildren) {
+ if (i == firstChildren) {
+ halfwayNodePtr = childPtr;
+ }
+ }
+ }
+ childPtr->nextPtr = otherPtr->children.nodePtr;
+ while (i <= firstChildren) {
+ halfwayNodePtr = childPtr;
+ childPtr = childPtr->nextPtr;
+ i++;
+ }
+ }
+
+ /*
+ * If the two siblings can simply be merged together, do it.
+ */
+
+ if (totalChildren <= MAX_CHILDREN) {
+ RecomputeNodeCounts(nodePtr);
+ nodePtr->nextPtr = otherPtr->nextPtr;
+ nodePtr->parentPtr->numChildren--;
+ DeleteSummaries(otherPtr->summaryPtr);
+ ckfree((char *) otherPtr);
+ continue;
+ }
+
+ /*
+ * The siblings can't be merged, so just divide their
+ * children evenly between them.
+ */
+
+ if (nodePtr->level == 0) {
+ otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
+ halfwayLinePtr->nextPtr = NULL;
+ } else {
+ otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
+ halfwayNodePtr->nextPtr = NULL;
+ }
+ RecomputeNodeCounts(nodePtr);
+ RecomputeNodeCounts(otherPtr);
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * RecomputeNodeCounts --
+ *
+ * This procedure is called to recompute all the counts in a node
+ * (tags, child information, etc.) by scanning the information in
+ * its descendants. This procedure is called during rebalancing
+ * when a node's child structure has changed.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * The tag counts for nodePtr are modified to reflect its current
+ * child structure, as are its numChildren and numLines fields.
+ * Also, all of the childrens' parentPtr fields are made to point
+ * to nodePtr.
+ *
+ *----------------------------------------------------------------------
+ */
+
+static void
+RecomputeNodeCounts(nodePtr)
+ register Node *nodePtr; /* Node whose tag summary information
+ * must be recomputed. */
+{
+ register Summary *summaryPtr, *summaryPtr2;
+ register Node *childPtr;
+ register TkTextLine *linePtr;
+ register TkTextSegment *segPtr;
+ TkTextTag *tagPtr;
+
+ /*
+ * Zero out all the existing counts for the node, but don't delete
+ * the existing Summary records (most of them will probably be reused).
+ */
+
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
+ summaryPtr = summaryPtr->nextPtr) {
+ summaryPtr->toggleCount = 0;
+ }
+ nodePtr->numChildren = 0;
+ nodePtr->numLines = 0;
+
+ /*
+ * Scan through the children, adding the childrens' tag counts into
+ * the node's tag counts and adding new Summary structures if
+ * necessary.
+ */
+
+ if (nodePtr->level == 0) {
+ for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
+ linePtr = linePtr->nextPtr) {
+ nodePtr->numChildren++;
+ nodePtr->numLines++;
+ linePtr->parentPtr = nodePtr;
+ for (segPtr = linePtr->segPtr; segPtr != NULL;
+ segPtr = segPtr->nextPtr) {
+ if (((segPtr->typePtr != &tkTextToggleOnType)
+ && (segPtr->typePtr != &tkTextToggleOffType))
+ || !(segPtr->body.toggle.inNodeCounts)) {
+ continue;
+ }
+ tagPtr = segPtr->body.toggle.tagPtr;
+ for (summaryPtr = nodePtr->summaryPtr; ;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr == NULL) {
+ summaryPtr = (Summary *) ckalloc(sizeof(Summary));
+ summaryPtr->tagPtr = tagPtr;
+ summaryPtr->toggleCount = 1;
+ summaryPtr->nextPtr = nodePtr->summaryPtr;
+ nodePtr->summaryPtr = summaryPtr;
+ break;
+ }
+ if (summaryPtr->tagPtr == tagPtr) {
+ summaryPtr->toggleCount++;
+ break;
+ }
+ }
+ }
+ }
+ } else {
+ for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
+ childPtr = childPtr->nextPtr) {
+ nodePtr->numChildren++;
+ nodePtr->numLines += childPtr->numLines;
+ childPtr->parentPtr = nodePtr;
+ for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
+ summaryPtr2 = summaryPtr2->nextPtr) {
+ for (summaryPtr = nodePtr->summaryPtr; ;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr == NULL) {
+ summaryPtr = (Summary *) ckalloc(sizeof(Summary));
+ summaryPtr->tagPtr = summaryPtr2->tagPtr;
+ summaryPtr->toggleCount = summaryPtr2->toggleCount;
+ summaryPtr->nextPtr = nodePtr->summaryPtr;
+ nodePtr->summaryPtr = summaryPtr;
+ break;
+ }
+ if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
+ summaryPtr->toggleCount += summaryPtr2->toggleCount;
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ /*
+ * Scan through the node's tag records again and delete any Summary
+ * records that still have a zero count, or that have all the toggles.
+ * The node with the children that account for all the tags toggles
+ * have no summary information, and they become the tagRootPtr for the tag.
+ */
+
+ summaryPtr2 = NULL;
+ for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
+ if (summaryPtr->toggleCount > 0 &&
+ summaryPtr->toggleCount < summaryPtr->tagPtr->toggleCount) {
+ if (nodePtr->level == summaryPtr->tagPtr->tagRootPtr->level) {
+ /*
+ * The tag's root node split and some toggles left.
+ * The tag root must move up a level.
+ */
+ summaryPtr->tagPtr->tagRootPtr = nodePtr->parentPtr;
+ }
+ summaryPtr2 = summaryPtr;
+ summaryPtr = summaryPtr->nextPtr;
+ continue;
+ }
+ if (summaryPtr->toggleCount == summaryPtr->tagPtr->toggleCount) {
+ /*
+ * A node merge has collected all the toggles under one node.
+ * Push the root down to this level.
+ */
+ summaryPtr->tagPtr->tagRootPtr = nodePtr;
+ }
+ if (summaryPtr2 != NULL) {
+ summaryPtr2->nextPtr = summaryPtr->nextPtr;
+ ckfree((char *) summaryPtr);
+ summaryPtr = summaryPtr2->nextPtr;
+ } else {
+ nodePtr->summaryPtr = summaryPtr->nextPtr;
+ ckfree((char *) summaryPtr);
+ summaryPtr = nodePtr->summaryPtr;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeNumLines --
+ *
+ * This procedure returns a count of the number of lines of
+ * text present in a given B-tree.
+ *
+ * Results:
+ * The return value is a count of the number of usable lines
+ * in tree (i.e. it doesn't include the dummy line that is just
+ * used to mark the end of the tree).
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreeNumLines(tree)
+ TkTextBTree tree; /* Information about tree. */
+{
+ BTree *treePtr = (BTree *) tree;
+ return treePtr->rootPtr->numLines - 1;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * CharSplitProc --
+ *
+ * This procedure implements splitting for character segments.
+ *
+ * Results:
+ * The return value is a pointer to a chain of two segments
+ * that have the same characters as segPtr except split
+ * among the two segments.
+ *
+ * Side effects:
+ * Storage for segPtr is freed.
+ *
+ *--------------------------------------------------------------
+ */
+
+static TkTextSegment *
+CharSplitProc(segPtr, index)
+ TkTextSegment *segPtr; /* Pointer to segment to split. */
+ int index; /* Position within segment at which
+ * to split. */
+{
+ TkTextSegment *newPtr1, *newPtr2;
+
+ newPtr1 = (TkTextSegment *) ckalloc(CSEG_SIZE(index));
+ newPtr2 = (TkTextSegment *) ckalloc(
+ CSEG_SIZE(segPtr->size - index));
+ newPtr1->typePtr = &tkTextCharType;
+ newPtr1->nextPtr = newPtr2;
+ newPtr1->size = index;
+ strncpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index);
+ newPtr1->body.chars[index] = 0;
+ newPtr2->typePtr = &tkTextCharType;
+ newPtr2->nextPtr = segPtr->nextPtr;
+ newPtr2->size = segPtr->size - index;
+ strcpy(newPtr2->body.chars, segPtr->body.chars + index);
+ ckfree((char*) segPtr);
+ return newPtr1;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * CharCleanupProc --
+ *
+ * This procedure merges adjacent character segments into
+ * a single character segment, if possible.
+ *
+ * Results:
+ * The return value is a pointer to the first segment in
+ * the (new) list of segments that used to start with segPtr.
+ *
+ * Side effects:
+ * Storage for the segments may be allocated and freed.
+ *
+ *--------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+static TkTextSegment *
+CharCleanupProc(segPtr, linePtr)
+ TkTextSegment *segPtr; /* Pointer to first of two adjacent
+ * segments to join. */
+ TkTextLine *linePtr; /* Line containing segments (not
+ * used). */
+{
+ TkTextSegment *segPtr2, *newPtr;
+
+ segPtr2 = segPtr->nextPtr;
+ if ((segPtr2 == NULL) || (segPtr2->typePtr != &tkTextCharType)) {
+ return segPtr;
+ }
+ newPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(
+ segPtr->size + segPtr2->size));
+ newPtr->typePtr = &tkTextCharType;
+ newPtr->nextPtr = segPtr2->nextPtr;
+ newPtr->size = segPtr->size + segPtr2->size;
+ strcpy(newPtr->body.chars, segPtr->body.chars);
+ strcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars);
+ ckfree((char*) segPtr);
+ ckfree((char*) segPtr2);
+ return newPtr;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * CharDeleteProc --
+ *
+ * This procedure is invoked to delete a character segment.
+ *
+ * Results:
+ * Always returns 0 to indicate that the segment was deleted.
+ *
+ * Side effects:
+ * Storage for the segment is freed.
+ *
+ *--------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+static int
+CharDeleteProc(segPtr, linePtr, treeGone)
+ TkTextSegment *segPtr; /* Segment to delete. */
+ TkTextLine *linePtr; /* Line containing segment. */
+ int treeGone; /* Non-zero means the entire tree is
+ * being deleted, so everything must
+ * get cleaned up. */
+{
+ ckfree((char*) segPtr);
+ return 0;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * CharCheckProc --
+ *
+ * This procedure is invoked to perform consistency checks
+ * on character segments.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * If the segment isn't inconsistent then the procedure
+ * panics.
+ *
+ *--------------------------------------------------------------
+ */
+
+ /* ARGSUSED */
+static void
+CharCheckProc(segPtr, linePtr)
+ TkTextSegment *segPtr; /* Segment to check. */
+ TkTextLine *linePtr; /* Line containing segment. */
+{
+ /*
+ * Make sure that the segment contains the number of
+ * characters indicated by its header, and that the last
+ * segment in a line ends in a newline. Also make sure
+ * that there aren't ever two character segments adjacent
+ * to each other: they should be merged together.
+ */
+
+ if (segPtr->size <= 0) {
+ panic("CharCheckProc: segment has size <= 0");
+ }
+ if (strlen(segPtr->body.chars) != (size_t) segPtr->size) {
+ panic("CharCheckProc: segment has wrong size");
+ }
+ if (segPtr->nextPtr == NULL) {
+ if (segPtr->body.chars[segPtr->size-1] != '\n') {
+ panic("CharCheckProc: line doesn't end with newline");
+ }
+ } else {
+ if (segPtr->nextPtr->typePtr == &tkTextCharType) {
+ panic("CharCheckProc: adjacent character segments weren't merged");
+ }
+ }
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * ToggleDeleteProc --
+ *
+ * This procedure is invoked to delete toggle segments.
+ *
+ * Results:
+ * Returns 1 to indicate that the segment may not be deleted,
+ * unless the entire B-tree is going away.
+ *
+ * Side effects:
+ * If the tree is going away then the toggle's memory is
+ * freed; otherwise the toggle counts in nodes above the
+ * segment get updated.
+ *
+ *--------------------------------------------------------------
+ */
+
+static int
+ToggleDeleteProc(segPtr, linePtr, treeGone)
+ TkTextSegment *segPtr; /* Segment to check. */
+ TkTextLine *linePtr; /* Line containing segment. */
+ int treeGone; /* Non-zero means the entire tree is
+ * being deleted, so everything must
+ * get cleaned up. */
+{
+ if (treeGone) {
+ ckfree((char *) segPtr);
+ return 0;
+ }
+
+ /*
+ * This toggle is in the middle of a range of characters that's
+ * being deleted. Refuse to die. We'll be moved to the end of
+ * the deleted range and our cleanup procedure will be called
+ * later. Decrement node toggle counts here, and set a flag
+ * so we'll re-increment them in the cleanup procedure.
+ */
+
+ if (segPtr->body.toggle.inNodeCounts) {
+ ChangeNodeToggleCount(linePtr->parentPtr,
+ segPtr->body.toggle.tagPtr, -1);
+ segPtr->body.toggle.inNodeCounts = 0;
+ }
+ return 1;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * ToggleCleanupProc --
+ *
+ * This procedure is called when a toggle is part of a line that's
+ * been modified in some way. It's invoked after the
+ * modifications are complete.
+ *
+ * Results:
+ * The return value is the head segment in a new list
+ * that is to replace the tail of the line that used to
+ * start at segPtr. This allows the procedure to delete
+ * or modify segPtr.
+ *
+ * Side effects:
+ * Toggle counts in the nodes above the new line will be
+ * updated if they're not already. Toggles may be collapsed
+ * if there are duplicate toggles at the same position.
+ *
+ *--------------------------------------------------------------
+ */
+
+static TkTextSegment *
+ToggleCleanupProc(segPtr, linePtr)
+ TkTextSegment *segPtr; /* Segment to check. */
+ TkTextLine *linePtr; /* Line that now contains segment. */
+{
+ TkTextSegment *segPtr2, *prevPtr;
+ int counts;
+
+ /*
+ * If this is a toggle-off segment, look ahead through the next
+ * segments to see if there's a toggle-on segment for the same tag
+ * before any segments with non-zero size. If so then the two
+ * toggles cancel each other; remove them both.
+ */
+
+ if (segPtr->typePtr == &tkTextToggleOffType) {
+ for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr;
+ (segPtr2 != NULL) && (segPtr2->size == 0);
+ prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) {
+ if (segPtr2->typePtr != &tkTextToggleOnType) {
+ continue;
+ }
+ if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) {
+ continue;
+ }
+ counts = segPtr->body.toggle.inNodeCounts
+ + segPtr2->body.toggle.inNodeCounts;
+ if (counts != 0) {
+ ChangeNodeToggleCount(linePtr->parentPtr,
+ segPtr->body.toggle.tagPtr, -counts);
+ }
+ prevPtr->nextPtr = segPtr2->nextPtr;
+ ckfree((char *) segPtr2);
+ segPtr2 = segPtr->nextPtr;
+ ckfree((char *) segPtr);
+ return segPtr2;
+ }
+ }
+
+ if (!segPtr->body.toggle.inNodeCounts) {
+ ChangeNodeToggleCount(linePtr->parentPtr,
+ segPtr->body.toggle.tagPtr, 1);
+ segPtr->body.toggle.inNodeCounts = 1;
+ }
+ return segPtr;
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * ToggleLineChangeProc --
+ *
+ * This procedure is invoked when a toggle segment is about
+ * to move from one line to another.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * Toggle counts are decremented in the nodes above the line.
+ *
+ *--------------------------------------------------------------
+ */
+
+static void
+ToggleLineChangeProc(segPtr, linePtr)
+ TkTextSegment *segPtr; /* Segment to check. */
+ TkTextLine *linePtr; /* Line that used to contain segment. */
+{
+ if (segPtr->body.toggle.inNodeCounts) {
+ ChangeNodeToggleCount(linePtr->parentPtr,
+ segPtr->body.toggle.tagPtr, -1);
+ segPtr->body.toggle.inNodeCounts = 0;
+ }
+}
+
+/*
+ *--------------------------------------------------------------
+ *
+ * ToggleCheckProc --
+ *
+ * This procedure is invoked to perform consistency checks
+ * on toggle segments.
+ *
+ * Results:
+ * None.
+ *
+ * Side effects:
+ * If a consistency problem is found the procedure panics.
+ *
+ *--------------------------------------------------------------
+ */
+
+static void
+ToggleCheckProc(segPtr, linePtr)
+ TkTextSegment *segPtr; /* Segment to check. */
+ TkTextLine *linePtr; /* Line containing segment. */
+{
+ register Summary *summaryPtr;
+ int needSummary;
+
+ if (segPtr->size != 0) {
+ panic("ToggleCheckProc: segment had non-zero size");
+ }
+ if (!segPtr->body.toggle.inNodeCounts) {
+ panic("ToggleCheckProc: toggle counts not updated in nodes");
+ }
+ needSummary = (segPtr->body.toggle.tagPtr->tagRootPtr != linePtr->parentPtr);
+ for (summaryPtr = linePtr->parentPtr->summaryPtr; ;
+ summaryPtr = summaryPtr->nextPtr) {
+ if (summaryPtr == NULL) {
+ if (needSummary) {
+ panic("ToggleCheckProc: tag not present in node");
+ } else {
+ break;
+ }
+ }
+ if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) {
+ if (!needSummary) {
+ panic("ToggleCheckProc: tag present in root node summary");
+ }
+ break;
+ }
+ }
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * TkBTreeCharsInLine --
+ *
+ * This procedure returns a count of the number of characters
+ * in a given line.
+ *
+ * Results:
+ * The return value is the character count for linePtr.
+ *
+ * Side effects:
+ * None.
+ *
+ *----------------------------------------------------------------------
+ */
+
+int
+TkBTreeCharsInLine(linePtr)
+ TkTextLine *linePtr; /* Line whose characters should be
+ * counted. */
+{
+ TkTextSegment *segPtr;
+ int count;
+
+ count = 0;
+ for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
+ count += segPtr->size;
+ }
+ return count;
+}