1 /*
2 * Copyright (c) 1988 Mark Nudleman
3 * Copyright (c) 1988, 1993
4 * The Regents of the University of California. All rights reserved.
5 *
6 * %sccs.include.redist.c%
7 */
8
9 #ifndef lint
10 static char sccsid[] = "@(#)linenum.c 8.1 (Berkeley) 06/06/93";
11 #endif /* not lint */
12
13 /*
14 * Code to handle displaying line numbers.
15 *
16 * Finding the line number of a given file position is rather tricky.
17 * We don't want to just start at the beginning of the file and
18 * count newlines, because that is slow for large files (and also
19 * wouldn't work if we couldn't get to the start of the file; e.g.
20 * if input is a long pipe).
21 *
22 * So we use the function add_lnum to cache line numbers.
23 * We try to be very clever and keep only the more interesting
24 * line numbers when we run out of space in our table. A line
25 * number is more interesting than another when it is far from
26 * other line numbers. For example, we'd rather keep lines
27 * 100,200,300 than 100,101,300. 200 is more interesting than
28 * 101 because 101 can be derived very cheaply from 100, while
29 * 200 is more expensive to derive from 100.
30 *
31 * The function currline() returns the line number of a given
32 * position in the file. As a side effect, it calls add_lnum
33 * to cache the line number. Therefore currline is occasionally
34 * called to make sure we cache line numbers often enough.
35 */
36
37 #include <sys/types.h>
38 #include <stdio.h>
39 #include <less.h>
40
41 /*
42 * Structure to keep track of a line number and the associated file position.
43 * A doubly-linked circular list of line numbers is kept ordered by line number.
44 */
45 struct linenum
46 {
47 struct linenum *next; /* Link to next in the list */
48 struct linenum *prev; /* Line to previous in the list */
49 off_t pos; /* File position */
50 off_t gap; /* Gap between prev and next */
51 int 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 50 /* Size of line number pool */
63
64 #define LONGTIME (2) /* In seconds */
65
66 int lnloop = 0; /* Are we in the line num loop? */
67
68 static struct linenum anchor; /* Anchor of the list */
69 static struct linenum *freelist; /* Anchor of the unused entries */
70 static struct linenum pool[NPOOL]; /* The pool itself */
71 static struct linenum *spare; /* We always keep one spare entry */
72
73 extern int linenums;
74 extern int sigs;
75
76 /*
77 * Initialize the line number structures.
78 */
clr_linenum()79 clr_linenum()
80 {
81 register struct linenum *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 = (off_t)0;
100 anchor.line = 1;
101 }
102
103 /*
104 * Calculate the gap for an entry.
105 */
106 static
calcgap(p)107 calcgap(p)
108 register struct linenum *p;
109 {
110 /*
111 * Don't bother to compute a gap for the anchor.
112 * Also don't compute a gap for the last one in the list.
113 * The gap for that last one should be considered infinite,
114 * but we never look at it anyway.
115 */
116 if (p == &anchor || p->next == &anchor)
117 return;
118 p->gap = p->next->pos - p->prev->pos;
119 }
120
121 /*
122 * Add a new line number to the cache.
123 * The specified position (pos) should be the file position of the
124 * FIRST character in the specified line.
125 */
add_lnum(line,pos)126 add_lnum(line, pos)
127 int line;
128 off_t pos;
129 {
130 register struct linenum *p;
131 register struct linenum *new;
132 register struct linenum *nextp;
133 register struct linenum *prevp;
134 register off_t mingap;
135
136 /*
137 * Find the proper place in the list for the new one.
138 * The entries are sorted by position.
139 */
140 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
141 if (p->line == line)
142 /* We already have this one. */
143 return;
144 nextp = p;
145 prevp = p->prev;
146
147 if (freelist != NULL)
148 {
149 /*
150 * We still have free (unused) entries.
151 * Use one of them.
152 */
153 new = freelist;
154 freelist = freelist->next;
155 } else
156 {
157 /*
158 * No free entries.
159 * Use the "spare" entry.
160 */
161 new = spare;
162 spare = NULL;
163 }
164
165 /*
166 * Fill in the fields of the new entry,
167 * and insert it into the proper place in the list.
168 */
169 new->next = nextp;
170 new->prev = prevp;
171 new->pos = pos;
172 new->line = line;
173
174 nextp->prev = new;
175 prevp->next = new;
176
177 /*
178 * Recalculate gaps for the new entry and the neighboring entries.
179 */
180 calcgap(new);
181 calcgap(nextp);
182 calcgap(prevp);
183
184 if (spare == NULL)
185 {
186 /*
187 * We have used the spare entry.
188 * Scan the list to find the one with the smallest
189 * gap, take it out and make it the spare.
190 * We should never remove the last one, so stop when
191 * we get to p->next == &anchor. This also avoids
192 * looking at the gap of the last one, which is
193 * not computed by calcgap.
194 */
195 mingap = anchor.next->gap;
196 for (p = anchor.next; p->next != &anchor; p = p->next)
197 {
198 if (p->gap <= mingap)
199 {
200 spare = p;
201 mingap = p->gap;
202 }
203 }
204 spare->next->prev = spare->prev;
205 spare->prev->next = spare->next;
206 }
207 }
208
209 /*
210 * If we get stuck in a long loop trying to figure out the
211 * line number, print a message to tell the user what we're doing.
212 */
213 static
longloopmessage()214 longloopmessage()
215 {
216 ierror("Calculating line numbers");
217 /*
218 * Set the lnloop flag here, so if the user interrupts while
219 * we are calculating line numbers, the signal handler will
220 * turn off line numbers (linenums=0).
221 */
222 lnloop = 1;
223 }
224
225 /*
226 * Find the line number associated with a given position.
227 * Return 0 if we can't figure it out.
228 */
find_linenum(pos)229 find_linenum(pos)
230 off_t pos;
231 {
232 register struct linenum *p;
233 register int lno;
234 register int loopcount;
235 off_t cpos, back_raw_line(), forw_raw_line();
236 time_t startime, time();
237
238 if (!linenums)
239 /*
240 * We're not using line numbers.
241 */
242 return (0);
243 if (pos == NULL_POSITION)
244 /*
245 * Caller doesn't know what he's talking about.
246 */
247 return (0);
248 if (pos == (off_t)0)
249 /*
250 * Beginning of file is always line number 1.
251 */
252 return (1);
253
254 /*
255 * Find the entry nearest to the position we want.
256 */
257 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
258 continue;
259 if (p->pos == pos)
260 /* Found it exactly. */
261 return (p->line);
262
263 /*
264 * This is the (possibly) time-consuming part.
265 * We start at the line we just found and start
266 * reading the file forward or backward till we
267 * get to the place we want.
268 *
269 * First decide whether we should go forward from the
270 * previous one or backwards from the next one.
271 * The decision is based on which way involves
272 * traversing fewer bytes in the file.
273 */
274 flush();
275 (void)time(&startime);
276 if (p == &anchor || pos - p->prev->pos < p->pos - pos)
277 {
278 /*
279 * Go forward.
280 */
281 p = p->prev;
282 if (ch_seek(p->pos))
283 return (0);
284 loopcount = 0;
285 for (lno = p->line, cpos = p->pos; cpos < pos; lno++)
286 {
287 /*
288 * Allow a signal to abort this loop.
289 */
290 cpos = forw_raw_line(cpos);
291 if (sigs || cpos == NULL_POSITION)
292 return (0);
293 if (loopcount >= 0 && ++loopcount > 100) {
294 loopcount = 0;
295 if (time((time_t *)NULL)
296 >= startime + LONGTIME) {
297 longloopmessage();
298 loopcount = -1;
299 }
300 }
301 }
302 lnloop = 0;
303 /*
304 * If the given position is not at the start of a line,
305 * make sure we return the correct line number.
306 */
307 if (cpos > pos)
308 lno--;
309 } else
310 {
311 /*
312 * Go backward.
313 */
314 if (ch_seek(p->pos))
315 return (0);
316 loopcount = 0;
317 for (lno = p->line, cpos = p->pos; cpos > pos; lno--)
318 {
319 /*
320 * Allow a signal to abort this loop.
321 */
322 cpos = back_raw_line(cpos);
323 if (sigs || cpos == NULL_POSITION)
324 return (0);
325 if (loopcount >= 0 && ++loopcount > 100) {
326 loopcount = 0;
327 if (time((time_t *)NULL)
328 >= startime + LONGTIME) {
329 longloopmessage();
330 loopcount = -1;
331 }
332 }
333 }
334 lnloop = 0;
335 }
336
337 /*
338 * We might as well cache it.
339 */
340 add_lnum(lno, cpos);
341 return (lno);
342 }
343
344 /*
345 * Return the line number of the "current" line.
346 * The argument "where" tells which line is to be considered
347 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
348 */
currline(where)349 currline(where)
350 int where;
351 {
352 off_t pos, ch_length(), position();
353
354 if ((pos = position(where)) == NULL_POSITION)
355 pos = ch_length();
356 return(find_linenum(pos));
357 }
358