lib_mvcur.c

ncurses 库 可能有用酒用 没用就算了 我觉得还可以用

/****************************************************************************
 * Copyright (c) 1998-2004,2005 Free Software Foundation, Inc.              *
 *                                                                          *
 * Permission is hereby granted, free of charge, to any person obtaining a  *
 * copy of this software and associated documentation files (the            *
 * "Software"), to deal in the Software without restriction, including      *
 * without limitation the rights to use, copy, modify, merge, publish,      *
 * distribute, distribute with modifications, sublicense, and/or sell       *
 * copies of the Software, and to permit persons to whom the Software is    *
 * furnished to do so, subject to the following conditions:                 *
 *                                                                          *
 * The above copyright notice and this permission notice shall be included  *
 * in all copies or substantial portions of the Software.                   *
 *                                                                          *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
 *                                                                          *
 * Except as contained in this notice, the name(s) of the above copyright   *
 * holders shall not be used in advertising or otherwise to promote the     *
 * sale, use or other dealings in this Software without prior written       *
 * authorization.                                                           *
 ****************************************************************************/

/****************************************************************************
 *  Author: Zeyd M. Ben-Halim <[e-mail]> 1992,1995               *
 *     and: Eric S. Raymond <[e-mail]>                         *
 *     and: Thomas E. Dickey                        1996-on                 *
 ****************************************************************************/

/*
**	lib_mvcur.c
**
**	The routines for moving the physical cursor and scrolling:
**
**		void _nc_mvcur_init(void)
**
**		void _nc_mvcur_resume(void)
**
**		int mvcur(int old_y, int old_x, int new_y, int new_x)
**
**		void _nc_mvcur_wrap(void)
**
** Comparisons with older movement optimizers:
**    SVr3 curses mvcur() can't use cursor_to_ll or auto_left_margin.
**    4.4BSD curses can't use cuu/cud/cuf/cub/hpa/vpa/tab/cbt for local
** motions.  It doesn't use tactics based on auto_left_margin.  Weirdly
** enough, it doesn't use its own hardware-scrolling routine to scroll up
** destination lines for out-of-bounds addresses!
**    old ncurses optimizer: less accurate cost computations (in fact,
** it was broken and had to be commented out!).
**
** Compile with -DMAIN to build an interactive tester/timer for the movement
** optimizer.  You can use it to investigate the optimizer's behavior.
** You can also use it for tuning the formulas used to determine whether
** or not full optimization is attempted.
**
** This code has a nasty tendency to find bugs in terminfo entries, because it
** exercises the non-cup movement capabilities heavily.  If you think you've
** found a bug, try deleting subsets of the following capabilities (arranged
** in decreasing order of suspiciousness): it, tab, cbt, hpa, vpa, cuu, cud,
** cuf, cub, cuu1, cud1, cuf1, cub1.  It may be that one or more are wrong.
**
** Note: you should expect this code to look like a resource hog in a profile.
** That's because it does a lot of I/O, through the tputs() calls.  The I/O
** cost swamps the computation overhead (and as machines get faster, this
** will become even more true).  Comments in the test exerciser at the end
** go into detail about tuning and how you can gauge the optimizer's
** effectiveness.
**/

/****************************************************************************
 *
 * Constants and macros for optimizer tuning.
 *
 ****************************************************************************/

/*
 * The average overhead of a full optimization computation in character
 * transmission times.  If it's too high, the algorithm will be a bit
 * over-biased toward using cup rather than local motions; if it's too
 * low, the algorithm may spend more time than is strictly optimal
 * looking for non-cup motions.  Profile the optimizer using the `t'
 * command of the exerciser (see below), and round to the nearest integer.
 *
 * Yes, I (esr) thought about computing expected overhead dynamically, say
 * by derivation from a running average of optimizer times.  But the
 * whole point of this optimization is to *decrease* the frequency of
 * system calls. :-)
 */
#define COMPUTE_OVERHEAD	1	/* I use a 90MHz Pentium @ 9.6Kbps */

/*
 * LONG_DIST is the distance we consider to be just as costly to move over as a
 * cup sequence is to emit.  In other words, it's the length of a cup sequence
 * adjusted for average computation overhead.  The magic number is the length
 * of "\033[yy;xxH", the typical cup sequence these days.
 */
