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