xref: /netbsd-src/external/bsd/less/dist/linenum.c (revision 3ffde583575d77f6c315096bca0eb95a16d90d46)
1 /*	$NetBSD: linenum.c,v 1.6 2023/10/06 06:25:22 simonb Exp $	*/
2 
3 /*
4  * Copyright (C) 1984-2023  Mark Nudelman
5  *
6  * You may distribute under the terms of either the GNU General Public
7  * License or the Less License, as specified in the README file.
8  *
9  * For more information, see the README file.
10  */
11 
12 
13 /*
14  * Code to handle displaying line numbers.
15  *
16  * Finding the line number of a given file position is rather tricky.
17  * We don't want to just start at the beginning of the file and
18  * count newlines, because that is slow for large files (and also
19  * wouldn't work if we couldn't get to the start of the file; e.g.
20  * if input is a long pipe).
21  *
22  * So we use the function add_lnum to cache line numbers.
23  * We try to be very clever and keep only the more interesting
24  * line numbers when we run out of space in our table.  A line
25  * number is more interesting than another when it is far from
26  * other line numbers.   For example, we'd rather keep lines
27  * 100,200,300 than 100,101,300.  200 is more interesting than
28  * 101 because 101 can be derived very cheaply from 100, while
29  * 200 is more expensive to derive from 100.
30  *
31  * The function currline() returns the line number of a given
32  * position in the file.  As a side effect, it calls add_lnum
33  * to cache the line number.  Therefore currline is occasionally
34  * called to make sure we cache line numbers often enough.
35  */
36 
37 #include "less.h"
38 
39 /*
40  * Structure to keep track of a line number and the associated file position.
41  * A doubly-linked circular list of line numbers is kept ordered by line number.
42  */
43 struct linenum_info
44 {
45 	struct linenum_info *next;      /* Link to next in the list */
46 	struct linenum_info *prev;      /* Line to previous in the list */
47 	POSITION pos;                   /* File position */
48 	POSITION gap;                   /* Gap between prev and next */
49 	LINENUM line;                   /* Line number */
50 };
51 /*
52  * "gap" needs some explanation: the gap of any particular line number
53  * is the distance between the previous one and the next one in the list.
54  * ("Distance" means difference in file position.)  In other words, the
55  * gap of a line number is the gap which would be introduced if this
56  * line number were deleted.  It is used to decide which one to replace
57  * when we have a new one to insert and the table is full.
58  */
59 
60 #define NPOOL   200                     /* Size of line number pool */
61 
62 #define LONGTIME        (2)             /* In seconds */
63 
64 static struct linenum_info anchor;      /* Anchor of the list */
65 static struct linenum_info *freelist;   /* Anchor of the unused entries */
66 static struct linenum_info pool[NPOOL]; /* The pool itself */
67 static struct linenum_info *spare;      /* We always keep one spare entry */
68 public int scanning_eof = FALSE;
69 
70 extern int linenums;
71 extern int sigs;
72 extern int sc_height;
73 extern int screen_trashed;
74 extern int header_lines;
75 extern int nonum_headers;
76 
77 /*
78  * Initialize the line number structures.
79  */
clr_linenum(void)80 public void clr_linenum(void)
81 {
82 	struct linenum_info *p;
83 
84 	/*
85 	 * Put all the entries on the free list.
86 	 * Leave one for the "spare".
87 	 */
88 	for (p = pool;  p < &pool[NPOOL-2];  p++)
89 		p->next = p+1;
90 	pool[NPOOL-2].next = NULL;
91 	freelist = pool;
92 
93 	spare = &pool[NPOOL-1];
94 
95 	/*
96 	 * Initialize the anchor.
97 	 */
98 	anchor.next = anchor.prev = &anchor;
99 	anchor.gap = 0;
100 	anchor.pos = (POSITION)0;
101 	anchor.line = 1;
102 }
103 
104 /*
105  * Calculate the gap for an entry.
106  */
calcgap(struct linenum_info * p)107 static void calcgap(struct linenum_info *p)
108 {
109 	/*
110 	 * Don't bother to compute a gap for the anchor.
111 	 * Also don't compute a gap for the last one in the list.
112 	 * The gap for that last one should be considered infinite,
113 	 * but we never look at it anyway.
114 	 */
115 	if (p == &anchor || p->next == &anchor)
116 		return;
117 	p->gap = p->next->pos - p->prev->pos;
118 }
119 
120 /*
121  * Add a new line number to the cache.
122  * The specified position (pos) should be the file position of the
123  * FIRST character in the specified line.
124  */
add_lnum(LINENUM linenum,POSITION pos)125 public void add_lnum(LINENUM linenum, POSITION pos)
126 {
127 	struct linenum_info *p;
128 	struct linenum_info *new;
129 	struct linenum_info *nextp;
130 	struct linenum_info *prevp;
131 	POSITION mingap;
132 
133 	/*
134 	 * Find the proper place in the list for the new one.
135 	 * The entries are sorted by position.
136 	 */
137 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
138 		if (p->line == linenum)
139 			/* We already have this one. */
140 			return;
141 	nextp = p;
142 	prevp = p->prev;
143 
144 	if (freelist != NULL)
145 	{
146 		/*
147 		 * We still have free (unused) entries.
148 		 * Use one of them.
149 		 */
150 		new = freelist;
151 		freelist = freelist->next;
152 	} else
153 	{
154 		/*
155 		 * No free entries.
156 		 * Use the "spare" entry.
157 		 */
158 		new = spare;
159 		spare = NULL;
160 	}
161 
162 	/*
163 	 * Fill in the fields of the new entry,
164 	 * and insert it into the proper place in the list.
165 	 */
166 	new->next = nextp;
167 	new->prev = prevp;
168 	new->pos = pos;
169 	new->line = linenum;
170 
171 	nextp->prev = new;
172 	prevp->next = new;
173 
174 	/*
175 	 * Recalculate gaps for the new entry and the neighboring entries.
176 	 */
177 	calcgap(new);
178 	calcgap(nextp);
179 	calcgap(prevp);
180 
181 	if (spare == NULL)
182 	{
183 		/*
184 		 * We have used the spare entry.
185 		 * Scan the list to find the one with the smallest
186 		 * gap, take it out and make it the spare.
187 		 * We should never remove the last one, so stop when
188 		 * we get to p->next == &anchor.  This also avoids
189 		 * looking at the gap of the last one, which is
190 		 * not computed by calcgap.
191 		 */
192 		mingap = anchor.next->gap;
193 		for (p = anchor.next;  p->next != &anchor;  p = p->next)
194 		{
195 			if (p->gap <= mingap)
196 			{
197 				spare = p;
198 				mingap = p->gap;
199 			}
200 		}
201 		spare->next->prev = spare->prev;
202 		spare->prev->next = spare->next;
203 	}
204 }
205 
206 /*
207  * If we get stuck in a long loop trying to figure out the
208  * line number, print a message to tell the user what we're doing.
209  */
longloopmessage(void)210 static void longloopmessage(void)
211 {
212 	ierror("Calculating line numbers", NULL_PARG);
213 }
214 
215 static int loopcount;
216 #if HAVE_TIME
217 static time_type startime;
218 #endif
219 
longish(void)220 static void longish(void)
221 {
222 #if HAVE_TIME
223 	if (loopcount >= 0 && ++loopcount > 100)
224 	{
225 		loopcount = 0;
226 		if (get_time() >= startime + LONGTIME)
227 		{
228 			longloopmessage();
229 			loopcount = -1;
230 		}
231 	}
232 #else
233 	if (loopcount >= 0 && ++loopcount > LONGLOOP)
234 	{
235 		longloopmessage();
236 		loopcount = -1;
237 	}
238 #endif
239 }
240 
241 /*
242  * Turn off line numbers because the user has interrupted
243  * a lengthy line number calculation.
244  */
abort_long(void)245 static void abort_long(void)
246 {
247 	if (loopcount >= 0)
248 		return;
249 	if (linenums == OPT_ONPLUS)
250 		/*
251 		 * We were displaying line numbers, so need to repaint.
252 		 */
253 		screen_trashed = 1;
254 	linenums = 0;
255 	error("Line numbers turned off", NULL_PARG);
256 }
257 
258 /*
259  * Find the line number associated with a given position.
260  * Return 0 if we can't figure it out.
261  */
find_linenum(POSITION pos)262 public LINENUM find_linenum(POSITION pos)
263 {
264 	struct linenum_info *p;
265 	LINENUM linenum;
266 	POSITION cpos;
267 
268 	if (!linenums)
269 		/*
270 		 * We're not using line numbers.
271 		 */
272 		return (0);
273 	if (pos == NULL_POSITION)
274 		/*
275 		 * Caller doesn't know what he's talking about.
276 		 */
277 		return (0);
278 	if (pos <= ch_zero())
279 		/*
280 		 * Beginning of file is always line number 1.
281 		 */
282 		return (1);
283 
284 	/*
285 	 * Find the entry nearest to the position we want.
286 	 */
287 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
288 		continue;
289 	if (p->pos == pos)
290 		/* Found it exactly. */
291 		return (p->line);
292 
293 	/*
294 	 * This is the (possibly) time-consuming part.
295 	 * We start at the line we just found and start
296 	 * reading the file forward or backward till we
297 	 * get to the place we want.
298 	 *
299 	 * First decide whether we should go forward from the
300 	 * previous one or backwards from the next one.
301 	 * The decision is based on which way involves
302 	 * traversing fewer bytes in the file.
303 	 */
304 #if HAVE_TIME
305 	startime = get_time();
306 #endif
307 	loopcount = 0;
308 	if (p == &anchor || pos - p->prev->pos < p->pos - pos)
309 	{
310 		/*
311 		 * Go forward.
312 		 */
313 		p = p->prev;
314 		if (ch_seek(p->pos))
315 			return (0);
316 		for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
317 		{
318 			/*
319 			 * Allow a signal to abort this loop.
320 			 */
321 			cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
322 			if (ABORT_SIGS()) {
323 				abort_long();
324 				return (0);
325 			}
326 			if (cpos == NULL_POSITION)
327 				return (0);
328 			longish();
329 		}
330 		/*
331 		 * We might as well cache it.
332 		 */
333 		add_lnum(linenum, cpos);
334 		/*
335 		 * If the given position is not at the start of a line,
336 		 * make sure we return the correct line number.
337 		 */
338 		if (cpos > pos)
339 			linenum--;
340 	} else
341 	{
342 		/*
343 		 * Go backward.
344 		 */
345 		if (ch_seek(p->pos))
346 			return (0);
347 		for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
348 		{
349 			/*
350 			 * Allow a signal to abort this loop.
351 			 */
352 			cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
353 			if (ABORT_SIGS()) {
354 				abort_long();
355 				return (0);
356 			}
357 			if (cpos == NULL_POSITION)
358 				return (0);
359 			longish();
360 		}
361 		/*
362 		 * We might as well cache it.
363 		 */
364 		add_lnum(linenum, cpos);
365 	}
366 	loopcount = 0;
367 	return (linenum);
368 }
369 
370 /*
371  * Find the position of a given line number.
372  * Return NULL_POSITION if we can't figure it out.
373  */
find_pos(LINENUM linenum)374 public POSITION find_pos(LINENUM linenum)
375 {
376 	struct linenum_info *p;
377 	POSITION cpos;
378 	LINENUM clinenum;
379 
380 	if (linenum <= 1)
381 		/*
382 		 * Line number 1 is beginning of file.
383 		 */
384 		return (ch_zero());
385 
386 	/*
387 	 * Find the entry nearest to the line number we want.
388 	 */
389 	for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
390 		continue;
391 	if (p->line == linenum)
392 		/* Found it exactly. */
393 		return (p->pos);
394 
395 	if (p == &anchor || linenum - p->prev->line < p->line - linenum)
396 	{
397 		/*
398 		 * Go forward.
399 		 */
400 		p = p->prev;
401 		if (ch_seek(p->pos))
402 			return (NULL_POSITION);
403 		for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
404 		{
405 			/*
406 			 * Allow a signal to abort this loop.
407 			 */
408 			cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
409 			if (ABORT_SIGS())
410 				return (NULL_POSITION);
411 			if (cpos == NULL_POSITION)
412 				return (NULL_POSITION);
413 		}
414 	} else
415 	{
416 		/*
417 		 * Go backward.
418 		 */
419 		if (ch_seek(p->pos))
420 			return (NULL_POSITION);
421 		for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
422 		{
423 			/*
424 			 * Allow a signal to abort this loop.
425 			 */
426 			cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
427 			if (ABORT_SIGS())
428 				return (NULL_POSITION);
429 			if (cpos == NULL_POSITION)
430 				return (NULL_POSITION);
431 		}
432 	}
433 	/*
434 	 * We might as well cache it.
435 	 */
436 	add_lnum(clinenum, cpos);
437 	return (cpos);
438 }
439 
440 /*
441  * Return the line number of the "current" line.
442  * The argument "where" tells which line is to be considered
443  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
444  */
currline(int where)445 public LINENUM currline(int where)
446 {
447 	POSITION pos;
448 	POSITION len;
449 	LINENUM linenum;
450 
451 	pos = position(where);
452 	len = ch_length();
453 	while (pos == NULL_POSITION && where >= 0 && where < sc_height)
454 		pos = position(++where);
455 	if (pos == NULL_POSITION)
456 		pos = len;
457 	linenum = find_linenum(pos);
458 	if (pos == len)
459 		linenum--;
460 	return (linenum);
461 }
462 
463 /*
464  * Scan entire file, counting line numbers.
465  */
scan_eof(void)466 public void scan_eof(void)
467 {
468 	POSITION pos = ch_zero();
469 	LINENUM linenum = 0;
470 
471 	if (ch_seek(0))
472 		return;
473 	ierror("Determining length of file", NULL_PARG);
474 	/*
475 	 * scanning_eof prevents the "Waiting for data" message from
476 	 * overwriting "Determining length of file".
477 	 */
478 	scanning_eof = TRUE;
479 	while (pos != NULL_POSITION)
480 	{
481 		/* For efficiency, only add one every 256 line numbers. */
482 		if ((linenum++ % 256) == 0)
483 			add_lnum(linenum, pos);
484 		pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
485 		if (ABORT_SIGS())
486 			break;
487 	}
488 	scanning_eof = FALSE;
489 }
490 
491 /*
492  * Return a line number adjusted for display
493  * (handles the --no-number-headers option).
494  */
vlinenum(LINENUM linenum)495 public LINENUM vlinenum(LINENUM linenum)
496 {
497 	if (nonum_headers)
498 		linenum = (linenum < header_lines) ? 0 : linenum - header_lines;
499 	return linenum;
500 }
501