home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 6 File / 06-File.zip / less373.zip / linenum.c < prev    next >
C/C++ Source or Header  |  2002-01-14  |  10KB  |  453 lines
  1. /*
  2.  * Copyright (C) 1984-2000  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
  43. {
  44.     struct linenum *next;        /* Link to next in the list */
  45.     struct linenum *prev;        /* Line to previous in the list */
  46.     POSITION pos;            /* File position */
  47.     POSITION gap;            /* Gap between prev and next */
  48.     int 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 anchor;        /* Anchor of the list */
  66. static struct linenum *freelist;    /* Anchor of the unused entries */
  67. static struct linenum pool[NPOOL];    /* The pool itself */
  68. static struct linenum *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 *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 *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(lno, pos)
  127.     int lno;
  128.     POSITION pos;
  129. {
  130.     register struct linenum *p;
  131.     register struct linenum *new;
  132.     register struct linenum *nextp;
  133.     register struct linenum *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 == lno)
  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 = lno;
  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 int
  257. find_linenum(pos)
  258.     POSITION pos;
  259. {
  260.     register struct linenum *p;
  261.     register int lno;
  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 (lno = p->line, cpos = p->pos;  cpos < pos;  lno++)
  313.         {
  314.             /*
  315.              * Allow a signal to abort this loop.
  316.              */
  317.             cpos = forw_raw_line(cpos, (char **)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(lno, 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.             lno--;
  333.     } else
  334.     {
  335.         /*
  336.          * Go backward.
  337.          */
  338.         if (ch_seek(p->pos))
  339.             return (0);
  340.         loopcount = 0;
  341.         for (lno = p->line, cpos = p->pos;  cpos > pos;  lno--)
  342.         {
  343.             /*
  344.              * Allow a signal to abort this loop.
  345.              */
  346.             cpos = back_raw_line(cpos, (char **)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(lno, cpos);
  356.     }
  357.  
  358.     return (lno);
  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(lno)
  367.     int lno;
  368. {
  369.     register struct linenum *p;
  370.     POSITION cpos;
  371.     int clno;
  372.  
  373.     if (lno <= 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 < lno;  p = p->next)
  383.         continue;
  384.     if (p->line == lno)
  385.         /* Found it exactly. */
  386.         return (p->pos);
  387.  
  388.     if (p == &anchor || lno - p->prev->line < p->line - lno)
  389.     {
  390.         /*
  391.          * Go forward.
  392.          */
  393.         p = p->prev;
  394.         if (ch_seek(p->pos))
  395.             return (NULL_POSITION);
  396.         for (clno = p->line, cpos = p->pos;  clno < lno;  clno++)
  397.         {
  398.             /*
  399.              * Allow a signal to abort this loop.
  400.              */
  401.             cpos = forw_raw_line(cpos, (char **)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 (clno = p->line, cpos = p->pos;  clno > lno;  clno--)
  413.         {
  414.             /*
  415.              * Allow a signal to abort this loop.
  416.              */
  417.             cpos = back_raw_line(cpos, (char **)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(clno, 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 int
  435. currline(where)
  436.     int where;
  437. {
  438.     POSITION pos;
  439.     POSITION len;
  440.     int lnum;
  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.     lnum = find_linenum(pos);
  449.     if (pos == len)
  450.         lnum--;
  451.     return (lnum);
  452. }
  453.