]> git.cworth.org Git - apitrace/blob - thirdparty/less/linenum.c
Update khronos headers.
[apitrace] / thirdparty / less / linenum.c
1 /*
2  * Copyright (C) 1984-2011  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_info
43 {
44         struct linenum_info *next;      /* Link to next in the list */
45         struct linenum_info *prev;      /* Line to previous in the list */
46         POSITION pos;                   /* File position */
47         POSITION gap;                   /* Gap between prev and next */
48         LINENUM 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   200                     /* Size of line number pool */
60
61 #define LONGTIME        (2)             /* In seconds */
62
63 static struct linenum_info anchor;      /* Anchor of the list */
64 static struct linenum_info *freelist;   /* Anchor of the unused entries */
65 static struct linenum_info pool[NPOOL]; /* The pool itself */
66 static struct linenum_info *spare;              /* We always keep one spare entry */
67
68 extern int linenums;
69 extern int sigs;
70 extern int sc_height;
71 extern int screen_trashed;
72
73 /*
74  * Initialize the line number structures.
75  */
76         public void
77 clr_linenum()
78 {
79         register struct linenum_info *p;
80
81         /*
82          * Put all the entries on the free list.
83          * Leave one for the "spare".
84          */
85         for (p = pool;  p < &pool[NPOOL-2];  p++)
86                 p->next = p+1;
87         pool[NPOOL-2].next = NULL;
88         freelist = pool;
89
90         spare = &pool[NPOOL-1];
91
92         /*
93          * Initialize the anchor.
94          */
95         anchor.next = anchor.prev = &anchor;
96         anchor.gap = 0;
97         anchor.pos = (POSITION)0;
98         anchor.line = 1;
99 }
100
101 /*
102  * Calculate the gap for an entry.
103  */
104         static void
105 calcgap(p)
106         register struct linenum_info *p;
107 {
108         /*
109          * Don't bother to compute a gap for the anchor.
110          * Also don't compute a gap for the last one in the list.
111          * The gap for that last one should be considered infinite,
112          * but we never look at it anyway.
113          */
114         if (p == &anchor || p->next == &anchor)
115                 return;
116         p->gap = p->next->pos - p->prev->pos;
117 }
118
119 /*
120  * Add a new line number to the cache.
121  * The specified position (pos) should be the file position of the
122  * FIRST character in the specified line.
123  */
124         public void
125 add_lnum(linenum, pos)
126         LINENUM linenum;
127         POSITION pos;
128 {
129         register struct linenum_info *p;
130         register struct linenum_info *new;
131         register struct linenum_info *nextp;
132         register struct linenum_info *prevp;
133         register POSITION mingap;
134
135         /*
136          * Find the proper place in the list for the new one.
137          * The entries are sorted by position.
138          */
139         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
140                 if (p->line == linenum)
141                         /* We already have this one. */
142                         return;
143         nextp = p;
144         prevp = p->prev;
145
146         if (freelist != NULL)
147         {
148                 /*
149                  * We still have free (unused) entries.
150                  * Use one of them.
151                  */
152                 new = freelist;
153                 freelist = freelist->next;
154         } else
155         {
156                 /*
157                  * No free entries.
158                  * Use the "spare" entry.
159                  */
160                 new = spare;
161                 spare = NULL;
162         }
163
164         /*
165          * Fill in the fields of the new entry,
166          * and insert it into the proper place in the list.
167          */
168         new->next = nextp;
169         new->prev = prevp;
170         new->pos = pos;
171         new->line = linenum;
172
173         nextp->prev = new;
174         prevp->next = new;
175
176         /*
177          * Recalculate gaps for the new entry and the neighboring entries.
178          */
179         calcgap(new);
180         calcgap(nextp);
181         calcgap(prevp);
182
183         if (spare == NULL)
184         {
185                 /*
186                  * We have used the spare entry.
187                  * Scan the list to find the one with the smallest
188                  * gap, take it out and make it the spare.
189                  * We should never remove the last one, so stop when
190                  * we get to p->next == &anchor.  This also avoids
191                  * looking at the gap of the last one, which is
192                  * not computed by calcgap.
193                  */
194                 mingap = anchor.next->gap;
195                 for (p = anchor.next;  p->next != &anchor;  p = p->next)
196                 {
197                         if (p->gap <= mingap)
198                         {
199                                 spare = p;
200                                 mingap = p->gap;
201                         }
202                 }
203                 spare->next->prev = spare->prev;
204                 spare->prev->next = spare->next;
205         }
206 }
207
208 /*
209  * If we get stuck in a long loop trying to figure out the
210  * line number, print a message to tell the user what we're doing.
211  */
212         static void
213 longloopmessage()
214 {
215         ierror("Calculating line numbers", NULL_PARG);
216 }
217
218 static int loopcount;
219 #if HAVE_TIME
220 static long startime;
221 #endif
222
223         static void
224 longish()
225 {
226 #if HAVE_TIME
227         if (loopcount >= 0 && ++loopcount > 100)
228         {
229                 loopcount = 0;
230                 if (get_time() >= startime + LONGTIME)
231                 {
232                         longloopmessage();
233                         loopcount = -1;
234                 }
235         }
236 #else
237         if (loopcount >= 0 && ++loopcount > LONGLOOP)
238         {
239                 longloopmessage();
240                 loopcount = -1;
241         }
242 #endif
243 }
244
245 /*
246  * Turn off line numbers because the user has interrupted
247  * a lengthy line number calculation.
248  */
249         static void
250 abort_long()
251 {
252         if (linenums == OPT_ONPLUS)
253                 /*
254                  * We were displaying line numbers, so need to repaint.
255                  */
256                 screen_trashed = 1;
257         linenums = 0;
258         error("Line numbers turned off", NULL_PARG);
259 }
260
261 /*
262  * Find the line number associated with a given position.
263  * Return 0 if we can't figure it out.
264  */
265         public LINENUM
266 find_linenum(pos)
267         POSITION pos;
268 {
269         register struct linenum_info *p;
270         register LINENUM linenum;
271         POSITION cpos;
272
273         if (!linenums)
274                 /*
275                  * We're not using line numbers.
276                  */
277                 return (0);
278         if (pos == NULL_POSITION)
279                 /*
280                  * Caller doesn't know what he's talking about.
281                  */
282                 return (0);
283         if (pos <= ch_zero())
284                 /*
285                  * Beginning of file is always line number 1.
286                  */
287                 return (1);
288
289         /*
290          * Find the entry nearest to the position we want.
291          */
292         for (p = anchor.next;  p != &anchor && p->pos < pos;  p = p->next)
293                 continue;
294         if (p->pos == pos)
295                 /* Found it exactly. */
296                 return (p->line);
297
298         /*
299          * This is the (possibly) time-consuming part.
300          * We start at the line we just found and start
301          * reading the file forward or backward till we
302          * get to the place we want.
303          *
304          * First decide whether we should go forward from the 
305          * previous one or backwards from the next one.
306          * The decision is based on which way involves 
307          * traversing fewer bytes in the file.
308          */
309 #if HAVE_TIME
310         startime = get_time();
311 #endif
312         if (p == &anchor || pos - p->prev->pos < p->pos - pos)
313         {
314                 /*
315                  * Go forward.
316                  */
317                 p = p->prev;
318                 if (ch_seek(p->pos))
319                         return (0);
320                 loopcount = 0;
321                 for (linenum = p->line, cpos = p->pos;  cpos < pos;  linenum++)
322                 {
323                         /*
324                          * Allow a signal to abort this loop.
325                          */
326                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
327                         if (ABORT_SIGS()) {
328                                 abort_long();
329                                 return (0);
330                         }
331                         if (cpos == NULL_POSITION)
332                                 return (0);
333                         longish();
334                 }
335                 /*
336                  * We might as well cache it.
337                  */
338                 add_lnum(linenum, cpos);
339                 /*
340                  * If the given position is not at the start of a line,
341                  * make sure we return the correct line number.
342                  */
343                 if (cpos > pos)
344                         linenum--;
345         } else
346         {
347                 /*
348                  * Go backward.
349                  */
350                 if (ch_seek(p->pos))
351                         return (0);
352                 loopcount = 0;
353                 for (linenum = p->line, cpos = p->pos;  cpos > pos;  linenum--)
354                 {
355                         /*
356                          * Allow a signal to abort this loop.
357                          */
358                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
359                         if (ABORT_SIGS()) {
360                                 abort_long();
361                                 return (0);
362                         }
363                         if (cpos == NULL_POSITION)
364                                 return (0);
365                         longish();
366                 }
367                 /*
368                  * We might as well cache it.
369                  */
370                 add_lnum(linenum, cpos);
371         }
372
373         return (linenum);
374 }
375
376 /*
377  * Find the position of a given line number.
378  * Return NULL_POSITION if we can't figure it out.
379  */
380         public POSITION
381 find_pos(linenum)
382         LINENUM linenum;
383 {
384         register struct linenum_info *p;
385         POSITION cpos;
386         LINENUM clinenum;
387
388         if (linenum <= 1)
389                 /*
390                  * Line number 1 is beginning of file.
391                  */
392                 return (ch_zero());
393
394         /*
395          * Find the entry nearest to the line number we want.
396          */
397         for (p = anchor.next;  p != &anchor && p->line < linenum;  p = p->next)
398                 continue;
399         if (p->line == linenum)
400                 /* Found it exactly. */
401                 return (p->pos);
402
403         if (p == &anchor || linenum - p->prev->line < p->line - linenum)
404         {
405                 /*
406                  * Go forward.
407                  */
408                 p = p->prev;
409                 if (ch_seek(p->pos))
410                         return (NULL_POSITION);
411                 for (clinenum = p->line, cpos = p->pos;  clinenum < linenum;  clinenum++)
412                 {
413                         /*
414                          * Allow a signal to abort this loop.
415                          */
416                         cpos = forw_raw_line(cpos, (char **)NULL, (int *)NULL);
417                         if (ABORT_SIGS())
418                                 return (NULL_POSITION);
419                         if (cpos == NULL_POSITION)
420                                 return (NULL_POSITION);
421                 }
422         } else
423         {
424                 /*
425                  * Go backward.
426                  */
427                 if (ch_seek(p->pos))
428                         return (NULL_POSITION);
429                 for (clinenum = p->line, cpos = p->pos;  clinenum > linenum;  clinenum--)
430                 {
431                         /*
432                          * Allow a signal to abort this loop.
433                          */
434                         cpos = back_raw_line(cpos, (char **)NULL, (int *)NULL);
435                         if (ABORT_SIGS())
436                                 return (NULL_POSITION);
437                         if (cpos == NULL_POSITION)
438                                 return (NULL_POSITION);
439                 }
440         }
441         /*
442          * We might as well cache it.
443          */
444         add_lnum(clinenum, cpos);
445         return (cpos);
446 }
447
448 /*
449  * Return the line number of the "current" line.
450  * The argument "where" tells which line is to be considered
451  * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
452  */
453         public LINENUM
454 currline(where)
455         int where;
456 {
457         POSITION pos;
458         POSITION len;
459         LINENUM linenum;
460
461         pos = position(where);
462         len = ch_length();
463         while (pos == NULL_POSITION && where >= 0 && where < sc_height)
464                 pos = position(++where);
465         if (pos == NULL_POSITION)
466                 pos = len;
467         linenum = find_linenum(pos);
468         if (pos == len)
469                 linenum--;
470         return (linenum);
471 }