contrib/less/linenum.c

   1 /*
   2  * Copyright (C) 1984-2015  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)
  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(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
 123 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
 209 longloopmessage(void)
 210 {
 211         ierror("Calculating line numbers", NULL_PARG);
 212 }
 213
 214 static int loopcount;
 215 #if HAVE_TIME
 216 static time_type startime;
 217 #endif
 218
 219         static void
 220 longish(void)
 221 {
 222 #if HAVE_TIME
 223         if (loopcount >= 0 && ++loopcount > 100)
 224         {
 225                 loopcount = 0;
 226                 if (get_time() >= startime + LONGTIME)
 227                 {
 228                         longloopmessage();
 229                         loopcount = -1;
 230                 }
 231         }
 232 #else
 233         if (loopcount >= 0 && ++loopcount > LONGLOOP)
 234         {
 235                 longloopmessage();
 236                 loopcount = -1;
 237         }
 238 #endif
 239 }
 240
 241 /*
 242  * Turn off line numbers because the user has interrupted
 243  * a lengthy line number calculation.
 244  */
 245         static void
 246 abort_long(void)
 247 {
 248         if (linenums == OPT_ONPLUS)
 249                 /*
 250                  * We were displaying line numbers, so need to repaint.
 251                  */
 252                 screen_trashed = 1;
 253         linenums = 0;
 254         error("Line numbers turned off", NULL_PARG);
 255 }
 256
 257 /*
 258  * Find the line number associated with a given position.
 259  * Return 0 if we can't figure it out.
 260  */
 261         public LINENUM
 262 find_linenum(POSITION pos)
 263 {
 264         struct linenum_info *p;
 265         LINENUM linenum;
 266         POSITION cpos;
 267
 268         if (!linenums)
 269                 /*
 270                  * We're not using line numbers.
 271                  */
 272                 return (0);
 273         if (pos == NULL_POSITION)
 274                 /*
 275                  * Caller doesn't know what he's talking about.
 276                  */
 277                 return (0);
 278         if (pos <= ch_zero())
 279                 /*
 280                  * Beginning of file is always line number 1.
 281                  */
 282                 return (1);
 283
 284         /*
 285          * Find the entry nearest to the position we want.
 286          */
 287         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 288                 continue;
 289         if (p->pos == pos)
 290                 /* Found it exactly. */
 291                 return (p->line);
 292
 293         /*
 294          * This is the (possibly) time-consuming part.
 295          * We start at the line we just found and start
 296          * reading the file forward or backward till we
 297          * get to the place we want.
 298          *
 299          * First decide whether we should go forward from the
 300          * previous one or backwards from the next one.
 301          * The decision is based on which way involves
 302          * traversing fewer bytes in the file.
 303          */
 304 #if HAVE_TIME
 305         startime = get_time();
 306 #endif
 307         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 308         {
 309                 /*
 310                  * Go forward.
 311                  */
 312                 p = p->prev;
 313                 if (ch_seek(p->pos))
 314                         return (0);
 315                 loopcount = 0;
 316                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 317                 {
 318                         /*
 319                          * Allow a signal to abort this loop.
 320                          */
 321                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 322                         if (ABORT_SIGS()) {
 323                                 abort_long();
 324                                 return (0);
 325                         }
 326                         if (cpos == NULL_POSITION)
 327                                 return (0);
 328                         longish();
 329                 }
 330                 /*
 331                  * We might as well cache it.
 332                  */
 333                 add_lnum(linenum, cpos);
 334                 /*
 335                  * If the given position is not at the start of a line,
 336                  * make sure we return the correct line number.
 337                  */
 338                 if (cpos > pos)
 339                         linenum--;
 340         } else
 341         {
 342                 /*
 343                  * Go backward.
 344                  */
 345                 if (ch_seek(p->pos))
 346                         return (0);
 347                 loopcount = 0;
 348                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
 349                 {
 350                         /*
 351                          * Allow a signal to abort this loop.
 352                          */
 353                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 354                         if (ABORT_SIGS()) {
 355                                 abort_long();
 356                                 return (0);
 357                         }
 358                         if (cpos == NULL_POSITION)
 359                                 return (0);
 360                         longish();
 361                 }
 362                 /*
 363                  * We might as well cache it.
 364                  */
 365                 add_lnum(linenum, cpos);
 366         }
 367
 368         return (linenum);
 369 }
 370
 371 /*
 372  * Find the position of a given line number.
 373  * Return NULL_POSITION if we can't figure it out.
 374  */
 375         public POSITION
 376 find_pos(LINENUM linenum)
 377 {
 378         struct linenum_info *p;
 379         POSITION cpos;
 380         LINENUM clinenum;
 381
 382         if (linenum <= 1)
 383                 /*
 384                  * Line number 1 is beginning of file.
 385                  */
 386                 return (ch_zero());
 387
 388         /*
 389          * Find the entry nearest to the line number we want.
 390          */
 391         for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
 392                 continue;
 393         if (p->line == linenum)
 394                 /* Found it exactly. */
 395                 return (p->pos);
 396
 397         if (p == &anchor || linenum - p->prev->line < p->line - linenum)
 398         {
 399                 /*
 400                  * Go forward.
 401                  */
 402                 p = p->prev;
 403                 if (ch_seek(p->pos))
 404                         return (NULL_POSITION);
 405                 for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
 406                 {
 407                         /*
 408                          * Allow a signal to abort this loop.
 409                          */
 410                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 411                         if (ABORT_SIGS())
 412                                 return (NULL_POSITION);
 413                         if (cpos == NULL_POSITION)
 414                                 return (NULL_POSITION);
 415                 }
 416         } else
 417         {
 418                 /*
 419                  * Go backward.
 420                  */
 421                 if (ch_seek(p->pos))
 422                         return (NULL_POSITION);
 423                 for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
 424                 {
 425                         /*
 426                          * Allow a signal to abort this loop.
 427                          */
 428                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 429                         if (ABORT_SIGS())
 430                                 return (NULL_POSITION);
 431                         if (cpos == NULL_POSITION)
 432                                 return (NULL_POSITION);
 433                 }
 434         }
 435         /*
 436          * We might as well cache it.
 437          */
 438         add_lnum(clinenum, cpos);
 439         return (cpos);
 440 }
 441
 442 /*
 443  * Return the line number of the "current" line.
 444  * The argument "where" tells which line is to be considered
 445  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
 446  */
 447         public LINENUM
 448 currline(int where)
 449 {
 450         POSITION pos;
 451         POSITION len;
 452         LINENUM linenum;
 453
 454         pos = position(where);
 455         len = ch_length();
 456         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
 457                 pos = position(++where);
 458         if (pos == NULL_POSITION)
 459                 pos = len;
 460         linenum = find_linenum(pos);
 461         if (pos == len)
 462                 linenum--;
 463         return (linenum);
 464 }