1238730Sdelphij/* 2330571Sdelphij * Copyright (C) 1984-2017 Mark Nudelman 3238730Sdelphij * 4238730Sdelphij * You may distribute under the terms of either the GNU General Public 5238730Sdelphij * License or the Less License, as specified in the README file. 6238730Sdelphij * 7238730Sdelphij * For more information, see the README file. 8238730Sdelphij */ 960786Sps 1060786Sps 1160786Sps/* 1260786Sps * Code to handle displaying line numbers. 1360786Sps * 1460786Sps * Finding the line number of a given file position is rather tricky. 1560786Sps * We don't want to just start at the beginning of the file and 1660786Sps * count newlines, because that is slow for large files (and also 1760786Sps * wouldn't work if we couldn't get to the start of the file; e.g. 1860786Sps * if input is a long pipe). 1960786Sps * 2060786Sps * So we use the function add_lnum to cache line numbers. 2160786Sps * We try to be very clever and keep only the more interesting 2260786Sps * line numbers when we run out of space in our table. A line 2360786Sps * number is more interesting than another when it is far from 2460786Sps * other line numbers. For example, we'd rather keep lines 2560786Sps * 100,200,300 than 100,101,300. 200 is more interesting than 2660786Sps * 101 because 101 can be derived very cheaply from 100, while 2760786Sps * 200 is more expensive to derive from 100. 2860786Sps * 2960786Sps * The function currline() returns the line number of a given 3060786Sps * position in the file. As a side effect, it calls add_lnum 3160786Sps * to cache the line number. Therefore currline is occasionally 3260786Sps * called to make sure we cache line numbers often enough. 3360786Sps */ 3460786Sps 3560786Sps#include "less.h" 3660786Sps 3760786Sps/* 3860786Sps * Structure to keep track of a line number and the associated file position. 3960786Sps * A doubly-linked circular list of line numbers is kept ordered by line number. 4060786Sps */ 41128345Stjrstruct linenum_info 4260786Sps{ 43128345Stjr struct linenum_info *next; /* Link to next in the list */ 44128345Stjr struct linenum_info *prev; /* Line to previous in the list */ 4560786Sps POSITION pos; /* File position */ 4660786Sps POSITION gap; /* Gap between prev and next */ 47128345Stjr LINENUM line; /* Line number */ 4860786Sps}; 4960786Sps/* 5060786Sps * "gap" needs some explanation: the gap of any particular line number 5160786Sps * is the distance between the previous one and the next one in the list. 5260786Sps * ("Distance" means difference in file position.) In other words, the 5360786Sps * gap of a line number is the gap which would be introduced if this 5460786Sps * line number were deleted. It is used to decide which one to replace 5560786Sps * when we have a new one to insert and the table is full. 5660786Sps */ 5760786Sps 58191930Sdelphij#define NPOOL 200 /* Size of line number pool */ 5960786Sps 6060786Sps#define LONGTIME (2) /* In seconds */ 6160786Sps 62128345Stjrstatic struct linenum_info anchor; /* Anchor of the list */ 63128345Stjrstatic struct linenum_info *freelist; /* Anchor of the unused entries */ 64128345Stjrstatic struct linenum_info pool[NPOOL]; /* The pool itself */ 65128345Stjrstatic struct linenum_info *spare; /* We always keep one spare entry */ 6660786Sps 6760786Spsextern int linenums; 6860786Spsextern int sigs; 6960786Spsextern int sc_height; 70191930Sdelphijextern int screen_trashed; 7160786Sps 7260786Sps/* 7360786Sps * Initialize the line number structures. 7460786Sps */ 7560786Sps public void 7660786Spsclr_linenum() 7760786Sps{ 78330571Sdelphij struct linenum_info *p; 7960786Sps 8060786Sps /* 8160786Sps * Put all the entries on the free list. 8260786Sps * Leave one for the "spare". 8360786Sps */ 8460786Sps for (p = pool; p < &pool[NPOOL-2]; p++) 8560786Sps p->next = p+1; 8660786Sps pool[NPOOL-2].next = NULL; 8760786Sps freelist = pool; 8860786Sps 8960786Sps spare = &pool[NPOOL-1]; 9060786Sps 9160786Sps /* 9260786Sps * Initialize the anchor. 9360786Sps */ 9460786Sps anchor.next = anchor.prev = &anchor; 9560786Sps anchor.gap = 0; 9660786Sps anchor.pos = (POSITION)0; 9760786Sps anchor.line = 1; 9860786Sps} 9960786Sps 10060786Sps/* 10160786Sps * Calculate the gap for an entry. 10260786Sps */ 10360786Sps static void 10460786Spscalcgap(p) 105330571Sdelphij struct linenum_info *p; 10660786Sps{ 10760786Sps /* 10860786Sps * Don't bother to compute a gap for the anchor. 10960786Sps * Also don't compute a gap for the last one in the list. 11060786Sps * The gap for that last one should be considered infinite, 11160786Sps * but we never look at it anyway. 11260786Sps */ 11360786Sps if (p == &anchor || p->next == &anchor) 11460786Sps return; 11560786Sps p->gap = p->next->pos - p->prev->pos; 11660786Sps} 11760786Sps 11860786Sps/* 11960786Sps * Add a new line number to the cache. 12060786Sps * The specified position (pos) should be the file position of the 12160786Sps * FIRST character in the specified line. 12260786Sps */ 12360786Sps public void 124128345Stjradd_lnum(linenum, pos) 125128345Stjr LINENUM linenum; 12660786Sps POSITION pos; 12760786Sps{ 128330571Sdelphij struct linenum_info *p; 129330571Sdelphij struct linenum_info *new; 130330571Sdelphij struct linenum_info *nextp; 131330571Sdelphij struct linenum_info *prevp; 132330571Sdelphij POSITION mingap; 13360786Sps 13460786Sps /* 13560786Sps * Find the proper place in the list for the new one. 13660786Sps * The entries are sorted by position. 13760786Sps */ 13860786Sps for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 139128345Stjr if (p->line == linenum) 14060786Sps /* We already have this one. */ 14160786Sps return; 14260786Sps nextp = p; 14360786Sps prevp = p->prev; 14460786Sps 14560786Sps if (freelist != NULL) 14660786Sps { 14760786Sps /* 14860786Sps * We still have free (unused) entries. 14960786Sps * Use one of them. 15060786Sps */ 15160786Sps new = freelist; 15260786Sps freelist = freelist->next; 15360786Sps } else 15460786Sps { 15560786Sps /* 15660786Sps * No free entries. 15760786Sps * Use the "spare" entry. 15860786Sps */ 15960786Sps new = spare; 16060786Sps spare = NULL; 16160786Sps } 16260786Sps 16360786Sps /* 16460786Sps * Fill in the fields of the new entry, 16560786Sps * and insert it into the proper place in the list. 16660786Sps */ 16760786Sps new->next = nextp; 16860786Sps new->prev = prevp; 16960786Sps new->pos = pos; 170128345Stjr new->line = linenum; 17160786Sps 17260786Sps nextp->prev = new; 17360786Sps prevp->next = new; 17460786Sps 17560786Sps /* 17660786Sps * Recalculate gaps for the new entry and the neighboring entries. 17760786Sps */ 17860786Sps calcgap(new); 17960786Sps calcgap(nextp); 18060786Sps calcgap(prevp); 18160786Sps 18260786Sps if (spare == NULL) 18360786Sps { 18460786Sps /* 18560786Sps * We have used the spare entry. 18660786Sps * Scan the list to find the one with the smallest 18760786Sps * gap, take it out and make it the spare. 18860786Sps * We should never remove the last one, so stop when 18960786Sps * we get to p->next == &anchor. This also avoids 19060786Sps * looking at the gap of the last one, which is 19160786Sps * not computed by calcgap. 19260786Sps */ 19360786Sps mingap = anchor.next->gap; 19460786Sps for (p = anchor.next; p->next != &anchor; p = p->next) 19560786Sps { 19660786Sps if (p->gap <= mingap) 19760786Sps { 19860786Sps spare = p; 19960786Sps mingap = p->gap; 20060786Sps } 20160786Sps } 20260786Sps spare->next->prev = spare->prev; 20360786Sps spare->prev->next = spare->next; 20460786Sps } 20560786Sps} 20660786Sps 20760786Sps/* 20860786Sps * If we get stuck in a long loop trying to figure out the 20960786Sps * line number, print a message to tell the user what we're doing. 21060786Sps */ 21160786Sps static void 21260786Spslongloopmessage() 21360786Sps{ 21460786Sps ierror("Calculating line numbers", NULL_PARG); 21560786Sps} 21660786Sps 21760786Spsstatic int loopcount; 21860786Sps#if HAVE_TIME 219294286Sdelphijstatic time_type startime; 22060786Sps#endif 22160786Sps 22260786Sps static void 22360786Spslongish() 22460786Sps{ 22560786Sps#if HAVE_TIME 22660786Sps if (loopcount >= 0 && ++loopcount > 100) 22760786Sps { 22860786Sps loopcount = 0; 22960786Sps if (get_time() >= startime + LONGTIME) 23060786Sps { 23160786Sps longloopmessage(); 23260786Sps loopcount = -1; 23360786Sps } 23460786Sps } 23560786Sps#else 23660786Sps if (loopcount >= 0 && ++loopcount > LONGLOOP) 23760786Sps { 23860786Sps longloopmessage(); 23960786Sps loopcount = -1; 24060786Sps } 24160786Sps#endif 24260786Sps} 24360786Sps 24460786Sps/* 245191930Sdelphij * Turn off line numbers because the user has interrupted 246191930Sdelphij * a lengthy line number calculation. 247191930Sdelphij */ 248191930Sdelphij static void 249191930Sdelphijabort_long() 250191930Sdelphij{ 251191930Sdelphij if (linenums == OPT_ONPLUS) 252191930Sdelphij /* 253191930Sdelphij * We were displaying line numbers, so need to repaint. 254191930Sdelphij */ 255191930Sdelphij screen_trashed = 1; 256191930Sdelphij linenums = 0; 257191930Sdelphij error("Line numbers turned off", NULL_PARG); 258191930Sdelphij} 259191930Sdelphij 260191930Sdelphij/* 26160786Sps * Find the line number associated with a given position. 26260786Sps * Return 0 if we can't figure it out. 26360786Sps */ 264128345Stjr public LINENUM 26560786Spsfind_linenum(pos) 26660786Sps POSITION pos; 26760786Sps{ 268330571Sdelphij struct linenum_info *p; 269330571Sdelphij LINENUM linenum; 27060786Sps POSITION cpos; 27160786Sps 27260786Sps if (!linenums) 27360786Sps /* 27460786Sps * We're not using line numbers. 27560786Sps */ 27660786Sps return (0); 27760786Sps if (pos == NULL_POSITION) 27860786Sps /* 27960786Sps * Caller doesn't know what he's talking about. 28060786Sps */ 28160786Sps return (0); 28260786Sps if (pos <= ch_zero()) 28360786Sps /* 28460786Sps * Beginning of file is always line number 1. 28560786Sps */ 28660786Sps return (1); 28760786Sps 28860786Sps /* 28960786Sps * Find the entry nearest to the position we want. 29060786Sps */ 29160786Sps for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 29260786Sps continue; 29360786Sps if (p->pos == pos) 29460786Sps /* Found it exactly. */ 29560786Sps return (p->line); 29660786Sps 29760786Sps /* 29860786Sps * This is the (possibly) time-consuming part. 29960786Sps * We start at the line we just found and start 30060786Sps * reading the file forward or backward till we 30160786Sps * get to the place we want. 30260786Sps * 30360786Sps * First decide whether we should go forward from the 30460786Sps * previous one or backwards from the next one. 30560786Sps * The decision is based on which way involves 30660786Sps * traversing fewer bytes in the file. 30760786Sps */ 30860786Sps#if HAVE_TIME 30960786Sps startime = get_time(); 31060786Sps#endif 31160786Sps if (p == &anchor || pos - p->prev->pos < p->pos - pos) 31260786Sps { 31360786Sps /* 31460786Sps * Go forward. 31560786Sps */ 31660786Sps p = p->prev; 31760786Sps if (ch_seek(p->pos)) 31860786Sps return (0); 31960786Sps loopcount = 0; 320128345Stjr for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) 32160786Sps { 32260786Sps /* 32360786Sps * Allow a signal to abort this loop. 32460786Sps */ 325170256Sdelphij cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL); 326191930Sdelphij if (ABORT_SIGS()) { 327191930Sdelphij abort_long(); 32860786Sps return (0); 329191930Sdelphij } 330191930Sdelphij if (cpos == NULL_POSITION) 331191930Sdelphij return (0); 33260786Sps longish(); 33360786Sps } 33460786Sps /* 33560786Sps * We might as well cache it. 33660786Sps */ 337128345Stjr add_lnum(linenum, cpos); 33860786Sps /* 33960786Sps * If the given position is not at the start of a line, 34060786Sps * make sure we return the correct line number. 34160786Sps */ 34260786Sps if (cpos > pos) 343128345Stjr linenum--; 34460786Sps } else 34560786Sps { 34660786Sps /* 34760786Sps * Go backward. 34860786Sps */ 34960786Sps if (ch_seek(p->pos)) 35060786Sps return (0); 35160786Sps loopcount = 0; 352128345Stjr for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) 35360786Sps { 35460786Sps /* 35560786Sps * Allow a signal to abort this loop. 35660786Sps */ 357170256Sdelphij cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL); 358191930Sdelphij if (ABORT_SIGS()) { 359191930Sdelphij abort_long(); 36060786Sps return (0); 361191930Sdelphij } 362191930Sdelphij if (cpos == NULL_POSITION) 363191930Sdelphij return (0); 36460786Sps longish(); 36560786Sps } 36660786Sps /* 36760786Sps * We might as well cache it. 36860786Sps */ 369128345Stjr add_lnum(linenum, cpos); 37060786Sps } 37160786Sps 372128345Stjr return (linenum); 37360786Sps} 37460786Sps 37560786Sps/* 37660786Sps * Find the position of a given line number. 37760786Sps * Return NULL_POSITION if we can't figure it out. 37860786Sps */ 37960786Sps public POSITION 380128345Stjrfind_pos(linenum) 381128345Stjr LINENUM linenum; 38260786Sps{ 383330571Sdelphij struct linenum_info *p; 38460786Sps POSITION cpos; 385128345Stjr LINENUM clinenum; 38660786Sps 387128345Stjr if (linenum <= 1) 38860786Sps /* 38960786Sps * Line number 1 is beginning of file. 39060786Sps */ 39160786Sps return (ch_zero()); 39260786Sps 39360786Sps /* 39460786Sps * Find the entry nearest to the line number we want. 39560786Sps */ 396128345Stjr for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next) 39760786Sps continue; 398128345Stjr if (p->line == linenum) 39960786Sps /* Found it exactly. */ 40060786Sps return (p->pos); 40160786Sps 402128345Stjr if (p == &anchor || linenum - p->prev->line < p->line - linenum) 40360786Sps { 40460786Sps /* 40560786Sps * Go forward. 40660786Sps */ 40760786Sps p = p->prev; 40860786Sps if (ch_seek(p->pos)) 40960786Sps return (NULL_POSITION); 410128345Stjr for (clinenum = p->line, cpos = p->pos; clinenum < linenum; clinenum++) 41160786Sps { 41260786Sps /* 41360786Sps * Allow a signal to abort this loop. 41460786Sps */ 415170256Sdelphij cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL); 416191930Sdelphij if (ABORT_SIGS()) 41760786Sps return (NULL_POSITION); 418191930Sdelphij if (cpos == NULL_POSITION) 419191930Sdelphij return (NULL_POSITION); 42060786Sps } 42160786Sps } else 42260786Sps { 42360786Sps /* 42460786Sps * Go backward. 42560786Sps */ 42660786Sps if (ch_seek(p->pos)) 42760786Sps return (NULL_POSITION); 428128345Stjr for (clinenum = p->line, cpos = p->pos; clinenum > linenum; clinenum--) 42960786Sps { 43060786Sps /* 43160786Sps * Allow a signal to abort this loop. 43260786Sps */ 433170256Sdelphij cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL); 434191930Sdelphij if (ABORT_SIGS()) 43560786Sps return (NULL_POSITION); 436191930Sdelphij if (cpos == NULL_POSITION) 437191930Sdelphij return (NULL_POSITION); 43860786Sps } 43960786Sps } 44060786Sps /* 44160786Sps * We might as well cache it. 44260786Sps */ 443128345Stjr add_lnum(clinenum, cpos); 44460786Sps return (cpos); 44560786Sps} 44660786Sps 44760786Sps/* 44860786Sps * Return the line number of the "current" line. 44960786Sps * The argument "where" tells which line is to be considered 45060786Sps * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 45160786Sps */ 452128345Stjr public LINENUM 45360786Spscurrline(where) 45460786Sps int where; 45560786Sps{ 45660786Sps POSITION pos; 45760786Sps POSITION len; 458128345Stjr LINENUM linenum; 45960786Sps 46060786Sps pos = position(where); 46160786Sps len = ch_length(); 46260786Sps while (pos == NULL_POSITION && where >= 0 && where < sc_height) 46360786Sps pos = position(++where); 46460786Sps if (pos == NULL_POSITION) 46560786Sps pos = len; 466128345Stjr linenum = find_linenum(pos); 46760786Sps if (pos == len) 468128345Stjr linenum--; 469128345Stjr return (linenum); 47060786Sps} 471