Annotation of src/usr.bin/less/linenum.c, Revision 1.1
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: }
![[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