rangeset.c

nedit 是一款linux下的开发源码的功能强大的编辑器

/* $Id: rangeset.c,v 1.7.2.5 2003/09/08 17:03:32 edg Exp $ */
/*******************************************************************************
*									       *
* rangeset.c	 -- Nirvana Editor rangest functions			       *
*									       *
* Copyright (C) 1999 Mark Edel						       *
*									       *
* This is free software; you can redistribute it and/or modify it under the    *
* terms of the GNU General Public License as published by the Free Software    *
* Foundation; either version 2 of the License, or (at your option) any later   *
* version.								       *
*									       *
* This software is distributed in the hope that it will be useful, but WITHOUT *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or	       *
* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License	       *
* for more details.							       *
*									       *
* You should have received a copy of the GNU General Public License along with *
* software; if not, write to the Free Software Foundation, Inc., 59 Temple     *
* Place, Suite 330, Boston, MA	02111-1307 USA				       *
*									       *
* Nirvana Text Editor							       *
* Sep 26, 2002								       *
*									       *
* Written by Tony Balinski with contributions from Andrew Hood		       *
*									       *
* Modifications:							       *
*									       *
*									       *
*******************************************************************************/
#ifdef HAVE_CONFIG_H
#include "../config.h"
#endif

#include "textBuf.h"
#include "textDisp.h"
#include "rangeset.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#ifdef HAVE_DEBUG_H
#include "../debug.h"
#endif

/* -------------------------------------------------------------------------- */

struct _Range {
    int start, end;			/* range from [start-]end */
};

typedef Rangeset *RangesetUpdateFn(Rangeset *p, int pos, int ins, int del);

struct _Rangeset {
    RangesetUpdateFn *update_fn;	/* modification update function */
    char *update_name;			/* update function name */
    int maxpos;				/* text buffer maxpos */
    int last_index;			/* a place to start looking */
    int n_ranges;			/* how many ranges in ranges */
    Range *ranges;			/* the ranges table */
    unsigned char label;		/* a number 1-63 */

    signed char color_set;              /* 0: unset; 1: set; -1: invalid */
    char *color_name;			/* the name of an assigned color */
    Pixel color;			/* the value of a particular color */
    textBuffer *buf;			/* the text buffer of the rangeset */
    char *name;                         /* name of rangeset */
};

struct _RangesetTable {
    int n_set;				/* how many sets are active */
    textBuffer *buf;			/* the text buffer of the rangeset */
    Rangeset set[N_RANGESETS];		/* the rangeset table */
    unsigned char order[N_RANGESETS];	/* inds of set[]s ordered by depth */
    unsigned char active[N_RANGESETS];	/* entry true if corresp. set active */
    unsigned char depth[N_RANGESETS];	/* depth[i]: pos of set[i] in order[] */
    unsigned char list[N_RANGESETS + 1];/* string of labels in depth order */
};

/* -------------------------------------------------------------------------- */

#define SWAPval(T,a,b) { T t; t = *(a); *(a) = *(b); *(b) = t; }

static unsigned char rangeset_labels[N_RANGESETS + 1] = {
      58, 10, 15,  1, 27, 52, 14,  3, 61, 13, 31, 30, 45, 28, 41, 55, 
      33, 20, 62, 34, 42, 18, 57, 47, 24, 49, 19, 50, 25, 38, 40,  2, 
      21, 39, 59, 22, 60,  4,  6, 16, 29, 37, 48, 46, 54, 43, 32, 56, 
      51,  7,  9, 63,  5,  8, 36, 44, 26, 11, 23, 17, 53, 35, 12, 0
   };

/* -------------------------------------------------------------------------- */

static RangesetUpdateFn rangesetInsDelMaintain;
static RangesetUpdateFn rangesetInclMaintain;
static RangesetUpdateFn rangesetDelInsMaintain;
static RangesetUpdateFn rangesetExclMaintain;
static RangesetUpdateFn rangesetBreakMaintain;

#define DEFAULT_UPDATE_FN_NAME	"maintain"

static struct {
    char *name;
    RangesetUpdateFn *update_fn;
} RangesetUpdateMap[] = {
    {DEFAULT_UPDATE_FN_NAME,	rangesetInsDelMaintain},
    {"ins_del",			rangesetInsDelMaintain},
    {"include",			rangesetInclMaintain},
    {"del_ins",			rangesetDelInsMaintain},
    {"exclude",			rangesetExclMaintain},
    {"break",			rangesetBreakMaintain},
    {(char *)0,			(RangesetUpdateFn *)0}
};

/* -------------------------------------------------------------------------- */

