external/bsd/less/dist/linenum.c

   1 /*      $NetBSD: linenum.c,v 1.4 2013/09/04 19:44:21 tron Exp $ */
   2
   3 /*
   4  * Copyright (C) 1984-2012  Mark Nudelman
   5  *
   6  * You may distribute under the terms of either the GNU General Public
   7  * License or the Less License, as specified in the README file.
   8  *
   9  * For more information, see the README file.
  10  */
  11
  12
  13 /*
  14  * Code to handle displaying line numbers.
  15  *
  16  * Finding the line number of a given file position is rather tricky.
  17  * We don't want to just start at the beginning of the file and
  18  * count newlines, because that is slow for large files (and also
  19  * wouldn't work if we couldn't get to the start of the file; e.g.
  20  * if input is a long pipe).
  21  *
  22  * So we use the function add_lnum to cache line numbers.
  23  * We try to be very clever and keep only the more interesting
  24  * line numbers when we run out of space in our table.  A line
  25  * number is more interesting than another when it is far from
  26  * other line numbers.   For example, we'd rather keep lines
  27  * 100,200,300 than 100,101,300.  200 is more interesting than
  28  * 101 because 101 can be derived very cheaply from 100, while
  29  * 200 is more expensive to derive from 100.
  30  *
  31  * The function currline() returns the line number of a given
  32  * position in the file.  As a side effect, it calls add_lnum
  33  * to cache the line number.  Therefore currline is occasionally
  34  * called to make sure we cache line numbers often enough.
  35  */
  36
  37 #include "less.h"
  38
  39 /*
  40  * Structure to keep track of a line number and the associated file position.
  41  * A doubly-linked circular list of line numbers is kept ordered by line number.
  42  */
  43 struct linenum_info
  44 {
  45         struct linenum_info *next;      /* Link to next in the list */
  46         struct linenum_info *prev;      /* Line to previous in the list */
  47         POSITION pos;                   /* File position */
  48         POSITION gap;                   /* Gap between prev and next */
  49         LINENUM line;                   /* Line number */
  50 };
  51 /*
  52  * "gap" needs some explanation: the gap of any particular line number
  53  * is the distance between the previous one and the next one in the list.
  54  * ("Distance" means difference in file position.)  In other words, the
  55  * gap of a line number is the gap which would be introduced if this
  56  * line number were deleted.  It is used to decide which one to replace
  57  * when we have a new one to insert and the table is full.
  58  */
  59
  60 #define NPOOL   200                     /* Size of line number pool */
  61
  62 #define LONGTIME        (2)             /* In seconds */
  63
  64 static struct linenum_info anchor;      /* Anchor of the list */
  65 static struct linenum_info *freelist;   /* Anchor of the unused entries */
  66 static struct linenum_info pool[NPOOL]; /* The pool itself */
  67 static struct linenum_info *spare;              /* We always keep one spare entry */
  68
  69 extern int linenums;
  70 extern int sigs;
  71 extern int sc_height;
  72 extern int screen_trashed;
  73
  74 static void calcgap __P((struct linenum_info *));
  75 static void longloopmessage __P((void));
  76 static void longish __P((void));
  77
  78 /*
  79  * Initialize the line number structures.
  80  */
  81         public void
  82 clr_linenum()
  83 {
  84         register struct linenum_info *p;
  85
  86         /*
  87          * Put all the entries on the free list.
  88          * Leave one for the "spare".
  89          */
  90         for (p = pool;  p < &pool[NPOOL-2];  p++)
  91                 p->next = p+1;
  92         pool[NPOOL-2].next = NULL;
  93         freelist = pool;
  94
  95         spare = &pool[NPOOL-1];
  96
  97         /*
  98          * Initialize the anchor.
  99          */
 100         anchor.next = anchor.prev = &anchor;
 101         anchor.gap = 0;
 102         anchor.pos = (POSITION)0;
 103         anchor.line = 1;
 104 }
 105
 106 /*
 107  * Calculate the gap for an entry.
 108  */
 109         static void
 110 calcgap(p)
 111         register struct linenum_info *p;
 112 {
 113         /*
 114          * Don't bother to compute a gap for the anchor.
 115          * Also don't compute a gap for the last one in the list.
 116          * The gap for that last one should be considered infinite,
 117          * but we never look at it anyway.
 118          */
 119         if (p == &anchor || p->next == &anchor)
 120                 return;
 121         p->gap = p->next->pos - p->prev->pos;
 122 }
 123
 124 /*
 125  * Add a new line number to the cache.
 126  * The specified position (pos) should be the file position of the
 127  * FIRST character in the specified line.
 128  */
 129         public void
 130 add_lnum(linenum, pos)
 131         LINENUM linenum;
 132         POSITION pos;
 133 {
 134         register struct linenum_info *p;
 135         register struct linenum_info *new;
 136         register struct linenum_info *nextp;
 137         register struct linenum_info *prevp;
 138         register POSITION mingap;
 139
 140         /*
 141          * Find the proper place in the list for the new one.
 142          * The entries are sorted by position.
 143          */
 144         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 145                 if (p->line == linenum)
 146                         /* We already have this one. */
 147                         return;
 148         nextp = p;
 149         prevp = p->prev;
 150
 151         if (freelist != NULL)
 152         {
 153                 /*
 154                  * We still have free (unused) entries.
 155                  * Use one of them.
 156                  */
 157                 new = freelist;
 158                 freelist = freelist->next;
 159         } else
 160         {
 161                 /*
 162                  * No free entries.
 163                  * Use the "spare" entry.
 164                  */
 165                 new = spare;
 166                 spare = NULL;
 167         }
 168
 169         /*
 170          * Fill in the fields of the new entry,
 171          * and insert it into the proper place in the list.
 172          */
 173         new->next = nextp;
 174         new->prev = prevp;
 175         new->pos = pos;
 176         new->line = linenum;
 177
 178         nextp->prev = new;
 179         prevp->next = new;
 180
 181         /*
 182          * Recalculate gaps for the new entry and the neighboring entries.
 183          */
 184         calcgap(new);
 185         calcgap(nextp);
 186         calcgap(prevp);
 187
 188         if (spare == NULL)
 189         {
 190                 /*
 191                  * We have used the spare entry.
 192                  * Scan the list to find the one with the smallest
 193                  * gap, take it out and make it the spare.
 194                  * We should never remove the last one, so stop when
 195                  * we get to p->next == &anchor.  This also avoids
 196                  * looking at the gap of the last one, which is
 197                  * not computed by calcgap.
 198                  */
 199                 mingap = anchor.next->gap;
 200                 for (p = anchor.next;  p->next != &anchor;  p = p->next)
 201                 {
 202                         if (p->gap <= mingap)
 203                         {
 204                                 spare = p;
 205                                 mingap = p->gap;
 206                         }
 207                 }
 208                 spare->next->prev = spare->prev;
 209                 spare->prev->next = spare->next;
 210         }
 211 }
 212
 213 /*
 214  * If we get stuck in a long loop trying to figure out the
 215  * line number, print a message to tell the user what we're doing.
 216  */
 217         static void
 218 longloopmessage()
 219 {
 220         ierror("Calculating line numbers", NULL_PARG);
 221 }
 222
 223 static int loopcount;
 224 #if HAVE_TIME
 225 static long startime;
 226 #endif
 227
 228         static void
 229 longish()
 230 {
 231 #if HAVE_TIME
 232         if (loopcount >= 0 && ++loopcount > 100)
 233         {
 234                 loopcount = 0;
 235                 if (get_time() >= startime + LONGTIME)
 236                 {
 237                         longloopmessage();
 238                         loopcount = -1;
 239                 }
 240         }
 241 #else
 242         if (loopcount >= 0 && ++loopcount > LONGLOOP)
 243         {
 244                 longloopmessage();
 245                 loopcount = -1;
 246         }
 247 #endif
 248 }
 249
 250 /*
 251  * Turn off line numbers because the user has interrupted
 252  * a lengthy line number calculation.
 253  */
 254         static void
 255 abort_long()
 256 {
 257         if (linenums == OPT_ONPLUS)
 258                 /*
 259                  * We were displaying line numbers, so need to repaint.
 260                  */
 261                 screen_trashed = 1;
 262         linenums = 0;
 263         error("Line numbers turned off", NULL_PARG);
 264 }
 265
 266 /*
 267  * Find the line number associated with a given position.
 268  * Return 0 if we can't figure it out.
 269  */
 270         public LINENUM
 271 find_linenum(pos)
 272         POSITION pos;
 273 {
 274         register struct linenum_info *p;
 275         register LINENUM linenum;
 276         POSITION cpos;
 277
 278         if (!linenums)
 279                 /*
 280                  * We're not using line numbers.
 281                  */
 282                 return (0);
 283         if (pos == NULL_POSITION)
 284                 /*
 285                  * Caller doesn't know what he's talking about.
 286                  */
 287                 return (0);
 288         if (pos <= ch_zero())
 289                 /*
 290                  * Beginning of file is always line number 1.
 291                  */
 292                 return (1);
 293
 294         /*
 295          * Find the entry nearest to the position we want.
 296          */
 297         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 298                 continue;
 299         if (p->pos == pos)
 300                 /* Found it exactly. */
 301                 return (p->line);
 302
 303         /*
 304          * This is the (possibly) time-consuming part.
 305          * We start at the line we just found and start
 306          * reading the file forward or backward till we
 307          * get to the place we want.
 308          *
 309          * First decide whether we should go forward from the
 310          * previous one or backwards from the next one.
 311          * The decision is based on which way involves
 312          * traversing fewer bytes in the file.
 313          */
 314 #if HAVE_TIME
 315         startime = get_time();
 316 #endif
 317         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 318         {
 319                 /*
 320                  * Go forward.
 321                  */
 322                 p = p->prev;
 323                 if (ch_seek(p->pos))
 324                         return (0);
 325                 loopcount = 0;
 326                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
 327                 {
 328                         /*
 329                          * Allow a signal to abort this loop.
 330                          */
 331                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 332                         if (ABORT_SIGS()) {
 333                                 abort_long();
 334                                 return (0);
 335                         }
 336                         if (cpos == NULL_POSITION)
 337                                 return (0);
 338                         longish();
 339                 }
 340                 /*
 341                  * We might as well cache it.
 342                  */
 343                 add_lnum(linenum, cpos);
 344                 /*
 345                  * If the given position is not at the start of a line,
 346                  * make sure we return the correct line number.
 347                  */
 348                 if (cpos > pos)
 349                         linenum--;
 350         } else
 351         {
 352                 /*
 353                  * Go backward.
 354                  */
 355                 if (ch_seek(p->pos))
 356                         return (0);
 357                 loopcount = 0;
 358                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
 359                 {
 360                         /*
 361                          * Allow a signal to abort this loop.
 362                          */
 363                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 364                         if (ABORT_SIGS()) {
 365                                 abort_long();
 366                                 return (0);
 367                         }
 368                         if (cpos == NULL_POSITION)
 369                                 return (0);
 370                         longish();
 371                 }
 372                 /*
 373                  * We might as well cache it.
 374                  */
 375                 add_lnum(linenum, cpos);
 376         }
 377
 378         return (linenum);
 379 }
 380
 381 /*
 382  * Find the position of a given line number.
 383  * Return NULL_POSITION if we can't figure it out.
 384  */
 385         public POSITION
 386 find_pos(linenum)
 387         LINENUM linenum;
 388 {
 389         register struct linenum_info *p;
 390         POSITION cpos;
 391         LINENUM clinenum;
 392
 393         if (linenum <= 1)
 394                 /*
 395                  * Line number 1 is beginning of file.
 396                  */
 397                 return (ch_zero());
 398
 399         /*
 400          * Find the entry nearest to the line number we want.
 401          */
 402         for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
 403                 continue;
 404         if (p->line == linenum)
 405                 /* Found it exactly. */
 406                 return (p->pos);
 407
 408         if (p == &anchor || linenum - p->prev->line < p->line - linenum)
 409         {
 410                 /*
 411                  * Go forward.
 412                  */
 413                 p = p->prev;
 414                 if (ch_seek(p->pos))
 415                         return (NULL_POSITION);
 416                 for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
 417                 {
 418                         /*
 419                          * Allow a signal to abort this loop.
 420                          */
 421                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
 422                         if (ABORT_SIGS())
 423                                 return (NULL_POSITION);
 424                         if (cpos == NULL_POSITION)
 425                                 return (NULL_POSITION);
 426                 }
 427         } else
 428         {
 429                 /*
 430                  * Go backward.
 431                  */
 432                 if (ch_seek(p->pos))
 433                         return (NULL_POSITION);
 434                 for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
 435                 {
 436                         /*
 437                          * Allow a signal to abort this loop.
 438                          */
 439                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
 440                         if (ABORT_SIGS())
 441                                 return (NULL_POSITION);
 442                         if (cpos == NULL_POSITION)
 443                                 return (NULL_POSITION);
 444                 }
 445         }
 446         /*
 447          * We might as well cache it.
 448          */
 449         add_lnum(clinenum, cpos);
 450         return (cpos);
 451 }
 452
 453 /*
 454  * Return the line number of the "current" line.
 455  * The argument "where" tells which line is to be considered
 456  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
 457  */
 458         public LINENUM
 459 currline(where)
 460         int where;
 461 {
 462         POSITION pos;
 463         POSITION len;
 464         LINENUM linenum;
 465
 466         pos = position(where);
 467         len = ch_length();
 468         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
 469                 pos = position(++where);
 470         if (pos == NULL_POSITION)
 471                 pos = len;
 472         linenum = find_linenum(pos);
 473         if (pos == len)
 474                 linenum--;
 475         return (linenum);
 476 }