git.marmaro.de Git - mmh/blob - docs/historical/mh-6.8.5/miscellany/less-177/linenum.c

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