Annotation of src/usr.bin/less/linenum.c, Revision 1.17
1.1 etheisen 1: /*
1.7 shadchin 2: * Copyright (C) 1984-2012 Mark Nudelman
1.10 nicm 3: * Modified for use with illumos by Garrett D'Amore.
4: * Copyright 2014 Garrett D'Amore <garrett@damore.org>
1.1 etheisen 5: *
1.4 millert 6: * You may distribute under the terms of either the GNU General Public
7: * License or the Less License, as specified in the README file.
1.1 etheisen 8: *
1.7 shadchin 9: * For more information, see the README file.
1.8 nicm 10: */
1.1 etheisen 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:
1.17 ! jca 36: #include <sys/time.h>
! 37:
! 38: #include <time.h>
! 39:
1.1 etheisen 40: #include "less.h"
41:
42: /*
43: * Structure to keep track of a line number and the associated file position.
44: * A doubly-linked circular list of line numbers is kept ordered by line number.
45: */
1.11 deraadt 46: struct linenum_info {
1.4 millert 47: struct linenum_info *next; /* Link to next in the list */
48: struct linenum_info *prev; /* Line to previous in the list */
1.8 nicm 49: off_t pos; /* File position */
50: off_t gap; /* Gap between prev and next */
1.14 mmcc 51: off_t line; /* Line number */
1.1 etheisen 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:
1.5 shadchin 62: #define NPOOL 200 /* Size of line number pool */
1.1 etheisen 63:
64: #define LONGTIME (2) /* In seconds */
65:
1.4 millert 66: static struct linenum_info anchor; /* Anchor of the list */
67: static struct linenum_info *freelist; /* Anchor of the unused entries */
68: static struct linenum_info pool[NPOOL]; /* The pool itself */
1.8 nicm 69: static struct linenum_info *spare; /* We always keep one spare entry */
1.1 etheisen 70:
71: extern int linenums;
1.6 millert 72: extern volatile sig_atomic_t sigs;
1.1 etheisen 73: extern int sc_height;
1.5 shadchin 74: extern int screen_trashed;
1.1 etheisen 75:
76: /*
77: * Initialize the line number structures.
78: */
1.8 nicm 79: void
80: clr_linenum(void)
1.1 etheisen 81: {
1.8 nicm 82: struct linenum_info *p;
1.1 etheisen 83:
84: /*
85: * Put all the entries on the free list.
86: * Leave one for the "spare".
87: */
1.15 deraadt 88: for (p = pool; p < &pool[NPOOL-2]; p++)
1.1 etheisen 89: p->next = p+1;
90: pool[NPOOL-2].next = NULL;
91: freelist = pool;
92:
93: spare = &pool[NPOOL-1];
94:
95: /*
96: * Initialize the anchor.
97: */
98: anchor.next = anchor.prev = &anchor;
99: anchor.gap = 0;
1.8 nicm 100: anchor.pos = 0;
1.1 etheisen 101: anchor.line = 1;
102: }
103:
104: /*
105: * Calculate the gap for an entry.
106: */
1.8 nicm 107: static void
108: calcgap(struct linenum_info *p)
1.1 etheisen 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: */
1.8 nicm 126: void
1.14 mmcc 127: add_lnum(off_t linenum, off_t pos)
1.1 etheisen 128: {
1.8 nicm 129: struct linenum_info *p;
130: struct linenum_info *new;
131: struct linenum_info *nextp;
132: struct linenum_info *prevp;
133: off_t mingap;
1.1 etheisen 134:
135: /*
136: * Find the proper place in the list for the new one.
137: * The entries are sorted by position.
138: */
1.15 deraadt 139: for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
1.4 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:
1.8 nicm 146: if (freelist != NULL) {
1.1 etheisen 147: /*
148: * We still have free (unused) entries.
149: * Use one of them.
150: */
151: new = freelist;
152: freelist = freelist->next;
1.8 nicm 153: } else {
1.1 etheisen 154: /*
155: * No free entries.
156: * Use the "spare" entry.
157: */
158: new = spare;
159: spare = NULL;
160: }
161:
162: /*
163: * Fill in the fields of the new entry,
164: * and insert it into the proper place in the list.
165: */
166: new->next = nextp;
167: new->prev = prevp;
168: new->pos = pos;
1.4 millert 169: new->line = linenum;
1.1 etheisen 170:
171: nextp->prev = new;
172: prevp->next = new;
173:
174: /*
175: * Recalculate gaps for the new entry and the neighboring entries.
176: */
177: calcgap(new);
178: calcgap(nextp);
179: calcgap(prevp);
180:
1.8 nicm 181: if (spare == NULL) {
1.1 etheisen 182: /*
183: * We have used the spare entry.
184: * Scan the list to find the one with the smallest
185: * gap, take it out and make it the spare.
186: * We should never remove the last one, so stop when
187: * we get to p->next == &anchor. This also avoids
188: * looking at the gap of the last one, which is
189: * not computed by calcgap.
190: */
191: mingap = anchor.next->gap;
1.15 deraadt 192: for (p = anchor.next; p->next != &anchor; p = p->next) {
1.8 nicm 193: if (p->gap <= mingap) {
1.1 etheisen 194: spare = p;
195: mingap = p->gap;
196: }
197: }
198: spare->next->prev = spare->prev;
199: spare->prev->next = spare->next;
200: }
201: }
202:
203: static int loopcount;
1.17 ! jca 204: static struct timespec timeout;
! 205:
! 206: static void
! 207: timeout_set(int seconds)
! 208: {
! 209: clock_gettime(CLOCK_MONOTONIC, &timeout);
! 210: timeout.tv_sec += seconds;
! 211: }
! 212:
! 213: static int
! 214: timeout_elapsed(void)
! 215: {
! 216: struct timespec now;
! 217:
! 218: clock_gettime(CLOCK_MONOTONIC, &now);
! 219: return timespeccmp(&now, &timeout, >=);
! 220: }
1.1 etheisen 221:
1.8 nicm 222: static void
223: longish(void)
1.1 etheisen 224: {
1.16 tedu 225: if (loopcount >= 0 && ++loopcount > 100) {
1.1 etheisen 226: loopcount = 0;
1.17 ! jca 227: if (timeout_elapsed()) {
1.13 mmcc 228: ierror("Calculating line numbers", NULL);
1.1 etheisen 229: loopcount = -1;
230: }
231: }
232: }
233:
234: /*
1.5 shadchin 235: * Turn off line numbers because the user has interrupted
236: * a lengthy line number calculation.
237: */
1.8 nicm 238: static void
239: abort_long(void)
1.5 shadchin 240: {
241: if (linenums == OPT_ONPLUS)
242: /*
243: * We were displaying line numbers, so need to repaint.
244: */
245: screen_trashed = 1;
246: linenums = 0;
1.12 deraadt 247: error("Line numbers turned off", NULL);
1.5 shadchin 248: }
249:
250: /*
1.1 etheisen 251: * Find the line number associated with a given position.
252: * Return 0 if we can't figure it out.
253: */
1.14 mmcc 254: off_t
1.8 nicm 255: find_linenum(off_t pos)
1.1 etheisen 256: {
1.8 nicm 257: struct linenum_info *p;
1.14 mmcc 258: off_t linenum;
1.8 nicm 259: off_t cpos;
1.1 etheisen 260:
261: if (!linenums)
262: /*
263: * We're not using line numbers.
264: */
265: return (0);
1.8 nicm 266: if (pos == -1)
1.1 etheisen 267: /*
268: * Caller doesn't know what he's talking about.
269: */
270: return (0);
271: if (pos <= ch_zero())
272: /*
273: * Beginning of file is always line number 1.
274: */
275: return (1);
276:
277: /*
278: * Find the entry nearest to the position we want.
279: */
1.15 deraadt 280: for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
1.1 etheisen 281: continue;
282: if (p->pos == pos)
283: /* Found it exactly. */
284: return (p->line);
285:
286: /*
287: * This is the (possibly) time-consuming part.
288: * We start at the line we just found and start
289: * reading the file forward or backward till we
290: * get to the place we want.
291: *
1.8 nicm 292: * First decide whether we should go forward from the
1.1 etheisen 293: * previous one or backwards from the next one.
1.8 nicm 294: * The decision is based on which way involves
1.1 etheisen 295: * traversing fewer bytes in the file.
296: */
1.17 ! jca 297: timeout_set(LONGTIME);
1.8 nicm 298: if (p == &anchor || pos - p->prev->pos < p->pos - pos) {
1.1 etheisen 299: /*
300: * Go forward.
301: */
302: p = p->prev;
303: if (ch_seek(p->pos))
304: return (0);
305: loopcount = 0;
1.8 nicm 306: for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) {
1.1 etheisen 307: /*
308: * Allow a signal to abort this loop.
309: */
1.8 nicm 310: cpos = forw_raw_line(cpos, NULL, NULL);
1.5 shadchin 311: if (ABORT_SIGS()) {
312: abort_long();
313: return (0);
314: }
1.8 nicm 315: if (cpos == -1)
1.1 etheisen 316: return (0);
317: longish();
318: }
319: /*
320: * We might as well cache it.
321: */
1.4 millert 322: add_lnum(linenum, cpos);
1.1 etheisen 323: /*
324: * If the given position is not at the start of a line,
325: * make sure we return the correct line number.
326: */
327: if (cpos > pos)
1.4 millert 328: linenum--;
1.8 nicm 329: } else {
1.1 etheisen 330: /*
331: * Go backward.
332: */
333: if (ch_seek(p->pos))
334: return (0);
335: loopcount = 0;
1.8 nicm 336: for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) {
1.1 etheisen 337: /*
338: * Allow a signal to abort this loop.
339: */
1.8 nicm 340: cpos = back_raw_line(cpos, NULL, NULL);
1.5 shadchin 341: if (ABORT_SIGS()) {
342: abort_long();
343: return (0);
344: }
1.8 nicm 345: if (cpos == -1)
1.1 etheisen 346: return (0);
347: longish();
348: }
349: /*
350: * We might as well cache it.
351: */
1.4 millert 352: add_lnum(linenum, cpos);
1.1 etheisen 353: }
354:
1.4 millert 355: return (linenum);
1.1 etheisen 356: }
357:
358: /*
359: * Find the position of a given line number.
1.8 nicm 360: * Return -1 if we can't figure it out.
1.1 etheisen 361: */
1.8 nicm 362: off_t
1.14 mmcc 363: find_pos(off_t linenum)
1.1 etheisen 364: {
1.8 nicm 365: struct linenum_info *p;
366: off_t cpos;
1.14 mmcc 367: off_t clinenum;
1.1 etheisen 368:
1.4 millert 369: if (linenum <= 1)
1.1 etheisen 370: /*
371: * Line number 1 is beginning of file.
372: */
373: return (ch_zero());
374:
375: /*
376: * Find the entry nearest to the line number we want.
377: */
1.15 deraadt 378: for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next)
1.1 etheisen 379: continue;
1.4 millert 380: if (p->line == linenum)
1.1 etheisen 381: /* Found it exactly. */
382: return (p->pos);
383:
1.8 nicm 384: if (p == &anchor || linenum - p->prev->line < p->line - linenum) {
1.1 etheisen 385: /*
386: * Go forward.
387: */
388: p = p->prev;
389: if (ch_seek(p->pos))
1.8 nicm 390: return (-1);
391: for (clinenum = p->line, cpos = p->pos;
392: clinenum < linenum;
393: clinenum++) {
1.1 etheisen 394: /*
395: * Allow a signal to abort this loop.
396: */
1.8 nicm 397: cpos = forw_raw_line(cpos, NULL, NULL);
1.5 shadchin 398: if (ABORT_SIGS())
1.8 nicm 399: return (-1);
400: if (cpos == -1)
401: return (-1);
1.1 etheisen 402: }
1.8 nicm 403: } else {
1.1 etheisen 404: /*
405: * Go backward.
406: */
407: if (ch_seek(p->pos))
1.8 nicm 408: return (-1);
409: for (clinenum = p->line, cpos = p->pos;
410: clinenum > linenum;
411: clinenum--) {
1.1 etheisen 412: /*
413: * Allow a signal to abort this loop.
414: */
1.5 shadchin 415: cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
416: if (ABORT_SIGS())
1.8 nicm 417: return (-1);
418: if (cpos == -1)
419: return (-1);
1.1 etheisen 420: }
421: }
422: /*
423: * We might as well cache it.
424: */
1.4 millert 425: add_lnum(clinenum, cpos);
1.1 etheisen 426: return (cpos);
427: }
428:
429: /*
430: * Return the line number of the "current" line.
431: * The argument "where" tells which line is to be considered
432: * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
433: */
1.14 mmcc 434: off_t
1.8 nicm 435: currline(int where)
1.1 etheisen 436: {
1.8 nicm 437: off_t pos;
438: off_t len;
1.14 mmcc 439: off_t linenum;
1.1 etheisen 440:
441: pos = position(where);
442: len = ch_length();
1.8 nicm 443: while (pos == -1 && where >= 0 && where < sc_height)
1.1 etheisen 444: pos = position(++where);
1.8 nicm 445: if (pos == -1)
1.1 etheisen 446: pos = len;
1.4 millert 447: linenum = find_linenum(pos);
1.1 etheisen 448: if (pos == len)
1.4 millert 449: linenum--;
450: return (linenum);
1.1 etheisen 451: }
![[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