#define LONG_DIST		(8 - COMPUTE_OVERHEAD)

/*
 * Tell whether a motion is optimizable by local motions.  Needs to be cheap to
 * compute. In general, all the fast moves go to either the right or left edge
 * of the screen.  So any motion to a location that is (a) further away than
 * LONG_DIST and (b) further inward from the right or left edge than LONG_DIST,
 * we'll consider nonlocal.
 */
#define NOT_LOCAL(fy, fx, ty, tx)	((tx > LONG_DIST) \
 		 && (tx < screen_columns - 1 - LONG_DIST) \
		 && (abs(ty-fy) + abs(tx-fx) > LONG_DIST))

/****************************************************************************
 *
 * External interfaces
 *
 ****************************************************************************/

/*
 * For this code to work OK, the following components must live in the
 * screen structure:
 *
 *	int		_char_padding;	// cost of character put
 *	int		_cr_cost;	// cost of (carriage_return)
 *	int		_cup_cost;	// cost of (cursor_address)
 *	int		_home_cost;	// cost of (cursor_home)
 *	int		_ll_cost;	// cost of (cursor_to_ll)
 *#if USE_HARD_TABS
 *	int		_ht_cost;	// cost of (tab)
 *	int		_cbt_cost;	// cost of (back_tab)
 *#endif USE_HARD_TABS
 *	int		_cub1_cost;	// cost of (cursor_left)
 *	int		_cuf1_cost;	// cost of (cursor_right)
 *	int		_cud1_cost;	// cost of (cursor_down)
 *	int		_cuu1_cost;	// cost of (cursor_up)
 *	int		_cub_cost;	// cost of (parm_cursor_left)
 *	int		_cuf_cost;	// cost of (parm_cursor_right)
 *	int		_cud_cost;	// cost of (parm_cursor_down)
 *	int		_cuu_cost;	// cost of (parm_cursor_up)
 *	int		_hpa_cost;	// cost of (column_address)
 *	int		_vpa_cost;	// cost of (row_address)
 *	int		_ech_cost;	// cost of (erase_chars)
 *	int		_rep_cost;	// cost of (repeat_char)
 *
 * The USE_HARD_TABS switch controls whether it is reliable to use tab/backtabs
 * for local motions.  On many systems, it's not, due to uncertainties about
 * tab delays and whether or not tabs will be expanded in raw mode.  If you
 * have parm_right_cursor, tab motions don't win you a lot anyhow.
 */

#include <curses.priv.h>
#include <term.h>
#include <ctype.h>

MODULE_ID("$Id: lib_mvcur.c,v 1.103 2005/06/11 19:30:15 tom Exp $")

#define WANT_CHAR(y, x)	SP->_newscr->_line[y].text[x]	/* desired state */
#define BAUDRATE	cur_term->_baudrate	/* bits per second */

#if defined(MAIN) || defined(NCURSES_TEST)
#include <sys/time.h>

static bool profiling = FALSE;
static float diff;
#endif /* MAIN */

#define OPT_SIZE 512

static int normalized_cost(const char *const cap, int affcnt);

/****************************************************************************
 *
 * Initialization/wrapup (including cost pre-computation)
 *
 ****************************************************************************/

#ifdef TRACE
static int
trace_cost_of(const char *capname, const char *cap, int affcnt)
{
    int result = _nc_msec_cost(cap, affcnt);
    TR(TRACE_CHARPUT | TRACE_MOVE,
       ("CostOf %s %d %s", capname, result, _nc_visbuf(cap)));
    return result;
}
#define CostOf(cap,affcnt) trace_cost_of(#cap,cap,affcnt);

static int
trace_normalized_cost(const char *capname, const char *cap, int affcnt)
{
    int result = normalized_cost(cap, affcnt);
    TR(TRACE_CHARPUT | TRACE_MOVE,
       ("NormalizedCost %s %d %s", capname, result, _nc_visbuf(cap)));
    return result;
}
#define NormalizedCost(cap,affcnt) trace_normalized_cost(#cap,cap,affcnt);

#else

#define CostOf(cap,affcnt) _nc_msec_cost(cap,affcnt);
#define NormalizedCost(cap,affcnt) normalized_cost(cap,affcnt);

#endif

