GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcurses/tty/hardscroll.c Lines: 0 30 0.0 %
Date: 2017-11-13 Branches: 0 38 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: hardscroll.c,v 1.7 2010/01/12 23:22:07 nicm Exp $	*/
2
3
/****************************************************************************
4
 * Copyright (c) 1998-2007,2008 Free Software Foundation, Inc.              *
5
 *                                                                          *
6
 * Permission is hereby granted, free of charge, to any person obtaining a  *
7
 * copy of this software and associated documentation files (the            *
8
 * "Software"), to deal in the Software without restriction, including      *
9
 * without limitation the rights to use, copy, modify, merge, publish,      *
10
 * distribute, distribute with modifications, sublicense, and/or sell       *
11
 * copies of the Software, and to permit persons to whom the Software is    *
12
 * furnished to do so, subject to the following conditions:                 *
13
 *                                                                          *
14
 * The above copyright notice and this permission notice shall be included  *
15
 * in all copies or substantial portions of the Software.                   *
16
 *                                                                          *
17
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
18
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
19
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
20
 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
21
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
22
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
23
 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
24
 *                                                                          *
25
 * Except as contained in this notice, the name(s) of the above copyright   *
26
 * holders shall not be used in advertising or otherwise to promote the     *
27
 * sale, use or other dealings in this Software without prior written       *
28
 * authorization.                                                           *
29
 ****************************************************************************/
30
31
/****************************************************************************
32
 *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
33
 *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
34
 *     and: Thomas E. Dickey                        1996-on                 *
35
 *     and: Alexander V Lukyanov                    1997-1998               *
36
 ****************************************************************************/
