1 /*
2 * Copyright (C) 1984-2012 Mark Nudelman
3 * Modified for use with illumos by Garrett D'Amore.
4 * Copyright 2014 Garrett D'Amore <garrett@damore.org>
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 * Code to handle displaying line numbers.
14 *
15 * Finding the line number of a given file position is rather tricky.
16 * We don't want to just start at the beginning of the file and
17 * count newlines, because that is slow for large files (and also
18 * wouldn't work if we couldn't get to the start of the file; e.g.
19 * if input is a long pipe).
20 *
21 * So we use the function add_lnum to cache line numbers.
22 * We try to be very clever and keep only the more interesting
23 * line numbers when we run out of space in our table. A line
24 * number is more interesting than another when it is far from
25 * other line numbers. For example, we'd rather keep lines
26 * 100,200,300 than 100,101,300. 200 is more interesting than
27 * 101 because 101 can be derived very cheaply from 100, while
28 * 200 is more expensive to derive from 100.
29 *
30 * The function currline() returns the line number of a given
31 * position in the file. As a side effect, it calls add_lnum
32 * to cache the line number. Therefore currline is occasionally
33 * called to make sure we cache line numbers often enough.
34 */
35
36 #include <sys/time.h>
37
38 #include <time.h>
39
40 #include "less.h"
41
42 /*
43 * Structure to keep track of a line number and the associated file position.
44 * A doubly-linked circular list of line numbers is kept ordered by line number.
45 */
46 struct linenum_info {
47 struct linenum_info *next; /* Link to next in the list */
48 struct linenum_info *prev; /* Line to previous in the list */
49 off_t pos; /* File position */
50 off_t gap; /* Gap between prev and next */
51 off_t line; /* Line number */
52 };
53 /*
54 * "gap" needs some explanation: the gap of any particular line number
55 * is the distance between the previous one and the next one in the list.
56 * ("Distance" means difference in file position.) In other words, the
57 * gap of a line number is the gap which would be introduced if this
58 * line number were deleted. It is used to decide which one to replace
59 * when we have a new one to insert and the table is full.
60 */
61
62 #define NPOOL 200 /* Size of line number pool */
63
64 #define LONGTIME (2) /* In seconds */
65
66 static struct linenum_info anchor; /* Anchor of the list */
67 static struct linenum_info *freelist; /* Anchor of the unused entries */
68 static struct linenum_info pool[NPOOL]; /* The pool itself */
69 static struct linenum_info *spare; /* We always keep one spare entry */
70
71 extern int linenums;
72 extern int sc_height;
73 extern int screen_trashed;
74
75 /*
76 * Initialize the line number structures.
77 */
78 void
clr_linenum(void)79 clr_linenum(void)
80 {
81 struct linenum_info *p;
82
83 /*
84 * Put all the entries on the free list.
85 * Leave one for the "spare".
86 */
87 for (p = pool; p < &pool[NPOOL-2]; p++)
88 p->next = p+1;
89 pool[NPOOL-2].next = NULL;
90 freelist = pool;
91
92 spare = &pool[NPOOL-1];
93
94 /*
95 * Initialize the anchor.
96 */
97 anchor.next = anchor.prev = &anchor;
98 anchor.gap = 0;
99 anchor.pos = 0;
100 anchor.line = 1;
101 }
102
103 /*
104 * Calculate the gap for an entry.
105 */
106 static void
calcgap(struct linenum_info * p)107 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 */
125 void
add_lnum(off_t linenum,off_t pos)126 add_lnum(off_t linenum, off_t pos)
127 {
128 struct linenum_info *p;
129 struct linenum_info *new;
130 struct linenum_info *nextp;
131 struct linenum_info *prevp;
132 off_t mingap;
133
134 /*
135 * Find the proper place in the list for the new one.
136 * The entries are sorted by position.
137 */
138 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
139 if (p->line == linenum)
140 /* We already have this one. */
141 return;
142 nextp = p;
143 prevp = p->prev;
144
145 if (freelist != NULL) {
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 * No free entries.
155 * Use the "spare" entry.
156 */
157 new = spare;
158 spare = NULL;
159 }
160
161 /*
162 * Fill in the fields of the new entry,
163 * and insert it into the proper place in the list.
164 */
165 new->next = nextp;
166 new->prev = prevp;
167 new->pos = pos;
168 new->line = linenum;
169
170 nextp->prev = new;
171 prevp->next = new;
172
173 /*
174 * Recalculate gaps for the new entry and the neighboring entries.
175 */
176 calcgap(new);
177 calcgap(nextp);
178 calcgap(prevp);
179
180 if (spare == NULL) {
181 /*
182 * We have used the spare entry.
183 * Scan the list to find the one with the smallest
184 * gap, take it out and make it the spare.
185 * We should never remove the last one, so stop when
186 * we get to p->next == &anchor. This also avoids
187 * looking at the gap of the last one, which is
188 * not computed by calcgap.
189 */
190 mingap = anchor.next->gap;
191 for (p = anchor.next; p->next != &anchor; p = p->next) {
192 if (p->gap <= mingap) {
193 spare = p;
194 mingap = p->gap;
195 }
196 }
197 spare->next->prev = spare->prev;
198 spare->prev->next = spare->next;
199 }
200 }
201
202 static int loopcount;
203 static struct timespec timeout;
204
205 static void
timeout_set(int seconds)206 timeout_set(int seconds)
207 {
208 clock_gettime(CLOCK_MONOTONIC, &timeout);
209 timeout.tv_sec += seconds;
210 }
211
212 static int
timeout_elapsed(void)213 timeout_elapsed(void)
214 {
215 struct timespec now;
216
217 clock_gettime(CLOCK_MONOTONIC, &now);
218 return timespeccmp(&now, &timeout, >=);
219 }
220
221 static void
longish(void)222 longish(void)
223 {
224 if (loopcount >= 0 && ++loopcount > 100) {
225 loopcount = 0;
226 if (timeout_elapsed()) {
227 ierror("Calculating line numbers", NULL);
228 loopcount = -1;
229 }
230 }
231 }
232
233 /*
234 * Turn off line numbers because the user has interrupted
235 * a lengthy line number calculation.
236 */
237 static void
abort_long(void)238 abort_long(void)
239 {
240 if (linenums == OPT_ONPLUS)
241 /*
242 * We were displaying line numbers, so need to repaint.
243 */
244 screen_trashed = 1;
245 linenums = 0;
246 error("Line numbers turned off", NULL);
247 }
248
249 /*
250 * Find the line number associated with a given position.
251 * Return 0 if we can't figure it out.
252 */
253 off_t
find_linenum(off_t pos)254 find_linenum(off_t pos)
255 {
256 struct linenum_info *p;
257 off_t linenum;
258 off_t cpos;
259
260 if (!linenums)
261 /*
262 * We're not using line numbers.
263 */
264 return (0);
265 if (pos == -1)
266 /*
267 * Caller doesn't know what he's talking about.
268 */
269 return (0);
270 if (pos <= ch_zero())
271 /*
272 * Beginning of file is always line number 1.
273 */
274 return (1);
275
276 /*
277 * Find the entry nearest to the position we want.
278 */
279 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
280 continue;
281 if (p->pos == pos)
282 /* Found it exactly. */
283 return (p->line);
284
285 /*
286 * This is the (possibly) time-consuming part.
287 * We start at the line we just found and start
288 * reading the file forward or backward till we
289 * get to the place we want.
290 *
291 * First decide whether we should go forward from the
292 * previous one or backwards from the next one.
293 * The decision is based on which way involves
294 * traversing fewer bytes in the file.
295 */
296 timeout_set(LONGTIME);
297 if (p == &anchor || pos - p->prev->pos < p->pos - pos) {
298 /*
299 * Go forward.
300 */
301 p = p->prev;
302 if (ch_seek(p->pos))
303 return (0);
304 loopcount = 0;
305 for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) {
306 /*
307 * Allow a signal to abort this loop.
308 */
309 cpos = forw_raw_line(cpos, NULL, NULL);
310 if (abort_sigs()) {
311 abort_long();
312 return (0);
313 }
314 if (cpos == -1)
315 return (0);
316 longish();
317 }
318 /*
319 * We might as well cache it.
320 */
321 add_lnum(linenum, cpos);
322 /*
323 * If the given position is not at the start of a line,
324 * make sure we return the correct line number.
325 */
326 if (cpos > pos)
327 linenum--;
328 } else {
329 /*
330 * Go backward.
331 */
332 if (ch_seek(p->pos))
333 return (0);
334 loopcount = 0;
335 for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) {
336 /*
337 * Allow a signal to abort this loop.
338 */
339 cpos = back_raw_line(cpos, NULL, NULL);
340 if (abort_sigs()) {
341 abort_long();
342 return (0);
343 }
344 if (cpos == -1)
345 return (0);
346 longish();
347 }
348 /*
349 * We might as well cache it.
350 */
351 add_lnum(linenum, cpos);
352 }
353
354 return (linenum);
355 }
356
357 /*
358 * Find the position of a given line number.
359 * Return -1 if we can't figure it out.
360 */
361 off_t
find_pos(off_t linenum)362 find_pos(off_t linenum)
363 {
364 struct linenum_info *p;
365 off_t cpos;
366 off_t clinenum;
367
368 if (linenum <= 1)
369 /*
370 * Line number 1 is beginning of file.
371 */
372 return (ch_zero());
373
374 /*
375 * Find the entry nearest to the line number we want.
376 */
377 for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next)
378 continue;
379 if (p->line == linenum)
380 /* Found it exactly. */
381 return (p->pos);
382
383 if (p == &anchor || linenum - p->prev->line < p->line - linenum) {
384 /*
385 * Go forward.
386 */
387 p = p->prev;
388 if (ch_seek(p->pos))
389 return (-1);
390 for (clinenum = p->line, cpos = p->pos;
391 clinenum < linenum;
392 clinenum++) {
393 /*
394 * Allow a signal to abort this loop.
395 */
396 cpos = forw_raw_line(cpos, NULL, NULL);
397 if (abort_sigs())
398 return (-1);
399 if (cpos == -1)
400 return (-1);
401 }
402 } else {
403 /*
404 * Go backward.
405 */
406 if (ch_seek(p->pos))
407 return (-1);
408 for (clinenum = p->line, cpos = p->pos;
409 clinenum > linenum;
410 clinenum--) {
411 /*
412 * Allow a signal to abort this loop.
413 */
414 cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
415 if (abort_sigs())
416 return (-1);
417 if (cpos == -1)
418 return (-1);
419 }
420 }
421 /*
422 * We might as well cache it.
423 */
424 add_lnum(clinenum, cpos);
425 return (cpos);
426 }
427
428 /*
429 * Return the line number of the "current" line.
430 * The argument "where" tells which line is to be considered
431 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
432 */
433 off_t
currline(int where)434 currline(int where)
435 {
436 off_t pos;
437 off_t len;
438 off_t linenum;
439
440 pos = position(where);
441 len = ch_length();
442 while (pos == -1 && where >= 0 && where < sc_height)
443 pos = position(++where);
444 if (pos == -1)
445 pos = len;
446 linenum = find_linenum(pos);
447 if (pos == len)
448 linenum--;
449 return (linenum);
450 }
451