tktextbtree.c

linux系统下的音频通信

/* 
 * 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.37 97/04/25 16:52:00
 */

#include "tkInt.h"
#include "tkPort.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 {
    TkTextTag *tagPtr;			/* Handle for tag. */
    int toggleCount;			/* Number of transitions into or
					 * out of this tag that occur in
					 * the subtree rooted at this node. */
    struct Summary *nextPtr;		/* Next in list of all tags for same
					 * node, or NULL if at end of list. */
} Summary;

/*
 * The data structure below defines a node in the B-tree.
 */

typedef struct Node {
    struct Node *parentPtr;		/* Pointer to parent node, or NULL if
					 * this is the root. */
    struct Node *nextPtr;		/* Next in list of siblings with the
					 * same parent node, or NULL for end
					 * of list. */
    Summary *summaryPtr;		/* First in malloc-ed list of info
					 * about tags in this subtree (NULL if
					 * no tag info in the subtree). */
    int level;				/* Level of this node in the B-tree.
					 * 0 refers to the bottom of the tree
					 * (children are lines, not nodes). */
    union {				/* First in linked list of children. */
	struct Node *nodePtr;		/* Used if level > 0. */
	TkTextLine *linePtr;		/* Used if level == 0. */
    } children;
    int numChildren;			/* Number of children of this node. */
    int numLines;			/* Total number of lines (leaves) in
					 * 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.
 */

#define MAX_CHILDREN 12
#define MIN_CHILDREN 6

/*
 * The data structure below defines an entire B-tree.
 */

typedef struct BTree {
    Node *rootPtr;			/* Pointer to root of B-tree. */
    TkText *textPtr;			/* Used to find tagTable in consistency
					 * checking code */
} BTree;

/*
 * The structure below is used to pass information between
 * TkBTreeGetTags and IncCount:
 */

typedef struct TagInfo {
    int numTags;			/* Number of tags for which there
					 * is currently information in
					 * tags and counts. */
    int arraySize;			/* Number of entries allocated for
					 * tags and counts. */
    TkTextTag **tagPtrs;		/* Array of tags seen so far.
					 * Malloc-ed. */
    int *counts;			/* Toggle count (so far) for each
					 * 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:
 */

#define CSEG_SIZE(chars) ((unsigned) (Tk_Offset(TkTextSegment, body) \
	+ 1 + (chars)))
#define TSEG_SIZE ((unsigned) (Tk_Offset(TkTextSegment, body) \
	+ sizeof(TkTextToggle)))

/*
 * Forward declarations for procedures defined in this file:
 */

static void		ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
			    TkTextTag *tagPtr, int delta));
static void		CharCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr));
static int		CharDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr, int treeGone));
static TkTextSegment *	CharCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr));
static TkTextSegment *	CharSplitProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    int index));
static void		CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
static void		CleanupLine _ANSI_ARGS_((TkTextLine *linePtr));
static void		DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
static void		DestroyNode _ANSI_ARGS_((Node *nodePtr));
static TkTextSegment *	FindTagEnd _ANSI_ARGS_((TkTextBTree tree, 
			    TkTextTag *tagPtr, TkTextIndex *indexPtr));
static void		IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc,
			    TagInfo *tagInfoPtr));
static void		Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
static void		RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
static TkTextSegment *	SplitSeg _ANSI_ARGS_((TkTextIndex *indexPtr));
static void		ToggleCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr));
static TkTextSegment *	ToggleCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr));
static int		ToggleDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr, int treeGone));
static void		ToggleLineChangeProc _ANSI_ARGS_((TkTextSegment *segPtr,
			    TkTextLine *linePtr));
static TkTextSegment *	FindTagStart _ANSI_ARGS_((TkTextBTree tree,
			    TkTextTag *tagPtr, TkTextIndex *indexPtr));

/*
 * Type record for character segments:
 */

Tk_SegType tkTextCharType = {
    "character",				/* name */
    0,						/* leftGravity */
    CharSplitProc,				/* splitProc */
    CharDeleteProc,				/* deleteProc */
    CharCleanupProc,				/* cleanupProc */
    (Tk_SegLineChangeProc *) NULL,		/* lineChangeProc */
    TkTextCharLayoutProc,			/* layoutProc */
    CharCheckProc				/* checkProc */
};

/*
 * Type record for segments marking the beginning of a tagged
 * range:
 */

Tk_SegType tkTextToggleOnType = {
    "toggleOn",					/* name */
    0,						/* leftGravity */
    (Tk_SegSplitProc *) NULL,			/* splitProc */
    ToggleDeleteProc,				/* deleteProc */
    ToggleCleanupProc,				/* cleanupProc */
    ToggleLineChangeProc,			/* lineChangeProc */
    (Tk_SegLayoutProc *) NULL,			/* layoutProc */
    ToggleCheckProc				/* checkProc */
};

/*
 * Type record for segments marking the end of a tagged
 * range:
 */