37
38
/******************************************************************************
39
40
NAME
41
   hardscroll.c -- hardware-scrolling optimization for ncurses
42
43
SYNOPSIS
44
   void _nc_scroll_optimize(void)
45
46
DESCRIPTION
47
			OVERVIEW
48
49
This algorithm for computes optimum hardware scrolling to transform an
50
old screen (curscr) into a new screen (newscr) via vertical line moves.
51
52
Because the screen has a `grain' (there are insert/delete/scroll line
53
operations but no insert/delete/scroll column operations), it is efficient
54
break the update algorithm into two pieces: a first stage that does only line
55
moves, optimizing the end product of user-invoked insertions, deletions, and
56
scrolls; and a second phase (corresponding to the present doupdate code in
57
ncurses) that does only line transformations.
58
59
The common case we want hardware scrolling for is to handle line insertions
60
and deletions in screen-oriented text-editors.  This two-stage approach will
61
accomplish that at a low computation and code-size cost.
62
63
			LINE-MOVE COMPUTATION
64
65
Now, to a discussion of the line-move computation.
66
67
For expository purposes, consider the screen lines to be represented by
68
integers 0..23 (with the understanding that the value of 23 may vary).
69
Let a new line introduced by insertion, scrolling, or at the bottom of
70
the screen following a line delete be given the index -1.
71
72
Assume that the real screen starts with lines 0..23.  Now, we have
73
the following possible line-oriented operations on the screen:
74
75
Insertion: inserts a line at a given screen row, forcing all lines below
76
to scroll forward.  The last screen line is lost.  For example, an insertion
77
at line 5 would produce: 0..4 -1 5..23.
78
79
Deletion: deletes a line at a given screen row, forcing all lines below
80
to scroll forward.  The last screen line is made new.  For example, a deletion
81
at line 7 would produce: 0..6 8..23 -1.
82
83
Scroll up: move a range of lines up 1.  The bottom line of the range
84
becomes new.  For example, scrolling up the region from 9 to 14 will
85
produce 0..8 10..14 -1 15..23.
86
87
Scroll down: move a range of lines down 1.  The top line of the range
88
becomes new.  For example, scrolling down the region from 12 to 16 will produce
89
0..11 -1 12..15 17..23.
90
91
Now, an obvious property of all these operations is that they preserve the
92
order of old lines, though not their position in the sequence.
93
94
The key trick of this algorithm is that the original line indices described
95
above are actually maintained as _line[].oldindex fields in the window
96
structure, and stick to each line through scroll and insert/delete operations.
97
98
Thus, it is possible at update time to look at the oldnum fields and compute
99
an optimal set of il/dl/scroll operations that will take the real screen
100
lines to the virtual screen lines.  Once these vertical moves have been done,
101
we can hand off to the second stage of the update algorithm, which does line
102
transformations.
103
104
Note that the move computation does not need to have the full generality
105
of a diff algorithm (which it superficially resembles) because lines cannot
106
be moved out of order.
107
108
			THE ALGORITHM
109
110
The scrolling is done in two passes. The first pass is from top to bottom
111
scroling hunks UP. The second one is from bottom to top scrolling hunks DOWN.
112
Obviously enough, no lines to be scrolled will be destroyed. (lav)
113
114
HOW TO TEST THIS:
115
116
Use the following production:
117
118
hardscroll: hardscroll.c
119
	$(CC) -g -DSCROLLDEBUG hardscroll.c -o hardscroll
120
121
Then just type scramble vectors and watch.  The following test loads are
122
a representative sample of cases:
123
124
-----------------------------  CUT HERE ------------------------------------
125
# No lines moved
126
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
127
#
128
# A scroll up
129
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 -1
130
#
131
# A scroll down
132
-1  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
133
#
134
# An insertion (after line 12)
135
 0  1  2  3  4  5  6  7  8  9 10 11 12 -1 13 14 15 16 17 18 19 20 21 22
136
#
137
# A simple deletion (line 10)
138
 0  1  2  3  4  5  6  7  8  9  11 12 13 14 15 16 17 18 19 20 21 22 23 -1
139
#
140
# A more complex case
141
-1 -1 -1 -1 -1  3  4  5  6  7  -1 -1  8  9 10 11 12 13 14 15 16 17 -1 -1
142
-----------------------------  CUT HERE ------------------------------------
143
144
AUTHOR
145
    Eric S. Raymond <esr@snark.thyrsus.com>, November 1994
146
    New algorithm by Alexander V. Lukyanov <lav@yars.free.net>, Aug 1997
147
148
*****************************************************************************/
149
150
#include <curses.priv.h>
151
152
MODULE_ID("$Id: hardscroll.c,v 1.7 2010/01/12 23:22:07 nicm Exp $")
153
154
#if defined(SCROLLDEBUG) || defined(HASHDEBUG)
155
156
# undef screen_lines
157
# define screen_lines MAXLINES
158
NCURSES_EXPORT_VAR(int)
159
oldnums[MAXLINES];
160
# define OLDNUM(n)	oldnums[n]
161
# define _tracef	printf
162
# undef TR
163
# define TR(n, a)	if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
164
165
extern NCURSES_EXPORT_VAR(unsigned) _nc_tracing;
166
167
#else /* no debug */
168
169
/* OLDNUM(n) indicates which line will be shifted to the position n.
170
   if OLDNUM(n) == _NEWINDEX, then the line n in new, not shifted from
171
   somewhere. */
172
NCURSES_EXPORT_VAR(int *)
173
_nc_oldnums = 0;		/* obsolete: keep for ABI compat */
174
175
# if USE_HASHMAP
176
#  define oldnums       SP->_oldnum_list
177
#  define OLDNUM(n)	oldnums[n]
178
# else				/* !USE_HASHMAP */
179
#  define OLDNUM(n)	newscr->_line[n].oldindex
180
# endif				/* !USE_HASHMAP */
181
182
#define OLDNUM_SIZE     SP->_oldnum_size
183
184
#endif /* defined(SCROLLDEBUG) || defined(HASHDEBUG) */
185
186
NCURSES_EXPORT(void)
187
_nc_scroll_optimize(void)
188
/* scroll optimization to transform curscr to newscr */
189
{
190
    int i;
191
    int start, end, shift;
192
193
    TR(TRACE_ICALLS, (T_CALLED("_nc_scroll_optimize")));
194
195
#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
196
#if USE_HASHMAP
197
    /* get enough storage */
198
    if (OLDNUM_SIZE < screen_lines) {
199
	int *new_oldnums = typeRealloc(int, screen_lines, oldnums);
200
	if (!new_oldnums)
201
	    return;
202
	oldnums = new_oldnums;
203
	OLDNUM_SIZE = screen_lines;
204
    }
205
    /* calculate the indices */
206
    _nc_hash_map();
207
#endif
208
#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
209
210
#ifdef TRACE
211
    if (USE_TRACEF(TRACE_UPDATE | TRACE_MOVE)) {
212
	_nc_linedump();
213
	_nc_unlock_global(tracef);
214
    }
215
#endif /* TRACE */
216
217
    /* pass 1 - from top to bottom scrolling up */
218
    for (i = 0; i < screen_lines;) {
219
	while (i < screen_lines && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) <= i))
