contrib/less/linenum.c

   1 /*
   2  * Copyright (C) 1984-2012  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()
  77 {
  78         register 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         register 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         register struct linenum_info *p;
 129         register struct linenum_info *new;
 130         register struct linenum_info *nextp;
 131         register struct linenum_info *prevp;
 132         register 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()
 213 {
 214         ierror("Calculating line numbers", NULL_PARG);
 215 }
 216
 217 static int loopcount;
 218 #if HAVE_TIME
 219 static long startime;
 220 #endif
 221
 222         static void
 223 longish()
 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()
 250 {
 251         if (linenums == OPT_ONPLUS)
 252                 /*
 253                  * We were displaying line numbers, so need to repaint.
 254                  */
 255                 screen_trashed = 1;
 256         linenums = 0;
 257         error("Line numbers turned off", NULL_PARG);
 258 }
 259
 260 /*
 261  * Find the line number associated with a given position.
 262  * Return 0 if we can't figure it out.
 263  */
 264         public LINENUM
 265 find_linenum(pos)
 266         POSITION pos;
 267 {
 268         register struct linenum_info *p;
 269         register LINENUM linenum;
 270         POSITION cpos;
 271
 272         if (!linenums)
 273                 /*
 274                  * We're not using line numbers.
 275                  */
 276                 return (0);
 277         if (pos == NULL_POSITION)
 278                 /*
 279                  * Caller doesn't know what he's talking about.
 280                  */
 281                 return (0);
 282         if (pos <= ch_zero())
 283                 /*
 284                  * Beginning of file is always line number 1.
 285                  */
 286                 return (1);
 287
 288         /*
 289          * Find the entry nearest to the position we want.
 290          */
 291         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 292                 continue;
 293         if (p->pos == pos)
 294                 /* Found it exactly. */
 295                 return (p->line);
 296
 297         /*
 298          * This is the (possibly) time-consuming part.
 299          * We start at the line we just found and start
 300          * reading the file forward or backward till we
 301          * get to the place we want.
 302          *
 303          * First decide whether we should go forward from the
 304          * previous one or backwards from the next one.
 305          * The decision is based on which way involves
 306          * traversing fewer bytes in the file.
 307          */
 308 #if HAVE_TIME
 309         startime = get_time();
 310 #endif
 311         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 312         {
 313                 /*
 314                  * Go forward.
 315                  */
 316                 p = p->prev;
 317                 if (ch_seek(p->pos))
 318                         return (0);
 319                 loopcount = 0;
 320                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 321                 {
 322                         /*
 323                          * Allow a signal to abort this loop.
 324                          */
 325                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 326                         if (ABORT_SIGS()) {
 327                                 abort_long();
 328                                 return (0);
 329                         }
 330                         if (cpos == NULL_POSITION)
 331                                 return (0);
 332                         longish();
 333                 }
 334                 /*
 335                  * We might as well cache it.
 336                  */
 337                 add_lnum(linenum, cpos);
 338                 /*
 339                  * If the given position is not at the start of a line,
 340                  * make sure we return the correct line number.
 341                  */
 342                 if (cpos > pos)
 343                         linenum--;
 344         } else
 345         {
 346                 /*
 347                  * Go backward.
 348                  */
 349                 if (ch_seek(p->pos))
 350                         return (0);
 351                 loopcount = 0;
 352                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
 353                 {
 354                         /*
 355                          * Allow a signal to abort this loop.
 356                          */
 357                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 358                         if (ABORT_SIGS()) {
 359                                 abort_long();
 360                                 return (0);
 361                         }
 362                         if (cpos == NULL_POSITION)
 363                                 return (0);
 364                         longish();
 365                 }
 366                 /*
 367                  * We might as well cache it.
 368                  */
 369                 add_lnum(linenum, cpos);
 370         }
 371
 372         return (linenum);
 373 }
 374
 375 /*
 376  * Find the position of a given line number.
 377  * Return NULL_POSITION if we can't figure it out.
 378  */
 379         public POSITION
 380 find_pos(linenum)
 381         LINENUM linenum;
 382 {
 383         register 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, (char **)NULL, (int *)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, (char **)NULL, (int *)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
 453 currline(where)
 454         int where;
 455 {
 456         POSITION pos;
 457         POSITION len;
 458         LINENUM linenum;
 459
 460         pos = position(where);
 461         len = ch_length();
 462         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
 463                 pos = position(++where);
 464         if (pos == NULL_POSITION)
 465                 pos = len;
 466         linenum = find_linenum(pos);
 467         if (pos == len)
 468                 linenum--;
 469         return (linenum);
 470 }