1 /*
2 * tkTextBTree.c --
3 *
4 * This file contains code that manages the B-tree representation of text
5 * for Tk's text widget and implements character and toggle segment
6 * types.
7 *
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 *
11 * See the file "license.terms" for information on usage and redistribution of
12 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
13 */
14
15 #include "tkInt.h"
16 #include "tkText.h"
17
18 /*
19 * Implementation notes:
20 *
21 * Most of this file is independent of the text widget implementation and
22 * representation now. Without much effort this could be developed further
23 * into a new Tcl object type of which the Tk text widget is one example of a
24 * client.
25 *
26 * The B-tree is set up with a dummy last line of text which must not be
27 * displayed, and must _never_ have a non-zero pixel count. This dummy line is
28 * a historical convenience to avoid other code having to deal with NULL
29 * TkTextLines. Since Tk 8.5, with pixel line height calculations and peer
30 * widgets, this dummy line is becoming somewhat of a liability, and special
31 * case code has been required to deal with it. It is probably a good idea to
32 * investigate removing the dummy line completely. This could result in an
33 * overall simplification (although it would require new special case code to
34 * deal with the fact that '.text index end' would then not really point to a
35 * valid line, rather it would point to the beginning of a non-existent line
36 * one beyond all current lines - we could perhaps define that as a
37 * TkTextIndex with a NULL TkTextLine ptr).
38 */
39
40 /*
41 * The data structure below keeps summary information about one tag as part of
42 * the tag information in a node.
43 */
44
45 typedef struct Summary {
46 TkTextTag *tagPtr; /* Handle for tag. */
47 int toggleCount; /* Number of transitions into or out of this
48 * tag that occur in the subtree rooted at
49 * this node. */
50 struct Summary *nextPtr; /* Next in list of all tags for same node, or
51 * NULL if at end of list. */
52 } Summary;
53
54 /*
55 * The data structure below defines a node in the B-tree.
56 */
57
58 typedef struct Node {
59 struct Node *parentPtr; /* Pointer to parent node, or NULL if this is
60 * the root. */
61 struct Node *nextPtr; /* Next in list of siblings with the same
62 * parent node, or NULL for end of list. */
63 Summary *summaryPtr; /* First in malloc-ed list of info about tags
64 * in this subtree (NULL if no tag info in the
65 * subtree). */
66 int level; /* Level of this node in the B-tree. 0 refers
67 * to the bottom of the tree (children are
68 * lines, not nodes). */
69 union { /* First in linked list of children. */
70 struct Node *nodePtr; /* Used if level > 0. */
71 TkTextLine *linePtr; /* Used if level == 0. */
72 } children;
73 int numChildren; /* Number of children of this node. */
74 int numLines; /* Total number of lines (leaves) in the
75 * subtree rooted here. */
76 int *numPixels; /* Array containing total number of vertical
77 * display pixels in the subtree rooted here,
78 * one entry for each peer widget. */
79 } Node;
80
81 /*
82 * Used to avoid having to allocate and deallocate arrays on the fly for
83 * commonly used functions. Must be > 0.
84 */
85
86 #define PIXEL_CLIENTS 5
87
88 /*
89 * Upper and lower bounds on how many children a node may have: rebalance when
90 * either of these limits is exceeded. MAX_CHILDREN should be twice
91 * MIN_CHILDREN and MIN_CHILDREN must be >= 2.
92 */
93
94 #define MAX_CHILDREN 12
95 #define MIN_CHILDREN 6
96
97 /*
98 * The data structure below defines an entire B-tree. Since text widgets are
99 * the only current B-tree clients, 'clients' and 'pixelReferences' are
100 * identical.
101 */
102
103 typedef struct BTree {
104 Node *rootPtr; /* Pointer to root of B-tree. */
105 int clients; /* Number of clients of this B-tree. */
106 int pixelReferences; /* Number of clients of this B-tree which care
107 * about pixel heights. */
108 int stateEpoch; /* Updated each time any aspect of the B-tree
109 * changes. */
110 TkSharedText *sharedTextPtr;/* Used to find tagTable in consistency
111 * checking code, and to access list of all
112 * B-tree clients. */
113 int startEndCount;
114 TkTextLine **startEnd;
115 TkText **startEndRef;
116 } BTree;
117
118 /*
119 * The structure below is used to pass information between
120 * TkBTreeGetTags and IncCount:
121 */
122
123 typedef struct TagInfo {
124 int numTags; /* Number of tags for which there is currently
125 * information in tags and counts. */
126 int arraySize; /* Number of entries allocated for tags and
127 * counts. */
128 TkTextTag **tagPtrs; /* Array of tags seen so far. Malloc-ed. */
129 int *counts; /* Toggle count (so far) for each entry in
130 * tags. Malloc-ed. */
131 } TagInfo;
132
133 /*
134 * Variable that indicates whether to enable consistency checks for debugging.
135 */
136
137 int tkBTreeDebug = 0;
138
139 /*
140 * Macros that determine how much space to allocate for new segments:
141 */
142
143 #define CSEG_SIZE(chars) ((unsigned) (Tk_Offset(TkTextSegment, body) \
144 + 1 + (chars)))
145 #define TSEG_SIZE ((unsigned) (Tk_Offset(TkTextSegment, body) \
146 + sizeof(TkTextToggle)))
147
148 /*
149 * Forward declarations for functions defined in this file:
150 */
151
152 static int AdjustPixelClient(BTree *treePtr, int defaultHeight,
153 Node *nodePtr, TkTextLine *start, TkTextLine *end,
154 int useReference, int newPixelReferences,
155 int *counting);
156 static void ChangeNodeToggleCount(Node *nodePtr,
157 TkTextTag *tagPtr, int delta);
158 static void CharCheckProc(TkTextSegment *segPtr,
159 TkTextLine *linePtr);
160 static int CharDeleteProc(TkTextSegment *segPtr,
161 TkTextLine *linePtr, int treeGone);
162 static TkTextSegment * CharCleanupProc(TkTextSegment *segPtr,
163 TkTextLine *linePtr);
164 static TkTextSegment * CharSplitProc(TkTextSegment *segPtr, int index);
165 static void CheckNodeConsistency(Node *nodePtr, int references);
166 static void CleanupLine(TkTextLine *linePtr);
167 static void DeleteSummaries(Summary *tagPtr);
168 static void DestroyNode(Node *nodePtr);
169 static TkTextSegment * FindTagEnd(TkTextBTree tree, TkTextTag *tagPtr,
170 TkTextIndex *indexPtr);
171 static void IncCount(TkTextTag *tagPtr, int inc,
172 TagInfo *tagInfoPtr);
173 static void Rebalance(BTree *treePtr, Node *nodePtr);
174 static void RecomputeNodeCounts(BTree *treePtr, Node *nodePtr);
175 static void RemovePixelClient(BTree *treePtr, Node *nodePtr,
176 int overwriteWithLast);
177 static TkTextSegment * SplitSeg(TkTextIndex *indexPtr);
178 static void ToggleCheckProc(TkTextSegment *segPtr,
179 TkTextLine *linePtr);
180 static TkTextSegment * ToggleCleanupProc(TkTextSegment *segPtr,
181 TkTextLine *linePtr);
182 static int ToggleDeleteProc(TkTextSegment *segPtr,
183 TkTextLine *linePtr, int treeGone);
184 static void ToggleLineChangeProc(TkTextSegment *segPtr,
185 TkTextLine *linePtr);
186 static TkTextSegment * FindTagStart(TkTextBTree tree, TkTextTag *tagPtr,
187 TkTextIndex *indexPtr);
188 static void AdjustStartEndRefs(BTree *treePtr, TkText *textPtr,
189 int action);
190
191 /*
192 * Actions for use by AdjustStartEndRefs
193 */
194
195 #define TEXT_ADD_REFS 1
196 #define TEXT_REMOVE_REFS 2
197
198 /*
199 * Type record for character segments:
200 */
201
202 const Tk_SegType tkTextCharType = {
203 "character", /* name */
204 0, /* leftGravity */
205 CharSplitProc, /* splitProc */
206 CharDeleteProc, /* deleteProc */
207 CharCleanupProc, /* cleanupProc */
208 NULL, /* lineChangeProc */
209 TkTextCharLayoutProc, /* layoutProc */
210 CharCheckProc /* checkProc */
211 };
212
213 /*
214 * Type record for segments marking the beginning of a tagged range:
215 */
216
217 const Tk_SegType tkTextToggleOnType = {
218 "toggleOn", /* name */
219 0, /* leftGravity */
220 NULL, /* splitProc */
221 ToggleDeleteProc, /* deleteProc */
222 ToggleCleanupProc, /* cleanupProc */
223 ToggleLineChangeProc, /* lineChangeProc */
224 NULL, /* layoutProc */
225 ToggleCheckProc /* checkProc */
226 };
227
228 /*
229 * Type record for segments marking the end of a tagged range:
230 */
231
232 const Tk_SegType tkTextToggleOffType = {
233 "toggleOff", /* name */
234 1, /* leftGravity */
235 NULL, /* splitProc */
236 ToggleDeleteProc, /* deleteProc */
237 ToggleCleanupProc, /* cleanupProc */
238 ToggleLineChangeProc, /* lineChangeProc */
239 NULL, /* layoutProc */
240 ToggleCheckProc /* checkProc */
241 };
242
243 /*
244 *----------------------------------------------------------------------
245 *
246 * TkBTreeCreate --
247 *
248 * This function is called to create a new text B-tree.
249 *
250 * Results:
251 * The return value is a pointer to a new B-tree containing one line with
252 * nothing but a newline character.
253 *
254 * Side effects:
255 * Memory is allocated and initialized.
256 *
257 *----------------------------------------------------------------------
258 */
259
260 TkTextBTree
TkBTreeCreate(TkSharedText * sharedTextPtr)261 TkBTreeCreate(
262 TkSharedText *sharedTextPtr)
263 {
264 register BTree *treePtr;
265 register Node *rootPtr;
266 register TkTextLine *linePtr, *linePtr2;
267 register TkTextSegment *segPtr;
268
269 /*
270 * The tree will initially have two empty lines. The second line isn't
271 * actually part of the tree's contents, but its presence makes several
272 * operations easier. The tree will have one node, which is also the root
273 * of the tree.
274 */
275
276 rootPtr = (Node *) ckalloc(sizeof(Node));
277 linePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
278 linePtr2 = (TkTextLine *) ckalloc(sizeof(TkTextLine));
279
280 rootPtr->parentPtr = NULL;
281 rootPtr->nextPtr = NULL;
282 rootPtr->summaryPtr = NULL;
283 rootPtr->level = 0;
284 rootPtr->children.linePtr = linePtr;
285 rootPtr->numChildren = 2;
286 rootPtr->numLines = 2;
287
288 /*
289 * The tree currently has no registered clients, so all pixel count
290 * pointers are simply NULL.
291 */
292
293 rootPtr->numPixels = NULL;
294 linePtr->pixels = NULL;
295 linePtr2->pixels = NULL;
296
297 linePtr->parentPtr = rootPtr;
298 linePtr->nextPtr = linePtr2;
299 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
300 linePtr->segPtr = segPtr;
301 segPtr->typePtr = &tkTextCharType;
302 segPtr->nextPtr = NULL;
303 segPtr->size = 1;
304 segPtr->body.chars[0] = '\n';
305 segPtr->body.chars[1] = 0;
306
307 linePtr2->parentPtr = rootPtr;
308 linePtr2->nextPtr = NULL;
309 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
310 linePtr2->segPtr = segPtr;
311 segPtr->typePtr = &tkTextCharType;
312 segPtr->nextPtr = NULL;
313 segPtr->size = 1;
314 segPtr->body.chars[0] = '\n';
315 segPtr->body.chars[1] = 0;
316
317 treePtr = (BTree *) ckalloc(sizeof(BTree));
318 treePtr->sharedTextPtr = sharedTextPtr;
319 treePtr->rootPtr = rootPtr;
320 treePtr->clients = 0;
321 treePtr->stateEpoch = 0;
322 treePtr->pixelReferences = 0;
323 treePtr->startEndCount = 0;
324 treePtr->startEnd = NULL;
325 treePtr->startEndRef = NULL;
326
327 return (TkTextBTree) treePtr;
328 }
329
330 /*
331 *----------------------------------------------------------------------
332 *
333 * TkBTreeAddClient --
334 *
335 * This function is called to provide a client with access to a given
336 * B-tree. If the client wishes to make use of the B-tree's pixel height
337 * storage, caching and calculation mechanisms, then a non-negative
338 * 'defaultHeight' must be provided. In this case the return value is a
339 * pixel tree reference which must be provided in all of the B-tree API
340 * which refers to or modifies pixel heights:
341 *
342 * TkBTreeAdjustPixelHeight,
343 * TkBTreeFindPixelLine,
344 * TkBTreeNumPixels,
345 * TkBTreePixelsTo,
346 * (and two private functions AdjustPixelClient, RemovePixelClient).
347 *
348 * If this is not provided, then the above functions must never be called
349 * for this client.
350 *
351 * Results:
352 * The return value is the pixelReference used by the B-tree to refer to
353 * pixel counts for the new client. It should be stored by the caller. If
354 * defaultHeight was negative, then the return value will be -1.
355 *
356 * Side effects:
357 * Memory may be allocated and initialized.
358 *
359 *----------------------------------------------------------------------
360 */
361
362 void
TkBTreeAddClient(TkTextBTree tree,TkText * textPtr,int defaultHeight)363 TkBTreeAddClient(
364 TkTextBTree tree, /* B-tree to add a client to. */
365 TkText *textPtr, /* Client to add. */
366 int defaultHeight) /* Default line height for the new client, or
367 * -1 if no pixel heights are to be kept. */
368 {
369 register BTree *treePtr = (BTree *) tree;
370
371 if (treePtr == NULL) {
372 Tcl_Panic("NULL treePtr in TkBTreeAddClient");
373 }
374
375 if (textPtr->start != NULL || textPtr->end != NULL) {
376 AdjustStartEndRefs(treePtr, textPtr, TEXT_ADD_REFS);
377 }
378
379 if (defaultHeight >= 0) {
380 TkTextLine *end;
381 int counting = (textPtr->start == NULL ? 1 : 0);
382 int useReference = treePtr->pixelReferences;
383
384 /*
385 * We must set the 'end' value in AdjustPixelClient so that the last
386 * dummy line in the B-tree doesn't contain a pixel height.
387 */
388
389 end = textPtr->end;
390 if (end == NULL) {
391 end = TkBTreeFindLine(tree, NULL, TkBTreeNumLines(tree, NULL));
392 }
393 AdjustPixelClient(treePtr, defaultHeight, treePtr->rootPtr,
394 textPtr->start, end, useReference, useReference+1, &counting);
395
396 textPtr->pixelReference = useReference;
397 treePtr->pixelReferences++;
398 } else {
399 textPtr->pixelReference = -1;
400 }
401 treePtr->clients++;
402 }
403
404 /*
405 *----------------------------------------------------------------------
406 *
407 * TkBTreeClientRangeChanged --
408 *
409 * Called when the -startline or -endline options of a text widget client
410 * of the B-tree have changed.
411 *
412 * Results:
413 * None.
414 *
415 * Side effects:
416 * Lots of processing of the B-tree is done, with potential for memory to
417 * be allocated and initialized for the pixel heights of the widget.
418 *
419 *----------------------------------------------------------------------
420 */
421
422 void
TkBTreeClientRangeChanged(TkText * textPtr,int defaultHeight)423 TkBTreeClientRangeChanged(
424 TkText *textPtr, /* Client whose start, end have changed. */
425 int defaultHeight) /* Default line height for the new client, or
426 * -1 if no pixel heights are to be kept. */
427 {
428 TkTextLine *end;
429 BTree *treePtr = (BTree *) textPtr->sharedTextPtr->tree;
430
431 int counting = (textPtr->start == NULL ? 1 : 0);
432 int useReference = textPtr->pixelReference;
433
434 AdjustStartEndRefs(treePtr, textPtr, TEXT_ADD_REFS | TEXT_REMOVE_REFS);
435
436 /*
437 * We must set the 'end' value in AdjustPixelClient so that the last dummy
438 * line in the B-tree doesn't contain a pixel height.
439 */
440
441 end = textPtr->end;
442 if (end == NULL) {
443 end = TkBTreeFindLine(textPtr->sharedTextPtr->tree,
444 NULL, TkBTreeNumLines(textPtr->sharedTextPtr->tree, NULL));
445 }
446 AdjustPixelClient(treePtr, defaultHeight, treePtr->rootPtr,
447 textPtr->start, end, useReference, treePtr->pixelReferences,
448 &counting);
449 }
450
451 /*
452 *----------------------------------------------------------------------
453 *
454 * TkBTreeDestroy --
455 *
456 * Delete a B-tree, recycling all of the storage it contains.
457 *
458 * Results:
459 * The tree is deleted, so 'tree' should never again be used.
460 *
461 * Side effects:
462 * Memory is freed.
463 *
464 *----------------------------------------------------------------------
465 */
466
467 void
TkBTreeDestroy(TkTextBTree tree)468 TkBTreeDestroy(
469 TkTextBTree tree) /* Tree to clean up. */
470 {
471 BTree *treePtr = (BTree *) tree;
472
473 /*
474 * There's no need to loop over each client of the tree, calling
475 * 'TkBTreeRemoveClient', since the 'DestroyNode' will clean everything up
476 * itself.
477 */
478
479 DestroyNode(treePtr->rootPtr);
480 if (treePtr->startEnd != NULL) {
481 ckfree((char *) treePtr->startEnd);
482 ckfree((char *) treePtr->startEndRef);
483 }
484 ckfree((char *) treePtr);
485 }
486
487 /*
488 *----------------------------------------------------------------------
489 *
490 * TkBTreeEpoch --
491 *
492 * Return the epoch for the B-tree. This number is incremented any time
493 * anything changes in the tree.
494 *
495 * Results:
496 * The epoch number.
497 *
498 * Side effects:
499 * None.
500 *
501 *----------------------------------------------------------------------
502 */
503
504 int
TkBTreeEpoch(TkTextBTree tree)505 TkBTreeEpoch(
506 TkTextBTree tree) /* Tree to get epoch for. */
507 {
508 BTree *treePtr = (BTree *) tree;
509 return treePtr->stateEpoch;
510 }
511
512 /*
513 *----------------------------------------------------------------------
514 *
515 * TkBTreeRemoveClient --
516 *
517 * Remove a client widget from its B-tree, cleaning up the pixel arrays
518 * which it uses if necessary. If this is the last such widget, we also
519 * destroy the whole tree.
520 *
521 * Results:
522 * All tree-specific aspects of the given client are deleted. If no more
523 * references exist, then the given tree is also deleted (in which case
524 * 'tree' must not be used again).
525 *
526 * Side effects:
527 * Memory may be freed.
528 *
529 *----------------------------------------------------------------------
530 */
531
532 void
TkBTreeRemoveClient(TkTextBTree tree,TkText * textPtr)533 TkBTreeRemoveClient(
534 TkTextBTree tree, /* Tree to remove client from. */
535 TkText *textPtr) /* Client to remove. */
536 {
537 BTree *treePtr = (BTree *) tree;
538 int pixelReference = textPtr->pixelReference;
539
540 if (treePtr->clients == 1) {
541 /*
542 * The last reference to the tree.
543 */
544
545 DestroyNode(treePtr->rootPtr);
546 ckfree((char *) treePtr);
547 return;
548 } else if (pixelReference == -1) {
549 /*
550 * A client which doesn't care about pixels.
551 */
552
553 treePtr->clients--;
554 } else {
555 /*
556 * Clean up pixel data for the given reference.
557 */
558
559 if (pixelReference == (treePtr->pixelReferences-1)) {
560 /*
561 * The widget we're removing has the last index, so deletion is
562 * easier.
563 */
564
565 RemovePixelClient(treePtr, treePtr->rootPtr, -1);
566 } else {
567 TkText *adjustPtr;
568
569 RemovePixelClient(treePtr, treePtr->rootPtr, pixelReference);
570
571 /*
572 * Now we need to adjust the 'pixelReference' of the peer widget
573 * whose storage we've just moved.
574 */
575
576 adjustPtr = treePtr->sharedTextPtr->peers;
577 while (adjustPtr != NULL) {
578 if (adjustPtr->pixelReference == treePtr->pixelReferences-1) {
579 adjustPtr->pixelReference = pixelReference;
580 break;
581 }
582 adjustPtr = adjustPtr->next;
583 }
584 if (adjustPtr == NULL) {
585 Tcl_Panic("Couldn't find text widget with correct reference");
586 }
587 }
588 treePtr->pixelReferences--;
589 treePtr->clients--;
590 }
591
592 if (textPtr->start != NULL || textPtr->end != NULL) {
593 AdjustStartEndRefs(treePtr, textPtr, TEXT_REMOVE_REFS);
594 }
595 }
596
597 /*
598 *----------------------------------------------------------------------
599 *
600 * AdjustStartEndRefs --
601 *
602 * Modify B-tree's cache of start, end lines for the given text widget.
603 *
604 * Results:
605 * None.
606 *
607 * Side effects:
608 * The number of cached items may change (treePtr->startEndCount).
609 *
610 *----------------------------------------------------------------------
611 */
612
613 static void
AdjustStartEndRefs(BTree * treePtr,TkText * textPtr,int action)614 AdjustStartEndRefs(
615 BTree *treePtr, /* The entire B-tree. */
616 TkText *textPtr, /* The text widget for which we want to adjust
617 * it's start and end cache. */
618 int action) /* Action to perform. */
619 {
620 if (action & TEXT_REMOVE_REFS) {
621 int i = 0;
622 int count = 0;
623
624 while (i < treePtr->startEndCount) {
625 if (i != count) {
626 treePtr->startEnd[count] = treePtr->startEnd[i];
627 treePtr->startEndRef[count] = treePtr->startEndRef[i];
628 }
629 if (treePtr->startEndRef[i] != textPtr) {
630 count++;
631 }
632 i++;
633 }
634 treePtr->startEndCount = count;
635 treePtr->startEnd = (TkTextLine **)
636 ckrealloc((char *) treePtr->startEnd,
637 sizeof(TkTextLine *) * count);
638 treePtr->startEndRef = (TkText **)
639 ckrealloc((char *) treePtr->startEndRef,
640 sizeof(TkText *) * count);
641 }
642 if ((action & TEXT_ADD_REFS)
643 && (textPtr->start != NULL || textPtr->end != NULL)) {
644 int count;
645
646 if (textPtr->start != NULL) {
647 treePtr->startEndCount++;
648 }
649 if (textPtr->end != NULL) {
650 treePtr->startEndCount++;
651 }
652
653 count = treePtr->startEndCount;
654
655 treePtr->startEnd = (TkTextLine **)
656 ckrealloc((char *) treePtr->startEnd,
657 sizeof(TkTextLine *) * count);
658 treePtr->startEndRef = (TkText **)
659 ckrealloc((char *) treePtr->startEndRef,
660 sizeof(TkText *) * count);
661
662 if (textPtr->start != NULL) {
663 count--;
664 treePtr->startEnd[count] = textPtr->start;
665 treePtr->startEndRef[count] = textPtr;
666 }
667 if (textPtr->end != NULL) {
668 count--;
669 treePtr->startEnd[count] = textPtr->end;
670 treePtr->startEndRef[count] = textPtr;
671 }
672 }
673 }
674
675 /*
676 *----------------------------------------------------------------------
677 *
678 * AdjustPixelClient --
679 *
680 * Utility function used to update all data structures for the existence
681 * of a new peer widget based on this B-tree, or for the modification of
682 * the start, end lines of an existing peer widget.
683 *
684 * Immediately _after_ calling this, treePtr->pixelReferences and
685 * treePtr->clients should be adjusted if needed (i.e. if this is a new
686 * peer).
687 *
688 * Results:
689 * None.
690 *
691 * Side effects:
692 * All the storage for Nodes and TkTextLines in the tree may be adjusted.
693 *
694 *----------------------------------------------------------------------
695 */
696
697 static int
AdjustPixelClient(BTree * treePtr,int defaultHeight,Node * nodePtr,TkTextLine * start,TkTextLine * end,int useReference,int newPixelReferences,int * counting)698 AdjustPixelClient(
699 BTree *treePtr, /* Pointer to tree. */
700 int defaultHeight, /* Default pixel line height, which can be
701 * zero. */
702 Node *nodePtr, /* Adjust from this node downwards. */
703 TkTextLine *start, /* First line for this pixel client. */
704 TkTextLine *end, /* Last line for this pixel client. */
705 int useReference, /* pixel reference for the client we are
706 * adding or changing. */
707 int newPixelReferences, /* New number of pixel references to this
708 * B-tree. */
709 int *counting) /* References an integer which is zero if
710 * we're outside the relevant range for this
711 * client, and 1 if we're inside. */
712 {
713 int pixelCount = 0;
714
715 /*
716 * Traverse entire tree down from nodePtr, reallocating pixel structures
717 * for each Node and TkTextLine, adding room for the new peer's pixel
718 * information (1 extra int per Node, 2 extra ints per TkTextLine). Also
719 * copy the information from the last peer into the new space (so it
720 * contains something sensible).
721 */
722
723 if (nodePtr->level != 0) {
724 Node *loopPtr = nodePtr->children.nodePtr;
725
726 while (loopPtr != NULL) {
727 pixelCount += AdjustPixelClient(treePtr, defaultHeight, loopPtr,
728 start, end, useReference, newPixelReferences, counting);
729 loopPtr = loopPtr->nextPtr;
730 }
731 } else {
732 register TkTextLine *linePtr = nodePtr->children.linePtr;
733
734 while (linePtr != NULL) {
735 if (!*counting && (linePtr == start)) {
736 *counting = 1;
737 }
738 if (*counting && (linePtr == end)) {
739 *counting = 0;
740 }
741 if (newPixelReferences != treePtr->pixelReferences) {
742 linePtr->pixels = (int *) ckrealloc((char *) linePtr->pixels,
743 sizeof(int) * 2 * newPixelReferences);
744 }
745
746 /*
747 * Notice that for the very last line, we are never counting and
748 * therefore this always has a height of 0 and an epoch of 1.
749 */
750
751 linePtr->pixels[2*useReference] = (*counting ? defaultHeight : 0);
752 linePtr->pixels[2*useReference+1] = (*counting ? 0 : 1);
753 pixelCount += linePtr->pixels[2*useReference];
754
755 linePtr = linePtr->nextPtr;
756 }
757 }
758 if (newPixelReferences != treePtr->pixelReferences) {
759 nodePtr->numPixels = (int *) ckrealloc((char *) nodePtr->numPixels,
760 sizeof(int) * newPixelReferences);
761 }
762 nodePtr->numPixels[useReference] = pixelCount;
763 return pixelCount;
764 }
765
766 /*
767 *----------------------------------------------------------------------
768 *
769 * RemovePixelClient --
770 *
771 * Utility function used to update all data structures for the removal of
772 * a peer widget which used to be based on this B-tree.
773 *
774 * Immediately _after_ calling this, treePtr->clients should be
775 * decremented.
776 *
777 * Results:
778 * None.
779 *
780 * Side effects:
781 * All the storage for Nodes and TkTextLines in the tree may be adjusted.
782 *
783 *----------------------------------------------------------------------
784 */
785
786 static void
RemovePixelClient(BTree * treePtr,Node * nodePtr,int overwriteWithLast)787 RemovePixelClient(
788 BTree *treePtr, /* Pointer to tree. */
789 Node *nodePtr, /* Adjust from this node downwards. */
790 int overwriteWithLast) /* Over-write this peer widget's information
791 * with the last one. */
792 {
793 /*
794 * Traverse entire tree down from nodePtr, reallocating pixel structures
795 * for each Node and TkTextLine, removing space allocated for one peer. If
796 * 'overwriteWithLast' is not -1, then copy the information which was in
797 * the last slot on top of one of the others (i.e. it's not the last one
798 * we're deleting).
799 */
800
801 if (overwriteWithLast != -1) {
802 nodePtr->numPixels[overwriteWithLast] =
803 nodePtr->numPixels[treePtr->pixelReferences-1];
804 }
805 if (treePtr->pixelReferences == 1) {
806 nodePtr->numPixels = NULL;
807 } else {
808 nodePtr->numPixels = (int *) ckrealloc((char *) nodePtr->numPixels,
809 sizeof(int) * (treePtr->pixelReferences - 1));
810 }
811 if (nodePtr->level != 0) {
812 nodePtr = nodePtr->children.nodePtr;
813 while (nodePtr != NULL) {
814 RemovePixelClient(treePtr, nodePtr, overwriteWithLast);
815 nodePtr = nodePtr->nextPtr;
816 }
817 } else {
818 register TkTextLine *linePtr = nodePtr->children.linePtr;
819 while (linePtr != NULL) {
820 if (overwriteWithLast != -1) {
821 linePtr->pixels[2*overwriteWithLast] =
822 linePtr->pixels[2*(treePtr->pixelReferences-1)];
823 linePtr->pixels[1+2*overwriteWithLast] =
824 linePtr->pixels[1+2*(treePtr->pixelReferences-1)];
825 }
826 if (treePtr->pixelReferences == 1) {
827 linePtr->pixels = NULL;
828 } else {
829 linePtr->pixels = (int *) ckrealloc((char *) linePtr->pixels,
830 sizeof(int) * 2 * (treePtr->pixelReferences-1));
831 }
832 linePtr = linePtr->nextPtr;
833 }
834 }
835 }
836
837 /*
838 *----------------------------------------------------------------------
839 *
840 * DestroyNode --
841 *
842 * This is a recursive utility function used during the deletion of a
843 * B-tree.
844 *
845 * Results:
846 * None.
847 *
848 * Side effects:
849 * All the storage for nodePtr and its descendants is freed.
850 *
851 *----------------------------------------------------------------------
852 */
853
854 static void
DestroyNode(register Node * nodePtr)855 DestroyNode(
856 register Node *nodePtr) /* Destroy from this node downwards. */
857 {
858 if (nodePtr->level == 0) {
859 TkTextLine *linePtr;
860 TkTextSegment *segPtr;
861
862 while (nodePtr->children.linePtr != NULL) {
863 linePtr = nodePtr->children.linePtr;
864 nodePtr->children.linePtr = linePtr->nextPtr;
865 while (linePtr->segPtr != NULL) {
866 segPtr = linePtr->segPtr;
867 linePtr->segPtr = segPtr->nextPtr;
868 (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
869 }
870 ckfree((char *) linePtr->pixels);
871 ckfree((char *) linePtr);
872 }
873 } else {
874 register Node *childPtr;
875
876 while (nodePtr->children.nodePtr != NULL) {
877 childPtr = nodePtr->children.nodePtr;
878 nodePtr->children.nodePtr = childPtr->nextPtr;
879 DestroyNode(childPtr);
880 }
881 }
882 DeleteSummaries(nodePtr->summaryPtr);
883 ckfree((char *) nodePtr->numPixels);
884 ckfree((char *) nodePtr);
885 }
886
887 /*
888 *----------------------------------------------------------------------
889 *
890 * DeleteSummaries --
891 *
892 * Free up all of the memory in a list of tag summaries associated with a
893 * node.
894 *
895 * Results:
896 * None.
897 *
898 * Side effects:
899 * Storage is released.
900 *
901 *----------------------------------------------------------------------
902 */
903
904 static void
DeleteSummaries(register Summary * summaryPtr)905 DeleteSummaries(
906 register Summary *summaryPtr)
907 /* First in list of node's tag summaries. */
908 {
909 register Summary *nextPtr;
910
911 while (summaryPtr != NULL) {
912 nextPtr = summaryPtr->nextPtr;
913 ckfree((char *) summaryPtr);
914 summaryPtr = nextPtr;
915 }
916 }
917
918 /*
919 *----------------------------------------------------------------------
920 *
921 * TkBTreeAdjustPixelHeight --
922 *
923 * Adjust the pixel height of a given logical line to the specified
924 * value.
925 *
926 * Results:
927 * Total number of valid pixels currently known in the tree.
928 *
929 * Side effects:
930 * Updates overall data structures so pixel height count is consistent.
931 *
932 *----------------------------------------------------------------------
933 */
934
935 int
TkBTreeAdjustPixelHeight(const TkText * textPtr,register TkTextLine * linePtr,int newPixelHeight,int mergedLogicalLines)936 TkBTreeAdjustPixelHeight(
937 const TkText *textPtr, /* Client of the B-tree. */
938 register TkTextLine *linePtr,
939 /* The logical line to update. */
940 int newPixelHeight, /* The line's known height in pixels. */
941 int mergedLogicalLines) /* The number of extra logical lines which
942 * have been merged with this one (due to
943 * elided eols). They will have their pixel
944 * height set to zero, and the total pixel
945 * height associated with the given
946 * linePtr. */
947 {
948 register Node *nodePtr;
949 int changeToPixelCount; /* Counts change to total number of pixels in
950 * file. */
951 int pixelReference = textPtr->pixelReference;
952
953 changeToPixelCount = newPixelHeight - linePtr->pixels[2 * pixelReference];
954
955 /*
956 * Increment the pixel counts in all the parent nodes of the current line,
957 * then rebalance the tree if necessary.
958 */
959
960 nodePtr = linePtr->parentPtr;
961 nodePtr->numPixels[pixelReference] += changeToPixelCount;
962
963 while (nodePtr->parentPtr != NULL) {
964 nodePtr = nodePtr->parentPtr;
965 nodePtr->numPixels[pixelReference] += changeToPixelCount;
966 }
967
968 linePtr->pixels[2 * pixelReference] = newPixelHeight;
969
970 /*
971 * Any merged logical lines must have their height set to zero.
972 */
973
974 while (mergedLogicalLines-- > 0) {
975 linePtr = TkBTreeNextLine(textPtr, linePtr);
976 TkBTreeAdjustPixelHeight(textPtr, linePtr, 0, 0);
977 }
978
979 /*
980 * Return total number of pixels in the tree.
981 */
982
983 return nodePtr->numPixels[pixelReference];
984 }
985
986 /*
987 *----------------------------------------------------------------------
988 *
989 * TkBTreeInsertChars --
990 *
991 * Insert characters at a given position in a B-tree.
992 *
993 * Results:
994 * None.
995 *
996 * Side effects:
997 * Characters are added to the B-tree at the given position. If the
998 * string contains newlines, new lines will be added, which could cause
999 * the structure of the B-tree to change.
1000 *
1001 *----------------------------------------------------------------------
1002 */
1003
1004 void
TkBTreeInsertChars(TkTextBTree tree,register TkTextIndex * indexPtr,const char * string)1005 TkBTreeInsertChars(
1006 TkTextBTree tree, /* Tree to insert into. */
1007 register TkTextIndex *indexPtr,
1008 /* Indicates where to insert text. When the
1009 * function returns, this index is no longer
1010 * valid because of changes to the segment
1011 * structure. */
1012 const char *string) /* Pointer to bytes to insert (may contain
1013 * newlines, must be null-terminated). */
1014 {
1015 register Node *nodePtr;
1016 register TkTextSegment *prevPtr;
1017 /* The segment just before the first new
1018 * segment (NULL means new segment is at
1019 * beginning of line). */
1020 TkTextSegment *curPtr; /* Current segment; new characters are
1021 * inserted just after this one. NULL means
1022 * insert at beginning of line. */
1023 TkTextLine *linePtr; /* Current line (new segments are added to
1024 * this line). */
1025 register TkTextSegment *segPtr;
1026 TkTextLine *newLinePtr;
1027 int chunkSize; /* # characters in current chunk. */
1028 register const char *eol; /* Pointer to character just after last one in
1029 * current chunk. */
1030 int changeToLineCount; /* Counts change to total number of lines in
1031 * file. */
1032 int *changeToPixelCount; /* Counts change to total number of pixels in
1033 * file. */
1034 int ref;
1035 int pixels[PIXEL_CLIENTS];
1036
1037 BTree *treePtr = (BTree *) tree;
1038 treePtr->stateEpoch++;
1039 prevPtr = SplitSeg(indexPtr);
1040 linePtr = indexPtr->linePtr;
1041 curPtr = prevPtr;
1042
1043 /*
1044 * Chop the string up into lines and create a new segment for each line,
1045 * plus a new line for the leftovers from the previous line.
1046 */
1047
1048 changeToLineCount = 0;
1049 if (treePtr->pixelReferences > PIXEL_CLIENTS) {
1050 changeToPixelCount = (int *)
1051 ckalloc(sizeof(int) * treePtr->pixelReferences);
1052 } else {
1053 changeToPixelCount = pixels;
1054 }
1055 for (ref = 0; ref < treePtr->pixelReferences; ref++) {
1056 changeToPixelCount[ref] = 0;
1057 }
1058
1059 while (*string != 0) {
1060 for (eol = string; *eol != 0; eol++) {
1061 if (*eol == '\n') {
1062 eol++;
1063 break;
1064 }
1065 }
1066 chunkSize = eol-string;
1067 segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
1068 segPtr->typePtr = &tkTextCharType;
1069 if (curPtr == NULL) {
1070 segPtr->nextPtr = linePtr->segPtr;
1071 linePtr->segPtr = segPtr;
1072 } else {
1073 segPtr->nextPtr = curPtr->nextPtr;
1074 curPtr->nextPtr = segPtr;
1075 }
1076 segPtr->size = chunkSize;
1077 memcpy(segPtr->body.chars, string, (size_t) chunkSize);
1078 segPtr->body.chars[chunkSize] = 0;
1079
1080 if (eol[-1] != '\n') {
1081 break;
1082 }
1083
1084 /*
1085 * The chunk ended with a newline, so create a new TkTextLine and move
1086 * the remainder of the old line to it.
1087 */
1088
1089 newLinePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
1090 newLinePtr->pixels = (int *)
1091 ckalloc(sizeof(int) * 2 * treePtr->pixelReferences);
1092
1093 newLinePtr->parentPtr = linePtr->parentPtr;
1094 newLinePtr->nextPtr = linePtr->nextPtr;
1095 linePtr->nextPtr = newLinePtr;
1096 newLinePtr->segPtr = segPtr->nextPtr;
1097
1098 /*
1099 * Set up a starting default height, which will be re-adjusted later.
1100 * We need to do this for each referenced widget.
1101 */
1102
1103 for (ref = 0; ref < treePtr->pixelReferences; ref++) {
1104 newLinePtr->pixels[2 * ref] = linePtr->pixels[2 * ref];
1105 newLinePtr->pixels[2 * ref + 1] = 0;
1106 changeToPixelCount[ref] += newLinePtr->pixels[2 * ref];
1107 }
1108
1109 segPtr->nextPtr = NULL;
1110 linePtr = newLinePtr;
1111 curPtr = NULL;
1112 changeToLineCount++;
1113
1114 string = eol;
1115 }
1116
1117 /*
1118 * I don't believe it's possible for either of the two lines passed to
1119 * this function to be the last line of text, but the function is robust
1120 * to that case anyway. (We must never re-calculate the line height of
1121 * the last line).
1122 */
1123
1124 TkTextInvalidateLineMetrics(treePtr->sharedTextPtr, NULL,
1125 indexPtr->linePtr, changeToLineCount, TK_TEXT_INVALIDATE_INSERT);
1126
1127 /*
1128 * Cleanup the starting line for the insertion, plus the ending line if
1129 * it's different.
1130 */
1131
1132 CleanupLine(indexPtr->linePtr);
1133 if (linePtr != indexPtr->linePtr) {
1134 CleanupLine(linePtr);
1135 }
1136
1137 /*
1138 * Increment the line and pixel counts in all the parent nodes of the
1139 * insertion point, then rebalance the tree if necessary.
1140 */
1141
1142 for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
1143 nodePtr = nodePtr->parentPtr) {
1144 nodePtr->numLines += changeToLineCount;
1145 for (ref = 0; ref < treePtr->pixelReferences; ref++) {
1146 nodePtr->numPixels[ref] += changeToPixelCount[ref];
1147 }
1148 }
1149 if (treePtr->pixelReferences > PIXEL_CLIENTS) {
1150 ckfree((char *) changeToPixelCount);
1151 }
1152
1153 nodePtr = linePtr->parentPtr;
1154 nodePtr->numChildren += changeToLineCount;
1155 if (nodePtr->numChildren > MAX_CHILDREN) {
1156 Rebalance(treePtr, nodePtr);
1157 }
1158
1159 if (tkBTreeDebug) {
1160 TkBTreeCheck(indexPtr->tree);
1161 }
1162 }
1163
1164 /*
1165 *--------------------------------------------------------------
1166 *
1167 * SplitSeg --
1168 *
1169 * This function is called before adding or deleting segments. It does
1170 * three things: (a) it finds the segment containing indexPtr; (b) if
1171 * there are several such segments (because some segments have zero
1172 * length) then it picks the first segment that does not have left
1173 * gravity; (c) if the index refers to the middle of a segment then it
1174 * splits the segment so that the index now refers to the beginning of a
1175 * segment.
1176 *
1177 * Results:
1178 * The return value is a pointer to the segment just before the segment
1179 * corresponding to indexPtr (as described above). If the segment
1180 * corresponding to indexPtr is the first in its line then the return
1181 * value is NULL.
1182 *
1183 * Side effects:
1184 * The segment referred to by indexPtr is split unless indexPtr refers to
1185 * its first character.
1186 *
1187 *--------------------------------------------------------------
1188 */
1189
1190 static TkTextSegment *
SplitSeg(TkTextIndex * indexPtr)1191 SplitSeg(
1192 TkTextIndex *indexPtr) /* Index identifying position at which to
1193 * split a segment. */
1194 {
1195 TkTextSegment *prevPtr, *segPtr;
1196 TkTextLine *linePtr;
1197 int count = indexPtr->byteIndex;
1198
1199 linePtr = indexPtr->linePtr;
1200 prevPtr = NULL;
1201 segPtr = linePtr->segPtr;
1202
1203 while (segPtr != NULL) {
1204 if (segPtr->size > count) {
1205 if (count == 0) {
1206 return prevPtr;
1207 }
1208 segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
1209 if (prevPtr == NULL) {
1210 indexPtr->linePtr->segPtr = segPtr;
1211 } else {
1212 prevPtr->nextPtr = segPtr;
1213 }
1214 return segPtr;
1215 } else if ((segPtr->size == 0) && (count == 0)
1216 && !segPtr->typePtr->leftGravity) {
1217 return prevPtr;
1218 }
1219
1220 count -= segPtr->size;
1221 prevPtr = segPtr;
1222 segPtr = segPtr->nextPtr;
1223 if (segPtr == NULL) {
1224 /*
1225 * Two logical lines merged into one display line through eliding
1226 * of a newline.
1227 */
1228
1229 linePtr = TkBTreeNextLine(NULL, linePtr);
1230 if (linePtr == NULL) {
1231 /*
1232 * Reached end of the text.
1233 */
1234 }
1235 segPtr = linePtr->segPtr;
1236 }
1237 }
1238 Tcl_Panic("SplitSeg reached end of line!");
1239 return NULL;
1240 }
1241
1242 /*
1243 *--------------------------------------------------------------
1244 *
1245 * CleanupLine --
1246 *
1247 * This function is called after modifications have been made to a line.
1248 * It scans over all of the segments in the line, giving each a chance to
1249 * clean itself up, e.g. by merging with the following segments, updating
1250 * internal information, etc.
1251 *
1252 * Results:
1253 * None.
1254 *
1255 * Side effects:
1256 * Depends on what the segment-specific cleanup functions do.
1257 *
1258 *--------------------------------------------------------------
1259 */
1260
1261 static void
CleanupLine(TkTextLine * linePtr)1262 CleanupLine(
1263 TkTextLine *linePtr) /* Line to be cleaned up. */
1264 {
1265 TkTextSegment *segPtr, **prevPtrPtr;
1266 int anyChanges;
1267
1268 /*
1269 * Make a pass over all of the segments in the line, giving each a chance
1270 * to clean itself up. This could potentially change the structure of the
1271 * line, e.g. by merging two segments together or having two segments
1272 * cancel themselves; if so, then repeat the whole process again, since
1273 * the first structure change might make other structure changes possible.
1274 * Repeat until eventually there are no changes.
1275 */
1276
1277 while (1) {
1278 anyChanges = 0;
1279 for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
1280 segPtr != NULL;
1281 prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
1282 if (segPtr->typePtr->cleanupProc != NULL) {
1283 *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
1284 if (segPtr != *prevPtrPtr) {
1285 anyChanges = 1;
1286 }
1287 }
1288 }
1289 if (!anyChanges) {
1290 break;
1291 }
1292 }
1293 }
1294
1295 /*
1296 *----------------------------------------------------------------------
1297 *
1298 * TkBTreeDeleteIndexRange --
1299 *
1300 * Delete a range of characters from a B-tree. The caller must make sure
1301 * that the final newline of the B-tree is never deleted.
1302 *
1303 * Results:
1304 * None.
1305 *
1306 * Side effects:
1307 * Information is deleted from the B-tree. This can cause the internal
1308 * structure of the B-tree to change. Note: because of changes to the
1309 * B-tree structure, the indices pointed to by index1Ptr and index2Ptr
1310 * should not be used after this function returns.
1311 *
1312 *----------------------------------------------------------------------
1313 */
1314
1315 void
TkBTreeDeleteIndexRange(TkTextBTree tree,register TkTextIndex * index1Ptr,register TkTextIndex * index2Ptr)1316 TkBTreeDeleteIndexRange(
1317 TkTextBTree tree, /* Tree to delete from. */
1318 register TkTextIndex *index1Ptr,
1319 /* Indicates first character that is to be
1320 * deleted. */
1321 register TkTextIndex *index2Ptr)
1322 /* Indicates character just after the last one
1323 * that is to be deleted. */
1324 {
1325 TkTextSegment *prevPtr; /* The segment just before the start of the
1326 * deletion range. */
1327 TkTextSegment *lastPtr; /* The segment just after the end of the
1328 * deletion range. */
1329 TkTextSegment *segPtr, *nextPtr;
1330 TkTextLine *curLinePtr;
1331 Node *curNodePtr, *nodePtr;
1332 int changeToLineCount = 0;
1333 int ref;
1334 BTree *treePtr = (BTree *) tree;
1335
1336 treePtr->stateEpoch++;
1337
1338 /*
1339 * Tricky point: split at index2Ptr first; otherwise the split at
1340 * index2Ptr may invalidate segPtr and/or prevPtr.
1341 */
1342
1343 lastPtr = SplitSeg(index2Ptr);
1344 if (lastPtr != NULL) {
1345 lastPtr = lastPtr->nextPtr;
1346 } else {
1347 lastPtr = index2Ptr->linePtr->segPtr;
1348 }
1349 prevPtr = SplitSeg(index1Ptr);
1350 if (prevPtr != NULL) {
1351 segPtr = prevPtr->nextPtr;
1352 prevPtr->nextPtr = lastPtr;
1353 } else {
1354 segPtr = index1Ptr->linePtr->segPtr;
1355 index1Ptr->linePtr->segPtr = lastPtr;
1356 }
1357
1358 /*
1359 * Delete all of the segments between prevPtr and lastPtr.
1360 */
1361
1362 curLinePtr = index1Ptr->linePtr;
1363
1364 curNodePtr = curLinePtr->parentPtr;
1365 while (segPtr != lastPtr) {
1366 if (segPtr == NULL) {
1367 TkTextLine *nextLinePtr;
1368
1369 /*
1370 * We just ran off the end of a line. First find the next line,
1371 * then go back to the old line and delete it (unless it's the
1372 * starting line for the range).
1373 */
1374
1375 nextLinePtr = TkBTreeNextLine(NULL, curLinePtr);
1376 if (curLinePtr != index1Ptr->linePtr) {
1377 if (curNodePtr == index1Ptr->linePtr->parentPtr) {
1378 index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
1379 } else {
1380 curNodePtr->children.linePtr = curLinePtr->nextPtr;
1381 }
1382 for (nodePtr = curNodePtr; nodePtr != NULL;
1383 nodePtr = nodePtr->parentPtr) {
1384 nodePtr->numLines--;
1385 for (ref = 0; ref < treePtr->pixelReferences; ref++) {
1386 nodePtr->numPixels[ref] -= curLinePtr->pixels[2*ref];
1387 }
1388 }
1389 changeToLineCount++;
1390 curNodePtr->numChildren--;
1391
1392 /*
1393 * Check if we need to adjust any partial clients.
1394 */
1395
1396 if (treePtr->startEnd != NULL) {
1397 int checkCount = 0;
1398
1399 while (checkCount < treePtr->startEndCount) {
1400 if (treePtr->startEnd[checkCount] == curLinePtr) {
1401 TkText *peer = treePtr->startEndRef[checkCount];
1402
1403 /*
1404 * We're deleting a line which is the start or end
1405 * of a current client. This means we need to
1406 * adjust that client.
1407 */
1408
1409 treePtr->startEnd[checkCount] = nextLinePtr;
1410 if (peer->start == curLinePtr) {
1411 peer->start = nextLinePtr;
1412 }
1413 if (peer->end == curLinePtr) {
1414 peer->end = nextLinePtr;
1415 }
1416 }
1417 checkCount++;
1418 }
1419 }
1420 ckfree((char *) curLinePtr->pixels);
1421 ckfree((char *) curLinePtr);
1422 }
1423 curLinePtr = nextLinePtr;
1424 segPtr = curLinePtr->segPtr;
1425
1426 /*
1427 * If the node is empty then delete it and its parents recursively
1428 * upwards until a non-empty node is found.
1429 */
1430
1431 while (curNodePtr->numChildren == 0) {
1432 Node *parentPtr;
1433
1434 parentPtr = curNodePtr->parentPtr;
1435 if (parentPtr->children.nodePtr == curNodePtr) {
1436 parentPtr->children.nodePtr = curNodePtr->nextPtr;
1437 } else {
1438 Node *prevNodePtr = parentPtr->children.nodePtr;
1439 while (prevNodePtr->nextPtr != curNodePtr) {
1440 prevNodePtr = prevNodePtr->nextPtr;
1441 }
1442 prevNodePtr->nextPtr = curNodePtr->nextPtr;
1443 }
1444 parentPtr->numChildren--;
1445 ckfree((char *) curNodePtr);
1446 curNodePtr = parentPtr;
1447 }
1448 curNodePtr = curLinePtr->parentPtr;
1449 continue;
1450 }
1451
1452 nextPtr = segPtr->nextPtr;
1453 if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
1454 /*
1455 * This segment refuses to die. Move it to prevPtr and advance
1456 * prevPtr if the segment has left gravity.
1457 */
1458
1459 if (prevPtr == NULL) {
1460 segPtr->nextPtr = index1Ptr->linePtr->segPtr;
1461 index1Ptr->linePtr->segPtr = segPtr;
1462 } else {
1463 segPtr->nextPtr = prevPtr->nextPtr;
1464 prevPtr->nextPtr = segPtr;
1465 }
1466 if (segPtr->typePtr->leftGravity) {
1467 prevPtr = segPtr;
1468 }
1469 }
1470 segPtr = nextPtr;
1471 }
1472
1473 /*
1474 * If the beginning and end of the deletion range are in different lines,
1475 * join the two lines together and discard the ending line.
1476 */
1477
1478 if (index1Ptr->linePtr != index2Ptr->linePtr) {
1479 TkTextLine *prevLinePtr;
1480
1481 for (segPtr = lastPtr; segPtr != NULL;
1482 segPtr = segPtr->nextPtr) {
1483 if (segPtr->typePtr->lineChangeProc != NULL) {
1484 (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
1485 }
1486 }
1487 curNodePtr = index2Ptr->linePtr->parentPtr;
1488 for (nodePtr = curNodePtr; nodePtr != NULL;
1489 nodePtr = nodePtr->parentPtr) {
1490 nodePtr->numLines--;
1491 for (ref = 0; ref < treePtr->pixelReferences; ref++) {
1492 nodePtr->numPixels[ref] -= index2Ptr->linePtr->pixels[2*ref];
1493 }
1494 }
1495 changeToLineCount++;
1496 curNodePtr->numChildren--;
1497 prevLinePtr = curNodePtr->children.linePtr;
1498 if (prevLinePtr == index2Ptr->linePtr) {
1499 curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
1500 } else {
1501 while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
1502 prevLinePtr = prevLinePtr->nextPtr;
1503 }
1504 prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
1505 }
1506
1507 /*
1508 * Check if we need to adjust any partial clients. In this case if
1509 * we're deleting the line, we actually move back to the previous line
1510 * for our (start,end) storage. We do this because we still want the
1511 * portion of the second line that still exists to be in the start,end
1512 * range.
1513 */
1514
1515 if (treePtr->startEnd != NULL) {
1516 int checkCount = 0;
1517
1518 while (checkCount < treePtr->startEndCount &&
1519 treePtr->startEnd[checkCount] != NULL) {
1520 if (treePtr->startEnd[checkCount] == index2Ptr->linePtr) {
1521 TkText *peer = treePtr->startEndRef[checkCount];
1522
1523 /*
1524 * We're deleting a line which is the start or end of a
1525 * current client. This means we need to adjust that
1526 * client.
1527 */
1528
1529 treePtr->startEnd[checkCount] = index1Ptr->linePtr;
1530 if (peer->start == index2Ptr->linePtr) {
1531 peer->start = index1Ptr->linePtr;
1532 }
1533 if (peer->end == index2Ptr->linePtr) {
1534 peer->end = index1Ptr->linePtr;
1535 }
1536 }
1537 checkCount++;
1538 }
1539 }
1540 ckfree((char *) index2Ptr->linePtr->pixels);
1541 ckfree((char *) index2Ptr->linePtr);
1542
1543 Rebalance((BTree *) index2Ptr->tree, curNodePtr);
1544 }
1545
1546 /*
1547 * Cleanup the segments in the new line.
1548 */
1549
1550 CleanupLine(index1Ptr->linePtr);
1551
1552 /*
1553 * This line now needs to have its height recalculated. For safety, ensure
1554 * we don't call this function with the last artificial line of text. I
1555 * _believe_ that it isn't possible to get this far with the last line,
1556 * but it is good to be safe.
1557 */
1558
1559 if (TkBTreeNextLine(NULL, index1Ptr->linePtr) != NULL) {
1560 TkTextInvalidateLineMetrics(treePtr->sharedTextPtr, NULL,
1561 index1Ptr->linePtr, changeToLineCount,
1562 TK_TEXT_INVALIDATE_DELETE);
1563 }
1564
1565 /*
1566 * Lastly, rebalance the first node of the range.
1567 */
1568
1569 Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
1570 if (tkBTreeDebug) {
1571 TkBTreeCheck(index1Ptr->tree);
1572 }
1573 }
1574
1575 /*
1576 *----------------------------------------------------------------------
1577 *
1578 * TkBTreeFindLine --
1579 *
1580 * Find a particular line in a B-tree based on its line number.
1581 *
1582 * Results:
1583 * The return value is a pointer to the line structure for the line whose
1584 * index is "line", or NULL if no such line exists.
1585 *
1586 * Side effects:
1587 * None.
1588 *
1589 *----------------------------------------------------------------------
1590 */
1591
1592 TkTextLine *
TkBTreeFindLine(TkTextBTree tree,const TkText * textPtr,int line)1593 TkBTreeFindLine(
1594 TkTextBTree tree, /* B-tree in which to find line. */
1595 const TkText *textPtr, /* Relative to this client of the B-tree. */
1596 int line) /* Index of desired line. */
1597 {
1598 BTree *treePtr = (BTree *) tree;
1599 register Node *nodePtr;
1600 register TkTextLine *linePtr;
1601
1602 if (treePtr == NULL) {
1603 treePtr = (BTree *) textPtr->sharedTextPtr->tree;
1604 }
1605
1606 nodePtr = treePtr->rootPtr;
1607 if ((line < 0) || (line >= nodePtr->numLines)) {
1608 return NULL;
1609 }
1610
1611 /*
1612 * Check for any start/end offset for this text widget.
1613 */
1614
1615 if (textPtr != NULL) {
1616 if (textPtr->start != NULL) {
1617 line += TkBTreeLinesTo(NULL, textPtr->start);
1618 if (line >= nodePtr->numLines) {
1619 return NULL;
1620 }
1621 }
1622 if (textPtr->end != NULL) {
1623 if (line > TkBTreeLinesTo(NULL, textPtr->end)) {
1624 return NULL;
1625 }
1626 }
1627 }
1628
1629 /*
1630 * Work down through levels of the tree until a node is found at level 0.
1631 */
1632
1633 while (nodePtr->level != 0) {
1634 for (nodePtr = nodePtr->children.nodePtr;
1635 nodePtr->numLines <= line;
1636 nodePtr = nodePtr->nextPtr) {
1637 if (nodePtr == NULL) {
1638 Tcl_Panic("TkBTreeFindLine ran out of nodes");
1639 }
1640 line -= nodePtr->numLines;
1641 }
1642 }
1643
1644 /*
1645 * Work through the lines attached to the level-0 node.
1646 */
1647
1648 for (linePtr = nodePtr->children.linePtr; line > 0;
1649 linePtr = linePtr->nextPtr) {
1650 if (linePtr == NULL) {
1651 Tcl_Panic("TkBTreeFindLine ran out of lines");
1652 }
1653 line -= 1;
1654 }
1655 return linePtr;
1656 }
1657
1658 /*
1659 *----------------------------------------------------------------------
1660 *
1661 * TkBTreeFindPixelLine --
1662 *
1663 * Find a particular line in a B-tree based on its pixel count.
1664 *
1665 * Results:
1666 * The return value is a pointer to the line structure for the line which
1667 * contains the pixel "pixels", or NULL if no such line exists. If the
1668 * first line is of height 20, then pixels 0-19 will return it, and
1669 * pixels = 20 will return the next line.
1670 *
1671 * If pixelOffset is non-NULL, it is set to the amount by which 'pixels'
1672 * exceeds the first pixel located on the returned line. This should
1673 * always be non-negative.
1674 *
1675 * Side effects:
1676 * None.
1677 *
1678 *----------------------------------------------------------------------
1679 */
1680
1681 TkTextLine *
TkBTreeFindPixelLine(TkTextBTree tree,const TkText * textPtr,int pixels,int * pixelOffset)1682 TkBTreeFindPixelLine(
1683 TkTextBTree tree, /* B-tree to use. */
1684 const TkText *textPtr, /* Relative to this client of the B-tree. */
1685 int pixels, /* Pixel index of desired line. */
1686 int *pixelOffset) /* Used to return offset. */
1687 {
1688 BTree *treePtr = (BTree *) tree;
1689 register Node *nodePtr;
1690 register TkTextLine *linePtr;
1691 int pixelReference = textPtr->pixelReference;
1692
1693 nodePtr = treePtr->rootPtr;
1694
1695 if ((pixels < 0) || (pixels > nodePtr->numPixels[pixelReference])) {
1696 return NULL;
1697 }
1698
1699 if (nodePtr->numPixels[pixelReference] == 0) {
1700 Tcl_Panic("TkBTreeFindPixelLine called with empty window");
1701 }
1702
1703 /*
1704 * Work down through levels of the tree until a node is found at level 0.
1705 */
1706
1707 while (nodePtr->level != 0) {
1708 for (nodePtr = nodePtr->children.nodePtr;
1709 nodePtr->numPixels[pixelReference] <= pixels;
1710 nodePtr = nodePtr->nextPtr) {
1711 if (nodePtr == NULL) {
1712 Tcl_Panic("TkBTreeFindPixelLine ran out of nodes");
1713 }
1714 pixels -= nodePtr->numPixels[pixelReference];
1715 }
1716 }
1717
1718 /*
1719 * Work through the lines attached to the level-0 node.
1720 */
1721
1722 for (linePtr = nodePtr->children.linePtr;
1723 linePtr->pixels[2 * pixelReference] < pixels;
1724 linePtr = linePtr->nextPtr) {
1725 if (linePtr == NULL) {
1726 Tcl_Panic("TkBTreeFindPixelLine ran out of lines");
1727 }
1728 pixels -= linePtr->pixels[2 * pixelReference];
1729 }
1730 if (pixelOffset != NULL && linePtr != NULL) {
1731 *pixelOffset = pixels;
1732 }
1733 return linePtr;
1734 }
1735
1736 /*
1737 *----------------------------------------------------------------------
1738 *
1739 * TkBTreeNextLine --
1740 *
1741 * Given an existing line in a B-tree, this function locates the next
1742 * line in the B-tree. This function is used for scanning through the
1743 * B-tree.
1744 *
1745 * Results:
1746 * The return value is a pointer to the line that immediately follows
1747 * linePtr, or NULL if there is no such line.
1748 *
1749 * Side effects:
1750 * None.
1751 *
1752 *----------------------------------------------------------------------
1753 */
1754
1755 TkTextLine *
TkBTreeNextLine(const TkText * textPtr,register TkTextLine * linePtr)1756 TkBTreeNextLine(
1757 const TkText *textPtr, /* Next line in the context of this client. */
1758 register TkTextLine *linePtr)
1759 /* Pointer to existing line in B-tree. */
1760 {
1761 register Node *nodePtr;
1762
1763 if (linePtr->nextPtr != NULL) {
1764 if (textPtr != NULL && (linePtr == textPtr->end)) {
1765 return NULL;
1766 } else {
1767 return linePtr->nextPtr;
1768 }
1769 }
1770
1771 /*
1772 * This was the last line associated with the particular parent node.
1773 * Search up the tree for the next node, then search down from that node
1774 * to find the first line.
1775 */
1776
1777 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
1778 if (nodePtr->nextPtr != NULL) {
1779 nodePtr = nodePtr->nextPtr;
1780 break;
1781 }
1782 if (nodePtr->parentPtr == NULL) {
1783 return NULL;
1784 }
1785 }
1786 while (nodePtr->level > 0) {
1787 nodePtr = nodePtr->children.nodePtr;
1788 }
1789 return nodePtr->children.linePtr;
1790 }
1791
1792 /*
1793 *----------------------------------------------------------------------
1794 *
1795 * TkBTreePreviousLine --
1796 *
1797 * Given an existing line in a B-tree, this function locates the previous
1798 * line in the B-tree. This function is used for scanning through the
1799 * B-tree in the reverse direction.
1800 *
1801 * Results:
1802 * The return value is a pointer to the line that immediately preceeds
1803 * linePtr, or NULL if there is no such line.
1804 *
1805 * Side effects:
1806 * None.
1807 *
1808 *----------------------------------------------------------------------
1809 */
1810
1811 TkTextLine *
TkBTreePreviousLine(TkText * textPtr,register TkTextLine * linePtr)1812 TkBTreePreviousLine(
1813 TkText *textPtr, /* Relative to this client of the B-tree. */
1814 register TkTextLine *linePtr)
1815 /* Pointer to existing line in B-tree. */
1816 {
1817 register Node *nodePtr;
1818 register Node *node2Ptr;
1819 register TkTextLine *prevPtr;
1820
1821 if (textPtr != NULL && textPtr->start == linePtr) {
1822 return NULL;
1823 }
1824
1825 /*
1826 * Find the line under this node just before the starting line.
1827 */
1828
1829 prevPtr = linePtr->parentPtr->children.linePtr; /* First line at leaf. */
1830 while (prevPtr != linePtr) {
1831 if (prevPtr->nextPtr == linePtr) {
1832 return prevPtr;
1833 }
1834 prevPtr = prevPtr->nextPtr;
1835 if (prevPtr == NULL) {
1836 Tcl_Panic("TkBTreePreviousLine ran out of lines");
1837 }
1838 }
1839
1840 /*
1841 * This was the first line associated with the particular parent node.
1842 * Search up the tree for the previous node, then search down from that
1843 * node to find its last line.
1844 */
1845
1846 for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
1847 if (nodePtr == NULL || nodePtr->parentPtr == NULL) {
1848 return NULL;
1849 }
1850 if (nodePtr != nodePtr->parentPtr->children.nodePtr) {
1851 break;
1852 }
1853 }
1854 for (node2Ptr = nodePtr->parentPtr->children.nodePtr; ;
1855 node2Ptr = node2Ptr->children.nodePtr) {
1856 while (node2Ptr->nextPtr != nodePtr) {
1857 node2Ptr = node2Ptr->nextPtr;
1858 }
1859 if (node2Ptr->level == 0) {
1860 break;
1861 }
1862 nodePtr = NULL;
1863 }
1864 for (prevPtr = node2Ptr->children.linePtr ; ; prevPtr = prevPtr->nextPtr) {
1865 if (prevPtr->nextPtr == NULL) {
1866 return prevPtr;
1867 }
1868 }
1869 }
1870
1871 /*
1872 *----------------------------------------------------------------------
1873 *
1874 * TkBTreePixelsTo --
1875 *
1876 * Given a pointer to a line in a B-tree, return the numerical pixel
1877 * index of the top of that line (i.e. the result does not include the
1878 * height of the given line).
1879 *
1880 * Since the last line of text (the artificial one) has zero height by
1881 * defintion, calling this with the last line will return the total
1882 * number of pixels in the widget.
1883 *
1884 * Results:
1885 * The result is the pixel height of the top of the given line.
1886 *
1887 * Side effects:
1888 * None.
1889 *
1890 *----------------------------------------------------------------------
1891 */
1892
1893 int
TkBTreePixelsTo(const TkText * textPtr,TkTextLine * linePtr)1894 TkBTreePixelsTo(
1895 const TkText *textPtr, /* Relative to this client of the B-tree. */
1896 TkTextLine *linePtr) /* Pointer to existing line in B-tree. */
1897 {
1898 register TkTextLine *linePtr2;
1899 register Node *nodePtr, *parentPtr;
1900 int index;
1901 int pixelReference = textPtr->pixelReference;
1902
1903 /*
1904 * First count how many pixels precede this line in its level-0 node.
1905 */
1906
1907 nodePtr = linePtr->parentPtr;
1908 index = 0;
1909 for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
1910 linePtr2 = linePtr2->nextPtr) {
1911 if (linePtr2 == NULL) {
1912 Tcl_Panic("TkBTreePixelsTo couldn't find line");
1913 }
1914 index += linePtr2->pixels[2 * pixelReference];
1915 }
1916
1917 /*
1918 * Now work up through the levels of the tree one at a time, counting how
1919 * many pixels are in nodes preceding the current node.
1920 */
1921
1922 for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
1923 nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
1924 register Node *nodePtr2;
1925
1926 for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
1927 nodePtr2 = nodePtr2->nextPtr) {
1928 if (nodePtr2 == NULL) {
1929 Tcl_Panic("TkBTreePixelsTo couldn't find node");
1930 }
1931 index += nodePtr2->numPixels[pixelReference];
1932 }
1933 }
1934 return index;
1935 }
1936
1937 /*
1938 *----------------------------------------------------------------------
1939 *
1940 * TkBTreeLinesTo --
1941 *
1942 * Given a pointer to a line in a B-tree, return the numerical index of
1943 * that line.
1944 *
1945 * Results:
1946 * The result is the index of linePtr within the tree, where 0
1947 * corresponds to the first line in the tree.
1948 *
1949 * Side effects:
1950 * None.
1951 *
1952 *----------------------------------------------------------------------
1953 */
1954
1955 int
TkBTreeLinesTo(const TkText * textPtr,TkTextLine * linePtr)1956 TkBTreeLinesTo(
1957 const TkText *textPtr, /* Relative to this client of the B-tree. */
1958 TkTextLine *linePtr) /* Pointer to existing line in B-tree. */
1959 {
1960 register TkTextLine *linePtr2;
1961 register Node *nodePtr, *parentPtr, *nodePtr2;
1962 int index;
1963
1964 /*
1965 * First count how many lines precede this one in its level-0 node.
1966 */
1967
1968 nodePtr = linePtr->parentPtr;
1969 index = 0;
1970 for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
1971 linePtr2 = linePtr2->nextPtr) {
1972 if (linePtr2 == NULL) {
1973 Tcl_Panic("TkBTreeLinesTo couldn't find line");
1974 }
1975 index += 1;
1976 }
1977
1978 /*
1979 * Now work up through the levels of the tree one at a time, counting how
1980 * many lines are in nodes preceding the current node.
1981 */
1982
1983 for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
1984 nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
1985 for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
1986 nodePtr2 = nodePtr2->nextPtr) {
1987 if (nodePtr2 == NULL) {
1988 Tcl_Panic("TkBTreeLinesTo couldn't find node");
1989 }
1990 index += nodePtr2->numLines;
1991 }
1992 }
1993 if (textPtr != NULL) {
1994 /*
1995 * The index to return must be relative to textPtr, not to the entire
1996 * tree. Take care to never return a negative index when linePtr
1997 * denotes a line before -startline, or an index larger than the
1998 * number of lines in textPtr when linePtr is a line past -endline.
1999 */
2000
2001 int indexStart, indexEnd;
2002
2003 if (textPtr->start != NULL) {
2004 indexStart = TkBTreeLinesTo(NULL, textPtr->start);
2005 } else {
2006 indexStart = 0;
2007 }
2008 if (textPtr->end != NULL) {
2009 indexEnd = TkBTreeLinesTo(NULL, textPtr->end);
2010 } else {
2011 indexEnd = TkBTreeNumLines(textPtr->sharedTextPtr->tree, NULL);
2012 }
2013 if (index < indexStart) {
2014 index = 0;
2015 } else if (index > indexEnd) {
2016 index = TkBTreeNumLines(textPtr->sharedTextPtr->tree, textPtr);
2017 } else {
2018 index -= indexStart;
2019 }
2020 }
2021 return index;
2022 }
2023
2024 /*
2025 *----------------------------------------------------------------------
2026 *
2027 * TkBTreeLinkSegment --
2028 *
2029 * This function adds a new segment to a B-tree at a given location.
2030 *
2031 * Results:
2032 * None.
2033 *
2034 * Side effects:
2035 * SegPtr will be linked into its tree.
2036 *
2037 *----------------------------------------------------------------------
2038 */
2039
2040 /* ARGSUSED */
2041 void
TkBTreeLinkSegment(TkTextSegment * segPtr,TkTextIndex * indexPtr)2042 TkBTreeLinkSegment(
2043 TkTextSegment *segPtr, /* Pointer to new segment to be added to
2044 * B-tree. Should be completely initialized by
2045 * caller except for nextPtr field. */
2046 TkTextIndex *indexPtr) /* Where to add segment: it gets linked in
2047 * just before the segment indicated here. */
2048 {
2049 register TkTextSegment *prevPtr;
2050
2051 prevPtr = SplitSeg(indexPtr);
2052 if (prevPtr == NULL) {
2053 segPtr->nextPtr = indexPtr->linePtr->segPtr;
2054 indexPtr->linePtr->segPtr = segPtr;
2055 } else {
2056 segPtr->nextPtr = prevPtr->nextPtr;
2057 prevPtr->nextPtr = segPtr;
2058 }
2059 CleanupLine(indexPtr->linePtr);
2060 if (tkBTreeDebug) {
2061 TkBTreeCheck(indexPtr->tree);
2062 }
2063 ((BTree *)indexPtr->tree)->stateEpoch++;
2064 }
2065
2066 /*
2067 *----------------------------------------------------------------------
2068 *
2069 * TkBTreeUnlinkSegment --
2070 *
2071 * This function unlinks a segment from its line in a B-tree.
2072 *
2073 * Results:
2074 * None.
2075 *
2076 * Side effects:
2077 * SegPtr will be unlinked from linePtr. The segment itself isn't
2078 * modified by this function.
2079 *
2080 *----------------------------------------------------------------------
2081 */
2082
2083 /* ARGSUSED */
2084 void
TkBTreeUnlinkSegment(TkTextSegment * segPtr,TkTextLine * linePtr)2085 TkBTreeUnlinkSegment(
2086 TkTextSegment *segPtr, /* Segment to be unlinked. */
2087 TkTextLine *linePtr) /* Line that currently contains segment. */
2088 {
2089 register TkTextSegment *prevPtr;
2090
2091 if (linePtr->segPtr == segPtr) {
2092 linePtr->segPtr = segPtr->nextPtr;
2093 } else {
2094 prevPtr = linePtr->segPtr;
2095 while (prevPtr->nextPtr != segPtr) {
2096 prevPtr = prevPtr->nextPtr;
2097
2098 if (prevPtr == NULL) {
2099 /*
2100 * Two logical lines merged into one display line through
2101 * eliding of a newline.
2102 */
2103
2104 linePtr = TkBTreeNextLine(NULL, linePtr);
2105 prevPtr = linePtr->segPtr;
2106 }
2107 }
2108 prevPtr->nextPtr = segPtr->nextPtr;
2109 }
2110 CleanupLine(linePtr);
2111 }
2112
2113 /*
2114 *----------------------------------------------------------------------
2115 *
2116 * TkBTreeTag --
2117 *
2118 * Turn a given tag on or off for a given range of characters in a B-tree
2119 * of text.
2120 *
2121 * Results:
2122 * 1 if the tags on any characters in the range were changed, and zero
2123 * otherwise (i.e. if the tag was already absent (add = 0) or present
2124 * (add = 1) on the index range in question).
2125 *
2126 * Side effects:
2127 * The given tag is added to the given range of characters in the tree or
2128 * removed from all those characters, depending on the "add" argument.
2129 * The structure of the btree is modified enough that index1Ptr and
2130 * index2Ptr are no longer valid after this function returns, and the
2131 * indexes may be modified by this function.
2132 *
2133 *----------------------------------------------------------------------
2134 */
2135
2136 int
TkBTreeTag(register TkTextIndex * index1Ptr,register TkTextIndex * index2Ptr,TkTextTag * tagPtr,int add)2137 TkBTreeTag(
2138 register TkTextIndex *index1Ptr,
2139 /* Indicates first character in range. */
2140 register TkTextIndex *index2Ptr,
2141 /* Indicates character just after the last one
2142 * in range. */
2143 TkTextTag *tagPtr, /* Tag to add or remove. */
2144 int add) /* One means add tag to the given range of
2145 * characters; zero means remove the tag from
2146 * the range. */
2147 {
2148 TkTextSegment *segPtr, *prevPtr;
2149 TkTextSearch search;
2150 TkTextLine *cleanupLinePtr;
2151 int oldState, changed, anyChanges = 0;
2152
2153 /*
2154 * See whether the tag is present at the start of the range. If the state
2155 * doesn't already match what we want then add a toggle there.
2156 */
2157
2158 oldState = TkBTreeCharTagged(index1Ptr, tagPtr);
2159 if ((add != 0) ^ oldState) {
2160 segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
2161 segPtr->typePtr = (add) ? &tkTextToggleOnType : &tkTextToggleOffType;
2162 prevPtr = SplitSeg(index1Ptr);
2163 if (prevPtr == NULL) {
2164 segPtr->nextPtr = index1Ptr->linePtr->segPtr;
2165 index1Ptr->linePtr->segPtr = segPtr;
2166 } else {
2167 segPtr->nextPtr = prevPtr->nextPtr;
2168 prevPtr->nextPtr = segPtr;
2169 }
2170 segPtr->size = 0;
2171 segPtr->body.toggle.tagPtr = tagPtr;
2172 segPtr->body.toggle.inNodeCounts = 0;
2173 anyChanges = 1;
2174 }
2175
2176 /*
2177 * Scan the range of characters and delete any internal tag transitions.
2178 * Keep track of what the old state was at the end of the range, and add a
2179 * toggle there if it's needed.
2180 */
2181
2182 TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
2183 cleanupLinePtr = index1Ptr->linePtr;
2184 while (TkBTreeNextTag(&search)) {
2185 anyChanges = 1;
2186 oldState ^= 1;
2187 segPtr = search.segPtr;
2188 prevPtr = search.curIndex.linePtr->segPtr;
2189 if (prevPtr == segPtr) {
2190 search.curIndex.linePtr->segPtr = segPtr->nextPtr;
2191 } else {
2192 while (prevPtr->nextPtr != segPtr) {
2193 prevPtr = prevPtr->nextPtr;
2194 }
2195 prevPtr->nextPtr = segPtr->nextPtr;
2196 }
2197 if (segPtr->body.toggle.inNodeCounts) {
2198 ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr,
2199 segPtr->body.toggle.tagPtr, -1);
2200 segPtr->body.toggle.inNodeCounts = 0;
2201 changed = 1;
2202 } else {
2203 changed = 0;
2204 }
2205 ckfree((char *) segPtr);
2206
2207 /*
2208 * The code below is a bit tricky. After deleting a toggle we
2209 * eventually have to call CleanupLine, in order to allow character
2210 * segments to be merged together. To do this, we remember in
2211 * cleanupLinePtr a line that needs to be cleaned up, but we don't
2212 * clean it up until we've moved on to a different line. That way the
2213 * cleanup process won't goof up segPtr.
2214 */
2215
2216 if (cleanupLinePtr != search.curIndex.linePtr) {
2217 CleanupLine(cleanupLinePtr);
2218 cleanupLinePtr = search.curIndex.linePtr;
2219 }
2220
2221 /*
2222 * Quick hack. ChangeNodeToggleCount may move the tag's root location
2223 * around and leave the search in the void. This resets the search.
2224 */
2225
2226 if (changed) {
2227 TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
2228 }
2229 }
2230 if ((add != 0) ^ oldState) {
2231 segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
2232 segPtr->typePtr = (add) ? &tkTextToggleOffType : &tkTextToggleOnType;
2233 prevPtr = SplitSeg(index2Ptr);
2234 if (prevPtr == NULL) {
2235 segPtr->nextPtr = index2Ptr->linePtr->segPtr;
2236 index2Ptr->linePtr->segPtr = segPtr;
2237 } else {
2238 segPtr->nextPtr = prevPtr->nextPtr;
2239 prevPtr->nextPtr = segPtr;
2240 }
2241 segPtr->size = 0;
2242 segPtr->body.toggle.tagPtr = tagPtr;
2243 segPtr->body.toggle.inNodeCounts = 0;
2244 anyChanges = 1;
2245 }
2246
2247 /*
2248 * Cleanup cleanupLinePtr and the last line of the range, if these are
2249 * different.
2250 */
2251
2252 if (anyChanges) {
2253 CleanupLine(cleanupLinePtr);
2254 if (cleanupLinePtr != index2Ptr->linePtr) {
2255 CleanupLine(index2Ptr->linePtr);
2256 }
2257 ((BTree *)index1Ptr->tree)->stateEpoch++;
2258 }
2259
2260 if (tkBTreeDebug) {
2261 TkBTreeCheck(index1Ptr->tree);
2262 }
2263 return anyChanges;
2264 }
2265
2266 /*
2267 *----------------------------------------------------------------------
2268 *
2269 * ChangeNodeToggleCount --
2270 *
2271 * This function increments or decrements the toggle count for a
2272 * particular tag in a particular node and all its ancestors up to the
2273 * per-tag root node.
2274 *
2275 * Results:
2276 * None.
2277 *
2278 * Side effects:
2279 * The toggle count for tag is adjusted up or down by "delta" in nodePtr.
2280 * This routine maintains the tagRootPtr that identifies the root node
2281 * for the tag, moving it up or down the tree as needed.
2282 *
2283 *----------------------------------------------------------------------
2284 */
2285
2286 static void
ChangeNodeToggleCount(register Node * nodePtr,TkTextTag * tagPtr,int delta)2287 ChangeNodeToggleCount(
2288 register Node *nodePtr, /* Node whose toggle count for a tag must be
2289 * changed. */
2290 TkTextTag *tagPtr, /* Information about tag. */
2291 int delta) /* Amount to add to current toggle count for
2292 * tag (may be negative). */
2293 {
2294 register Summary *summaryPtr, *prevPtr;
2295 register Node *node2Ptr;
2296 int rootLevel; /* Level of original tag root. */
2297
2298 tagPtr->toggleCount += delta;
2299 if (tagPtr->tagRootPtr == NULL) {
2300 tagPtr->tagRootPtr = nodePtr;
2301 return;
2302 }
2303
2304 /*
2305 * Note the level of the existing root for the tag so we can detect if it
2306 * needs to be moved because of the toggle count change.
2307 */
2308
2309 rootLevel = tagPtr->tagRootPtr->level;
2310
2311 /*
2312 * Iterate over the node and its ancestors up to the tag root, adjusting
2313 * summary counts at each node and moving the tag's root upwards if
2314 * necessary.
2315 */
2316
2317 for ( ; nodePtr != tagPtr->tagRootPtr; nodePtr = nodePtr->parentPtr) {
2318 /*
2319 * See if there's already an entry for this tag for this node. If so,
2320 * perhaps all we have to do is adjust its count.
2321 */
2322
2323 for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
2324 summaryPtr != NULL;
2325 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
2326 if (summaryPtr->tagPtr == tagPtr) {
2327 break;
2328 }
2329 }
2330 if (summaryPtr != NULL) {
2331 summaryPtr->toggleCount += delta;
2332 if (summaryPtr->toggleCount > 0 &&
2333 summaryPtr->toggleCount < tagPtr->toggleCount) {
2334 continue;
2335 }
2336 if (summaryPtr->toggleCount != 0) {
2337 /*
2338 * Should never find a node with max toggle count at this
2339 * point (there shouldn't have been a summary entry in the
2340 * first place).
2341 */
2342
2343 Tcl_Panic("ChangeNodeToggleCount: bad toggle count (%d) max (%d)",
2344 summaryPtr->toggleCount, tagPtr->toggleCount);
2345 }
2346
2347 /*
2348 * Zero toggle count; must remove this tag from the list.
2349 */
2350
2351 if (prevPtr == NULL) {
2352 nodePtr->summaryPtr = summaryPtr->nextPtr;
2353 } else {
2354 prevPtr->nextPtr = summaryPtr->nextPtr;
2355 }
2356 ckfree((char *) summaryPtr);
2357 } else {
2358 /*
2359 * This tag isn't currently in the summary information list.
2360 */
2361
2362 if (rootLevel == nodePtr->level) {
2363 /*
2364 * The old tag root is at the same level in the tree as this
2365 * node, but it isn't at this node. Move the tag root up a
2366 * level, in the hopes that it will now cover this node as
2367 * well as the old root (if not, we'll move it up again the
2368 * next time through the loop). To push it up one level we
2369 * copy the original toggle count into the summary information
2370 * at the old root and change the root to its parent node.
2371 */
2372
2373 Node *rootNodePtr = tagPtr->tagRootPtr;
2374
2375 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2376 summaryPtr->tagPtr = tagPtr;
2377 summaryPtr->toggleCount = tagPtr->toggleCount - delta;
2378 summaryPtr->nextPtr = rootNodePtr->summaryPtr;
2379 rootNodePtr->summaryPtr = summaryPtr;
2380 rootNodePtr = rootNodePtr->parentPtr;
2381 rootLevel = rootNodePtr->level;
2382 tagPtr->tagRootPtr = rootNodePtr;
2383 }
2384 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
2385 summaryPtr->tagPtr = tagPtr;
2386 summaryPtr->toggleCount = delta;
2387 summaryPtr->nextPtr = nodePtr->summaryPtr;
2388 nodePtr->summaryPtr = summaryPtr;
2389 }
2390 }
2391
2392 /*
2393 * If we've decremented the toggle count, then it may be necessary to push
2394 * the tag root down one or more levels.
2395 */
2396
2397 if (delta >= 0) {
2398 return;
2399 }
2400 if (tagPtr->toggleCount == 0) {
2401 tagPtr->tagRootPtr = NULL;
2402 return;
2403 }
2404 nodePtr = tagPtr->tagRootPtr;
2405 while (nodePtr->level > 0) {
2406 /*
2407 * See if a single child node accounts for all of the tag's toggles.
2408 * If so, push the root down one level.
2409 */
2410
2411 for (node2Ptr = nodePtr->children.nodePtr;
2412 node2Ptr != NULL ;
2413 node2Ptr = node2Ptr->nextPtr) {
2414 for (prevPtr = NULL, summaryPtr = node2Ptr->summaryPtr;
2415 summaryPtr != NULL;
2416 prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
2417 if (summaryPtr->tagPtr == tagPtr) {
2418 break;
2419 }
2420 }
2421 if (summaryPtr == NULL) {
2422 continue;
2423 }
2424 if (summaryPtr->toggleCount != tagPtr->toggleCount) {
2425 /*
2426 * No node has all toggles, so the root is still valid.
2427 */
2428
2429 return;
2430 }
2431
2432 /*
2433 * This node has all the toggles, so push down the root.
2434 */
2435
2436 if (prevPtr == NULL) {
2437 node2Ptr->summaryPtr = summaryPtr->nextPtr;
2438 } else {
2439 prevPtr->nextPtr = summaryPtr->nextPtr;
2440 }
2441 ckfree((char *) summaryPtr);
2442 tagPtr->tagRootPtr = node2Ptr;
2443 break;
2444 }
2445 nodePtr = tagPtr->tagRootPtr;
2446 }
2447 }
2448
2449 /*
2450 *----------------------------------------------------------------------
2451 *
2452 * FindTagStart --
2453 *
2454 * Find the start of the first range of a tag.
2455 *
2456 * Results:
2457 * The return value is a pointer to the first tag toggle segment for the
2458 * tag. This can be either a tagon or tagoff segments because of the way
2459 * TkBTreeAdd removes a tag. Sets *indexPtr to be the index of the tag
2460 * toggle.
2461 *
2462 * Side effects:
2463 * None.
2464 *
2465 *----------------------------------------------------------------------
2466 */
2467
2468 static TkTextSegment *
FindTagStart(TkTextBTree tree,TkTextTag * tagPtr,TkTextIndex * indexPtr)2469 FindTagStart(
2470 TkTextBTree tree, /* Tree to search within. */
2471 TkTextTag *tagPtr, /* Tag to search for. */
2472 TkTextIndex *indexPtr) /* Return - index information. */
2473 {
2474 register Node *nodePtr;
2475 register TkTextLine *linePtr;
2476 register TkTextSegment *segPtr;
2477 register Summary *summaryPtr;
2478 int offset;
2479
2480 nodePtr = tagPtr->tagRootPtr;
2481 if (nodePtr == NULL) {
2482 return NULL;
2483 }
2484
2485 /*
2486 * Search from the root of the subtree that contains the tag down to the
2487 * level 0 node.
2488 */
2489
2490 while (nodePtr->level > 0) {
2491 for (nodePtr = nodePtr->children.nodePtr ; nodePtr != NULL;
2492 nodePtr = nodePtr->nextPtr) {
2493 for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL;
2494 summaryPtr = summaryPtr->nextPtr) {
2495 if (summaryPtr->tagPtr == tagPtr) {
2496 goto gotNodeWithTag;
2497 }
2498 }
2499 }
2500 gotNodeWithTag:
2501 continue;
2502 }
2503
2504 /*
2505 * Work through the lines attached to the level-0 node.
2506 */
2507
2508 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
2509 linePtr = linePtr->nextPtr) {
2510 for (offset = 0, segPtr = linePtr->segPtr ; segPtr != NULL;
2511 offset += segPtr->size, segPtr = segPtr->nextPtr) {
2512 if (((segPtr->typePtr == &tkTextToggleOnType)
2513 || (segPtr->typePtr == &tkTextToggleOffType))
2514 && (segPtr->body.toggle.tagPtr == tagPtr)) {
2515 /*
2516 * It is possible that this is a tagoff tag, but that gets
2517 * cleaned up later.
2518 */
2519
2520 indexPtr->tree = tree;
2521 indexPtr->linePtr = linePtr;
2522 indexPtr->byteIndex = offset;
2523 return segPtr;
2524 }
2525 }
2526 }
2527 return NULL;
2528 }
2529
2530 /*
2531 *----------------------------------------------------------------------
2532 *
2533 * FindTagEnd --
2534 *
2535 * Find the end of the last range of a tag.
2536 *
2537 * Results:
2538 * The return value is a pointer to the last tag toggle segment for the
2539 * tag. This can be either a tagon or tagoff segments because of the way
2540 * TkBTreeAdd removes a tag. Sets *indexPtr to be the index of the tag
2541 * toggle.
2542 *
2543 * Side effects:
2544 * None.
2545 *
2546 *----------------------------------------------------------------------
2547 */
2548
2549 static TkTextSegment *
FindTagEnd(TkTextBTree tree,TkTextTag * tagPtr,TkTextIndex * indexPtr)2550 FindTagEnd(
2551 TkTextBTree tree, /* Tree to search within. */
2552 TkTextTag *tagPtr, /* Tag to search for. */
2553 TkTextIndex *indexPtr) /* Return - index information. */
2554 {
2555 register Node *nodePtr, *lastNodePtr;
2556 register TkTextLine *linePtr ,*lastLinePtr;
2557 register TkTextSegment *segPtr, *lastSegPtr, *last2SegPtr;
2558 register Summary *summaryPtr;
2559 int lastoffset, lastoffset2, offset;
2560
2561 nodePtr = tagPtr->tagRootPtr;
2562 if (nodePtr == NULL) {
2563 return NULL;
2564 }
2565
2566 /*
2567 * Search from the root of the subtree that contains the tag down to the
2568 * level 0 node.
2569 */
2570
2571 while (nodePtr->level > 0) {
2572 for (lastNodePtr = NULL, nodePtr = nodePtr->children.nodePtr ;
2573 nodePtr != NULL; nodePtr = nodePtr->nextPtr) {
2574 for (summaryPtr = nodePtr->summaryPtr ; summaryPtr != NULL;
2575 summaryPtr = summaryPtr->nextPtr) {
2576 if (summaryPtr->tagPtr == tagPtr) {
2577 lastNodePtr = nodePtr;
2578 break;
2579 }
2580 }
2581 }
2582 nodePtr = lastNodePtr;
2583 }
2584
2585 /*
2586 * Work through the lines attached to the level-0 node.
2587 */
2588
2589 last2SegPtr = NULL;
2590 lastoffset2 = 0;
2591 lastoffset = 0;
2592 for (lastLinePtr = NULL, linePtr = nodePtr->children.linePtr;
2593 linePtr != NULL; linePtr = linePtr->nextPtr) {
2594 for (offset = 0, lastSegPtr = NULL, segPtr = linePtr->segPtr ;
2595 segPtr != NULL;
2596 offset += segPtr->size, segPtr = segPtr->nextPtr) {
2597 if (((segPtr->typePtr == &tkTextToggleOnType)
2598 || (segPtr->typePtr == &tkTextToggleOffType))
2599 && (segPtr->body.toggle.tagPtr == tagPtr)) {
2600 lastSegPtr = segPtr;
2601 lastoffset = offset;
2602 }
2603 }
2604 if (lastSegPtr != NULL) {
2605 lastLinePtr = linePtr;
2606 last2SegPtr = lastSegPtr;
2607 lastoffset2 = lastoffset;
2608 }
2609 }
2610 indexPtr->tree = tree;
2611 indexPtr->linePtr = lastLinePtr;
2612 indexPtr->byteIndex = lastoffset2;
2613 return last2SegPtr;
2614 }
2615
2616 /*
2617 *----------------------------------------------------------------------
2618 *
2619 * TkBTreeStartSearch --
2620 *
2621 * This function sets up a search for tag transitions involving a given
2622 * tag (or all tags) in a given range of the text.
2623 *
2624 * Results:
2625 * None.
2626 *
2627 * Side effects:
2628 * The information at *searchPtr is set up so that subsequent calls to
2629 * TkBTreeNextTag or TkBTreePrevTag will return information about the
2630 * locations of tag transitions. Note that TkBTreeNextTag or
2631 * TkBTreePrevTag must be called to get the first transition. Note:
2632 * unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not
2633 * guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be
2634 * greater than that if *index1Ptr is less than the first tag transition.
2635 *
2636 *----------------------------------------------------------------------
2637 */
2638
2639 void
TkBTreeStartSearch(TkTextIndex * index1Ptr,TkTextIndex * index2Ptr,TkTextTag * tagPtr,register TkTextSearch * searchPtr)2640 TkBTreeStartSearch(
2641 TkTextIndex *index1Ptr, /* Search starts here. Tag toggles at this
2642 * position will not be returned. */
2643 TkTextIndex *index2Ptr, /* Search stops here. Tag toggles at this
2644 * position *will* be returned. */
2645 TkTextTag *tagPtr, /* Tag to search for. NULL means search for
2646 * any tag. */
2647 register TkTextSearch *searchPtr)
2648 /* Where to store information about search's
2649 * progress. */
2650 {
2651 int offset;
2652 TkTextIndex index0; /* First index of the tag. */
2653 TkTextSegment *seg0Ptr; /* First segment of the tag. */
2654
2655 /*
2656 * Find the segment that contains the first toggle for the tag. This may
2657 * become the starting point in the search.
2658 */
2659
2660 seg0Ptr = FindTagStart(index1Ptr->tree, tagPtr, &index0);
2661 if (seg0Ptr == NULL) {
2662 /*
2663 * Even though there are no toggles, the display code still uses the
2664 * search curIndex, so initialize that anyway.
2665 */
2666
2667 searchPtr->linesLeft = 0;
2668 searchPtr->curIndex = *index1Ptr;
2669 searchPtr->segPtr = NULL;
2670 searchPtr->nextPtr = NULL;
2671 return;
2672 }
2673 if (TkTextIndexCmp(index1Ptr, &index0) < 0) {
2674 /*
2675 * Adjust start of search up to the first range of the tag.
2676 */
2677
2678 searchPtr->curIndex = index0;
2679 searchPtr->segPtr = NULL;
2680 searchPtr->nextPtr = seg0Ptr; /* Will be returned by NextTag. */
2681 index1Ptr = &index0;
2682 } else {
2683 searchPtr->curIndex = *index1Ptr;
2684 searchPtr->segPtr = NULL;
2685 searchPtr->nextPtr = TkTextIndexToSeg(index1Ptr, &offset);
2686 searchPtr->curIndex.byteIndex -= offset;
2687 }
2688 searchPtr->lastPtr = TkTextIndexToSeg(index2Ptr, NULL);
2689 searchPtr->tagPtr = tagPtr;
2690 searchPtr->linesLeft = TkBTreeLinesTo(NULL, index2Ptr->linePtr) + 1
2691 - TkBTreeLinesTo(NULL, index1Ptr->linePtr);
2692 searchPtr->allTags = (tagPtr == NULL);
2693 if (searchPtr->linesLeft == 1) {
2694 /*
2695 * Starting and stopping segments are in the same line; mark the
2696 * search as over immediately if the second segment is before the
2697 * first. A search does not return a toggle at the very start of the
2698 * range, unless the range is artificially moved up to index0.
2699 */
2700
2701 if (((index1Ptr == &index0) &&
2702 (index1Ptr->byteIndex > index2Ptr->byteIndex)) ||
2703 ((index1Ptr != &index0) &&
2704 (index1Ptr->byteIndex >= index2Ptr->byteIndex))) {
2705 searchPtr->linesLeft = 0;
2706 }
2707 }
2708 }
2709
2710 /*
2711 *----------------------------------------------------------------------
2712 *
2713 * TkBTreeStartSearchBack --
2714 *
2715 * This function sets up a search backwards for tag transitions involving
2716 * a given tag (or all tags) in a given range of the text. In the normal
2717 * case the first index (*index1Ptr) is beyond the second index
2718 * (*index2Ptr).
2719 *
2720 * Results:
2721 * None.
2722 *
2723 * Side effects:
2724 * The information at *searchPtr is set up so that subsequent calls to
2725 * TkBTreePrevTag will return information about the locations of tag
2726 * transitions. Note that TkBTreePrevTag must be called to get the first
2727 * transition. Note: unlike TkBTreeNextTag and TkBTreePrevTag, this
2728 * routine does not guarantee that searchPtr->curIndex is equal to
2729 * *index1Ptr. It may be less than that if *index1Ptr is greater than the
2730 * last tag transition.
2731 *
2732 *----------------------------------------------------------------------
2733 */
2734
2735 void
TkBTreeStartSearchBack(TkTextIndex * index1Ptr,TkTextIndex * index2Ptr,TkTextTag * tagPtr,register TkTextSearch * searchPtr)2736 TkBTreeStartSearchBack(
2737 TkTextIndex *index1Ptr, /* Search starts here. Tag toggles at this
2738 * position will not be returned. */
2739 TkTextIndex *index2Ptr, /* Search stops here. Tag toggles at this
2740 * position *will* be returned. */
2741 TkTextTag *tagPtr, /* Tag to search for. NULL means search for
2742 * any tag. */
2743 register TkTextSearch *searchPtr)
2744 /* Where to store information about search's
2745 * progress. */
2746 {
2747 int offset;
2748 TkTextIndex index0; /* Last index of the tag. */
2749 TkTextIndex backOne; /* One character before starting index. */
2750 TkTextSegment *seg0Ptr; /* Last segment of the tag. */
2751
2752 /*
2753 * Find the segment that contains the last toggle for the tag. This may
2754 * become the starting point in the search.
2755 */
2756
2757 seg0Ptr = FindTagEnd(index1Ptr->tree, tagPtr, &index0);
2758 if (seg0Ptr == NULL) {
2759 /*
2760 * Even though there are no toggles, the display code still uses the
2761 * search curIndex, so initialize that anyway.
2762 */
2763
2764 searchPtr->linesLeft = 0;
2765 searchPtr->curIndex = *index1Ptr;
2766 searchPtr->segPtr = NULL;
2767 searchPtr->nextPtr = NULL;
2768 return;
2769 }
2770
2771 /*
2772 * Adjust the start of the search so it doesn't find any tag toggles
2773 * that are right at the index specified by the user.
2774 */
2775
2776 if (TkTextIndexCmp(index1Ptr, &index0) > 0) {
2777 searchPtr->curIndex = index0;
2778 index1Ptr = &index0;
2779 } else {
2780 TkTextIndexBackChars(NULL, index1Ptr, 1, &searchPtr->curIndex,
2781 COUNT_INDICES);
2782 }
2783 searchPtr->segPtr = NULL;
2784 searchPtr->nextPtr = TkTextIndexToSeg(&searchPtr->curIndex, &offset);
2785 searchPtr->curIndex.byteIndex -= offset;
2786
2787 /*
2788 * Adjust the end of the search so it does find toggles that are right at
2789 * the second index specified by the user.
2790 */
2791
2792 if ((TkBTreeLinesTo(NULL, index2Ptr->linePtr) == 0) &&
2793 (index2Ptr->byteIndex == 0)) {
2794 backOne = *index2Ptr;
2795 searchPtr->lastPtr = NULL; /* Signals special case for 1.0. */
2796 } else {
2797 TkTextIndexBackChars(NULL, index2Ptr, 1, &backOne, COUNT_INDICES);
2798 searchPtr->lastPtr = TkTextIndexToSeg(&backOne, NULL);
2799 }
2800 searchPtr->tagPtr = tagPtr;
2801 searchPtr->linesLeft = TkBTreeLinesTo(NULL, index1Ptr->linePtr) + 1
2802 - TkBTreeLinesTo(NULL, backOne.linePtr);
2803 searchPtr->allTags = (tagPtr == NULL);
2804 if (searchPtr->linesLeft == 1) {
2805 /*
2806 * Starting and stopping segments are in the same line; mark the
2807 * search as over immediately if the second segment is after the
2808 * first.
2809 */
2810
2811 if (index1Ptr->byteIndex <= backOne.byteIndex) {
2812 searchPtr->linesLeft = 0;
2813 }
2814 }
2815 }
2816
2817 /*
2818 *----------------------------------------------------------------------
2819 *
2820 * TkBTreeNextTag --
2821 *
2822 * Once a tag search has begun, successive calls to this function return
2823 * successive tag toggles. Note: it is NOT SAFE to call this function if
2824 * characters have been inserted into or deleted from the B-tree since
2825 * the call to TkBTreeStartSearch.
2826 *
2827 * Results:
2828 * The return value is 1 if another toggle was found that met the
2829 * criteria specified in the call to TkBTreeStartSearch; in this case
2830 * searchPtr->curIndex gives the toggle's position and
2831 * searchPtr->curTagPtr points to its segment. 0 is returned if no more
2832 * matching tag transitions were found; in this case searchPtr->curIndex
2833 * is the same as searchPtr->stopIndex.
2834 *
2835 * Side effects:
2836 * Information in *searchPtr is modified to update the state of the
2837 * search and indicate where the next tag toggle is located.
2838 *
2839 *----------------------------------------------------------------------
2840 */
2841
2842 int
TkBTreeNextTag(register TkTextSearch * searchPtr)2843 TkBTreeNextTag(
2844 register TkTextSearch *searchPtr)
2845 /* Information about search in progress; must
2846 * have been set up by call to
2847 * TkBTreeStartSearch. */
2848 {
2849 register TkTextSegment *segPtr;
2850 register Node *nodePtr;
2851 register Summary *summaryPtr;
2852
2853 if (searchPtr->linesLeft <= 0) {
2854 goto searchOver;
2855 }
2856
2857 /*
2858 * The outermost loop iterates over lines that may potentially contain a
2859 * relevant tag transition, starting from the current segment in the
2860 * current line.
2861 */
2862
2863 segPtr = searchPtr->nextPtr;
2864 while (1) {
2865 /*
2866 * Check for more tags on the current line.
2867 */
2868
2869 for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) {
2870 if (segPtr == searchPtr->lastPtr) {
2871 goto searchOver;
2872 }
2873 if (((segPtr->typePtr == &tkTextToggleOnType)
2874 || (segPtr->typePtr == &tkTextToggleOffType))
2875 && (searchPtr->allTags
2876 || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
2877 searchPtr->segPtr = segPtr;
2878 searchPtr->nextPtr = segPtr->nextPtr;
2879 searchPtr->tagPtr = segPtr->body.toggle.tagPtr;
2880 return 1;
2881 }
2882 searchPtr->curIndex.byteIndex += segPtr->size;
2883 }
2884
2885 /*
2886 * See if there are more lines associated with the current parent
2887 * node. If so, go back to the top of the loop to search the next one.
2888 */
2889
2890 nodePtr = searchPtr->curIndex.linePtr->parentPtr;
2891 searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr;
2892 searchPtr->linesLeft--;
2893 if (searchPtr->linesLeft <= 0) {
2894 goto searchOver;
2895 }
2896 if (searchPtr->curIndex.linePtr != NULL) {
2897 segPtr = searchPtr->curIndex.linePtr->segPtr;
2898 searchPtr->curIndex.byteIndex = 0;
2899 continue;
2900 }
2901 if (nodePtr == searchPtr->tagPtr->tagRootPtr) {
2902 goto searchOver;
2903 }
2904
2905 /*
2906 * Search across and up through the B-tree's node hierarchy looking
2907 * for the next node that has a relevant tag transition somewhere in
2908 * its subtree. Be sure to update linesLeft as we skip over large
2909 * chunks of lines.
2910 */
2911
2912 while (1) {
2913 while (nodePtr->nextPtr == NULL) {
2914 if (nodePtr->parentPtr == NULL ||
2915 nodePtr->parentPtr == searchPtr->tagPtr->tagRootPtr) {
2916 goto searchOver;
2917 }
2918 nodePtr = nodePtr->parentPtr;
2919 }
2920 nodePtr = nodePtr->nextPtr;
2921 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
2922 summaryPtr = summaryPtr->nextPtr) {
2923 if ((searchPtr->allTags) ||
2924 (summaryPtr->tagPtr == searchPtr->tagPtr)) {
2925 goto gotNodeWithTag;
2926 }
2927 }
2928 searchPtr->linesLeft -= nodePtr->numLines;
2929 }
2930
2931 /*
2932 * At this point we've found a subtree that has a relevant tag
2933 * transition. Now search down (and across) through that subtree to
2934 * find the first level-0 node that has a relevant tag transition.
2935 */
2936
2937 gotNodeWithTag:
2938 while (nodePtr->level > 0) {
2939 for (nodePtr = nodePtr->children.nodePtr; ;
2940 nodePtr = nodePtr->nextPtr) {
2941 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
2942 summaryPtr = summaryPtr->nextPtr) {
2943 if ((searchPtr->allTags)
2944 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
2945 /*
2946 * Would really like a multi-level continue here...
2947 */
2948
2949 goto nextChild;
2950 }
2951 }
2952 searchPtr->linesLeft -= nodePtr->numLines;
2953 if (nodePtr->nextPtr == NULL) {
2954 Tcl_Panic("TkBTreeNextTag found incorrect tag summary info.");
2955 }
2956 }
2957 nextChild:
2958 continue;
2959 }
2960
2961 /*
2962 * Now we're down to a level-0 node that contains a line that contains
2963 * a relevant tag transition. Set up line information and go back to
2964 * the beginning of the loop to search through lines.
2965 */
2966
2967 searchPtr->curIndex.linePtr = nodePtr->children.linePtr;
2968 searchPtr->curIndex.byteIndex = 0;
2969 segPtr = searchPtr->curIndex.linePtr->segPtr;
2970 if (searchPtr->linesLeft <= 0) {
2971 goto searchOver;
2972 }
2973 continue;
2974 }
2975
2976 searchOver:
2977 searchPtr->linesLeft = 0;
2978 searchPtr->segPtr = NULL;
2979 return 0;
2980 }
2981
2982 /*
2983 *----------------------------------------------------------------------
2984 *
2985 * TkBTreePrevTag --
2986 *
2987 * Once a tag search has begun, successive calls to this function return
2988 * successive tag toggles in the reverse direction. Note: it is NOT SAFE
2989 * to call this function if characters have been inserted into or deleted
2990 * from the B-tree since the call to TkBTreeStartSearch.
2991 *
2992 * Results:
2993 * The return value is 1 if another toggle was found that met the
2994 * criteria specified in the call to TkBTreeStartSearch; in this case
2995 * searchPtr->curIndex gives the toggle's position and
2996 * searchPtr->curTagPtr points to its segment. 0 is returned if no more
2997 * matching tag transitions were found; in this case searchPtr->curIndex
2998 * is the same as searchPtr->stopIndex.
2999 *
3000 * Side effects:
3001 * Information in *searchPtr is modified to update the state of the
3002 * search and indicate where the next tag toggle is located.
3003 *
3004 *----------------------------------------------------------------------
3005 */
3006
3007 int
TkBTreePrevTag(register TkTextSearch * searchPtr)3008 TkBTreePrevTag(
3009 register TkTextSearch *searchPtr)
3010 /* Information about search in progress; must
3011 * have been set up by call to
3012 * TkBTreeStartSearch. */
3013 {
3014 register TkTextSegment *segPtr, *prevPtr;
3015 register TkTextLine *linePtr, *prevLinePtr;
3016 register Node *nodePtr, *node2Ptr, *prevNodePtr;
3017 register Summary *summaryPtr;
3018 int byteIndex, linesSkipped;
3019 int pastLast; /* Saw last marker during scan. */
3020
3021 if (searchPtr->linesLeft <= 0) {
3022 goto searchOver;
3023 }
3024
3025 /*
3026 * The outermost loop iterates over lines that may potentially contain a
3027 * relevant tag transition, starting from the current segment in the
3028 * current line. "nextPtr" is maintained as the last segment in a line
3029 * that we can look at.
3030 */
3031
3032 while (1) {
3033 /*
3034 * Check for the last toggle before the current segment on this line.
3035 */
3036
3037 byteIndex = 0;
3038 if (searchPtr->lastPtr == NULL) {
3039 /*
3040 * Search back to the very beginning, so pastLast is irrelevent.
3041 */
3042
3043 pastLast = 1;
3044 } else {
3045 pastLast = 0;
3046 }
3047
3048 for (prevPtr = NULL, segPtr = searchPtr->curIndex.linePtr->segPtr ;
3049 segPtr != NULL && segPtr != searchPtr->nextPtr;
3050 segPtr = segPtr->nextPtr) {
3051 if (((segPtr->typePtr == &tkTextToggleOnType)
3052 || (segPtr->typePtr == &tkTextToggleOffType))
3053 && (searchPtr->allTags
3054 || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
3055 prevPtr = segPtr;
3056 searchPtr->curIndex.byteIndex = byteIndex;
3057 }
3058 if (segPtr == searchPtr->lastPtr) {
3059 prevPtr = NULL; /* Segments earlier than last don't
3060 * count. */
3061 pastLast = 1;
3062 }
3063 byteIndex += segPtr->size;
3064 }
3065 if (prevPtr != NULL) {
3066 if (searchPtr->linesLeft == 1 && !pastLast) {
3067 /*
3068 * We found a segment that is before the stopping index. Note
3069 * that it is OK if prevPtr == lastPtr.
3070 */
3071
3072 goto searchOver;
3073 }
3074 searchPtr->segPtr = prevPtr;
3075 searchPtr->nextPtr = prevPtr;
3076 searchPtr->tagPtr = prevPtr->body.toggle.tagPtr;
3077 return 1;
3078 }
3079
3080 searchPtr->linesLeft--;
3081 if (searchPtr->linesLeft <= 0) {
3082 goto searchOver;
3083 }
3084
3085 /*
3086 * See if there are more lines associated with the current parent
3087 * node. If so, go back to the top of the loop to search the previous
3088 * one.
3089 */
3090
3091 nodePtr = searchPtr->curIndex.linePtr->parentPtr;
3092 for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr;
3093 linePtr != NULL && linePtr != searchPtr->curIndex.linePtr;
3094 prevLinePtr = linePtr, linePtr = linePtr->nextPtr) {
3095 /* empty loop body */ ;
3096 }
3097 if (prevLinePtr != NULL) {
3098 searchPtr->curIndex.linePtr = prevLinePtr;
3099 searchPtr->nextPtr = NULL;
3100 continue;
3101 }
3102 if (nodePtr == searchPtr->tagPtr->tagRootPtr) {
3103 goto searchOver;
3104 }
3105
3106 /*
3107 * Search across and up through the B-tree's node hierarchy looking
3108 * for the previous node that has a relevant tag transition somewhere
3109 * in its subtree. The search and line counting is trickier with/out
3110 * back pointers. We'll scan all the nodes under a parent up to the
3111 * current node, searching all of them for tag state. The last one we
3112 * find, if any, is recorded in prevNodePtr, and any nodes past
3113 * prevNodePtr that don't have tag state increment linesSkipped.
3114 */
3115
3116 while (1) {
3117 for (prevNodePtr = NULL, linesSkipped = 0,
3118 node2Ptr = nodePtr->parentPtr->children.nodePtr ;
3119 node2Ptr != nodePtr; node2Ptr = node2Ptr->nextPtr) {
3120 for (summaryPtr = node2Ptr->summaryPtr; summaryPtr != NULL;
3121 summaryPtr = summaryPtr->nextPtr) {
3122 if ((searchPtr->allTags) ||
3123 (summaryPtr->tagPtr == searchPtr->tagPtr)) {
3124 prevNodePtr = node2Ptr;
3125 linesSkipped = 0;
3126 goto keepLooking;
3127 }
3128 }
3129 linesSkipped += node2Ptr->numLines;
3130
3131 keepLooking:
3132 continue;
3133 }
3134 if (prevNodePtr != NULL) {
3135 nodePtr = prevNodePtr;
3136 searchPtr->linesLeft -= linesSkipped;
3137 goto gotNodeWithTag;
3138 }
3139 nodePtr = nodePtr->parentPtr;
3140 if (nodePtr->parentPtr == NULL ||
3141 nodePtr == searchPtr->tagPtr->tagRootPtr) {
3142 goto searchOver;
3143 }
3144 }
3145
3146 /*
3147 * At this point we've found a subtree that has a relevant tag
3148 * transition. Now search down (and across) through that subtree to
3149 * find the last level-0 node that has a relevant tag transition.
3150 */
3151
3152 gotNodeWithTag:
3153 while (nodePtr->level > 0) {
3154 for (linesSkipped = 0, prevNodePtr = NULL,
3155 nodePtr = nodePtr->children.nodePtr; nodePtr != NULL ;
3156 nodePtr = nodePtr->nextPtr) {
3157 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
3158 summaryPtr = summaryPtr->nextPtr) {
3159 if ((searchPtr->allTags)
3160 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
3161 prevNodePtr = nodePtr;
3162 linesSkipped = 0;
3163 goto keepLooking2;
3164 }
3165 }
3166 linesSkipped += nodePtr->numLines;
3167
3168 keepLooking2:
3169 continue;
3170 }
3171 if (prevNodePtr == NULL) {
3172 Tcl_Panic("TkBTreePrevTag found incorrect tag summary info.");
3173 }
3174 searchPtr->linesLeft -= linesSkipped;
3175 nodePtr = prevNodePtr;
3176 }
3177
3178 /*
3179 * Now we're down to a level-0 node that contains a line that contains
3180 * a relevant tag transition. Set up line information and go back to
3181 * the beginning of the loop to search through lines. We start with
3182 * the last line below the node.
3183 */
3184
3185 for (prevLinePtr = NULL, linePtr = nodePtr->children.linePtr;
3186 linePtr != NULL ;
3187 prevLinePtr = linePtr, linePtr = linePtr->nextPtr) {
3188 /* empty loop body */ ;
3189 }
3190 searchPtr->curIndex.linePtr = prevLinePtr;
3191 searchPtr->curIndex.byteIndex = 0;
3192 if (searchPtr->linesLeft <= 0) {
3193 goto searchOver;
3194 }
3195 continue;
3196 }
3197
3198 searchOver:
3199 searchPtr->linesLeft = 0;
3200 searchPtr->segPtr = NULL;
3201 return 0;
3202 }
3203
3204 /*
3205 *----------------------------------------------------------------------
3206 *
3207 * TkBTreeCharTagged --
3208 *
3209 * Determine whether a particular character has a particular tag.
3210 *
3211 * Results:
3212 * The return value is 1 if the given tag is in effect at the character
3213 * given by linePtr and ch, and 0 otherwise.
3214 *
3215 * Side effects:
3216 * None.
3217 *
3218 *----------------------------------------------------------------------
3219 */
3220
3221 int
TkBTreeCharTagged(const TkTextIndex * indexPtr,TkTextTag * tagPtr)3222 TkBTreeCharTagged(
3223 const TkTextIndex *indexPtr,/* Indicates a character position at which to
3224 * check for a tag. */
3225 TkTextTag *tagPtr) /* Tag of interest. */
3226 {
3227 register Node *nodePtr;
3228 register TkTextLine *siblingLinePtr;
3229 register TkTextSegment *segPtr;
3230 TkTextSegment *toggleSegPtr;
3231 int toggles, index;
3232
3233 /*
3234 * Check for toggles for the tag in indexPtr's line but before indexPtr.
3235 * If there is one, its type indicates whether or not the character is
3236 * tagged.
3237 */
3238
3239 toggleSegPtr = NULL;
3240 for (index = 0, segPtr = indexPtr->linePtr->segPtr;
3241 (index + segPtr->size) <= indexPtr->byteIndex;
3242 index += segPtr->size, segPtr = segPtr->nextPtr) {
3243 if (((segPtr->typePtr == &tkTextToggleOnType)
3244 || (segPtr->typePtr == &tkTextToggleOffType))
3245 && (segPtr->body.toggle.tagPtr == tagPtr)) {
3246 toggleSegPtr = segPtr;
3247 }
3248 }
3249 if (toggleSegPtr != NULL) {
3250 return (toggleSegPtr->typePtr == &tkTextToggleOnType);
3251 }
3252
3253 /*
3254 * No toggle in this line. Look for toggles for the tag in lines that are
3255 * predecessors of indexPtr->linePtr but under the same level-0 node.
3256 */
3257
3258 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
3259 siblingLinePtr != indexPtr->linePtr;
3260 siblingLinePtr = siblingLinePtr->nextPtr) {
3261 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
3262 segPtr = segPtr->nextPtr) {
3263 if (((segPtr->typePtr == &tkTextToggleOnType)
3264 || (segPtr->typePtr == &tkTextToggleOffType))
3265 && (segPtr->body.toggle.tagPtr == tagPtr)) {
3266 toggleSegPtr = segPtr;
3267 }
3268 }
3269 }
3270 if (toggleSegPtr != NULL) {
3271 return (toggleSegPtr->typePtr == &tkTextToggleOnType);
3272 }
3273
3274 /*
3275 * No toggle in this node. Scan upwards through the ancestors of this
3276 * node, counting the number of toggles of the given tag in siblings that
3277 * precede that node.
3278 */
3279
3280 toggles = 0;
3281 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
3282 nodePtr = nodePtr->parentPtr) {
3283 register Node *siblingPtr;
3284 register Summary *summaryPtr;
3285
3286 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
3287 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
3288 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
3289 summaryPtr = summaryPtr->nextPtr) {
3290 if (summaryPtr->tagPtr == tagPtr) {
3291 toggles += summaryPtr->toggleCount;
3292 }
3293 }
3294 }
3295 if (nodePtr == tagPtr->tagRootPtr) {
3296 break;
3297 }
3298 }
3299
3300 /*
3301 * An odd number of toggles means that the tag is present at the given
3302 * point.
3303 */
3304
3305 return toggles & 1;
3306 }
3307
3308 /*
3309 *----------------------------------------------------------------------
3310 *
3311 * TkBTreeGetTags --
3312 *
3313 * Return information about all of the tags that are associated with a
3314 * particular character in a B-tree of text.
3315 *
3316 * Results:
3317 * The return value is a malloc-ed array containing pointers to
3318 * information for each of the tags that is associated with the character
3319 * at the position given by linePtr and ch. The word at *numTagsPtr is
3320 * filled in with the number of pointers in the array. It is up to the
3321 * caller to free the array by passing it to free. If there are no tags
3322 * at the given character then a NULL pointer is returned and *numTagsPtr
3323 * will be set to 0.
3324 *
3325 * Side effects:
3326 * None.
3327 *
3328 *----------------------------------------------------------------------
3329 */
3330
3331 /* ARGSUSED */
3332 TkTextTag **
TkBTreeGetTags(const TkTextIndex * indexPtr,const TkText * textPtr,int * numTagsPtr)3333 TkBTreeGetTags(
3334 const TkTextIndex *indexPtr,/* Indicates a particular position in the
3335 * B-tree. */
3336 const TkText *textPtr, /* If non-NULL, then only return tags for this
3337 * text widget (when there are peer
3338 * widgets). */
3339 int *numTagsPtr) /* Store number of tags found at this
3340 * location. */
3341 {
3342 register Node *nodePtr;
3343 register TkTextLine *siblingLinePtr;
3344 register TkTextSegment *segPtr;
3345 TkTextLine *linePtr;
3346 int src, dst, index;
3347 TagInfo tagInfo;
3348 #define NUM_TAG_INFOS 10
3349
3350 tagInfo.numTags = 0;
3351 tagInfo.arraySize = NUM_TAG_INFOS;
3352 tagInfo.tagPtrs = (TkTextTag **)
3353 ckalloc((unsigned) NUM_TAG_INFOS * sizeof(TkTextTag *));
3354 tagInfo.counts = (int *)
3355 ckalloc((unsigned) NUM_TAG_INFOS * sizeof(int));
3356
3357 /*
3358 * Record tag toggles within the line of indexPtr but preceding indexPtr.
3359 */
3360
3361 linePtr = indexPtr->linePtr;
3362 index = 0;
3363 segPtr = linePtr->segPtr;
3364 while ((index + segPtr->size) <= indexPtr->byteIndex) {
3365 if ((segPtr->typePtr == &tkTextToggleOnType)
3366 || (segPtr->typePtr == &tkTextToggleOffType)) {
3367 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
3368 }
3369 index += segPtr->size;
3370 segPtr = segPtr->nextPtr;
3371
3372 if (segPtr == NULL) {
3373 /*
3374 * Two logical lines merged into one display line through eliding
3375 * of a newline.
3376 */
3377
3378 linePtr = TkBTreeNextLine(NULL, linePtr);
3379 segPtr = linePtr->segPtr;
3380 }
3381 }
3382
3383 /*
3384 * Record toggles for tags in lines that are predecessors of
3385 * indexPtr->linePtr but under the same level-0 node.
3386 */
3387
3388 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
3389 siblingLinePtr != indexPtr->linePtr;
3390 siblingLinePtr = siblingLinePtr->nextPtr) {
3391 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
3392 segPtr = segPtr->nextPtr) {
3393 if ((segPtr->typePtr == &tkTextToggleOnType)
3394 || (segPtr->typePtr == &tkTextToggleOffType)) {
3395 IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
3396 }
3397 }
3398 }
3399
3400 /*
3401 * For each node in the ancestry of this line, record tag toggles for all
3402 * siblings that precede that node.
3403 */
3404
3405 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
3406 nodePtr = nodePtr->parentPtr) {
3407 register Node *siblingPtr;
3408 register Summary *summaryPtr;
3409
3410 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
3411 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
3412 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
3413 summaryPtr = summaryPtr->nextPtr) {
3414 if (summaryPtr->toggleCount & 1) {
3415 IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount,
3416 &tagInfo);
3417 }
3418 }
3419 }
3420 }
3421
3422 /*
3423 * Go through the tag information and squash out all of the tags that have
3424 * even toggle counts (these tags exist before the point of interest, but
3425 * not at the desired character itself). Also squash out all tags that
3426 * don't belong to the requested widget.
3427 */
3428
3429 for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
3430 if (tagInfo.counts[src] & 1) {
3431 const TkText *tagTextPtr = tagInfo.tagPtrs[src]->textPtr;
3432
3433 if (tagTextPtr==NULL || textPtr==NULL || tagTextPtr==textPtr) {
3434 tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
3435 dst++;
3436 }
3437 }
3438 }
3439 *numTagsPtr = dst;
3440 ckfree((char *) tagInfo.counts);
3441 if (dst == 0) {
3442 ckfree((char *) tagInfo.tagPtrs);
3443 return NULL;
3444 }
3445 return tagInfo.tagPtrs;
3446 }
3447
3448 /*
3449 *----------------------------------------------------------------------
3450 *
3451 * TkTextIsElided --
3452 *
3453 * Special case to just return information about elided attribute.
3454 * Specialized from TkBTreeGetTags(indexPtr, textPtr, numTagsPtr) and
3455 * GetStyle(textPtr, indexPtr). Just need to keep track of invisibility
3456 * settings for each priority, pick highest one active at end.
3457 *
3458 * Note that this returns all elide information up to and including the
3459 * given index (quite obviously). However, this does mean that if
3460 * indexPtr is a line-start and one then iterates from the beginning of
3461 * that line forwards, one will actually revisit the segPtrs of size zero
3462 * (for tag toggling, for example) which have already been seen here.
3463 *
3464 * For this reason we fill in the fields 'segPtr' and 'segOffset' of
3465 * elideInfo, enabling our caller easily to calculate incremental changes
3466 * from where we left off.
3467 *
3468 * Results:
3469 * Returns whether this text should be elided or not.
3470 *
3471 * Optionally returns more detailed information in elideInfo.
3472 *
3473 * Side effects:
3474 * None.
3475 *
3476 *----------------------------------------------------------------------
3477 */
3478
3479 /* ARGSUSED */
3480 int
TkTextIsElided(const TkText * textPtr,const TkTextIndex * indexPtr,TkTextElideInfo * elideInfo)3481 TkTextIsElided(
3482 const TkText *textPtr, /* Overall information about text widget. */
3483 const TkTextIndex *indexPtr,/* The character in the text for which display
3484 * information is wanted. */
3485 TkTextElideInfo *elideInfo) /* NULL or a pointer to a structure in which
3486 * indexPtr's elide state will be stored and
3487 * returned. */
3488 {
3489 register Node *nodePtr;
3490 register TkTextLine *siblingLinePtr;
3491 register TkTextSegment *segPtr;
3492 register TkTextTag *tagPtr = NULL;
3493 register int i, index;
3494 register TkTextElideInfo *infoPtr;
3495 TkTextLine *linePtr;
3496 int elide;
3497
3498 if (elideInfo == NULL) {
3499 infoPtr = (TkTextElideInfo *)
3500 ckalloc((unsigned) sizeof(TkTextElideInfo));
3501 } else {
3502 infoPtr = elideInfo;
3503 }
3504
3505 infoPtr->elide = 0; /* If nobody says otherwise, it's visible. */
3506 infoPtr->tagCnts = infoPtr->deftagCnts;
3507 infoPtr->tagPtrs = infoPtr->deftagPtrs;
3508 infoPtr->numTags = textPtr->sharedTextPtr->numTags;
3509
3510 /*
3511 * Almost always avoid malloc, so stay out of system calls.
3512 */
3513
3514 if (LOTSA_TAGS < infoPtr->numTags) {
3515 infoPtr->tagCnts = (int *)
3516 ckalloc((unsigned) sizeof(int) * infoPtr->numTags);
3517 infoPtr->tagPtrs = (TkTextTag **)
3518 ckalloc((unsigned) sizeof(TkTextTag *) * infoPtr->numTags);
3519 }
3520
3521 for (i=0; i<infoPtr->numTags; i++) {
3522 infoPtr->tagCnts[i] = 0;
3523 }
3524
3525 /*
3526 * Record tag toggles within the line of indexPtr but preceding indexPtr.
3527 */
3528
3529 index = 0;
3530 linePtr = indexPtr->linePtr;
3531 segPtr = linePtr->segPtr;
3532 while ((index + segPtr->size) <= indexPtr->byteIndex) {
3533 if ((segPtr->typePtr == &tkTextToggleOnType)
3534 || (segPtr->typePtr == &tkTextToggleOffType)) {
3535 tagPtr = segPtr->body.toggle.tagPtr;
3536 if (tagPtr->elideString != NULL) {
3537 infoPtr->tagPtrs[tagPtr->priority] = tagPtr;
3538 infoPtr->tagCnts[tagPtr->priority]++;
3539 }
3540 }
3541
3542 index += segPtr->size;
3543 segPtr = segPtr->nextPtr;
3544 if (segPtr == NULL) {
3545 /*
3546 * Two logical lines merged into one display line through eliding
3547 * of a newline.
3548 */
3549
3550 linePtr = TkBTreeNextLine(NULL, linePtr);
3551 segPtr = linePtr->segPtr;
3552 }
3553 }
3554
3555 /*
3556 * Store the first segPtr we haven't examined completely so that our
3557 * caller knows where to start.
3558 */
3559
3560 infoPtr->segPtr = segPtr;
3561 infoPtr->segOffset = index;
3562
3563 /*
3564 * Record toggles for tags in lines that are predecessors of
3565 * indexPtr->linePtr but under the same level-0 node.
3566 */
3567
3568 for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
3569 siblingLinePtr != indexPtr->linePtr;
3570 siblingLinePtr = siblingLinePtr->nextPtr) {
3571 for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
3572 segPtr = segPtr->nextPtr) {
3573 if ((segPtr->typePtr == &tkTextToggleOnType)
3574 || (segPtr->typePtr == &tkTextToggleOffType)) {
3575 tagPtr = segPtr->body.toggle.tagPtr;
3576 if (tagPtr->elideString != NULL) {
3577 infoPtr->tagPtrs[tagPtr->priority] = tagPtr;
3578 infoPtr->tagCnts[tagPtr->priority]++;
3579 }
3580 }
3581 }
3582 }
3583
3584 /*
3585 * For each node in the ancestry of this line, record tag toggles for all
3586 * siblings that precede that node.
3587 */
3588
3589 for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
3590 nodePtr = nodePtr->parentPtr) {
3591 register Node *siblingPtr;
3592 register Summary *summaryPtr;
3593
3594 for (siblingPtr = nodePtr->parentPtr->children.nodePtr;
3595 siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
3596 for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
3597 summaryPtr = summaryPtr->nextPtr) {
3598 if (summaryPtr->toggleCount & 1) {
3599 tagPtr = summaryPtr->tagPtr;
3600 if (tagPtr->elideString != NULL) {
3601 infoPtr->tagPtrs[tagPtr->priority] = tagPtr;
3602 infoPtr->tagCnts[tagPtr->priority] +=
3603 summaryPtr->toggleCount;
3604 }
3605 }
3606 }
3607 }
3608 }
3609
3610 /*
3611 * Now traverse from highest priority to lowest, take elided value from
3612 * first odd count (= on).
3613 */
3614
3615 infoPtr->elidePriority = -1;
3616 for (i = infoPtr->numTags-1; i >=0; i--) {
3617 if (infoPtr->tagCnts[i] & 1) {
3618 infoPtr->elide = infoPtr->tagPtrs[i]->elide;
3619
3620 /*
3621 * Note: i == infoPtr->tagPtrs[i]->priority
3622 */
3623
3624 infoPtr->elidePriority = i;
3625 break;
3626 }
3627 }
3628
3629 elide = infoPtr->elide;
3630
3631 if (elideInfo == NULL) {
3632 if (LOTSA_TAGS < infoPtr->numTags) {
3633 ckfree((char *) infoPtr->tagCnts);
3634 ckfree((char *) infoPtr->tagPtrs);
3635 }
3636
3637 ckfree((char *) infoPtr);
3638 }
3639
3640 return elide;
3641 }
3642
3643 /*
3644 *----------------------------------------------------------------------
3645 *
3646 * TkTextFreeElideInfo --
3647 *
3648 * This is a utility function used to free up any memory allocated by the
3649 * TkTextIsElided function above.
3650 *
3651 * Results:
3652 * None.
3653 *
3654 * Side effects:
3655 * Memory may be freed.
3656 *
3657 *----------------------------------------------------------------------
3658 */
3659
3660 void
TkTextFreeElideInfo(TkTextElideInfo * elideInfo)3661 TkTextFreeElideInfo(
3662 TkTextElideInfo *elideInfo) /* Free any allocated memory in this
3663 * structure. */
3664 {
3665 if (LOTSA_TAGS < elideInfo->numTags) {
3666 ckfree((char *) elideInfo->tagCnts);
3667 ckfree((char *) elideInfo->tagPtrs);
3668 }
3669 }
3670
3671 /*
3672 *----------------------------------------------------------------------
3673 *
3674 * IncCount --
3675 *
3676 * This is a utility function used by TkBTreeGetTags. It increments the
3677 * count for a particular tag, adding a new entry for that tag if there
3678 * wasn't one previously.
3679 *
3680 * Results:
3681 * None.
3682 *
3683 * Side effects:
3684 * The information at *tagInfoPtr may be modified, and the arrays may be
3685 * reallocated to make them larger.
3686 *
3687 *----------------------------------------------------------------------
3688 */
3689
3690 static void
IncCount(TkTextTag * tagPtr,int inc,TagInfo * tagInfoPtr)3691 IncCount(
3692 TkTextTag *tagPtr, /* Handle for tag. */
3693 int inc, /* Amount by which to increment tag count. */
3694 TagInfo *tagInfoPtr) /* Holds cumulative information about tags;
3695 * increment count here. */
3696 {
3697 register TkTextTag **tagPtrPtr;
3698 int count;
3699
3700 for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
3701 count > 0; tagPtrPtr++, count--) {
3702 if (*tagPtrPtr == tagPtr) {
3703 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
3704 return;
3705 }
3706 }
3707
3708 /*
3709 * There isn't currently an entry for this tag, so we have to make a new
3710 * one. If the arrays are full, then enlarge the arrays first.
3711 */
3712
3713 if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
3714 TkTextTag **newTags;
3715 int *newCounts, newSize;
3716
3717 newSize = 2 * tagInfoPtr->arraySize;
3718 newTags = (TkTextTag **)
3719 ckalloc((unsigned) newSize * sizeof(TkTextTag *));
3720 memcpy(newTags, tagInfoPtr->tagPtrs,
3721 tagInfoPtr->arraySize * sizeof(TkTextTag *));
3722 ckfree((char *) tagInfoPtr->tagPtrs);
3723 tagInfoPtr->tagPtrs = newTags;
3724 newCounts = (int *) ckalloc((unsigned) newSize * sizeof(int));
3725 memcpy(newCounts, tagInfoPtr->counts,
3726 tagInfoPtr->arraySize * sizeof(int));
3727 ckfree((char *) tagInfoPtr->counts);
3728 tagInfoPtr->counts = newCounts;
3729 tagInfoPtr->arraySize = newSize;
3730 }
3731
3732 tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
3733 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
3734 tagInfoPtr->numTags++;
3735 }
3736
3737 /*
3738 *----------------------------------------------------------------------
3739 *
3740 * TkBTreeCheck --
3741 *
3742 * This function runs a set of consistency checks over a B-tree and
3743 * panics if any inconsistencies are found.
3744 *
3745 * Results:
3746 * None.
3747 *
3748 * Side effects:
3749 * If a structural defect is found, the function panics with an error
3750 * message.
3751 *
3752 *----------------------------------------------------------------------
3753 */
3754
3755 void
TkBTreeCheck(TkTextBTree tree)3756 TkBTreeCheck(
3757 TkTextBTree tree) /* Tree to check. */
3758 {
3759 BTree *treePtr = (BTree *) tree;
3760 register Summary *summaryPtr;
3761 register Node *nodePtr;
3762 register TkTextLine *linePtr;
3763 register TkTextSegment *segPtr;
3764 register TkTextTag *tagPtr;
3765 Tcl_HashEntry *entryPtr;
3766 Tcl_HashSearch search;
3767 int count;
3768
3769 /*
3770 * Make sure that the tag toggle counts and the tag root pointers are OK.
3771 */
3772
3773 for (entryPtr=Tcl_FirstHashEntry(&treePtr->sharedTextPtr->tagTable,&search);
3774 entryPtr != NULL ; entryPtr = Tcl_NextHashEntry(&search)) {
3775 tagPtr = (TkTextTag *) Tcl_GetHashValue(entryPtr);
3776 nodePtr = tagPtr->tagRootPtr;
3777 if (nodePtr == NULL) {
3778 if (tagPtr->toggleCount != 0) {
3779 Tcl_Panic("TkBTreeCheck found \"%s\" with toggles (%d) but no root",
3780 tagPtr->name, tagPtr->toggleCount);
3781 }
3782 continue; /* No ranges for the tag. */
3783 } else if (tagPtr->toggleCount == 0) {
3784 Tcl_Panic("TkBTreeCheck found root for \"%s\" with no toggles",
3785 tagPtr->name);
3786 } else if (tagPtr->toggleCount & 1) {
3787 Tcl_Panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
3788 tagPtr->name, tagPtr->toggleCount);
3789 }
3790 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
3791 summaryPtr = summaryPtr->nextPtr) {
3792 if (summaryPtr->tagPtr == tagPtr) {
3793 Tcl_Panic("TkBTreeCheck found root node with summary info");
3794 }
3795 }
3796 count = 0;
3797 if (nodePtr->level > 0) {
3798 for (nodePtr = nodePtr->children.nodePtr ; nodePtr != NULL ;
3799 nodePtr = nodePtr->nextPtr) {
3800 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
3801 summaryPtr = summaryPtr->nextPtr) {
3802 if (summaryPtr->tagPtr == tagPtr) {
3803 count += summaryPtr->toggleCount;
3804 }
3805 }
3806 }
3807 } else {
3808 for (linePtr = nodePtr->children.linePtr ; linePtr != NULL ;
3809 linePtr = linePtr->nextPtr) {
3810 for (segPtr = linePtr->segPtr; segPtr != NULL;
3811 segPtr = segPtr->nextPtr) {
3812 if ((segPtr->typePtr == &tkTextToggleOnType ||
3813 segPtr->typePtr == &tkTextToggleOffType) &&
3814 segPtr->body.toggle.tagPtr == tagPtr) {
3815 count++;
3816 }
3817 }
3818 }
3819 }
3820 if (count != tagPtr->toggleCount) {
3821 Tcl_Panic("TkBTreeCheck toggleCount (%d) wrong for \"%s\" should be (%d)",
3822 tagPtr->toggleCount, tagPtr->name, count);
3823 }
3824 }
3825
3826 /*
3827 * Call a recursive function to do the main body of checks.
3828 */
3829
3830 nodePtr = treePtr->rootPtr;
3831 CheckNodeConsistency(treePtr->rootPtr, treePtr->pixelReferences);
3832
3833 /*
3834 * Make sure that there are at least two lines in the text and that the
3835 * last line has no characters except a newline.
3836 */
3837
3838 if (nodePtr->numLines < 2) {
3839 Tcl_Panic("TkBTreeCheck: less than 2 lines in tree");
3840 }
3841 while (nodePtr->level > 0) {
3842 nodePtr = nodePtr->children.nodePtr;
3843 while (nodePtr->nextPtr != NULL) {
3844 nodePtr = nodePtr->nextPtr;
3845 }
3846 }
3847 linePtr = nodePtr->children.linePtr;
3848 while (linePtr->nextPtr != NULL) {
3849 linePtr = linePtr->nextPtr;
3850 }
3851 segPtr = linePtr->segPtr;
3852 while ((segPtr->typePtr == &tkTextToggleOffType)
3853 || (segPtr->typePtr == &tkTextRightMarkType)
3854 || (segPtr->typePtr == &tkTextLeftMarkType)) {
3855 /*
3856 * It's OK to toggle a tag off in the last line, but not to start a
3857 * new range. It's also OK to have marks in the last line.
3858 */
3859
3860 segPtr = segPtr->nextPtr;
3861 }
3862 if (segPtr->typePtr != &tkTextCharType) {
3863 Tcl_Panic("TkBTreeCheck: last line has bogus segment type");
3864 }
3865 if (segPtr->nextPtr != NULL) {
3866 Tcl_Panic("TkBTreeCheck: last line has too many segments");
3867 }
3868 if (segPtr->size != 1) {
3869 Tcl_Panic("TkBTreeCheck: last line has wrong # characters: %d",
3870 segPtr->size);
3871 }
3872 if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) {
3873 Tcl_Panic("TkBTreeCheck: last line had bad value: %s",
3874 segPtr->body.chars);
3875 }
3876 }
3877
3878 /*
3879 *----------------------------------------------------------------------
3880 *
3881 * CheckNodeConsistency --
3882 *
3883 * This function is called as part of consistency checking for B-trees:
3884 * it checks several aspects of a node and also runs checks recursively
3885 * on the node's children.
3886 *
3887 * Results:
3888 * None.
3889 *
3890 * Side effects:
3891 * If anything suspicious is found in the tree structure, the function
3892 * panics.
3893 *
3894 *----------------------------------------------------------------------
3895 */
3896
3897 static void
CheckNodeConsistency(register Node * nodePtr,int references)3898 CheckNodeConsistency(
3899 register Node *nodePtr, /* Node whose subtree should be checked. */
3900 int references) /* Number of referring widgets which have
3901 * pixel counts. */
3902 {
3903 register Node *childNodePtr;
3904 register Summary *summaryPtr, *summaryPtr2;
3905 register TkTextLine *linePtr;
3906 register TkTextSegment *segPtr;
3907 int numChildren, numLines, toggleCount, minChildren, i;
3908 int *numPixels;
3909 int pixels[PIXEL_CLIENTS];
3910
3911 if (nodePtr->parentPtr != NULL) {
3912 minChildren = MIN_CHILDREN;
3913 } else if (nodePtr->level > 0) {
3914 minChildren = 2;
3915 } else {
3916 minChildren = 1;
3917 }
3918 if ((nodePtr->numChildren < minChildren)
3919 || (nodePtr->numChildren > MAX_CHILDREN)) {
3920 Tcl_Panic("CheckNodeConsistency: bad child count (%d)",
3921 nodePtr->numChildren);
3922 }
3923
3924 numChildren = 0;
3925 numLines = 0;
3926 if (references > PIXEL_CLIENTS) {
3927 numPixels = (int *) ckalloc(sizeof(int) * references);
3928 } else {
3929 numPixels = pixels;
3930 }
3931 for (i = 0; i<references; i++) {
3932 numPixels[i] = 0;
3933 }
3934
3935 if (nodePtr->level == 0) {
3936 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
3937 linePtr = linePtr->nextPtr) {
3938 if (linePtr->parentPtr != nodePtr) {
3939 Tcl_Panic("CheckNodeConsistency: line doesn't point to parent");
3940 }
3941 if (linePtr->segPtr == NULL) {
3942 Tcl_Panic("CheckNodeConsistency: line has no segments");
3943 }
3944 for (segPtr = linePtr->segPtr; segPtr != NULL;
3945 segPtr = segPtr->nextPtr) {
3946 if (segPtr->typePtr->checkProc != NULL) {
3947 (*segPtr->typePtr->checkProc)(segPtr, linePtr);
3948 }
3949 if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity)
3950 && (segPtr->nextPtr != NULL)
3951 && (segPtr->nextPtr->size == 0)
3952 && (segPtr->nextPtr->typePtr->leftGravity)) {
3953 Tcl_Panic("CheckNodeConsistency: wrong segment order for gravity");
3954 }
3955 if ((segPtr->nextPtr == NULL)
3956 && (segPtr->typePtr != &tkTextCharType)) {
3957 Tcl_Panic("CheckNodeConsistency: line ended with wrong type");
3958 }
3959 }
3960 numChildren++;
3961 numLines++;
3962 for (i = 0; i<references; i++) {
3963 numPixels[i] += linePtr->pixels[2 * i];
3964 }
3965 }
3966 } else {
3967 for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
3968 childNodePtr = childNodePtr->nextPtr) {
3969 if (childNodePtr->parentPtr != nodePtr) {
3970 Tcl_Panic("CheckNodeConsistency: node doesn't point to parent");
3971 }
3972 if (childNodePtr->level != (nodePtr->level-1)) {
3973 Tcl_Panic("CheckNodeConsistency: level mismatch (%d %d)",
3974 nodePtr->level, childNodePtr->level);
3975 }
3976 CheckNodeConsistency(childNodePtr, references);
3977 for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
3978 summaryPtr = summaryPtr->nextPtr) {
3979 for (summaryPtr2 = nodePtr->summaryPtr; ;
3980 summaryPtr2 = summaryPtr2->nextPtr) {
3981 if (summaryPtr2 == NULL) {
3982 if (summaryPtr->tagPtr->tagRootPtr == nodePtr) {
3983 break;
3984 }
3985 Tcl_Panic("CheckNodeConsistency: node tag \"%s\" not %s",
3986 summaryPtr->tagPtr->name,
3987 "present in parent summaries");
3988 }
3989 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
3990 break;
3991 }
3992 }
3993 }
3994 numChildren++;
3995 numLines += childNodePtr->numLines;
3996 for (i = 0; i<references; i++) {
3997 numPixels[i] += childNodePtr->numPixels[i];
3998 }
3999 }
4000 }
4001 if (numChildren != nodePtr->numChildren) {
4002 Tcl_Panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
4003 numChildren, nodePtr->numChildren);
4004 }
4005 if (numLines != nodePtr->numLines) {
4006 Tcl_Panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
4007 numLines, nodePtr->numLines);
4008 }
4009 for (i = 0; i<references; i++) {
4010 if (numPixels[i] != nodePtr->numPixels[i]) {
4011 Tcl_Panic("CheckNodeConsistency: mismatch in numPixels (%d %d) for widget (%d)",
4012 numPixels[i], nodePtr->numPixels[i], i);
4013 }
4014 }
4015 if (references > PIXEL_CLIENTS) {
4016 ckfree((char *) numPixels);
4017 }
4018
4019 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
4020 summaryPtr = summaryPtr->nextPtr) {
4021 if (summaryPtr->tagPtr->toggleCount == summaryPtr->toggleCount) {
4022 Tcl_Panic("CheckNodeConsistency: found unpruned root for \"%s\"",
4023 summaryPtr->tagPtr->name);
4024 }
4025 toggleCount = 0;
4026 if (nodePtr->level == 0) {
4027 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
4028 linePtr = linePtr->nextPtr) {
4029 for (segPtr = linePtr->segPtr; segPtr != NULL;
4030 segPtr = segPtr->nextPtr) {
4031 if ((segPtr->typePtr != &tkTextToggleOnType)
4032 && (segPtr->typePtr != &tkTextToggleOffType)) {
4033 continue;
4034 }
4035 if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) {
4036 toggleCount++;
4037 }
4038 }
4039 }
4040 } else {
4041 for (childNodePtr = nodePtr->children.nodePtr;
4042 childNodePtr != NULL;
4043 childNodePtr = childNodePtr->nextPtr) {
4044 for (summaryPtr2 = childNodePtr->summaryPtr;
4045 summaryPtr2 != NULL;
4046 summaryPtr2 = summaryPtr2->nextPtr) {
4047 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
4048 toggleCount += summaryPtr2->toggleCount;
4049 }
4050 }
4051 }
4052 }
4053 if (toggleCount != summaryPtr->toggleCount) {
4054 Tcl_Panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
4055 toggleCount, summaryPtr->toggleCount);
4056 }
4057 for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
4058 summaryPtr2 = summaryPtr2->nextPtr) {
4059 if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
4060 Tcl_Panic("CheckNodeConsistency: duplicated node tag: %s",
4061 summaryPtr->tagPtr->name);
4062 }
4063 }
4064 }
4065 }
4066
4067 /*
4068 *----------------------------------------------------------------------
4069 *
4070 * Rebalance --
4071 *
4072 * This function is called when a node of a B-tree appears to be out of
4073 * balance (too many children, or too few). It rebalances that node and
4074 * all of its ancestors in the tree.
4075 *
4076 * Results:
4077 * None.
4078 *
4079 * Side effects:
4080 * The internal structure of treePtr may change.
4081 *
4082 *----------------------------------------------------------------------
4083 */
4084
4085 static void
Rebalance(BTree * treePtr,register Node * nodePtr)4086 Rebalance(
4087 BTree *treePtr, /* Tree that is being rebalanced. */
4088 register Node *nodePtr) /* Node that may be out of balance. */
4089 {
4090 /*
4091 * Loop over the entire ancestral chain of the node, working up through
4092 * the tree one node at a time until the root node has been processed.
4093 */
4094
4095 for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
4096 register Node *newPtr, *childPtr;
4097 register TkTextLine *linePtr;
4098 int i;
4099
4100 /*
4101 * Check to see if the node has too many children. If it does, then
4102 * split off all but the first MIN_CHILDREN into a separate node
4103 * following the original one. Then repeat until the node has a decent
4104 * size.
4105 */
4106
4107 if (nodePtr->numChildren > MAX_CHILDREN) {
4108 while (1) {
4109 /*
4110 * If the node being split is the root node, then make a new
4111 * root node above it first.
4112 */
4113
4114 if (nodePtr->parentPtr == NULL) {
4115 newPtr = (Node *) ckalloc(sizeof(Node));
4116 newPtr->parentPtr = NULL;
4117 newPtr->nextPtr = NULL;
4118 newPtr->summaryPtr = NULL;
4119 newPtr->level = nodePtr->level + 1;
4120 newPtr->children.nodePtr = nodePtr;
4121 newPtr->numChildren = 1;
4122 newPtr->numLines = nodePtr->numLines;
4123 newPtr->numPixels = (int *)
4124 ckalloc(sizeof(int) * treePtr->pixelReferences);
4125 for (i=0; i<treePtr->pixelReferences; i++) {
4126 newPtr->numPixels[i] = nodePtr->numPixels[i];
4127 }
4128 RecomputeNodeCounts(treePtr, newPtr);
4129 treePtr->rootPtr = newPtr;
4130 }
4131 newPtr = (Node *) ckalloc(sizeof(Node));
4132 newPtr->numPixels = (int *)
4133 ckalloc(sizeof(int) * treePtr->pixelReferences);
4134 for (i=0; i<treePtr->pixelReferences; i++) {
4135 newPtr->numPixels[i] = 0;
4136 }
4137 newPtr->parentPtr = nodePtr->parentPtr;
4138 newPtr->nextPtr = nodePtr->nextPtr;
4139 nodePtr->nextPtr = newPtr;
4140 newPtr->summaryPtr = NULL;
4141 newPtr->level = nodePtr->level;
4142 newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
4143 if (nodePtr->level == 0) {
4144 for (i = MIN_CHILDREN-1,
4145 linePtr = nodePtr->children.linePtr;
4146 i > 0; i--, linePtr = linePtr->nextPtr) {
4147 /* Empty loop body. */
4148 }
4149 newPtr->children.linePtr = linePtr->nextPtr;
4150 linePtr->nextPtr = NULL;
4151 } else {
4152 for (i = MIN_CHILDREN-1,
4153 childPtr = nodePtr->children.nodePtr;
4154 i > 0; i--, childPtr = childPtr->nextPtr) {
4155 /* Empty loop body. */
4156 }
4157 newPtr->children.nodePtr = childPtr->nextPtr;
4158 childPtr->nextPtr = NULL;
4159 }
4160 RecomputeNodeCounts(treePtr, nodePtr);
4161 nodePtr->parentPtr->numChildren++;
4162 nodePtr = newPtr;
4163 if (nodePtr->numChildren <= MAX_CHILDREN) {
4164 RecomputeNodeCounts(treePtr, nodePtr);
4165 break;
4166 }
4167 }
4168 }
4169
4170 while (nodePtr->numChildren < MIN_CHILDREN) {
4171 register Node *otherPtr;
4172 Node *halfwayNodePtr = NULL; /* Initialization needed only */
4173 TkTextLine *halfwayLinePtr = NULL; /* to prevent cc warnings. */
4174 int totalChildren, firstChildren, i;
4175
4176 /*
4177 * Too few children for this node. If this is the root then, it's
4178 * OK for it to have less than MIN_CHILDREN children as long as
4179 * it's got at least two. If it has only one (and isn't at level
4180 * 0), then chop the root node out of the tree and use its child
4181 * as the new root.
4182 */
4183
4184 if (nodePtr->parentPtr == NULL) {
4185 if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
4186 treePtr->rootPtr = nodePtr->children.nodePtr;
4187 treePtr->rootPtr->parentPtr = NULL;
4188 DeleteSummaries(nodePtr->summaryPtr);
4189 ckfree((char *) nodePtr);
4190 }
4191 return;
4192 }
4193
4194 /*
4195 * Not the root. Make sure that there are siblings to balance
4196 * with.
4197 */
4198
4199 if (nodePtr->parentPtr->numChildren < 2) {
4200 Rebalance(treePtr, nodePtr->parentPtr);
4201 continue;
4202 }
4203
4204 /*
4205 * Find a sibling neighbor to borrow from, and arrange for nodePtr
4206 * to be the earlier of the pair.
4207 */
4208
4209 if (nodePtr->nextPtr == NULL) {
4210 for (otherPtr = nodePtr->parentPtr->children.nodePtr;
4211 otherPtr->nextPtr != nodePtr;
4212 otherPtr = otherPtr->nextPtr) {
4213 /* Empty loop body. */
4214 }
4215 nodePtr = otherPtr;
4216 }
4217 otherPtr = nodePtr->nextPtr;
4218
4219 /*
4220 * We're going to either merge the two siblings together into one
4221 * node or redivide the children among them to balance their
4222 * loads. As preparation, join their two child lists into a single
4223 * list and remember the half-way point in the list.
4224 */
4225
4226 totalChildren = nodePtr->numChildren + otherPtr->numChildren;
4227 firstChildren = totalChildren/2;
4228 if (nodePtr->children.nodePtr == NULL) {
4229 nodePtr->children = otherPtr->children;
4230 otherPtr->children.nodePtr = NULL;
4231 otherPtr->children.linePtr = NULL;
4232 }
4233 if (nodePtr->level == 0) {
4234 register TkTextLine *linePtr;
4235
4236 for (linePtr = nodePtr->children.linePtr, i = 1;
4237 linePtr->nextPtr != NULL;
4238 linePtr = linePtr->nextPtr, i++) {
4239 if (i == firstChildren) {
4240 halfwayLinePtr = linePtr;
4241 }
4242 }
4243 linePtr->nextPtr = otherPtr->children.linePtr;
4244 while (i <= firstChildren) {
4245 halfwayLinePtr = linePtr;
4246 linePtr = linePtr->nextPtr;
4247 i++;
4248 }
4249 } else {
4250 register Node *childPtr;
4251
4252 for (childPtr = nodePtr->children.nodePtr, i = 1;
4253 childPtr->nextPtr != NULL;
4254 childPtr = childPtr->nextPtr, i++) {
4255 if (i <= firstChildren) {
4256 if (i == firstChildren) {
4257 halfwayNodePtr = childPtr;
4258 }
4259 }
4260 }
4261 childPtr->nextPtr = otherPtr->children.nodePtr;
4262 while (i <= firstChildren) {
4263 halfwayNodePtr = childPtr;
4264 childPtr = childPtr->nextPtr;
4265 i++;
4266 }
4267 }
4268
4269 /*
4270 * If the two siblings can simply be merged together, do it.
4271 */
4272
4273 if (totalChildren <= MAX_CHILDREN) {
4274 RecomputeNodeCounts(treePtr, nodePtr);
4275 nodePtr->nextPtr = otherPtr->nextPtr;
4276 nodePtr->parentPtr->numChildren--;
4277 DeleteSummaries(otherPtr->summaryPtr);
4278 ckfree((char *) otherPtr);
4279 continue;
4280 }
4281
4282 /*
4283 * The siblings can't be merged, so just divide their children
4284 * evenly between them.
4285 */
4286
4287 if (nodePtr->level == 0) {
4288 otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
4289 halfwayLinePtr->nextPtr = NULL;
4290 } else {
4291 otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
4292 halfwayNodePtr->nextPtr = NULL;
4293 }
4294 RecomputeNodeCounts(treePtr, nodePtr);
4295 RecomputeNodeCounts(treePtr, otherPtr);
4296 }
4297 }
4298 }
4299
4300 /*
4301 *----------------------------------------------------------------------
4302 *
4303 * RecomputeNodeCounts --
4304 *
4305 * This function is called to recompute all the counts in a node (tags,
4306 * child information, etc.) by scanning the information in its
4307 * descendants. This function is called during rebalancing when a node's
4308 * child structure has changed.
4309 *
4310 * Results:
4311 * None.
4312 *
4313 * Side effects:
4314 * The tag counts for nodePtr are modified to reflect its current child
4315 * structure, as are its numChildren and numLines fields. Also, all of
4316 * the childrens' parentPtr fields are made to point to nodePtr.
4317 *
4318 *----------------------------------------------------------------------
4319 */
4320
4321 static void
RecomputeNodeCounts(register BTree * treePtr,register Node * nodePtr)4322 RecomputeNodeCounts(
4323 register BTree *treePtr, /* The whole B-tree. */
4324 register Node *nodePtr) /* Node whose tag summary information must be
4325 * recomputed. */
4326 {
4327 register Summary *summaryPtr, *summaryPtr2;
4328 register Node *childPtr;
4329 register TkTextLine *linePtr;
4330 register TkTextSegment *segPtr;
4331 TkTextTag *tagPtr;
4332 int ref;
4333
4334 /*
4335 * Zero out all the existing counts for the node, but don't delete the
4336 * existing Summary records (most of them will probably be reused).
4337 */
4338
4339 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
4340 summaryPtr = summaryPtr->nextPtr) {
4341 summaryPtr->toggleCount = 0;
4342 }
4343 nodePtr->numChildren = 0;
4344 nodePtr->numLines = 0;
4345 for (ref = 0; ref<treePtr->pixelReferences; ref++) {
4346 nodePtr->numPixels[ref] = 0;
4347 }
4348
4349 /*
4350 * Scan through the children, adding the childrens' tag counts into the
4351 * node's tag counts and adding new Summary structures if necessary.
4352 */
4353
4354 if (nodePtr->level == 0) {
4355 for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
4356 linePtr = linePtr->nextPtr) {
4357 nodePtr->numChildren++;
4358 nodePtr->numLines++;
4359 for (ref = 0; ref<treePtr->pixelReferences; ref++) {
4360 nodePtr->numPixels[ref] += linePtr->pixels[2 * ref];
4361 }
4362 linePtr->parentPtr = nodePtr;
4363 for (segPtr = linePtr->segPtr; segPtr != NULL;
4364 segPtr = segPtr->nextPtr) {
4365 if (((segPtr->typePtr != &tkTextToggleOnType)
4366 && (segPtr->typePtr != &tkTextToggleOffType))
4367 || !(segPtr->body.toggle.inNodeCounts)) {
4368 continue;
4369 }
4370 tagPtr = segPtr->body.toggle.tagPtr;
4371 for (summaryPtr = nodePtr->summaryPtr; ;
4372 summaryPtr = summaryPtr->nextPtr) {
4373 if (summaryPtr == NULL) {
4374 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
4375 summaryPtr->tagPtr = tagPtr;
4376 summaryPtr->toggleCount = 1;
4377 summaryPtr->nextPtr = nodePtr->summaryPtr;
4378 nodePtr->summaryPtr = summaryPtr;
4379 break;
4380 }
4381 if (summaryPtr->tagPtr == tagPtr) {
4382 summaryPtr->toggleCount++;
4383 break;
4384 }
4385 }
4386 }
4387 }
4388 } else {
4389 for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
4390 childPtr = childPtr->nextPtr) {
4391 nodePtr->numChildren++;
4392 nodePtr->numLines += childPtr->numLines;
4393 for (ref = 0; ref<treePtr->pixelReferences; ref++) {
4394 nodePtr->numPixels[ref] += childPtr->numPixels[ref];
4395 }
4396 childPtr->parentPtr = nodePtr;
4397 for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
4398 summaryPtr2 = summaryPtr2->nextPtr) {
4399 for (summaryPtr = nodePtr->summaryPtr; ;
4400 summaryPtr = summaryPtr->nextPtr) {
4401 if (summaryPtr == NULL) {
4402 summaryPtr = (Summary *) ckalloc(sizeof(Summary));
4403 summaryPtr->tagPtr = summaryPtr2->tagPtr;
4404 summaryPtr->toggleCount = summaryPtr2->toggleCount;
4405 summaryPtr->nextPtr = nodePtr->summaryPtr;
4406 nodePtr->summaryPtr = summaryPtr;
4407 break;
4408 }
4409 if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
4410 summaryPtr->toggleCount += summaryPtr2->toggleCount;
4411 break;
4412 }
4413 }
4414 }
4415 }
4416 }
4417
4418 /*
4419 * Scan through the node's tag records again and delete any Summary
4420 * records that still have a zero count, or that have all the toggles.
4421 * The node with the children that account for all the tags toggles have
4422 * no summary information, and they become the tagRootPtr for the tag.
4423 */
4424
4425 summaryPtr2 = NULL;
4426 for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
4427 if (summaryPtr->toggleCount > 0 &&
4428 summaryPtr->toggleCount < summaryPtr->tagPtr->toggleCount) {
4429 if (nodePtr->level == summaryPtr->tagPtr->tagRootPtr->level) {
4430 /*
4431 * The tag's root node split and some toggles left. The tag
4432 * root must move up a level.
4433 */
4434
4435 summaryPtr->tagPtr->tagRootPtr = nodePtr->parentPtr;
4436 }
4437 summaryPtr2 = summaryPtr;
4438 summaryPtr = summaryPtr->nextPtr;
4439 continue;
4440 }
4441 if (summaryPtr->toggleCount == summaryPtr->tagPtr->toggleCount) {
4442 /*
4443 * A node merge has collected all the toggles under one node. Push
4444 * the root down to this level.
4445 */
4446
4447 summaryPtr->tagPtr->tagRootPtr = nodePtr;
4448 }
4449 if (summaryPtr2 != NULL) {
4450 summaryPtr2->nextPtr = summaryPtr->nextPtr;
4451 ckfree((char *) summaryPtr);
4452 summaryPtr = summaryPtr2->nextPtr;
4453 } else {
4454 nodePtr->summaryPtr = summaryPtr->nextPtr;
4455 ckfree((char *) summaryPtr);
4456 summaryPtr = nodePtr->summaryPtr;
4457 }
4458 }
4459 }
4460
4461 /*
4462 *----------------------------------------------------------------------
4463 *
4464 * TkBTreeNumLines --
4465 *
4466 * This function returns a count of the number of logical lines of text
4467 * present in a given B-tree.
4468 *
4469 * Results:
4470 * The return value is a count of the number of usable lines in tree
4471 * (i.e. it doesn't include the dummy line that is just used to mark the
4472 * end of the tree).
4473 *
4474 * Side effects:
4475 * None.
4476 *
4477 *----------------------------------------------------------------------
4478 */
4479
4480 int
TkBTreeNumLines(TkTextBTree tree,const TkText * textPtr)4481 TkBTreeNumLines(
4482 TkTextBTree tree, /* Information about tree. */
4483 const TkText *textPtr) /* Relative to this client of the B-tree. */
4484 {
4485 BTree *treePtr = (BTree *) tree;
4486 int count;
4487
4488 if (textPtr != NULL && textPtr->end != NULL) {
4489 count = TkBTreeLinesTo(NULL, textPtr->end);
4490 } else {
4491 count = treePtr->rootPtr->numLines - 1;
4492 }
4493 if (textPtr != NULL && textPtr->start != NULL) {
4494 count -= TkBTreeLinesTo(NULL, textPtr->start);
4495 }
4496
4497 return count;
4498 }
4499
4500 /*
4501 *----------------------------------------------------------------------
4502 *
4503 * TkBTreeNumPixels --
4504 *
4505 * This function returns a count of the number of pixels of text present
4506 * in a given widget's B-tree representation.
4507 *
4508 * Results:
4509 * The return value is a count of the number of usable pixels in tree
4510 * (since the dummy line used to mark the end of the B-tree is maintained
4511 * with zero height, as are any lines that are before or after the
4512 * '-start -end' range of the text widget in question, the number stored
4513 * at the root is the number we want).
4514 *
4515 * Side effects:
4516 * None.
4517 *
4518 *----------------------------------------------------------------------
4519 */
4520
4521 int
TkBTreeNumPixels(TkTextBTree tree,const TkText * textPtr)4522 TkBTreeNumPixels(
4523 TkTextBTree tree, /* The B-tree. */
4524 const TkText *textPtr) /* Relative to this client of the B-tree. */
4525 {
4526 BTree *treePtr = (BTree *) tree;
4527 return treePtr->rootPtr->numPixels[textPtr->pixelReference];
4528 }
4529
4530 /*
4531 *--------------------------------------------------------------
4532 *
4533 * CharSplitProc --
4534 *
4535 * This function implements splitting for character segments.
4536 *
4537 * Results:
4538 * The return value is a pointer to a chain of two segments that have the
4539 * same characters as segPtr except split among the two segments.
4540 *
4541 * Side effects:
4542 * Storage for segPtr is freed.
4543 *
4544 *--------------------------------------------------------------
4545 */
4546
4547 static TkTextSegment *
CharSplitProc(TkTextSegment * segPtr,int index)4548 CharSplitProc(
4549 TkTextSegment *segPtr, /* Pointer to segment to split. */
4550 int index) /* Position within segment at which to
4551 * split. */
4552 {
4553 TkTextSegment *newPtr1, *newPtr2;
4554
4555 newPtr1 = (TkTextSegment *) ckalloc(CSEG_SIZE(index));
4556 newPtr2 = (TkTextSegment *) ckalloc(
4557 CSEG_SIZE(segPtr->size - index));
4558 newPtr1->typePtr = &tkTextCharType;
4559 newPtr1->nextPtr = newPtr2;
4560 newPtr1->size = index;
4561 memcpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index);
4562 newPtr1->body.chars[index] = 0;
4563 newPtr2->typePtr = &tkTextCharType;
4564 newPtr2->nextPtr = segPtr->nextPtr;
4565 newPtr2->size = segPtr->size - index;
4566 memcpy(newPtr2->body.chars, segPtr->body.chars + index, newPtr2->size);
4567 newPtr2->body.chars[newPtr2->size] = 0;
4568 ckfree((char *) segPtr);
4569 return newPtr1;
4570 }
4571
4572 /*
4573 *--------------------------------------------------------------
4574 *
4575 * CharCleanupProc --
4576 *
4577 * This function merges adjacent character segments into a single
4578 * character segment, if possible.
4579 *
4580 * Results:
4581 * The return value is a pointer to the first segment in the (new) list
4582 * of segments that used to start with segPtr.
4583 *
4584 * Side effects:
4585 * Storage for the segments may be allocated and freed.
4586 *
4587 *--------------------------------------------------------------
4588 */
4589
4590 /* ARGSUSED */
4591 static TkTextSegment *
CharCleanupProc(TkTextSegment * segPtr,TkTextLine * linePtr)4592 CharCleanupProc(
4593 TkTextSegment *segPtr, /* Pointer to first of two adjacent segments
4594 * to join. */
4595 TkTextLine *linePtr) /* Line containing segments (not used). */
4596 {
4597 TkTextSegment *segPtr2, *newPtr;
4598
4599 segPtr2 = segPtr->nextPtr;
4600 if ((segPtr2 == NULL) || (segPtr2->typePtr != &tkTextCharType)) {
4601 return segPtr;
4602 }
4603 newPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(
4604 segPtr->size + segPtr2->size));
4605 newPtr->typePtr = &tkTextCharType;
4606 newPtr->nextPtr = segPtr2->nextPtr;
4607 newPtr->size = segPtr->size + segPtr2->size;
4608 memcpy(newPtr->body.chars, segPtr->body.chars, segPtr->size);
4609 memcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars, segPtr2->size);
4610 newPtr->body.chars[newPtr->size] = 0;
4611 ckfree((char *) segPtr);
4612 ckfree((char *) segPtr2);
4613 return newPtr;
4614 }
4615
4616 /*
4617 *--------------------------------------------------------------
4618 *
4619 * CharDeleteProc --
4620 *
4621 * This function is invoked to delete a character segment.
4622 *
4623 * Results:
4624 * Always returns 0 to indicate that the segment was deleted.
4625 *
4626 * Side effects:
4627 * Storage for the segment is freed.
4628 *
4629 *--------------------------------------------------------------
4630 */
4631
4632 /* ARGSUSED */
4633 static int
CharDeleteProc(TkTextSegment * segPtr,TkTextLine * linePtr,int treeGone)4634 CharDeleteProc(
4635 TkTextSegment *segPtr, /* Segment to delete. */
4636 TkTextLine *linePtr, /* Line containing segment. */
4637 int treeGone) /* Non-zero means the entire tree is being
4638 * deleted, so everything must get cleaned
4639 * up. */
4640 {
4641 ckfree((char *) segPtr);
4642 return 0;
4643 }
4644
4645 /*
4646 *--------------------------------------------------------------
4647 *
4648 * CharCheckProc --
4649 *
4650 * This function is invoked to perform consistency checks on character
4651 * segments.
4652 *
4653 * Results:
4654 * None.
4655 *
4656 * Side effects:
4657 * If the segment isn't inconsistent then the function panics.
4658 *
4659 *--------------------------------------------------------------
4660 */
4661
4662 /* ARGSUSED */
4663 static void
CharCheckProc(TkTextSegment * segPtr,TkTextLine * linePtr)4664 CharCheckProc(
4665 TkTextSegment *segPtr, /* Segment to check. */
4666 TkTextLine *linePtr) /* Line containing segment. */
4667 {
4668 /*
4669 * Make sure that the segment contains the number of characters indicated
4670 * by its header, and that the last segment in a line ends in a newline.
4671 * Also make sure that there aren't ever two character segments adjacent
4672 * to each other: they should be merged together.
4673 */
4674
4675 if (segPtr->size <= 0) {
4676 Tcl_Panic("CharCheckProc: segment has size <= 0");
4677 }
4678 if (strlen(segPtr->body.chars) != (size_t) segPtr->size) {
4679 Tcl_Panic("CharCheckProc: segment has wrong size");
4680 }
4681 if (segPtr->nextPtr == NULL) {
4682 if (segPtr->body.chars[segPtr->size-1] != '\n') {
4683 Tcl_Panic("CharCheckProc: line doesn't end with newline");
4684 }
4685 } else if (segPtr->nextPtr->typePtr == &tkTextCharType) {
4686 Tcl_Panic("CharCheckProc: adjacent character segments weren't merged");
4687 }
4688 }
4689
4690 /*
4691 *--------------------------------------------------------------
4692 *
4693 * ToggleDeleteProc --
4694 *
4695 * This function is invoked to delete toggle segments.
4696 *
4697 * Results:
4698 * Returns 1 to indicate that the segment may not be deleted, unless the
4699 * entire B-tree is going away.
4700 *
4701 * Side effects:
4702 * If the tree is going away then the toggle's memory is freed; otherwise
4703 * the toggle counts in nodes above the segment get updated.
4704 *
4705 *--------------------------------------------------------------
4706 */
4707
4708 static int
ToggleDeleteProc(TkTextSegment * segPtr,TkTextLine * linePtr,int treeGone)4709 ToggleDeleteProc(
4710 TkTextSegment *segPtr, /* Segment to check. */
4711 TkTextLine *linePtr, /* Line containing segment. */
4712 int treeGone) /* Non-zero means the entire tree is being
4713 * deleted, so everything must get cleaned
4714 * up. */
4715 {
4716 if (treeGone) {
4717 ckfree((char *) segPtr);
4718 return 0;
4719 }
4720
4721 /*
4722 * This toggle is in the middle of a range of characters that's being
4723 * deleted. Refuse to die. We'll be moved to the end of the deleted range
4724 * and our cleanup function will be called later. Decrement node toggle
4725 * counts here, and set a flag so we'll re-increment them in the cleanup
4726 * function.
4727 */
4728
4729 if (segPtr->body.toggle.inNodeCounts) {
4730 ChangeNodeToggleCount(linePtr->parentPtr,
4731 segPtr->body.toggle.tagPtr, -1);
4732 segPtr->body.toggle.inNodeCounts = 0;
4733 }
4734 return 1;
4735 }
4736
4737 /*
4738 *--------------------------------------------------------------
4739 *
4740 * ToggleCleanupProc --
4741 *
4742 * This function is called when a toggle is part of a line that's been
4743 * modified in some way. It's invoked after the modifications are
4744 * complete.
4745 *
4746 * Results:
4747 * The return value is the head segment in a new list that is to replace
4748 * the tail of the line that used to start at segPtr. This allows the
4749 * function to delete or modify segPtr.
4750 *
4751 * Side effects:
4752 * Toggle counts in the nodes above the new line will be updated if
4753 * they're not already. Toggles may be collapsed if there are duplicate
4754 * toggles at the same position.
4755 *
4756 *--------------------------------------------------------------
4757 */
4758
4759 static TkTextSegment *
ToggleCleanupProc(TkTextSegment * segPtr,TkTextLine * linePtr)4760 ToggleCleanupProc(
4761 TkTextSegment *segPtr, /* Segment to check. */
4762 TkTextLine *linePtr) /* Line that now contains segment. */
4763 {
4764 TkTextSegment *segPtr2, *prevPtr;
4765 int counts;
4766
4767 /*
4768 * If this is a toggle-off segment, look ahead through the next segments
4769 * to see if there's a toggle-on segment for the same tag before any
4770 * segments with non-zero size. If so then the two toggles cancel each
4771 * other; remove them both.
4772 */
4773
4774 if (segPtr->typePtr == &tkTextToggleOffType) {
4775 for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr;
4776 (segPtr2 != NULL) && (segPtr2->size == 0);
4777 prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) {
4778 if (segPtr2->typePtr != &tkTextToggleOnType) {
4779 continue;
4780 }
4781 if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) {
4782 continue;
4783 }
4784 counts = segPtr->body.toggle.inNodeCounts
4785 + segPtr2->body.toggle.inNodeCounts;
4786 if (counts != 0) {
4787 ChangeNodeToggleCount(linePtr->parentPtr,
4788 segPtr->body.toggle.tagPtr, -counts);
4789 }
4790 prevPtr->nextPtr = segPtr2->nextPtr;
4791 ckfree((char *) segPtr2);
4792 segPtr2 = segPtr->nextPtr;
4793 ckfree((char *) segPtr);
4794 return segPtr2;
4795 }
4796 }
4797
4798 if (!segPtr->body.toggle.inNodeCounts) {
4799 ChangeNodeToggleCount(linePtr->parentPtr,
4800 segPtr->body.toggle.tagPtr, 1);
4801 segPtr->body.toggle.inNodeCounts = 1;
4802 }
4803 return segPtr;
4804 }
4805
4806 /*
4807 *--------------------------------------------------------------
4808 *
4809 * ToggleLineChangeProc --
4810 *
4811 * This function is invoked when a toggle segment is about to move from
4812 * one line to another.
4813 *
4814 * Results:
4815 * None.
4816 *
4817 * Side effects:
4818 * Toggle counts are decremented in the nodes above the line.
4819 *
4820 *--------------------------------------------------------------
4821 */
4822
4823 static void
ToggleLineChangeProc(TkTextSegment * segPtr,TkTextLine * linePtr)4824 ToggleLineChangeProc(
4825 TkTextSegment *segPtr, /* Segment to check. */
4826 TkTextLine *linePtr) /* Line that used to contain segment. */
4827 {
4828 if (segPtr->body.toggle.inNodeCounts) {
4829 ChangeNodeToggleCount(linePtr->parentPtr,
4830 segPtr->body.toggle.tagPtr, -1);
4831 segPtr->body.toggle.inNodeCounts = 0;
4832 }
4833 }
4834
4835 /*
4836 *--------------------------------------------------------------
4837 *
4838 * ToggleCheckProc --
4839 *
4840 * This function is invoked to perform consistency checks on toggle
4841 * segments.
4842 *
4843 * Results:
4844 * None.
4845 *
4846 * Side effects:
4847 * If a consistency problem is found the function panics.
4848 *
4849 *--------------------------------------------------------------
4850 */
4851
4852 static void
ToggleCheckProc(TkTextSegment * segPtr,TkTextLine * linePtr)4853 ToggleCheckProc(
4854 TkTextSegment *segPtr, /* Segment to check. */
4855 TkTextLine *linePtr) /* Line containing segment. */
4856 {
4857 register Summary *summaryPtr;
4858 int needSummary;
4859
4860 if (segPtr->size != 0) {
4861 Tcl_Panic("ToggleCheckProc: segment had non-zero size");
4862 }
4863 if (!segPtr->body.toggle.inNodeCounts) {
4864 Tcl_Panic("ToggleCheckProc: toggle counts not updated in nodes");
4865 }
4866 needSummary = (segPtr->body.toggle.tagPtr->tagRootPtr!=linePtr->parentPtr);
4867 for (summaryPtr = linePtr->parentPtr->summaryPtr; ;
4868 summaryPtr = summaryPtr->nextPtr) {
4869 if (summaryPtr == NULL) {
4870 if (needSummary) {
4871 Tcl_Panic("ToggleCheckProc: tag not present in node");
4872 } else {
4873 break;
4874 }
4875 }
4876 if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) {
4877 if (!needSummary) {
4878 Tcl_Panic("ToggleCheckProc: tag present in root node summary");
4879 }
4880 break;
4881 }
4882 }
4883 }
4884
4885 /*
4886 * Local Variables:
4887 * mode: c
4888 * c-basic-offset: 4
4889 * fill-column: 78
4890 * End:
4891 */
4892