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