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

Line Branch Exec Source
1
/*	$OpenBSD: hashmap.c,v 1.8 2010/01/12 23:22:07 nicm Exp $	*/
2
3
/****************************************************************************
4
 * Copyright (c) 1998-2006,2007 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
 ****************************************************************************/
35
36
/******************************************************************************
37
38
NAME
39
   hashmap.c -- fill in scramble vector based on text hashes
40
41
SYNOPSIS
42
   void _nc_hash_map(void)
43
44
DESCRIPTION:
45
   This code attempts to recognize pairs of old and new lines in the physical
46
and virtual screens.  When a line pair is recognized, the old line index is
47
placed in the oldindex member of the virtual screen line, to be used by the
48
vertical-motion optimizer portion of the update logic (see hardscroll.c).
49
50
   Line pairs are recognized by applying a modified Heckel's algorithm,
51
sped up by hashing.  If a line hash is unique in both screens, those
52
lines must be a pair. Then if the lines just before or after the pair
53
are the same or similar, they are a pair too.
54
55
   We don't worry about false pairs produced by hash collisions, on the
56
assumption that such cases are rare and will only make the latter stages
57
of update less efficient, not introduce errors.
58
59
HOW TO TEST THIS:
60
61
Use the following production:
62
63
hashmap: hashmap.c
64
	$(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
65
66
AUTHOR
67
    Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
68
    Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
69
70
*****************************************************************************/
71
72
#include <curses.priv.h>
73
#include <term.h>		/* for back_color_erase */
74
75
MODULE_ID("$Id: hashmap.c,v 1.8 2010/01/12 23:22:07 nicm Exp $")
76
77
#ifdef HASHDEBUG
78
79
# define _tracef	printf
80
# undef TR
81
# define TR(n, a)	if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
82
# undef screen_lines
83
# define screen_lines MAXLINES
84
# define TEXTWIDTH	1
85
int oldnums[MAXLINES], reallines[MAXLINES];
86
static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
87
static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
88
# define OLDNUM(n)	oldnums[n]
89
# define OLDTEXT(n)	oldtext[n]
90
# define NEWTEXT(m)	newtext[m]
91
# define PENDING(n)     1
92
93
#else /* !HASHDEBUG */
94
95
# define OLDNUM(n)	SP->_oldnum_list[n]
96
# define OLDTEXT(n)	curscr->_line[n].text
97
# define NEWTEXT(m)	newscr->_line[m].text
98
# define TEXTWIDTH	(curscr->_maxx+1)
99
# define PENDING(n)     (newscr->_line[n].firstchar != _NOCHANGE)
100
101
#endif /* !HASHDEBUG */
102
103
#define oldhash		(SP->oldhash)
104
#define newhash		(SP->newhash)
105
#define hashtab		(SP->hashtab)
106
#define lines_alloc	(SP->hashtab_len)
107
108
#if USE_WIDEC_SUPPORT
109
#define HASH_VAL(ch) (ch.chars[0])
110
#else
111
#define HASH_VAL(ch) (ch)
112
#endif
113
114
static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
115
116
static NCURSES_INLINE unsigned long
117
hash(NCURSES_CH_T * text)
118
{
119
    int i;
120
    NCURSES_CH_T ch;
121
    unsigned long result = 0;
122
    for (i = TEXTWIDTH; i > 0; i--) {
123
	ch = *text++;
124
	result += (result << 5) + HASH_VAL(ch);
125
    }
126
    return result;
127
}
128
129
/* approximate update cost */
130
static int
131
update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
132
{
133
    int cost = 0;
134
    int i;
135
136
    for (i = TEXTWIDTH; i > 0; i--, from++, to++)
137
	if (!(CharEq(*from, *to)))
138
	    cost++;
139
140
    return cost;
141
}
142
143
static int
144
update_cost_from_blank(NCURSES_CH_T * to)
145
{
146
    int cost = 0;
147
    int i;
148
    NCURSES_CH_T blank = blankchar;
149
150
    if (back_color_erase)
151
	SetPair(blank, GetPair(stdscr->_nc_bkgd));
152
153
    for (i = TEXTWIDTH; i > 0; i--, to++)
154
	if (!(CharEq(blank, *to)))
155
	    cost++;
156
157
    return cost;
158
}
159
160
/*
161
 * Returns true when moving line 'from' to line 'to' seems to be cost
162
 * effective. 'blank' indicates whether the line 'to' would become blank.
163
 */
