/*
* tkTextBTree.c --
*
* This file contains code that manages the B-tree representation
* of text for Tk's text widget and implements character and
* toggle segment types.
*
* Copyright (c) 1992-1994 The Regents of the University of California.
* Copyright (c) 1994-1995 Sun Microsystems, Inc.
*
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
* SCCS: @(#) tkTextBTree.c 1.35 96/03/21 15:51:39
*/
#include "tkInt.h"
#include "tkText.h"
/*
* The data structure below keeps summary information about one tag as part
* of the tag information in a node.
*/
typedef struct Summary {
* out of this tag that occur in
* the subtree rooted at this node. */
* node, or NULL if at end of list. */
} Summary;
/*
* The data structure below defines a node in the B-tree.
*/
typedef struct Node {
* this is the root. */
* same parent node, or NULL for end
* of list. */
* about tags in this subtree (NULL if
* no tag info in the subtree). */
* 0 refers to the bottom of the tree
* (children are lines, not nodes). */
union { /* First in linked list of children. */
} children;
* the subtree rooted here. */
} Node;
/*
* Upper and lower bounds on how many children a node may have:
* rebalance when either of these limits is exceeded. MAX_CHILDREN
* should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
*/
/*
* The data structure below defines an entire B-tree.
*/
typedef struct BTree {
* checking code */
} BTree;
/*
* The structure below is used to pass information between
* TkBTreeGetTags and IncCount:
*/
typedef struct TagInfo {
* is currently information in
* tags and counts. */
* tags and counts. */
* Malloc-ed. */
* entry in tags. Malloc-ed. */
} TagInfo;
/*
* Variable that indicates whether to enable consistency checks for
* debugging.
*/
int tkBTreeDebug = 0;
/*
* Macros that determine how much space to allocate for new segments:
*/
+ 1 + (chars)))
+ sizeof(TkTextToggle)))
/*
* Forward declarations for procedures defined in this file:
*/
TkTextLine *linePtr));
TkTextLine *linePtr));
int index));
TagInfo *tagInfoPtr));
TkTextLine *linePtr));
TkTextLine *linePtr));
TkTextLine *linePtr));
/*
* Type record for character segments:
*/
"character", /* name */
0, /* leftGravity */
CharSplitProc, /* splitProc */
CharDeleteProc, /* deleteProc */
CharCleanupProc, /* cleanupProc */
TkTextCharLayoutProc, /* layoutProc */
CharCheckProc /* checkProc */
};
/*
* Type record for segments marking the beginning of a tagged
* range:
*/
"toggleOn", /* name */
0, /* leftGravity */
ToggleDeleteProc, /* deleteProc */
ToggleCleanupProc, /* cleanupProc */
ToggleLineChangeProc, /* lineChangeProc */
ToggleCheckProc /* checkProc */
};
/*
* Type record for segments marking the end of a tagged
* range:
*/
"toggleOff", /* name */
1, /* leftGravity */
ToggleDeleteProc, /* deleteProc */
ToggleCleanupProc, /* cleanupProc */
ToggleLineChangeProc, /* lineChangeProc */
ToggleCheckProc /* checkProc */
};
/*
*----------------------------------------------------------------------
*
* TkBTreeCreate --
*
* This procedure is called to create a new text B-tree.
*
* Results:
* The return value is a pointer to a new B-tree containing
* one line with nothing but a newline character.
*
* Side effects:
* Memory is allocated and initialized.
*
*----------------------------------------------------------------------
*/
{
/*
* The tree will initially have two empty lines. The second line
* isn't actually part of the tree's contents, but its presence
* makes several operations easier. The tree will have one node,
* which is also the root of the tree.
*/
return (TkTextBTree) treePtr;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeDestroy --
*
* Delete a B-tree, recycling all of the storage it contains.
*
* Results:
* The tree given by treePtr is deleted. TreePtr should never
* again be used.
*
* Side effects:
* Memory is freed.
*
*----------------------------------------------------------------------
*/
void
{
}
/*
*----------------------------------------------------------------------
*
* DestroyNode --
*
* This is a recursive utility procedure used during the deletion
* of a B-tree.
*
* Results:
* None.
*
* Side effects:
* All the storage for nodePtr and its descendants is freed.
*
*----------------------------------------------------------------------
*/
static void
{
}
}
} else {
}
}
}
/*
*----------------------------------------------------------------------
*
* DeleteSummaries --
*
* Free up all of the memory in a list of tag summaries associated
* with a node.
*
* Results:
* None.
*
* Side effects:
* Storage is released.
*
*----------------------------------------------------------------------
*/
static void
* summaries. */
{
while (summaryPtr != NULL) {
ckfree((char *) summaryPtr);
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeInsertChars --
*
* Insert characters at a given position in a B-tree.
*
* Results:
* None.
*
* Side effects:
* Characters are added to the B-tree at the given position.
* If the string contains newlines, new lines will be added,
* which could cause the structure of the B-tree to change.
*
*----------------------------------------------------------------------
*/
void
* When the procedure returns, this
* index is no longer valid because
* of changes to the segment
* structure. */
char *string; /* Pointer to bytes to insert (may
* contain newlines, must be null-
* terminated). */
{
* new segment (NULL means new segment
* is at beginning of line). */
* are inserted just after this one.
* NULL means insert at beginning of
* line. */
* added to this line). */
* one in current chunk. */
* lines in file. */
/*
* Chop the string up into lines and create a new segment for
* each line, plus a new line for the leftovers from the
* previous line.
*/
changeToLineCount = 0;
while (*string != 0) {
if (*eol == '\n') {
eol++;
break;
}
}
} else {
}
break;
}
/*
* The chunk ended with a newline, so create a new TkTextLine
* and move the remainder of the old line to it.
*/
}
/*
* Cleanup the starting line for the insertion, plus the ending
* line if it's different.
*/
}
/*
* Increment the line counts in all the parent nodes of the insertion
* point, then rebalance the tree if necessary.
*/
}
}
if (tkBTreeDebug) {
}
}
/*
*--------------------------------------------------------------
*
* SplitSeg --
*
* This procedure is called before adding or deleting
* segments. It does three things: (a) it finds the segment
* containing indexPtr; (b) if there are several such
* segments (because some segments have zero length) then
* it picks the first segment that does not have left
* gravity; (c) if the index refers to the middle of
* a segment then it splits the segment so that the
* index now refers to the beginning of a segment.
*
* Results:
* The return value is a pointer to the segment just
* before the segment corresponding to indexPtr (as
* described above). If the segment corresponding to
* indexPtr is the first in its line then the return
* value is NULL.
*
* Side effects:
* The segment referred to by indexPtr is split unless
* indexPtr refers to its first character.
*
*--------------------------------------------------------------
*/
static TkTextSegment *
* at which to split a segment. */
{
int count;
if (count == 0) {
return prevPtr;
}
} else {
}
return segPtr;
return prevPtr;
}
}
panic("SplitSeg reached end of line!");
return NULL;
}
/*
*--------------------------------------------------------------
*
* CleanupLine --
*
* This procedure is called after modifications have been
* made to a line. It scans over all of the segments in
* the line, giving each a chance to clean itself up, e.g.
* by merging with the following segments, updating internal
* information, etc.
*
* Results:
* None.
*
* Side effects:
* Depends on what the segment-specific cleanup procedures do.
*
*--------------------------------------------------------------
*/
static void
{
int anyChanges;
/*
* Make a pass over all of the segments in the line, giving each
* a chance to clean itself up. This could potentially change
* the structure of the line, e.g. by merging two segments
* together or having two segments cancel themselves; if so,
* then repeat the whole process again, since the first structure
* change might make other structure changes possible. Repeat
* until eventually there are no changes.
*/
while (1) {
anyChanges = 0;
if (segPtr != *prevPtrPtr) {
anyChanges = 1;
}
}
}
if (!anyChanges) {
break;
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeDeleteChars --
*
* Delete a range of characters from a B-tree. The caller
* must make sure that the final newline of the B-tree is
* never deleted.
*
* Results:
* None.
*
* Side effects:
* Information is deleted from the B-tree. This can cause the
* internal structure of the B-tree to change. Note: because
* of changes to the B-tree structure, the indices pointed
* to by index1Ptr and index2Ptr should not be used after this
* procedure returns.
*
*----------------------------------------------------------------------
*/
void
* to be deleted. */
* last one that is to be deleted. */
{
* of the deletion range. */
* of the deletion range. */
/*
* Tricky point: split at index2Ptr first; otherwise the split
*/
} else {
}
} else {
}
/*
* Delete all of the segments between prevPtr and lastPtr.
*/
/*
* We just ran off the end of a line. First find the
* next line, then go back to the old line and delete it
* (unless it's the starting line for the range).
*/
} else {
}
}
ckfree((char *) curLinePtr);
}
/*
* If the node is empty then delete it and its parents,
* recursively upwards until a non-empty node is found.
*/
while (curNodePtr->numChildren == 0) {
} else {
}
}
parentPtr->numChildren--;
ckfree((char *) curNodePtr);
}
continue;
}
/*
* This segment refuses to die. Move it to prevPtr and
* advance prevPtr if the segment has left gravity.
*/
} else {
}
}
}
}
/*
* If the beginning and end of the deletion range are in different
* lines, join the two lines together and discard the ending line.
*/
}
}
}
} else {
}
}
}
/*
* Cleanup the segments in the new line.
*/
/*
* Lastly, rebalance the first node of the range.
*/
if (tkBTreeDebug) {
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeFindLine --
*
* Find a particular line in a B-tree based on its line number.
*
* Results:
* The return value is a pointer to the line structure for the
* line whose index is "line", or NULL if no such line exists.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
int line; /* Index of desired line. */
{
int linesLeft;
return NULL;
}
/*
* Work down through levels of the tree until a node is found at
* level 0.
*/
panic("TkBTreeFindLine ran out of nodes");
}
}
}
/*
* Work through the lines attached to the level-0 node.
*/
panic("TkBTreeFindLine ran out of lines");
}
linesLeft -= 1;
}
return linePtr;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeNextLine --
*
* Given an existing line in a B-tree, this procedure locates the
* next line in the B-tree. This procedure is used for scanning
* through the B-tree.
*
* Results:
* The return value is a pointer to the line that immediately
* follows linePtr, or NULL if there is no such line.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
* B-tree. */
{
}
/*
* This was the last line associated with the particular parent node.
* Search up the tree for the next node, then search down from that
* node to find the first line.
*/
break;
}
return (TkTextLine *) NULL;
}
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreePreviousLine --
*
* Given an existing line in a B-tree, this procedure locates the
* previous line in the B-tree. This procedure is used for scanning
* through the B-tree in the reverse direction.
*
* Results:
* The return value is a pointer to the line that immediately
* preceeds linePtr, or NULL if there is no such line.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
* B-tree. */
{
/*
* Find the line under this node just before the starting line.
*/
return prevPtr;
}
panic("TkBTreePreviousLine ran out of lines");
}
}
/*
* This was the first line associated with the particular parent node.
* Search up the tree for the previous node, then search down from that
* node to find its last line.
*/
return (TkTextLine *) NULL;
}
break;
}
}
}
break;
}
}
return prevPtr;
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeLineIndex --
*
* Given a pointer to a line in a B-tree, return the numerical
* index of that line.
*
* Results:
* The result is the index of linePtr within the tree, where 0
* corresponds to the first line in the tree.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
int
* B-tree. */
{
int index;
/*
* First count how many lines precede this one in its level-0
* node.
*/
index = 0;
panic("TkBTreeLineIndex couldn't find line");
}
index += 1;
}
/*
* Now work up through the levels of the tree one at a time,
* counting how many lines are in nodes preceding the current
* node.
*/
panic("TkBTreeLineIndex couldn't find node");
}
}
}
return index;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeLinkSegment --
*
* This procedure adds a new segment to a B-tree at a given
* location.
*
* Results:
* None.
*
* Side effects:
* SegPtr will be linked into its tree.
*
*----------------------------------------------------------------------
*/
/* ARGSUSED */
void
* B-tree. Should be completely initialized
* by caller except for nextPtr field. */
* in just before the segment indicated
* here. */
{
} else {
}
if (tkBTreeDebug) {
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeUnlinkSegment --
*
* This procedure unlinks a segment from its line in a B-tree.
*
* Results:
* None.
*
* Side effects:
* SegPtr will be unlinked from linePtr. The segment itself
* isn't modified by this procedure.
*
*----------------------------------------------------------------------
*/
/* ARGSUSED */
void
* segment. */
{
} else {
/* Empty loop body. */
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeTag --
*
* Turn a given tag on or off for a given range of characters in
* a B-tree of text.
*
* Results:
* None.
*
* Side effects:
* The given tag is added to the given range of characters
* in the tree or removed from all those characters, depending
* on the "add" argument. The structure of the btree is modified
* enough that index1Ptr and index2Ptr are no longer valid after
* this procedure returns, and the indexes may be modified by
* this procedure.
*
*----------------------------------------------------------------------
*/
void
* range. */
* last one in range. */
int add; /* One means add tag to the given
* range of characters; zero means
* remove the tag from the range. */
{
int oldState;
int changed;
/*
* See whether the tag is present at the start of the range. If
* the state doesn't already match what we want then add a toggle
* there.
*/
} else {
}
}
/*
* Scan the range of characters and delete any internal tag
* transitions. Keep track of what the old state was at the end
* of the range, and add a toggle there if it's needed.
*/
while (TkBTreeNextTag(&search)) {
oldState ^= 1;
} else {
}
}
changed = 1;
} else {
changed = 0;
}
/*
* The code below is a bit tricky. After deleting a toggle
* we eventually have to call CleanupLine, in order to allow
* character segments to be merged together. To do this, we
* remember in cleanupLinePtr a line that needs to be
* cleaned up, but we don't clean it up until we've moved
* on to a different line. That way the cleanup process
* won't goof up segPtr.
*/
}
/*
* Quick hack. ChangeNodeToggleCount may move the tag's root
* location around and leave the search in the void. This resets
* the search.
*/
if (changed) {
}
}
} else {
}
}
/*
* Cleanup cleanupLinePtr and the last line of the range, if
* these are different.
*/
}
if (tkBTreeDebug) {
}
}
/*
*----------------------------------------------------------------------
*
* ChangeNodeToggleCount --
*
* This procedure increments or decrements the toggle count for
* a particular tag in a particular node and all its ancestors
* up to the per-tag root node.
*
* Results:
* None.
*
* Side effects:
* The toggle count for tag is adjusted up or down by "delta" in
* nodePtr. This routine maintains the tagRootPtr that identifies
* the root node for the tag, moving it up or down the tree as needed.
*
*----------------------------------------------------------------------
*/
static void
* must be changed. */
int delta; /* Amount to add to current toggle
* count for tag (may be negative). */
{
return;
}
/*
* Note the level of the existing root for the tag so we can detect
* if it needs to be moved because of the toggle count change.
*/
/*
* Iterate over the node and its ancestors up to the tag root, adjusting
* summary counts at each node and moving the tag's root upwards if
* necessary.
*/
/*
* See if there's already an entry for this tag for this node. If so,
* perhaps all we have to do is adjust its count.
*/
summaryPtr != NULL;
break;
}
}
if (summaryPtr != NULL) {
if (summaryPtr->toggleCount > 0 &&
continue;
}
if (summaryPtr->toggleCount != 0) {
/*
* Should never find a node with max toggle count at this
* point (there shouldn't have been a summary entry in the
* first place).
*/
panic("ChangeNodeToggleCount: bad toggle count (%d) max (%d)",
}
/*
* Zero toggle count; must remove this tag from the list.
*/
} else {
}
ckfree((char *) summaryPtr);
} else {
/*
* This tag isn't currently in the summary information list.
*/
/*
* The old tag root is at the same level in the tree as this
* node, but it isn't at this node. Move the tag root up
* a level, in the hopes that it will now cover this node
* as well as the old root (if not, we'll move it up again
* the next time through the loop). To push it up one level
* we copy the original toggle count into the summary
* information at the old root and change the root to its
* parent node.
*/
}
}
}
/*
* If we've decremented the toggle count, then it may be necessary
* to push the tag root down one or more levels.
*/
if (delta >= 0) {
return;
}
if (tagPtr->toggleCount == 0) {
return;
}
/*
* See if a single child node accounts for all of the tag's
* toggles. If so, push the root down one level.
*/
summaryPtr != NULL;
break;
}
}
if (summaryPtr == NULL) {
continue;
}
/*
* No node has all toggles, so the root is still valid.
*/
return;
}
/*
* This node has all the toggles, so push down the root.
*/
} else {
}
ckfree((char *) summaryPtr);
break;
}
}
}
/*
*----------------------------------------------------------------------
*
* FindTagStart --
*
* Find the start of the first range of a tag.
*
* Results:
* The return value is a pointer to the first tag toggle segment
* for the tag. This can be either a tagon or tagoff segments because
* of the way TkBTreeAdd removes a tag.
* Sets *indexPtr to be the index of the tag toggle.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static TkTextSegment *
{
int offset = 0;
return NULL;
}
/*
* Search from the root of the subtree that contains the tag down
* to the level 0 node.
*/
goto gotNodeWithTag;
}
}
}
continue;
}
/*
* Work through the lines attached to the level-0 node.
*/
/*
* It is possible that this is a tagoff tag, but that
* gets cleaned up later.
*/
return segPtr;
}
}
}
return NULL;
}
/*
*----------------------------------------------------------------------
*
* FindTagEnd --
*
* Find the end of the last range of a tag.
*
* Results:
* The return value is a pointer to the last tag toggle segment
* for the tag. This can be either a tagon or tagoff segments because
* of the way TkBTreeAdd removes a tag.
* Sets *indexPtr to be the index of the tag toggle.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static TkTextSegment *
{
return NULL;
}
/*
* Search from the root of the subtree that contains the tag down
* to the level 0 node.
*/
break;
}
}
}
}
/*
* Work through the lines attached to the level-0 node.
*/
last2SegPtr = NULL;
lastoffset2 = 0;
lastoffset = 0;
lastSegPtr = segPtr;
lastoffset = offset;
}
}
if (lastSegPtr != NULL) {
}
}
return last2SegPtr;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeStartSearch --
*
* This procedure sets up a search for tag transitions involving
* a given tag (or all tags) in a given range of the text.
*
* Results:
* None.
*
* Side effects:
* The information at *searchPtr is set up so that subsequent calls
* to TkBTreeNextTag or TkBTreePrevTag will return information about the
* locations of tag transitions. Note that TkBTreeNextTag or
* TkBTreePrevTag must be called to get the first transition.
* Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not
* guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be
* greater than that if *index1Ptr is less than the first tag transition.
*
*----------------------------------------------------------------------
*/
void
* at this position will not be
* returned. */
* at this position *will* be
* returned. */
* search for any tag. */
* search's progress. */
{
int offset;
/*
* Find the segment that contains the first toggle for the tag. This
* may become the starting point in the search.
*/
/*
* Even though there are no toggles, the display code still
* uses the search curIndex, so initialize that anyway.
*/
return;
}
/*
* Adjust start of search up to the first range of the tag
*/
} else {
}
/*
* Starting and stopping segments are in the same line; mark the
* search as over immediately if the second segment is before the
* first. A search does not return a toggle at the very start of
* the range, unless the range is artificially moved up to index0.
*/
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeStartSearchBack --
*
* This procedure sets up a search backwards for tag transitions involving
* a given tag (or all tags) in a given range of the text. In the
* normal case the first index (*index1Ptr) is beyond the second
* index (*index2Ptr).
*
*
* Results:
* None.
*
* Side effects:
* The information at *searchPtr is set up so that subsequent calls
* to TkBTreePrevTag will return information about the
* locations of tag transitions. Note that TkBTreePrevTag must be called
* to get the first transition.
* Note: unlike TkBTreeNextTag and TkBTreePrevTag, this routine does not
* guarantee that searchPtr->curIndex is equal to *index1Ptr. It may be
* less than that if *index1Ptr is greater than the last tag transition.
*
*----------------------------------------------------------------------
*/
void
* at this position will not be
* returned. */
* at this position *will* be
* returned. */
* search for any tag. */
* search's progress. */
{
int offset;
/*
* Find the segment that contains the last toggle for the tag. This
* may become the starting point in the search.
*/
/*
* Even though there are no toggles, the display code still
* uses the search curIndex, so initialize that anyway.
*/
return;
}
/*
* Adjust the start of the search so it doesn't find any tag toggles
* that are right at the index specified by the user.
*/
} else {
}
/*
* Adjust the end of the search so it does find toggles that are right
* at the second index specified by the user.
*/
} else {
}
/*
* Starting and stopping segments are in the same line; mark the
* search as over immediately if the second segment is after the
* first.
*/
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeNextTag --
*
* Once a tag search has begun, successive calls to this procedure
* return successive tag toggles. Note: it is NOT SAFE to call this
* procedure if characters have been inserted into or deleted from
* the B-tree since the call to TkBTreeStartSearch.
*
* Results:
* The return value is 1 if another toggle was found that met the
* criteria specified in the call to TkBTreeStartSearch; in this
* case searchPtr->curIndex gives the toggle's position and
* searchPtr->curTagPtr points to its segment. 0 is returned if
* no more matching tag transitions were found; in this case
* searchPtr->curIndex is the same as searchPtr->stopIndex.
*
* Side effects:
* Information in *searchPtr is modified to update the state of the
* search and indicate where the next tag toggle is located.
*
*----------------------------------------------------------------------
*/
int
* progress; must have been set up by
* call to TkBTreeStartSearch. */
{
goto searchOver;
}
/*
* The outermost loop iterates over lines that may potentially contain
* a relevant tag transition, starting from the current segment in
* the current line.
*/
while (1) {
/*
* Check for more tags on the current line.
*/
goto searchOver;
}
return 1;
}
}
/*
* See if there are more lines associated with the current parent
* node. If so, go back to the top of the loop to search the next
* one.
*/
goto searchOver;
}
continue;
}
goto searchOver;
}
/*
* Search across and up through the B-tree's node hierarchy looking
* for the next node that has a relevant tag transition somewhere in
* its subtree. Be sure to update linesLeft as we skip over large
* chunks of lines.
*/
while (1) {
goto searchOver;
}
}
goto gotNodeWithTag;
}
}
}
/*
* At this point we've found a subtree that has a relevant tag
* transition. Now search down (and across) through that subtree
* to find the first level-0 node that has a relevant tag transition.
*/
goto nextChild;
}
}
panic("TkBTreeNextTag found incorrect tag summary info.");
}
}
continue;
}
/*
* Now we're down to a level-0 node that contains a line that contains
* a relevant tag transition. Set up line information and go back to
* the beginning of the loop to search through lines.
*/
goto searchOver;
}
continue;
}
return 0;
}
/*
*----------------------------------------------------------------------
*
* TkBTreePrevTag --
*
* Once a tag search has begun, successive calls to this procedure
* return successive tag toggles in the reverse direction.
* Note: it is NOT SAFE to call this
* procedure if characters have been inserted into or deleted from
* the B-tree since the call to TkBTreeStartSearch.
*
* Results:
* The return value is 1 if another toggle was found that met the
* criteria specified in the call to TkBTreeStartSearch; in this
* case searchPtr->curIndex gives the toggle's position and
* searchPtr->curTagPtr points to its segment. 0 is returned if
* no more matching tag transitions were found; in this case
* searchPtr->curIndex is the same as searchPtr->stopIndex.
*
* Side effects:
* Information in *searchPtr is modified to update the state of the
* search and indicate where the next tag toggle is located.
*
*----------------------------------------------------------------------
*/
int
* progress; must have been set up by
* call to TkBTreeStartSearch. */
{
int charIndex;
int linesSkipped;
goto searchOver;
}
/*
* The outermost loop iterates over lines that may potentially contain
* a relevant tag transition, starting from the current segment in
* the current line. "nextPtr" is maintained as the last segment in
* a line that we can look at.
*/
while (1) {
/*
* Check for the last toggle before the current segment on this line.
*/
charIndex = 0;
/*
* Search back to the very beginning, so pastLast is irrelevent.
*/
pastLast = 1;
} else {
pastLast = 0;
}
}
pastLast = 1;
}
}
/*
* We found a segment that is before the stopping index.
* Note that it is OK if prevPtr == lastPtr.
*/
goto searchOver;
}
return 1;
}
goto searchOver;
}
/*
* See if there are more lines associated with the current parent
* node. If so, go back to the top of the loop to search the previous
* one.
*/
/* empty loop body */ ;
}
if (prevLinePtr != NULL) {
continue;
}
goto searchOver;
}
/*
* Search across and up through the B-tree's node hierarchy looking
* for the previous node that has a relevant tag transition somewhere in
* back pointers. We'll scan all the nodes under a parent up to
* the current node, searching all of them for tag state. The last
* one we find, if any, is recorded in prevNodePtr, and any nodes
* past prevNodePtr that don't have tag state increment linesSkipped.
*/
while (1) {
linesSkipped = 0;
goto keepLooking;
}
}
continue;
}
if (prevNodePtr != NULL) {
goto gotNodeWithTag;
}
goto searchOver;
}
}
/*
* At this point we've found a subtree that has a relevant tag
* transition. Now search down (and across) through that subtree
* to find the last level-0 node that has a relevant tag transition.
*/
linesSkipped = 0;
goto keepLooking2;
}
}
continue;
}
if (prevNodePtr == NULL) {
panic("TkBTreePrevTag found incorrect tag summary info.");
}
}
/*
* Now we're down to a level-0 node that contains a line that contains
* a relevant tag transition. Set up line information and go back to
* the beginning of the loop to search through lines. We start with
* the last line below the node.
*/
/* empty loop body */ ;
}
goto searchOver;
}
continue;
}
return 0;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeCharTagged --
*
* Determine whether a particular character has a particular tag.
*
* Results:
* The return value is 1 if the given tag is in effect at the
* character given by linePtr and ch, and 0 otherwise.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
int
* which to check for a tag. */
{
/*
* Check for toggles for the tag in indexPtr's line but before
* indexPtr. If there is one, its type indicates whether or
* not the character is tagged.
*/
toggleSegPtr = NULL;
}
}
if (toggleSegPtr != NULL) {
}
/*
* No toggle in this line. Look for toggles for the tag in lines
* that are predecessors of indexPtr->linePtr but under the same
* level-0 node.
*/
toggles = 0;
}
}
}
if (toggleSegPtr != NULL) {
}
/*
* No toggle in this node. Scan upwards through the ancestors of
* this node, counting the number of toggles of the given tag in
* siblings that precede that node.
*/
toggles = 0;
}
}
}
break;
}
}
/*
* An odd number of toggles means that the tag is present at the
* given point.
*/
return toggles & 1;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeGetTags --
*
* Return information about all of the tags that are associated
* with a particular character in a B-tree of text.
*
* Results:
* The return value is a malloc-ed array containing pointers to
* information for each of the tags that is associated with
* the character at the position given by linePtr and ch. The
* word at *numTagsPtr is filled in with the number of pointers
* in the array. It is up to the caller to free the array by
* passing it to free. If there are no tags at the given character
* then a NULL pointer is returned and *numTagsPtr will be set to 0.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
/* ARGSUSED */
TkTextTag **
* the B-tree. */
int *numTagsPtr; /* Store number of tags found at this
* location. */
{
NUM_TAG_INFOS*sizeof(TkTextTag *));
NUM_TAG_INFOS*sizeof(int));
/*
* Record tag toggles within the line of indexPtr but preceding
* indexPtr.
*/
}
}
/*
* Record toggles for tags in lines that are predecessors of
* indexPtr->linePtr but under the same level-0 node.
*/
}
}
}
/*
* For each node in the ancestry of this line, record tag toggles
* for all siblings that precede that node.
*/
&tagInfo);
}
}
}
}
/*
* Go through the tag information and squash out all of the tags
* that have even toggle counts (these tags exist before the point
* of interest, but not at the desired character itself).
*/
dst++;
}
}
*numTagsPtr = dst;
if (dst == 0) {
return NULL;
}
}
/*
*----------------------------------------------------------------------
*
* IncCount --
*
* This is a utility procedure used by TkBTreeGetTags. It
* increments the count for a particular tag, adding a new
* entry for that tag if there wasn't one previously.
*
* Results:
* None.
*
* Side effects:
* The information at *tagInfoPtr may be modified, and the arrays
* may be reallocated to make them larger.
*
*----------------------------------------------------------------------
*/
static void
int inc; /* Amount by which to increment tag count. */
* increment count here. */
{
int count;
return;
}
}
/*
* There isn't currently an entry for this tag, so we have to
* make a new one. If the arrays are full, then enlarge the
* arrays first.
*/
tagInfoPtr->arraySize * sizeof(int));
}
tagInfoPtr->numTags++;
}
/*
*----------------------------------------------------------------------
*
* TkBTreeCheck --
*
* This procedure runs a set of consistency checks over a B-tree
* and panics if any inconsistencies are found.
*
* Results:
* None.
*
* Side effects:
* If a structural defect is found, the procedure panics with an
* error message.
*
*----------------------------------------------------------------------
*/
void
{
int count;
/*
* Make sure that the tag toggle counts and the tag root pointers are OK.
*/
if (tagPtr->toggleCount != 0) {
panic("TkBTreeCheck found \"%s\" with toggles (%d) but no root",
}
continue; /* no ranges for the tag */
} else if (tagPtr->toggleCount == 0) {
panic("TkBTreeCheck found root for \"%s\" with no toggles",
panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
}
panic("TkBTreeCheck found root node with summary info");
}
}
count = 0;
}
}
}
} else {
count++;
}
}
}
}
panic("TkBTreeCheck toggleCount (%d) wrong for \"%s\" should be (%d)",
}
}
/*
* Call a recursive procedure to do the main body of checks.
*/
/*
* Make sure that there are at least two lines in the text and
* that the last line has no characters except a newline.
*/
panic("TkBTreeCheck: less than 2 lines in tree");
}
}
}
}
/*
* It's OK to toggle a tag off in the last line, but
* not to start a new range. It's also OK to have marks
* in the last line.
*/
}
panic("TkBTreeCheck: last line has bogus segment type");
}
panic("TkBTreeCheck: last line has too many segments");
}
panic("TkBTreeCheck: last line has wrong # characters: %d",
}
panic("TkBTreeCheck: last line had bad value: %s",
}
}
/*
*----------------------------------------------------------------------
*
* CheckNodeConsistency --
*
* This procedure is called as part of consistency checking for
* B-trees: it checks several aspects of a node and also runs
* checks recursively on the node's children.
*
* Results:
* None.
*
* Side effects:
* If anything suspicious is found in the tree structure, the
* procedure panics.
*
*----------------------------------------------------------------------
*/
static void
* checked. */
{
minChildren = 2;
} else {
minChildren = 1;
}
panic("CheckNodeConsistency: bad child count (%d)",
}
numChildren = 0;
numLines = 0;
panic("CheckNodeConsistency: line doesn't point to parent");
}
panic("CheckNodeConsistency: line has no segments");
}
}
panic("CheckNodeConsistency: wrong segment order for gravity");
}
panic("CheckNodeConsistency: line ended with wrong type");
}
}
numChildren++;
numLines++;
}
} else {
panic("CheckNodeConsistency: node doesn't point to parent");
}
panic("CheckNodeConsistency: level mismatch (%d %d)",
}
if (summaryPtr2 == NULL) {
break;
}
panic("CheckNodeConsistency: node tag \"%s\" not %s",
"present in parent summaries");
}
break;
}
}
}
numChildren++;
}
}
panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
}
panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
}
panic("CheckNodeConsistency: found unpruned root for \"%s\"",
}
toggleCount = 0;
continue;
}
toggleCount ++;
}
}
}
} else {
childNodePtr != NULL;
summaryPtr2 != NULL;
}
}
}
}
panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
}
panic("CheckNodeConsistency: duplicated node tag: %s",
}
}
}
}
/*
*----------------------------------------------------------------------
*
* Rebalance --
*
* This procedure is called when a node of a B-tree appears to be
* out of balance (too many children, or too few). It rebalances
* that node and all of its ancestors in the tree.
*
* Results:
* None.
*
* Side effects:
* The internal structure of treePtr may change.
*
*----------------------------------------------------------------------
*/
static void
{
/*
* Loop over the entire ancestral chain of the node, working up
* through the tree one node at a time until the root node has
* been processed.
*/
int i;
/*
* Check to see if the node has too many children. If it does,
* then split off all but the first MIN_CHILDREN into a separate
* node following the original one. Then repeat until the
* node has a decent size.
*/
while (1) {
/*
* If the node being split is the root node, then make a
* new root node above it first.
*/
}
for (i = MIN_CHILDREN-1,
/* Empty loop body. */
}
} else {
for (i = MIN_CHILDREN-1,
/* Empty loop body. */
}
}
break;
}
}
}
/*
* Too few children for this node. If this is the root then,
* it's OK for it to have less than MIN_CHILDREN children
* as long as it's got at least two. If it has only one
* (and isn't at level 0), then chop the root node out of
* the tree and use its child as the new root.
*/
}
return;
}
/*
* Not the root. Make sure that there are siblings to
* balance with.
*/
continue;
}
/*
* Find a sibling neighbor to borrow from, and arrange for
* nodePtr to be the earlier of the pair.
*/
/* Empty loop body. */
}
}
/*
* We're going to either merge the two siblings together
* into one node or redivide the children among them to
* balance their loads. As preparation, join their two
* child lists into a single list and remember the half-way
* point in the list.
*/
}
if (i == firstChildren) {
}
}
while (i <= firstChildren) {
i++;
}
} else {
if (i <= firstChildren) {
if (i == firstChildren) {
}
}
}
while (i <= firstChildren) {
i++;
}
}
/*
* If the two siblings can simply be merged together, do it.
*/
if (totalChildren <= MAX_CHILDREN) {
continue;
}
/*
* The siblings can't be merged, so just divide their
* children evenly between them.
*/
} else {
}
}
}
}
/*
*----------------------------------------------------------------------
*
* RecomputeNodeCounts --
*
* This procedure is called to recompute all the counts in a node
* (tags, child information, etc.) by scanning the information in
* its descendants. This procedure is called during rebalancing
* when a node's child structure has changed.
*
* Results:
* None.
*
* Side effects:
* The tag counts for nodePtr are modified to reflect its current
* child structure, as are its numChildren and numLines fields.
* Also, all of the childrens' parentPtr fields are made to point
* to nodePtr.
*
*----------------------------------------------------------------------
*/
static void
* must be recomputed. */
{
/*
* Zero out all the existing counts for the node, but don't delete
* the existing Summary records (most of them will probably be reused).
*/
summaryPtr->toggleCount = 0;
}
nodePtr->numChildren = 0;
/*
* Scan through the children, adding the childrens' tag counts into
* the node's tag counts and adding new Summary structures if
* necessary.
*/
nodePtr->numChildren++;
continue;
}
if (summaryPtr == NULL) {
break;
}
break;
}
}
}
}
} else {
nodePtr->numChildren++;
if (summaryPtr == NULL) {
break;
}
break;
}
}
}
}
}
/*
* Scan through the node's tag records again and delete any Summary
* records that still have a zero count, or that have all the toggles.
* The node with the children that account for all the tags toggles
* have no summary information, and they become the tagRootPtr for the tag.
*/
summaryPtr2 = NULL;
if (summaryPtr->toggleCount > 0 &&
/*
* The tag's root node split and some toggles left.
* The tag root must move up a level.
*/
}
continue;
}
/*
* A node merge has collected all the toggles under one node.
* Push the root down to this level.
*/
}
if (summaryPtr2 != NULL) {
ckfree((char *) summaryPtr);
} else {
ckfree((char *) summaryPtr);
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeNumLines --
*
* This procedure returns a count of the number of lines of
* text present in a given B-tree.
*
* Results:
* The return value is a count of the number of usable lines
* in tree (i.e. it doesn't include the dummy line that is just
* used to mark the end of the tree).
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
int
{
}
/*
*--------------------------------------------------------------
*
* CharSplitProc --
*
* This procedure implements splitting for character segments.
*
* Results:
* The return value is a pointer to a chain of two segments
* that have the same characters as segPtr except split
* among the two segments.
*
* Side effects:
* Storage for segPtr is freed.
*
*--------------------------------------------------------------
*/
static TkTextSegment *
int index; /* Position within segment at which
* to split. */
{
return newPtr1;
}
/*
*--------------------------------------------------------------
*
* CharCleanupProc --
*
* This procedure merges adjacent character segments into
* a single character segment, if possible.
*
* Results:
* The return value is a pointer to the first segment in
* the (new) list of segments that used to start with segPtr.
*
* Side effects:
* Storage for the segments may be allocated and freed.
*
*--------------------------------------------------------------
*/
/* ARGSUSED */
static TkTextSegment *
* segments to join. */
* used). */
{
return segPtr;
}
return newPtr;
}
/*
*--------------------------------------------------------------
*
* CharDeleteProc --
*
* This procedure is invoked to delete a character segment.
*
* Results:
* Always returns 0 to indicate that the segment was deleted.
*
* Side effects:
* Storage for the segment is freed.
*
*--------------------------------------------------------------
*/
/* ARGSUSED */
static int
int treeGone; /* Non-zero means the entire tree is
* being deleted, so everything must
* get cleaned up. */
{
return 0;
}
/*
*--------------------------------------------------------------
*
* CharCheckProc --
*
* This procedure is invoked to perform consistency checks
* on character segments.
*
* Results:
* None.
*
* Side effects:
* If the segment isn't inconsistent then the procedure
* panics.
*
*--------------------------------------------------------------
*/
/* ARGSUSED */
static void
{
/*
* Make sure that the segment contains the number of
* characters indicated by its header, and that the last
* segment in a line ends in a newline. Also make sure
* that there aren't ever two character segments adjacent
* to each other: they should be merged together.
*/
panic("CharCheckProc: segment has size <= 0");
}
panic("CharCheckProc: segment has wrong size");
}
panic("CharCheckProc: line doesn't end with newline");
}
} else {
panic("CharCheckProc: adjacent character segments weren't merged");
}
}
}
/*
*--------------------------------------------------------------
*
* ToggleDeleteProc --
*
* This procedure is invoked to delete toggle segments.
*
* Results:
* Returns 1 to indicate that the segment may not be deleted,
* unless the entire B-tree is going away.
*
* Side effects:
* If the tree is going away then the toggle's memory is
* freed; otherwise the toggle counts in nodes above the
* segment get updated.
*
*--------------------------------------------------------------
*/
static int
int treeGone; /* Non-zero means the entire tree is
* being deleted, so everything must
* get cleaned up. */
{
if (treeGone) {
return 0;
}
/*
* This toggle is in the middle of a range of characters that's
* being deleted. Refuse to die. We'll be moved to the end of
* the deleted range and our cleanup procedure will be called
* later. Decrement node toggle counts here, and set a flag
* so we'll re-increment them in the cleanup procedure.
*/
}
return 1;
}
/*
*--------------------------------------------------------------
*
* ToggleCleanupProc --
*
* This procedure is called when a toggle is part of a line that's
* been modified in some way. It's invoked after the
* modifications are complete.
*
* Results:
* The return value is the head segment in a new list
* that is to replace the tail of the line that used to
* start at segPtr. This allows the procedure to delete
* or modify segPtr.
*
* Side effects:
* Toggle counts in the nodes above the new line will be
* updated if they're not already. Toggles may be collapsed
* if there are duplicate toggles at the same position.
*
*--------------------------------------------------------------
*/
static TkTextSegment *
{
int counts;
/*
* If this is a toggle-off segment, look ahead through the next
* segments to see if there's a toggle-on segment for the same tag
* before any segments with non-zero size. If so then the two
* toggles cancel each other; remove them both.
*/
continue;
}
continue;
}
if (counts != 0) {
}
return segPtr2;
}
}
}
return segPtr;
}
/*
*--------------------------------------------------------------
*
* ToggleLineChangeProc --
*
* This procedure is invoked when a toggle segment is about
* to move from one line to another.
*
* Results:
* None.
*
* Side effects:
* Toggle counts are decremented in the nodes above the line.
*
*--------------------------------------------------------------
*/
static void
{
}
}
/*
*--------------------------------------------------------------
*
* ToggleCheckProc --
*
* This procedure is invoked to perform consistency checks
* on toggle segments.
*
* Results:
* None.
*
* Side effects:
* If a consistency problem is found the procedure panics.
*
*--------------------------------------------------------------
*/
static void
{
int needSummary;
panic("ToggleCheckProc: segment had non-zero size");
}
panic("ToggleCheckProc: toggle counts not updated in nodes");
}
if (summaryPtr == NULL) {
if (needSummary) {
panic("ToggleCheckProc: tag not present in node");
} else {
break;
}
}
if (!needSummary) {
panic("ToggleCheckProc: tag present in root node summary");
}
break;
}
}
}
/*
*----------------------------------------------------------------------
*
* TkBTreeCharsInLine --
*
* This procedure returns a count of the number of characters
* in a given line.
*
* Results:
* The return value is the character count for linePtr.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
int
* counted. */
{
int count;
count = 0;
}
return count;
}