contrib/less-4/linenum.c

   1 /*
   2  * Copyright (C) 1984-2007  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   50                      /* Size of line number pool */
  60
  61 #define LONGTIME        (2)             /* In seconds */
  62
  63 public int lnloop = 0;                  /* Are we in the line num loop? */
  64
  65 static struct linenum_info anchor;      /* Anchor of the list */
  66 static struct linenum_info *freelist;   /* Anchor of the unused entries */
  67 static struct linenum_info pool[NPOOL]; /* The pool itself */
  68 static struct linenum_info *spare;              /* We always keep one spare entry */
  69
  70 extern int linenums;
  71 extern int sigs;
  72 extern int sc_height;
  73
  74 /*
  75  * Initialize the line number structures.
  76  */
  77         public void
  78 clr_linenum()
  79 {
  80         register 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
 106 calcgap(p)
 107         register struct linenum_info *p;
 108 {
 109         /*
 110          * Don't bother to compute a gap for the anchor.
 111          * Also don't compute a gap for the last one in the list.
 112          * The gap for that last one should be considered infinite,
 113          * but we never look at it anyway.
 114          */
 115         if (p == &anchor || p->next == &anchor)
 116                 return;
 117         p->gap = p->next->pos - p->prev->pos;
 118 }
 119
 120 /*
 121  * Add a new line number to the cache.
 122  * The specified position (pos) should be the file position of the
 123  * FIRST character in the specified line.
 124  */
 125         public void
 126 add_lnum(linenum, pos)
 127         LINENUM linenum;
 128         POSITION pos;
 129 {
 130         register struct linenum_info *p;
 131         register struct linenum_info *new;
 132         register struct linenum_info *nextp;
 133         register struct linenum_info *prevp;
 134         register POSITION mingap;
 135
 136         /*
 137          * Find the proper place in the list for the new one.
 138          * The entries are sorted by position.
 139          */
 140         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 141                 if (p->line == linenum)
 142                         /* We already have this one. */
 143                         return;
 144         nextp = p;
 145         prevp = p->prev;
 146
 147         if (freelist != NULL)
 148         {
 149                 /*
 150                  * We still have free (unused) entries.
 151                  * Use one of them.
 152                  */
 153                 new = freelist;
 154                 freelist = freelist->next;
 155         } else
 156         {
 157                 /*
 158                  * No free entries.
 159                  * Use the "spare" entry.
 160                  */
 161                 new = spare;
 162                 spare = NULL;
 163         }
 164
 165         /*
 166          * Fill in the fields of the new entry,
 167          * and insert it into the proper place in the list.
 168          */
 169         new->next = nextp;
 170         new->prev = prevp;
 171         new->pos = pos;
 172         new->line = linenum;
 173
 174         nextp->prev = new;
 175         prevp->next = new;
 176
 177         /*
 178          * Recalculate gaps for the new entry and the neighboring entries.
 179          */
 180         calcgap(new);
 181         calcgap(nextp);
 182         calcgap(prevp);
 183
 184         if (spare == NULL)
 185         {
 186                 /*
 187                  * We have used the spare entry.
 188                  * Scan the list to find the one with the smallest
 189                  * gap, take it out and make it the spare.
 190                  * We should never remove the last one, so stop when
 191                  * we get to p->next == &anchor.  This also avoids
 192                  * looking at the gap of the last one, which is
 193                  * not computed by calcgap.
 194                  */
 195                 mingap = anchor.next->gap;
 196                 for (p = anchor.next;  p->next != &anchor;  p = p->next)
 197                 {
 198                         if (p->gap <= mingap)
 199                         {
 200                                 spare = p;
 201                                 mingap = p->gap;
 202                         }
 203                 }
 204                 spare->next->prev = spare->prev;
 205                 spare->prev->next = spare->next;
 206         }
 207 }
 208
 209 /*
 210  * If we get stuck in a long loop trying to figure out the
 211  * line number, print a message to tell the user what we're doing.
 212  */
 213         static void
 214 longloopmessage()
 215 {
 216         ierror("Calculating line numbers", NULL_PARG);
 217         /*
 218          * Set the lnloop flag here, so if the user interrupts while
 219          * we are calculating line numbers, the signal handler will
 220          * turn off line numbers (linenums=0).
 221          */
 222         lnloop = 1;
 223 }
 224
 225 static int loopcount;
 226 #if HAVE_TIME
 227 static long startime;
 228 #endif
 229
 230         static void
 231 longish()
 232 {
 233 #if HAVE_TIME
 234         if (loopcount >= 0 && ++loopcount > 100)
 235         {
 236                 loopcount = 0;
 237                 if (get_time() >= startime + LONGTIME)
 238                 {
 239                         longloopmessage();
 240                         loopcount = -1;
 241                 }
 242         }
 243 #else
 244         if (loopcount >= 0 && ++loopcount > LONGLOOP)
 245         {
 246                 longloopmessage();
 247                 loopcount = -1;
 248         }
 249 #endif
 250 }
 251
 252 /*
 253  * Find the line number associated with a given position.
 254  * Return 0 if we can't figure it out.
 255  */
 256         public LINENUM
 257 find_linenum(pos)
 258         POSITION pos;
 259 {
 260         register struct linenum_info *p;
 261         register LINENUM linenum;
 262         POSITION cpos;
 263
 264         if (!linenums)
 265                 /*
 266                  * We're not using line numbers.
 267                  */
 268                 return (0);
 269         if (pos == NULL_POSITION)
 270                 /*
 271                  * Caller doesn't know what he's talking about.
 272                  */
 273                 return (0);
 274         if (pos <= ch_zero())
 275                 /*
 276                  * Beginning of file is always line number 1.
 277                  */
 278                 return (1);
 279
 280         /*
 281          * Find the entry nearest to the position we want.
 282          */
 283         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 284                 continue;
 285         if (p->pos == pos)
 286                 /* Found it exactly. */
 287                 return (p->line);
 288
 289         /*
 290          * This is the (possibly) time-consuming part.
 291          * We start at the line we just found and start
 292          * reading the file forward or backward till we
 293          * get to the place we want.
 294          *
 295          * First decide whether we should go forward from the
 296          * previous one or backwards from the next one.
 297          * The decision is based on which way involves
 298          * traversing fewer bytes in the file.
 299          */
 300 #if HAVE_TIME
 301         startime = get_time();
 302 #endif
 303         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 304         {
 305                 /*
 306                  * Go forward.
 307                  */
 308                 p = p->prev;
 309                 if (ch_seek(p->pos))
 310                         return (0);
 311                 loopcount = 0;
 312                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 313                 {
 314                         /*
 315                          * Allow a signal to abort this loop.
 316                          */
 317                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 318                         if (ABORT_SIGS() || cpos == NULL_POSITION)
 319                                 return (0);
 320                         longish();
 321                 }
 322                 lnloop = 0;
 323                 /*
 324                  * We might as well cache it.
 325                  */
 326                 add_lnum(linenum, cpos);
 327                 /*
 328                  * If the given position is not at the start of a line,
 329                  * make sure we return the correct line number.
 330                  */
 331                 if (cpos > pos)
 332                         linenum--;
 333         } else
 334         {
 335                 /*
 336                  * Go backward.
 337                  */
 338                 if (ch_seek(p->pos))
 339                         return (0);
 340                 loopcount = 0;
 341                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
 342                 {
 343                         /*
 344                          * Allow a signal to abort this loop.
 345                          */
 346                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 347                         if (ABORT_SIGS() || cpos == NULL_POSITION)
 348                                 return (0);
 349                         longish();
 350                 }
 351                 lnloop = 0;
 352                 /*
 353                  * We might as well cache it.
 354                  */
 355                 add_lnum(linenum, cpos);
 356         }
 357
 358         return (linenum);
 359 }
 360
 361 /*
 362  * Find the position of a given line number.
 363  * Return NULL_POSITION if we can't figure it out.
 364  */
 365         public POSITION
 366 find_pos(linenum)
 367         LINENUM linenum;
 368 {
 369         register struct linenum_info *p;
 370         POSITION cpos;
 371         LINENUM clinenum;
 372
 373         if (linenum <= 1)
 374                 /*
 375                  * Line number 1 is beginning of file.
 376                  */
 377                 return (ch_zero());
 378
 379         /*
 380          * Find the entry nearest to the line number we want.
 381          */
 382         for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
 383                 continue;
 384         if (p->line == linenum)
 385                 /* Found it exactly. */
 386                 return (p->pos);
 387
 388         if (p == &anchor || linenum - p->prev->line < p->line - linenum)
 389         {
 390                 /*
 391                  * Go forward.
 392                  */
 393                 p = p->prev;
 394                 if (ch_seek(p->pos))
 395                         return (NULL_POSITION);
 396                 for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
 397                 {
 398                         /*
 399                          * Allow a signal to abort this loop.
 400                          */
 401                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 402                         if (ABORT_SIGS() || cpos == NULL_POSITION)
 403                                 return (NULL_POSITION);
 404                 }
 405         } else
 406         {
 407                 /*
 408                  * Go backward.
 409                  */
 410                 if (ch_seek(p->pos))
 411                         return (NULL_POSITION);
 412                 for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
 413                 {
 414                         /*
 415                          * Allow a signal to abort this loop.
 416                          */
 417                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 418                         if (ABORT_SIGS() || cpos == NULL_POSITION)
 419                                 return (NULL_POSITION);
 420                 }
 421         }
 422         /*
 423          * We might as well cache it.
 424          */
 425         add_lnum(clinenum, cpos);
 426         return (cpos);
 427 }
 428
 429 /*
 430  * Return the line number of the "current" line.
 431  * The argument "where" tells which line is to be considered
 432  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
 433  */
 434         public LINENUM
 435 currline(where)
 436         int where;
 437 {
 438         POSITION pos;
 439         POSITION len;
 440         LINENUM linenum;
 441
 442         pos = position(where);
 443         len = ch_length();
 444         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
 445                 pos = position(++where);
 446         if (pos == NULL_POSITION)
 447                 pos = len;
 448         linenum = find_linenum(pos);
 449         if (pos == len)
 450                 linenum--;
 451         return (linenum);
 452 }