static Range *RangesNew(int n)
{
    Range *newRanges;

    if (n != 0) {
	/* We use a blocked allocation scheme here, with a block size of factor.
	   Only allocations of multiples of factor will be allowed.
	   Be sure to allocate at least one more than we really need, and
	   round up to next higher multiple of factor, ie
		n = (((n + 1) + factor - 1) / factor) * factor
	   If we choose factor = (1 << factor_bits), we can use shifts
	   instead of multiply/divide, ie
	        n = ((n + (1 << factor_bits)) >> factor_bits) << factor_bits
	   or
		n = (1 + (n >> factor_bits)) << factor_bits
	   Since the shifts just strip the end 1 bits, we can even get away
	   with
	   	n = ((1 << factor_bits) + n) & (~0 << factor_bits);
	   Finally, we decide on factor_bits according to the size of n:
	   if n >= 256, we probably want less reallocation on growth than
	   otherwise; choose some arbitrary values thus:
		factor_bits = (n >= 256) ? 6 : 4
	   so
	   	n = (n >= 256) ? (n + (1<<6)) & (~0<<6) : (n + (1<<4)) & (~0<<4)
	   or
	   	n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15)
	 */
	n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15);
	newRanges = (Range *)XtMalloc(n * sizeof (Range));
	return newRanges;
    }

    return NULL;
}

/* -------------------------------------------------------------------------- */

static Range* RangesRealloc(Range* ranges, int n)
{
    int size;
    Range* newRanges;

    if (n > 0)
    {
        /* see RangesNew() for comments */
        n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15);
        size = n * sizeof (Range);
        newRanges = (Range*) (ranges != NULL
                ? XtRealloc((char *)ranges, size)
                : XtMalloc(size));
        return newRanges;
    } else if (ranges != NULL)
    {
        XtFree((char*) ranges);
    }

    return NULL;
}

/* -------------------------------------------------------------------------- */

static Range *RangesFree(Range *ranges)
{
    if (ranges != NULL)
	XtFree((char *)ranges);

    return NULL;
}

/* -------------------------------------------------------------------------- */

/*
** Refresh the given range on the screen. If the range indicated is null, we
** refresh the screen for the whole file.
*/

void RangesetRefreshRange(Rangeset *rangeset, int start, int end)
{
    if (rangeset->buf != NULL)
	BufCheckDisplay(rangeset->buf, start, end);
}

void RangesetRefreshAllRanges(Rangeset *rangeset)
{
    int i;

    for (i = 0; i < rangeset->n_ranges; i++)
	RangesetRefreshRange(rangeset, rangeset->ranges[i].start, rangeset->ranges[i].end);
}

/* -------------------------------------------------------------------------- */

/*
** Remove all ranges from a range set.
*/

void RangesetEmpty(Rangeset *rangeset)
{
    Range *ranges = rangeset->ranges;
    int start, end;

    if (rangeset->color_name && rangeset->color_set > 0) {
	/* this range is colored: we need to clear it */
	rangeset->color_set = -1;

	while (rangeset->n_ranges--) {
	    start = ranges[rangeset->n_ranges].start;
	    end = ranges[rangeset->n_ranges].end;
	    RangesetRefreshRange(rangeset, start, end);
	}
    }

    if (rangeset->color_name)
	XtFree(rangeset->color_name);

    if (rangeset->name) {
        XtFree(rangeset->name);
    }

    rangeset->color_name = (char *)0;
    rangeset->name = (char *)0;
    rangeset->ranges = RangesFree(rangeset->ranges);
}

/* -------------------------------------------------------------------------- */

/*
** Initialise a new range set.
*/

void RangesetInit(Rangeset *rangeset, int label, textBuffer *buf)
{
    rangeset->label = (unsigned char)label;     /* a letter A-Z */
    rangeset->maxpos = 0;			/* text buffer maxpos */
    rangeset->last_index = 0;			/* a place to start looking */
    rangeset->n_ranges = 0;			/* how many ranges in ranges */
    rangeset->ranges = (Range *)0;		/* the ranges table */

    rangeset->color_name = (char *)0;
    rangeset->name = (char *)0;
    rangeset->color_set = 0;
    rangeset->buf = buf;

    rangeset->maxpos = buf->gapEnd - buf->gapStart + buf->length;

    RangesetChangeModifyResponse(rangeset, DEFAULT_UPDATE_FN_NAME);
}

/*
** Change a range set's modification behaviour. Returns true (non-zero)
** if the update function name was found, else false.
*/

