1 /* $NetBSD: linenum.c,v 1.3 1998/02/04 11:08:55 christos Exp $ */ 2 3 /* 4 * Copyright (c) 1988 Mark Nudleman 5 * Copyright (c) 1988, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #include <sys/cdefs.h> 38 #ifndef lint 39 #if 0 40 static char sccsid[] = "@(#)linenum.c 8.1 (Berkeley) 6/6/93"; 41 #else 42 __RCSID("$NetBSD: linenum.c,v 1.3 1998/02/04 11:08:55 christos Exp $"); 43 #endif 44 #endif /* not lint */ 45 46 /* 47 * Code to handle displaying line numbers. 48 * 49 * Finding the line number of a given file position is rather tricky. 50 * We don't want to just start at the beginning of the file and 51 * count newlines, because that is slow for large files (and also 52 * wouldn't work if we couldn't get to the start of the file; e.g. 53 * if input is a long pipe). 54 * 55 * So we use the function add_lnum to cache line numbers. 56 * We try to be very clever and keep only the more interesting 57 * line numbers when we run out of space in our table. A line 58 * number is more interesting than another when it is far from 59 * other line numbers. For example, we'd rather keep lines 60 * 100,200,300 than 100,101,300. 200 is more interesting than 61 * 101 because 101 can be derived very cheaply from 100, while 62 * 200 is more expensive to derive from 100. 63 * 64 * The function currline() returns the line number of a given 65 * position in the file. As a side effect, it calls add_lnum 66 * to cache the line number. Therefore currline is occasionally 67 * called to make sure we cache line numbers often enough. 68 */ 69 70 #include <sys/types.h> 71 #include <stdio.h> 72 #include <time.h> 73 74 #include "less.h" 75 #include "extern.h" 76 77 /* 78 * Structure to keep track of a line number and the associated file position. 79 * A doubly-linked circular list of line numbers is kept ordered by line number. 80 */ 81 struct linenum 82 { 83 struct linenum *next; /* Link to next in the list */ 84 struct linenum *prev; /* Line to previous in the list */ 85 off_t pos; /* File position */ 86 off_t gap; /* Gap between prev and next */ 87 int line; /* Line number */ 88 }; 89 /* 90 * "gap" needs some explanation: the gap of any particular line number 91 * is the distance between the previous one and the next one in the list. 92 * ("Distance" means difference in file position.) In other words, the 93 * gap of a line number is the gap which would be introduced if this 94 * line number were deleted. It is used to decide which one to replace 95 * when we have a new one to insert and the table is full. 96 */ 97 98 #define NPOOL 50 /* Size of line number pool */ 99 100 #define LONGTIME (2) /* In seconds */ 101 102 int lnloop = 0; /* Are we in the line num loop? */ 103 104 static struct linenum anchor; /* Anchor of the list */ 105 static struct linenum *freelist; /* Anchor of the unused entries */ 106 static struct linenum pool[NPOOL]; /* The pool itself */ 107 static struct linenum *spare; /* We always keep one spare entry */ 108 109 static void calcgap __P((struct linenum *)); 110 static void longloopmessage __P((void)); 111 /* 112 * Initialize the line number structures. 113 */ 114 void 115 clr_linenum() 116 { 117 struct linenum *p; 118 119 /* 120 * Put all the entries on the free list. 121 * Leave one for the "spare". 122 */ 123 for (p = pool; p < &pool[NPOOL-2]; p++) 124 p->next = p+1; 125 pool[NPOOL-2].next = NULL; 126 freelist = pool; 127 128 spare = &pool[NPOOL-1]; 129 130 /* 131 * Initialize the anchor. 132 */ 133 anchor.next = anchor.prev = &anchor; 134 anchor.gap = 0; 135 anchor.pos = (off_t)0; 136 anchor.line = 1; 137 } 138 139 /* 140 * Calculate the gap for an entry. 141 */ 142 static void 143 calcgap(p) 144 struct linenum *p; 145 { 146 /* 147 * Don't bother to compute a gap for the anchor. 148 * Also don't compute a gap for the last one in the list. 149 * The gap for that last one should be considered infinite, 150 * but we never look at it anyway. 151 */ 152 if (p == &anchor || p->next == &anchor) 153 return; 154 p->gap = p->next->pos - p->prev->pos; 155 } 156 157 /* 158 * Add a new line number to the cache. 159 * The specified position (pos) should be the file position of the 160 * FIRST character in the specified line. 161 */ 162 void 163 add_lnum(line, pos) 164 int line; 165 off_t pos; 166 { 167 struct linenum *p; 168 struct linenum *new; 169 struct linenum *nextp; 170 struct linenum *prevp; 171 off_t mingap; 172 173 /* 174 * Find the proper place in the list for the new one. 175 * The entries are sorted by position. 176 */ 177 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 178 if (p->line == line) 179 /* We already have this one. */ 180 return; 181 nextp = p; 182 prevp = p->prev; 183 184 if (freelist != NULL) 185 { 186 /* 187 * We still have free (unused) entries. 188 * Use one of them. 189 */ 190 new = freelist; 191 freelist = freelist->next; 192 } else 193 { 194 /* 195 * No free entries. 196 * Use the "spare" entry. 197 */ 198 new = spare; 199 spare = NULL; 200 } 201 202 /* 203 * Fill in the fields of the new entry, 204 * and insert it into the proper place in the list. 205 */ 206 new->next = nextp; 207 new->prev = prevp; 208 new->pos = pos; 209 new->line = line; 210 211 nextp->prev = new; 212 prevp->next = new; 213 214 /* 215 * Recalculate gaps for the new entry and the neighboring entries. 216 */ 217 calcgap(new); 218 calcgap(nextp); 219 calcgap(prevp); 220 221 if (spare == NULL) 222 { 223 /* 224 * We have used the spare entry. 225 * Scan the list to find the one with the smallest 226 * gap, take it out and make it the spare. 227 * We should never remove the last one, so stop when 228 * we get to p->next == &anchor. This also avoids 229 * looking at the gap of the last one, which is 230 * not computed by calcgap. 231 */ 232 mingap = anchor.next->gap; 233 for (p = anchor.next; p->next != &anchor; p = p->next) 234 { 235 if (p->gap <= mingap) 236 { 237 spare = p; 238 mingap = p->gap; 239 } 240 } 241 spare->next->prev = spare->prev; 242 spare->prev->next = spare->next; 243 } 244 } 245 246 /* 247 * If we get stuck in a long loop trying to figure out the 248 * line number, print a message to tell the user what we're doing. 249 */ 250 static void 251 longloopmessage() 252 { 253 ierror("Calculating line numbers"); 254 /* 255 * Set the lnloop flag here, so if the user interrupts while 256 * we are calculating line numbers, the signal handler will 257 * turn off line numbers (linenums=0). 258 */ 259 lnloop = 1; 260 } 261 262 /* 263 * Find the line number associated with a given position. 264 * Return 0 if we can't figure it out. 265 */ 266 int 267 find_linenum(pos) 268 off_t pos; 269 { 270 struct linenum *p; 271 int lno; 272 int loopcount; 273 off_t cpos; 274 time_t startime; 275 276 if (!linenums) 277 /* 278 * We're not using line numbers. 279 */ 280 return (0); 281 if (pos == NULL_POSITION) 282 /* 283 * Caller doesn't know what he's talking about. 284 */ 285 return (0); 286 if (pos == (off_t)0) 287 /* 288 * Beginning of file is always line number 1. 289 */ 290 return (1); 291 292 /* 293 * Find the entry nearest to the position we want. 294 */ 295 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 296 continue; 297 if (p->pos == pos) 298 /* Found it exactly. */ 299 return (p->line); 300 301 /* 302 * This is the (possibly) time-consuming part. 303 * We start at the line we just found and start 304 * reading the file forward or backward till we 305 * get to the place we want. 306 * 307 * First decide whether we should go forward from the 308 * previous one or backwards from the next one. 309 * The decision is based on which way involves 310 * traversing fewer bytes in the file. 311 */ 312 flush(); 313 (void)time(&startime); 314 if (p == &anchor || pos - p->prev->pos < p->pos - pos) 315 { 316 /* 317 * Go forward. 318 */ 319 p = p->prev; 320 if (ch_seek(p->pos)) 321 return (0); 322 loopcount = 0; 323 for (lno = p->line, cpos = p->pos; cpos < pos; lno++) 324 { 325 /* 326 * Allow a signal to abort this loop. 327 */ 328 cpos = forw_raw_line(cpos); 329 if (sigs || cpos == NULL_POSITION) 330 return (0); 331 if (loopcount >= 0 && ++loopcount > 100) { 332 loopcount = 0; 333 if (time((time_t *)NULL) 334 >= startime + LONGTIME) { 335 longloopmessage(); 336 loopcount = -1; 337 } 338 } 339 } 340 lnloop = 0; 341 /* 342 * If the given position is not at the start of a line, 343 * make sure we return the correct line number. 344 */ 345 if (cpos > pos) 346 lno--; 347 } else 348 { 349 /* 350 * Go backward. 351 */ 352 if (ch_seek(p->pos)) 353 return (0); 354 loopcount = 0; 355 for (lno = p->line, cpos = p->pos; cpos > pos; lno--) 356 { 357 /* 358 * Allow a signal to abort this loop. 359 */ 360 cpos = back_raw_line(cpos); 361 if (sigs || cpos == NULL_POSITION) 362 return (0); 363 if (loopcount >= 0 && ++loopcount > 100) { 364 loopcount = 0; 365 if (time((time_t *)NULL) 366 >= startime + LONGTIME) { 367 longloopmessage(); 368 loopcount = -1; 369 } 370 } 371 } 372 lnloop = 0; 373 } 374 375 /* 376 * We might as well cache it. 377 */ 378 add_lnum(lno, cpos); 379 return (lno); 380 } 381 382 /* 383 * Return the line number of the "current" line. 384 * The argument "where" tells which line is to be considered 385 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 386 */ 387 int 388 currline(where) 389 int where; 390 { 391 off_t pos; 392 393 if ((pos = position(where)) == NULL_POSITION) 394 pos = ch_length(); 395 return(find_linenum(pos)); 396 } 397