distrib/utils/more/linenum.c

   1 /*      $NetBSD: linenum.c,v 1.4 2003/08/07 09:28:00 agc Exp $  */
   2
   3 /*
   4  * Copyright (c) 1988 Mark Nudelman
   5  * Copyright (c) 1988, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #include <sys/cdefs.h>
  34 #ifndef lint
  35 #if 0
  36 static char sccsid[] = "@(#)linenum.c   8.1 (Berkeley) 6/6/93";
  37 #else
  38 __RCSID("$NetBSD: linenum.c,v 1.4 2003/08/07 09:28:00 agc Exp $");
  39 #endif
  40 #endif /* not lint */
  41
  42 /*
  43  * Code to handle displaying line numbers.
  44  *
  45  * Finding the line number of a given file position is rather tricky.
  46  * We don't want to just start at the beginning of the file and
  47  * count newlines, because that is slow for large files (and also
  48  * wouldn't work if we couldn't get to the start of the file; e.g.
  49  * if input is a long pipe).
  50  *
  51  * So we use the function add_lnum to cache line numbers.
  52  * We try to be very clever and keep only the more interesting
  53  * line numbers when we run out of space in our table.  A line
  54  * number is more interesting than another when it is far from
  55  * other line numbers.   For example, we'd rather keep lines
  56  * 100,200,300 than 100,101,300.  200 is more interesting than
  57  * 101 because 101 can be derived very cheaply from 100, while
  58  * 200 is more expensive to derive from 100.
  59  *
  60  * The function currline() returns the line number of a given
  61  * position in the file.  As a side effect, it calls add_lnum
  62  * to cache the line number.  Therefore currline is occasionally
  63  * called to make sure we cache line numbers often enough.
  64  */
  65
  66 #include <sys/types.h>
  67 #include <stdio.h>
  68 #include <time.h>
  69
  70 #include "less.h"
  71 #include "extern.h"
  72
  73 /*
  74  * Structure to keep track of a line number and the associated file position.
  75  * A doubly-linked circular list of line numbers is kept ordered by line number.
  76  */
  77 struct linenum
  78 {
  79         struct linenum *next;           /* Link to next in the list */
  80         struct linenum *prev;           /* Line to previous in the list */
  81         off_t pos;                      /* File position */
  82         off_t gap;                      /* Gap between prev and next */
  83         int line;                       /* Line number */
  84 };
  85 /*
  86  * "gap" needs some explanation: the gap of any particular line number
  87  * is the distance between the previous one and the next one in the list.
  88  * ("Distance" means difference in file position.)  In other words, the
  89  * gap of a line number is the gap which would be introduced if this
  90  * line number were deleted.  It is used to decide which one to replace
  91  * when we have a new one to insert and the table is full.
  92  */
  93
  94 #define NPOOL   50                      /* Size of line number pool */
  95
  96 #define LONGTIME        (2)             /* In seconds */
  97
  98 int lnloop = 0;                         /* Are we in the line num loop? */
  99
 100 static struct linenum anchor;           /* Anchor of the list */
 101 static struct linenum *freelist;        /* Anchor of the unused entries */
 102 static struct linenum pool[NPOOL];      /* The pool itself */
 103 static struct linenum *spare;           /* We always keep one spare entry */
 104
 105 static void calcgap __P((struct linenum *));
 106 static void longloopmessage __P((void));
 107 /*
 108  * Initialize the line number structures.
 109  */
 110 void
 111 clr_linenum()
 112 {
 113         struct linenum *p;
 114
 115         /*
 116          * Put all the entries on the free list.
 117          * Leave one for the "spare".
 118          */
 119         for (p = pool;  p < &pool[NPOOL-2];  p++)
 120                 p->next = p+1;
 121         pool[NPOOL-2].next = NULL;
 122         freelist = pool;
 123
 124         spare = &pool[NPOOL-1];
 125
 126         /*
 127          * Initialize the anchor.
 128          */
 129         anchor.next = anchor.prev = &anchor;
 130         anchor.gap = 0;
 131         anchor.pos = (off_t)0;
 132         anchor.line = 1;
 133 }
 134
 135 /*
 136  * Calculate the gap for an entry.
 137  */
 138 static void
 139 calcgap(p)
 140         struct linenum *p;
 141 {
 142         /*
 143          * Don't bother to compute a gap for the anchor.
 144          * Also don't compute a gap for the last one in the list.
 145          * The gap for that last one should be considered infinite,
 146          * but we never look at it anyway.
 147          */
 148         if (p == &anchor || p->next == &anchor)
 149                 return;
 150         p->gap = p->next->pos - p->prev->pos;
 151 }
 152
 153 /*
 154  * Add a new line number to the cache.
 155  * The specified position (pos) should be the file position of the
 156  * FIRST character in the specified line.
 157  */
 158 void
 159 add_lnum(line, pos)
 160         int line;
 161         off_t pos;
 162 {
 163         struct linenum *p;
 164         struct linenum *new;
 165         struct linenum *nextp;
 166         struct linenum *prevp;
 167         off_t mingap;
 168
 169         /*
 170          * Find the proper place in the list for the new one.
 171          * The entries are sorted by position.
 172          */
 173         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
 174                 if (p->line == line)
 175                         /* We already have this one. */
 176                         return;
 177         nextp = p;
 178         prevp = p->prev;
 179
 180         if (freelist != NULL)
 181         {
 182                 /*
 183                  * We still have free (unused) entries.
 184                  * Use one of them.
 185                  */
 186                 new = freelist;
 187                 freelist = freelist->next;
 188         } else
 189         {
 190                 /*
 191                  * No free entries.
 192                  * Use the "spare" entry.
 193                  */
 194                 new = spare;
 195                 spare = NULL;
 196         }
 197
 198         /*
 199          * Fill in the fields of the new entry,
 200          * and insert it into the proper place in the list.
 201          */
 202         new->next = nextp;
 203         new->prev = prevp;
 204         new->pos = pos;
 205         new->line = line;
 206
 207         nextp->prev = new;
 208         prevp->next = new;
 209
 210         /*
 211          * Recalculate gaps for the new entry and the neighboring entries.
 212          */
 213         calcgap(new);
 214         calcgap(nextp);
 215         calcgap(prevp);
 216
 217         if (spare == NULL)
 218         {
 219                 /*
 220                  * We have used the spare entry.
 221                  * Scan the list to find the one with the smallest
 222                  * gap, take it out and make it the spare.
 223                  * We should never remove the last one, so stop when
 224                  * we get to p->next == &anchor.  This also avoids
 225                  * looking at the gap of the last one, which is
 226                  * not computed by calcgap.
 227                  */
 228                 mingap = anchor.next->gap;
 229                 for (p = anchor.next;  p->next != &anchor;  p = p->next)
 230                 {
 231                         if (p->gap <= mingap)
 232                         {
 233                                 spare = p;
 234                                 mingap = p->gap;
 235                         }
 236                 }
 237                 spare->next->prev = spare->prev;
 238                 spare->prev->next = spare->next;
 239         }
 240 }
 241
 242 /*
 243  * If we get stuck in a long loop trying to figure out the
 244  * line number, print a message to tell the user what we're doing.
 245  */
 246 static void
 247 longloopmessage()
 248 {
 249         ierror("Calculating line numbers");
 250         /*
 251          * Set the lnloop flag here, so if the user interrupts while
 252          * we are calculating line numbers, the signal handler will
 253          * turn off line numbers (linenums=0).
 254          */
 255         lnloop = 1;
 256 }
 257
 258 /*
 259  * Find the line number associated with a given position.
 260  * Return 0 if we can't figure it out.
 261  */
 262 int
 263 find_linenum(pos)
 264         off_t pos;
 265 {
 266         struct linenum *p;
 267         int lno;
 268         int loopcount;
 269         off_t cpos;
 270         time_t startime;
 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 == (off_t)0)
 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         flush();
 309         (void)time(&startime);
 310         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
 311         {
 312                 /*
 313                  * Go forward.
 314                  */
 315                 p = p->prev;
 316                 if (ch_seek(p->pos))
 317                         return (0);
 318                 loopcount = 0;
 319                 for (lno = p->line, cpos = p->pos;  cpos < pos;  lno++)
 320                 {
 321                         /*
 322                          * Allow a signal to abort this loop.
 323                          */
 324                         cpos = forw_raw_line(cpos);
 325                         if (sigs || cpos == NULL_POSITION)
 326                                 return (0);
 327                         if (loopcount >= 0 && ++loopcount > 100) {
 328                                 loopcount = 0;
 329                                 if (time((time_t *)NULL)
 330                                     >= startime + LONGTIME) {
 331                                         longloopmessage();
 332                                         loopcount = -1;
 333                                 }
 334                         }
 335                 }
 336                 lnloop = 0;
 337                 /*
 338                  * If the given position is not at the start of a line,
 339                  * make sure we return the correct line number.
 340                  */
 341                 if (cpos > pos)
 342                         lno--;
 343         } else
 344         {
 345                 /*
 346                  * Go backward.
 347                  */
 348                 if (ch_seek(p->pos))
 349                         return (0);
 350                 loopcount = 0;
 351                 for (lno = p->line, cpos = p->pos;  cpos > pos;  lno--)
 352                 {
 353                         /*
 354                          * Allow a signal to abort this loop.
 355                          */
 356                         cpos = back_raw_line(cpos);
 357                         if (sigs || cpos == NULL_POSITION)
 358                                 return (0);
 359                         if (loopcount >= 0 && ++loopcount > 100) {
 360                                 loopcount = 0;
 361                                 if (time((time_t *)NULL)
 362                                     >= startime + LONGTIME) {
 363                                         longloopmessage();
 364                                         loopcount = -1;
 365                                 }
 366                         }
 367                 }
 368                 lnloop = 0;
 369         }
 370
 371         /*
 372          * We might as well cache it.
 373          */
 374         add_lnum(lno, cpos);
 375         return (lno);
 376 }
 377
 378 /*
 379  * Return the line number of the "current" line.
 380  * The argument "where" tells which line is to be considered
 381  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
 382  */
 383 int
 384 currline(where)
 385         int where;
 386 {
 387         off_t pos;
 388
 389         if ((pos = position(where)) == NULL_POSITION)
 390                 pos = ch_length();
 391         return(find_linenum(pos));
 392 }