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