Mercurial > hg > xemacs-beta

comparison src/line-number.c @ 211:78478c60bfcd r20-4b4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-4b4
author cvs
date Mon, 13 Aug 2007 10:05:51 +0200
parents
children 262b8bb4a523
comparison
equal deleted inserted replaced
210:49f55ca3ba57 211:78478c60bfcd
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