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