tktextbtree.c

linux系统下的音频通信

	 * The chunk ended with a newline, so create a new TkTextLine
	 * and move the remainder of the old line to it.
	 */

	newLinePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
	newLinePtr->parentPtr = linePtr->parentPtr;
	newLinePtr->nextPtr = linePtr->nextPtr;
	linePtr->nextPtr = newLinePtr;
	newLinePtr->segPtr = segPtr->nextPtr;
	segPtr->nextPtr = NULL;
	linePtr = newLinePtr;
	curPtr = NULL;
	changeToLineCount++;

	string = eol;
    }

    /*
     * Cleanup the starting line for the insertion, plus the ending
     * line if it's different.
     */

    CleanupLine(indexPtr->linePtr);
    if (linePtr != indexPtr->linePtr) {
	CleanupLine(linePtr);
    }

    /*
     * Increment the line counts in all the parent nodes of the insertion
     * point, then rebalance the tree if necessary.
     */

    for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
	    nodePtr = nodePtr->parentPtr) {
	nodePtr->numLines += changeToLineCount;
    }
    nodePtr = linePtr->parentPtr;
    nodePtr->numChildren += changeToLineCount;
    if (nodePtr->numChildren > MAX_CHILDREN) {
	Rebalance((BTree *) indexPtr->tree, nodePtr);
    }

    if (tkBTreeDebug) {
	TkBTreeCheck(indexPtr->tree);
    }
}

