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