home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / LESS177.ZIP / src / linenum.c < prev    next >
C/C++ Source or Header  |  1992-07-18  |  10KB  |  445 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. 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. }
  445.