/*
 *--------------------------------------------------------------
 *
 * 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 *
SplitSeg(indexPtr)
    TkTextIndex *indexPtr;		/* Index identifying position
					 * at which to split a segment. */
{
    TkTextSegment *prevPtr, *segPtr;
    int count;

    for (count = indexPtr->charIndex, prevPtr = NULL,
	    segPtr = indexPtr->linePtr->segPtr; segPtr != NULL;
	    count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) {
	if (segPtr->size > count) {
	    if (count == 0) {
		return prevPtr;
	    }
	    segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
	    if (prevPtr == NULL) {
		indexPtr->linePtr->segPtr = segPtr;
	    } else {
		prevPtr->nextPtr = segPtr;
	    }
	    return segPtr;
	} else if ((segPtr->size == 0) && (count == 0)
		&& !segPtr->typePtr->leftGravity) {
	    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
CleanupLine(linePtr)
    TkTextLine *linePtr;		/* Line to be cleaned up. */
{
    TkTextSegment *segPtr, **prevPtrPtr;
    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;
	for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
		segPtr != NULL;
		prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
	    if (segPtr->typePtr->cleanupProc != NULL) {
		*prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
		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
TkBTreeDeleteChars(index1Ptr, index2Ptr)
    register TkTextIndex *index1Ptr;	/* Indicates first character that is
					 * to be deleted. */
    register TkTextIndex *index2Ptr;	/* Indicates character just after the
					 * last one that is to be deleted. */
{
    TkTextSegment *prevPtr;		/* The segment just before the start
					 * of the deletion range. */
    TkTextSegment *lastPtr;		/* The segment just after the end
					 * of the deletion range. */
    TkTextSegment *segPtr, *nextPtr;
    TkTextLine *curLinePtr;
    Node *curNodePtr, *nodePtr;

    /*
     * Tricky point:  split at index2Ptr first;  otherwise the split
     * at index2Ptr may invalidate segPtr and/or prevPtr.
     */

    lastPtr = SplitSeg(index2Ptr);
    if (lastPtr != NULL) {
	lastPtr = lastPtr->nextPtr;
    }  else {
	lastPtr = index2Ptr->linePtr->segPtr;
    }
    prevPtr = SplitSeg(index1Ptr);
    if (prevPtr != NULL) {
	segPtr = prevPtr->nextPtr;
	prevPtr->nextPtr = lastPtr;
    } else {
	segPtr = index1Ptr->linePtr->segPtr;
	index1Ptr->linePtr->segPtr = lastPtr;
    }

    /*
     * Delete all of the segments between prevPtr and lastPtr.
     */

    curLinePtr = index1Ptr->linePtr;
    curNodePtr = curLinePtr->parentPtr;
    while (segPtr != lastPtr) {
	if (segPtr == NULL) {
	    TkTextLine *nextLinePtr;

	    /*
	     * 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).
	     */

	    nextLinePtr = TkBTreeNextLine(curLinePtr);
	    if (curLinePtr != index1Ptr->linePtr) {
		if (curNodePtr == index1Ptr->linePtr->parentPtr) {
		    index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
		} else {
		    curNodePtr->children.linePtr = curLinePtr->nextPtr;
		}
		for (nodePtr = curNodePtr; nodePtr != NULL;
			nodePtr = nodePtr->parentPtr) {
		    nodePtr->numLines--;
		}
		curNodePtr->numChildren--;
		ckfree((char *) curLinePtr);
	    }
	    curLinePtr = nextLinePtr;
	    segPtr = curLinePtr->segPtr;

	    /*
	     * If the node is empty then delete it and its parents,
	     * recursively upwards until a non-empty node is found.
	     */

	    while (curNodePtr->numChildren == 0) {
		Node *parentPtr;

		parentPtr = curNodePtr->parentPtr;
		if (parentPtr->children.nodePtr == curNodePtr) {
		    parentPtr->children.nodePtr = curNodePtr->nextPtr;
		} else {
		    Node *prevNodePtr = parentPtr->children.nodePtr;
		    while (prevNodePtr->nextPtr != curNodePtr) {
			prevNodePtr = prevNodePtr->nextPtr;
		    }
		    prevNodePtr->nextPtr = curNodePtr->nextPtr;
		}
		parentPtr->numChildren--;
		ckfree((char *) curNodePtr);
		curNodePtr = parentPtr;
	    }
	    curNodePtr = curLinePtr->parentPtr;
	    continue;
	}

	nextPtr = segPtr->nextPtr;
	if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
	    /*
	     * This segment refuses to die.  Move it to prevPtr and
	     * advance prevPtr if the segment has left gravity.
	     */

	    if (prevPtr == NULL) {
		segPtr->nextPtr = index1Ptr->linePtr->segPtr;
		index1Ptr->linePtr->segPtr = segPtr;
	    } else {
		segPtr->nextPtr = prevPtr->nextPtr;
		prevPtr->nextPtr = segPtr;
	    }
	    if (segPtr->typePtr->leftGravity) {
		prevPtr = segPtr;
	    }
	}
	segPtr = nextPtr;
    }

    /*
     * If the beginning and end of the deletion range are in different
     * lines, join the two lines together and discard the ending line.
     */

    if (index1Ptr->linePtr != index2Ptr->linePtr) {
	TkTextLine *prevLinePtr;

	for (segPtr = lastPtr; segPtr != NULL;
		segPtr = segPtr->nextPtr) {
	    if (segPtr->typePtr->lineChangeProc != NULL) {
		(*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
	    }
	}
	curNodePtr = index2Ptr->linePtr->parentPtr;
	for (nodePtr = curNodePtr; nodePtr != NULL;
		nodePtr = nodePtr->parentPtr) {
	    nodePtr->numLines--;
	}
	curNodePtr->numChildren--;
	prevLinePtr = curNodePtr->children.linePtr;
	if (prevLinePtr == index2Ptr->linePtr) {
	    curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
	} else {
	    while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
		prevLinePtr = prevLinePtr->nextPtr;
	    }
	    prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
	}
	ckfree((char *) index2Ptr->linePtr);
	Rebalance((BTree *) index2Ptr->tree, curNodePtr);
    }

    /*
     * Cleanup the segments in the new line.
     */

    CleanupLine(index1Ptr->linePtr);

    /*
     * Lastly, rebalance the first node of the range.
     */

    Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
    if (tkBTreeDebug) {
	TkBTreeCheck(index1Ptr->tree);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * 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.
 *
 *----------------------------------------------------------------------
 */

TkTextLine *
TkBTreeFindLine(tree, line)
    TkTextBTree tree;			/* B-tree in which to find line. */
    int line;				/* Index of desired line. */
{
    BTree *treePtr = (BTree *) tree;
    register Node *nodePtr;
    register TkTextLine *linePtr;
    int linesLeft;

    nodePtr = treePtr->rootPtr;
    linesLeft = line;
    if ((line < 0) || (line >= nodePtr->numLines)) {
	return NULL;
    }

    /*
     * Work down through levels of the tree until a node is found at
     * level 0.
     */

    while (nodePtr->level != 0) {
	for (nodePtr = nodePtr->children.nodePtr;
		nodePtr->numLines <= linesLeft;
		nodePtr = nodePtr->nextPtr) {
	    if (nodePtr == NULL) {
		panic("TkBTreeFindLine ran out of nodes");
	    }
	    linesLeft -= nodePtr->numLines;
	}
    }

    /*
     * Work through the lines attached to the level-0 node.
     */

    for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
	    linePtr = linePtr->nextPtr) {
	if (linePtr == NULL) {
	    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.
 *
 *----------------------------------------------------------------------
 */

TkTextLine *
TkBTreeNextLine(linePtr)
    register TkTextLine *linePtr;	/* Pointer to existing line in
					 * B-tree. */
{
    register Node *nodePtr;

    if (linePtr->nextPtr != NULL) {
	return linePtr->nextPtr;
    }

    /*
     * 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.
     */

    for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
	if (nodePtr->nextPtr != NULL) {
	    nodePtr = nodePtr->nextPtr;
	    break;
	}
	if (nodePtr->parentPtr == NULL) {
	    return (TkTextLine *) NULL;
	}