int RangesetChangeModifyResponse(Rangeset *rangeset, char *name)
{
    int i;

    if (name == NULL)
	name = DEFAULT_UPDATE_FN_NAME;

    for (i = 0; RangesetUpdateMap[i].name; i++)
	if (strcmp(RangesetUpdateMap[i].name, name) == 0) {
	    rangeset->update_fn = RangesetUpdateMap[i].update_fn;
	    rangeset->update_name = RangesetUpdateMap[i].name;
	    return 1;
	}

    return 0;
}

/* -------------------------------------------------------------------------- */

/*
** Find the index of the first integer in table greater than or equal to pos.
** Fails with len (the total number of entries). The start index base can be
** chosen appropriately.
*/

static int at_or_before(int *table, int base, int len, int val)
{
    int lo, mid=0, hi;

    if (base >= len)
	return len;		/* not sure what this means! */

    lo = base;			/* first valid index */
    hi = len - 1;		/* last valid index */

    while (lo <= hi) {
	mid = (lo + hi) / 2;
	if (val == table[mid])
	    return mid;
	if (val < table[mid])
	    hi = mid - 1;
	else
	    lo = mid + 1;
    }
    /* if we get here, we didn't find val itself */
    if (val > table[mid])
	mid++;

    return mid;
}

static int weighted_at_or_before(int *table, int base, int len, int val)
{
    int lo, mid=0, hi;
    int min, max;

    if (base >= len)
	return len;		/* not sure what this means! */

    lo = base;			/* first valid index */
    hi = len - 1;		/* last valid index */

    min = table[lo];		/* establish initial min/max */
    max = table[hi];

    if (val <= min)		/* initial range checks */
	return lo;		/* needed to avoid out-of-range mid values */
    else if (val > max)
	return len;
    else if (val == max)
	return hi;

    while (lo <= hi) {
        /* Beware of integer overflow when multiplying large numbers! */
        mid = lo + (int)((hi - lo) * (double)(max - val) / (max - min));
	/* we won't worry about min == max - values should be unique */

	if (val == table[mid])
	    return mid;
	if (val < table[mid]) {
	    hi = mid - 1;
	    max = table[mid];
	}
	else { /* val > table[mid] */
	    lo = mid + 1;
	    min = table[mid];
	}
    }

    /* if we get here, we didn't find val itself */
    if (val > table[mid])
	return mid + 1;

    return mid;
}

/* -------------------------------------------------------------------------- */

/*
** Find out whether the position pos is included in one of the ranges of 
** rangeset. Returns the containing range's index if true, -1 otherwise.
** Note: ranges are indexed from zero. 
*/

int RangesetFindRangeNo(Rangeset *rangeset, int index, int *start, int *end)
{
    if (!rangeset || index < 0 || rangeset->n_ranges <= index || !rangeset->ranges)
	return 0;

    *start = rangeset->ranges[index].start;
    *end   = rangeset->ranges[index].end;

    return 1;
}

/*
** Find out whether the position pos is included in one of the ranges of
** rangeset. Returns the containing range's index if true, -1 otherwise.
** Note: ranges are indexed from zero.
*/

int RangesetFindRangeOfPos(Rangeset *rangeset, int pos, int incl_end)
{
    int *ranges;
    int len, ind;

    if (!rangeset || !rangeset->n_ranges || !rangeset->ranges)
	return -1;

    ranges = (int *)rangeset->ranges;		/* { s1,e1, s2,e2, s3,e3,... } */
    len = rangeset->n_ranges * 2;
    ind = at_or_before(ranges, 0, len, pos);
    
    if (ind == len)
	return -1;			/* beyond end */

    if (ind & 1) {			/* ind odd: references an end marker */
	if (pos < ranges[ind] || (incl_end && pos == ranges[ind]))
	    return ind / 2;		/* return the range index */
    }
    else {				/* ind even: references start marker */
	if (pos == ranges[ind])
	    return ind / 2;		/* return the range index */
    }
    return -1;				/* not in any range */
}

/*
** Find out whether the position pos is included in one of the ranges of
** rangeset. Returns the containing range's index if true, -1 otherwise.
** Essentially the same as the RangesetFindRangeOfPos() function, but uses the
** last_index member of the rangeset and weighted_at_or_before() for speedy
** lookup in refresh tasks. The rangeset is assumed to be valid, as is the
** position. We also don't allow checking of the endpoint.
** Returns the including range index, or -1 if not found.
*/

int RangesetCheckRangeOfPos(Rangeset *rangeset, int pos)
{
    int *ranges;
    int len, index, last;

    len = rangeset->n_ranges;
    if (len == 0)
	return -1;			/* no ranges */

    ranges = (int *)rangeset->ranges;		/* { s1,e1, s2,e2, s3,e3,... } */