1 /* 2 * Copyright (C) 1984-2024 Mark Nudelman 3 * 4 * You may distribute under the terms of either the GNU General Public 5 * License or the Less License, as specified in the README file. 6 * 7 * For more information, see the README file. 8 */ 9 10 11 /* 12 * Code to handle displaying line numbers. 13 * 14 * Finding the line number of a given file position is rather tricky. 15 * We don't want to just start at the beginning of the file and 16 * count newlines, because that is slow for large files (and also 17 * wouldn't work if we couldn't get to the start of the file; e.g. 18 * if input is a long pipe). 19 * 20 * So we use the function add_lnum to cache line numbers. 21 * We try to be very clever and keep only the more interesting 22 * line numbers when we run out of space in our table. A line 23 * number is more interesting than another when it is far from 24 * other line numbers. For example, we'd rather keep lines 25 * 100,200,300 than 100,101,300. 200 is more interesting than 26 * 101 because 101 can be derived very cheaply from 100, while 27 * 200 is more expensive to derive from 100. 28 * 29 * The function currline() returns the line number of a given 30 * position in the file. As a side effect, it calls add_lnum 31 * to cache the line number. Therefore currline is occasionally 32 * called to make sure we cache line numbers often enough. 33 */ 34 35 #include "less.h" 36 37 /* 38 * Structure to keep track of a line number and the associated file position. 39 * A doubly-linked circular list of line numbers is kept ordered by line number. 40 */ 41 struct linenum_info 42 { 43 struct linenum_info *next; /* Link to next in the list */ 44 struct linenum_info *prev; /* Line to previous in the list */ 45 POSITION pos; /* File position */ 46 POSITION gap; /* Gap between prev and next */ 47 LINENUM line; /* Line number */ 48 }; 49 /* 50 * "gap" needs some explanation: the gap of any particular line number 51 * is the distance between the previous one and the next one in the list. 52 * ("Distance" means difference in file position.) In other words, the 53 * gap of a line number is the gap which would be introduced if this 54 * line number were deleted. It is used to decide which one to replace 55 * when we have a new one to insert and the table is full. 56 */ 57 58 #define NPOOL 200 /* Size of line number pool */ 59 60 #define LONGTIME (2) /* In seconds */ 61 62 static struct linenum_info anchor; /* Anchor of the list */ 63 static struct linenum_info *freelist; /* Anchor of the unused entries */ 64 static struct linenum_info pool[NPOOL]; /* The pool itself */ 65 static struct linenum_info *spare; /* We always keep one spare entry */ 66 public lbool scanning_eof = FALSE; 67 68 extern int linenums; 69 extern int sigs; 70 extern int sc_height; 71 extern int header_lines; 72 extern int nonum_headers; 73 74 /* 75 * Initialize the line number structures. 76 */ 77 public void clr_linenum(void) 78 { 79 struct linenum_info *p; 80 81 /* 82 * Put all the entries on the free list. 83 * Leave one for the "spare". 84 */ 85 for (p = pool; p < &pool[NPOOL-2]; p++) 86 p->next = p+1; 87 pool[NPOOL-2].next = NULL; 88 freelist = pool; 89 90 spare = &pool[NPOOL-1]; 91 92 /* 93 * Initialize the anchor. 94 */ 95 anchor.next = anchor.prev = &anchor; 96 anchor.gap = 0; 97 anchor.pos = (POSITION)0; 98 anchor.line = 1; 99 } 100 101 /* 102 * Calculate the gap for an entry. 103 */ 104 static void calcgap(struct linenum_info *p) 105 { 106 /* 107 * Don't bother to compute a gap for the anchor. 108 * Also don't compute a gap for the last one in the list. 109 * The gap for that last one should be considered infinite, 110 * but we never look at it anyway. 111 */ 112 if (p == &anchor || p->next == &anchor) 113 return; 114 p->gap = p->next->pos - p->prev->pos; 115 } 116 117 /* 118 * Add a new line number to the cache. 119 * The specified position (pos) should be the file position of the 120 * FIRST character in the specified line. 121 */ 122 public void add_lnum(LINENUM linenum, POSITION pos) 123 { 124 struct linenum_info *p; 125 struct linenum_info *new; 126 struct linenum_info *nextp; 127 struct linenum_info *prevp; 128 POSITION mingap; 129 130 /* 131 * Find the proper place in the list for the new one. 132 * The entries are sorted by position. 133 */ 134 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 135 if (p->line == linenum) 136 /* We already have this one. */ 137 return; 138 nextp = p; 139 prevp = p->prev; 140 141 if (freelist != NULL) 142 { 143 /* 144 * We still have free (unused) entries. 145 * Use one of them. 146 */ 147 new = freelist; 148 freelist = freelist->next; 149 } else 150 { 151 /* 152 * No free entries. 153 * Use the "spare" entry. 154 */ 155 new = spare; 156 spare = NULL; 157 } 158 159 /* 160 * Fill in the fields of the new entry, 161 * and insert it into the proper place in the list. 162 */ 163 new->next = nextp; 164 new->prev = prevp; 165 new->pos = pos; 166 new->line = linenum; 167 168 nextp->prev = new; 169 prevp->next = new; 170 171 /* 172 * Recalculate gaps for the new entry and the neighboring entries. 173 */ 174 calcgap(new); 175 calcgap(nextp); 176 calcgap(prevp); 177 178 if (spare == NULL) 179 { 180 /* 181 * We have used the spare entry. 182 * Scan the list to find the one with the smallest 183 * gap, take it out and make it the spare. 184 * We should never remove the last one, so stop when 185 * we get to p->next == &anchor. This also avoids 186 * looking at the gap of the last one, which is 187 * not computed by calcgap. 188 */ 189 mingap = anchor.next->gap; 190 for (p = anchor.next; p->next != &anchor; p = p->next) 191 { 192 if (p->gap <= mingap) 193 { 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 /* 204 * If we get stuck in a long loop trying to figure out the 205 * line number, print a message to tell the user what we're doing. 206 */ 207 static void longloopmessage(void) 208 { 209 ierror("Calculating line numbers", NULL_PARG); 210 } 211 212 struct delayed_msg 213 { 214 void (*message)(void); 215 int loopcount; 216 #if HAVE_TIME 217 time_type startime; 218 #endif 219 }; 220 221 static void start_delayed_msg(struct delayed_msg *dmsg, void (*message)(void)) 222 { 223 dmsg->loopcount = 0; 224 dmsg->message = message; 225 #if HAVE_TIME 226 dmsg->startime = get_time(); 227 #endif 228 } 229 230 static void delayed_msg(struct delayed_msg *dmsg) 231 { 232 #if HAVE_TIME 233 if (dmsg->loopcount >= 0 && ++(dmsg->loopcount) > 100) 234 { 235 dmsg->loopcount = 0; 236 if (get_time() >= dmsg->startime + LONGTIME) 237 { 238 dmsg->message(); 239 dmsg->loopcount = -1; 240 } 241 } 242 #else 243 if (dmsg->loopcount >= 0 && ++(dmsg->loopcount) > LONGLOOP) 244 { 245 dmsg->message(); 246 dmsg->loopcount = -1; 247 } 248 #endif 249 } 250 251 /* 252 * Turn off line numbers because the user has interrupted 253 * a lengthy line number calculation. 254 */ 255 static void abort_delayed_msg(struct delayed_msg *dmsg) 256 { 257 if (dmsg->loopcount >= 0) 258 return; 259 if (linenums == OPT_ONPLUS) 260 /* 261 * We were displaying line numbers, so need to repaint. 262 */ 263 screen_trashed(); 264 linenums = 0; 265 error("Line numbers turned off", NULL_PARG); 266 } 267 268 /* 269 * Find the line number associated with a given position. 270 * Return 0 if we can't figure it out. 271 */ 272 public LINENUM find_linenum(POSITION pos) 273 { 274 struct linenum_info *p; 275 LINENUM linenum; 276 POSITION cpos; 277 struct delayed_msg dmsg; 278 279 if (!linenums) 280 /* 281 * We're not using line numbers. 282 */ 283 return (0); 284 if (pos == NULL_POSITION) 285 /* 286 * Caller doesn't know what he's talking about. 287 */ 288 return (0); 289 if (pos <= ch_zero()) 290 /* 291 * Beginning of file is always line number 1. 292 */ 293 return (1); 294 295 /* 296 * Find the entry nearest to the position we want. 297 */ 298 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next) 299 continue; 300 if (p->pos == pos) 301 /* Found it exactly. */ 302 return (p->line); 303 304 /* 305 * This is the (possibly) time-consuming part. 306 * We start at the line we just found and start 307 * reading the file forward or backward till we 308 * get to the place we want. 309 * 310 * First decide whether we should go forward from the 311 * previous one or backwards from the next one. 312 * The decision is based on which way involves 313 * traversing fewer bytes in the file. 314 */ 315 start_delayed_msg(&dmsg, longloopmessage); 316 if (p == &anchor || pos - p->prev->pos < p->pos - pos) 317 { 318 /* 319 * Go forward. 320 */ 321 p = p->prev; 322 if (ch_seek(p->pos)) 323 return (0); 324 for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) 325 { 326 /* 327 * Allow a signal to abort this loop. 328 */ 329 cpos = forw_raw_line(cpos, NULL, NULL); 330 if (ABORT_SIGS()) { 331 abort_delayed_msg(&dmsg); 332 return (0); 333 } 334 if (cpos == NULL_POSITION) 335 return (0); 336 delayed_msg(&dmsg); 337 } 338 /* 339 * We might as well cache it. 340 */ 341 add_lnum(linenum, cpos); 342 /* 343 * If the given position is not at the start of a line, 344 * make sure we return the correct line number. 345 */ 346 if (cpos > pos) 347 linenum--; 348 } else 349 { 350 /* 351 * Go backward. 352 */ 353 if (ch_seek(p->pos)) 354 return (0); 355 for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) 356 { 357 /* 358 * Allow a signal to abort this loop. 359 */ 360 cpos = back_raw_line(cpos, NULL, NULL); 361 if (ABORT_SIGS()) { 362 abort_delayed_msg(&dmsg); 363 return (0); 364 } 365 if (cpos == NULL_POSITION) 366 return (0); 367 delayed_msg(&dmsg); 368 } 369 /* 370 * We might as well cache it. 371 */ 372 add_lnum(linenum, cpos); 373 } 374 return (linenum); 375 } 376 377 /* 378 * Find the position of a given line number. 379 * Return NULL_POSITION if we can't figure it out. 380 */ 381 public POSITION find_pos(LINENUM linenum) 382 { 383 struct linenum_info *p; 384 POSITION cpos; 385 LINENUM clinenum; 386 387 if (linenum <= 1) 388 /* 389 * Line number 1 is beginning of file. 390 */ 391 return (ch_zero()); 392 393 /* 394 * Find the entry nearest to the line number we want. 395 */ 396 for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next) 397 continue; 398 if (p->line == linenum) 399 /* Found it exactly. */ 400 return (p->pos); 401 402 if (p == &anchor || linenum - p->prev->line < p->line - linenum) 403 { 404 /* 405 * Go forward. 406 */ 407 p = p->prev; 408 if (ch_seek(p->pos)) 409 return (NULL_POSITION); 410 for (clinenum = p->line, cpos = p->pos; clinenum < linenum; clinenum++) 411 { 412 /* 413 * Allow a signal to abort this loop. 414 */ 415 cpos = forw_raw_line(cpos, NULL, NULL); 416 if (ABORT_SIGS()) 417 return (NULL_POSITION); 418 if (cpos == NULL_POSITION) 419 return (NULL_POSITION); 420 } 421 } else 422 { 423 /* 424 * Go backward. 425 */ 426 if (ch_seek(p->pos)) 427 return (NULL_POSITION); 428 for (clinenum = p->line, cpos = p->pos; clinenum > linenum; clinenum--) 429 { 430 /* 431 * Allow a signal to abort this loop. 432 */ 433 cpos = back_raw_line(cpos, NULL, NULL); 434 if (ABORT_SIGS()) 435 return (NULL_POSITION); 436 if (cpos == NULL_POSITION) 437 return (NULL_POSITION); 438 } 439 } 440 /* 441 * We might as well cache it. 442 */ 443 add_lnum(clinenum, cpos); 444 return (cpos); 445 } 446 447 /* 448 * Return the line number of the "current" line. 449 * The argument "where" tells which line is to be considered 450 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc). 451 */ 452 public LINENUM currline(int where) 453 { 454 POSITION pos; 455 POSITION len; 456 LINENUM linenum; 457 458 pos = position(where); 459 len = ch_length(); 460 while (pos == NULL_POSITION && where >= 0 && where < sc_height) 461 pos = position(++where); 462 if (pos == NULL_POSITION) 463 pos = len; 464 linenum = find_linenum(pos); 465 if (pos == len) 466 linenum--; 467 return (linenum); 468 } 469 470 static void detlenmessage(void) 471 { 472 ierror("Determining length of file", NULL_PARG); 473 } 474 475 /* 476 * Scan entire file, counting line numbers. 477 */ 478 public void scan_eof(void) 479 { 480 POSITION pos = ch_zero(); 481 LINENUM linenum = 0; 482 struct delayed_msg dmsg; 483 484 if (ch_seek(0)) 485 return; 486 /* 487 * scanning_eof prevents the "Waiting for data" message from 488 * overwriting "Determining length of file". 489 */ 490 start_delayed_msg(&dmsg, detlenmessage); 491 scanning_eof = TRUE; 492 while (pos != NULL_POSITION) 493 { 494 /* For efficiency, only add one every 256 line numbers. */ 495 if ((linenum++ % 256) == 0) 496 add_lnum(linenum, pos); 497 pos = forw_raw_line(pos, NULL, NULL); 498 if (ABORT_SIGS()) 499 { 500 abort_delayed_msg(&dmsg); 501 break; 502 } 503 delayed_msg(&dmsg); 504 } 505 scanning_eof = FALSE; 506 } 507 508 /* 509 * Return a line number adjusted for display 510 * (handles the --no-number-headers option). 511 */ 512 public LINENUM vlinenum(LINENUM linenum) 513 { 514 if (nonum_headers) 515 linenum = (linenum < header_lines) ? 0 : linenum - header_lines; 516 return linenum; 517 } 518