linenum.c revision 89019
1214501Srpaulo/* 2214501Srpaulo * Copyright (C) 1984-2000 Mark Nudelman 3281806Srpaulo * 4214501Srpaulo * You may distribute under the terms of either the GNU General Public 5252726Srpaulo * License or the Less License, as specified in the README file. 6252726Srpaulo * 7214501Srpaulo * For more information about less, or for information on how to 8214501Srpaulo * contact the author, see the README file. 9214501Srpaulo */ 10214501Srpaulo 11214501Srpaulo 12281806Srpaulo/* 13214501Srpaulo * Code to handle displaying line numbers. 14214501Srpaulo * 15214501Srpaulo * Finding the line number of a given file position is rather tricky. 16214501Srpaulo * We don't want to just start at the beginning of the file and 17281806Srpaulo * count newlines, because that is slow for large files (and also 18346981Scy * wouldn't work if we couldn't get to the start of the file; e.g. 19252726Srpaulo * if input is a long pipe). 20252726Srpaulo * 21252726Srpaulo * So we use the function add_lnum to cache line numbers. 22289549Srpaulo * We try to be very clever and keep only the more interesting 23252726Srpaulo * line numbers when we run out of space in our table. A line 24214501Srpaulo * number is more interesting than another when it is far from 25214501Srpaulo * other line numbers. For example, we'd rather keep lines 26337817Scy * 100,200,300 than 100,101,300. 200 is more interesting than 27214501Srpaulo * 101 because 101 can be derived very cheaply from 100, while 28214501Srpaulo * 200 is more expensive to derive from 100. 29214501Srpaulo * 30214501Srpaulo * The function currline() returns the line number of a given 31214501Srpaulo * position in the file. As a side effect, it calls add_lnum 32214501Srpaulo * to cache the line number. Therefore currline is occasionally 33252726Srpaulo * called to make sure we cache line numbers often enough. 34214501Srpaulo */ 35346981Scy 36252726Srpaulo#include "less.h" 37281806Srpaulo 38281806Srpaulo/* 39337817Scy * Structure to keep track of a line number and the associated file position. 40346981Scy * A doubly-linked circular list of line numbers is kept ordered by line number. 41346981Scy */ 42346981Scystruct linenum 43214501Srpaulo{ 44214501Srpaulo struct linenum *next; /* Link to next in the list */ 45346981Scy struct linenum *prev; /* Line to previous in the list */ 46346981Scy POSITION pos; /* File position */ 47346981Scy POSITION gap; /* Gap between prev and next */ 48346981Scy int line; /* Line number */ 49346981Scy}; 50346981Scy/* 51346981Scy * "gap" needs some explanation: the gap of any particular line number 52346981Scy * is the distance between the previous one and the next one in the list. 53346981Scy * ("Distance" means difference in file position.) In other words, the 54346981Scy * gap of a line number is the gap which would be introduced if this 55346981Scy * line number were deleted. It is used to decide which one to replace 56346981Scy * when we have a new one to insert and the table is full. 57346981Scy */ 58346981Scy 59346981Scy#define NPOOL 50 /* Size of line number pool */ 60346981Scy 61346981Scy#define LONGTIME (2) /* In seconds */ 62346981Scy 63346981Scypublic int lnloop = 0; /* Are we in the line num loop? */ 64346981Scy 65346981Scystatic struct linenum anchor; /* Anchor of the list */ 66346981Scystatic struct linenum *freelist; /* Anchor of the unused entries */ 67346981Scystatic struct linenum pool[NPOOL]; /* The pool itself */ 68346981Scystatic struct linenum *spare; /* We always keep one spare entry */ 69346981Scy 70346981Scyextern int linenums; 71346981Scyextern int sigs; 72346981Scyextern int sc_height; 73346981Scy 74346981Scy/* 75346981Scy * Initialize the line number structures. 76346981Scy */ 77346981Scy public void 78346981Scyclr_linenum() 79346981Scy{ 80346981Scy register struct linenum *p; 81346981Scy 82346981Scy /* 83346981Scy * Put all the entries on the free list. 84346981Scy * Leave one for the "spare". 85346981Scy */ 86346981Scy for (p = pool; p < &pool[NPOOL-2]; p++) 87346981Scy p->next = p+1; 88346981Scy pool[NPOOL-2].next = NULL; 89346981Scy freelist = pool; 90346981Scy 91346981Scy spare = &pool[NPOOL-1]; 92346981Scy 93346981Scy /* 94346981Scy * Initialize the anchor. 95346981Scy */ 96346981Scy anchor.next = anchor.prev = &anchor; 97346981Scy anchor.gap = 0; 98346981Scy anchor.pos = (POSITION)0; 99346981Scy anchor.line = 1; 100346981Scy} 101346981Scy 102346981Scy/* 103346981Scy * Calculate the gap for an entry. 104346981Scy */ 105346981Scy static void 106214501Srpaulocalcgap(p) 107252726Srpaulo register struct linenum *p; 108214501Srpaulo{ 109214501Srpaulo /* 110214501Srpaulo * Don't bother to compute a gap for the anchor. 111214501Srpaulo * Also don't compute a gap for the last one in the list. 112252726Srpaulo * The gap for that last one should be considered infinite, 113252726Srpaulo * but we never look at it anyway. 114346981Scy */ 115252726Srpaulo if (p == &anchor || p->next == &anchor) 116252726Srpaulo return; 117346981Scy p->gap = p->next->pos - p->prev->pos; 118252726Srpaulo} 119252726Srpaulo 120281806Srpaulo/* 121214501Srpaulo * Add a new line number to the cache. 122214501Srpaulo * The specified position (pos) should be the file position of the 123214501Srpaulo * FIRST character in the specified line. 124214501Srpaulo */ 125214501Srpaulo public void 126214501Srpauloadd_lnum(lno, pos) 127214501Srpaulo int lno; 128214501Srpaulo POSITION pos; 129214501Srpaulo{ 130289549Srpaulo register struct linenum *p; 131289549Srpaulo register struct linenum *new; 132214501Srpaulo register struct linenum *nextp; 133214501Srpaulo register struct linenum *prevp; 134252726Srpaulo register POSITION mingap; 135214501Srpaulo 136214501Srpaulo /* 137214501Srpaulo * Find the proper place in the list for the new one. 138214501Srpaulo * The entries are sorted by position. 139252726Srpaulo */ 140214501Srpaulo for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 141214501Srpaulo if (p->line == lno) 142214501Srpaulo /* We already have this one. */ 143214501Srpaulo return; 144214501Srpaulo nextp = p; 145214501Srpaulo prevp = p->prev; 146214501Srpaulo 147214501Srpaulo if (freelist != NULL) 148214501Srpaulo { 149214501Srpaulo /* 150214501Srpaulo * We still have free (unused) entries. 151214501Srpaulo * Use one of them. 152281806Srpaulo */ 153281806Srpaulo new = freelist; 154281806Srpaulo freelist = freelist->next; 155281806Srpaulo } else 156281806Srpaulo { 157281806Srpaulo /* 158214501Srpaulo * No free entries. 159214501Srpaulo * Use the "spare" entry. 160214501Srpaulo */ 161289549Srpaulo new = spare; 162289549Srpaulo spare = NULL; 163214501Srpaulo } 164214501Srpaulo 165214501Srpaulo /* 166214501Srpaulo * Fill in the fields of the new entry, 167281806Srpaulo * and insert it into the proper place in the list. 168214501Srpaulo */ 169252726Srpaulo new->next = nextp; 170252726Srpaulo new->prev = prevp; 171252726Srpaulo new->pos = pos; 172252726Srpaulo new->line = lno; 173252726Srpaulo 174252726Srpaulo nextp->prev = new; 175214501Srpaulo prevp->next = new; 176214501Srpaulo 177252726Srpaulo /* 178252726Srpaulo * Recalculate gaps for the new entry and the neighboring entries. 179252726Srpaulo */ 180214501Srpaulo calcgap(new); 181252726Srpaulo calcgap(nextp); 182214501Srpaulo calcgap(prevp); 183252726Srpaulo 184214501Srpaulo if (spare == NULL) 185337817Scy { 186337817Scy /* 187337817Scy * We have used the spare entry. 188337817Scy * Scan the list to find the one with the smallest 189337817Scy * gap, take it out and make it the spare. 190337817Scy * We should never remove the last one, so stop when 191337817Scy * we get to p->next == &anchor. This also avoids 192337817Scy * looking at the gap of the last one, which is 193337817Scy * not computed by calcgap. 194337817Scy */ 195337817Scy mingap = anchor.next->gap; 196337817Scy for (p = anchor.next; p->next != &anchor; p = p->next) 197337817Scy { 198337817Scy if (p->gap <= mingap) 199337817Scy { 200252726Srpaulo spare = p; 201252726Srpaulo mingap = p->gap; 202252726Srpaulo } 203252726Srpaulo } 204252726Srpaulo spare->next->prev = spare->prev; 205281806Srpaulo spare->prev->next = spare->next; 206281806Srpaulo } 207252726Srpaulo} 208252726Srpaulo 209252726Srpaulo/* 210281806Srpaulo * If we get stuck in a long loop trying to figure out the 211281806Srpaulo * line number, print a message to tell the user what we're doing. 212281806Srpaulo */ 213281806Srpaulo static void 214281806Srpaulolongloopmessage() 215281806Srpaulo{ 216281806Srpaulo ierror("Calculating line numbers", NULL_PARG); 217281806Srpaulo /* 218281806Srpaulo * Set the lnloop flag here, so if the user interrupts while 219281806Srpaulo * we are calculating line numbers, the signal handler will 220281806Srpaulo * turn off line numbers (linenums=0). 221281806Srpaulo */ 222281806Srpaulo lnloop = 1; 223281806Srpaulo} 224281806Srpaulo 225281806Srpaulostatic int loopcount; 226281806Srpaulo#if HAVE_TIME 227281806Srpaulostatic long startime; 228281806Srpaulo#endif 229281806Srpaulo 230281806Srpaulo static void 231281806Srpaulolongish() 232281806Srpaulo{ 233252726Srpaulo#if HAVE_TIME 234252726Srpaulo if (loopcount >= 0 && ++loopcount > 100) 235252726Srpaulo { 236252726Srpaulo loopcount = 0; 237252726Srpaulo if (get_time() >= startime + LONGTIME) 238252726Srpaulo { 239252726Srpaulo longloopmessage(); 240346981Scy loopcount = -1; 241346981Scy } 242346981Scy } 243346981Scy#else 244346981Scy if (loopcount >= 0 && ++loopcount > LONGLOOP) 245346981Scy { 246346981Scy longloopmessage(); 247346981Scy loopcount = -1; 248252726Srpaulo } 249252726Srpaulo#endif 250289549Srpaulo} 251289549Srpaulo 252289549Srpaulo/* 253289549Srpaulo * Find the line number associated with a given position. 254289549Srpaulo * Return 0 if we can't figure it out. 255289549Srpaulo */ 256289549Srpaulo public int 257289549Srpaulofind_linenum(pos) 258337817Scy POSITION pos; 259337817Scy{ 260337817Scy register struct linenum *p; 261337817Scy register int lno; 262337817Scy POSITION cpos; 263214501Srpaulo 264214501Srpaulo if (!linenums) 265252726Srpaulo /* 266214501Srpaulo * We're not using line numbers. 267289549Srpaulo */ 268289549Srpaulo return (0); 269214501Srpaulo if (pos == NULL_POSITION) 270214501Srpaulo /* 271214501Srpaulo * Caller doesn't know what he's talking about. 272252726Srpaulo */ 273214501Srpaulo return (0); 274214501Srpaulo if (pos <= ch_zero()) 275346981Scy /* 276346981Scy * Beginning of file is always line number 1. 277346981Scy */ 278214501Srpaulo return (1); 279252726Srpaulo 280214501Srpaulo /* 281214501Srpaulo * Find the entry nearest to the position we want. 282252726Srpaulo */ 283289549Srpaulo for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 284214501Srpaulo continue; 285252726Srpaulo if (p->pos == pos) 286252726Srpaulo /* Found it exactly. */ 287252726Srpaulo return (p->line); 288252726Srpaulo 289289549Srpaulo /* 290289549Srpaulo * This is the (possibly) time-consuming part. 291252726Srpaulo * We start at the line we just found and start 292252726Srpaulo * reading the file forward or backward till we 293252726Srpaulo * get to the place we want. 294252726Srpaulo * 295214501Srpaulo * First decide whether we should go forward from the 296214501Srpaulo * previous one or backwards from the next one. 297252726Srpaulo * The decision is based on which way involves 298214501Srpaulo * traversing fewer bytes in the file. 299214501Srpaulo */ 300214501Srpaulo#if HAVE_TIME 301281806Srpaulo startime = get_time(); 302281806Srpaulo#endif 303214501Srpaulo if (p == &anchor || pos - p->prev->pos < p->pos - pos) 304289549Srpaulo { 305289549Srpaulo /* 306214501Srpaulo * Go forward. 307214501Srpaulo */ 308214501Srpaulo p = p->prev; 309346981Scy if (ch_seek(p->pos)) 310252726Srpaulo return (0); 311346981Scy loopcount = 0; 312346981Scy for (lno = p->line, cpos = p->pos; cpos < pos; lno++) 313214501Srpaulo { 314289549Srpaulo /* 315289549Srpaulo * Allow a signal to abort this loop. 316289549Srpaulo */ 317214501Srpaulo cpos = forw_raw_line(cpos, (char **)NULL); 318252726Srpaulo if (ABORT_SIGS() || cpos == NULL_POSITION) 319252726Srpaulo return (0); 320252726Srpaulo longish(); 321252726Srpaulo } 322252726Srpaulo lnloop = 0; 323252726Srpaulo /* 324252726Srpaulo * We might as well cache it. 325252726Srpaulo */ 326252726Srpaulo add_lnum(lno, cpos); 327252726Srpaulo /* 328214501Srpaulo * If the given position is not at the start of a line, 329252726Srpaulo * make sure we return the correct line number. 330252726Srpaulo */ 331252726Srpaulo if (cpos > pos) 332252726Srpaulo lno--; 333346981Scy } else 334346981Scy { 335252726Srpaulo /* 336214501Srpaulo * Go backward. 337252726Srpaulo */ 338252726Srpaulo if (ch_seek(p->pos)) 339252726Srpaulo return (0); 340252726Srpaulo loopcount = 0; 341252726Srpaulo for (lno = p->line, cpos = p->pos; cpos > pos; lno--) 342214501Srpaulo { 343252726Srpaulo /* 344346981Scy * Allow a signal to abort this loop. 345346981Scy */ 346346981Scy cpos = back_raw_line(cpos, (char **)NULL); 347252726Srpaulo if (ABORT_SIGS() || cpos == NULL_POSITION) 348252726Srpaulo return (0); 349346981Scy longish(); 350346981Scy } 351346981Scy lnloop = 0; 352252726Srpaulo /* 353252726Srpaulo * We might as well cache it. 354252726Srpaulo */ 355252726Srpaulo add_lnum(lno, cpos); 356252726Srpaulo } 357252726Srpaulo 358252726Srpaulo return (lno); 359252726Srpaulo} 360252726Srpaulo 361252726Srpaulo/* 362252726Srpaulo * Find the position of a given line number. 363252726Srpaulo * Return NULL_POSITION if we can't figure it out. 364252726Srpaulo */ 365252726Srpaulo public POSITION 366252726Srpaulofind_pos(lno) 367252726Srpaulo int lno; 368252726Srpaulo{ 369252726Srpaulo register struct linenum *p; 370252726Srpaulo POSITION cpos; 371252726Srpaulo int clno; 372252726Srpaulo 373252726Srpaulo if (lno <= 1) 374252726Srpaulo /* 375252726Srpaulo * Line number 1 is beginning of file. 376252726Srpaulo */ 377252726Srpaulo return (ch_zero()); 378346981Scy 379252726Srpaulo /* 380252726Srpaulo * Find the entry nearest to the line number we want. 381252726Srpaulo */ 382252726Srpaulo for (p = anchor.next; p != &anchor && p->line < lno; p = p->next) 383252726Srpaulo continue; 384252726Srpaulo if (p->line == lno) 385252726Srpaulo /* Found it exactly. */ 386252726Srpaulo return (p->pos); 387252726Srpaulo 388252726Srpaulo if (p == &anchor || lno - p->prev->line < p->line - lno) 389252726Srpaulo { 390252726Srpaulo /* 391252726Srpaulo * Go forward. 392346981Scy */ 393214501Srpaulo p = p->prev; 394252726Srpaulo if (ch_seek(p->pos)) 395252726Srpaulo return (NULL_POSITION); 396289549Srpaulo for (clno = p->line, cpos = p->pos; clno < lno; clno++) 397252726Srpaulo { 398252726Srpaulo /* 399252726Srpaulo * Allow a signal to abort this loop. 400252726Srpaulo */ 401252726Srpaulo cpos = forw_raw_line(cpos, (char **)NULL); 402252726Srpaulo if (ABORT_SIGS() || cpos == NULL_POSITION) 403252726Srpaulo return (NULL_POSITION); 404252726Srpaulo } 405252726Srpaulo } else 406252726Srpaulo { 407252726Srpaulo /* 408252726Srpaulo * Go backward. 409252726Srpaulo */ 410252726Srpaulo if (ch_seek(p->pos)) 411214501Srpaulo return (NULL_POSITION); 412252726Srpaulo for (clno = p->line, cpos = p->pos; clno > lno; clno--) 413289549Srpaulo { 414289549Srpaulo /* 415252726Srpaulo * Allow a signal to abort this loop. 416252726Srpaulo */ 417214501Srpaulo cpos = back_raw_line(cpos, (char **)NULL); 418214501Srpaulo if (ABORT_SIGS() || cpos == NULL_POSITION) 419252726Srpaulo return (NULL_POSITION); 420252726Srpaulo } 421281806Srpaulo } 422281806Srpaulo /* 423281806Srpaulo * We might as well cache it. 424281806Srpaulo */ 425281806Srpaulo add_lnum(clno, cpos); 426281806Srpaulo return (cpos); 427281806Srpaulo} 428281806Srpaulo 429281806Srpaulo/* 430281806Srpaulo * Return the line number of the "current" line. 431281806Srpaulo * The argument "where" tells which line is to be considered 432281806Srpaulo * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 433281806Srpaulo */ 434281806Srpaulo public int 435281806Srpaulocurrline(where) 436289549Srpaulo int where; 437289549Srpaulo{ 438281806Srpaulo POSITION pos; 439281806Srpaulo POSITION len; 440281806Srpaulo int lnum; 441281806Srpaulo 442281806Srpaulo pos = position(where); 443281806Srpaulo len = ch_length(); 444214501Srpaulo while (pos == NULL_POSITION && where >= 0 && where < sc_height) 445337817Scy pos = position(++where); 446337817Scy if (pos == NULL_POSITION) 447337817Scy pos = len; 448337817Scy lnum = find_linenum(pos); 449337817Scy if (pos == len) 450337817Scy lnum--; 451337817Scy return (lnum); 452337817Scy} 453337817Scy