/*  * 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. * *---------------------------------------------------------------------- */TkTextBTreeTkBTreeCreate(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. * *---------------------------------------------------------------------- */voidTkBTreeDestroy(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 voidDestroyNode(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 voidDeleteSummaries(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. * *---------------------------------------------------------------------- */voidTkBTreeInsertChars(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;	}	/*