Mercurial > hg > xemacs-beta

comparison src/line-number.c @ 219:262b8bb4a523 r20-4b8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-4b8
author cvs
date Mon, 13 Aug 2007 10:09:35 +0200
parents 78478c60bfcd
children f955c73f5258
comparison
equal deleted inserted replaced
218:c9f226976f56 219:262b8bb4a523
1 /* Line number cache routines. 1 /* Line number cache.
2 Copyright (C) 1997 Free Software Foundation, Inc. 2 Copyright (C) 1997 Free Software Foundation, Inc.
3 3
4 This file is part of XEmacs. 4 This file is part of XEmacs.
5 5
6 XEmacs is free software; you can redistribute it and/or modify it 6 XEmacs is free software; you can redistribute it and/or modify it
36 buffer (see the comment to window_line_number.) 36 buffer (see the comment to window_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. 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.
42 46
43 NOTE: line-number cache should not be confused with line-start 47 NOTE: line-number cache should not be confused with line-start
44 cache. Line-start cache (a part of redisplay) works with the 48 cache. Line-start cache (a part of redisplay) works with the
45 display lines, whereas this works with the buffer lines (literally 49 display lines, whereas this works with the buffer lines (literally
46 counting the newlines). */ 50 counting the newlines). */
52 56
53 #include "line-number.h" 57 #include "line-number.h"
54 58
55 59
56 /* #### The following three values could use some tweaking, to get the 60 /* #### The following three values could use some tweaking, to get the
57 best performance. */ 61 best performance. I suspect LINE_NUMBER_FAR and
62 LINE_NUMBER_LARGE_STRING could be made bigger. */
58 63
59 /* Size of the ring. The current code expects this to be a small 64 /* 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 65 number. If you make it much bigger, you should probably tr yto
61 optimize the various routines to keep it sorted. */ 66 optimize the various routines to keep it sorted. */
62 #define LINE_NUMBER_RING_SIZE 8 67 #define LINE_NUMBER_RING_SIZE 8
94 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil), 99 b->line_number_cache = Fcons (make_vector (LINE_NUMBER_RING_SIZE, Qnil),
95 Qzero); 100 Qzero);
96 narrow_line_number_cache (b); 101 narrow_line_number_cache (b);
97 } 102 }
98 103
99 /* Update line_number_begv. Do it only if the line number cache is 104 /* Update line_number_begv, or flag it as dirty. Do it only if the
100 already initialized. */ 105 line number cache is already initialized. */
101 void 106 void
102 narrow_line_number_cache (struct buffer *b) 107 narrow_line_number_cache (struct buffer *b)
103 { 108 {
104 EMACS_INT lots = 999999999, shortage;
105
106 if (NILP (b->line_number_cache)) 109 if (NILP (b->line_number_cache))
107 return; 110 return;
108 /* Optimization: if BUF_BEG == BUF_BEGV (as is the case after Fwiden 111 /* Optimization: if BUF_BEG == BUF_BEGV (as is the case after Fwiden
109 and save_restriction_restore), don't bother calling scan_buffer. */ 112 and save_restriction_restore), don't bother calling scan_buffer. */
110 if (BUF_BEG (b) == BUF_BEGV (b)) 113 if (BUF_BEG (b) == BUF_BEGV (b))
111 { 114 {
112 LINE_NUMBER_BEGV (b) = Qzero; 115 LINE_NUMBER_BEGV (b) = Qzero;
113 return; 116 return;
114 } 117 }
115 /* Count the newlines between beginning of buffer and beginning of 118 /* Calculating the line number of BUF_BEGV here is a bad idea,
116 the visible portion of the buffer. */ 119 because there is absolutely no reason to do it before the next
117 scan_buffer (b, '\n', BUF_BEG (b), BUF_BEGV (b), lots, 120 redisplay. We simply mark it as dirty instead. */
118 (int *)&shortage, 0); 121 LINE_NUMBER_BEGV (b) = make_int (-1);
119 LINE_NUMBER_BEGV (b) = make_int (lots - shortage);
120 } 122 }
121 123
122 /* Invalidate the line number cache positions that lie after POS. */ 124 /* Invalidate the line number cache positions that lie after POS. */
123 static void 125 static void
124 invalidate_line_number_cache (struct buffer *b, Bufpos pos) 126 invalidate_line_number_cache (struct buffer *b, Bufpos pos)
129 131
130 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++) 132 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++)
131 { 133 {
132 if (!CONSP (ring[i])) 134 if (!CONSP (ring[i]))
133 break; 135 break;
134 if (marker_position (XCAR (ring[i])) > pos) 136 /* As the marker stays behind the insertions, this check might
137 as well be >=. However, Finsert_before_markers can move the
138 marker anyway, which bites in shell buffers. */
139 if (marker_position (XCAR (ring[i])) >= pos)
135 { 140 {
136 /* Get the marker out of the way. */ 141 /* Get the marker out of the way. */
137 Fset_marker (XCAR (ring[i]), Qnil, lisp_buffer); 142 Fset_marker (XCAR (ring[i]), Qnil, lisp_buffer);
138 /* ...and shift the ring elements, up to the first nil. */ 143 /* ...and shift the ring elements, up to the first nil. */
139 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++) 144 for (j = i; !NILP (ring[j]) && j < LINE_NUMBER_RING_SIZE - 1; j++)
140 ring[j] = ring[j + 1]; 145 ring[j] = ring[j + 1];
141 ring[j] = Qnil; 146 ring[j] = Qnil;
142 /* Must reevaluate the thing at position i. */ 147 /* Must recheck position i. */
143 i--; 148 i--;
144 } 149 }
145 } 150 }
146 } 151 }
147 152
184 else 189 else
185 { 190 {
186 int shortage; 191 int shortage;
187 scan_buffer (b, '\n', from, to, 1, &shortage, 0); 192 scan_buffer (b, '\n', from, to, 1, &shortage, 0);
188 if (!shortage) 193 if (!shortage)
189 /* The same as above applies. */
190 invalidate_line_number_cache (b, from); 194 invalidate_line_number_cache (b, from);
191 } 195 }
192 } 196 }
193 197
194 198
195 /* Get the nearest known position we know the line number of 199 /* Get the nearest known position we know the line number of
196 (i.e. BUF_BEGV, and cached positions). The return position will be 200 (i.e. BUF_BEGV, and cached positions). The return position will be
197 either closer than BEG, or BEG. 201 either closer than BEG, or BEG. The line of this known position
202 will be stored in LINE.
198 203
199 *LINE should be initialized to the line number of BEG (normally, 204 *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). 205 BEG will be BUF_BEGV, and *LINE will be XINT (LINE_NUMBER_BEGV).
201 This will initialize the cache, if necessary. */ 206 This will initialize the cache, if necessary. */
202 static void 207 static void
243 marker = Fmake_marker (); 248 marker = Fmake_marker ();
244 Fset_marker (marker, make_int (pos), make_buffer (b)); 249 Fset_marker (marker, make_int (pos), make_buffer (b));
245 ring[0] = Fcons (marker, make_int (line)); 250 ring[0] = Fcons (marker, make_int (line));
246 } 251 }
247 252
248 /* Calculate the buffer line number. If CACHEP is non-zero, 253 /* Calculate the line number in buffer B at position POS. If CACHEP
249 initialize the line-number cache for future use. The line number 254 is non-zero, initialize and facilitate the line-number cache. The
250 of the first line is 0. If narrowing is in effect, count the lines 255 line number of the first line is 0. If narrowing is in effect,
251 from the beginning of the visible portion of the buffer. 256 count the lines are counted from the beginning of the visible
257 portion of the buffer.
252 258
253 The cache works as follows: To calculate the line number, we need 259 The cache works as follows: To calculate the line number, we need
254 two positions: position of point (POS) and the position from which 260 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 261 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 > 262 this would require too much searching (i.e. pos - BUF_BEGV >
263 EMACS_INT 269 EMACS_INT
264 buffer_line_number (struct buffer *b, Bufpos pos, int cachep) 270 buffer_line_number (struct buffer *b, Bufpos pos, int cachep)
265 { 271 {
266 Bufpos beg = BUF_BEGV (b); 272 Bufpos beg = BUF_BEGV (b);
267 EMACS_INT cached_lines = 0; 273 EMACS_INT cached_lines = 0;
268 EMACS_INT lots = 999999999;
269 EMACS_INT shortage, line; 274 EMACS_INT shortage, line;
275
276 if ((pos > beg ? pos - beg : beg - pos) <= LINE_NUMBER_FAR)
277 cachep = 0;
270 278
271 if (cachep) 279 if (cachep)
272 { 280 {
273 if (NILP (b->line_number_cache)) 281 if (NILP (b->line_number_cache))
274 allocate_line_number_cache (b); 282 allocate_line_number_cache (b);
283 /* If we don't know the line number of BUF_BEGV, calculate it now. */
284 if (XINT (LINE_NUMBER_BEGV (b)) == -1)
285 {
286 LINE_NUMBER_BEGV (b) = Qzero;
287 /* #### This has a side-effect of changing the cache. */
288 LINE_NUMBER_BEGV (b) =
289 make_int (buffer_line_number (b, BUF_BEGV (b), 1));
290 }
275 cached_lines = XINT (LINE_NUMBER_BEGV (b)); 291 cached_lines = XINT (LINE_NUMBER_BEGV (b));
276 get_nearest_line_number (b, &beg, pos, &cached_lines); 292 get_nearest_line_number (b, &beg, pos, &cached_lines);
277 } 293 }
278 294
279 scan_buffer (b, '\n', beg, pos, pos > beg ? lots : -lots, 295 /* An EMACS_MAXINT would be cool to have. */
296 #define LOTS 999999999
297
298 scan_buffer (b, '\n', beg, pos, pos > beg ? LOTS : -LOTS,
280 (int *)&shortage, 0); 299 (int *)&shortage, 0);
281 300
282 line = lots - shortage; 301 line = LOTS - shortage;
283 if (beg > pos) 302 if (beg > pos)
284 line = -line; 303 line = -line;
285 line += cached_lines; 304 line += cached_lines;
286 305
287 if (cachep) 306 if (cachep)
289 /* If too far, update the cache. */ 308 /* If too far, update the cache. */
290 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR) 309 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
291 add_line_number (b, pos, line); 310 add_line_number (b, pos, line);
292 /* Account for narrowing. If CACHEP is nil, this is 311 /* Account for narrowing. If CACHEP is nil, this is
293 unnecessary, because we counted from BUF_BEGV anyway. */ 312 unnecessary, because we counted from BUF_BEGV anyway. */
294 if (cachep) 313 line -= XINT (LINE_NUMBER_BEGV (b));
295 line -= XINT (LINE_NUMBER_BEGV (b));
296 } 314 }
297 315
298 return line; 316 return line;
299 } 317 }
300 318