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