Initial revision

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;
+}