contrib/less/linenum.c

   1 /*
   2  * Copyright (C) 1984-2011  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 about less, or for information on how to
   8  * contact the author, see the README file.
   9  */
  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 "less.h"
  37
  38 /*
  39  * Structure to keep track of a line number and the associated file position.
  40  * A doubly-linked circular list of line numbers is kept ordered by line number.
  41  */
  42 struct linenum_info
  43 {
  44         struct linenum_info *next;      /* Link to next in the list */
  45         struct linenum_info *prev;      /* Line to previous in the list */
  46         POSITION pos;                   /* File position */
  47         POSITION gap;                   /* Gap between prev and next */
  48         LINENUM line;                   /* Line number */
  49 };
  50 /*
  51  * "gap" needs some explanation: the gap of any particular line number
  52  * is the distance between the previous one and the next one in the list.
  53  * ("Distance" means difference in file position.)  In other words, the
  54  * gap of a line number is the gap which would be introduced if this
  55  * line number were deleted.  It is used to decide which one to replace
  56  * when we have a new one to insert and the table is full.
  57  */
  58
  59 #define NPOOL   200                     /* Size of line number pool */
  60
  61 #define LONGTIME        (2)             /* In seconds */
  62
  63 static struct linenum_info anchor;      /* Anchor of the list */
  64 static struct linenum_info *freelist;   /* Anchor of the unused entries */
  65 static struct linenum_info pool[NPOOL]; /* The pool itself */
  66 static struct linenum_info *spare;              /* We always keep one spare entry */
  67
  68 extern int linenums;
  69 extern int sigs;
  70 extern int sc_height;
  71 extern int screen_trashed;
  72
  73 /*
  74  * Initialize the line number structures.
  75  */
  76         public void
  77 clr_linenum()
  78 {
  79         register 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
 105 calcgap(p)
 106         register struct linenum_info *p;
 107 {
 108         /*
 109          * Don't bother to compute a gap for the anchor.
 110          * Also don't compute a gap for the last one in the list.
 111          * The gap for that last one should be considered infinite,
 112          * but we never look at it anyway.
 113          */
 114         if (p == &anchor || p->next == &anchor)
 115                 return;
 116         p->gap = p->next->pos - p->prev->pos;
 117 }
 118
 119 /*
 120  * Add a new line number to the cache.
 121  * The specified position (pos) should be the file position of the
 122  * FIRST character in the specified line.
 123  */
 124         public void
 125 add_lnum(linenum, pos)
 126         LINENUM linenum;
 127         POSITION pos;
 128 {
 129         register struct linenum_info *p;
 130         register struct linenum_info *new;
 131         register struct linenum_info *nextp;
 132         register struct linenum_info *prevp;
 133         register POSITION 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                 /*
 149                  * We still have free (unused) entries.
 150                  * Use one of them.
 151                  */
 152                 new = freelist;
 153                 freelist = freelist->next;
 154         } else
 155         {
 156                 /*
 157                  * No free entries.
 158                  * Use the "spare" entry.
 159                  */
 160                 new = spare;
 161                 spare = NULL;
 162         }
 163
 164         /*
 165          * Fill in the fields of the new entry,
 166          * and insert it into the proper place in the list.
 167          */
 168         new->next = nextp;
 169         new->prev = prevp;
 170         new->pos = pos;
 171         new->line = linenum;
 172
 173         nextp->prev = new;
 174         prevp->next = new;
 175
 176         /*
 177          * Recalculate gaps for the new entry and the neighboring entries.
 178          */
 179         calcgap(new);
 180         calcgap(nextp);
 181         calcgap(prevp);
 182
 183         if (spare == NULL)
 184         {
 185                 /*
 186                  * We have used the spare entry.
 187                  * Scan the list to find the one with the smallest
 188                  * gap, take it out and make it the spare.
 189                  * We should never remove the last one, so stop when
 190                  * we get to p->next == &anchor.  This also avoids
 191                  * looking at the gap of the last one, which is
 192                  * not computed by calcgap.
 193                  */
 194                 mingap = anchor.next->gap;
 195                 for (p = anchor.next;  p->next != &anchor;  p = p->next)
 196                 {
 197                         if (p->gap <= mingap)
 198                         {
 199                                 spare = p;
 200                                 mingap = p->gap;
 201                         }
 202                 }
 203                 spare->next->prev = spare->prev;
 204                 spare->prev->next = spare->next;
 205         }
 206 }
 207
 208 /*
 209  * If we get stuck in a long loop trying to figure out the
 210  * line number, print a message to tell the user what we're doing.
 211  */
 212         static void
 213 longloopmessage()
 214 {
 215         ierror("Calculating line numbers", NULL_PARG);
 216 }
 217
 218 static int loopcount;
 219 #if HAVE_TIME
 220 static long startime;
 221 #endif
 222
 223         static void
 224 longish()
 225 {
 226 #if HAVE_TIME
 227         if (loopcount >= 0 && ++loopcount > 100)
 228         {
 229                 loopcount = 0;
 230                 if (get_time() >= startime + LONGTIME)
 231                 {
 232                         longloopmessage();
 233                         loopcount = -1;
 234                 }
 235         }
 236 #else
 237         if (loopcount >= 0 && ++loopcount > LONGLOOP)
 238         {
 239                 longloopmessage();
 240                 loopcount = -1;
 241         }
 242 #endif
 243 }
 244
 245 /*
 246  * Turn off line numbers because the user has interrupted
 247  * a lengthy line number calculation.
 248  */
 249         static void
 250 abort_long()
 251 {
 252         if (linenums == OPT_ONPLUS)
 253                 /*
 254                  * We were displaying line numbers, so need to repaint.
 255                  */
 256                 screen_trashed = 1;
 257         linenums = 0;
 258         error("Line numbers turned off", NULL_PARG);
 259 }
 260
 261 /*
 262  * Find the line number associated with a given position.
 263  * Return 0 if we can't figure it out.
 264  */
 265         public LINENUM
 266 find_linenum(pos)
 267         POSITION pos;
 268 {
 269         register struct linenum_info *p;
 270         register LINENUM linenum;
 271         POSITION cpos;
 272
 273         if (!linenums)
 274                 /*
 275                  * We're not using line numbers.
 276                  */
 277                 return (0);
 278         if (pos == NULL_POSITION)
 279                 /*
 280                  * Caller doesn't know what he's talking about.
 281                  */
 282                 return (0);
 283         if (pos <= ch_zero())
 284                 /*
 285                  * Beginning of file is always line number 1.
 286                  */
 287                 return (1);
 288
 289         /*
 290          * Find the entry nearest to the position we want.
 291          */
 292         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 293                 continue;
 294         if (p->pos == pos)
 295                 /* Found it exactly. */
 296                 return (p->line);
 297
 298         /*
 299          * This is the (possibly) time-consuming part.
 300          * We start at the line we just found and start
 301          * reading the file forward or backward till we
 302          * get to the place we want.
 303          *
 304          * First decide whether we should go forward from the
 305          * previous one or backwards from the next one.
 306          * The decision is based on which way involves
 307          * traversing fewer bytes in the file.
 308          */
 309 #if HAVE_TIME
 310         startime = get_time();
 311 #endif
 312         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 313         {
 314                 /*
 315                  * Go forward.
 316                  */
 317                 p = p->prev;
 318                 if (ch_seek(p->pos))
 319                         return (0);
 320                 loopcount = 0;
 321                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 322                 {
 323                         /*
 324                          * Allow a signal to abort this loop.
 325                          */
 326                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 327                         if (ABORT_SIGS()) {
 328                                 abort_long();
 329                                 return (0);
 330                         }
 331                         if (cpos == NULL_POSITION)
 332                                 return (0);
 333                         longish();
 334                 }
 335                 /*
 336                  * We might as well cache it.
 337                  */
 338                 add_lnum(linenum, cpos);
 339                 /*
 340                  * If the given position is not at the start of a line,
 341                  * make sure we return the correct line number.
 342                  */
 343                 if (cpos > pos)
 344                         linenum--;
 345         } else
 346         {
 347                 /*
 348                  * Go backward.
 349                  */
 350                 if (ch_seek(p->pos))
 351                         return (0);
 352                 loopcount = 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
 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         register 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 }