/* $NetBSD: linenum.c,v 1.5 2003/10/13 14:34:25 agc Exp $ */ /* * Copyright (c) 1988 Mark Nudelman * Copyright (c) 1988, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include <sys/cdefs.h> #ifndef lint #if 0 static char sccsid[] = "@(#)linenum.c 8.1 (Berkeley) 6/6/93"; #else __RCSID("$NetBSD: linenum.c,v 1.5 2003/10/13 14:34:25 agc Exp $"); #endif #endif /* not lint */ /* * Code to handle displaying line numbers. * * Finding the line number of a given file position is rather tricky. * We don't want to just start at the beginning of the file and * count newlines, because that is slow for large files (and also * wouldn't work if we couldn't get to the start of the file; e.g. * if input is a long pipe). * * So we use the function add_lnum to cache line numbers. * We try to be very clever and keep only the more interesting * line numbers when we run out of space in our table. A line * number is more interesting than another when it is far from * other line numbers. For example, we'd rather keep lines * 100,200,300 than 100,101,300. 200 is more interesting than * 101 because 101 can be derived very cheaply from 100, while * 200 is more expensive to derive from 100. * * The function currline() returns the line number of a given * position in the file. As a side effect, it calls add_lnum * to cache the line number. Therefore currline is occasionally * called to make sure we cache line numbers often enough. */ #include <sys/types.h> #include <stdio.h> #include <time.h> #include "less.h" #include "extern.h" /* * Structure to keep track of a line number and the associated file position. * A doubly-linked circular list of line numbers is kept ordered by line number. */ struct linenum { struct linenum *next; /* Link to next in the list */ struct linenum *prev; /* Line to previous in the list */ off_t pos; /* File position */ off_t gap; /* Gap between prev and next */ int line; /* Line number */ }; /* * "gap" needs some explanation: the gap of any particular line number * is the distance between the previous one and the next one in the list. * ("Distance" means difference in file position.) In other words, the * gap of a line number is the gap which would be introduced if this * line number were deleted. It is used to decide which one to replace * when we have a new one to insert and the table is full. */ #define NPOOL 50 /* Size of line number pool */ #define LONGTIME (2) /* In seconds */ int lnloop = 0; /* Are we in the line num loop? */ static struct linenum anchor; /* Anchor of the list */ static struct linenum *freelist; /* Anchor of the unused entries */ static struct linenum pool[NPOOL]; /* The pool itself */ static struct linenum *spare; /* We always keep one spare entry */ static void calcgap __P((struct linenum *)); static void longloopmessage __P((void)); /* * Initialize the line number structures. */ void clr_linenum() { struct linenum *p; /* * Put all the entries on the free list. * Leave one for the "spare". */ for (p = pool; p < &pool[NPOOL-2]; p++) p->next = p+1; pool[NPOOL-2].next = NULL; freelist = pool; spare = &pool[NPOOL-1]; /* * Initialize the anchor. */ anchor.next = anchor.prev = &anchor; anchor.gap = 0; anchor.pos = (off_t)0; anchor.line = 1; } /* * Calculate the gap for an entry. */ static void calcgap(p) struct linenum *p; { /* * Don't bother to compute a gap for the anchor. * Also don't compute a gap for the last one in the list. * The gap for that last one should be considered infinite, * but we never look at it anyway. */ if (p == &anchor || p->next == &anchor) return; p->gap = p->next->pos - p->prev->pos; } /* * Add a new line number to the cache. * The specified position (pos) should be the file position of the * FIRST character in the specified line. */ void add_lnum(line, pos) int line; off_t pos; { struct linenum *p; struct linenum *new; struct linenum *nextp; struct linenum *prevp; off_t mingap; /* * Find the proper place in the list for the new one. * The entries are sorted by position. */ for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) if (p->line == line) /* We already have this one. */ return; nextp = p; prevp = p->prev; if (freelist != NULL) { /* * We still have free (unused) entries. * Use one of them. */ new = freelist; freelist = freelist->next; } else { /* * No free entries. * Use the "spare" entry. */ new = spare; spare = NULL; } /* * Fill in the fields of the new entry, * and insert it into the proper place in the list. */ new->next = nextp; new->prev = prevp; new->pos = pos; new->line = line; nextp->prev = new; prevp->next = new; /* * Recalculate gaps for the new entry and the neighboring entries. */ calcgap(new); calcgap(nextp); calcgap(prevp); if (spare == NULL) { /* * We have used the spare entry. * Scan the list to find the one with the smallest * gap, take it out and make it the spare. * We should never remove the last one, so stop when * we get to p->next == &anchor. This also avoids * looking at the gap of the last one, which is * not computed by calcgap. */ mingap = anchor.next->gap; for (p = anchor.next; p->next != &anchor; p = p->next) { if (p->gap <= mingap) { spare = p; mingap = p->gap; } } spare->next->prev = spare->prev; spare->prev->next = spare->next; } } /* * If we get stuck in a long loop trying to figure out the * line number, print a message to tell the user what we're doing. */ static void longloopmessage() { ierror("Calculating line numbers"); /* * Set the lnloop flag here, so if the user interrupts while * we are calculating line numbers, the signal handler will * turn off line numbers (linenums=0). */ lnloop = 1; } /* * Find the line number associated with a given position. * Return 0 if we can't figure it out. */ int find_linenum(pos) off_t pos; { struct linenum *p; int lno; int loopcount; off_t cpos; time_t startime; if (!linenums) /* * We're not using line numbers. */ return (0); if (pos == NULL_POSITION) /* * Caller doesn't know what he's talking about. */ return (0); if (pos == (off_t)0) /* * Beginning of file is always line number 1. */ return (1); /* * Find the entry nearest to the position we want. */ for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) continue; if (p->pos == pos) /* Found it exactly. */ return (p->line); /* * This is the (possibly) time-consuming part. * We start at the line we just found and start * reading the file forward or backward till we * get to the place we want. * * First decide whether we should go forward from the * previous one or backwards from the next one. * The decision is based on which way involves * traversing fewer bytes in the file. */ flush(); (void)time(&startime); if (p == &anchor || pos - p->prev->pos < p->pos - pos) { /* * Go forward. */ p = p->prev; if (ch_seek(p->pos)) return (0); loopcount = 0; for (lno = p->line, cpos = p->pos; cpos < pos; lno++) { /* * Allow a signal to abort this loop. */ cpos = forw_raw_line(cpos); if (sigs || cpos == NULL_POSITION) return (0); if (loopcount >= 0 && ++loopcount > 100) { loopcount = 0; if (time((time_t *)NULL) >= startime + LONGTIME) { longloopmessage(); loopcount = -1; } } } lnloop = 0; /* * If the given position is not at the start of a line, * make sure we return the correct line number. */ if (cpos > pos) lno--; } else { /* * Go backward. */ if (ch_seek(p->pos)) return (0); loopcount = 0; for (lno = p->line, cpos = p->pos; cpos > pos; lno--) { /* * Allow a signal to abort this loop. */ cpos = back_raw_line(cpos); if (sigs || cpos == NULL_POSITION) return (0); if (loopcount >= 0 && ++loopcount > 100) { loopcount = 0; if (time((time_t *)NULL) >= startime + LONGTIME) { longloopmessage(); loopcount = -1; } } } lnloop = 0; } /* * We might as well cache it. */ add_lnum(lno, cpos); return (lno); } /* * Return the line number of the "current" line. * The argument "where" tells which line is to be considered * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). */ int currline(where) int where; { off_t pos; if ((pos = position(where)) == NULL_POSITION) pos = ch_length(); return(find_linenum(pos)); }
