|
211
|
1 /* Line number cache routines.
|
|
|
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
|
|
|
41 moves a lot), and low memory usage.
|
|
|
42
|
|
|
43 NOTE: line-number cache should not be confused with line-start
|
|
|
44 cache. Line-start cache (a part of redisplay) works with the
|
|
|
45 display lines, whereas this works with the buffer lines (literally
|
|
|
46 counting the newlines). */
|
|
|
47
|
|
|
48 #include <config.h>
|
|
|
49 #include "lisp.h"
|
|
|
50 #include "buffer.h"
|
|
|
51 #include "insdel.h"
|
|
|
52
|
|
|
53 #include "line-number.h"
|
|
|
54
|
|
|
55
|
|
|
56 /* #### The following three values could use some tweaking, to get the
|
|
|
57 best performance. */
|
|
|
58
|
|
|
59 /* Size of the ring. The current code expects this to be a small
|
|
|
60 number. If you make it much bigger, you should probably tr yto
|
|
|
61 optimize the various routines to keep it sorted. */
|
|
|
62 #define LINE_NUMBER_RING_SIZE 8
|
|
|
63
|
|
|
64 /* How much traversal has to be exceeded for two points to be
|
|
|
65 considered "far" from each other. When two points are far, cache
|
|
|
66 will be used. You can set this to a small value for debugging
|
|
|
67 purposes. */
|
|
|
68 #define LINE_NUMBER_FAR 16384
|
|
|
69
|
|
|
70 /* How large a string has to be to give up searching it for newlines,
|
|
|
71 before change. */
|
|
|
72 #define LINE_NUMBER_LARGE_STRING 256
|
|
|
73
|
|
|
74 /* To be used only when you *know* the cache has been allocated! */
|
|
|
75 #define LINE_NUMBER_RING(b) (XCAR ((b)->line_number_cache))
|
|
|
76 #define LINE_NUMBER_BEGV(b) (XCDR ((b)->line_number_cache))
|
|
|
77
|
|
|
78
|
|
|
79 /* Initialize the cache. Cache is (in pseudo-BNF):
|
|
|
80
|
|
|
81 CACHE = nil | INITIALIZED-CACHE
|
|
|
82 INITITIALIZED-CACHE = cons (RING, BEGV-LINE)
|
|
|
83 RING = vector (*RING-ELEMENT)
|
|
|
84 RING-ELEMENT = nil | RING-PAIR
|
|
|
85 RING-PAIR = cons (marker, integer)
|
|
|
86 BEGV-LINE = integer
|
|
|
87
|
|
|
88 Line number cache should never, ever, be visible to Lisp (because
|
|
|
89 destructively modifying its elements can cause crashes.) Debug it
|
|
|
90 using debug_print (current_buffer->last_number_cache). */
|
|
|
91 static void
|
|
|
92 allocate_line_number_cache (struct buffer *b)
|
|
|
93 {
|
|
|
94 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil),
|
|
|
95 Qzero);
|
|
|
96 narrow_line_number_cache (b);
|
|
|
97 }
|
|
|
98
|
|
|
99 /* Update line_number_begv. Do it only if the line number cache is
|
|
|
100 already initialized. */
|
|
|
101 void
|
|
|
102 narrow_line_number_cache (struct buffer *b)
|
|
|
103 {
|
|
|
104 EMACS_INT lots = 999999999, shortage;
|
|
|
105
|
|
|
106 if (NILP (b->line_number_cache))
|
|
|
107 return;
|
|
|
108 /* Optimization: if BUF_BEG == BUF_BEGV (as is the case after Fwiden
|
|
|
109 and save_restriction_restore), don't bother calling scan_buffer. */
|
|
|
110 if (BUF_BEG (b) == BUF_BEGV (b))
|
|
|
111 {
|
|
|
112 LINE_NUMBER_BEGV (b) = Qzero;
|
|
|
113 return;
|
|
|
114 }
|
|
|
115 /* Count the newlines between beginning of buffer and beginning of
|
|
|
116 the visible portion of the buffer. */
|
|
|
117 scan_buffer (b, '\n', BUF_BEG (b), BUF_BEGV (b), lots,
|
|
|
118 (int *)&shortage, 0);
|
|
|
119 LINE_NUMBER_BEGV (b) = make_int (lots - shortage);
|
|
|
120 }
|
|
|
121
|
|
|
122 /* Invalidate the line number cache positions that lie after POS. */
|
|
|
123 static void
|
|
|
124 invalidate_line_number_cache (struct buffer *b, Bufpos pos)
|
|
|
125 {
|
|
|
126 EMACS_INT i, j;
|
|
|
127 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
128 Lisp_Object lisp_buffer = make_buffer (b);
|
|
|
129
|
|
|
130 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
|
|
|
131 {
|
|
|
132 if (!CONSP (ring[i]))
|
|
|
133 break;
|
|
|
134 if (marker_position (XCAR (ring[i])) > pos)
|
|
|
135 {
|
|
|
136 /* Get the marker out of the way. */
|
|
|
137 Fset_marker (XCAR (ring[i]), Qnil, lisp_buffer);
|
|
|
138 /* ...and shift the ring elements, up to the first nil. */
|
|
|
139 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++)
|
|
|
140 ring[j] = ring[j + 1];
|
|
|
141 ring[j] = Qnil;
|
|
|
142 /* Must reevaluate the thing at position i. */
|
|
|
143 i--;
|
|
|
144 }
|
|
|
145 }
|
|
|
146 }
|
|
|
147
|
|
|
148 /* Invalidate the cache positions after POS, if the string to be
|
|
|
149 inserted contains a newline. If the string is too large (larger
|
|
|
150 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
|
|
|
151 after POS without prior search.
|
|
|
152
|
|
|
153 This will do nothing, if cache is uninitialized. */
|
|
|
154 void
|
|
|
155 insert_invalidate_line_number_cache (struct buffer *b, Bufpos pos,
|
|
|
156 CONST Bufbyte *nonreloc, Bytecount length)
|
|
|
157 {
|
|
|
158 if (NILP (b->line_number_cache))
|
|
|
159 return;
|
|
|
160
|
|
|
161 if (length > LINE_NUMBER_LARGE_STRING
|
|
|
162 ||
|
|
|
163 /* We could also count how many newlines are in the string, and
|
|
|
164 update the cache accordingly, but it would be too much work
|
|
|
165 for too little gain. */
|
|
|
166 memchr ((void *)nonreloc, '\n', (size_t) length))
|
|
|
167 invalidate_line_number_cache (b, pos);
|
|
|
168 }
|
|
|
169
|
|
|
170 /* Invalidate the cache positions after FROM, if the region to be
|
|
|
171 deleted contains a newline. If the region is too large (larger
|
|
|
172 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
|
|
|
173 after FROM without prior search.
|
|
|
174
|
|
|
175 This will do nothing, if cache is uninitialized. */
|
|
|
176 void
|
|
|
177 delete_invalidate_line_number_cache (struct buffer *b, Bufpos from, Bufpos to)
|
|
|
178 {
|
|
|
179 if (NILP (b->line_number_cache))
|
|
|
180 return;
|
|
|
181
|
|
|
182 if ((to - from) > LINE_NUMBER_LARGE_STRING)
|
|
|
183 invalidate_line_number_cache (b, from);
|
|
|
184 else
|
|
|
185 {
|
|
|
186 int shortage;
|
|
|
187 scan_buffer (b, '\n', from, to, 1, &shortage, 0);
|
|
|
188 if (!shortage)
|
|
|
189 /* The same as above applies. */
|
|
|
190 invalidate_line_number_cache (b, from);
|
|
|
191 }
|
|
|
192 }
|
|
|
193
|
|
|
194
|
|
|
195 /* Get the nearest known position we know the line number of
|
|
|
196 (i.e. BUF_BEGV, and cached positions). The return position will be
|
|
|
197 either closer than BEG, or BEG.
|
|
|
198
|
|
|
199 *LINE should be initialized to the line number of BEG (normally,
|
|
|
200 BEG will be BUF_BEGV, and *LINE will be XINT (LINE_NUMBER_BEGV).
|
|
|
201 This will initialize the cache, if necessary. */
|
|
|
202 static void
|
|
|
203 get_nearest_line_number (struct buffer *b, Bufpos *beg, Bufpos pos,
|
|
|
204 EMACS_INT *line)
|
|
|
205 {
|
|
|
206 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
207 EMACS_INT i;
|
|
|
208 Charcount length, howfar;
|
|
|
209 Bufpos newpos;
|
|
|
210
|
|
|
211 length = pos - *beg;
|
|
|
212 if (length < 0)
|
|
|
213 length = -length;
|
|
|
214
|
|
|
215 /* Look for the nearest match. */
|
|
|
216 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
|
|
|
217 {
|
|
|
218 if (!CONSP (ring[i]))
|
|
|
219 break;
|
|
|
220 newpos = marker_position (XCAR (ring[i]));
|
|
|
221 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_line_number (struct buffer *b, Bufpos pos, int line)
|
|
|
236 {
|
|
|
237 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
|
|
|
238 Lisp_Object marker;
|
|
|
239 int i;
|
|
|
240
|
|
|
241 for (i = LINE_NUMBER_RING_SIZE - 1; i > 0; i--)
|
|
|
242 ring[i] = ring[i - 1];
|
|
|
243 marker = Fmake_marker ();
|
|
|
244 Fset_marker (marker, make_int (pos), make_buffer (b));
|
|
|
245 ring[0] = Fcons (marker, make_int (line));
|
|
|
246 }
|
|
|
247
|
|
|
248 /* Calculate the buffer line number. If CACHEP is non-zero,
|
|
|
249 initialize the line-number cache for future use. The line number
|
|
|
250 of the first line is 0. If narrowing is in effect, count the lines
|
|
|
251 from the beginning of the visible portion of the buffer.
|
|
|
252
|
|
|
253 The cache works as follows: To calculate the line number, we need
|
|
|
254 two positions: position of point (POS) and the position from which
|
|
|
255 to count newlines (BEG). We start by setting BEG to BUF_BEGV. If
|
|
|
256 this would require too much searching (i.e. pos - BUF_BEGV >
|
|
|
257 LINE_NUMBER_FAR), try to find a closer position in the ring. If it
|
|
|
258 is found, use that position for BEG, and increment the line number
|
|
|
259 appropriately.
|
|
|
260
|
|
|
261 If the calculation (with or without the cache lookup) required more
|
|
|
262 than LINE_NUMBER_FAR bytes of traversal, update the cache. */
|
|
|
263 EMACS_INT
|
|
|
264 buffer_line_number (struct buffer *b, Bufpos pos, int cachep)
|
|
|
265 {
|
|
|
266 Bufpos beg = BUF_BEGV (b);
|
|
|
267 EMACS_INT cached_lines = 0;
|
|
|
268 EMACS_INT lots = 999999999;
|
|
|
269 EMACS_INT shortage, line;
|
|
|
270
|
|
|
271 if (cachep)
|
|
|
272 {
|
|
|
273 if (NILP (b->line_number_cache))
|
|
|
274 allocate_line_number_cache (b);
|
|
|
275 cached_lines = XINT (LINE_NUMBER_BEGV (b));
|
|
|
276 get_nearest_line_number (b, &beg, pos, &cached_lines);
|
|
|
277 }
|
|
|
278
|
|
|
279 scan_buffer (b, '\n', beg, pos, pos > beg ? lots : -lots,
|
|
|
280 (int *)&shortage, 0);
|
|
|
281
|
|
|
282 line = lots - shortage;
|
|
|
283 if (beg > pos)
|
|
|
284 line = -line;
|
|
|
285 line += cached_lines;
|
|
|
286
|
|
|
287 if (cachep)
|
|
|
288 {
|
|
|
289 /* If too far, update the cache. */
|
|
|
290 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
|
|
|
291 add_line_number (b, pos, line);
|
|
|
292 /* Account for narrowing. If CACHEP is nil, this is
|
|
|
293 unnecessary, because we counted from BUF_BEGV anyway. */
|
|
|
294 if (cachep)
|
|
|
295 line -= XINT (LINE_NUMBER_BEGV (b));
|
|
|
296 }
|
|
|
297
|
|
|
298 return line;
|
|
|
299 }
|
|
|
300
|
