2 * Copyright (C) 1984-2015 Mark Nudelman
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.
7 * For more information, see the README file.
12 * Code to handle displaying line numbers.
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).
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.
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.
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.
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 */
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.
58 #define NPOOL 200 /* Size of line number pool */
60 #define LONGTIME (2) /* In seconds */
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 */
70 extern int screen_trashed
;
73 * Initialize the line number structures.
78 register struct linenum_info
*p
;
81 * Put all the entries on the free list.
82 * Leave one for the "spare".
84 for (p
= pool
; p
< &pool
[NPOOL
-2]; p
++)
86 pool
[NPOOL
-2].next
= NULL
;
89 spare
= &pool
[NPOOL
-1];
92 * Initialize the anchor.
94 anchor
.next
= anchor
.prev
= &anchor
;
96 anchor
.pos
= (POSITION
)0;
101 * Calculate the gap for an entry.
105 register struct linenum_info
*p
;
108 * Don't bother to compute a gap for the anchor.
109 * Also don't compute a gap for the last one in the list.
110 * The gap for that last one should be considered infinite,
111 * but we never look at it anyway.
113 if (p
== &anchor
|| p
->next
== &anchor
)
115 p
->gap
= p
->next
->pos
- p
->prev
->pos
;
119 * Add a new line number to the cache.
120 * The specified position (pos) should be the file position of the
121 * FIRST character in the specified line.
124 add_lnum(linenum
, pos
)
128 register struct linenum_info
*p
;
129 register struct linenum_info
*new;
130 register struct linenum_info
*nextp
;
131 register struct linenum_info
*prevp
;
132 register POSITION mingap
;
135 * Find the proper place in the list for the new one.
136 * The entries are sorted by position.
138 for (p
= anchor
.next
; p
!= &anchor
&& p
->pos
< pos
; p
= p
->next
)
139 if (p
->line
== linenum
)
140 /* We already have this one. */
145 if (freelist
!= NULL
)
148 * We still have free (unused) entries.
152 freelist
= freelist
->next
;
157 * Use the "spare" entry.
164 * Fill in the fields of the new entry,
165 * and insert it into the proper place in the list.
176 * Recalculate gaps for the new entry and the neighboring entries.
185 * We have used the spare entry.
186 * Scan the list to find the one with the smallest
187 * gap, take it out and make it the spare.
188 * We should never remove the last one, so stop when
189 * we get to p->next == &anchor. This also avoids
190 * looking at the gap of the last one, which is
191 * not computed by calcgap.
193 mingap
= anchor
.next
->gap
;
194 for (p
= anchor
.next
; p
->next
!= &anchor
; p
= p
->next
)
196 if (p
->gap
<= mingap
)
202 spare
->next
->prev
= spare
->prev
;
203 spare
->prev
->next
= spare
->next
;
208 * If we get stuck in a long loop trying to figure out the
209 * line number, print a message to tell the user what we're doing.
214 ierror("Calculating line numbers", NULL_PARG
);
217 static int loopcount
;
219 static time_type startime
;
226 if (loopcount
>= 0 && ++loopcount
> 100)
229 if (get_time() >= startime
+ LONGTIME
)
236 if (loopcount
>= 0 && ++loopcount
> LONGLOOP
)
245 * Turn off line numbers because the user has interrupted
246 * a lengthy line number calculation.
251 if (linenums
== OPT_ONPLUS
)
253 * We were displaying line numbers, so need to repaint.
257 error("Line numbers turned off", NULL_PARG
);
261 * Find the line number associated with a given position.
262 * Return 0 if we can't figure it out.
268 register struct linenum_info
*p
;
269 register LINENUM linenum
;
274 * We're not using line numbers.
277 if (pos
== NULL_POSITION
)
279 * Caller doesn't know what he's talking about.
282 if (pos
<= ch_zero())
284 * Beginning of file is always line number 1.
289 * Find the entry nearest to the position we want.
291 for (p
= anchor
.next
; p
!= &anchor
&& p
->pos
< pos
; p
= p
->next
)
294 /* Found it exactly. */
298 * This is the (possibly) time-consuming part.
299 * We start at the line we just found and start
300 * reading the file forward or backward till we
301 * get to the place we want.
303 * First decide whether we should go forward from the
304 * previous one or backwards from the next one.
305 * The decision is based on which way involves
306 * traversing fewer bytes in the file.
309 startime
= get_time();
311 if (p
== &anchor
|| pos
- p
->prev
->pos
< p
->pos
- pos
)
320 for (linenum
= p
->line
, cpos
= p
->pos
; cpos
< pos
; linenum
++)
323 * Allow a signal to abort this loop.
325 cpos
= forw_raw_line(cpos
, (char **)NULL
, (int *)NULL
);
330 if (cpos
== NULL_POSITION
)
335 * We might as well cache it.
337 add_lnum(linenum
, cpos
);
339 * If the given position is not at the start of a line,
340 * make sure we return the correct line number.
352 for (linenum
= p
->line
, cpos
= p
->pos
; cpos
> pos
; linenum
--)
355 * Allow a signal to abort this loop.
357 cpos
= back_raw_line(cpos
, (char **)NULL
, (int *)NULL
);
362 if (cpos
== NULL_POSITION
)
367 * We might as well cache it.
369 add_lnum(linenum
, cpos
);
376 * Find the position of a given line number.
377 * Return NULL_POSITION if we can't figure it out.
383 register struct linenum_info
*p
;
389 * Line number 1 is beginning of file.
394 * Find the entry nearest to the line number we want.
396 for (p
= anchor
.next
; p
!= &anchor
&& p
->line
< linenum
; p
= p
->next
)
398 if (p
->line
== linenum
)
399 /* Found it exactly. */
402 if (p
== &anchor
|| linenum
- p
->prev
->line
< p
->line
- linenum
)
409 return (NULL_POSITION
);
410 for (clinenum
= p
->line
, cpos
= p
->pos
; clinenum
< linenum
; clinenum
++)
413 * Allow a signal to abort this loop.
415 cpos
= forw_raw_line(cpos
, (char **)NULL
, (int *)NULL
);
417 return (NULL_POSITION
);
418 if (cpos
== NULL_POSITION
)
419 return (NULL_POSITION
);
427 return (NULL_POSITION
);
428 for (clinenum
= p
->line
, cpos
= p
->pos
; clinenum
> linenum
; clinenum
--)
431 * Allow a signal to abort this loop.
433 cpos
= back_raw_line(cpos
, (char **)NULL
, (int *)NULL
);
435 return (NULL_POSITION
);
436 if (cpos
== NULL_POSITION
)
437 return (NULL_POSITION
);
441 * We might as well cache it.
443 add_lnum(clinenum
, cpos
);
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).
460 pos
= position(where
);
462 while (pos
== NULL_POSITION
&& where
>= 0 && where
< sc_height
)
463 pos
= position(++where
);
464 if (pos
== NULL_POSITION
)
466 linenum
= find_linenum(pos
);