220
	    i++;
221
	if (i >= screen_lines)
222
	    break;
223
224
	shift = OLDNUM(i) - i;	/* shift > 0 */
225
	start = i;
226
227
	i++;
228
	while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
229
	       == shift)
230
	    i++;
231
	end = i - 1 + shift;
232
233
	TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift));
234
#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
235
	if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) {
236
	    TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll"));
237
	    continue;
238
	}
239
#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
240
    }
241
242
    /* pass 2 - from bottom to top scrolling down */
243
    for (i = screen_lines - 1; i >= 0;) {
244
	while (i >= 0 && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) >= i))
245
	    i--;
246
	if (i < 0)
247
	    break;
248
249
	shift = OLDNUM(i) - i;	/* shift < 0 */
250
	end = i;
251
252
	i--;
253
	while (i >= 0 && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
254
	    i--;
255
	start = i + 1 - (-shift);
256
257
	TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift));
258
#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
259
	if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) {
260
	    TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll"));
261
	    continue;
262
	}
263
#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
264
    }
265
    TR(TRACE_ICALLS, (T_RETURN("")));
266
}
267
268
#if defined(TRACE) || defined(SCROLLDEBUG) || defined(HASHDEBUG)
269
NCURSES_EXPORT(void)
270
_nc_linedump(void)
271
/* dump the state of the real and virtual oldnum fields */
272
{
273
    int n;
274
    char *buf = 0;
275
    size_t want = (screen_lines + 1) * 4;
276
277
    if ((buf = typeMalloc(char, want)) != 0) {
278
279
	(void) strlcpy(buf, "virt", want);
280
	for (n = 0; n < screen_lines; n++)
281
		(void) snprintf(buf + strlen(buf), want - strlen(buf), " %02d", OLDNUM(n));
282
	TR(TRACE_UPDATE | TRACE_MOVE, (buf));
283
	free(buf);
284
    }
285
}
286
#endif /* defined(TRACE) || defined(SCROLLDEBUG) */
287
288
#ifdef SCROLLDEBUG
289
290
int
291
main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
292
{
293
    char line[BUFSIZ], *st, *last;
294
295
#ifdef TRACE
296
    _nc_tracing = TRACE_MOVE;
297
#endif
298
    for (;;) {
299
	int n;
300
301
	for (n = 0; n < screen_lines; n++)
302
	    oldnums[n] = _NEWINDEX;
303
304
	/* grab the test vector */
305
	if (fgets(line, sizeof(line), stdin) == (char *) NULL)
306
	    exit(EXIT_SUCCESS);
307
308
	/* parse it */
309
	n = 0;
310
	if (line[0] == '#') {
311
	    (void) fputs(line, stderr);
312
	    continue;
313
	}
314
	st = strtok_r(line, " ", &last);
315
	do {
316
	    oldnums[n++] = atoi(st);
317
	} while
318
	    ((st = strtok_r((char *) NULL, " ", &last)) != 0);
319
320
	/* display it */
321
	(void) fputs("Initial input:\n", stderr);
322
	_nc_linedump();
323
324
	_nc_scroll_optimize();
325
    }
326
}
327
328
#endif /* SCROLLDEBUG */
329
330
/* hardscroll.c ends here */