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