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 volatile sig_atomic_t sigs; 73 extern int sc_height; 74 extern int screen_trashed; 75 76 /* 77 * Initialize the line number structures. 78 */ 79 void 80 clr_linenum(void) 81 { 82 struct linenum_info *p; 83 84 /* 85 * Put all the entries on the free list. 86 * Leave one for the "spare". 87 */ 88 for (p = pool; p < &pool[NPOOL-2]; p++) 89 p->next = p+1; 90 pool[NPOOL-2].next = NULL; 91 freelist = pool; 92 93 spare = &pool[NPOOL-1]; 94 95 /* 96 * Initialize the anchor. 97 */ 98 anchor.next = anchor.prev = &anchor; 99 anchor.gap = 0; 100 anchor.pos = 0; 101 anchor.line = 1; 102 } 103 104 /* 105 * Calculate the gap for an entry. 106 */ 107 static void 108 calcgap(struct linenum_info *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 void 127 add_lnum(off_t linenum, off_t pos) 128 { 129 struct linenum_info *p; 130 struct linenum_info *new; 131 struct linenum_info *nextp; 132 struct linenum_info *prevp; 133 off_t mingap; 134 135 /* 136 * Find the proper place in the list for the new one. 137 * The entries are sorted by position. 138 */ 139 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 140 if (p->line == linenum) 141 /* We already have this one. */ 142 return; 143 nextp = p; 144 prevp = p->prev; 145 146 if (freelist != NULL) { 147 /* 148 * We still have free (unused) entries. 149 * Use one of them. 150 */ 151 new = freelist; 152 freelist = freelist->next; 153 } else { 154 /* 155 * No free entries. 156 * Use the "spare" entry. 157 */ 158 new = spare; 159 spare = NULL; 160 } 161 162 /* 163 * Fill in the fields of the new entry, 164 * and insert it into the proper place in the list. 165 */ 166 new->next = nextp; 167 new->prev = prevp; 168 new->pos = pos; 169 new->line = linenum; 170 171 nextp->prev = new; 172 prevp->next = new; 173 174 /* 175 * Recalculate gaps for the new entry and the neighboring entries. 176 */ 177 calcgap(new); 178 calcgap(nextp); 179 calcgap(prevp); 180 181 if (spare == NULL) { 182 /* 183 * We have used the spare entry. 184 * Scan the list to find the one with the smallest 185 * gap, take it out and make it the spare. 186 * We should never remove the last one, so stop when 187 * we get to p->next == &anchor. This also avoids 188 * looking at the gap of the last one, which is 189 * not computed by calcgap. 190 */ 191 mingap = anchor.next->gap; 192 for (p = anchor.next; p->next != &anchor; p = p->next) { 193 if (p->gap <= mingap) { 194 spare = p; 195 mingap = p->gap; 196 } 197 } 198 spare->next->prev = spare->prev; 199 spare->prev->next = spare->next; 200 } 201 } 202 203 static int loopcount; 204 static struct timespec timeout; 205 206 static void 207 timeout_set(int seconds) 208 { 209 clock_gettime(CLOCK_MONOTONIC, &timeout); 210 timeout.tv_sec += seconds; 211 } 212 213 static int 214 timeout_elapsed(void) 215 { 216 struct timespec now; 217 218 clock_gettime(CLOCK_MONOTONIC, &now); 219 return timespeccmp(&now, &timeout, >=); 220 } 221 222 static void 223 longish(void) 224 { 225 if (loopcount >= 0 && ++loopcount > 100) { 226 loopcount = 0; 227 if (timeout_elapsed()) { 228 ierror("Calculating line numbers", NULL); 229 loopcount = -1; 230 } 231 } 232 } 233 234 /* 235 * Turn off line numbers because the user has interrupted 236 * a lengthy line number calculation. 237 */ 238 static void 239 abort_long(void) 240 { 241 if (linenums == OPT_ONPLUS) 242 /* 243 * We were displaying line numbers, so need to repaint. 244 */ 245 screen_trashed = 1; 246 linenums = 0; 247 error("Line numbers turned off", NULL); 248 } 249 250 /* 251 * Find the line number associated with a given position. 252 * Return 0 if we can't figure it out. 253 */ 254 off_t 255 find_linenum(off_t pos) 256 { 257 struct linenum_info *p; 258 off_t linenum; 259 off_t cpos; 260 261 if (!linenums) 262 /* 263 * We're not using line numbers. 264 */ 265 return (0); 266 if (pos == -1) 267 /* 268 * Caller doesn't know what he's talking about. 269 */ 270 return (0); 271 if (pos <= ch_zero()) 272 /* 273 * Beginning of file is always line number 1. 274 */ 275 return (1); 276 277 /* 278 * Find the entry nearest to the position we want. 279 */ 280 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 281 continue; 282 if (p->pos == pos) 283 /* Found it exactly. */ 284 return (p->line); 285 286 /* 287 * This is the (possibly) time-consuming part. 288 * We start at the line we just found and start 289 * reading the file forward or backward till we 290 * get to the place we want. 291 * 292 * First decide whether we should go forward from the 293 * previous one or backwards from the next one. 294 * The decision is based on which way involves 295 * traversing fewer bytes in the file. 296 */ 297 timeout_set(LONGTIME); 298 if (p == &anchor || pos - p->prev->pos < p->pos - pos) { 299 /* 300 * Go forward. 301 */ 302 p = p->prev; 303 if (ch_seek(p->pos)) 304 return (0); 305 loopcount = 0; 306 for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) { 307 /* 308 * Allow a signal to abort this loop. 309 */ 310 cpos = forw_raw_line(cpos, NULL, NULL); 311 if (ABORT_SIGS()) { 312 abort_long(); 313 return (0); 314 } 315 if (cpos == -1) 316 return (0); 317 longish(); 318 } 319 /* 320 * We might as well cache it. 321 */ 322 add_lnum(linenum, cpos); 323 /* 324 * If the given position is not at the start of a line, 325 * make sure we return the correct line number. 326 */ 327 if (cpos > pos) 328 linenum--; 329 } else { 330 /* 331 * Go backward. 332 */ 333 if (ch_seek(p->pos)) 334 return (0); 335 loopcount = 0; 336 for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) { 337 /* 338 * Allow a signal to abort this loop. 339 */ 340 cpos = back_raw_line(cpos, NULL, NULL); 341 if (ABORT_SIGS()) { 342 abort_long(); 343 return (0); 344 } 345 if (cpos == -1) 346 return (0); 347 longish(); 348 } 349 /* 350 * We might as well cache it. 351 */ 352 add_lnum(linenum, cpos); 353 } 354 355 return (linenum); 356 } 357 358 /* 359 * Find the position of a given line number. 360 * Return -1 if we can't figure it out. 361 */ 362 off_t 363 find_pos(off_t linenum) 364 { 365 struct linenum_info *p; 366 off_t cpos; 367 off_t clinenum; 368 369 if (linenum <= 1) 370 /* 371 * Line number 1 is beginning of file. 372 */ 373 return (ch_zero()); 374 375 /* 376 * Find the entry nearest to the line number we want. 377 */ 378 for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next) 379 continue; 380 if (p->line == linenum) 381 /* Found it exactly. */ 382 return (p->pos); 383 384 if (p == &anchor || linenum - p->prev->line < p->line - linenum) { 385 /* 386 * Go forward. 387 */ 388 p = p->prev; 389 if (ch_seek(p->pos)) 390 return (-1); 391 for (clinenum = p->line, cpos = p->pos; 392 clinenum < linenum; 393 clinenum++) { 394 /* 395 * Allow a signal to abort this loop. 396 */ 397 cpos = forw_raw_line(cpos, NULL, NULL); 398 if (ABORT_SIGS()) 399 return (-1); 400 if (cpos == -1) 401 return (-1); 402 } 403 } else { 404 /* 405 * Go backward. 406 */ 407 if (ch_seek(p->pos)) 408 return (-1); 409 for (clinenum = p->line, cpos = p->pos; 410 clinenum > linenum; 411 clinenum--) { 412 /* 413 * Allow a signal to abort this loop. 414 */ 415 cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL); 416 if (ABORT_SIGS()) 417 return (-1); 418 if (cpos == -1) 419 return (-1); 420 } 421 } 422 /* 423 * We might as well cache it. 424 */ 425 add_lnum(clinenum, cpos); 426 return (cpos); 427 } 428 429 /* 430 * Return the line number of the "current" line. 431 * The argument "where" tells which line is to be considered 432 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 433 */ 434 off_t 435 currline(int where) 436 { 437 off_t pos; 438 off_t len; 439 off_t linenum; 440 441 pos = position(where); 442 len = ch_length(); 443 while (pos == -1 && where >= 0 && where < sc_height) 444 pos = position(++where); 445 if (pos == -1) 446 pos = len; 447 linenum = find_linenum(pos); 448 if (pos == len) 449 linenum--; 450 return (linenum); 451 } 452