NCURSES_EXPORT(int)
_nc_msec_cost(const char *const cap, int affcnt)
/* compute the cost of a given operation */
{
    if (cap == 0)
	return (INFINITY);
    else {
	const char *cp;
	float cum_cost = 0.0;

	for (cp = cap; *cp; cp++) {
	    /* extract padding, either mandatory or required */
	    if (cp[0] == '$' && cp[1] == '<' && strchr(cp, '>')) {
		float number = 0.0;

		for (cp += 2; *cp != '>'; cp++) {
		    if (isdigit(UChar(*cp)))
			number = number * 10 + (*cp - '0');
		    else if (*cp == '*')
			number *= affcnt;
		    else if (*cp == '.' && (*++cp != '>') && isdigit(UChar(*cp)))
			number += (*cp - '0') / 10.0;
		}

#if NCURSES_NO_PADDING
		if (!(SP->_no_padding))
#endif
		    cum_cost += number * 10;
	    } else
		cum_cost += SP->_char_padding;
	}

	return ((int) cum_cost);
    }
}

static int
normalized_cost(const char *const cap, int affcnt)
/* compute the effective character-count for an operation (round up) */
{
    int cost = _nc_msec_cost(cap, affcnt);
    if (cost != INFINITY)
	cost = (cost + SP->_char_padding - 1) / SP->_char_padding;
    return cost;
}

static void
reset_scroll_region(void)
/* Set the scroll-region to a known state (the default) */
{
    if (change_scroll_region) {
	TPUTS_TRACE("change_scroll_region");
	putp(tparm(change_scroll_region, 0, screen_lines - 1));
    }
}

NCURSES_EXPORT(void)
_nc_mvcur_resume(void)
/* what to do at initialization time and after each shellout */
{
    /* initialize screen for cursor access */
    if (enter_ca_mode) {
	TPUTS_TRACE("enter_ca_mode");
	putp(enter_ca_mode);
    }

    /*
     * Doing this here rather than in _nc_mvcur_wrap() ensures that
     * ncurses programs will see a reset scroll region even if a
     * program that messed with it died ungracefully.
     *
     * This also undoes the effects of terminal init strings that assume
     * they know the screen size.  This is useful when you're running
     * a vt100 emulation through xterm.
     */
    reset_scroll_region();
    SP->_cursrow = SP->_curscol = -1;

    /* restore cursor shape */
    if (SP->_cursor != -1) {
	int cursor = SP->_cursor;
	SP->_cursor = -1;
	curs_set(cursor);
    }
}

