Added -clobber switch to mhstore(1) [Bug #11160].
[mmh] / docs / historical / mh-6.8.5 / miscellany / less-177 / linenum.c
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 }