contrib/less/linenum.c

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