|
219
|
1 /* Line number cache.
|
|
211
|
2 Copyright (C) 1997 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of XEmacs.
|
|
|
5
|
|
|
6 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 2, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with XEmacs; see the file COPYING. If not, write to
|
|
|
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
19 Boston, MA 02111-1307, USA. */
|
|
|
20
|
|
|
21 /* Synched up with: Not in FSF. */
|
|
|
22
|
|
|
23 /* To calculate the line numbers, redisplay must count the newlines
|
|
|
24 from a known position. This used to be BUF_BEGV, but this made the
|
|
|
25 redisplay extremely slow for large buffers, because Emacs must
|
|
|
26 rescan the whole buffer at each redisplay, just to count the
|
|
|
27 newlines.
|
|
|
28
|
|
|
29 To make line numbering efficient, we maintain a simple-minded
|
|
|
30 cache. Each buffer contains a small ring of known positions, each
|
|
|
31 element of the ring being a Lisp_Object -- either nil or a cons of
|
|
|
32 a buffer position and the line number (beginning with 0).
|
|
|
33
|
|
|
34 When calculating the line numbers, this cache is consulted if it
|
|
|
35 would otherwise take too much time to count the newlines in the
|
|
|
36 buffer (see the comment to window_line_number.)
|
|
|
37
|
|
|
38 Insertion and deletions that contain/delete newlines invalidate the
|
|
|
39 cached positions after the insertion point. This guarantees
|
|
|
40 relatively fast line numbers caching (even in buffers where point
|
|
219
|
41 moves a lot), and low memory usage. All of this is done only in
|
|
|
42 the buffers where the cache is actually initialized -- i.e. where
|
|
|
43 line-numbering is on, and you move the point farther than
|
|
|
44 LINE_NUMBER_FAR from the beginning of buffer. In this sense, the
|
|
|
45 cache is lazy. If you don't use it, you don't pay for it.
|
|
211
|
46
|
|
|
47 NOTE: line-number cache should not be confused with line-start
|
|
|
48 cache. Line-start cache (a part of redisplay) works with the
|
|
|
49 display lines, whereas this works with the buffer lines (literally
|
|
|
50 counting the newlines). */
|
|
|
51
|
|
|
52 #include <config.h>
|
|
|
53 #include "lisp.h"
|
|
|
54 #include "buffer.h"
|
|
|
55 #include "insdel.h"
|
|
|
56
|
|
|
57 #include "line-number.h"
|
|
|
58
|
|
|
59
|
|
|
60 /* #### The following three values could use some tweaking, to get the
|
|
219
|
61 best performance. I suspect LINE_NUMBER_FAR and
|
|
|
62 LINE_NUMBER_LARGE_STRING could be made bigger. */
|
|
211
|
63
|
|
|
64 /* Size of the ring. The current code expects this to be a small
|
|
|
65 number. If you make it much bigger, you should probably tr yto
|
|
|
66 optimize the various routines to keep it sorted. */
|
|
|
67 #define LINE_NUMBER_RING_SIZE 8
|
|
|
68
|
|
|
69 /* How much traversal has to be exceeded for two points to be
|
|
|
70 considered "far" from each other. When two points are far, cache
|
|
|
71 will be used. You can set this to a small value for debugging
|
|
|
72 purposes. */
|
|
|
73 #define LINE_NUMBER_FAR 16384
|
|
|
74
|
|
|
75 /* How large a string has to be to give up searching it for newlines,
|
|
|
76 before change. */
|
|
|
77 #define LINE_NUMBER_LARGE_STRING 256
|
|
|
78
|
|
|
79 /* To be used only when you *know* the cache has been allocated! */
|
|
|
80 #define LINE_NUMBER_RING(b) (XCAR ((b)->line_number_cache))
|
|
|
81 #define LINE_NUMBER_BEGV(b) (XCDR ((b)->line_number_cache))
|
|
|
82
|
|
|
83
|
|
|
84 /* Initialize the cache. Cache is (in pseudo-BNF):
|
|
|
85
|
|
|
86 CACHE = nil | INITIALIZED-CACHE
|
|
|
87 INITITIALIZED-CACHE = cons (RING, BEGV-LINE)
|
|
|
88 RING = vector (*RING-ELEMENT)
|
|
|
89 RING-ELEMENT = nil | RING-PAIR
|
|
|
90 RING-PAIR = cons (marker, integer)
|
|
|
91 BEGV-LINE = integer
|
|
|
92
|
|
|
93 Line number cache should never, ever, be visible to Lisp (because
|
|
|
94 destructively modifying its elements can cause crashes.) Debug it
|
|
|
95 using debug_print (current_buffer->last_number_cache). */
|
|
|
96 static void
|
|
|
97 allocate_line_number_cache (struct buffer *b)
|
|
|
98 {
|
|
|
99 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil),
|
|
|
100 Qzero);
|
|
|
101 narrow_line_number_cache (b);
|
|
|
102 }
|
|
|
103
|
|
219
|
104 /* Update line_number_begv, or flag it as dirty. Do it only if the
|
|
|
105 line number cache is already initialized. */
|
|
211
|
106 void
|
|
|
107 narrow_line_number_cache (struct buffer *b)
|
|
|
108 {
|
|
|
109 if (NILP (b->line_number_cache))
|
|
|
110 return;
|
|
|
111 /* Optimization: if BUF_BEG == BUF_BEGV (as is the case after Fwiden
|
|
|
112 and save_restriction_restore), don't bother calling scan_buffer. */
|
|
|
113 if (BUF_BEG (b) == BUF_BEGV (b))
|
|
|
114 {
|
|
|
115 LINE_NUMBER_BEGV (b) = Qzero;
|
|
|
116 return;
|
|
|
117 }
|
|
219
|
118 /* Calculating the line number of BUF_BEGV here is a bad idea,
|
|
|
119 because there is absolutely no reason to do it before the next
|
|
|
120 redisplay. We simply mark it as dirty instead. */
|
|
|
121 LINE_NUMBER_BEGV (b) = make_int (-1);
|
|
211
|
122 }
|
|
|
123
|
|
|
124 /* Invalidate the line number cache positions that lie after POS. */
|
|
|
125 static void
|
|
|
126 invalidate_line_number_cache (struct buffer *b, Bufpos pos)
|
|
|
127 {
|
|
|
128 EMACS_INT i, j;
|
|
|
129 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
130 Lisp_Object lisp_buffer = make_buffer (b);
|
|
|
131
|
|
|
132 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
|
|
|
133 {
|
|
|
134 if (!CONSP (ring[i]))
|
|
|
135 break;
|
|
219
|
136 /* As the marker stays behind the insertions, this check might
|
|
241
|
137 as well be `>'. However, Finsert_before_markers can move the
|
|
|
138 marker anyway, which bites in shell buffers.
|
|
|
139
|
|
|
140 #### This is wrong; it works right, but forces recreation of
|
|
|
141 the cached marker (and recalculation of newlines) every time
|
|
|
142 a newline is inserted at point, which is way losing. Isn't
|
|
|
143 there a way to make a marker impervious to
|
|
|
144 Finsert_before_markers()?? Maybe I should convert to using
|
|
|
145 extents. */
|
|
219
|
146 if (marker_position (XCAR (ring[i])) >= pos)
|
|
211
|
147 {
|
|
|
148 /* Get the marker out of the way. */
|
|
|
149 Fset_marker (XCAR (ring[i]), Qnil, lisp_buffer);
|
|
|
150 /* ...and shift the ring elements, up to the first nil. */
|
|
|
151 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++)
|
|
|
152 ring[j] = ring[j + 1];
|
|
|
153 ring[j] = Qnil;
|
|
219
|
154 /* Must recheck position i. */
|
|
211
|
155 i--;
|
|
|
156 }
|
|
|
157 }
|
|
|
158 }
|
|
|
159
|
|
|
160 /* Invalidate the cache positions after POS, if the string to be
|
|
|
161 inserted contains a newline. If the string is too large (larger
|
|
|
162 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
|
|
|
163 after POS without prior search.
|
|
|
164
|
|
|
165 This will do nothing, if cache is uninitialized. */
|
|
|
166 void
|
|
|
167 insert_invalidate_line_number_cache (struct buffer *b, Bufpos pos,
|
|
|
168 CONST Bufbyte *nonreloc, Bytecount length)
|
|
|
169 {
|
|
|
170 if (NILP (b->line_number_cache))
|
|
|
171 return;
|
|
|
172
|
|
|
173 if (length > LINE_NUMBER_LARGE_STRING
|
|
|
174 ||
|
|
|
175 /* We could also count how many newlines are in the string, and
|
|
|
176 update the cache accordingly, but it would be too much work
|
|
|
177 for too little gain. */
|
|
|
178 memchr ((void *)nonreloc, '\n', (size_t) length))
|
|
|
179 invalidate_line_number_cache (b, pos);
|
|
|
180 }
|
|
|
181
|
|
|
182 /* Invalidate the cache positions after FROM, if the region to be
|
|
|
183 deleted contains a newline. If the region is too large (larger
|
|
|
184 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
|
|
|
185 after FROM without prior search.
|
|
|
186
|
|
|
187 This will do nothing, if cache is uninitialized. */
|
|
|
188 void
|
|
|
189 delete_invalidate_line_number_cache (struct buffer *b, Bufpos from, Bufpos to)
|
|
|
190 {
|
|
|
191 if (NILP (b->line_number_cache))
|
|
|
192 return;
|
|
|
193
|
|
|
194 if ((to - from) > LINE_NUMBER_LARGE_STRING)
|
|
|
195 invalidate_line_number_cache (b, from);
|
|
|
196 else
|
|
|
197 {
|
|
|
198 int shortage;
|
|
|
199 scan_buffer (b, '\n', from, to, 1, &shortage, 0);
|
|
|
200 if (!shortage)
|
|
|
201 invalidate_line_number_cache (b, from);
|
|
|
202 }
|
|
|
203 }
|
|
|
204
|
|
|
205
|
|
|
206 /* Get the nearest known position we know the line number of
|
|
|
207 (i.e. BUF_BEGV, and cached positions). The return position will be
|
|
219
|
208 either closer than BEG, or BEG. The line of this known position
|
|
|
209 will be stored in LINE.
|
|
211
|
210
|
|
|
211 *LINE should be initialized to the line number of BEG (normally,
|
|
|
212 BEG will be BUF_BEGV, and *LINE will be XINT (LINE_NUMBER_BEGV).
|
|
|
213 This will initialize the cache, if necessary. */
|
|
|
214 static void
|
|
|
215 get_nearest_line_number (struct buffer *b, Bufpos *beg, Bufpos pos,
|
|
|
216 EMACS_INT *line)
|
|
|
217 {
|
|
|
218 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
219 EMACS_INT i;
|
|
|
220 Charcount length, howfar;
|
|
|
221 Bufpos newpos;
|
|
|
222
|
|
|
223 length = pos - *beg;
|
|
|
224 if (length < 0)
|
|
|
225 length = -length;
|
|
|
226
|
|
|
227 /* Look for the nearest match. */
|
|
|
228 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
|
|
|
229 {
|
|
|
230 if (!CONSP (ring[i]))
|
|
|
231 break;
|
|
|
232 newpos = marker_position (XCAR (ring[i]));
|
|
|
233 howfar = newpos - pos;
|
|
|
234 if (howfar < 0)
|
|
|
235 howfar = -howfar;
|
|
|
236 if (howfar < length)
|
|
|
237 {
|
|
|
238 length = howfar;
|
|
|
239 *beg = newpos;
|
|
|
240 *line = XINT (XCDR (ring[i]));
|
|
|
241 }
|
|
|
242 }
|
|
|
243 }
|
|
|
244
|
|
|
245 /* Add a (pos, line) pair to the ring, and rotate it. */
|
|
|
246 static void
|
|
|
247 add_line_number (struct buffer *b, Bufpos pos, int line)
|
|
|
248 {
|
|
|
249 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
250 Lisp_Object marker;
|
|
|
251 int i;
|
|
|
252
|
|
|
253 for (i = LINE_NUMBER_RING_SIZE - 1; i > 0; i--)
|
|
|
254 ring[i] = ring[i - 1];
|
|
|
255 marker = Fmake_marker ();
|
|
|
256 Fset_marker (marker, make_int (pos), make_buffer (b));
|
|
|
257 ring[0] = Fcons (marker, make_int (line));
|
|
|
258 }
|
|
|
259
|
|
219
|
260 /* Calculate the line number in buffer B at position POS. If CACHEP
|
|
|
261 is non-zero, initialize and facilitate the line-number cache. The
|
|
|
262 line number of the first line is 0. If narrowing is in effect,
|
|
|
263 count the lines are counted from the beginning of the visible
|
|
|
264 portion of the buffer.
|
|
211
|
265
|
|
|
266 The cache works as follows: To calculate the line number, we need
|
|
|
267 two positions: position of point (POS) and the position from which
|
|
|
268 to count newlines (BEG). We start by setting BEG to BUF_BEGV. If
|
|
|
269 this would require too much searching (i.e. pos - BUF_BEGV >
|
|
|
270 LINE_NUMBER_FAR), try to find a closer position in the ring. If it
|
|
|
271 is found, use that position for BEG, and increment the line number
|
|
|
272 appropriately.
|
|
|
273
|
|
|
274 If the calculation (with or without the cache lookup) required more
|
|
|
275 than LINE_NUMBER_FAR bytes of traversal, update the cache. */
|
|
|
276 EMACS_INT
|
|
|
277 buffer_line_number (struct buffer *b, Bufpos pos, int cachep)
|
|
|
278 {
|
|
|
279 Bufpos beg = BUF_BEGV (b);
|
|
|
280 EMACS_INT cached_lines = 0;
|
|
|
281 EMACS_INT shortage, line;
|
|
|
282
|
|
219
|
283 if ((pos > beg ? pos - beg : beg - pos) <= LINE_NUMBER_FAR)
|
|
|
284 cachep = 0;
|
|
|
285
|
|
211
|
286 if (cachep)
|
|
|
287 {
|
|
|
288 if (NILP (b->line_number_cache))
|
|
|
289 allocate_line_number_cache (b);
|
|
219
|
290 /* If we don't know the line number of BUF_BEGV, calculate it now. */
|
|
|
291 if (XINT (LINE_NUMBER_BEGV (b)) == -1)
|
|
|
292 {
|
|
|
293 LINE_NUMBER_BEGV (b) = Qzero;
|
|
|
294 /* #### This has a side-effect of changing the cache. */
|
|
|
295 LINE_NUMBER_BEGV (b) =
|
|
|
296 make_int (buffer_line_number (b, BUF_BEGV (b), 1));
|
|
|
297 }
|
|
211
|
298 cached_lines = XINT (LINE_NUMBER_BEGV (b));
|
|
|
299 get_nearest_line_number (b, &beg, pos, &cached_lines);
|
|
|
300 }
|
|
|
301
|
|
219
|
302 /* An EMACS_MAXINT would be cool to have. */
|
|
|
303 #define LOTS 999999999
|
|
|
304
|
|
|
305 scan_buffer (b, '\n', beg, pos, pos > beg ? LOTS : -LOTS,
|
|
211
|
306 (int *)&shortage, 0);
|
|
|
307
|
|
219
|
308 line = LOTS - shortage;
|
|
211
|
309 if (beg > pos)
|
|
|
310 line = -line;
|
|
|
311 line += cached_lines;
|
|
|
312
|
|
|
313 if (cachep)
|
|
|
314 {
|
|
|
315 /* If too far, update the cache. */
|
|
|
316 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
|
|
|
317 add_line_number (b, pos, line);
|
|
|
318 /* Account for narrowing. If CACHEP is nil, this is
|
|
|
319 unnecessary, because we counted from BUF_BEGV anyway. */
|
|
219
|
320 line -= XINT (LINE_NUMBER_BEGV (b));
|
|
211
|
321 }
|
|
|
322
|
|
|
323 return line;
|
|
|
324 }
|
|
|
325
|
