ckTextBTree.c

   1 /*
   2  * ckTextBTree.c --
   3  *
   4  *      This file contains code that manages the B-tree representation
   5  *      of text for Ck's text widget and implements character and
   6  *      toggle segment types.
   7  *
   8  * Copyright (c) 1992-1994 The Regents of the University of California.
   9  * Copyright (c) 1994-1995 Sun Microsystems, Inc.
  10  * Copyright (c) 1995 Christian Werner
  11  *
  12  * See the file "license.terms" for information on usage and redistribution
  13  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  14  */
  15
  16 #include "ckPort.h"
  17 #include "ck.h"
  18 #include "ckText.h"
  19
  20 /*
  21  * The data structure below keeps summary information about one tag as part
  22  * of the tag information in a node.
  23  */
  24
  25 typedef struct Summary {
  26     CkTextTag *tagPtr;                  /* Handle for tag. */
  27     int toggleCount;                    /* Number of transitions into or
  28                                          * out of this tag that occur in
  29                                          * the subtree rooted at this node. */
  30     struct Summary *nextPtr;            /* Next in list of all tags for same
  31                                          * node, or NULL if at end of list. */
  32 } Summary;
  33
  34 /*
  35  * The data structure below defines a node in the B-tree.
  36  */
  37
  38 typedef struct Node {
  39     struct Node *parentPtr;             /* Pointer to parent node, or NULL if
  40                                          * this is the root. */
  41     struct Node *nextPtr;               /* Next in list of siblings with the
  42                                          * same parent node, or NULL for end
  43                                          * of list. */
  44     Summary *summaryPtr;                /* First in malloc-ed list of info
  45                                          * about tags in this subtree (NULL if
  46                                          * no tag info in the subtree). */
  47     int level;                          /* Level of this node in the B-tree.
  48                                          * 0 refers to the bottom of the tree
  49                                          * (children are lines, not nodes). */
  50     union {                             /* First in linked list of children. */
  51         struct Node *nodePtr;           /* Used if level > 0. */
  52         CkTextLine *linePtr;            /* Used if level == 0. */
  53     } children;
  54     int numChildren;                    /* Number of children of this node. */
  55     int numLines;                       /* Total number of lines (leaves) in
  56                                          * the subtree rooted here. */
  57 } Node;
  58
  59 /*
  60  * Upper and lower bounds on how many children a node may have:
  61  * rebalance when either of these limits is exceeded.  MAX_CHILDREN
  62  * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
  63  */
  64
  65 #define MAX_CHILDREN 12
  66 #define MIN_CHILDREN 6
  67
  68 /*
  69  * The data structure below defines an entire B-tree.
  70  */
  71
  72 typedef struct BTree {
  73     Node *rootPtr;                      /* Pointer to root of B-tree. */
  74 } BTree;
  75
  76 /*
  77  * The structure below is used to pass information between
  78  * CkBTreeGetTags and IncCount:
  79  */
  80
  81 typedef struct TagInfo {
  82     int numTags;                        /* Number of tags for which there
  83                                          * is currently information in
  84                                          * tags and counts. */
  85     int arraySize;                      /* Number of entries allocated for
  86                                          * tags and counts. */
  87     CkTextTag **tagPtrs;                /* Array of tags seen so far.
  88                                          * Malloc-ed. */
  89     int *counts;                        /* Toggle count (so far) for each
  90                                          * entry in tags.  Malloc-ed. */
  91 } TagInfo;
  92
  93 /*
  94  * Variable that indicates whether to enable consistency checks for
  95  * debugging.
  96  */
  97
  98 int ckBTreeDebug = 0;
  99
 100 /*
 101  * Macros that determine how much space to allocate for new segments:
 102  */
 103
 104 #define CSEG_SIZE(chars) ((unsigned) (Ck_Offset(CkTextSegment, body) \
 105         + 1 + (chars)))
 106 #define TSEG_SIZE ((unsigned) (Ck_Offset(CkTextSegment, body) \
 107         + sizeof(CkTextToggle)))
 108
 109 /*
 110  * Forward declarations for procedures defined in this file:
 111  */
 112
 113 static void             ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
 114                             CkTextTag *tagPtr, int delta));
 115 static void             CharCheckProc _ANSI_ARGS_((CkTextSegment *segPtr,
 116                             CkTextLine *linePtr));
 117 static int              CharDeleteProc _ANSI_ARGS_((CkTextSegment *segPtr,
 118                             CkTextLine *linePtr, int treeGone));
 119 static CkTextSegment *  CharCleanupProc _ANSI_ARGS_((CkTextSegment *segPtr,
 120                             CkTextLine *linePtr));
 121 static CkTextSegment *  CharSplitProc _ANSI_ARGS_((CkTextSegment *segPtr,
 122                             int index));
 123 static void             CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
 124 static void             CleanupLine _ANSI_ARGS_((CkTextLine *linePtr));
 125 static void             DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
 126 static void             DestroyNode _ANSI_ARGS_((Node *nodePtr));
 127 static void             IncCount _ANSI_ARGS_((CkTextTag *tagPtr, int inc,
 128                             TagInfo *tagInfoPtr));
 129 static void             Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
 130 static void             RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
 131 static CkTextSegment *  SplitSeg _ANSI_ARGS_((CkTextIndex *indexPtr));
 132 static void             ToggleCheckProc _ANSI_ARGS_((CkTextSegment *segPtr,
 133                             CkTextLine *linePtr));
 134 static CkTextSegment *  ToggleCleanupProc _ANSI_ARGS_((CkTextSegment *segPtr,
 135                             CkTextLine *linePtr));
 136 static int              ToggleDeleteProc _ANSI_ARGS_((CkTextSegment *segPtr,
 137                             CkTextLine *linePtr, int treeGone));
 138 static void             ToggleLineChangeProc _ANSI_ARGS_((CkTextSegment *segPtr,
 139                             CkTextLine *linePtr));
 140
 141 /*
 142  * Type record for character segments:
 143  */
 144
 145 Ck_SegType ckTextCharType = {
 146     "character",                                /* name */
 147     0,                                          /* leftGravity */
 148     CharSplitProc,                              /* splitProc */
 149     CharDeleteProc,                             /* deleteProc */
 150     CharCleanupProc,                            /* cleanupProc */
 151     (Ck_SegLineChangeProc *) NULL,              /* lineChangeProc */
 152     CkTextCharLayoutProc,                       /* layoutProc */
 153     CharCheckProc                               /* checkProc */
 154 };
 155
 156 /*
 157  * Type record for segments marking the beginning of a tagged
 158  * range:
 159  */
 160
 161 Ck_SegType ckTextToggleOnType = {
 162     "toggleOn",                                 /* name */
 163     0,                                          /* leftGravity */
 164     (Ck_SegSplitProc *) NULL,                   /* splitProc */
 165     ToggleDeleteProc,                           /* deleteProc */
 166     ToggleCleanupProc,                          /* cleanupProc */
 167     ToggleLineChangeProc,                       /* lineChangeProc */
 168     (Ck_SegLayoutProc *) NULL,                  /* layoutProc */
 169     ToggleCheckProc                             /* checkProc */
 170 };
 171
 172 /*
 173  * Type record for segments marking the end of a tagged
 174  * range:
 175  */
 176
 177 Ck_SegType ckTextToggleOffType = {
 178     "toggleOff",                                /* name */
 179     1,                                          /* leftGravity */
 180     (Ck_SegSplitProc *) NULL,                   /* splitProc */
 181     ToggleDeleteProc,                           /* deleteProc */
 182     ToggleCleanupProc,                          /* cleanupProc */
 183     ToggleLineChangeProc,                       /* lineChangeProc */
 184     (Ck_SegLayoutProc *) NULL,                  /* layoutProc */
 185     ToggleCheckProc                             /* checkProc */
 186 };
 187 \f
 188 /*
 189  *----------------------------------------------------------------------
 190  *
 191  * CkBTreeCreate --
 192  *
 193  *      This procedure is called to create a new text B-tree.
 194  *
 195  * Results:
 196  *      The return value is a pointer to a new B-tree containing
 197  *      one line with nothing but a newline character.
 198  *
 199  * Side effects:
 200  *      Memory is allocated and initialized.
 201  *
 202  *----------------------------------------------------------------------
 203  */
 204
 205 CkTextBTree
 206 CkBTreeCreate()
 207 {
 208     register BTree *treePtr;
 209     register Node *rootPtr;
 210     register CkTextLine *linePtr, *linePtr2;
 211     register CkTextSegment *segPtr;
 212
 213     /*
 214      * The tree will initially have two empty lines.  The second line
 215      * isn't actually part of the tree's contents, but its presence
 216      * makes several operations easier.  The tree will have one node,
 217      * which is also the root of the tree.
 218      */
 219
 220     rootPtr = (Node *) ckalloc(sizeof(Node));
 221     linePtr = (CkTextLine *) ckalloc(sizeof(CkTextLine));
 222     linePtr2 = (CkTextLine *) ckalloc(sizeof(CkTextLine));
 223     rootPtr->parentPtr = NULL;
 224     rootPtr->nextPtr = NULL;
 225     rootPtr->summaryPtr = NULL;
 226     rootPtr->level = 0;
 227     rootPtr->children.linePtr = linePtr;
 228     rootPtr->numChildren = 2;
 229     rootPtr->numLines = 2;
 230
 231     linePtr->parentPtr = rootPtr;
 232     linePtr->nextPtr = linePtr2;
 233     segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(1));
 234     linePtr->segPtr = segPtr;
 235     segPtr->typePtr = &ckTextCharType;
 236     segPtr->nextPtr = NULL;
 237     segPtr->size = 1;
 238     segPtr->body.chars[0] = '\n';
 239     segPtr->body.chars[1] = 0;
 240
 241     linePtr2->parentPtr = rootPtr;
 242     linePtr2->nextPtr = NULL;
 243     segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(1));
 244     linePtr2->segPtr = segPtr;
 245     segPtr->typePtr = &ckTextCharType;
 246     segPtr->nextPtr = NULL;
 247     segPtr->size = 1;
 248     segPtr->body.chars[0] = '\n';
 249     segPtr->body.chars[1] = 0;
 250
 251     treePtr = (BTree *) ckalloc(sizeof(BTree));
 252     treePtr->rootPtr = rootPtr;
 253
 254     return (CkTextBTree) treePtr;
 255 }
 256 \f
 257 /*
 258  *----------------------------------------------------------------------
 259  *
 260  * CkBTreeDestroy --
 261  *
 262  *      Delete a B-tree, recycling all of the storage it contains.
 263  *
 264  * Results:
 265  *      The tree given by treePtr is deleted.  TreePtr should never
 266  *      again be used.
 267  *
 268  * Side effects:
 269  *      Memory is freed.
 270  *
 271  *----------------------------------------------------------------------
 272  */
 273
 274 void
 275 CkBTreeDestroy(tree)
 276     CkTextBTree tree;                   /* Pointer to tree to delete. */
 277 {
 278     BTree *treePtr = (BTree *) tree;
 279
 280     DestroyNode(treePtr->rootPtr);
 281     ckfree((char *) treePtr);
 282 }
 283 \f
 284 /*
 285  *----------------------------------------------------------------------
 286  *
 287  * DestroyNode --
 288  *
 289  *      This is a recursive utility procedure used during the deletion
 290  *      of a B-tree.
 291  *
 292  * Results:
 293  *      None.
 294  *
 295  * Side effects:
 296  *      All the storage for nodePtr and its descendants is freed.
 297  *
 298  *----------------------------------------------------------------------
 299  */
 300
 301 static void
 302 DestroyNode(nodePtr)
 303     register Node *nodePtr;
 304 {
 305     if (nodePtr->level == 0) {
 306         CkTextLine *linePtr;
 307         CkTextSegment *segPtr;
 308
 309         while (nodePtr->children.linePtr != NULL) {
 310             linePtr = nodePtr->children.linePtr;
 311             nodePtr->children.linePtr = linePtr->nextPtr;
 312             while (linePtr->segPtr != NULL) {
 313                 segPtr = linePtr->segPtr;
 314                 linePtr->segPtr = segPtr->nextPtr;
 315                 (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
 316             }
 317             ckfree((char *) linePtr);
 318         }
 319     } else {
 320         register Node *childPtr;
 321
 322         while (nodePtr->children.nodePtr != NULL) {
 323             childPtr = nodePtr->children.nodePtr;
 324             nodePtr->children.nodePtr = childPtr->nextPtr;
 325             DestroyNode(childPtr);
 326         }
 327     }
 328     DeleteSummaries(nodePtr->summaryPtr);
 329     ckfree((char *) nodePtr);
 330 }
 331 \f
 332 /*
 333  *----------------------------------------------------------------------
 334  *
 335  * DeleteSummaries --
 336  *
 337  *      Free up all of the memory in a list of tag summaries associated
 338  *      with a node.
 339  *
 340  * Results:
 341  *      None.
 342  *
 343  * Side effects:
 344  *      Storage is released.
 345  *
 346  *----------------------------------------------------------------------
 347  */
 348
 349 static void
 350 DeleteSummaries(summaryPtr)
 351     register Summary *summaryPtr;       /* First in list of node's tag
 352                                          * summaries. */
 353 {
 354     register Summary *nextPtr;
 355     while (summaryPtr != NULL) {
 356         nextPtr = summaryPtr->nextPtr;
 357         ckfree((char *) summaryPtr);
 358         summaryPtr = nextPtr;
 359     }
 360 }
 361 \f
 362 /*
 363  *----------------------------------------------------------------------
 364  *
 365  * CkBTreeInsertChars --
 366  *
 367  *      Insert characters at a given position in a B-tree.
 368  *
 369  * Results:
 370  *      None.
 371  *
 372  * Side effects:
 373  *      Characters are added to the B-tree at the given position.
 374  *      If the string contains newlines, new lines will be added,
 375  *      which could cause the structure of the B-tree to change.
 376  *
 377  *----------------------------------------------------------------------
 378  */
 379
 380 void
 381 CkBTreeInsertChars(indexPtr, string)
 382     register CkTextIndex *indexPtr;     /* Indicates where to insert text.
 383                                          * When the procedure returns, this
 384                                          * index is no longer valid because
 385                                          * of changes to the segment
 386                                          * structure. */
 387     char *string;                       /* Pointer to bytes to insert (may
 388                                          * contain newlines, must be null-
 389                                          * terminated). */
 390 {
 391     register Node *nodePtr;
 392     register CkTextSegment *prevPtr;    /* The segment just before the first
 393                                          * new segment (NULL means new segment
 394                                          * is at beginning of line). */
 395     CkTextSegment *curPtr;              /* Current segment;  new characters
 396                                          * are inserted just after this one.
 397                                          * NULL means insert at beginning of
 398                                          * line. */
 399     CkTextLine *linePtr;                /* Current line (new segments are
 400                                          * added to this line). */
 401     register CkTextSegment *segPtr;
 402     CkTextLine *newLinePtr;
 403     int chunkSize;                      /* # characters in current chunk. */
 404     register char *eol;                 /* Pointer to character just after last
 405                                          * one in current chunk. */
 406     int changeToLineCount;              /* Counts change to total number of
 407                                          * lines in file. */
 408
 409     prevPtr = SplitSeg(indexPtr);
 410     linePtr = indexPtr->linePtr;
 411     curPtr = prevPtr;
 412
 413     /*
 414      * Chop the string up into lines and create a new segment for
 415      * each line, plus a new line for the leftovers from the
 416      * previous line.
 417      */
 418
 419     changeToLineCount = 0;
 420     while (*string != 0) {
 421         for (eol = string; *eol != 0; eol++) {
 422             if (*eol == '\n') {
 423                 eol++;
 424                 break;
 425             }
 426         }
 427         chunkSize = eol-string;
 428         segPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
 429         segPtr->typePtr = &ckTextCharType;
 430         if (curPtr == NULL) {
 431             segPtr->nextPtr = linePtr->segPtr;
 432             linePtr->segPtr = segPtr;
 433         } else {
 434             segPtr->nextPtr = curPtr->nextPtr;
 435             curPtr->nextPtr = segPtr;
 436         }
 437         segPtr->size = chunkSize;
 438         strncpy(segPtr->body.chars, string, (size_t) chunkSize);
 439         segPtr->body.chars[chunkSize] = 0;
 440         curPtr = segPtr;
 441
 442         if (eol[-1] != '\n') {
 443             break;
 444         }
 445
 446         /*
 447          * The chunk ended with a newline, so create a new CkTextLine
 448          * and move the remainder of the old line to it.
 449          */
 450
 451         newLinePtr = (CkTextLine *) ckalloc(sizeof(CkTextLine));
 452         newLinePtr->parentPtr = linePtr->parentPtr;
 453         newLinePtr->nextPtr = linePtr->nextPtr;
 454         linePtr->nextPtr = newLinePtr;
 455         newLinePtr->segPtr = segPtr->nextPtr;
 456         segPtr->nextPtr = NULL;
 457         linePtr = newLinePtr;
 458         curPtr = NULL;
 459         changeToLineCount++;
 460
 461         string = eol;
 462     }
 463
 464     /*
 465      * Cleanup the starting line for the insertion, plus the ending
 466      * line if it's different.
 467      */
 468
 469     CleanupLine(indexPtr->linePtr);
 470     if (linePtr != indexPtr->linePtr) {
 471         CleanupLine(linePtr);
 472     }
 473
 474     /*
 475      * Increment the line counts in all the parent nodes of the insertion
 476      * point, then rebalance the tree if necessary.
 477      */
 478
 479     for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
 480             nodePtr = nodePtr->parentPtr) {
 481         nodePtr->numLines += changeToLineCount;
 482     }
 483     nodePtr = linePtr->parentPtr;
 484     nodePtr->numChildren += changeToLineCount;
 485     if (nodePtr->numChildren > MAX_CHILDREN) {
 486         Rebalance((BTree *) indexPtr->tree, nodePtr);
 487     }
 488
 489     if (ckBTreeDebug) {
 490         CkBTreeCheck(indexPtr->tree);
 491     }
 492 }
 493 \f
 494 /*
 495  *--------------------------------------------------------------
 496  *
 497  * SplitSeg --
 498  *
 499  *      This procedure is called before adding or deleting
 500  *      segments.  It does three things: (a) it finds the segment
 501  *      containing indexPtr;  (b) if there are several such
 502  *      segments (because some segments have zero length) then
 503  *      it picks the first segment that does not have left
 504  *      gravity;  (c) if the index refers to the middle of
 505  *      a segment then it splits the segment so that the
 506  *      index now refers to the beginning of a segment.
 507  *
 508  * Results:
 509  *      The return value is a pointer to the segment just
 510  *      before the segment corresponding to indexPtr (as
 511  *      described above).  If the segment corresponding to
 512  *      indexPtr is the first in its line then the return
 513  *      value is NULL.
 514  *
 515  * Side effects:
 516  *      The segment referred to by indexPtr is split unless
 517  *      indexPtr refers to its first character.
 518  *
 519  *--------------------------------------------------------------
 520  */
 521
 522 static CkTextSegment *
 523 SplitSeg(indexPtr)
 524     CkTextIndex *indexPtr;              /* Index identifying position
 525                                          * at which to split a segment. */
 526 {
 527     CkTextSegment *prevPtr, *segPtr;
 528     int count;
 529
 530     for (count = indexPtr->charIndex, prevPtr = NULL,
 531             segPtr = indexPtr->linePtr->segPtr; segPtr != NULL;
 532             count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) {
 533         if (segPtr->size > count) {
 534             if (count == 0) {
 535                 return prevPtr;
 536             }
 537             segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
 538             if (prevPtr == NULL) {
 539                 indexPtr->linePtr->segPtr = segPtr;
 540             } else {
 541                 prevPtr->nextPtr = segPtr;
 542             }
 543             return segPtr;
 544         } else if ((segPtr->size == 0) && (count == 0)
 545                 && !segPtr->typePtr->leftGravity) {
 546             return prevPtr;
 547         }
 548     }
 549     panic("SplitSeg reached end of line!");
 550     return NULL;
 551 }
 552 \f
 553 /*
 554  *--------------------------------------------------------------
 555  *
 556  * CleanupLine --
 557  *
 558  *      This procedure is called after modifications have been
 559  *      made to a line.  It scans over all of the segments in
 560  *      the line, giving each a chance to clean itself up, e.g.
 561  *      by merging with the following segments, updating internal
 562  *      information, etc.
 563  *
 564  * Results:
 565  *      None.
 566  *
 567  * Side effects:
 568  *      Depends on what the segment-specific cleanup procedures do.
 569  *
 570  *--------------------------------------------------------------
 571  */
 572
 573 static void
 574 CleanupLine(linePtr)
 575     CkTextLine *linePtr;                /* Line to be cleaned up. */
 576 {
 577     CkTextSegment *segPtr, **prevPtrPtr;
 578     int anyChanges;
 579
 580     /*
 581      * Make a pass over all of the segments in the line, giving each
 582      * a chance to clean itself up.  This could potentially change
 583      * the structure of the line, e.g. by merging two segments
 584      * together or having two segments cancel themselves;  if so,
 585      * then repeat the whole process again, since the first structure
 586      * change might make other structure changes possible.  Repeat
 587      * until eventually there are no changes.
 588      */
 589
 590     while (1) {
 591         anyChanges = 0;
 592         for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
 593                 segPtr != NULL;
 594                 prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
 595             if (segPtr->typePtr->cleanupProc != NULL) {
 596                 *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
 597                 if (segPtr != *prevPtrPtr) {
 598                     anyChanges = 1;
 599                 }
 600             }
 601         }
 602         if (!anyChanges) {
 603             break;
 604         }
 605     }
 606 }
 607 \f
 608 /*
 609  *----------------------------------------------------------------------
 610  *
 611  * CkBTreeDeleteChars --
 612  *
 613  *      Delete a range of characters from a B-tree.  The caller
 614  *      must make sure that the final newline of the B-tree is
 615  *      never deleted.
 616  *
 617  * Results:
 618  *      None.
 619  *
 620  * Side effects:
 621  *      Information is deleted from the B-tree.  This can cause the
 622  *      internal structure of the B-tree to change.  Note: because
 623  *      of changes to the B-tree structure, the indices pointed
 624  *      to by index1Ptr and index2Ptr should not be used after this
 625  *      procedure returns.
 626  *
 627  *----------------------------------------------------------------------
 628  */
 629
 630 void
 631 CkBTreeDeleteChars(index1Ptr, index2Ptr)
 632     register CkTextIndex *index1Ptr;    /* Indicates first character that is
 633                                          * to be deleted. */
 634     register CkTextIndex *index2Ptr;    /* Indicates character just after the
 635                                          * last one that is to be deleted. */
 636 {
 637     CkTextSegment *prevPtr;             /* The segment just before the start
 638                                          * of the deletion range. */
 639     CkTextSegment *lastPtr;             /* The segment just after the end
 640                                          * of the deletion range. */
 641     CkTextSegment *segPtr, *nextPtr;
 642     CkTextLine *curLinePtr;
 643     Node *curNodePtr, *nodePtr;
 644
 645     /*
 646      * Tricky point:  split at index2Ptr first;  otherwise the split
 647      * at index2Ptr may invalidate segPtr and/or prevPtr.
 648      */
 649
 650     lastPtr = SplitSeg(index2Ptr);
 651     if (lastPtr != NULL) {
 652         lastPtr = lastPtr->nextPtr;
 653     }  else {
 654         lastPtr = index2Ptr->linePtr->segPtr;
 655     }
 656     prevPtr = SplitSeg(index1Ptr);
 657     if (prevPtr != NULL) {
 658         segPtr = prevPtr->nextPtr;
 659         prevPtr->nextPtr = lastPtr;
 660     } else {
 661         segPtr = index1Ptr->linePtr->segPtr;
 662         index1Ptr->linePtr->segPtr = lastPtr;
 663     }
 664
 665     /*
 666      * Delete all of the segments between prevPtr and lastPtr.
 667      */
 668
 669     curLinePtr = index1Ptr->linePtr;
 670     curNodePtr = curLinePtr->parentPtr;
 671     while (segPtr != lastPtr) {
 672         if (segPtr == NULL) {
 673             CkTextLine *nextLinePtr;
 674
 675             /*
 676              * We just ran off the end of a line.  First find the
 677              * next line, then go back to the old line and delete it
 678              * (unless it's the starting line for the range).
 679              */
 680
 681             nextLinePtr = CkBTreeNextLine(curLinePtr);
 682             if (curLinePtr != index1Ptr->linePtr) {
 683                 if (curNodePtr == index1Ptr->linePtr->parentPtr) {
 684                     index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
 685                 } else {
 686                     curNodePtr->children.linePtr = curLinePtr->nextPtr;
 687                 }
 688                 for (nodePtr = curNodePtr; nodePtr != NULL;
 689                         nodePtr = nodePtr->parentPtr) {
 690                     nodePtr->numLines--;
 691                 }
 692                 curNodePtr->numChildren--;
 693                 ckfree((char *) curLinePtr);
 694             }
 695             curLinePtr = nextLinePtr;
 696             segPtr = curLinePtr->segPtr;
 697
 698             /*
 699              * If the node is empty then delete it and its parents,
 700              * recursively upwards until a non-empty node is found.
 701              */
 702
 703             while (curNodePtr->numChildren == 0) {
 704                 Node *parentPtr;
 705
 706                 parentPtr = curNodePtr->parentPtr;
 707                 if (parentPtr->children.nodePtr == curNodePtr) {
 708                     parentPtr->children.nodePtr = curNodePtr->nextPtr;
 709                 } else {
 710                     Node *prevNodePtr = parentPtr->children.nodePtr;
 711                     while (prevNodePtr->nextPtr != curNodePtr) {
 712                         prevNodePtr = prevNodePtr->nextPtr;
 713                     }
 714                     prevNodePtr->nextPtr = curNodePtr->nextPtr;
 715                 }
 716                 parentPtr->numChildren--;
 717                 ckfree((char *) curNodePtr);
 718                 curNodePtr = parentPtr;
 719             }
 720             curNodePtr = curLinePtr->parentPtr;
 721             continue;
 722         }
 723
 724         nextPtr = segPtr->nextPtr;
 725         if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
 726             /*
 727              * This segment refuses to die.  Move it to prevPtr and
 728              * advance prevPtr if the segment has left gravity.
 729              */
 730
 731             if (prevPtr == NULL) {
 732                 segPtr->nextPtr = index1Ptr->linePtr->segPtr;
 733                 index1Ptr->linePtr->segPtr = segPtr;
 734             } else {
 735                 segPtr->nextPtr = prevPtr->nextPtr;
 736                 prevPtr->nextPtr = segPtr;
 737             }
 738             if (segPtr->typePtr->leftGravity) {
 739                 prevPtr = segPtr;
 740             }
 741         }
 742         segPtr = nextPtr;
 743     }
 744
 745     /*
 746      * If the beginning and end of the deletion range are in different
 747      * lines, join the two lines together and discard the ending line.
 748      */
 749
 750     if (index1Ptr->linePtr != index2Ptr->linePtr) {
 751         CkTextLine *prevLinePtr;
 752
 753         for (segPtr = lastPtr; segPtr != NULL;
 754                 segPtr = segPtr->nextPtr) {
 755             if (segPtr->typePtr->lineChangeProc != NULL) {
 756                 (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
 757             }
 758         }
 759         curNodePtr = index2Ptr->linePtr->parentPtr;
 760         for (nodePtr = curNodePtr; nodePtr != NULL;
 761                 nodePtr = nodePtr->parentPtr) {
 762             nodePtr->numLines--;
 763         }
 764         curNodePtr->numChildren--;
 765         prevLinePtr = curNodePtr->children.linePtr;
 766         if (prevLinePtr == index2Ptr->linePtr) {
 767             curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
 768         } else {
 769             while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
 770                 prevLinePtr = prevLinePtr->nextPtr;
 771             }
 772             prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
 773         }
 774         ckfree((char *) index2Ptr->linePtr);
 775         Rebalance((BTree *) index2Ptr->tree, curNodePtr);
 776     }
 777
 778     /*
 779      * Cleanup the segments in the new line.
 780      */
 781
 782     CleanupLine(index1Ptr->linePtr);
 783
 784     /*
 785      * Lastly, rebalance the first node of the range.
 786      */
 787
 788     Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
 789     if (ckBTreeDebug) {
 790         CkBTreeCheck(index1Ptr->tree);
 791     }
 792 }
 793 \f
 794 /*
 795  *----------------------------------------------------------------------
 796  *
 797  * CkBTreeFindLine --
 798  *
 799  *      Find a particular line in a B-tree based on its line number.
 800  *
 801  * Results:
 802  *      The return value is a pointer to the line structure for the
 803  *      line whose index is "line", or NULL if no such line exists.
 804  *
 805  * Side effects:
 806  *      None.
 807  *
 808  *----------------------------------------------------------------------
 809  */
 810
 811 CkTextLine *
 812 CkBTreeFindLine(tree, line)
 813     CkTextBTree tree;                   /* B-tree in which to find line. */
 814     int line;                           /* Index of desired line. */
 815 {
 816     BTree *treePtr = (BTree *) tree;
 817     register Node *nodePtr;
 818     register CkTextLine *linePtr;
 819     int linesLeft;
 820
 821     nodePtr = treePtr->rootPtr;
 822     linesLeft = line;
 823     if ((line < 0) || (line >= nodePtr->numLines)) {
 824         return NULL;
 825     }
 826
 827     /*
 828      * Work down through levels of the tree until a node is found at
 829      * level 0.
 830      */
 831
 832     while (nodePtr->level != 0) {
 833         for (nodePtr = nodePtr->children.nodePtr;
 834                 nodePtr->numLines <= linesLeft;
 835                 nodePtr = nodePtr->nextPtr) {
 836             if (nodePtr == NULL) {
 837                 panic("CkBTreeFindLine ran out of nodes");
 838             }
 839             linesLeft -= nodePtr->numLines;
 840         }
 841     }
 842
 843     /*
 844      * Work through the lines attached to the level-0 node.
 845      */
 846
 847     for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
 848             linePtr = linePtr->nextPtr) {
 849         if (linePtr == NULL) {
 850             panic("CkBTreeFindLine ran out of lines");
 851         }
 852         linesLeft -= 1;
 853     }
 854     return linePtr;
 855 }
 856 \f
 857 /*
 858  *----------------------------------------------------------------------
 859  *
 860  * CkBTreeNextLine --
 861  *
 862  *      Given an existing line in a B-tree, this procedure locates the
 863  *      next line in the B-tree.  This procedure is used for scanning
 864  *      through the B-tree.
 865  *
 866  * Results:
 867  *      The return value is a pointer to the line that immediately
 868  *      follows linePtr, or NULL if there is no such line.
 869  *
 870  * Side effects:
 871  *      None.
 872  *
 873  *----------------------------------------------------------------------
 874  */
 875
 876 CkTextLine *
 877 CkBTreeNextLine(linePtr)
 878     register CkTextLine *linePtr;       /* Pointer to existing line in
 879                                          * B-tree. */
 880 {
 881     register Node *nodePtr;
 882
 883     if (linePtr->nextPtr != NULL) {
 884         return linePtr->nextPtr;
 885     }
 886
 887     /*
 888      * This was the last line associated with the particular parent node.
 889      * Search up the tree for the next node, then search down from that
 890      * node to find the first line,
 891      */
 892
 893     for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
 894         if (nodePtr->nextPtr != NULL) {
 895             nodePtr = nodePtr->nextPtr;
 896             break;
 897         }
 898         if (nodePtr->parentPtr == NULL) {
 899             return (CkTextLine *) NULL;
 900         }
 901     }
 902     while (nodePtr->level > 0) {
 903         nodePtr = nodePtr->children.nodePtr;
 904     }
 905     return nodePtr->children.linePtr;
 906 }
 907 \f
 908 /*
 909  *----------------------------------------------------------------------
 910  *
 911  * CkBTreeLineIndex --
 912  *
 913  *      Given a pointer to a line in a B-tree, return the numerical
 914  *      index of that line.
 915  *
 916  * Results:
 917  *      The result is the index of linePtr within the tree, where 0
 918  *      corresponds to the first line in the tree.
 919  *
 920  * Side effects:
 921  *      None.
 922  *
 923  *----------------------------------------------------------------------
 924  */
 925
 926 int
 927 CkBTreeLineIndex(linePtr)
 928     CkTextLine *linePtr;                /* Pointer to existing line in
 929                                          * B-tree. */
 930 {
 931     register CkTextLine *linePtr2;
 932     register Node *nodePtr, *parentPtr, *nodePtr2;
 933     int index;
 934
 935     /*
 936      * First count how many lines precede this one in its level-0
 937      * node.
 938      */
 939
 940     nodePtr = linePtr->parentPtr;
 941     index = 0;
 942     for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
 943             linePtr2 = linePtr2->nextPtr) {
 944         if (linePtr2 == NULL) {
 945             panic("CkBTreeLineIndex couldn't find line");
 946         }
 947         index += 1;
 948     }
 949
 950     /*
 951      * Now work up through the levels of the tree one at a time,
 952      * counting how many lines are in nodes preceding the current
 953      * node.
 954      */
 955
 956     for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
 957             nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
 958         for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
 959                 nodePtr2 = nodePtr2->nextPtr) {
 960             if (nodePtr2 == NULL) {
 961                 panic("CkBTreeLineIndex couldn't find node");
 962             }
 963             index += nodePtr2->numLines;
 964         }
 965     }
 966     return index;
 967 }
 968 \f
 969 /*
 970  *----------------------------------------------------------------------
 971  *
 972  * CkBTreeLinkSegment --
 973  *
 974  *      This procedure adds a new segment to a B-tree at a given
 975  *      location.
 976  *
 977  * Results:
 978  *      None.
 979  *
 980  * Side effects:
 981  *      SegPtr will be linked into its tree.
 982  *
 983  *----------------------------------------------------------------------
 984  */
 985
 986         /* ARGSUSED */
 987 void
 988 CkBTreeLinkSegment(segPtr, indexPtr)
 989     CkTextSegment *segPtr;      /* Pointer to new segment to be added to
 990                                  * B-tree.  Should be completely initialized
 991                                  * by caller except for nextPtr field. */
 992     CkTextIndex *indexPtr;      /* Where to add segment:  it gets linked
 993                                  * in just before the segment indicated
 994                                  * here. */
 995 {
 996     register CkTextSegment *prevPtr;
 997
 998     prevPtr = SplitSeg(indexPtr);
 999     if (prevPtr == NULL) {
1000         segPtr->nextPtr = indexPtr->linePtr->segPtr;
1001         indexPtr->linePtr->segPtr = segPtr;
1002     } else {
1003         segPtr->nextPtr = prevPtr->nextPtr;
1004         prevPtr->nextPtr = segPtr;
1005     }
1006     CleanupLine(indexPtr->linePtr);
1007     if (ckBTreeDebug) {
1008         CkBTreeCheck(indexPtr->tree);
1009     }
1010 }
1011 \f
1012 /*
1013  *----------------------------------------------------------------------
1014  *
1015  * CkBTreeUnlinkSegment --
1016  *
1017  *      This procedure unlinks a segment from its line in a B-tree.
1018  *
1019  * Results:
1020  *      None.
1021  *
1022  * Side effects:
1023  *      SegPtr will be unlinked from linePtr.  The segment itself
1024  *      isn't modified by this procedure.
1025  *
1026  *----------------------------------------------------------------------
1027  */
1028
1029         /* ARGSUSED */
1030 void
1031 CkBTreeUnlinkSegment(tree, segPtr, linePtr)
1032     CkTextBTree tree;                   /* Tree containing segment. */
1033     CkTextSegment *segPtr;              /* Segment to be unlinked. */
1034     CkTextLine *linePtr;                /* Line that currently contains
1035                                          * segment. */
1036 {
1037     register CkTextSegment *prevPtr;
1038
1039     if (linePtr->segPtr == segPtr) {
1040         linePtr->segPtr = segPtr->nextPtr;
1041     } else {
1042         for (prevPtr = linePtr->segPtr; prevPtr->nextPtr != segPtr;
1043                 prevPtr = prevPtr->nextPtr) {
1044             /* Empty loop body. */
1045         }
1046         prevPtr->nextPtr = segPtr->nextPtr;
1047     }
1048     CleanupLine(linePtr);
1049 }
1050 \f
1051 /*
1052  *----------------------------------------------------------------------
1053  *
1054  * CkBTreeTag --
1055  *
1056  *      Turn a given tag on or off for a given range of characters in
1057  *      a B-tree of text.
1058  *
1059  * Results:
1060  *      None.
1061  *
1062  * Side effects:
1063  *      The given tag is added to the given range of characters
1064  *      in the tree or removed from all those characters, depending
1065  *      on the "add" argument.  The structure of the btree is modified
1066  *      enough that index1Ptr and index2Ptr are no longer valid after
1067  *      this procedure returns, and the indexes may be modified by
1068  *      this procedure.
1069  *
1070  *----------------------------------------------------------------------
1071  */
1072
1073 void
1074 CkBTreeTag(index1Ptr, index2Ptr, tagPtr, add)
1075     register CkTextIndex *index1Ptr;    /* Indicates first character in
1076                                          * range. */
1077     register CkTextIndex *index2Ptr;    /* Indicates character just after the
1078                                          * last one in range. */
1079     CkTextTag *tagPtr;                  /* Tag to add or remove. */
1080     int add;                            /* One means add tag to the given
1081                                          * range of characters;  zero means
1082                                          * remove the tag from the range. */
1083 {
1084     CkTextSegment *segPtr, *prevPtr;
1085     CkTextSearch search;
1086     CkTextLine *cleanupLinePtr;
1087     int oldState;
1088
1089     /*
1090      * See whether the tag is present at the start of the range.  If
1091      * the state doesn't already match what we want then add a toggle
1092      * there.
1093      */
1094
1095     oldState = CkBTreeCharTagged(index1Ptr, tagPtr);
1096     if ((add != 0) ^ oldState) {
1097         segPtr = (CkTextSegment *) ckalloc(TSEG_SIZE);
1098         segPtr->typePtr = (add) ? &ckTextToggleOnType : &ckTextToggleOffType;
1099         prevPtr = SplitSeg(index1Ptr);
1100         if (prevPtr == NULL) {
1101             segPtr->nextPtr = index1Ptr->linePtr->segPtr;
1102             index1Ptr->linePtr->segPtr = segPtr;
1103         } else {
1104             segPtr->nextPtr = prevPtr->nextPtr;
1105             prevPtr->nextPtr = segPtr;
1106         }
1107         segPtr->size = 0;
1108         segPtr->body.toggle.tagPtr = tagPtr;
1109         segPtr->body.toggle.inNodeCounts = 0;
1110     }
1111
1112     /*
1113      * Scan the range of characters and delete any internal tag
1114      * transitions.  Keep track of what the old state was at the end
1115      * of the range, and add a toggle there if it's needed.
1116      */
1117
1118     CkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
1119     cleanupLinePtr = index1Ptr->linePtr;
1120     while (CkBTreeNextTag(&search)) {
1121         oldState ^= 1;
1122         segPtr = search.segPtr;
1123         prevPtr = search.curIndex.linePtr->segPtr;
1124         if (prevPtr == segPtr) {
1125             search.curIndex.linePtr->segPtr = segPtr->nextPtr;
1126         } else {
1127             while (prevPtr->nextPtr != segPtr) {
1128                 prevPtr = prevPtr->nextPtr;
1129             }
1130             prevPtr->nextPtr = segPtr->nextPtr;
1131         }
1132         if (segPtr->body.toggle.inNodeCounts) {
1133             ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr,
1134                     segPtr->body.toggle.tagPtr, -1);
1135             segPtr->body.toggle.inNodeCounts = 0;
1136         }
1137         ckfree((char *) segPtr);
1138
1139         /*
1140          * The code below is a bit tricky.  After deleting a toggle
1141          * we eventually have to call CleanupLine, in order to allow
1142          * character segments to be merged together.  To do this, we
1143          * remember in cleanupLinePtr a line that needs to be
1144          * cleaned up, but we don't clean it up until we've moved
1145          * on to a different line.  That way the cleanup process
1146          * won't goof up segPtr.
1147          */
1148
1149         if (cleanupLinePtr != search.curIndex.linePtr) {
1150             CleanupLine(cleanupLinePtr);
1151             cleanupLinePtr = search.curIndex.linePtr;
1152         }
1153     }
1154     if ((add != 0) ^ oldState) {
1155         segPtr = (CkTextSegment *) ckalloc(TSEG_SIZE);
1156         segPtr->typePtr = (add) ? &ckTextToggleOffType : &ckTextToggleOnType;
1157         prevPtr = SplitSeg(index2Ptr);
1158         if (prevPtr == NULL) {
1159             segPtr->nextPtr = index2Ptr->linePtr->segPtr;
1160             index2Ptr->linePtr->segPtr = segPtr;
1161         } else {
1162             segPtr->nextPtr = prevPtr->nextPtr;
1163             prevPtr->nextPtr = segPtr;
1164         }
1165         segPtr->size = 0;
1166         segPtr->body.toggle.tagPtr = tagPtr;
1167         segPtr->body.toggle.inNodeCounts = 0;
1168     }
1169
1170     /*
1171      * Cleanup cleanupLinePtr and the last line of the range, if
1172      * these are different.
1173      */
1174
1175     CleanupLine(cleanupLinePtr);
1176     if (cleanupLinePtr != index2Ptr->linePtr) {
1177         CleanupLine(index2Ptr->linePtr);
1178     }
1179
1180     if (ckBTreeDebug) {
1181         CkBTreeCheck(index1Ptr->tree);
1182     }
1183 }
1184 \f
1185 /*
1186  *----------------------------------------------------------------------
1187  *
1188  * ChangeNodeToggleCount --
1189  *
1190  *      This procedure increments or decrements the toggle count for
1191  *      a particular tag in a particular node and all its ancestors.
1192  *
1193  * Results:
1194  *      None.
1195  *
1196  * Side effects:
1197  *      The toggle count for tag is adjusted up or down by "delta" in
1198  *      nodePtr.
1199  *
1200  *----------------------------------------------------------------------
1201  */
1202
1203 static void
1204 ChangeNodeToggleCount(nodePtr, tagPtr, delta)
1205     register Node *nodePtr;             /* Node whose toggle count for a tag
1206                                          * must be changed. */
1207     CkTextTag *tagPtr;                  /* Information about tag. */
1208     int delta;                          /* Amount to add to current toggle
1209                                          * count for tag (may be negative). */
1210 {
1211     register Summary *summaryPtr, *prevPtr;
1212
1213     /*
1214      * Iterate over the node and all of its ancestors.
1215      */
1216
1217     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
1218         /*
1219          * See if there's already an entry for this tag for this node.  If so,
1220          * perhaps all we have to do is adjust its count.
1221          */
1222
1223         for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
1224                 summaryPtr != NULL;
1225                 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
1226             if (summaryPtr->tagPtr != tagPtr) {
1227                 continue;
1228             }
1229             summaryPtr->toggleCount += delta;
1230             if (summaryPtr->toggleCount > 0) {
1231                 goto nextAncestor;
1232             }
1233             if (summaryPtr->toggleCount < 0) {
1234                 panic("ChangeNodeToggleCount: negative toggle count");
1235             }
1236
1237             /*
1238              * Zero count;  must remove this tag from the list.
1239              */
1240
1241             if (prevPtr == NULL) {
1242                 nodePtr->summaryPtr = summaryPtr->nextPtr;
1243             } else {
1244                 prevPtr->nextPtr = summaryPtr->nextPtr;
1245             }
1246             ckfree((char *) summaryPtr);
1247             goto nextAncestor;
1248         }
1249
1250         /*
1251          * This tag isn't in the list.  Add a new entry to the list.
1252          */
1253
1254         if (delta < 0) {
1255             panic("ChangeNodeToggleCount: negative delta, no tag entry");
1256         }
1257         summaryPtr = (Summary *) ckalloc(sizeof(Summary));
1258         summaryPtr->tagPtr = tagPtr;
1259         summaryPtr->toggleCount = delta;
1260         summaryPtr->nextPtr = nodePtr->summaryPtr;
1261         nodePtr->summaryPtr = summaryPtr;
1262
1263         nextAncestor:
1264         continue;
1265     }
1266 }
1267 \f
1268 /*
1269  *----------------------------------------------------------------------
1270  *
1271  * CkBTreeStartSearch --
1272  *
1273  *      This procedure sets up a search for tag transitions involving
1274  *      a given tag (or all tags) in a given range of the text.
1275  *
1276  * Results:
1277  *      None.
1278  *
1279  * Side effects:
1280  *      The information at *searchPtr is set up so that subsequent calls
1281  *      to CkBTreeNextTag will return information about the locations of
1282  *      tag transitions.  Note that CkBTreeNextTag must be called to get
1283  *      the first transition.
1284  *
1285  *----------------------------------------------------------------------
1286  */
1287
1288 void
1289 CkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, searchPtr)
1290     CkTextIndex *index1Ptr;             /* Search starts here.  Tag toggles
1291                                          * at this position will not be
1292                                          * returned. */
1293     CkTextIndex *index2Ptr;             /* Search stops here.  Tag toggles
1294                                          * at this position *will* be
1295                                          * returned. */
1296     CkTextTag *tagPtr;                  /* Tag to search for.  NULL means
1297                                          * search for any tag. */
1298     register CkTextSearch *searchPtr;   /* Where to store information about
1299                                          * search's progress. */
1300 {
1301     int offset;
1302
1303     searchPtr->curIndex = *index1Ptr;
1304     searchPtr->segPtr = NULL;
1305     searchPtr->nextPtr = CkTextIndexToSeg(index1Ptr, &offset);
1306     searchPtr->curIndex.charIndex -= offset;
1307     searchPtr->lastPtr = CkTextIndexToSeg(index2Ptr, (int *) NULL);
1308     searchPtr->tagPtr = tagPtr;
1309     searchPtr->linesLeft = CkBTreeLineIndex(index2Ptr->linePtr) + 1
1310             - CkBTreeLineIndex(index1Ptr->linePtr);
1311     searchPtr->allTags = (tagPtr == NULL);
1312     if (searchPtr->linesLeft == 1) {
1313         /*
1314          * Starting and stopping segments are in the same line; mark the
1315          * search as over immediately if the second segment is before the
1316          * first.
1317          */
1318
1319         if (index1Ptr->charIndex >= index2Ptr->charIndex) {
1320             searchPtr->linesLeft = 0;
1321         }
1322     }
1323 }
1324 \f
1325 /*
1326  *----------------------------------------------------------------------
1327  *
1328  * CkBTreeNextTag --
1329  *
1330  *      Once a tag search has begun, successive calls to this procedure
1331  *      return successive tag toggles.  Note:  it is NOT SAFE to call this
1332  *      procedure if characters have been inserted into or deleted from
1333  *      the B-tree since the call to CkBTreeStartSearch.
1334  *
1335  * Results:
1336  *      The return value is 1 if another toggle was found that met the
1337  *      criteria specified in the call to CkBTreeStartSearch;  in this
1338  *      case searchPtr->curIndex gives the toggle's position and
1339  *      searchPtr->curTagPtr points to its segment.  0 is returned if
1340  *      no more matching tag transitions were found; in this case
1341  *      searchPtr->curIndex is the same as searchPtr->stopIndex.
1342  *
1343  * Side effects:
1344  *      Information in *searchPtr is modified to update the state of the
1345  *      search and indicate where the next tag toggle is located.
1346  *
1347  *----------------------------------------------------------------------
1348  */
1349
1350 int
1351 CkBTreeNextTag(searchPtr)
1352     register CkTextSearch *searchPtr;   /* Information about search in
1353                                          * progress;  must have been set up by
1354                                          * call to CkBTreeStartSearch. */
1355 {
1356     register CkTextSegment *segPtr;
1357     register Node *nodePtr;
1358     register Summary *summaryPtr;
1359
1360     if (searchPtr->linesLeft <= 0) {
1361         goto searchOver;
1362     }
1363
1364     /*
1365      * The outermost loop iterates over lines that may potentially contain
1366      * a relevant tag transition, starting from the current segment in
1367      * the current line.
1368      */
1369
1370     segPtr = searchPtr->nextPtr;
1371     while (1) {
1372         /*
1373          * Check for more tags on the current line.
1374          */
1375
1376         for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) {
1377             if (segPtr == searchPtr->lastPtr) {
1378                 goto searchOver;
1379             }
1380             if (((segPtr->typePtr == &ckTextToggleOnType)
1381                     || (segPtr->typePtr == &ckTextToggleOffType))
1382                     && (searchPtr->allTags
1383                     || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
1384                 searchPtr->segPtr = segPtr;
1385                 searchPtr->nextPtr = segPtr->nextPtr;
1386                 searchPtr->tagPtr = segPtr->body.toggle.tagPtr;
1387                 return 1;
1388             }
1389             searchPtr->curIndex.charIndex += segPtr->size;
1390         }
1391
1392         /*
1393          * See if there are more lines associated with the current parent
1394          * node.  If so, go back to the top of the loop to search the next
1395          * one.
1396          */
1397
1398         nodePtr = searchPtr->curIndex.linePtr->parentPtr;
1399         searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr;
1400         searchPtr->linesLeft--;
1401         if (searchPtr->linesLeft <= 0) {
1402             goto searchOver;
1403         }
1404         if (searchPtr->curIndex.linePtr != NULL) {
1405             segPtr = searchPtr->curIndex.linePtr->segPtr;
1406             searchPtr->curIndex.charIndex = 0;
1407             continue;
1408         }
1409
1410         /*
1411          * Search across and up through the B-tree's node hierarchy looking
1412          * for the next node that has a relevant tag transition somewhere in
1413          * its subtree.  Be sure to update linesLeft as we skip over large
1414          * chunks of lines.
1415          */
1416
1417         while (1) {
1418             while (nodePtr->nextPtr == NULL) {
1419                 if (nodePtr->parentPtr == NULL) {
1420                     goto searchOver;
1421                 }
1422                 nodePtr = nodePtr->parentPtr;
1423             }
1424             nodePtr = nodePtr->nextPtr;
1425             for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1426                     summaryPtr = summaryPtr->nextPtr) {
1427                 if ((searchPtr->allTags) ||
1428                         (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1429                     goto gotNodeWithTag;
1430                 }
1431             }
1432             searchPtr->linesLeft -= nodePtr->numLines;
1433         }
1434
1435         /*
1436          * At this point we've found a subtree that has a relevant tag
1437          * transition.  Now search down (and across) through that subtree
1438          * to find the first level-0 node that has a relevant tag transition.
1439          */
1440
1441         gotNodeWithTag:
1442         while (nodePtr->level > 0) {
1443             for (nodePtr = nodePtr->children.nodePtr; ;
1444                     nodePtr = nodePtr->nextPtr) {
1445                 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1446                         summaryPtr = summaryPtr->nextPtr) {
1447                     if ((searchPtr->allTags)
1448                             || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
1449                         goto nextChild;
1450                     }
1451                 }
1452                 searchPtr->linesLeft -= nodePtr->numLines;
1453                 if (nodePtr->nextPtr == NULL) {
1454                     panic("CkBTreeNextTag found incorrect tag summary info.");
1455                 }
1456             }
1457             nextChild:
1458             continue;
1459         }
1460
1461         /*
1462          * Now we're down to a level-0 node that contains a line that contains
1463          * a relevant tag transition.  Set up line information and go back to
1464          * the beginning of the loop to search through lines.
1465          */
1466
1467         searchPtr->curIndex.linePtr = nodePtr->children.linePtr;
1468         searchPtr->curIndex.charIndex = 0;
1469         segPtr = searchPtr->curIndex.linePtr->segPtr;
1470         if (searchPtr->linesLeft <= 0) {
1471             goto searchOver;
1472         }
1473         continue;
1474     }
1475
1476     searchOver:
1477     searchPtr->linesLeft = 0;
1478     searchPtr->segPtr = NULL;
1479     return 0;
1480 }
1481 \f
1482 /*
1483  *----------------------------------------------------------------------
1484  *
1485  * CkBTreeCharTagged --
1486  *
1487  *      Determine whether a particular character has a particular tag.
1488  *
1489  * Results:
1490  *      The return value is 1 if the given tag is in effect at the
1491  *      character given by linePtr and ch, and 0 otherwise.
1492  *
1493  * Side effects:
1494  *      None.
1495  *
1496  *----------------------------------------------------------------------
1497  */
1498
1499 int
1500 CkBTreeCharTagged(indexPtr, tagPtr)
1501     CkTextIndex *indexPtr;              /* Indicates a character position at
1502                                          * which to check for a tag. */
1503     CkTextTag *tagPtr;                  /* Tag of interest. */
1504 {
1505     register Node *nodePtr;
1506     register CkTextLine *siblingLinePtr;
1507     register CkTextSegment *segPtr;
1508     CkTextSegment *toggleSegPtr;
1509     int toggles, index;
1510
1511     /*
1512      * Check for toggles for the tag in indexPtr's line but before
1513      * indexPtr.  If there is one, its type indicates whether or
1514      * not the character is tagged.
1515      */
1516
1517     toggleSegPtr = NULL;
1518     for (index = 0, segPtr = indexPtr->linePtr->segPtr;
1519             (index + segPtr->size) <= indexPtr->charIndex;
1520             index += segPtr->size, segPtr = segPtr->nextPtr) {
1521         if (((segPtr->typePtr == &ckTextToggleOnType)
1522                 || (segPtr->typePtr == &ckTextToggleOffType))
1523                 && (segPtr->body.toggle.tagPtr == tagPtr)) {
1524             toggleSegPtr = segPtr;
1525         }
1526     }
1527     if (toggleSegPtr != NULL) {
1528         return (toggleSegPtr->typePtr == &ckTextToggleOnType);
1529     }
1530
1531     /*
1532      * No toggle in this line.  Look for toggles for the tag in lines
1533      * that are predecessors of indexPtr->linePtr but under the same
1534      * level-0 node.
1535      */
1536
1537     toggles = 0;
1538     for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
1539             siblingLinePtr != indexPtr->linePtr;
1540             siblingLinePtr = siblingLinePtr->nextPtr) {
1541         for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
1542                 segPtr = segPtr->nextPtr) {
1543             if (((segPtr->typePtr == &ckTextToggleOnType)
1544                     || (segPtr->typePtr == &ckTextToggleOffType))
1545                     && (segPtr->body.toggle.tagPtr == tagPtr)) {
1546                 toggleSegPtr = segPtr;
1547             }
1548         }
1549     }
1550     if (toggleSegPtr != NULL) {
1551         return (toggleSegPtr->typePtr == &ckTextToggleOnType);
1552     }
1553
1554     /*
1555      * No toggle in this node.  Scan upwards through the ancestors of
1556      * this node, counting the number of toggles of the given tag in
1557      * siblings that precede that node.
1558      */
1559
1560     toggles = 0;
1561     for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
1562             nodePtr = nodePtr->parentPtr) {
1563         register Node *siblingPtr;
1564         register Summary *summaryPtr;
1565
1566         for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
1567                 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
1568             for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
1569                     summaryPtr = summaryPtr->nextPtr) {
1570                 if (summaryPtr->tagPtr == tagPtr) {
1571                     toggles += summaryPtr->toggleCount;
1572                 }
1573             }
1574         }
1575     }
1576
1577     /*
1578      * An odd number of toggles means that the tag is present at the
1579      * given point.
1580      */
1581
1582     return toggles & 1;
1583 }
1584 \f
1585 /*
1586  *----------------------------------------------------------------------
1587  *
1588  * CkBTreeGetTags --
1589  *
1590  *      Return information about all of the tags that are associated
1591  *      with a particular character in a B-tree of text.
1592  *
1593  * Results:
1594  *      The return value is a malloc-ed array containing pointers to
1595  *      information for each of the tags that is associated with
1596  *      the character at the position given by linePtr and ch.  The
1597  *      word at *numTagsPtr is filled in with the number of pointers
1598  *      in the array.  It is up to the caller to free the array by
1599  *      passing it to free.  If there are no tags at the given character
1600  *      then a NULL pointer is returned and *numTagsPtr will be set to 0.
1601  *
1602  * Side effects:
1603  *      None.
1604  *
1605  *----------------------------------------------------------------------
1606  */
1607
1608         /* ARGSUSED */
1609 CkTextTag **
1610 CkBTreeGetTags(indexPtr, numTagsPtr)
1611     CkTextIndex *indexPtr;      /* Indicates a particular position in
1612                                  * the B-tree. */
1613     int *numTagsPtr;            /* Store number of tags found at this
1614                                  * location. */
1615 {
1616     register Node *nodePtr;
1617     register CkTextLine *siblingLinePtr;
1618     register CkTextSegment *segPtr;
1619     int src, dst, index;
1620     TagInfo tagInfo;
1621 #define NUM_TAG_INFOS 10
1622
1623     tagInfo.numTags = 0;
1624     tagInfo.arraySize = NUM_TAG_INFOS;
1625     tagInfo.tagPtrs = (CkTextTag **) ckalloc((unsigned)
1626             NUM_TAG_INFOS*sizeof(CkTextTag *));
1627     tagInfo.counts = (int *) ckalloc((unsigned)
1628             NUM_TAG_INFOS*sizeof(int));
1629
1630     /*
1631      * Record tag toggles within the line of indexPtr but preceding
1632      * indexPtr.
1633      */
1634
1635     for (index = 0, segPtr = indexPtr->linePtr->segPtr;
1636             (index + segPtr->size) <= indexPtr->charIndex;
1637             index += segPtr->size, segPtr = segPtr->nextPtr) {
1638         if ((segPtr->typePtr == &ckTextToggleOnType)
1639                 || (segPtr->typePtr == &ckTextToggleOffType)) {
1640             IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
1641         }
1642     }
1643
1644     /*
1645      * Record toggles for tags in lines that are predecessors of
1646      * indexPtr->linePtr but under the same level-0 node.
1647      */
1648
1649     for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
1650             siblingLinePtr != indexPtr->linePtr;
1651             siblingLinePtr = siblingLinePtr->nextPtr) {
1652         for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
1653                 segPtr = segPtr->nextPtr) {
1654             if ((segPtr->typePtr == &ckTextToggleOnType)
1655                     || (segPtr->typePtr == &ckTextToggleOffType)) {
1656                 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
1657             }
1658         }
1659     }
1660
1661     /*
1662      * For each node in the ancestry of this line, record tag toggles
1663      * for all siblings that precede that node.
1664      */
1665
1666     for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
1667             nodePtr = nodePtr->parentPtr) {
1668         register Node *siblingPtr;
1669         register Summary *summaryPtr;
1670
1671         for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
1672                 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
1673             for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
1674                     summaryPtr = summaryPtr->nextPtr) {
1675                 if (summaryPtr->toggleCount & 1) {
1676                     IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount,
1677                             &tagInfo);
1678                 }
1679             }
1680         }
1681     }
1682
1683     /*
1684      * Go through the tag information and squash out all of the tags
1685      * that have even toggle counts (these tags exist before the point
1686      * of interest, but not at the desired character itself).
1687      */
1688
1689     for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
1690         if (tagInfo.counts[src] & 1) {
1691             tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
1692             dst++;
1693         }
1694     }
1695     *numTagsPtr = dst;
1696     ckfree((char *) tagInfo.counts);
1697     if (dst == 0) {
1698         ckfree((char *) tagInfo.tagPtrs);
1699         return NULL;
1700     }
1701     return tagInfo.tagPtrs;
1702 }
1703 \f
1704 /*
1705  *----------------------------------------------------------------------
1706  *
1707  * IncCount --
1708  *
1709  *      This is a utility procedure used by CkBTreeGetTags.  It
1710  *      increments the count for a particular tag, adding a new
1711  *      entry for that tag if there wasn't one previously.
1712  *
1713  * Results:
1714  *      None.
1715  *
1716  * Side effects:
1717  *      The information at *tagInfoPtr may be modified, and the arrays
1718  *      may be reallocated to make them larger.
1719  *
1720  *----------------------------------------------------------------------
1721  */
1722
1723 static void
1724 IncCount(tagPtr, inc, tagInfoPtr)
1725     CkTextTag *tagPtr;          /* Handle for tag. */
1726     int inc;                    /* Amount by which to increment tag count. */
1727     TagInfo *tagInfoPtr;        /* Holds cumulative information about tags;
1728                                  * increment count here. */
1729 {
1730     register CkTextTag **tagPtrPtr;
1731     int count;
1732
1733     for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
1734             count > 0; tagPtrPtr++, count--) {
1735         if (*tagPtrPtr == tagPtr) {
1736             tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
1737             return;
1738         }
1739     }
1740
1741     /*
1742      * There isn't currently an entry for this tag, so we have to
1743      * make a new one.  If the arrays are full, then enlarge the
1744      * arrays first.
1745      */
1746
1747     if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
1748         CkTextTag **newTags;
1749         int *newCounts, newSize;
1750
1751         newSize = 2*tagInfoPtr->arraySize;
1752         newTags = (CkTextTag **) ckalloc((unsigned)
1753                 (newSize*sizeof(CkTextTag *)));
1754         memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
1755                 tagInfoPtr->arraySize * sizeof(CkTextTag *));
1756         ckfree((char *) tagInfoPtr->tagPtrs);
1757         tagInfoPtr->tagPtrs = newTags;
1758         newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
1759         memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
1760                 tagInfoPtr->arraySize * sizeof(int));
1761         ckfree((char *) tagInfoPtr->counts);
1762         tagInfoPtr->counts = newCounts;
1763         tagInfoPtr->arraySize = newSize;
1764     }
1765
1766     tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
1767     tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
1768     tagInfoPtr->numTags++;
1769 }
1770 \f
1771 /*
1772  *----------------------------------------------------------------------
1773  *
1774  * CkBTreeCheck --
1775  *
1776  *      This procedure runs a set of consistency checks over a B-tree
1777  *      and panics if any inconsistencies are found.
1778  *
1779  * Results:
1780  *      None.
1781  *
1782  * Side effects:
1783  *      If a structural defect is found, the procedure panics with an
1784  *      error message.
1785  *
1786  *----------------------------------------------------------------------
1787  */
1788
1789 void
1790 CkBTreeCheck(tree)
1791     CkTextBTree tree;           /* Tree to check. */
1792 {
1793     BTree *treePtr = (BTree *) tree;
1794     register Summary *summaryPtr;
1795     register Node *nodePtr;
1796     register CkTextLine *linePtr;
1797     register CkTextSegment *segPtr;
1798
1799     /*
1800      * Make sure that overall there is an even count of tag transitions
1801      * for the whole tree.
1802      */
1803
1804     for (summaryPtr = treePtr->rootPtr->summaryPtr; summaryPtr != NULL;
1805             summaryPtr = summaryPtr->nextPtr) {
1806         if (summaryPtr->toggleCount & 1) {
1807             panic("CkBTreeCheck found odd toggle count for \"%s\" (%d)",
1808                     summaryPtr->tagPtr->name, summaryPtr->toggleCount);
1809         }
1810     }
1811
1812     /*
1813      * Call a recursive procedure to do the main body of checks.
1814      */
1815
1816     nodePtr = treePtr->rootPtr;
1817     CheckNodeConsistency(treePtr->rootPtr);
1818
1819     /*
1820      * Make sure that there are at least two lines in the text and
1821      * that the last line has no characters except a newline.
1822      */
1823
1824     if (nodePtr->numLines < 2) {
1825         panic("CkBTreeCheck: less than 2 lines in tree");
1826     }
1827     while (nodePtr->level > 0) {
1828         nodePtr = nodePtr->children.nodePtr;
1829         while (nodePtr->nextPtr != NULL) {
1830             nodePtr = nodePtr->nextPtr;
1831         }
1832     }
1833     linePtr = nodePtr->children.linePtr;
1834     while (linePtr->nextPtr != NULL) {
1835         linePtr = linePtr->nextPtr;
1836     }
1837     segPtr = linePtr->segPtr;
1838     while ((segPtr->typePtr == &ckTextToggleOffType)
1839             || (segPtr->typePtr == &ckTextRightMarkType)
1840             || (segPtr->typePtr == &ckTextLeftMarkType)) {
1841         /*
1842          * It's OK to toggle a tag off in the last line, but
1843          * not to start a new range.  It's also OK to have marks
1844          * in the last line.
1845          */
1846
1847         segPtr = segPtr->nextPtr;
1848     }
1849     if (segPtr->typePtr != &ckTextCharType) {
1850         panic("CkBTreeCheck: last line has bogus segment type");
1851     }
1852     if (segPtr->nextPtr != NULL) {
1853         panic("CkBTreeCheck: last line has too many segments");
1854     }
1855     if (segPtr->size != 1) {
1856         panic("CkBTreeCheck: last line has wrong # characters: %d",
1857                 segPtr->size);
1858     }
1859     if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) {
1860         panic("CkBTreeCheck: last line had bad value: %s",
1861                 segPtr->body.chars);
1862     }
1863 }
1864 \f
1865 /*
1866  *----------------------------------------------------------------------
1867  *
1868  * CheckNodeConsistency --
1869  *
1870  *      This procedure is called as part of consistency checking for
1871  *      B-trees:  it checks several aspects of a node and also runs
1872  *      checks recursively on the node's children.
1873  *
1874  * Results:
1875  *      None.
1876  *
1877  * Side effects:
1878  *      If anything suspicious is found in the tree structure, the
1879  *      procedure panics.
1880  *
1881  *----------------------------------------------------------------------
1882  */
1883
1884 static void
1885 CheckNodeConsistency(nodePtr)
1886     register Node *nodePtr;             /* Node whose subtree should be
1887                                          * checked. */
1888 {
1889     register Node *childNodePtr;
1890     register Summary *summaryPtr, *summaryPtr2;
1891     register CkTextLine *linePtr;
1892     register CkTextSegment *segPtr;
1893     int numChildren, numLines, toggleCount, minChildren;
1894
1895     if (nodePtr->parentPtr != NULL) {
1896         minChildren = MIN_CHILDREN;
1897     } else if (nodePtr->level > 0) {
1898         minChildren = 2;
1899     } else  {
1900         minChildren = 1;
1901     }
1902     if ((nodePtr->numChildren < minChildren)
1903             || (nodePtr->numChildren > MAX_CHILDREN)) {
1904         panic("CheckNodeConsistency: bad child count (%d)",
1905                 nodePtr->numChildren);
1906     }
1907
1908     numChildren = 0;
1909     numLines = 0;
1910     if (nodePtr->level == 0) {
1911         for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
1912                 linePtr = linePtr->nextPtr) {
1913             if (linePtr->parentPtr != nodePtr) {
1914                 panic("CheckNodeConsistency: line doesn't point to parent");
1915             }
1916             if (linePtr->segPtr == NULL) {
1917                 panic("CheckNodeConsistency: line has no segments");
1918             }
1919             for (segPtr = linePtr->segPtr; segPtr != NULL;
1920                     segPtr = segPtr->nextPtr) {
1921                 if (segPtr->typePtr->checkProc != NULL) {
1922                     (*segPtr->typePtr->checkProc)(segPtr, linePtr);
1923                 }
1924                 if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity)
1925                         && (segPtr->nextPtr != NULL)
1926                         && (segPtr->nextPtr->size == 0)
1927                         && (segPtr->nextPtr->typePtr->leftGravity)) {
1928                     panic("CheckNodeConsistency: wrong segment order for gravity");
1929                 }
1930                 if ((segPtr->nextPtr == NULL)
1931                         && (segPtr->typePtr != &ckTextCharType)) {
1932                     panic("CheckNodeConsistency: line ended with wrong type");
1933                 }
1934             }
1935             numChildren++;
1936             numLines++;
1937         }
1938     } else {
1939         for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
1940                 childNodePtr = childNodePtr->nextPtr) {
1941             if (childNodePtr->parentPtr != nodePtr) {
1942                 panic("CheckNodeConsistency: node doesn't point to parent");
1943             }
1944             if (childNodePtr->level != (nodePtr->level-1)) {
1945                 panic("CheckNodeConsistency: level mismatch (%d %d)",
1946                         nodePtr->level, childNodePtr->level);
1947             }
1948             CheckNodeConsistency(childNodePtr);
1949             for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
1950                         summaryPtr = summaryPtr->nextPtr) {
1951                 for (summaryPtr2 = nodePtr->summaryPtr; ;
1952                         summaryPtr2 = summaryPtr2->nextPtr) {
1953                     if (summaryPtr2 == NULL) {
1954                         panic("CheckNodeConsistency: node tag \"%s\" not %s",
1955                                 summaryPtr->tagPtr->name,
1956                                 "present in parent summaries");
1957                     }
1958                     if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
1959                         break;
1960                     }
1961                 }
1962             }
1963             numChildren++;
1964             numLines += childNodePtr->numLines;
1965         }
1966     }
1967     if (numChildren != nodePtr->numChildren) {
1968         panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
1969                 numChildren, nodePtr->numChildren);
1970     }
1971     if (numLines != nodePtr->numLines) {
1972         panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
1973                 numLines, nodePtr->numLines);
1974     }
1975
1976     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
1977             summaryPtr = summaryPtr->nextPtr) {
1978         toggleCount = 0;
1979         if (nodePtr->level == 0) {
1980             for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
1981                     linePtr = linePtr->nextPtr) {
1982                 for (segPtr = linePtr->segPtr; segPtr != NULL;
1983                         segPtr = segPtr->nextPtr) {
1984                     if ((segPtr->typePtr != &ckTextToggleOnType)
1985                             && (segPtr->typePtr != &ckTextToggleOffType)) {
1986                         continue;
1987                     }
1988                     if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) {
1989                         toggleCount ++;
1990                     }
1991                 }
1992             }
1993         } else {
1994             for (childNodePtr = nodePtr->children.nodePtr;
1995                     childNodePtr != NULL;
1996                     childNodePtr = childNodePtr->nextPtr) {
1997                 for (summaryPtr2 = childNodePtr->summaryPtr;
1998                         summaryPtr2 != NULL;
1999                         summaryPtr2 = summaryPtr2->nextPtr) {
2000                     if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2001                         toggleCount += summaryPtr2->toggleCount;
2002                     }
2003                 }
2004             }
2005         }
2006         if (toggleCount != summaryPtr->toggleCount) {
2007             panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
2008                     toggleCount, summaryPtr->toggleCount);
2009         }
2010         for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
2011                 summaryPtr2 = summaryPtr2->nextPtr) {
2012             if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
2013                 panic("CheckNodeConsistency: duplicated node tag: %s",
2014                         summaryPtr->tagPtr->name);
2015             }
2016         }
2017     }
2018 }
2019 \f
2020 /*
2021  *----------------------------------------------------------------------
2022  *
2023  * Rebalance --
2024  *
2025  *      This procedure is called when a node of a B-tree appears to be
2026  *      out of balance (too many children, or too few).  It rebalances
2027  *      that node and all of its ancestors in the tree.
2028  *
2029  * Results:
2030  *      None.
2031  *
2032  * Side effects:
2033  *      The internal structure of treePtr may change.
2034  *
2035  *----------------------------------------------------------------------
2036  */
2037
2038 static void
2039 Rebalance(treePtr, nodePtr)
2040     BTree *treePtr;                     /* Tree that is being rebalanced. */
2041     register Node *nodePtr;             /* Node that may be out of balance. */
2042 {
2043     /*
2044      * Loop over the entire ancestral chain of the node, working up
2045      * through the tree one node at a time until the root node has
2046      * been processed.
2047      */
2048
2049     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
2050         register Node *newPtr, *childPtr;
2051         register CkTextLine *linePtr;
2052         int i;
2053
2054         /*
2055          * Check to see if the node has too many children.  If it does,
2056          * then split off all but the first MIN_CHILDREN into a separate
2057          * node following the original one.  Then repeat until the
2058          * node has a decent size.
2059          */
2060
2061         if (nodePtr->numChildren > MAX_CHILDREN) {
2062             while (1) {
2063                 /*
2064                  * If the node being split is the root node, then make a
2065                  * new root node above it first.
2066                  */
2067
2068                 if (nodePtr->parentPtr == NULL) {
2069                     newPtr = (Node *) ckalloc(sizeof(Node));
2070                     newPtr->parentPtr = NULL;
2071                     newPtr->nextPtr = NULL;
2072                     newPtr->summaryPtr = NULL;
2073                     newPtr->level = nodePtr->level + 1;
2074                     newPtr->children.nodePtr = nodePtr;
2075                     newPtr->numChildren = 1;
2076                     newPtr->numLines = nodePtr->numLines;
2077                     RecomputeNodeCounts(newPtr);
2078                     treePtr->rootPtr = newPtr;
2079                 }
2080                 newPtr = (Node *) ckalloc(sizeof(Node));
2081                 newPtr->parentPtr = nodePtr->parentPtr;
2082                 newPtr->nextPtr = nodePtr->nextPtr;
2083                 nodePtr->nextPtr = newPtr;
2084                 newPtr->summaryPtr = NULL;
2085                 newPtr->level = nodePtr->level;
2086                 newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
2087                 if (nodePtr->level == 0) {
2088                     for (i = MIN_CHILDREN-1,
2089                             linePtr = nodePtr->children.linePtr;
2090                             i > 0; i--, linePtr = linePtr->nextPtr) {
2091                         /* Empty loop body. */
2092                     }
2093                     newPtr->children.linePtr = linePtr->nextPtr;
2094                     linePtr->nextPtr = NULL;
2095                 } else {
2096                     for (i = MIN_CHILDREN-1,
2097                             childPtr = nodePtr->children.nodePtr;
2098                             i > 0; i--, childPtr = childPtr->nextPtr) {
2099                         /* Empty loop body. */
2100                     }
2101                     newPtr->children.nodePtr = childPtr->nextPtr;
2102                     childPtr->nextPtr = NULL;
2103                 }
2104                 RecomputeNodeCounts(nodePtr);
2105                 nodePtr->parentPtr->numChildren++;
2106                 nodePtr = newPtr;
2107                 if (nodePtr->numChildren <= MAX_CHILDREN) {
2108                     RecomputeNodeCounts(nodePtr);
2109                     break;
2110                 }
2111             }
2112         }
2113
2114         while (nodePtr->numChildren < MIN_CHILDREN) {
2115             register Node *otherPtr;
2116             Node *halfwayNodePtr = NULL;        /* Initialization needed only */
2117             CkTextLine *halfwayLinePtr = NULL;  /* to prevent cc warnings. */
2118             int totalChildren, firstChildren, i;
2119
2120             /*
2121              * Too few children for this node.  If this is the root then,
2122              * it's OK for it to have less than MIN_CHILDREN children
2123              * as long as it's got at least two.  If it has only one
2124              * (and isn't at level 0), then chop the root node out of
2125              * the tree and use its child as the new root.
2126              */
2127
2128             if (nodePtr->parentPtr == NULL) {
2129                 if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
2130                     treePtr->rootPtr = nodePtr->children.nodePtr;
2131                     treePtr->rootPtr->parentPtr = NULL;
2132                     DeleteSummaries(nodePtr->summaryPtr);
2133                     ckfree((char *) nodePtr);
2134                 }
2135                 return;
2136             }
2137
2138             /*
2139              * Not the root.  Make sure that there are siblings to
2140              * balance with.
2141              */
2142
2143             if (nodePtr->parentPtr->numChildren < 2) {
2144                 Rebalance(treePtr, nodePtr->parentPtr);
2145                 continue;
2146             }
2147
2148             /*
2149              * Find a sibling neighbor to borrow from, and arrange for
2150              * nodePtr to be the earlier of the pair.
2151              */
2152
2153             if (nodePtr->nextPtr == NULL) {
2154                 for (otherPtr = nodePtr->parentPtr->children.nodePtr;
2155                         otherPtr->nextPtr != nodePtr;
2156                         otherPtr = otherPtr->nextPtr) {
2157                     /* Empty loop body. */
2158                 }
2159                 nodePtr = otherPtr;
2160             }
2161             otherPtr = nodePtr->nextPtr;
2162
2163             /*
2164              * We're going to either merge the two siblings together
2165              * into one node or redivide the children among them to
2166              * balance their loads.  As preparation, join their two
2167              * child lists into a single list and remember the half-way
2168              * point in the list.
2169              */
2170
2171             totalChildren = nodePtr->numChildren + otherPtr->numChildren;
2172             firstChildren = totalChildren/2;
2173             if (nodePtr->children.nodePtr == NULL) {
2174                 nodePtr->children = otherPtr->children;
2175                 otherPtr->children.nodePtr = NULL;
2176                 otherPtr->children.linePtr = NULL;
2177             }
2178             if (nodePtr->level == 0) {
2179                 register CkTextLine *linePtr;
2180
2181                 for (linePtr = nodePtr->children.linePtr, i = 1;
2182                         linePtr->nextPtr != NULL;
2183                         linePtr = linePtr->nextPtr, i++) {
2184                     if (i == firstChildren) {
2185                         halfwayLinePtr = linePtr;
2186                     }
2187                 }
2188                 linePtr->nextPtr = otherPtr->children.linePtr;
2189                 while (i <= firstChildren) {
2190                     halfwayLinePtr = linePtr;
2191                     linePtr = linePtr->nextPtr;
2192                     i++;
2193                 }
2194             } else {
2195                 register Node *childPtr;
2196
2197                 for (childPtr = nodePtr->children.nodePtr, i = 1;
2198                         childPtr->nextPtr != NULL;
2199                         childPtr = childPtr->nextPtr, i++) {
2200                     if (i <= firstChildren) {
2201                         if (i == firstChildren) {
2202                             halfwayNodePtr = childPtr;
2203                         }
2204                     }
2205                 }
2206                 childPtr->nextPtr = otherPtr->children.nodePtr;
2207                 while (i <= firstChildren) {
2208                     halfwayNodePtr = childPtr;
2209                     childPtr = childPtr->nextPtr;
2210                     i++;
2211                 }
2212             }
2213
2214             /*
2215              * If the two siblings can simply be merged together, do it.
2216              */
2217
2218             if (totalChildren <= MAX_CHILDREN) {
2219                 RecomputeNodeCounts(nodePtr);
2220                 nodePtr->nextPtr = otherPtr->nextPtr;
2221                 nodePtr->parentPtr->numChildren--;
2222                 DeleteSummaries(otherPtr->summaryPtr);
2223                 ckfree((char *) otherPtr);
2224                 continue;
2225             }
2226
2227             /*
2228              * The siblings can't be merged, so just divide their
2229              * children evenly between them.
2230              */
2231
2232             if (nodePtr->level == 0) {
2233                 otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
2234                 halfwayLinePtr->nextPtr = NULL;
2235             } else {
2236                 otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
2237                 halfwayNodePtr->nextPtr = NULL;
2238             }
2239             RecomputeNodeCounts(nodePtr);
2240             RecomputeNodeCounts(otherPtr);
2241         }
2242     }
2243 }
2244 \f
2245 /*
2246  *----------------------------------------------------------------------
2247  *
2248  * RecomputeNodeCounts --
2249  *
2250  *      This procedure is called to recompute all the counts in a node
2251  *      (tags, child information, etc.) by scanning the information in
2252  *      its descendants.  This procedure is called during rebalancing
2253  *      when a node's child structure has changed.
2254  *
2255  * Results:
2256  *      None.
2257  *
2258  * Side effects:
2259  *      The tag counts for nodePtr are modified to reflect its current
2260  *      child structure, as are its numChildren and numLines fields.
2261  *      Also, all of the childrens' parentPtr fields are made to point
2262  *      to nodePtr.
2263  *
2264  *----------------------------------------------------------------------
2265  */
2266
2267 static void
2268 RecomputeNodeCounts(nodePtr)
2269     register Node *nodePtr;             /* Node whose tag summary information
2270                                          * must be recomputed. */
2271 {
2272     register Summary *summaryPtr, *summaryPtr2;
2273     register Node *childPtr;
2274     register CkTextLine *linePtr;
2275     register CkTextSegment *segPtr;
2276     CkTextTag *tagPtr;
2277
2278     /*
2279      * Zero out all the existing counts for the node, but don't delete
2280      * the existing Summary records (most of them will probably be reused).
2281      */
2282
2283     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
2284             summaryPtr = summaryPtr->nextPtr) {
2285         summaryPtr->toggleCount = 0;
2286     }
2287     nodePtr->numChildren = 0;
2288     nodePtr->numLines = 0;
2289
2290     /*
2291      * Scan through the children, adding the childrens' tag counts into
2292      * the node's tag counts and adding new Summary structures if
2293      * necessary.
2294      */
2295
2296     if (nodePtr->level == 0) {
2297         for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
2298                 linePtr = linePtr->nextPtr) {
2299             nodePtr->numChildren++;
2300             nodePtr->numLines++;
2301             linePtr->parentPtr = nodePtr;
2302             for (segPtr = linePtr->segPtr; segPtr != NULL;
2303                     segPtr = segPtr->nextPtr) {
2304                 if (((segPtr->typePtr != &ckTextToggleOnType)
2305                         && (segPtr->typePtr != &ckTextToggleOffType))
2306                         || !(segPtr->body.toggle.inNodeCounts)) {
2307                     continue;
2308                 }
2309                 tagPtr = segPtr->body.toggle.tagPtr;
2310                 for (summaryPtr = nodePtr->summaryPtr; ;
2311                         summaryPtr = summaryPtr->nextPtr) {
2312                     if (summaryPtr == NULL) {
2313                         summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2314                         summaryPtr->tagPtr = tagPtr;
2315                         summaryPtr->toggleCount = 1;
2316                         summaryPtr->nextPtr = nodePtr->summaryPtr;
2317                         nodePtr->summaryPtr = summaryPtr;
2318                         break;
2319                     }
2320                     if (summaryPtr->tagPtr == tagPtr) {
2321                         summaryPtr->toggleCount++;
2322                         break;
2323                     }
2324                 }
2325             }
2326         }
2327     } else {
2328         for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
2329                 childPtr = childPtr->nextPtr) {
2330             nodePtr->numChildren++;
2331             nodePtr->numLines += childPtr->numLines;
2332             childPtr->parentPtr = nodePtr;
2333             for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
2334                     summaryPtr2 = summaryPtr2->nextPtr) {
2335                 for (summaryPtr = nodePtr->summaryPtr; ;
2336                         summaryPtr = summaryPtr->nextPtr) {
2337                     if (summaryPtr == NULL) {
2338                         summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2339                         summaryPtr->tagPtr = summaryPtr2->tagPtr;
2340                         summaryPtr->toggleCount = summaryPtr2->toggleCount;
2341                         summaryPtr->nextPtr = nodePtr->summaryPtr;
2342                         nodePtr->summaryPtr = summaryPtr;
2343                         break;
2344                     }
2345                     if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
2346                         summaryPtr->toggleCount += summaryPtr2->toggleCount;
2347                         break;
2348                     }
2349                 }
2350             }
2351         }
2352     }
2353
2354     /*
2355      * Scan through the node's tag records again and delete any Summary
2356      * records that still have a zero count.
2357      */
2358
2359     summaryPtr2 = NULL;
2360     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
2361         if (summaryPtr->toggleCount > 0) {
2362             summaryPtr2 = summaryPtr;
2363             summaryPtr = summaryPtr->nextPtr;
2364             continue;
2365         }
2366         if (summaryPtr2 != NULL) {
2367             summaryPtr2->nextPtr = summaryPtr->nextPtr;
2368             ckfree((char *) summaryPtr);
2369             summaryPtr = summaryPtr2->nextPtr;
2370         } else {
2371             nodePtr->summaryPtr = summaryPtr->nextPtr;
2372             ckfree((char *) summaryPtr);
2373             summaryPtr = nodePtr->summaryPtr;
2374         }
2375     }
2376 }
2377 \f
2378 /*
2379  *----------------------------------------------------------------------
2380  *
2381  * CkBTreeNumLines --
2382  *
2383  *      This procedure returns a count of the number of lines of
2384  *      text present in a given B-tree.
2385  *
2386  * Results:
2387  *      The return value is a count of the number of usable lines
2388  *      in tree (i.e. it doesn't include the dummy line that is just
2389  *      used to mark the end of the tree).
2390  *
2391  * Side effects:
2392  *      None.
2393  *
2394  *----------------------------------------------------------------------
2395  */
2396
2397 int
2398 CkBTreeNumLines(tree)
2399     CkTextBTree tree;                   /* Information about tree. */
2400 {
2401     BTree *treePtr = (BTree *) tree;
2402     return treePtr->rootPtr->numLines - 1;
2403 }
2404 \f
2405 /*
2406  *--------------------------------------------------------------
2407  *
2408  * CharSplitProc --
2409  *
2410  *      This procedure implements splitting for character segments.
2411  *
2412  * Results:
2413  *      The return value is a pointer to a chain of two segments
2414  *      that have the same characters as segPtr except split
2415  *      among the two segments.
2416  *
2417  * Side effects:
2418  *      Storage for segPtr is freed.
2419  *
2420  *--------------------------------------------------------------
2421  */
2422
2423 static CkTextSegment *
2424 CharSplitProc(segPtr, index)
2425     CkTextSegment *segPtr;              /* Pointer to segment to split. */
2426     int index;                          /* Position within segment at which
2427                                          * to split. */
2428 {
2429     CkTextSegment *newPtr1, *newPtr2;
2430
2431     newPtr1 = (CkTextSegment *) ckalloc(CSEG_SIZE(index));
2432     newPtr2 = (CkTextSegment *) ckalloc(
2433             CSEG_SIZE(segPtr->size - index));
2434     newPtr1->typePtr = &ckTextCharType;
2435     newPtr1->nextPtr = newPtr2;
2436     newPtr1->size = index;
2437     strncpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index);
2438     newPtr1->body.chars[index] = 0;
2439     newPtr2->typePtr = &ckTextCharType;
2440     newPtr2->nextPtr = segPtr->nextPtr;
2441     newPtr2->size = segPtr->size - index;
2442     strcpy(newPtr2->body.chars, segPtr->body.chars + index);
2443     ckfree((char*) segPtr);
2444     return newPtr1;
2445 }
2446 \f
2447 /*
2448  *--------------------------------------------------------------
2449  *
2450  * CharCleanupProc --
2451  *
2452  *      This procedure merges adjacent character segments into
2453  *      a single character segment, if possible.
2454  *
2455  * Results:
2456  *      The return value is a pointer to the first segment in
2457  *      the (new) list of segments that used to start with segPtr.
2458  *
2459  * Side effects:
2460  *      Storage for the segments may be allocated and freed.
2461  *
2462  *--------------------------------------------------------------
2463  */
2464
2465         /* ARGSUSED */
2466 static CkTextSegment *
2467 CharCleanupProc(segPtr, linePtr)
2468     CkTextSegment *segPtr;              /* Pointer to first of two adjacent
2469                                          * segments to join. */
2470     CkTextLine *linePtr;                /* Line containing segments (not
2471                                          * used). */
2472 {
2473     CkTextSegment *segPtr2, *newPtr;
2474
2475     segPtr2 = segPtr->nextPtr;
2476     if ((segPtr2 == NULL) || (segPtr2->typePtr != &ckTextCharType)) {
2477         return segPtr;
2478     }
2479     newPtr = (CkTextSegment *) ckalloc(CSEG_SIZE(
2480             segPtr->size + segPtr2->size));
2481     newPtr->typePtr = &ckTextCharType;
2482     newPtr->nextPtr = segPtr2->nextPtr;
2483     newPtr->size = segPtr->size + segPtr2->size;
2484     strcpy(newPtr->body.chars, segPtr->body.chars);
2485     strcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars);
2486     ckfree((char*) segPtr);
2487     ckfree((char*) segPtr2);
2488     return newPtr;
2489 }
2490 \f
2491 /*
2492  *--------------------------------------------------------------
2493  *
2494  * CharDeleteProc --
2495  *
2496  *      This procedure is invoked to delete a character segment.
2497  *
2498  * Results:
2499  *      Always returns 0 to indicate that the segment was deleted.
2500  *
2501  * Side effects:
2502  *      Storage for the segment is freed.
2503  *
2504  *--------------------------------------------------------------
2505  */
2506
2507         /* ARGSUSED */
2508 static int
2509 CharDeleteProc(segPtr, linePtr, treeGone)
2510     CkTextSegment *segPtr;              /* Segment to delete. */
2511     CkTextLine *linePtr;                /* Line containing segment. */
2512     int treeGone;                       /* Non-zero means the entire tree is
2513                                          * being deleted, so everything must
2514                                          * get cleaned up. */
2515 {
2516     ckfree((char*) segPtr);
2517     return 0;
2518 }
2519 \f
2520 /*
2521  *--------------------------------------------------------------
2522  *
2523  * CharCheckProc --
2524  *
2525  *      This procedure is invoked to perform consistency checks
2526  *      on character segments.
2527  *
2528  * Results:
2529  *      None.
2530  *
2531  * Side effects:
2532  *      If the segment isn't inconsistent then the procedure
2533  *      panics.
2534  *
2535  *--------------------------------------------------------------
2536  */
2537
2538         /* ARGSUSED */
2539 static void
2540 CharCheckProc(segPtr, linePtr)
2541     CkTextSegment *segPtr;              /* Segment to check. */
2542     CkTextLine *linePtr;                /* Line containing segment. */
2543 {
2544     /*
2545      * Make sure that the segment contains the number of
2546      * characters indicated by its header, and that the last
2547      * segment in a line ends in a newline.  Also make sure
2548      * that there aren't ever two character segments adjacent
2549      * to each other:  they should be merged together.
2550      */
2551
2552     if (segPtr->size <= 0) {
2553         panic("CharCheckProc: segment has size <= 0");
2554     }
2555     if ((int) strlen(segPtr->body.chars) != segPtr->size) {
2556         panic("CharCheckProc: segment has wrong size");
2557     }
2558     if (segPtr->nextPtr == NULL) {
2559         if (segPtr->body.chars[segPtr->size-1] != '\n') {
2560             panic("CharCheckProc: line doesn't end with newline");
2561         }
2562     } else {
2563         if (segPtr->nextPtr->typePtr == &ckTextCharType) {
2564             panic("CharCheckProc: adjacent character segments weren't merged");
2565         }
2566     }
2567 }
2568 \f
2569 /*
2570  *--------------------------------------------------------------
2571  *
2572  * ToggleDeleteProc --
2573  *
2574  *      This procedure is invoked to delete toggle segments.
2575  *
2576  * Results:
2577  *      Returns 1 to indicate that the segment may not be deleted,
2578  *      unless the entire B-tree is going away.
2579  *
2580  * Side effects:
2581  *      If the tree is going away then the toggle's memory is
2582  *      freed;  otherwise the toggle counts in nodes above the
2583  *      segment get updated.
2584  *
2585  *--------------------------------------------------------------
2586  */
2587
2588 static int
2589 ToggleDeleteProc(segPtr, linePtr, treeGone)
2590     CkTextSegment *segPtr;              /* Segment to check. */
2591     CkTextLine *linePtr;                /* Line containing segment. */
2592     int treeGone;                       /* Non-zero means the entire tree is
2593                                          * being deleted, so everything must
2594                                          * get cleaned up. */
2595 {
2596     if (treeGone) {
2597         ckfree((char *) segPtr);
2598         return 0;
2599     }
2600
2601     /*
2602      * This toggle is in the middle of a range of characters that's
2603      * being deleted.  Refuse to die.  We'll be moved to the end of
2604      * the deleted range and our cleanup procedure will be called
2605      * later.  Decrement node toggle counts here, and set a flag
2606      * so we'll re-increment them in the cleanup procedure.
2607      */
2608
2609     if (segPtr->body.toggle.inNodeCounts) {
2610         ChangeNodeToggleCount(linePtr->parentPtr,
2611                 segPtr->body.toggle.tagPtr, -1);
2612         segPtr->body.toggle.inNodeCounts = 0;
2613     }
2614     return 1;
2615 }
2616 \f
2617 /*
2618  *--------------------------------------------------------------
2619  *
2620  * ToggleCleanupProc --
2621  *
2622  *      This procedure when a toggle is part of a line that's
2623  *      been modified in some way.  It's invoked after the
2624  *      modifications are complete.
2625  *
2626  * Results:
2627  *      The return value is the head segment in a new list
2628  *      that is to replace the tail of the line that used to
2629  *      start at segPtr.  This allows the procedure to delete
2630  *      or modify segPtr.
2631  *
2632  * Side effects:
2633  *      Toggle counts in the nodes above the new line will be
2634  *      updated if they're not already.  Toggles may be collapsed
2635  *      if there are duplicate toggles at the same position.
2636  *
2637  *--------------------------------------------------------------
2638  */
2639
2640 static CkTextSegment *
2641 ToggleCleanupProc(segPtr, linePtr)
2642     CkTextSegment *segPtr;      /* Segment to check. */
2643     CkTextLine *linePtr;        /* Line that now contains segment. */
2644 {
2645     CkTextSegment *segPtr2, *prevPtr;
2646     int counts;
2647
2648     /*
2649      * If this is a toggle-off segment, look ahead through the next
2650      * segments to see if there's a toggle-on segment for the same tag
2651      * before any segments with non-zero size.  If so then the two
2652      * toggles cancel each other;  remove them both.
2653      */
2654
2655     if (segPtr->typePtr == &ckTextToggleOffType) {
2656         for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr;
2657                 (segPtr2 != NULL) && (segPtr2->size == 0);
2658                 prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) {
2659             if (segPtr2->typePtr != &ckTextToggleOnType) {
2660                 continue;
2661             }
2662             if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) {
2663                 continue;
2664             }
2665             counts = segPtr->body.toggle.inNodeCounts
2666                     + segPtr2->body.toggle.inNodeCounts;
2667             if (counts != 0) {
2668                 ChangeNodeToggleCount(linePtr->parentPtr,
2669                         segPtr->body.toggle.tagPtr, -counts);
2670             }
2671             prevPtr->nextPtr = segPtr2->nextPtr;
2672             ckfree((char *) segPtr2);
2673             segPtr2 = segPtr->nextPtr;
2674             ckfree((char *) segPtr);
2675             return segPtr2;
2676         }
2677     }
2678
2679     if (!segPtr->body.toggle.inNodeCounts) {
2680         ChangeNodeToggleCount(linePtr->parentPtr,
2681                 segPtr->body.toggle.tagPtr, 1);
2682         segPtr->body.toggle.inNodeCounts = 1;
2683     }
2684     return segPtr;
2685 }
2686 \f
2687 /*
2688  *--------------------------------------------------------------
2689  *
2690  * ToggleLineChangeProc --
2691  *
2692  *      This procedure is invoked when a toggle segment is about
2693  *      to move from one line to another.
2694  *
2695  * Results:
2696  *      None.
2697  *
2698  * Side effects:
2699  *      Toggle counts are decremented in the nodes above the line.
2700  *
2701  *--------------------------------------------------------------
2702  */
2703
2704 static void
2705 ToggleLineChangeProc(segPtr, linePtr)
2706     CkTextSegment *segPtr;      /* Segment to check. */
2707     CkTextLine *linePtr;        /* Line that used to contain segment. */
2708 {
2709     if (segPtr->body.toggle.inNodeCounts) {
2710         ChangeNodeToggleCount(linePtr->parentPtr,
2711                 segPtr->body.toggle.tagPtr, -1);
2712         segPtr->body.toggle.inNodeCounts = 0;
2713     }
2714 }
2715 \f
2716 /*
2717  *--------------------------------------------------------------
2718  *
2719  * ToggleCheckProc --
2720  *
2721  *      This procedure is invoked to perform consistency checks
2722  *      on toggle segments.
2723  *
2724  * Results:
2725  *      None.
2726  *
2727  * Side effects:
2728  *      If a consistency problem is found the procedure panics.
2729  *
2730  *--------------------------------------------------------------
2731  */
2732
2733 static void
2734 ToggleCheckProc(segPtr, linePtr)
2735     CkTextSegment *segPtr;              /* Segment to check. */
2736     CkTextLine *linePtr;                /* Line containing segment. */
2737 {
2738     register Summary *summaryPtr;
2739
2740     if (segPtr->size != 0) {
2741         panic("ToggleCheckProc: segment had non-zero size");
2742     }
2743     if (!segPtr->body.toggle.inNodeCounts) {
2744         panic("ToggleCheckProc: toggle counts not updated in nodes");
2745     }
2746     for (summaryPtr = linePtr->parentPtr->summaryPtr; ;
2747             summaryPtr = summaryPtr->nextPtr) {
2748         if (summaryPtr == NULL) {
2749             panic("ToggleCheckProc: tag not present in node");
2750         }
2751         if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) {
2752             break;
2753         }
2754     }
2755 }
2756 \f
2757 /*
2758  *----------------------------------------------------------------------
2759  *
2760  * CkBTreeCharsInLine --
2761  *
2762  *      This procedure returns a count of the number of characters
2763  *      in a given line.
2764  *
2765  * Results:
2766  *      The return value is the character count for linePtr.
2767  *
2768  * Side effects:
2769  *      None.
2770  *
2771  *----------------------------------------------------------------------
2772  */
2773
2774 int
2775 CkBTreeCharsInLine(linePtr)
2776     CkTextLine *linePtr;                /* Line whose characters should be
2777                                          * counted. */
2778 {
2779     CkTextSegment *segPtr;
2780     int count = 0;
2781
2782 #if CK_USE_UTF
2783     for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
2784         if (segPtr->typePtr == &ckTextCharType) {
2785             count += Tcl_NumUtfChars(segPtr->body.chars, segPtr->size);
2786         } else {
2787             count += segPtr->size;
2788         }
2789     }
2790 #else
2791     for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
2792         count += segPtr->size;
2793     }
2794 #endif
2795     return count;
2796 }