Tk_SegType tkTextToggleOffType = {
    "toggleOff",				/* name */
    1,						/* leftGravity */
    (Tk_SegSplitProc *) NULL,			/* splitProc */
    ToggleDeleteProc,				/* deleteProc */
    ToggleCleanupProc,				/* cleanupProc */
    ToggleLineChangeProc,			/* lineChangeProc */
    (Tk_SegLayoutProc *) NULL,			/* layoutProc */
    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.
 *
 *----------------------------------------------------------------------
 */

TkTextBTree
TkBTreeCreate(textPtr)
    TkText *textPtr;
{
    register BTree *treePtr;
    register Node *rootPtr;
    register TkTextLine *linePtr, *linePtr2;
    register TkTextSegment *segPtr;

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

    rootPtr = (Node *) ckalloc(sizeof(Node));
    linePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
    linePtr2 = (TkTextLine *) ckalloc(sizeof(TkTextLine));
    rootPtr->parentPtr = NULL;
    rootPtr->nextPtr = NULL;
    rootPtr->summaryPtr = NULL;
    rootPtr->level = 0;
    rootPtr->children.linePtr = linePtr;
    rootPtr->numChildren = 2;
    rootPtr->numLines = 2;

    linePtr->parentPtr = rootPtr;
    linePtr->nextPtr = linePtr2;
    segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
    linePtr->segPtr = segPtr;
    segPtr->typePtr = &tkTextCharType;
    segPtr->nextPtr = NULL;
    segPtr->size = 1;
    segPtr->body.chars[0] = '\n';
    segPtr->body.chars[1] = 0;

    linePtr2->parentPtr = rootPtr;
    linePtr2->nextPtr = NULL;
    segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
    linePtr2->segPtr = segPtr;
    segPtr->typePtr = &tkTextCharType;
    segPtr->nextPtr = NULL;
    segPtr->size = 1;
    segPtr->body.chars[0] = '\n';
    segPtr->body.chars[1] = 0;

    treePtr = (BTree *) ckalloc(sizeof(BTree));
    treePtr->rootPtr = rootPtr;
    treePtr->textPtr = textPtr;

    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
TkBTreeDestroy(tree)
    TkTextBTree tree;			/* Pointer to tree to delete. */ 
{
    BTree *treePtr = (BTree *) tree;

    DestroyNode(treePtr->rootPtr);
    ckfree((char *) treePtr);
}

/*
 *----------------------------------------------------------------------
 *
 * 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
DestroyNode(nodePtr)
    register Node *nodePtr;
{
    if (nodePtr->level == 0) {
	TkTextLine *linePtr;
	TkTextSegment *segPtr;

	while (nodePtr->children.linePtr != NULL) {
	    linePtr = nodePtr->children.linePtr;
	    nodePtr->children.linePtr = linePtr->nextPtr;
	    while (linePtr->segPtr != NULL) {
		segPtr = linePtr->segPtr;
		linePtr->segPtr = segPtr->nextPtr;
		(*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
	    }
	    ckfree((char *) linePtr);
	}
    } else {
	register Node *childPtr;

	while (nodePtr->children.nodePtr != NULL) {
	    childPtr = nodePtr->children.nodePtr;
	    nodePtr->children.nodePtr = childPtr->nextPtr;
	    DestroyNode(childPtr);
	}
    }
    DeleteSummaries(nodePtr->summaryPtr);
    ckfree((char *) nodePtr);
}

/*
 *----------------------------------------------------------------------
 *
 * 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
DeleteSummaries(summaryPtr)
    register Summary *summaryPtr;	/* First in list of node's tag
					 * summaries. */
{
    register Summary *nextPtr;
    while (summaryPtr != NULL) {
	nextPtr = summaryPtr->nextPtr;
	ckfree((char *) summaryPtr);
	summaryPtr = nextPtr;
    }
}

/*
 *----------------------------------------------------------------------
 *
 * 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
TkBTreeInsertChars(indexPtr, string)
    register TkTextIndex *indexPtr;	/* Indicates where to insert text.
					 * 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). */
{
    register Node *nodePtr;
    register TkTextSegment *prevPtr;	/* The segment just before the first
					 * new segment (NULL means new segment
					 * is at beginning of line). */
    TkTextSegment *curPtr;		/* Current segment;  new characters
					 * are inserted just after this one. 
					 * NULL means insert at beginning of
					 * line. */
    TkTextLine *linePtr;		/* Current line (new segments are
					 * added to this line). */
    register TkTextSegment *segPtr;
    TkTextLine *newLinePtr;
    int chunkSize;			/* # characters in current chunk. */
    register char *eol;			/* Pointer to character just after last
					 * one in current chunk. */
    int changeToLineCount;		/* Counts change to total number of
					 * lines in file. */

    prevPtr = SplitSeg(indexPtr);
    linePtr = indexPtr->linePtr;
    curPtr = prevPtr;

    /*
     * 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) {
	for (eol = string; *eol != 0; eol++) {
	    if (*eol == '\n') {
		eol++;
		break;
	    }
	}
	chunkSize = eol-string;
	segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
	segPtr->typePtr = &tkTextCharType;
	if (curPtr == NULL) {
	    segPtr->nextPtr = linePtr->segPtr;
	    linePtr->segPtr = segPtr;
	} else {
	    segPtr->nextPtr = curPtr->nextPtr;
	    curPtr->nextPtr = segPtr;
	}
	segPtr->size = chunkSize;
	strncpy(segPtr->body.chars, string, (size_t) chunkSize);
	segPtr->body.chars[chunkSize] = 0;

	if (eol[-1] != '\n') {
	    break;
	}

	/*