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