contrib/less/linenum.c

   1 /*
   2  * Copyright (C) 1984-2023  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 int scanning_eof = FALSE;
  67
  68 extern int linenums;
  69 extern int sigs;
  70 extern int sc_height;
  71 extern int screen_trashed;
  72 extern int header_lines;
  73 extern int nonum_headers;
  74
  75 /*
  76  * Initialize the line number structures.
  77  */
  78 public void clr_linenum(void)
  79 {
  80         struct linenum_info *p;
  81
  82         /*
  83          * Put all the entries on the free list.
  84          * Leave one for the "spare".
  85          */
  86         for (p = pool;  p < &pool[NPOOL-2];  p++)
  87                 p->next = p+1;
  88         pool[NPOOL-2].next = NULL;
  89         freelist = pool;
  90
  91         spare = &pool[NPOOL-1];
  92
  93         /*
  94          * Initialize the anchor.
  95          */
  96         anchor.next = anchor.prev = &anchor;
  97         anchor.gap = 0;
  98         anchor.pos = (POSITION)0;
  99         anchor.line = 1;
 100 }
 101
 102 /*
 103  * Calculate the gap for an entry.
 104  */
 105 static void calcgap(struct linenum_info *p)
 106 {
 107         /*
 108          * Don't bother to compute a gap for the anchor.
 109          * Also don't compute a gap for the last one in the list.
 110          * The gap for that last one should be considered infinite,
 111          * but we never look at it anyway.
 112          */
 113         if (p == &anchor || p->next == &anchor)
 114                 return;
 115         p->gap = p->next->pos - p->prev->pos;
 116 }
 117
 118 /*
 119  * Add a new line number to the cache.
 120  * The specified position (pos) should be the file position of the
 121  * FIRST character in the specified line.
 122  */
 123 public void add_lnum(LINENUM linenum, POSITION pos)
 124 {
 125         struct linenum_info *p;
 126         struct linenum_info *new;
 127         struct linenum_info *nextp;
 128         struct linenum_info *prevp;
 129         POSITION mingap;
 130
 131         /*
 132          * Find the proper place in the list for the new one.
 133          * The entries are sorted by position.
 134          */
 135         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 136                 if (p->line == linenum)
 137                         /* We already have this one. */
 138                         return;
 139         nextp = p;
 140         prevp = p->prev;
 141
 142         if (freelist != NULL)
 143         {
 144                 /*
 145                  * We still have free (unused) entries.
 146                  * Use one of them.
 147                  */
 148                 new = freelist;
 149                 freelist = freelist->next;
 150         } else
 151         {
 152                 /*
 153                  * No free entries.
 154                  * Use the "spare" entry.
 155                  */
 156                 new = spare;
 157                 spare = NULL;
 158         }
 159
 160         /*
 161          * Fill in the fields of the new entry,
 162          * and insert it into the proper place in the list.
 163          */
 164         new->next = nextp;
 165         new->prev = prevp;
 166         new->pos = pos;
 167         new->line = linenum;
 168
 169         nextp->prev = new;
 170         prevp->next = new;
 171
 172         /*
 173          * Recalculate gaps for the new entry and the neighboring entries.
 174          */
 175         calcgap(new);
 176         calcgap(nextp);
 177         calcgap(prevp);
 178
 179         if (spare == NULL)
 180         {
 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                 {
 193                         if (p->gap <= mingap)
 194                         {
 195                                 spare = p;
 196                                 mingap = p->gap;
 197                         }
 198                 }
 199                 spare->next->prev = spare->prev;
 200                 spare->prev->next = spare->next;
 201         }
 202 }
 203
 204 /*
 205  * If we get stuck in a long loop trying to figure out the
 206  * line number, print a message to tell the user what we're doing.
 207  */
 208 static void longloopmessage(void)
 209 {
 210         ierror("Calculating line numbers", NULL_PARG);
 211 }
 212
 213 static int loopcount;
 214 #if HAVE_TIME
 215 static time_type startime;
 216 #endif
 217
 218 static void longish(void)
 219 {
 220 #if HAVE_TIME
 221         if (loopcount >= 0 && ++loopcount > 100)
 222         {
 223                 loopcount = 0;
 224                 if (get_time() >= startime + LONGTIME)
 225                 {
 226                         longloopmessage();
 227                         loopcount = -1;
 228                 }
 229         }
 230 #else
 231         if (loopcount >= 0 && ++loopcount > LONGLOOP)
 232         {
 233                 longloopmessage();
 234                 loopcount = -1;
 235         }
 236 #endif
 237 }
 238
 239 /*
 240  * Turn off line numbers because the user has interrupted
 241  * a lengthy line number calculation.
 242  */
 243 static void abort_long(void)
 244 {
 245         if (loopcount >= 0)
 246                 return;
 247         if (linenums == OPT_ONPLUS)
 248                 /*
 249                  * We were displaying line numbers, so need to repaint.
 250                  */
 251                 screen_trashed = 1;
 252         linenums = 0;
 253         error("Line numbers turned off", NULL_PARG);
 254 }
 255
 256 /*
 257  * Find the line number associated with a given position.
 258  * Return 0 if we can't figure it out.
 259  */
 260 public LINENUM find_linenum(POSITION pos)
 261 {
 262         struct linenum_info *p;
 263         LINENUM linenum;
 264         POSITION cpos;
 265
 266         if (!linenums)
 267                 /*
 268                  * We're not using line numbers.
 269                  */
 270                 return (0);
 271         if (pos == NULL_POSITION)
 272                 /*
 273                  * Caller doesn't know what he's talking about.
 274                  */
 275                 return (0);
 276         if (pos <= ch_zero())
 277                 /*
 278                  * Beginning of file is always line number 1.
 279                  */
 280                 return (1);
 281
 282         /*
 283          * Find the entry nearest to the position we want.
 284          */
 285         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 286                 continue;
 287         if (p->pos == pos)
 288                 /* Found it exactly. */
 289                 return (p->line);
 290
 291         /*
 292          * This is the (possibly) time-consuming part.
 293          * We start at the line we just found and start
 294          * reading the file forward or backward till we
 295          * get to the place we want.
 296          *
 297          * First decide whether we should go forward from the
 298          * previous one or backwards from the next one.
 299          * The decision is based on which way involves
 300          * traversing fewer bytes in the file.
 301          */
 302 #if HAVE_TIME
 303         startime = get_time();
 304 #endif
 305         loopcount = 0;
 306         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 307         {
 308                 /*
 309                  * Go forward.
 310                  */
 311                 p = p->prev;
 312                 if (ch_seek(p->pos))
 313                         return (0);
 314                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 315                 {
 316                         /*
 317                          * Allow a signal to abort this loop.
 318                          */
 319                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 320                         if (ABORT_SIGS()) {
 321                                 abort_long();
 322                                 return (0);
 323                         }
 324                         if (cpos == NULL_POSITION)
 325                                 return (0);
 326                         longish();
 327                 }
 328                 /*
 329                  * We might as well cache it.
 330                  */
 331                 add_lnum(linenum, cpos);
 332                 /*
 333                  * If the given position is not at the start of a line,
 334                  * make sure we return the correct line number.
 335                  */
 336                 if (cpos > pos)
 337                         linenum--;
 338         } else
 339         {
 340                 /*
 341                  * Go backward.
 342                  */
 343                 if (ch_seek(p->pos))
 344                         return (0);
 345                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
 346                 {
 347                         /*
 348                          * Allow a signal to abort this loop.
 349                          */
 350                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 351                         if (ABORT_SIGS()) {
 352                                 abort_long();
 353                                 return (0);
 354                         }
 355                         if (cpos == NULL_POSITION)
 356                                 return (0);
 357                         longish();
 358                 }
 359                 /*
 360                  * We might as well cache it.
 361                  */
 362                 add_lnum(linenum, cpos);
 363         }
 364         loopcount = 0;
 365         return (linenum);
 366 }
 367
 368 /*
 369  * Find the position of a given line number.
 370  * Return NULL_POSITION if we can't figure it out.
 371  */
 372 public POSITION find_pos(LINENUM linenum)
 373 {
 374         struct linenum_info *p;
 375         POSITION cpos;
 376         LINENUM clinenum;
 377
 378         if (linenum <= 1)
 379                 /*
 380                  * Line number 1 is beginning of file.
 381                  */
 382                 return (ch_zero());
 383
 384         /*
 385          * Find the entry nearest to the line number we want.
 386          */
 387         for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
 388                 continue;
 389         if (p->line == linenum)
 390                 /* Found it exactly. */
 391                 return (p->pos);
 392
 393         if (p == &anchor || linenum - p->prev->line < p->line - linenum)
 394         {
 395                 /*
 396                  * Go forward.
 397                  */
 398                 p = p->prev;
 399                 if (ch_seek(p->pos))
 400                         return (NULL_POSITION);
 401                 for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
 402                 {
 403                         /*
 404                          * Allow a signal to abort this loop.
 405                          */
 406                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 407                         if (ABORT_SIGS())
 408                                 return (NULL_POSITION);
 409                         if (cpos == NULL_POSITION)
 410                                 return (NULL_POSITION);
 411                 }
 412         } else
 413         {
 414                 /*
 415                  * Go backward.
 416                  */
 417                 if (ch_seek(p->pos))
 418                         return (NULL_POSITION);
 419                 for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
 420                 {
 421                         /*
 422                          * Allow a signal to abort this loop.
 423                          */
 424                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 425                         if (ABORT_SIGS())
 426                                 return (NULL_POSITION);
 427                         if (cpos == NULL_POSITION)
 428                                 return (NULL_POSITION);
 429                 }
 430         }
 431         /*
 432          * We might as well cache it.
 433          */
 434         add_lnum(clinenum, cpos);
 435         return (cpos);
 436 }
 437
 438 /*
 439  * Return the line number of the "current" line.
 440  * The argument "where" tells which line is to be considered
 441  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
 442  */
 443 public LINENUM currline(int where)
 444 {
 445         POSITION pos;
 446         POSITION len;
 447         LINENUM linenum;
 448
 449         pos = position(where);
 450         len = ch_length();
 451         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
 452                 pos = position(++where);
 453         if (pos == NULL_POSITION)
 454                 pos = len;
 455         linenum = find_linenum(pos);
 456         if (pos == len)
 457                 linenum--;
 458         return (linenum);
 459 }
 460
 461 /*
 462  * Scan entire file, counting line numbers.
 463  */
 464 public void scan_eof(void)
 465 {
 466         POSITION pos = ch_zero();
 467         LINENUM linenum = 0;
 468
 469         if (ch_seek(0))
 470                 return;
 471         ierror("Determining length of file", NULL_PARG);
 472         /*
 473          * scanning_eof prevents the "Waiting for data" message from
 474          * overwriting "Determining length of file".
 475          */
 476         scanning_eof = TRUE;
 477         while (pos != NULL_POSITION)
 478         {
 479                 /* For efficiency, only add one every 256 line numbers. */
 480                 if ((linenum++ % 256) == 0)
 481                         add_lnum(linenum, pos);
 482                 pos = forw_raw_line(pos, (char **)NULL, (int *)NULL);
 483                 if (ABORT_SIGS())
 484                         break;
 485         }
 486         scanning_eof = FALSE;
 487 }
 488
 489 /*
 490  * Return a line number adjusted for display
 491  * (handles the --no-number-headers option).
 492  */
 493 public LINENUM vlinenum(LINENUM linenum)
 494 {
 495         if (nonum_headers)
 496                 linenum = (linenum < header_lines) ? 0 : linenum - header_lines;
 497         return linenum;
 498 }