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