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