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