1 /* 2 * Copyright (C) 1984-2012 Mark Nudelman 3 * Modified for use with illumos by Garrett D'Amore. 4 * Copyright 2014 Garrett D'Amore <garrett@damore.org> 5 * 6 * You may distribute under the terms of either the GNU General Public 7 * License or the Less License, as specified in the README file. 8 * 9 * For more information, see the README file. 10 */ 11 12 /* 13 * Code to handle displaying line numbers. 14 * 15 * Finding the line number of a given file position is rather tricky. 16 * We don't want to just start at the beginning of the file and 17 * count newlines, because that is slow for large files (and also 18 * wouldn't work if we couldn't get to the start of the file; e.g. 19 * if input is a long pipe). 20 * 21 * So we use the function add_lnum to cache line numbers. 22 * We try to be very clever and keep only the more interesting 23 * line numbers when we run out of space in our table. A line 24 * number is more interesting than another when it is far from 25 * other line numbers. For example, we'd rather keep lines 26 * 100,200,300 than 100,101,300. 200 is more interesting than 27 * 101 because 101 can be derived very cheaply from 100, while 28 * 200 is more expensive to derive from 100. 29 * 30 * The function currline() returns the line number of a given 31 * position in the file. As a side effect, it calls add_lnum 32 * to cache the line number. Therefore currline is occasionally 33 * called to make sure we cache line numbers often enough. 34 */ 35 36 #include <sys/time.h> 37 38 #include <time.h> 39 40 #include "less.h" 41 42 /* 43 * Structure to keep track of a line number and the associated file position. 44 * A doubly-linked circular list of line numbers is kept ordered by line number. 45 */ 46 struct linenum_info { 47 struct linenum_info *next; /* Link to next in the list */ 48 struct linenum_info *prev; /* Line to previous in the list */ 49 off_t pos; /* File position */ 50 off_t gap; /* Gap between prev and next */ 51 off_t 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 200 /* Size of line number pool */ 63 64 #define LONGTIME (2) /* In seconds */ 65 66 static struct linenum_info anchor; /* Anchor of the list */ 67 static struct linenum_info *freelist; /* Anchor of the unused entries */ 68 static struct linenum_info pool[NPOOL]; /* The pool itself */ 69 static struct linenum_info *spare; /* We always keep one spare entry */ 70 71 extern int linenums; 72 extern int sc_height; 73 extern int screen_trashed; 74 75 /* 76 * Initialize the line number structures. 77 */ 78 void 79 clr_linenum(void) 80 { 81 struct linenum_info *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 = 0; 100 anchor.line = 1; 101 } 102 103 /* 104 * Calculate the gap for an entry. 105 */ 106 static void 107 calcgap(struct linenum_info *p) 108 { 109 /* 110 * Don't bother to compute a gap for the anchor. 111 * Also don't compute a gap for the last one in the list. 112 * The gap for that last one should be considered infinite, 113 * but we never look at it anyway. 114 */ 115 if (p == &anchor || p->next == &anchor) 116 return; 117 p->gap = p->next->pos - p->prev->pos; 118 } 119 120 /* 121 * Add a new line number to the cache. 122 * The specified position (pos) should be the file position of the 123 * FIRST character in the specified line. 124 */ 125 void 126 add_lnum(off_t linenum, off_t pos) 127 { 128 struct linenum_info *p; 129 struct linenum_info *new; 130 struct linenum_info *nextp; 131 struct linenum_info *prevp; 132 off_t mingap; 133 134 /* 135 * Find the proper place in the list for the new one. 136 * The entries are sorted by position. 137 */ 138 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 139 if (p->line == linenum) 140 /* We already have this one. */ 141 return; 142 nextp = p; 143 prevp = p->prev; 144 145 if (freelist != NULL) { 146 /* 147 * We still have free (unused) entries. 148 * Use one of them. 149 */ 150 new = freelist; 151 freelist = freelist->next; 152 } else { 153 /* 154 * No free entries. 155 * Use the "spare" entry. 156 */ 157 new = spare; 158 spare = NULL; 159 } 160 161 /* 162 * Fill in the fields of the new entry, 163 * and insert it into the proper place in the list. 164 */ 165 new->next = nextp; 166 new->prev = prevp; 167 new->pos = pos; 168 new->line = linenum; 169 170 nextp->prev = new; 171 prevp->next = new; 172 173 /* 174 * Recalculate gaps for the new entry and the neighboring entries. 175 */ 176 calcgap(new); 177 calcgap(nextp); 178 calcgap(prevp); 179 180 if (spare == NULL) { 181 /* 182 * We have used the spare entry. 183 * Scan the list to find the one with the smallest 184 * gap, take it out and make it the spare. 185 * We should never remove the last one, so stop when 186 * we get to p->next == &anchor. This also avoids 187 * looking at the gap of the last one, which is 188 * not computed by calcgap. 189 */ 190 mingap = anchor.next->gap; 191 for (p = anchor.next; p->next != &anchor; p = p->next) { 192 if (p->gap <= mingap) { 193 spare = p; 194 mingap = p->gap; 195 } 196 } 197 spare->next->prev = spare->prev; 198 spare->prev->next = spare->next; 199 } 200 } 201 202 static int loopcount; 203 static struct timespec timeout; 204 205 static void 206 timeout_set(int seconds) 207 { 208 clock_gettime(CLOCK_MONOTONIC, &timeout); 209 timeout.tv_sec += seconds; 210 } 211 212 static int 213 timeout_elapsed(void) 214 { 215 struct timespec now; 216 217 clock_gettime(CLOCK_MONOTONIC, &now); 218 return timespeccmp(&now, &timeout, >=); 219 } 220 221 static void 222 longish(void) 223 { 224 if (loopcount >= 0 && ++loopcount > 100) { 225 loopcount = 0; 226 if (timeout_elapsed()) { 227 ierror("Calculating line numbers", NULL); 228 loopcount = -1; 229 } 230 } 231 } 232 233 /* 234 * Turn off line numbers because the user has interrupted 235 * a lengthy line number calculation. 236 */ 237 static void 238 abort_long(void) 239 { 240 if (linenums == OPT_ONPLUS) 241 /* 242 * We were displaying line numbers, so need to repaint. 243 */ 244 screen_trashed = 1; 245 linenums = 0; 246 error("Line numbers turned off", NULL); 247 } 248 249 /* 250 * Find the line number associated with a given position. 251 * Return 0 if we can't figure it out. 252 */ 253 off_t 254 find_linenum(off_t pos) 255 { 256 struct linenum_info *p; 257 off_t linenum; 258 off_t cpos; 259 260 if (!linenums) 261 /* 262 * We're not using line numbers. 263 */ 264 return (0); 265 if (pos == -1) 266 /* 267 * Caller doesn't know what he's talking about. 268 */ 269 return (0); 270 if (pos <= ch_zero()) 271 /* 272 * Beginning of file is always line number 1. 273 */ 274 return (1); 275 276 /* 277 * Find the entry nearest to the position we want. 278 */ 279 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 280 continue; 281 if (p->pos == pos) 282 /* Found it exactly. */ 283 return (p->line); 284 285 /* 286 * This is the (possibly) time-consuming part. 287 * We start at the line we just found and start 288 * reading the file forward or backward till we 289 * get to the place we want. 290 * 291 * First decide whether we should go forward from the 292 * previous one or backwards from the next one. 293 * The decision is based on which way involves 294 * traversing fewer bytes in the file. 295 */ 296 timeout_set(LONGTIME); 297 if (p == &anchor || pos - p->prev->pos < p->pos - pos) { 298 /* 299 * Go forward. 300 */ 301 p = p->prev; 302 if (ch_seek(p->pos)) 303 return (0); 304 loopcount = 0; 305 for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) { 306 /* 307 * Allow a signal to abort this loop. 308 */ 309 cpos = forw_raw_line(cpos, NULL, NULL); 310 if (abort_sigs()) { 311 abort_long(); 312 return (0); 313 } 314 if (cpos == -1) 315 return (0); 316 longish(); 317 } 318 /* 319 * We might as well cache it. 320 */ 321 add_lnum(linenum, cpos); 322 /* 323 * If the given position is not at the start of a line, 324 * make sure we return the correct line number. 325 */ 326 if (cpos > pos) 327 linenum--; 328 } else { 329 /* 330 * Go backward. 331 */ 332 if (ch_seek(p->pos)) 333 return (0); 334 loopcount = 0; 335 for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) { 336 /* 337 * Allow a signal to abort this loop. 338 */ 339 cpos = back_raw_line(cpos, NULL, NULL); 340 if (abort_sigs()) { 341 abort_long(); 342 return (0); 343 } 344 if (cpos == -1) 345 return (0); 346 longish(); 347 } 348 /* 349 * We might as well cache it. 350 */ 351 add_lnum(linenum, cpos); 352 } 353 354 return (linenum); 355 } 356 357 /* 358 * Find the position of a given line number. 359 * Return -1 if we can't figure it out. 360 */ 361 off_t 362 find_pos(off_t linenum) 363 { 364 struct linenum_info *p; 365 off_t cpos; 366 off_t clinenum; 367 368 if (linenum <= 1) 369 /* 370 * Line number 1 is beginning of file. 371 */ 372 return (ch_zero()); 373 374 /* 375 * Find the entry nearest to the line number we want. 376 */ 377 for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next) 378 continue; 379 if (p->line == linenum) 380 /* Found it exactly. */ 381 return (p->pos); 382 383 if (p == &anchor || linenum - p->prev->line < p->line - linenum) { 384 /* 385 * Go forward. 386 */ 387 p = p->prev; 388 if (ch_seek(p->pos)) 389 return (-1); 390 for (clinenum = p->line, cpos = p->pos; 391 clinenum < linenum; 392 clinenum++) { 393 /* 394 * Allow a signal to abort this loop. 395 */ 396 cpos = forw_raw_line(cpos, NULL, NULL); 397 if (abort_sigs()) 398 return (-1); 399 if (cpos == -1) 400 return (-1); 401 } 402 } else { 403 /* 404 * Go backward. 405 */ 406 if (ch_seek(p->pos)) 407 return (-1); 408 for (clinenum = p->line, cpos = p->pos; 409 clinenum > linenum; 410 clinenum--) { 411 /* 412 * Allow a signal to abort this loop. 413 */ 414 cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL); 415 if (abort_sigs()) 416 return (-1); 417 if (cpos == -1) 418 return (-1); 419 } 420 } 421 /* 422 * We might as well cache it. 423 */ 424 add_lnum(clinenum, cpos); 425 return (cpos); 426 } 427 428 /* 429 * Return the line number of the "current" line. 430 * The argument "where" tells which line is to be considered 431 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 432 */ 433 off_t 434 currline(int where) 435 { 436 off_t pos; 437 off_t len; 438 off_t linenum; 439 440 pos = position(where); 441 len = ch_length(); 442 while (pos == -1 && where >= 0 && where < sc_height) 443 pos = position(++where); 444 if (pos == -1) 445 pos = len; 446 linenum = find_linenum(pos); 447 if (pos == len) 448 linenum--; 449 return (linenum); 450 } 451