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