xref: /netbsd-src/external/bsd/less/dist/linenum.c (revision 3ffde583575d77f6c315096bca0eb95a16d90d46)
1*3ffde583Ssimonb /*	$NetBSD: linenum.c,v 1.6 2023/10/06 06:25:22 simonb Exp $	*/
220006a0bStron 
320006a0bStron /*
4838f5788Ssimonb  * Copyright (C) 1984-2023  Mark Nudelman
520006a0bStron  *
620006a0bStron  * You may distribute under the terms of either the GNU General Public
720006a0bStron  * License or the Less License, as specified in the README file.
820006a0bStron  *
9ec18bca0Stron  * For more information, see the README file.
1020006a0bStron  */
1120006a0bStron 
1220006a0bStron 
1320006a0bStron /*
1420006a0bStron  * Code to handle displaying line numbers.
1520006a0bStron  *
1620006a0bStron  * Finding the line number of a given file position is rather tricky.
1720006a0bStron  * We don't want to just start at the beginning of the file and
1820006a0bStron  * count newlines, because that is slow for large files (and also
1920006a0bStron  * wouldn't work if we couldn't get to the start of the file; e.g.
2020006a0bStron  * if input is a long pipe).
2120006a0bStron  *
2220006a0bStron  * So we use the function add_lnum to cache line numbers.
2320006a0bStron  * We try to be very clever and keep only the more interesting
2420006a0bStron  * line numbers when we run out of space in our table.  A line
2520006a0bStron  * number is more interesting than another when it is far from
2620006a0bStron  * other line numbers.   For example, we'd rather keep lines
2720006a0bStron  * 100,200,300 than 100,101,300.  200 is more interesting than
2820006a0bStron  * 101 because 101 can be derived very cheaply from 100, while
2920006a0bStron  * 200 is more expensive to derive from 100.
3020006a0bStron  *
3120006a0bStron  * The function currline() returns the line number of a given
3220006a0bStron  * position in the file.  As a side effect, it calls add_lnum
3320006a0bStron  * to cache the line number.  Therefore currline is occasionally
3420006a0bStron  * called to make sure we cache line numbers often enough.
3520006a0bStron  */
3620006a0bStron 
3720006a0bStron #include "less.h"
3820006a0bStron 
3920006a0bStron /*
4020006a0bStron  * Structure to keep track of a line number and the associated file position.
4120006a0bStron  * A doubly-linked circular list of line numbers is kept ordered by line number.
4220006a0bStron  */
4320006a0bStron struct linenum_info
4420006a0bStron {
4520006a0bStron 	struct linenum_info *next;      /* Link to next in the list */
4620006a0bStron 	struct linenum_info *prev;      /* Line to previous in the list */
4720006a0bStron 	POSITION pos;                   /* File position */
4820006a0bStron 	POSITION gap;                   /* Gap between prev and next */
4920006a0bStron 	LINENUM line;                   /* Line number */
5020006a0bStron };
5120006a0bStron /*
5220006a0bStron  * "gap" needs some explanation: the gap of any particular line number
5320006a0bStron  * is the distance between the previous one and the next one in the list.
5420006a0bStron  * ("Distance" means difference in file position.)  In other words, the
5520006a0bStron  * gap of a line number is the gap which would be introduced if this
5620006a0bStron  * line number were deleted.  It is used to decide which one to replace
5720006a0bStron  * when we have a new one to insert and the table is full.
5820006a0bStron  */
5920006a0bStron 
6020006a0bStron #define NPOOL   200                     /* Size of line number pool */
6120006a0bStron 
6220006a0bStron #define LONGTIME        (2)             /* In seconds */
6320006a0bStron 
6420006a0bStron static struct linenum_info anchor;      /* Anchor of the list */
6520006a0bStron static struct linenum_info *freelist;   /* Anchor of the unused entries */
6620006a0bStron static struct linenum_info pool[NPOOL]; /* The pool itself */
6720006a0bStron static struct linenum_info *spare;      /* We always keep one spare entry */
68838f5788Ssimonb public int scanning_eof = FALSE;
6920006a0bStron 
7020006a0bStron extern int linenums;
7120006a0bStron extern int sigs;
7220006a0bStron extern int sc_height;
7320006a0bStron extern int screen_trashed;
74838f5788Ssimonb extern int header_lines;
75838f5788Ssimonb extern int nonum_headers;
7620006a0bStron 
7720006a0bStron /*
7820006a0bStron  * Initialize the line number structures.
7920006a0bStron  */
clr_linenum(void)80838f5788Ssimonb public void clr_linenum(void)
8120006a0bStron {
82838f5788Ssimonb 	struct linenum_info *p;
8320006a0bStron 
8420006a0bStron 	/*
8520006a0bStron 	 * Put all the entries on the free list.
8620006a0bStron 	 * Leave one for the "spare".
8720006a0bStron 	 */
8820006a0bStron 	for (p = pool;  p < &pool[NPOOL-2];  p++)
8920006a0bStron 		p->next = p+1;
9020006a0bStron 	pool[NPOOL-2].next = NULL;
9120006a0bStron 	freelist = pool;
9220006a0bStron 
9320006a0bStron 	spare = &pool[NPOOL-1];
9420006a0bStron 
9520006a0bStron 	/*
9620006a0bStron 	 * Initialize the anchor.
9720006a0bStron 	 */
9820006a0bStron 	anchor.next = anchor.prev = &anchor;
9920006a0bStron 	anchor.gap = 0;
10020006a0bStron 	anchor.pos = (POSITION)0;
10120006a0bStron 	anchor.line = 1;
10220006a0bStron }
10320006a0bStron 
10420006a0bStron /*
10520006a0bStron  * Calculate the gap for an entry.
10620006a0bStron  */
calcgap(struct linenum_info * p)107838f5788Ssimonb static void calcgap(struct linenum_info *p)
10820006a0bStron {
10920006a0bStron 	/*
11020006a0bStron 	 * Don't bother to compute a gap for the anchor.
11120006a0bStron 	 * Also don't compute a gap for the last one in the list.
11220006a0bStron 	 * The gap for that last one should be considered infinite,
11320006a0bStron 	 * but we never look at it anyway.
11420006a0bStron 	 */
11520006a0bStron 	if (p == &anchor || p->next == &anchor)
11620006a0bStron 		return;
11720006a0bStron 	p->gap = p->next->pos - p->prev->pos;
11820006a0bStron }
11920006a0bStron 
12020006a0bStron /*
12120006a0bStron  * Add a new line number to the cache.
12220006a0bStron  * The specified position (pos) should be the file position of the
12320006a0bStron  * FIRST character in the specified line.
12420006a0bStron  */
add_lnum(LINENUM linenum,POSITION pos)125838f5788Ssimonb public void add_lnum(LINENUM linenum, POSITION pos)
12620006a0bStron {
127838f5788Ssimonb 	struct linenum_info *p;
128838f5788Ssimonb 	struct linenum_info *new;
129838f5788Ssimonb 	struct linenum_info *nextp;
130838f5788Ssimonb 	struct linenum_info *prevp;
131838f5788Ssimonb 	POSITION mingap;
13220006a0bStron 
13320006a0bStron 	/*
13420006a0bStron 	 * Find the proper place in the list for the new one.
13520006a0bStron 	 * The entries are sorted by position.
13620006a0bStron 	 */
13720006a0bStron 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
13820006a0bStron 		if (p->line == linenum)
13920006a0bStron 			/* We already have this one. */
14020006a0bStron 			return;
14120006a0bStron 	nextp = p;
14220006a0bStron 	prevp = p->prev;
14320006a0bStron 
14420006a0bStron 	if (freelist != NULL)
14520006a0bStron 	{
14620006a0bStron 		/*
14720006a0bStron 		 * We still have free (unused) entries.
14820006a0bStron 		 * Use one of them.
14920006a0bStron 		 */
15020006a0bStron 		new = freelist;
15120006a0bStron 		freelist = freelist->next;
15220006a0bStron 	} else
15320006a0bStron 	{
15420006a0bStron 		/*
15520006a0bStron 		 * No free entries.
15620006a0bStron 		 * Use the "spare" entry.
15720006a0bStron 		 */
15820006a0bStron 		new = spare;
15920006a0bStron 		spare = NULL;
16020006a0bStron 	}
16120006a0bStron 
16220006a0bStron 	/*
16320006a0bStron 	 * Fill in the fields of the new entry,
16420006a0bStron 	 * and insert it into the proper place in the list.
16520006a0bStron 	 */
16620006a0bStron 	new->next = nextp;
16720006a0bStron 	new->prev = prevp;
16820006a0bStron 	new->pos = pos;
16920006a0bStron 	new->line = linenum;
17020006a0bStron 
17120006a0bStron 	nextp->prev = new;
17220006a0bStron 	prevp->next = new;
17320006a0bStron 
17420006a0bStron 	/*
17520006a0bStron 	 * Recalculate gaps for the new entry and the neighboring entries.
17620006a0bStron 	 */
17720006a0bStron 	calcgap(new);
17820006a0bStron 	calcgap(nextp);
17920006a0bStron 	calcgap(prevp);
18020006a0bStron 
18120006a0bStron 	if (spare == NULL)
18220006a0bStron 	{
18320006a0bStron 		/*
18420006a0bStron 		 * We have used the spare entry.
18520006a0bStron 		 * Scan the list to find the one with the smallest
18620006a0bStron 		 * gap, take it out and make it the spare.
18720006a0bStron 		 * We should never remove the last one, so stop when
18820006a0bStron 		 * we get to p->next == &anchor.  This also avoids
18920006a0bStron 		 * looking at the gap of the last one, which is
19020006a0bStron 		 * not computed by calcgap.
19120006a0bStron 		 */
19220006a0bStron 		mingap = anchor.next->gap;
19320006a0bStron 		for (p = anchor.next;  p->next != &anchor;  p = p->next)
19420006a0bStron 		{
19520006a0bStron 			if (p->gap <= mingap)
19620006a0bStron 			{
19720006a0bStron 				spare = p;
19820006a0bStron 				mingap = p->gap;
19920006a0bStron 			}
20020006a0bStron 		}
20120006a0bStron 		spare->next->prev = spare->prev;
20220006a0bStron 		spare->prev->next = spare->next;
20320006a0bStron 	}
20420006a0bStron }
20520006a0bStron 
20620006a0bStron /*
20720006a0bStron  * If we get stuck in a long loop trying to figure out the
20820006a0bStron  * line number, print a message to tell the user what we're doing.
20920006a0bStron  */
longloopmessage(void)210838f5788Ssimonb static void longloopmessage(void)
21120006a0bStron {
21220006a0bStron 	ierror("Calculating line numbers", NULL_PARG);
21320006a0bStron }
21420006a0bStron 
21520006a0bStron static int loopcount;
21620006a0bStron #if HAVE_TIME
217838f5788Ssimonb static time_type startime;
21820006a0bStron #endif
21920006a0bStron 
longish(void)220838f5788Ssimonb static void longish(void)
22120006a0bStron {
22220006a0bStron #if HAVE_TIME
22320006a0bStron 	if (loopcount >= 0 && ++loopcount > 100)
22420006a0bStron 	{
22520006a0bStron 		loopcount = 0;
22620006a0bStron 		if (get_time() >= startime + LONGTIME)
22720006a0bStron 		{
22820006a0bStron 			longloopmessage();
22920006a0bStron 			loopcount = -1;
23020006a0bStron 		}
23120006a0bStron 	}
23220006a0bStron #else
23320006a0bStron 	if (loopcount >= 0 && ++loopcount > LONGLOOP)
23420006a0bStron 	{
23520006a0bStron 		longloopmessage();
23620006a0bStron 		loopcount = -1;
23720006a0bStron 	}
23820006a0bStron #endif
23920006a0bStron }
24020006a0bStron 
24120006a0bStron /*
24220006a0bStron  * Turn off line numbers because the user has interrupted
24320006a0bStron  * a lengthy line number calculation.
24420006a0bStron  */
abort_long(void)245838f5788Ssimonb static void abort_long(void)
24620006a0bStron {
247838f5788Ssimonb 	if (loopcount >= 0)
248838f5788Ssimonb 		return;
24920006a0bStron 	if (linenums == OPT_ONPLUS)
25020006a0bStron 		/*
25120006a0bStron 		 * We were displaying line numbers, so need to repaint.
25220006a0bStron 		 */
25320006a0bStron 		screen_trashed = 1;
25420006a0bStron 	linenums = 0;
25520006a0bStron 	error("Line numbers turned off", NULL_PARG);
25620006a0bStron }
25720006a0bStron 
25820006a0bStron /*
25920006a0bStron  * Find the line number associated with a given position.
26020006a0bStron  * Return 0 if we can't figure it out.
26120006a0bStron  */
find_linenum(POSITION pos)262838f5788Ssimonb public LINENUM find_linenum(POSITION pos)
26320006a0bStron {
264838f5788Ssimonb 	struct linenum_info *p;
265838f5788Ssimonb 	LINENUM linenum;
26620006a0bStron 	POSITION cpos;
26720006a0bStron 
26820006a0bStron 	if (!linenums)
26920006a0bStron 		/*
27020006a0bStron 		 * We're not using line numbers.
27120006a0bStron 		 */
27220006a0bStron 		return (0);
27320006a0bStron 	if (pos == NULL_POSITION)
27420006a0bStron 		/*
27520006a0bStron 		 * Caller doesn't know what he's talking about.
27620006a0bStron 		 */
27720006a0bStron 		return (0);
27820006a0bStron 	if (pos <= ch_zero())
27920006a0bStron 		/*
28020006a0bStron 		 * Beginning of file is always line number 1.
28120006a0bStron 		 */
28220006a0bStron 		return (1);
28320006a0bStron 
28420006a0bStron 	/*
28520006a0bStron 	 * Find the entry nearest to the position we want.
28620006a0bStron 	 */
28720006a0bStron 	for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
28820006a0bStron 		continue;
28920006a0bStron 	if (p->pos == pos)
29020006a0bStron 		/* Found it exactly. */
29120006a0bStron 		return (p->line);
29220006a0bStron 
29320006a0bStron 	/*
29420006a0bStron 	 * This is the (possibly) time-consuming part.
29520006a0bStron 	 * We start at the line we just found and start
29620006a0bStron 	 * reading the file forward or backward till we
29720006a0bStron 	 * get to the place we want.
29820006a0bStron 	 *
29920006a0bStron 	 * First decide whether we should go forward from the
30020006a0bStron 	 * previous one or backwards from the next one.
30120006a0bStron 	 * The decision is based on which way involves
30220006a0bStron 	 * traversing fewer bytes in the file.
30320006a0bStron 	 */
30420006a0bStron #if HAVE_TIME
30520006a0bStron 	startime = get_time();
30620006a0bStron #endif
307838f5788Ssimonb 	loopcount = 0;
30820006a0bStron 	if (p == &anchor || pos - p->prev->pos < p->pos - pos)
30920006a0bStron 	{
31020006a0bStron 		/*
31120006a0bStron 		 * Go forward.
31220006a0bStron 		 */
31320006a0bStron 		p = p->prev;
31420006a0bStron 		if (ch_seek(p->pos))
31520006a0bStron 			return (0);
31620006a0bStron 		for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
31720006a0bStron 		{
31820006a0bStron 			/*
31920006a0bStron 			 * Allow a signal to abort this loop.
32020006a0bStron 			 */
32120006a0bStron 			cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
32220006a0bStron 			if (ABORT_SIGS()) {
32320006a0bStron 				abort_long();
32420006a0bStron 				return (0);
32520006a0bStron 			}
32620006a0bStron 			if (cpos == NULL_POSITION)
32720006a0bStron 				return (0);
32820006a0bStron 			longish();
32920006a0bStron 		}
33020006a0bStron 		/*
33120006a0bStron 		 * We might as well cache it.
33220006a0bStron 		 */
33320006a0bStron 		add_lnum(linenum, cpos);
33420006a0bStron 		/*
33520006a0bStron 		 * If the given position is not at the start of a line,
33620006a0bStron 		 * make sure we return the correct line number.
33720006a0bStron 		 */
33820006a0bStron 		if (cpos > pos)
33920006a0bStron 			linenum--;
34020006a0bStron 	} else
34120006a0bStron 	{
34220006a0bStron 		/*
34320006a0bStron 		 * Go backward.
34420006a0bStron 		 */
34520006a0bStron 		if (ch_seek(p->pos))
34620006a0bStron 			return (0);
34720006a0bStron 		for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
34820006a0bStron 		{
34920006a0bStron 			/*
35020006a0bStron 			 * Allow a signal to abort this loop.
35120006a0bStron 			 */
35220006a0bStron 			cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
35320006a0bStron 			if (ABORT_SIGS()) {
35420006a0bStron 				abort_long();
35520006a0bStron 				return (0);
35620006a0bStron 			}
35720006a0bStron 			if (cpos == NULL_POSITION)
35820006a0bStron 				return (0);
35920006a0bStron 			longish();
36020006a0bStron 		}
36120006a0bStron 		/*
36220006a0bStron 		 * We might as well cache it.
36320006a0bStron 		 */
36420006a0bStron 		add_lnum(linenum, cpos);
36520006a0bStron 	}
366838f5788Ssimonb 	loopcount = 0;
36720006a0bStron 	return (linenum);
36820006a0bStron }
36920006a0bStron 
37020006a0bStron /*
37120006a0bStron  * Find the position of a given line number.
37220006a0bStron  * Return NULL_POSITION if we can't figure it out.
37320006a0bStron  */
find_pos(LINENUM linenum)374838f5788Ssimonb public POSITION find_pos(LINENUM linenum)
37520006a0bStron {
376838f5788Ssimonb 	struct linenum_info *p;
37720006a0bStron 	POSITION cpos;
37820006a0bStron 	LINENUM clinenum;
37920006a0bStron 
38020006a0bStron 	if (linenum <= 1)
38120006a0bStron 		/*
38220006a0bStron 		 * Line number 1 is beginning of file.
38320006a0bStron 		 */
38420006a0bStron 		return (ch_zero());
38520006a0bStron 
38620006a0bStron 	/*
38720006a0bStron 	 * Find the entry nearest to the line number we want.
38820006a0bStron 	 */
38920006a0bStron 	for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
39020006a0bStron 		continue;
39120006a0bStron 	if (p->line == linenum)
39220006a0bStron 		/* Found it exactly. */
39320006a0bStron 		return (p->pos);
39420006a0bStron 
39520006a0bStron 	if (p == &anchor || linenum - p->prev->line < p->line - linenum)
39620006a0bStron 	{
39720006a0bStron 		/*
39820006a0bStron 		 * Go forward.
39920006a0bStron 		 */
40020006a0bStron 		p = p->prev;
40120006a0bStron 		if (ch_seek(p->pos))
40220006a0bStron 			return (NULL_POSITION);
40320006a0bStron 		for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
40420006a0bStron 		{
40520006a0bStron 			/*
40620006a0bStron 			 * Allow a signal to abort this loop.
40720006a0bStron 			 */
40820006a0bStron 			cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
40920006a0bStron 			if (ABORT_SIGS())
41020006a0bStron 				return (NULL_POSITION);
41120006a0bStron 			if (cpos == NULL_POSITION)
41220006a0bStron 				return (NULL_POSITION);
41320006a0bStron 		}
41420006a0bStron 	} else
41520006a0bStron 	{
41620006a0bStron 		/*
41720006a0bStron 		 * Go backward.
41820006a0bStron 		 */
41920006a0bStron 		if (ch_seek(p->pos))
42020006a0bStron 			return (NULL_POSITION);
42120006a0bStron 		for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
42220006a0bStron 		{
42320006a0bStron 			/*
42420006a0bStron 			 * Allow a signal to abort this loop.
42520006a0bStron 			 */
42620006a0bStron 			cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
42720006a0bStron 			if (ABORT_SIGS())
42820006a0bStron 				return (NULL_POSITION);
42920006a0bStron 			if (cpos == NULL_POSITION)
43020006a0bStron 				return (NULL_POSITION);
43120006a0bStron 		}
43220006a0bStron 	}
43320006a0bStron 	/*
43420006a0bStron 	 * We might as well cache it.
43520006a0bStron 	 */
43620006a0bStron 	add_lnum(clinenum, cpos);
43720006a0bStron 	return (cpos);
43820006a0bStron }
43920006a0bStron 
44020006a0bStron /*
44120006a0bStron  * Return the line number of the "current" line.
44220006a0bStron  * The argument "where" tells which line is to be considered
44320006a0bStron  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
44420006a0bStron  */
currline(int where)445838f5788Ssimonb public LINENUM currline(int where)
44620006a0bStron {
44720006a0bStron 	POSITION pos;
44820006a0bStron 	POSITION len;
44920006a0bStron 	LINENUM linenum;
45020006a0bStron 
45120006a0bStron 	pos = position(where);
45220006a0bStron 	len = ch_length();
45320006a0bStron 	while (pos == NULL_POSITION && where >= 0 && where < sc_height)
45420006a0bStron 		pos = position(++where);
45520006a0bStron 	if (pos == NULL_POSITION)
45620006a0bStron 		pos = len;
45720006a0bStron 	linenum = find_linenum(pos);
45820006a0bStron 	if (pos == len)
45920006a0bStron 		linenum--;
46020006a0bStron 	return (linenum);
46120006a0bStron }
462838f5788Ssimonb 
463838f5788Ssimonb /*
464838f5788Ssimonb  * Scan entire file, counting line numbers.
465838f5788Ssimonb  */
scan_eof(void)466838f5788Ssimonb public void scan_eof(void)
467838f5788Ssimonb {
468838f5788Ssimonb 	POSITION pos = ch_zero();
469838f5788Ssimonb 	LINENUM linenum = 0;
470838f5788Ssimonb 
471838f5788Ssimonb 	if (ch_seek(0))
472838f5788Ssimonb 		return;
473838f5788Ssimonb 	ierror("Determining length of file", NULL_PARG);
474838f5788Ssimonb 	/*
475838f5788Ssimonb 	 * scanning_eof prevents the "Waiting for data" message from
476838f5788Ssimonb 	 * overwriting "Determining length of file".
477838f5788Ssimonb 	 */
478838f5788Ssimonb 	scanning_eof = TRUE;
479838f5788Ssimonb 	while (pos != NULL_POSITION)
480838f5788Ssimonb 	{
481838f5788Ssimonb 		/* For efficiency, only add one every 256 line numbers. */
482838f5788Ssimonb 		if ((linenum++ % 256) == 0)
483838f5788Ssimonb 			add_lnum(linenum, pos);
484838f5788Ssimonb 		pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
485838f5788Ssimonb 		if (ABORT_SIGS())
486838f5788Ssimonb 			break;
487838f5788Ssimonb 	}
488838f5788Ssimonb 	scanning_eof = FALSE;
489838f5788Ssimonb }
490838f5788Ssimonb 
491838f5788Ssimonb /*
492838f5788Ssimonb  * Return a line number adjusted for display
493838f5788Ssimonb  * (handles the --no-number-headers option).
494838f5788Ssimonb  */
vlinenum(LINENUM linenum)495838f5788Ssimonb public LINENUM vlinenum(LINENUM linenum)
496838f5788Ssimonb {
497838f5788Ssimonb 	if (nonum_headers)
498838f5788Ssimonb 		linenum = (linenum < header_lines) ? 0 : linenum - header_lines;
499838f5788Ssimonb 	return linenum;
500838f5788Ssimonb }
501