home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / GNU / LES177AS.ZIP / LINENUM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-12  |  10.4 KB  |  454 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.     unsigned 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    (1)        /* 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.  
  209. static long loopcount;
  210. #if GET_TIME
  211. static long startime;
  212. #endif
  213.  
  214.     static void
  215. longish()
  216. {
  217. #ifdef TURBOC
  218.     if (kbhit()) ;    /* permit control^c checking */
  219. #endif
  220. #if GET_TIME
  221.     if (loopcount >= 0 && ++loopcount > 100)
  222.     {
  223.         loopcount = 0;
  224.         if (get_time() >= startime + LONGTIME)
  225.         {
  226.             longloopmessage();
  227.             loopcount = -1;
  228.         }
  229.     }
  230. #else
  231.     if (loopcount >= 0 && ++loopcount > LONGLOOP)
  232.     {
  233.         longloopmessage();
  234.         loopcount = -1;
  235.     }
  236. #endif
  237. }
  238.  
  239. /*
  240.  * Find the line number associated with a given position.
  241.  * Return 0 if we can't figure it out.
  242.  */
  243.     public int
  244. find_linenum(pos)
  245.     POSITION pos;
  246. {
  247.     register struct linenum *p;
  248.     register unsigned lno;
  249.     POSITION cpos;
  250.  
  251.     if (!linenums)
  252.         /*
  253.          * We're not using line numbers.
  254.          */
  255.         return (0);
  256.     if (pos == NULL_POSITION)
  257.         /*
  258.          * Caller doesn't know what he's talking about.
  259.          */
  260.         return (0);
  261.     if (pos <= ch_zero())
  262.         /*
  263.          * Beginning of file is always line number 1.
  264.          */
  265.         return (1);
  266.  
  267.     /*
  268.      * Find the entry nearest to the position we want.
  269.      */
  270.     for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
  271.         continue;
  272.     if (p->pos == pos)
  273.         /* Found it exactly. */
  274.         return (p->line);
  275.  
  276.     /*
  277.      * This is the (possibly) time-consuming part.
  278.      * We start at the line we just found and start
  279.      * reading the file forward or backward till we
  280.      * get to the place we want.
  281.      *
  282.      * First decide whether we should go forward from the 
  283.      * previous one or backwards from the next one.
  284.      * The decision is based on which way involves 
  285.      * traversing fewer bytes in the file.
  286.      */
  287.     flush();
  288. #if GET_TIME
  289.     startime = get_time();
  290. #endif
  291.     if (p == &anchor || pos - p->prev->pos < p->pos - pos)
  292.     {
  293.         /*
  294.          * Go forward.
  295.          */
  296.         p = p->prev;
  297.         if (ch_seek(p->pos))
  298.             return (0);
  299.         loopcount = 0;
  300.         /*
  301.          * Set the lnloop flag here, so if the user interrupts while
  302.          * we are calculating line numbers, the signal handler will 
  303.          * turn off line numbers (linenums=0).
  304.          */
  305.         lnloop = 1;
  306.         for (lno = p->line, cpos = p->pos;  cpos < pos;  lno++)
  307.         {
  308.             /*
  309.              * Allow a signal to abort this loop.
  310.              */
  311.             cpos = forw_raw_line(cpos, (char **)NULL);
  312.             if (sigs || cpos == NULL_POSITION)
  313.                 return (0);
  314.             longish();
  315.         }
  316.         lnloop = 0;
  317.         /*
  318.          * We might as well cache it.
  319.          */
  320.         add_lnum(lno, cpos);
  321.         /*
  322.          * If the given position is not at the start of a line,
  323.          * make sure we return the correct line number.
  324.          */
  325.         if (cpos > pos)
  326.             lno--;
  327.     } else
  328.     {
  329.         /*
  330.          * Go backward.
  331.          */
  332.         if (ch_seek(p->pos))
  333.             return (0);
  334.         loopcount = 0;
  335.         /*
  336.          * Set the lnloop flag here, so if the user interrupts while
  337.          * we are calculating line numbers, the signal handler will 
  338.          * turn off line numbers (linenums=0).
  339.          */
  340.         lnloop = 1;
  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 (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.     unsigned 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.     flush();
  389.     if (p == &anchor || lno - p->prev->line < p->line - lno)
  390.     {
  391.         /*
  392.          * Go forward.
  393.          */
  394.         p = p->prev;
  395.         if (ch_seek(p->pos))
  396.             return (NULL_POSITION);
  397.         for (clno = p->line, cpos = p->pos;  clno < lno;  clno++)
  398.         {
  399.             /*
  400.              * Allow a signal to abort this loop.
  401.              */
  402.             cpos = forw_raw_line(cpos, (char **)NULL);
  403.             if (sigs || cpos == NULL_POSITION)
  404.                 return (NULL_POSITION);
  405.         }
  406.     } else
  407.     {
  408.         /*
  409.          * Go backward.
  410.          */
  411.         if (ch_seek(p->pos))
  412.             return (NULL_POSITION);
  413.         for (clno = p->line, cpos = p->pos;  clno > lno;  clno--)
  414.         {
  415.             /*
  416.              * Allow a signal to abort this loop.
  417.              */
  418.             cpos = back_raw_line(cpos, (char **)NULL);
  419.             if (sigs || cpos == NULL_POSITION)
  420.                 return (NULL_POSITION);
  421.         }
  422.     }
  423.     /*
  424.      * We might as well cache it.
  425.      */
  426.     add_lnum(clno, cpos);
  427.     return (cpos);
  428. }
  429.  
  430. /*
  431.  * Return the line number of the "current" line.
  432.  * The argument "where" tells which line is to be considered
  433.  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
  434.  */
  435.     public int
  436. currline(where)
  437.     int where;
  438. {
  439.     POSITION pos;
  440.     POSITION len;
  441.     unsigned lnum;
  442.  
  443.     pos = position(where);
  444.     len = ch_length();
  445.     while (pos == NULL_POSITION && where >= 0 && where < sc_height)
  446.         pos = position(++where);
  447.     if (pos == NULL_POSITION)
  448.         pos = len;
  449.     lnum = find_linenum(pos);
  450.     if (pos == len)
  451.         lnum--;
  452.     return (lnum);
  453. }
  454.