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