164
static NCURSES_INLINE bool
165
cost_effective(const int from, const int to, const bool blank)
166
{
167
    int new_from;
168
169
    if (from == to)
170
	return FALSE;
171
172
    new_from = OLDNUM(from);
173
    if (new_from == _NEWINDEX)
174
	new_from = from;
175
176
    /*
177
     * On the left side of >= is the cost before moving;
178
     * on the right side -- cost after moving.
179
     */
180
    return (((blank ? update_cost_from_blank(NEWTEXT(to))
181
	      : update_cost(OLDTEXT(to), NEWTEXT(to)))
182
	     + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
183
	    >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
184
		 : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
185
		+ update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
186
}
187
188
static void
189
grow_hunks(void)
190
{
191
    int start, end, shift;
192
    int back_limit, forward_limit;	/* limits for cells to fill */
193
    int back_ref_limit, forward_ref_limit;	/* limits for refrences */
194
    int i;
195
    int next_hunk;
196
197
    /*
198
     * This is tricky part.  We have unique pairs to use as anchors.
199
     * Use these to deduce the presence of spans of identical lines.
200
     */
201
    back_limit = 0;
202
    back_ref_limit = 0;
203
204
    i = 0;
205
    while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
206
	i++;
207
    for (; i < screen_lines; i = next_hunk) {
208
	start = i;
209
	shift = OLDNUM(i) - i;
210
211
	/* get forward limit */
212
	i = start + 1;
213
	while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
214
	       == shift)
215
	    i++;
216
	end = i;
217
	while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
218
	    i++;
219
	next_hunk = i;
220
	forward_limit = i;
221
	if (i >= screen_lines || OLDNUM(i) >= i)
222
	    forward_ref_limit = i;
223
	else
224
	    forward_ref_limit = OLDNUM(i);
225
226
	i = start - 1;
227
	/* grow back */
228
	if (shift < 0)
229
	    back_limit = back_ref_limit + (-shift);
230
	while (i >= back_limit) {
231
	    if (newhash[i] == oldhash[i + shift]
232
		|| cost_effective(i + shift, i, shift < 0)) {
233
		OLDNUM(i) = i + shift;
234
		TR(TRACE_UPDATE | TRACE_MOVE,
235
		   ("connected new line %d to old line %d (backward continuation)",
236
		    i, i + shift));
237
	    } else {
238
		TR(TRACE_UPDATE | TRACE_MOVE,
239
		   ("not connecting new line %d to old line %d (backward continuation)",
240
		    i, i + shift));
241
		break;
242
	    }
243
	    i--;
244
	}
245
246
	i = end;
247
	/* grow forward */
248
	if (shift > 0)
249
	    forward_limit = forward_ref_limit - shift;
250
	while (i < forward_limit) {
251
	    if (newhash[i] == oldhash[i + shift]
252
		|| cost_effective(i + shift, i, shift > 0)) {
253
		OLDNUM(i) = i + shift;
254
		TR(TRACE_UPDATE | TRACE_MOVE,
255
		   ("connected new line %d to old line %d (forward continuation)",
256
		    i, i + shift));
257
	    } else {
258
		TR(TRACE_UPDATE | TRACE_MOVE,
259
		   ("not connecting new line %d to old line %d (forward continuation)",
260
		    i, i + shift));
261
		break;
262
	    }
263
	    i++;
264
	}
265
266
	back_ref_limit = back_limit = i;
267
	if (shift > 0)
268
	    back_ref_limit += shift;
269
    }
270
}
271
272
NCURSES_EXPORT(void)
273
_nc_hash_map(void)
274
{
275
    HASHMAP *sp;
276
    register int i;
277
    int start, shift, size;
278
279
    if (screen_lines > lines_alloc) {
280
	if (hashtab)
281
	    free(hashtab);
282
	hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
283
	if (!hashtab) {
284
	    if (oldhash) {
285
		FreeAndNull(oldhash);
286
	    }
287
	    lines_alloc = 0;
288
	    return;
289
	}
290
	lines_alloc = screen_lines;
291
    }
292
293
    if (oldhash && newhash) {
294
	/* re-hash only changed lines */
295
	for (i = 0; i < screen_lines; i++) {
296
	    if (PENDING(i))
297
		newhash[i] = hash(NEWTEXT(i));
298
	}
299
    } else {
300
	/* re-hash all */
301
	if (oldhash == 0)
302
	    oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
303
	if (newhash == 0)
304
	    newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
305
	if (!oldhash || !newhash)
306
	    return;		/* malloc failure */
307
	for (i = 0; i < screen_lines; i++) {
308
	    newhash[i] = hash(NEWTEXT(i));
309
	    oldhash[i] = hash(OLDTEXT(i));
310
	}
311
    }
312
313
#ifdef HASH_VERIFY
314
    for (i = 0; i < screen_lines; i++) {
315
	if (newhash[i] != hash(NEWTEXT(i)))
316
	    fprintf(stderr, "error in newhash[%d]\n", i);
317
	if (oldhash[i] != hash(OLDTEXT(i)))
318
	    fprintf(stderr, "error in oldhash[%d]\n", i);
319
    }
320
#endif
321
322
    /*
323
     * Set up and count line-hash values.
324
     */
325
    memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
326
    for (i = 0; i < screen_lines; i++) {
327
	unsigned long hashval = oldhash[i];
328
329
	for (sp = hashtab; sp->hashval; sp++)
330
	    if (sp->hashval == hashval)
331
		break;
332
	sp->hashval = hashval;	/* in case this is a new entry */
333
	sp->oldcount++;
334
	sp->oldindex = i;
335
    }
336
    for (i = 0; i < screen_lines; i++) {
337
	unsigned long hashval = newhash[i];
338
339
	for (sp = hashtab; sp->hashval; sp++)
340
	    if (sp->hashval == hashval)
341
		break;
342
	sp->hashval = hashval;	/* in case this is a new entry */
343
	sp->newcount++;
344
	sp->newindex = i;
345
346
	OLDNUM(i) = _NEWINDEX;	/* initialize old indices array */
347
    }
348
349
    /*
350
     * Mark line pairs corresponding to unique hash pairs.
351
     *
352
     * We don't mark lines with offset 0, because it can make fail
353
     * extending hunks by cost_effective. Otherwise, it does not
354
     * have any side effects.
355
     */
356
    for (sp = hashtab; sp->hashval; sp++)
357
	if (sp->oldcount == 1 && sp->newcount == 1
358
	    && sp->oldindex != sp->newindex) {
359
	    TR(TRACE_UPDATE | TRACE_MOVE,
360
	       ("new line %d is hash-identical to old line %d (unique)",
361
		sp->newindex, sp->oldindex));
362
	    OLDNUM(sp->newindex) = sp->oldindex;
363
	}
364
365
    grow_hunks();
366
367
    /*
368
     * Eliminate bad or impossible shifts -- this includes removing
369
     * those hunks which could not grow because of conflicts, as well
370
     * those which are to be moved too far, they are likely to destroy
371
     * more than carry.
372
     */
373
    for (i = 0; i < screen_lines;) {
374
	while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
375
	    i++;
376
	if (i >= screen_lines)
377
	    break;
378
	start = i;
379
	shift = OLDNUM(i) - i;
380
	i++;
381
	while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
382
	       == shift)
383
	    i++;
384
	size = i - start;
385
	if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
386
	    while (start < i) {
387
		OLDNUM(start) = _NEWINDEX;
388
		start++;
389
	    }
390
	}
391
    }
