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