shared_source/c_tk_base_7_5_w_mods/tktextbtree.c

/* $Header$ */

/* 
 * 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.
 *
 * RCS: @(#) $Id: tktextbtree.c,v 1.1.1.1 2001/06/13 05:09:26 dtashley Exp $
 */

#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->byteIndex, 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->byteIndex = 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->byteIndex = 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.byteIndex -= 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->byteIndex > index2Ptr->byteIndex)) ||
            ((index1Ptr != &index0) && 
                (index1Ptr->byteIndex >= index2Ptr->byteIndex))) {
                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.byteIndex -= 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->byteIndex == 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->byteIndex <= backOne.byteIndex) {
            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.byteIndex += 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.byteIndex = 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.byteIndex = 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 byteIndex;
    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.
         */
        byteIndex = 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.byteIndex = byteIndex;
            }
            if (segPtr == searchPtr->lastPtr) {
                prevPtr = NULL;   /* Segments earlier than last don't count */
                pastLast = 1;
            }
            byteIndex += 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.byteIndex = 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->byteIndex;
            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->byteIndex;
            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;
}

/*
 *----------------------------------------------------------------------
 *
 * TkTextIsElided --
 *
 *      Special case to just return information about elided attribute.
 *      Specialized from TkBTreeGetTags(indexPtr, numTagsPtr)
 *      and GetStyle(textPtr, indexPtr).
 *      Just need to keep track of invisibility settings for each priority,
 *      pick highest one active at end
 *
 * Results:
 *      Returns whether this text should be elided or not.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

        /* ARGSUSED */
int
TkTextIsElided(textPtr, indexPtr)
    TkText *textPtr;            /* Overall information about text widget. */
    TkTextIndex *indexPtr;      /* The character in the text for which
                                 * display information is wanted. */
{
#define LOTSA_TAGS 1000
    int elide = 0;              /* if nobody says otherwise, it's visible */

    int deftagCnts[LOTSA_TAGS];
    int *tagCnts = deftagCnts;
    TkTextTag *deftagPtrs[LOTSA_TAGS];
    TkTextTag **tagPtrs = deftagPtrs;
    int numTags = textPtr->numTags;
    register Node *nodePtr;
    register TkTextLine *siblingLinePtr;
    register TkTextSegment *segPtr;
    register TkTextTag *tagPtr;
    register int i, index;

        /* almost always avoid malloc, so stay out of system calls */
    if (LOTSA_TAGS < numTags) {
        tagCnts = (int *)ckalloc((unsigned)sizeof(int) * numTags);
        tagPtrs = (TkTextTag **)ckalloc((unsigned)sizeof(TkTextTag *) * numTags);
    }
 
    for (i=0; i<numTags; i++) {
        tagCnts[i] = 0;
    }

    /*
     * Record tag toggles within the line of indexPtr but preceding
     * indexPtr.
     */

    for (index = 0, segPtr = indexPtr->linePtr->segPtr;
         (index + segPtr->size) <= indexPtr->byteIndex;
         index += segPtr->size, segPtr = segPtr->nextPtr) {
        if ((segPtr->typePtr == &tkTextToggleOnType)
                || (segPtr->typePtr == &tkTextToggleOffType)) {
            tagPtr = segPtr->body.toggle.tagPtr;
            if (tagPtr->elideString != NULL) {
                tagPtrs[tagPtr->priority] = tagPtr;
                tagCnts[tagPtr->priority]++;
            }
        }
    }

    /*
     * 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)) {
                tagPtr = segPtr->body.toggle.tagPtr;
                if (tagPtr->elideString != NULL) {
                    tagPtrs[tagPtr->priority] = tagPtr;
                    tagCnts[tagPtr->priority]++;
                }
            }
        }
    }

    /*
     * 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) {
                    tagPtr = summaryPtr->tagPtr;
                    if (tagPtr->elideString != NULL) {
                        tagPtrs[tagPtr->priority] = tagPtr;
                        tagCnts[tagPtr->priority] += summaryPtr->toggleCount;
                    }
                }
            }
        }
    }

    /*
     * Now traverse from highest priority to lowest, 
     * take elided value from first odd count (= on)
     */

    for (i = numTags-1; i >=0; i--) {
        if (tagCnts[i] & 1) {
#ifndef ALWAYS_SHOW_SELECTION
            /* who would make the selection elided? */
            if ((tagPtr == textPtr->selTagPtr)
                    && !(textPtr->flags & GOT_FOCUS)) {
                continue;
            }
#endif
            elide = tagPtrs[i]->elide;
            break;
        }
    }

    if (LOTSA_TAGS < numTags) {
        ckfree((char *) tagCnts);
        ckfree((char *) tagPtrs);
    }

    return elide;
}

/*
 *----------------------------------------------------------------------
 *
 * 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) {
        if (segPtr->typePtr == &tkTextCharType) {
            count += Tcl_NumUtfChars(segPtr->body.chars, segPtr->size);
        } else {
            count += segPtr->size;
        }
    }
    return count;
}

int
TkBTreeBytesInLine(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;
}

/* End of tktextbtree.c */