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