home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume16 / less5 / part03 / linenum.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-09-22  |  8.6 KB  |  390 lines
  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.  
  63. /*
  64.  * Initialize the line number structures.
  65.  */
  66.     public void
  67. clr_linenum()
  68. {
  69.     register struct linenum *p;
  70.  
  71.     /*
  72.      * Put all the entries on the free list.
  73.      * Leave one for the "spare".
  74.      */
  75.     for (p = pool;  p < &pool[NPOOL-2];  p++)
  76.         p->next = p+1;
  77.     pool[NPOOL-2].next = NULL;
  78.     freelist = pool;
  79.  
  80.     spare = &pool[NPOOL-1];
  81.  
  82.     /*
  83.      * Initialize the anchor.
  84.      */
  85.     anchor.next = anchor.prev = &anchor;
  86.     anchor.gap = 0;
  87.     anchor.pos = (POSITION)0;
  88.     anchor.line = 1;
  89. }
  90.  
  91. /*
  92.  * Calculate the gap for an entry.
  93.  */
  94.     static void
  95. calcgap(p)
  96.     register struct linenum *p;
  97. {
  98.     /*
  99.      * Don't bother to compute a gap for the anchor.
  100.      * Also don't compute a gap for the last one in the list.
  101.      * The gap for that last one should be considered infinite,
  102.      * but we never look at it anyway.
  103.      */
  104.     if (p == &anchor || p->next == &anchor)
  105.         return;
  106.     p->gap = p->next->pos - p->prev->pos;
  107. }
  108.  
  109. /*
  110.  * Add a new line number to the cache.
  111.  * The specified position (pos) should be the file position of the
  112.  * FIRST character in the specified line.
  113.  */
  114.     public void
  115. add_lnum(line, pos)
  116.     int line;
  117.     POSITION pos;
  118. {
  119.     register struct linenum *p;
  120.     register struct linenum *new;
  121.     register struct linenum *nextp;
  122.     register struct linenum *prevp;
  123.     register POSITION mingap;
  124.  
  125.     /*
  126.      * Find the proper place in the list for the new one.
  127.      * The entries are sorted by position.
  128.      */
  129.     for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
  130.         if (p->line == line)
  131.             /* We already have this one. */
  132.             return;
  133.     nextp = p;
  134.     prevp = p->prev;
  135.  
  136.     if (freelist != NULL)
  137.     {
  138.         /*
  139.          * We still have free (unused) entries.
  140.          * Use one of them.
  141.          */
  142.         new = freelist;
  143.         freelist = freelist->next;
  144.     } else
  145.     {
  146.         /*
  147.          * No free entries.
  148.          * Use the "spare" entry.
  149.          */
  150.         new = spare;
  151.         spare = NULL;
  152.     }
  153.  
  154.     /*
  155.      * Fill in the fields of the new entry,
  156.      * and insert it into the proper place in the list.
  157.      */
  158.     new->next = nextp;
  159.     new->prev = prevp;
  160.     new->pos = pos;
  161.     new->line = line;
  162.  
  163.     nextp->prev = new;
  164.     prevp->next = new;
  165.  
  166.     /*
  167.      * Recalculate gaps for the new entry and the neighboring entries.
  168.      */
  169.     calcgap(new);
  170.     calcgap(nextp);
  171.     calcgap(prevp);
  172.  
  173.     if (spare == NULL)
  174.     {
  175.         /*
  176.          * We have used the spare entry.
  177.          * Scan the list to find the one with the smallest
  178.          * gap, take it out and make it the spare.
  179.          * We should never remove the last one, so stop when
  180.          * we get to p->next == &anchor.  This also avoids
  181.          * looking at the gap of the last one, which is
  182.          * not computed by calcgap.
  183.          */
  184.         mingap = anchor.next->gap;
  185.         for (p = anchor.next;  p->next != &anchor;  p = p->next)
  186.         {
  187.             if (p->gap <= mingap)
  188.             {
  189.                 spare = p;
  190.                 mingap = p->gap;
  191.             }
  192.         }
  193.         spare->next->prev = spare->prev;
  194.         spare->prev->next = spare->next;
  195.     }
  196. }
  197.  
  198. /*
  199.  * If we get stuck in a long loop trying to figure out the
  200.  * line number, print a message to tell the user what we're doing.
  201.  */
  202.     static void
  203. longloopmessage()
  204. {
  205.     ierror("Calculating line numbers");
  206.     /*
  207.      * Set the lnloop flag here, so if the user interrupts while
  208.      * we are calculating line numbers, the signal handler will 
  209.      * turn off line numbers (linenums=0).
  210.      */
  211.     lnloop = 1;
  212. }
  213.  
  214. /*
  215.  * Find the line number associated with a given position.
  216.  * Return 0 if we can't figure it out.
  217.  */
  218.     public int
  219. find_linenum(pos)
  220.     POSITION pos;
  221. {
  222.     register struct linenum *p;
  223.     register int lno;
  224.     register int loopcount;
  225.     POSITION cpos;
  226. #if GET_TIME
  227.     long startime;
  228. #endif
  229.  
  230.     if (!linenums)
  231.         /*
  232.          * We're not using line numbers.
  233.          */
  234.         return (0);
  235.     if (pos == NULL_POSITION)
  236.         /*
  237.          * Caller doesn't know what he's talking about.
  238.          */
  239.         return (0);
  240.     if (pos == (POSITION)0)
  241.         /*
  242.          * Beginning of file is always line number 1.
  243.          */
  244.         return (1);
  245.  
  246.     /*
  247.      * Find the entry nearest to the position we want.
  248.      */
  249.     for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
  250.         continue;
  251.     if (p->pos == pos)
  252.         /* Found it exactly. */
  253.         return (p->line);
  254.  
  255.     /*
  256.      * This is the (possibly) time-consuming part.
  257.      * We start at the line we just found and start
  258.      * reading the file forward or backward till we
  259.      * get to the place we want.
  260.      *
  261.      * First decide whether we should go forward from the 
  262.      * previous one or backwards from the next one.
  263.      * The decision is based on which way involves 
  264.      * traversing fewer bytes in the file.
  265.      */
  266.     flush();
  267. #if GET_TIME
  268.     startime = get_time();
  269. #endif
  270.     if (p == &anchor || pos - p->prev->pos < p->pos - pos)
  271.     {
  272.         /*
  273.          * Go forward.
  274.          */
  275.         p = p->prev;
  276.         if (ch_seek(p->pos))
  277.             return (0);
  278.         loopcount = 0;
  279.         for (lno = p->line, cpos = p->pos;  cpos < pos;  lno++)
  280.         {
  281.             /*
  282.              * Allow a signal to abort this loop.
  283.              */
  284.             cpos = forw_raw_line(cpos);
  285.             if (sigs || cpos == NULL_POSITION)
  286.                 return (0);
  287. #if GET_TIME
  288.             if (loopcount >= 0 && ++loopcount > 100)
  289.             {
  290.                 loopcount = 0;
  291.                 if (get_time() >= startime + LONGTIME)
  292.                 {
  293.                     longloopmessage();
  294.                     loopcount = -1;
  295.                 }
  296.             }
  297. #else
  298.             if (loopcount >= 0 && ++loopcount > LONGLOOP)
  299.             {
  300.                 longloopmessage();
  301.                 loopcount = -1;
  302.             }
  303. #endif
  304.         }
  305.         lnloop = 0;
  306.         /*
  307.          * If the given position is not at the start of a line,
  308.          * make sure we return the correct line number.
  309.          */
  310.         if (cpos > pos)
  311.             lno--;
  312.     } else
  313.     {
  314.         /*
  315.          * Go backward.
  316.          */
  317.         if (ch_seek(p->pos))
  318.             return (0);
  319.         loopcount = 0;
  320.         for (lno = p->line, cpos = p->pos;  cpos > pos;  lno--)
  321.         {
  322.             /*
  323.              * Allow a signal to abort this loop.
  324.              */
  325.             cpos = back_raw_line(cpos);
  326.             if (sigs || cpos == NULL_POSITION)
  327.                 return (0);
  328. #if GET_TIME
  329.             if (loopcount >= 0 && ++loopcount > 100)
  330.             {
  331.                 loopcount = 0;
  332.                 if (get_time() >= startime + LONGTIME)
  333.                 {
  334.                     longloopmessage();
  335.                     loopcount = -1;
  336.                 }
  337.             }
  338. #else
  339.             if (loopcount >= 0 && ++loopcount > LONGLOOP)
  340.             {
  341.                 longloopmessage();
  342.                 loopcount = -1;
  343.             }
  344. #endif
  345.         }
  346.         lnloop = 0;
  347.     }
  348.  
  349.     /*
  350.      * We might as well cache it.
  351.      */
  352.     add_lnum(lno, cpos);
  353.     return (lno);
  354. }
  355.  
  356. /*
  357.  * Return the line number of the "current" line.
  358.  * The argument "where" tells which line is to be considered
  359.  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
  360.  */
  361.     public int
  362. currline(where)
  363.     int where;
  364. {
  365.     POSITION pos;
  366.  
  367.     pos = position(where);
  368.     if (pos == NULL_POSITION)
  369.         pos = ch_length();
  370.     return (find_linenum(pos));
  371. }
  372.  
  373. #if DEBUG_STUFF
  374. debug()
  375. {
  376.     register struct linenum *p;
  377.     char buf[20];
  378.  
  379.     lower_left();
  380.     clear_eol();
  381.     for (p = anchor.next;  p != &anchor;  p = p->next)
  382.     {
  383.         sprintf(buf, "%d-%d ", p->line, p->pos);
  384.         putstr(buf);
  385.     }
  386.     putstr("\n");
  387.     error("DEBUG");
  388. }
  389. #endif /*DEBUG_STUFF*/
  390.