392
393
    /* After clearing invalid hunks, try grow the rest. */
394
    grow_hunks();
395
}
396
397
NCURSES_EXPORT(void)
398
_nc_make_oldhash(int i)
399
{
400
    if (oldhash)
401
	oldhash[i] = hash(OLDTEXT(i));
402
}
403
404
NCURSES_EXPORT(void)
405
_nc_scroll_oldhash(int n, int top, int bot)
406
{
407
    size_t size;
408
    int i;
409
410
    if (!oldhash)
411
	return;
412
413
    size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
414
    if (n > 0) {
415
	memmove(oldhash + top, oldhash + top + n, size);
416
	for (i = bot; i > bot - n; i--)
417
	    oldhash[i] = hash(OLDTEXT(i));
418
    } else {
419
	memmove(oldhash + top - n, oldhash + top, size);
420
	for (i = top; i < top - n; i++)
421
	    oldhash[i] = hash(OLDTEXT(i));
422
    }
423
}
424
425
#ifdef HASHDEBUG
426
static void
427
usage(void)
428
{
429
    static const char *table[] =
430
    {
431
	"hashmap test-driver",
432
	"",
433
	"#  comment",
434
	"l  get initial line number vector",
435
	"n  use following letters as text of new lines",
436
	"o  use following letters as text of old lines",
437
	"d  dump state of test arrays",
438
	"h  apply hash mapper and see scroll optimization",
439
	"?  this message"
440
    };
441
    size_t n;
442
    for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
443
	fprintf(stderr, "%s\n", table[n]);
444
}
445
446
int
447
main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
448
{
449
    char line[BUFSIZ], *st, *last;
450
    int n;
451
452
    if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
453
	return EXIT_FAILURE;
454
    (void) _nc_alloc_screen();
455
456
    for (n = 0; n < screen_lines; n++) {
457
	reallines[n] = n;
458
	oldnums[n] = _NEWINDEX;
459
	CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
460
    }
461
462
    if (isatty(fileno(stdin)))
463
	usage();
464
465
#ifdef TRACE
466
    _nc_tracing = TRACE_MOVE;
467
#endif
468
    for (;;) {
469
	/* grab a test command */
470
	if (fgets(line, sizeof(line), stdin) == (char *) NULL)
471
	    break;
472
473
	switch (line[0]) {
474
	case '#':		/* comment */
475
	    (void) fputs(line, stderr);
476
	    break;
477
478
	case 'l':		/* get initial line number vector */
479
	    for (n = 0; n < screen_lines; n++) {
480
		reallines[n] = n;
481
		oldnums[n] = _NEWINDEX;
482
	    }
483
	    n = 0;
484
	    st = strtok_r(line, " ", &last);
485
	    do {
486
		oldnums[n++] = atoi(st);
487
	    } while
488
		((st = strtok_r((char *) NULL, " "), &last) != 0);
489
	    break;
490
491
	case 'n':		/* use following letters as text of new lines */
492
	    for (n = 0; n < screen_lines; n++)
493
		CharOf(newtext[n][0]) = '.';
494
	    for (n = 0; n < screen_lines; n++)
495
		if (line[n + 1] == '\n')
496
		    break;
497
		else
498
		    CharOf(newtext[n][0]) = line[n + 1];
499
	    break;
500
501
	case 'o':		/* use following letters as text of old lines */
502
	    for (n = 0; n < screen_lines; n++)
503
		CharOf(oldtext[n][0]) = '.';
504
	    for (n = 0; n < screen_lines; n++)
505
		if (line[n + 1] == '\n')
506
		    break;
507
		else
508
		    CharOf(oldtext[n][0]) = line[n + 1];
509
	    break;
510
511
	case 'd':		/* dump state of test arrays */
512
#ifdef TRACE
513
	    _nc_linedump();
514
#endif
515
	    (void) fputs("Old lines: [", stdout);
516
	    for (n = 0; n < screen_lines; n++)
517
		putchar(CharOf(oldtext[n][0]));
518
	    putchar(']');
519
	    putchar('\n');
520
	    (void) fputs("New lines: [", stdout);
521
	    for (n = 0; n < screen_lines; n++)
522
		putchar(CharOf(newtext[n][0]));
523
	    putchar(']');
524
	    putchar('\n');
525
	    break;
526
527
	case 'h':		/* apply hash mapper and see scroll optimization */
528
	    _nc_hash_map();
529
	    (void) fputs("Result:\n", stderr);
530
#ifdef TRACE
531
	    _nc_linedump();
532
#endif
533
	    _nc_scroll_optimize();
534
	    (void) fputs("Done.\n", stderr);
535
	    break;
536
	default:
537
	case '?':
538
	    usage();
539
	    break;
540
	}
541
    }
542
#if NO_LEAKS
543
    _nc_free_and_exit(EXIT_SUCCESS);
544
#else
545
    return EXIT_SUCCESS;
546
#endif
547
}
548
549
#endif /* HASHDEBUG */
550
551
/* hashmap.c ends here */