Mercurial > hg > xemacs-beta

comparison src/line-number.c @ 284:558f606b08ae r21-0b40

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-0b40
author cvs
date Mon, 13 Aug 2007 10:34:13 +0200
parents f955c73f5258
children 57709be46d1b
comparison
equal deleted inserted replaced
283:fa3d41851a08 284:558f606b08ae
20 20
21 /* Synched up with: Not in FSF. */ 21 /* Synched up with: Not in FSF. */
22 22
23 /* To calculate the line numbers, redisplay must count the newlines 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 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 25 line numbering extremely slow for large buffers, because Emacs had
26 rescan the whole buffer at each redisplay, just to count the 26 to rescan the whole buffer at each redisplay.
27 newlines. 27
28 28 To make line numbering efficient, we maintain a buffer-local cache
29 To make line numbering efficient, we maintain a simple-minded 29 of recently used positions and their line numbers. The cache is
30 cache. Each buffer contains a small ring of known positions, each 30 implemented as a small ring of cache positions. A cache position
31 element of the ring being a Lisp_Object -- either nil or a cons of 31 is either nil or a cons of a buffer position (marker) and the
32 a buffer position and the line number (beginning with 0). 32 corresponding line number.
33 33
34 When calculating the line numbers, this cache is consulted if it 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 35 would otherwise take too much time to count the newlines in the
36 buffer (see the comment to window_line_number.) 36 buffer (see the comment to buffer_line_number().)
37 37
38 Insertion and deletions that contain/delete newlines invalidate the 38 Insertion and deletions that contain/delete newlines invalidate the
39 cached positions after the insertion point. This guarantees 39 cached positions after the insertion point. This guarantees
40 relatively fast line numbers caching (even in buffers where point 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 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 42 the buffers where the cache is actually initialized -- i.e. where
43 line-numbering is on, and you move the point farther than 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 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. 45 cache is lazy -- if you don't use it, you don't pay for it.
46 46
47 NOTE: line-number cache should not be confused with line-start 47 NOTE: line-number cache should not be confused with line-start
48 cache. Line-start cache (a part of redisplay) works with the 48 cache. Line-start cache (a part of redisplay) works with the
49 display lines, whereas this works with the buffer lines (literally 49 display lines, whereas this works with the buffer lines (literally
50 counting the newlines). */ 50 counting the newlines). */
54 #include "buffer.h" 54 #include "buffer.h"
55 #include "insdel.h" 55 #include "insdel.h"
56 56
57 #include "line-number.h" 57 #include "line-number.h"
58 58
59 59 /* #### The following three values could stand more exploration for
60 /* #### The following three values could use some tweaking, to get the 60 best performance. */
61 best performance. I suspect LINE_NUMBER_FAR and
62 LINE_NUMBER_LARGE_STRING could be made bigger. */
63 61
64 /* Size of the ring. The current code expects this to be a small 62 /* 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 63 number. If you make it larger, you should probably optimize the
66 optimize the various routines to keep it sorted. */ 64 code below to keep it sorted. */
67 #define LINE_NUMBER_RING_SIZE 8 65 #define LINE_NUMBER_RING_SIZE 8
68 66
69 /* How much traversal has to be exceeded for two points to be 67 /* How much traversal has to be exceeded for two points to be
70 considered "far" from each other. When two points are far, cache 68 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 69 will be used. */
72 purposes. */ 70 #define LINE_NUMBER_FAR 32768
73 #define LINE_NUMBER_FAR 16384
74 71
75 /* How large a string has to be to give up searching it for newlines, 72 /* How large a string has to be to give up searching it for newlines,
76 before change. */ 73 before change. */
77 #define LINE_NUMBER_LARGE_STRING 256 74 #define LINE_NUMBER_LARGE_STRING 256
78 75
99 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil), 96 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil),
100 Qzero); 97 Qzero);
101 narrow_line_number_cache (b); 98 narrow_line_number_cache (b);
102 } 99 }
103 100
104 /* Update line_number_begv, or flag it as dirty. Do it only if the 101 /* Flag LINE_NUMBER_BEGV (b) as dirty. Do it only if the line number
105 line number cache is already initialized. */ 102 cache is already initialized. */
106 void 103 void
107 narrow_line_number_cache (struct buffer *b) 104 narrow_line_number_cache (struct buffer *b)
108 { 105 {
109 if (NILP (b->line_number_cache)) 106 if (NILP (b->line_number_cache))
110 return; 107 return;
111 /* Optimization: if BUF_BEG == BUF_BEGV (as is the case after Fwiden 108
112 and save_restriction_restore), don't bother calling scan_buffer. */
113 if (BUF_BEG (b) == BUF_BEGV (b)) 109 if (BUF_BEG (b) == BUF_BEGV (b))
114 { 110 /* The is the case Fwiden and save_restriction_restore. Since we
115 LINE_NUMBER_BEGV (b) = Qzero; 111 know the correct value, we can update it now. */
116 return; 112 LINE_NUMBER_BEGV (b) = Qzero;
117 } 113 else
118 /* Calculating the line number of BUF_BEGV here is a bad idea, 114 /* 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 115 because there is absolutely no reason to do it before the next
120 redisplay. We simply mark it as dirty instead. */ 116 redisplay. We simply mark it as dirty instead. */
121 LINE_NUMBER_BEGV (b) = make_int (-1); 117 LINE_NUMBER_BEGV (b) = make_int (-1);
122 } 118 }
123 119
124 /* Invalidate the line number cache positions that lie after POS. */ 120 /* Invalidate the line number cache positions that lie after POS. */
125 static void 121 static void
126 invalidate_line_number_cache (struct buffer *b, Bufpos pos) 122 invalidate_line_number_cache (struct buffer *b, Bufpos pos)
127 { 123 {
128 EMACS_INT i, j; 124 EMACS_INT i, j;
129 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b)); 125 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
130 Lisp_Object lisp_buffer = make_buffer (b);
131 126
132 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++) 127 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
133 { 128 {
134 if (!CONSP (ring[i])) 129 if (!CONSP (ring[i]))
135 break; 130 break;
136 /* As the marker stays behind the insertions, this check might 131 /* As the marker stays behind the insertions, this check might
137 as well be `>'. However, Finsert_before_markers can move the 132 as well be `>'. However, Finsert_before_markers can advance
138 marker anyway, which bites in shell buffers. 133 the marker anyway, which bites in shell buffers.
139 134
140 #### This is wrong; it works right, but forces recreation of 135 #### This forces recreation of the cached marker (and
141 the cached marker (and recalculation of newlines) every time 136 recalculation of newlines) every time a newline is inserted
142 a newline is inserted at point, which is way losing. Isn't 137 at point, which is way losing. Isn't there a way to make a
143 there a way to make a marker impervious to 138 marker impervious to Finsert_before_markers()?? Maybe I
144 Finsert_before_markers()?? Maybe I should convert to using 139 should convert the code to use extents. */
145 extents. */
146 if (marker_position (XCAR (ring[i])) >= pos) 140 if (marker_position (XCAR (ring[i])) >= pos)
147 { 141 {
148 /* Get the marker out of the way. */ 142 /* Get the marker out of the way. */
149 Fset_marker (XCAR (ring[i]), Qnil, lisp_buffer); 143 Fset_marker (XCAR (ring[i]), Qnil, Qnil);
150 /* ...and shift the ring elements, up to the first nil. */ 144 /* ...and shift the ring elements, up to the first nil. */
151 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++) 145 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++)
152 ring[j] = ring[j + 1]; 146 ring[j] = ring[j + 1];
153 ring[j] = Qnil; 147 ring[j] = Qnil;
154 /* Must recheck position i. */ 148 /* Must recheck position i. */
160 /* Invalidate the cache positions after POS, if the string to be 154 /* Invalidate the cache positions after POS, if the string to be
161 inserted contains a newline. If the string is too large (larger 155 inserted contains a newline. If the string is too large (larger
162 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions 156 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
163 after POS without prior search. 157 after POS without prior search.
164 158
165 This will do nothing, if cache is uninitialized. */ 159 This will do nothing if the cache is uninitialized. */
166 void 160 void
167 insert_invalidate_line_number_cache (struct buffer *b, Bufpos pos, 161 insert_invalidate_line_number_cache (struct buffer *b, Bufpos pos,
168 CONST Bufbyte *nonreloc, Bytecount length) 162 CONST Bufbyte *nonreloc, Bytecount length)
169 { 163 {
170 if (NILP (b->line_number_cache)) 164 if (NILP (b->line_number_cache))
171 return; 165 return;
172 166
173 if (length > LINE_NUMBER_LARGE_STRING 167 if (length > LINE_NUMBER_LARGE_STRING
174 || 168 ||
175 /* We could also count how many newlines are in the string, and 169 /* We could also count how many newlines there are in the string
176 update the cache accordingly, but it would be too much work 170 and update the cache accordingly, but it would be too much
177 for too little gain. */ 171 work for too little gain. */
178 memchr ((void *)nonreloc, '\n', (size_t) length)) 172 memchr ((void *)nonreloc, '\n', (size_t) length))
179 invalidate_line_number_cache (b, pos); 173 invalidate_line_number_cache (b, pos);
180 } 174 }
181 175
182 /* Invalidate the cache positions after FROM, if the region to be 176 /* Invalidate the cache positions after FROM, if the region to be
183 deleted contains a newline. If the region is too large (larger 177 deleted contains a newline. If the region-to-be-deleted is larger
184 than LINE_NUMBER_LARGE_STRING), invalidate the cache positions 178 than LINE_NUMBER_LARGE_STRING, invalidate the cache positions after
185 after FROM without prior search. 179 FROM without unconditionally.
186 180
187 This will do nothing, if cache is uninitialized. */ 181 This will do nothing if the cache is uninitialized. */
188 void 182 void
189 delete_invalidate_line_number_cache (struct buffer *b, Bufpos from, Bufpos to) 183 delete_invalidate_line_number_cache (struct buffer *b, Bufpos from, Bufpos to)
190 { 184 {
191 if (NILP (b->line_number_cache)) 185 if (NILP (b->line_number_cache))
192 return; 186 return;
213 This will initialize the cache, if necessary. */ 207 This will initialize the cache, if necessary. */
214 static void 208 static void
215 get_nearest_line_number (struct buffer *b, Bufpos *beg, Bufpos pos, 209 get_nearest_line_number (struct buffer *b, Bufpos *beg, Bufpos pos,
216 EMACS_INT *line) 210 EMACS_INT *line)
217 { 211 {
212 EMACS_INT i;
218 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b)); 213 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
219 EMACS_INT i; 214 Charcount length = pos - *beg;
220 Charcount length, howfar; 215
221 Bufpos newpos;
222
223 length = pos - *beg;
224 if (length < 0) 216 if (length < 0)
225 length = -length; 217 length = -length;
226 218
227 /* Look for the nearest match. */ 219 /* Find the ring entry closest to POS, if it is closer than BEG. */
228 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++) 220 for (i = 0; i < LINE_NUMBER_RING_SIZE && CONSP (ring[i]); i++)
229 { 221 {
230 if (!CONSP (ring[i])) 222 Bufpos newpos = marker_position (XCAR (ring[i]));
231 break; 223 Charcount howfar = newpos - pos;
232 newpos = marker_position (XCAR (ring[i]));
233 howfar = newpos - pos;
234 if (howfar < 0) 224 if (howfar < 0)
235 howfar = -howfar; 225 howfar = -howfar;
236 if (howfar < length) 226 if (howfar < length)
237 { 227 {
238 length = howfar; 228 length = howfar;
240 *line = XINT (XCDR (ring[i])); 230 *line = XINT (XCDR (ring[i]));
241 } 231 }
242 } 232 }
243 } 233 }
244 234
245 /* Add a (pos, line) pair to the ring, and rotate it. */ 235 /* Add a (POS . LINE) pair to the ring, and rotate it. */
246 static void 236 static void
247 add_line_number (struct buffer *b, Bufpos pos, int line) 237 add_position_to_cache (struct buffer *b, Bufpos pos, int line)
248 { 238 {
249 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b)); 239 Lisp_Object *ring = XVECTOR_DATA (LINE_NUMBER_RING (b));
250 Lisp_Object marker; 240 int i = LINE_NUMBER_RING_SIZE - 1;
251 int i; 241
252 242 /* Set the last marker in the ring to point nowhere. */
253 for (i = LINE_NUMBER_RING_SIZE - 1; i > 0; i--) 243 if (CONSP (ring[i]))
244 Fset_marker (XCAR (ring[i]), Qnil, Qnil);
245
246 /* Rotate the ring... */
247 for (; i > 0; i--)
254 ring[i] = ring[i - 1]; 248 ring[i] = ring[i - 1];
255 marker = Fmake_marker (); 249
256 Fset_marker (marker, make_int (pos), make_buffer (b)); 250 /* ...and update it. */
257 ring[0] = Fcons (marker, make_int (line)); 251 ring[0] = Fcons (Fset_marker (Fmake_marker (), make_int (pos),
252 make_buffer (b)),
253 make_int (line));
258 } 254 }
259 255
260 /* Calculate the line number in buffer B at position POS. If CACHEP 256 /* Calculate the line number in buffer B at position POS. If CACHEP
261 is non-zero, initialize and facilitate the line-number cache. The 257 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, 258 line number of the first line is 0. If narrowing is in effect,
270 LINE_NUMBER_FAR), try to find a closer position in the ring. If it 266 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 267 is found, use that position for BEG, and increment the line number
272 appropriately. 268 appropriately.
273 269
274 If the calculation (with or without the cache lookup) required more 270 If the calculation (with or without the cache lookup) required more
275 than LINE_NUMBER_FAR bytes of traversal, update the cache. */ 271 than LINE_NUMBER_FAR characters of traversal, update the cache. */
276 EMACS_INT 272 EMACS_INT
277 buffer_line_number (struct buffer *b, Bufpos pos, int cachep) 273 buffer_line_number (struct buffer *b, Bufpos pos, int cachep)
278 { 274 {
279 Bufpos beg = BUF_BEGV (b); 275 Bufpos beg = BUF_BEGV (b);
280 EMACS_INT cached_lines = 0; 276 EMACS_INT cached_lines = 0;
312 308
313 if (cachep) 309 if (cachep)
314 { 310 {
315 /* If too far, update the cache. */ 311 /* If too far, update the cache. */
316 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR) 312 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
317 add_line_number (b, pos, line); 313 add_position_to_cache (b, pos, line);
318 /* Account for narrowing. If CACHEP is nil, this is 314 /* Account for narrowing. If cache is not used, this is
319 unnecessary, because we counted from BUF_BEGV anyway. */ 315 unnecessary, because we counted from BUF_BEGV anyway. */
320 line -= XINT (LINE_NUMBER_BEGV (b)); 316 line -= XINT (LINE_NUMBER_BEGV (b));
321 } 317 }
322 318
323 return line; 319 return line;
324 } 320 }
325