NCURSES_EXPORT(void)
_nc_mvcur_init(void)
/* initialize the cost structure */
{
    if (isatty(fileno(SP->_ofp)))
	SP->_char_padding = ((BAUDBYTE * 1000 * 10)
			     / (BAUDRATE > 0 ? BAUDRATE : 9600));
    else
	SP->_char_padding = 1;	/* must be nonzero */
    if (SP->_char_padding <= 0)
	SP->_char_padding = 1;	/* must be nonzero */
    TR(TRACE_CHARPUT | TRACE_MOVE, ("char_padding %d msecs", SP->_char_padding));

    /* non-parameterized local-motion strings */
    SP->_cr_cost = CostOf(carriage_return, 0);
    SP->_home_cost = CostOf(cursor_home, 0);
    SP->_ll_cost = CostOf(cursor_to_ll, 0);
#if USE_HARD_TABS
    SP->_ht_cost = CostOf(tab, 0);
    SP->_cbt_cost = CostOf(back_tab, 0);
#endif /* USE_HARD_TABS */
    SP->_cub1_cost = CostOf(cursor_left, 0);
    SP->_cuf1_cost = CostOf(cursor_right, 0);
    SP->_cud1_cost = CostOf(cursor_down, 0);
    SP->_cuu1_cost = CostOf(cursor_up, 0);

    SP->_smir_cost = CostOf(enter_insert_mode, 0);
    SP->_rmir_cost = CostOf(exit_insert_mode, 0);
    SP->_ip_cost = 0;
    if (insert_padding) {
	SP->_ip_cost = CostOf(insert_padding, 0);
    }

    /*
     * Assumption: if the terminal has memory_relative addressing, the
     * initialization strings or smcup will set single-page mode so we
     * can treat it like absolute screen addressing.  This seems to be true
     * for all cursor_mem_address terminal types in the terminfo database.
     */
    SP->_address_cursor = cursor_address ? cursor_address : cursor_mem_address;

    /*
     * Parametrized local-motion strings.  This static cost computation
     * depends on the following assumptions:
     *
     * (1) They never have * padding.  In the entire master terminfo database
     *     as of March 1995, only the obsolete Zenith Z-100 pc violates this.
     *     (Proportional padding is found mainly in insert, delete and scroll
     *     capabilities).
     *
     * (2) The average case of cup has two two-digit parameters.  Strictly,
     *     the average case for a 24 * 80 screen has ((10*10*(1 + 1)) +
     *     (14*10*(1 + 2)) + (10*70*(2 + 1)) + (14*70*4)) / (24*80) = 3.458
     *     digits of parameters.  On a 25x80 screen the average is 3.6197.
     *     On larger screens the value gets much closer to 4.
     *
     * (3) The average case of cub/cuf/hpa/ech/rep has 2 digits of parameters
     *     (strictly, (((10 * 1) + (70 * 2)) / 80) = 1.8750).
     *
     * (4) The average case of cud/cuu/vpa has 2 digits of parameters
     *     (strictly, (((10 * 1) + (14 * 2)) / 24) = 1.5833).
     *
     * All these averages depend on the assumption that all parameter values
     * are equally probable.
     */
    SP->_cup_cost = CostOf(tparm(SP->_address_cursor, 23, 23), 1);
    SP->_cub_cost = CostOf(tparm(parm_left_cursor, 23), 1);
    SP->_cuf_cost = CostOf(tparm(parm_right_cursor, 23), 1);
    SP->_cud_cost = CostOf(tparm(parm_down_cursor, 23), 1);
    SP->_cuu_cost = CostOf(tparm(parm_up_cursor, 23), 1);
    SP->_hpa_cost = CostOf(tparm(column_address, 23), 1);
    SP->_vpa_cost = CostOf(tparm(row_address, 23), 1);

    /* non-parameterized screen-update strings */
    SP->_ed_cost = NormalizedCost(clr_eos, 1);
    SP->_el_cost = NormalizedCost(clr_eol, 1);
    SP->_el1_cost = NormalizedCost(clr_bol, 1);
    SP->_dch1_cost = NormalizedCost(delete_character, 1);
    SP->_ich1_cost = NormalizedCost(insert_character, 1);

    /*
     * If this is a bce-terminal, we want to bias the choice so we use clr_eol
     * rather than spaces at the end of a line.
     */
    if (back_color_erase)
	SP->_el_cost = 0;

    /* parameterized screen-update strings */
    SP->_dch_cost = NormalizedCost(tparm(parm_dch, 23), 1);
    SP->_ich_cost = NormalizedCost(tparm(parm_ich, 23), 1);
    SP->_ech_cost = NormalizedCost(tparm(erase_chars, 23), 1);
    SP->_rep_cost = NormalizedCost(tparm(repeat_char, ' ', 23), 1);

    SP->_cup_ch_cost = NormalizedCost(tparm(SP->_address_cursor, 23, 23), 1);
    SP->_hpa_ch_cost = NormalizedCost(tparm(column_address, 23), 1);
    SP->_cuf_ch_cost = NormalizedCost(tparm(parm_right_cursor, 23), 1);
    SP->_inline_cost = min(SP->_cup_ch_cost,
			   min(SP->_hpa_ch_cost,
			       SP->_cuf_ch_cost));

    /*
     * If save_cursor is used within enter_ca_mode, we should not use it for
     * scrolling optimization, since the corresponding restore_cursor is not
     * nested on the various terminals (vt100, xterm, etc.) which use this
     * feature.
     */
    if (save_cursor != 0
	&& enter_ca_mode != 0
	&& strstr(enter_ca_mode, save_cursor) != 0) {
	T(("...suppressed sc/rc capability due to conflict with smcup/rmcup"));
	save_cursor = 0;
	restore_cursor = 0;
    }

    /*
     * A different, possibly better way to arrange this would be to set
     * SP->_endwin = TRUE at window initialization time and let this be
     * called by doupdate's return-from-shellout code.
     */
    _nc_mvcur_resume();
}