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