|
428
|
1 /* Line number cache.
|
|
|
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 line numbering extremely slow for large buffers, because Emacs had
|
|
|
26 to rescan the whole buffer at each redisplay.
|
|
|
27
|
|
|
28 To make line numbering efficient, we maintain a buffer-local cache
|
|
|
29 of recently used positions and their line numbers. The cache is
|
|
|
30 implemented as a small ring of cache positions. A cache position
|
|
|
31 is either nil or a cons of a buffer position (marker) and the
|
|
|
32 corresponding line number.
|
|
|
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 buffer_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
|
|
|
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.
|
|
|
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
|
|
|
56 #include "line-number.h"
|
|
|
57
|
|
|
58 /* #### The following three values could stand more exploration for
|
|
|
59 best performance. */
|
|
|
60
|
|
|
61 /* Size of the ring. The current code expects this to be a small
|
|
|
62 number. If you make it larger, you should probably optimize the
|
|
|
63 code below to keep it sorted. */
|
|
|
64 #define LINE_NUMBER_RING_SIZE 8
|
|
|
65
|
|
|
66 /* How much traversal has to be exceeded for two points to be
|
|
|
67 considered "far" from each other. When two points are far, cache
|
|
|
68 will be used. */
|
|
|
69 #define LINE_NUMBER_FAR 16384
|
|
|
70
|
|
|
71 /* How large a string has to be to give up searching it for newlines,
|
|
|
72 before change. */
|
|
|
73 #define LINE_NUMBER_LARGE_STRING 256
|
|
|
74
|
|
|
75 /* To be used only when you *know* the cache has been allocated! */
|
|
|
76 #define LINE_NUMBER_RING(b) (XCAR ((b)->text->line_number_cache))
|
|
|
77 #define LINE_NUMBER_BEGV(b) (XCDR ((b)->text->line_number_cache))
|
|
|
78
|
|
|
79
|
|
|
80 /* Initialize the cache. Cache is (in pseudo-BNF):
|
|
|
81
|
|
|
82 CACHE = nil | INITIALIZED-CACHE
|
|
|
83 INITIALIZED-CACHE = cons (RING, BEGV-LINE)
|
|
|
84 RING = vector (*RING-ELEMENT)
|
|
|
85 RING-ELEMENT = nil | RING-PAIR
|
|
|
86 RING-PAIR = cons (marker, integer)
|
|
|
87 BEGV-LINE = integer
|
|
|
88
|
|
|
89 Line number cache should never, ever, be visible to Lisp (because
|
|
|
90 destructively modifying its elements can cause crashes.) Debug it
|
|
|
91 using debug_print (current_buffer->text->last_number_cache). */
|
|
|
92 static void
|
|
|
93 allocate_line_number_cache (struct buffer *b)
|
|
|
94 {
|
|
|
95 b->text->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil),
|
|
|
96 Qzero);
|
|
|
97 narrow_line_number_cache (b);
|
|
|
98 }
|
|
|
99
|
|
|
100 /* Flag LINE_NUMBER_BEGV (b) as dirty. Do it only if the line number
|
|
442
|
101 cache is already initialized. */
|
|
428
|
102 void
|
|
|
103 narrow_line_number_cache (struct buffer *b)
|
|
|
104 {
|
|
|
105 if (NILP (b->text->line_number_cache))
|
|
|
106 return;
|
|
|
107
|
|
|
108 if (BUF_BEG (b) == BUF_BEGV (b))
|
|
|
109 /* The is the case Fwiden and save_restriction_restore. Since we
|
|
|
110 know the correct value, we can update it now. */
|
|
|
111 LINE_NUMBER_BEGV (b) = Qzero;
|
|
|
112 else
|
|
|
113 /* Calculating the line number of BUF_BEGV here is a bad idea,
|
|
|
114 because there is absolutely no reason to do it before the next
|
|
|
115 redisplay. We simply mark it as dirty instead. */
|
|
|
116 LINE_NUMBER_BEGV (b) = make_int (-1);
|
|
|
117 }
|
|
|
118
|
|
|
119 /* Invalidate the line number cache positions that lie after POS. */
|
|
|
120 static void
|
|
|
121 invalidate_line_number_cache (struct buffer *b, Bufpos pos)
|
|
|
122 {
|
|
|
123 EMACS_INT i, j;
|
|
|
124 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
125
|
|
|
126 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
|
|
|
127 {
|
|
|
128 if (!CONSP (ring[i]))
|
|
|
129 break;
|
|
|
130 /* As the marker stays behind the insertions, this check might
|
|
|
131 as well be `>'. However, Finsert_before_markers can advance
|
|
|
132 the marker anyway, which bites in shell buffers.
|
|
|
133
|
|
|
134 #### This forces recreation of the cached marker (and
|
|
|
135 recalculation of newlines) every time a newline is inserted
|
|
|
136 at point, which is way losing. Isn't there a way to make a
|
|
|
137 marker impervious to Finsert_before_markers()?? Maybe I
|
|
|
138 should convert the code to use extents. */
|
|
|
139 if (marker_position (XCAR (ring[i])) >= pos)
|
|
|
140 {
|
|
|
141 /* Get the marker out of the way. */
|
|
|
142 Fset_marker (XCAR (ring[i]), Qnil, Qnil);
|
|
|
143 /* ...and shift the ring elements, up to the first nil. */
|
|
|
144 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++)
|
|
|
145 ring[j] = ring[j + 1];
|
|
|
146 ring[j] = Qnil;
|
|
|
147 /* Must recheck position i. */
|
|
|
148 i--;
|
|
|
149 }
|
|
|
150 }
|
|
|
151 }
|
|
|
152
|
|
|
153 /* Invalidate the cache positions after POS, if the string to be
|
|
|
154 inserted contains a newline. If the string is too large (larger
|
|
|
155 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
|
|
|
156 after POS without prior search.
|
|
|
157
|
|
|
158 This will do nothing if the cache is uninitialized. */
|
|
|
159 void
|
|
|
160 insert_invalidate_line_number_cache (struct buffer *b, Bufpos pos,
|
|
442
|
161 const Bufbyte *nonreloc, Bytecount length)
|
|
428
|
162 {
|
|
|
163 if (NILP (b->text->line_number_cache))
|
|
|
164 return;
|
|
|
165
|
|
|
166 if (length > LINE_NUMBER_LARGE_STRING
|
|
|
167 ||
|
|
|
168 /* We could also count how many newlines there are in the string
|
|
|
169 and update the cache accordingly, but it would be too much
|
|
|
170 work for too little gain. */
|
|
|
171 memchr ((void *)nonreloc, '\n', (size_t) length))
|
|
|
172 invalidate_line_number_cache (b, pos);
|
|
|
173 }
|
|
|
174
|
|
|
175 /* Invalidate the cache positions after FROM, if the region to be
|
|
|
176 deleted contains a newline. If the region-to-be-deleted is larger
|
|
|
177 than LINE_NUMBER_LARGE_STRING, invalidate the cache positions after
|
|
|
178 FROM without unconditionally.
|
|
|
179
|
|
|
180 This will do nothing if the cache is uninitialized. */
|
|
|
181 void
|
|
|
182 delete_invalidate_line_number_cache (struct buffer *b, Bufpos from, Bufpos to)
|
|
|
183 {
|
|
|
184 if (NILP (b->text->line_number_cache))
|
|
|
185 return;
|
|
|
186
|
|
|
187 if ((to - from) > LINE_NUMBER_LARGE_STRING)
|
|
|
188 invalidate_line_number_cache (b, from);
|
|
|
189 else
|
|
|
190 {
|
|
|
191 EMACS_INT shortage;
|
|
|
192 scan_buffer (b, '\n', from, to, 1, &shortage, 0);
|
|
|
193 if (!shortage)
|
|
|
194 invalidate_line_number_cache (b, from);
|
|
|
195 }
|
|
|
196 }
|
|
|
197
|
|
|
198 /* Get the nearest known position we know the line number of
|
|
|
199 (i.e. BUF_BEGV, and cached positions). The return position will be
|
|
|
200 either closer than BEG, or BEG. The line of this known position
|
|
|
201 will be stored in LINE.
|
|
|
202
|
|
|
203 *LINE should be initialized to the line number of BEG (normally,
|
|
|
204 BEG will be BUF_BEGV, and *LINE will be XINT (LINE_NUMBER_BEGV).
|
|
|
205 This will initialize the cache, if necessary. */
|
|
|
206 static void
|
|
|
207 get_nearest_line_number (struct buffer *b, Bufpos *beg, Bufpos pos,
|
|
|
208 EMACS_INT *line)
|
|
|
209 {
|
|
|
210 EMACS_INT i;
|
|
|
211 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
212 Charcount length = pos - *beg;
|
|
|
213
|
|
|
214 if (length < 0)
|
|
|
215 length = -length;
|
|
|
216
|
|
|
217 /* Find the ring entry closest to POS, if it is closer than BEG. */
|
|
|
218 for (i = 0; i < LINE_NUMBER_RING_SIZE && CONSP (ring[i]); i++)
|
|
|
219 {
|
|
|
220 Bufpos newpos = marker_position (XCAR (ring[i]));
|
|
|
221 Charcount howfar = newpos - pos;
|
|
|
222 if (howfar < 0)
|
|
|
223 howfar = -howfar;
|
|
|
224 if (howfar < length)
|
|
|
225 {
|
|
|
226 length = howfar;
|
|
|
227 *beg = newpos;
|
|
|
228 *line = XINT (XCDR (ring[i]));
|
|
|
229 }
|
|
|
230 }
|
|
|
231 }
|
|
|
232
|
|
|
233 /* Add a (POS . LINE) pair to the ring, and rotate it. */
|
|
|
234 static void
|
|
|
235 add_position_to_cache (struct buffer *b, Bufpos pos, EMACS_INT line)
|
|
|
236 {
|
|
|
237 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
238 int i = LINE_NUMBER_RING_SIZE - 1;
|
|
|
239
|
|
|
240 /* Set the last marker in the ring to point nowhere. */
|
|
|
241 if (CONSP (ring[i]))
|
|
|
242 Fset_marker (XCAR (ring[i]), Qnil, Qnil);
|
|
|
243
|
|
|
244 /* Rotate the ring... */
|
|
|
245 for (; i > 0; i--)
|
|
|
246 ring[i] = ring[i - 1];
|
|
|
247
|
|
|
248 /* ...and update it. */
|
|
|
249 ring[0] = Fcons (Fset_marker (Fmake_marker (), make_int (pos),
|
|
|
250 make_buffer (b)),
|
|
|
251 make_int (line));
|
|
|
252 }
|
|
|
253
|
|
|
254 /* Calculate the line number in buffer B at position POS. If CACHEP
|
|
|
255 is non-zero, initialize and facilitate the line-number cache. The
|
|
|
256 line number of the first line is 0. If narrowing is in effect,
|
|
|
257 count the lines are counted from the beginning of the visible
|
|
|
258 portion of the buffer.
|
|
|
259
|
|
|
260 The cache works as follows: To calculate the line number, we need
|
|
|
261 two positions: position of point (POS) and the position from which
|
|
|
262 to count newlines (BEG). We start by setting BEG to BUF_BEGV. If
|
|
|
263 this would require too much searching (i.e. pos - BUF_BEGV >
|
|
|
264 LINE_NUMBER_FAR), try to find a closer position in the ring. If it
|
|
|
265 is found, use that position for BEG, and increment the line number
|
|
|
266 appropriately.
|
|
|
267
|
|
|
268 If the calculation (with or without the cache lookup) required more
|
|
|
269 than LINE_NUMBER_FAR characters of traversal, update the cache. */
|
|
|
270 EMACS_INT
|
|
|
271 buffer_line_number (struct buffer *b, Bufpos pos, int cachep)
|
|
|
272 {
|
|
|
273 Bufpos beg = BUF_BEGV (b);
|
|
|
274 EMACS_INT cached_lines = 0;
|
|
|
275 EMACS_INT shortage, line;
|
|
|
276
|
|
|
277 if ((pos > beg ? pos - beg : beg - pos) <= LINE_NUMBER_FAR)
|
|
|
278 cachep = 0;
|
|
|
279
|
|
|
280 if (cachep)
|
|
|
281 {
|
|
|
282 if (NILP (b->text->line_number_cache))
|
|
|
283 allocate_line_number_cache (b);
|
|
|
284 /* If we don't know the line number of BUF_BEGV, calculate it now. */
|
|
|
285 if (XINT (LINE_NUMBER_BEGV (b)) == -1)
|
|
|
286 {
|
|
|
287 LINE_NUMBER_BEGV (b) = Qzero;
|
|
|
288 /* #### This has a side-effect of changing the cache. */
|
|
|
289 LINE_NUMBER_BEGV (b) =
|
|
|
290 make_int (buffer_line_number (b, BUF_BEGV (b), 1));
|
|
|
291 }
|
|
|
292 cached_lines = XINT (LINE_NUMBER_BEGV (b));
|
|
|
293 get_nearest_line_number (b, &beg, pos, &cached_lines);
|
|
|
294 }
|
|
|
295
|
|
|
296 scan_buffer (b, '\n', beg, pos, pos > beg ? EMACS_INT_MAX : -EMACS_INT_MAX,
|
|
|
297 &shortage, 0);
|
|
|
298
|
|
|
299 line = EMACS_INT_MAX - shortage;
|
|
|
300 if (beg > pos)
|
|
|
301 line = -line;
|
|
|
302 line += cached_lines;
|
|
|
303
|
|
|
304 if (cachep)
|
|
|
305 {
|
|
|
306 /* If too far, update the cache. */
|
|
|
307 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
|
|
|
308 add_position_to_cache (b, pos, line);
|
|
|
309 /* Account for narrowing. If cache is not used, this is
|
|
|
310 unnecessary, because we counted from BUF_BEGV anyway. */
|
|
|
311 line -= XINT (LINE_NUMBER_BEGV (b));
|
|
|
312 }
|
|
|
313
|
|
|
314 return line;
|
|
|
315 }
|
