Return to tktxbtre.c CVS log

Up to [Micropolis - Activity] / micropolis / src / tk

Annotation of micropolis/src/tk/tktxbtre.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.