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