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