Mercurial > emacs
annotate src/region-cache.c @ 109147:783986775ee8
Set default-frame-alist, if necessary, in menu/tool-bar-mode.
* menu-bar.el (menu-bar-mode):
* tool-bar.el (tool-bar-mode): Replace default-frame-alist element
if it has been set.
author | Chong Yidong <cyd@stupidchicken.com> |
---|---|
date | Mon, 05 Jul 2010 13:54:13 -0400 |
parents | aec1143e8d85 |
children | 875202ac5b45 |
rev | line source |
---|---|
11047 | 1 /* Caching facts about regions of the buffer, for optimization. |
75227
e90d04cd455a
Update copyright for years from Emacs 21 to present (mainly adding
Glenn Morris <rgm@gnu.org>
parents:
68651
diff
changeset
|
2 Copyright (C) 1985, 1986, 1987, 1988, 1989, 1993, 1995, 2001, 2002, 2003, |
106815 | 3 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
11047 | 4 |
5 This file is part of GNU Emacs. | |
6 | |
94963
8971ddf55736
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
79759
diff
changeset
|
7 GNU Emacs is free software: you can redistribute it and/or modify |
11047 | 8 it under the terms of the GNU General Public License as published by |
94963
8971ddf55736
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
79759
diff
changeset
|
9 the Free Software Foundation, either version 3 of the License, or |
8971ddf55736
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
79759
diff
changeset
|
10 (at your option) any later version. |
11047 | 11 |
12 GNU Emacs is distributed in the hope that it will be useful, | |
13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 GNU General Public License for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
94963
8971ddf55736
Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents:
79759
diff
changeset
|
18 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */ |
11047 | 19 |
20 | |
21 #include <config.h> | |
53901
d85f8f2e71f7
Move include stdio.h to same place as in other files.
Jan Djärv <jan.h.d@swipnet.se>
parents:
52401
diff
changeset
|
22 #include <stdio.h> |
105669
68dd71358159
* alloc.c: Do not define struct catchtag.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
100951
diff
changeset
|
23 #include <setjmp.h> |
53901
d85f8f2e71f7
Move include stdio.h to same place as in other files.
Jan Djärv <jan.h.d@swipnet.se>
parents:
52401
diff
changeset
|
24 |
11047 | 25 #include "lisp.h" |
26 #include "buffer.h" | |
27 #include "region-cache.h" | |
28 | |
29 | |
30 /* Data structures. */ | |
31 | |
32 /* The region cache. | |
33 | |
34 We want something that maps character positions in a buffer onto | |
35 values. The representation should deal well with long runs of | |
36 characters with the same value. | |
37 | |
38 The tricky part: the representation should be very cheap to | |
39 maintain in the presence of many insertions and deletions. If the | |
40 overhead of maintaining the cache is too high, the speedups it | |
41 offers will be worthless. | |
42 | |
43 | |
44 We represent the region cache as a sorted array of struct | |
45 boundary's, each of which contains a buffer position and a value; | |
46 the value applies to all the characters after the buffer position, | |
47 until the position of the next boundary, or the end of the buffer. | |
48 | |
49 The cache always has a boundary whose position is BUF_BEG, so | |
50 there's always a value associated with every character in the | |
51 buffer. Since the cache is sorted, this is always the first | |
52 element of the cache. | |
53 | |
54 To facilitate the insertion and deletion of boundaries in the | |
55 cache, the cache has a gap, just like Emacs's text buffers do. | |
56 | |
57 To help boundary positions float along with insertions and | |
58 deletions, all boundary positions before the cache gap are stored | |
59 relative to BUF_BEG (buf) (thus they're >= 0), and all boundary | |
60 positions after the gap are stored relative to BUF_Z (buf) (thus | |
61 they're <= 0). Look at BOUNDARY_POS to see this in action. See | |
62 revalidate_region_cache to see how this helps. */ | |
63 | |
64 struct boundary { | |
65 int pos; | |
66 int value; | |
67 }; | |
68 | |
69 struct region_cache { | |
70 /* A sorted array of locations where the known-ness of the buffer | |
71 changes. */ | |
72 struct boundary *boundaries; | |
73 | |
74 /* boundaries[gap_start ... gap_start + gap_len - 1] is the gap. */ | |
75 int gap_start, gap_len; | |
76 | |
77 /* The number of elements allocated to boundaries, not including the | |
78 gap. */ | |
79 int cache_len; | |
80 | |
81 /* The areas that haven't changed since the last time we cleaned out | |
82 invalid entries from the cache. These overlap when the buffer is | |
83 entirely unchanged. */ | |
84 int beg_unchanged, end_unchanged; | |
85 | |
86 /* The first and last positions in the buffer. Because boundaries | |
87 store their positions relative to the start (BEG) and end (Z) of | |
88 the buffer, knowing these positions allows us to accurately | |
89 interpret positions without having to pass the buffer structure | |
90 or its endpoints around all the time. | |
91 | |
92 Yes, buffer_beg is always 1. It's there for symmetry with | |
93 buffer_end and the BEG and BUF_BEG macros. */ | |
94 int buffer_beg, buffer_end; | |
95 }; | |
96 | |
97 /* Return the position of boundary i in cache c. */ | |
98 #define BOUNDARY_POS(c, i) \ | |
99 ((i) < (c)->gap_start \ | |
100 ? (c)->buffer_beg + (c)->boundaries[(i)].pos \ | |
101 : (c)->buffer_end + (c)->boundaries[(c)->gap_len + (i)].pos) | |
102 | |
103 /* Return the value for text after boundary i in cache c. */ | |
104 #define BOUNDARY_VALUE(c, i) \ | |
105 ((i) < (c)->gap_start \ | |
106 ? (c)->boundaries[(i)].value \ | |
107 : (c)->boundaries[(c)->gap_len + (i)].value) | |
108 | |
109 /* Set the value for text after boundary i in cache c to v. */ | |
110 #define SET_BOUNDARY_VALUE(c, i, v) \ | |
111 ((i) < (c)->gap_start \ | |
112 ? ((c)->boundaries[(i)].value = (v))\ | |
113 : ((c)->boundaries[(c)->gap_len + (i)].value = (v))) | |
114 | |
115 | |
116 /* How many elements to add to the gap when we resize the buffer. */ | |
117 #define NEW_CACHE_GAP (40) | |
118 | |
119 /* See invalidate_region_cache; if an invalidation would throw away | |
120 information about this many characters, call | |
121 revalidate_region_cache before doing the new invalidation, to | |
122 preserve that information, instead of throwing it away. */ | |
123 #define PRESERVE_THRESHOLD (500) | |
124 | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
125 static void revalidate_region_cache (struct buffer *buf, struct region_cache *c); |
11047 | 126 |
127 | |
128 /* Interface: Allocating, initializing, and disposing of region caches. */ | |
129 | |
130 struct region_cache * | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
131 new_region_cache (void) |
11047 | 132 { |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
133 struct region_cache *c |
11047 | 134 = (struct region_cache *) xmalloc (sizeof (struct region_cache)); |
135 | |
136 c->gap_start = 0; | |
137 c->gap_len = NEW_CACHE_GAP; | |
138 c->cache_len = 0; | |
139 c->boundaries = | |
140 (struct boundary *) xmalloc ((c->gap_len + c->cache_len) | |
141 * sizeof (*c->boundaries)); | |
142 | |
143 c->beg_unchanged = 0; | |
144 c->end_unchanged = 0; | |
44621
f713f6056d87
(new_region_cache): Use BEG.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
14186
diff
changeset
|
145 c->buffer_beg = BEG; |
f713f6056d87
(new_region_cache): Use BEG.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
14186
diff
changeset
|
146 c->buffer_end = BEG; |
11047 | 147 |
148 /* Insert the boundary for the buffer start. */ | |
149 c->cache_len++; | |
150 c->gap_len--; | |
151 c->gap_start++; | |
152 c->boundaries[0].pos = 0; /* from buffer_beg */ | |
153 c->boundaries[0].value = 0; | |
154 | |
155 return c; | |
156 } | |
157 | |
158 void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
159 free_region_cache (struct region_cache *c) |
11047 | 160 { |
161 xfree (c->boundaries); | |
162 xfree (c); | |
163 } | |
164 | |
165 | |
166 /* Finding positions in the cache. */ | |
167 | |
168 /* Return the index of the last boundary in cache C at or before POS. | |
169 In other words, return the boundary that specifies the value for | |
170 the region POS..(POS + 1). | |
171 | |
172 This operation should be logarithmic in the number of cache | |
173 entries. It would be nice if it took advantage of locality of | |
174 reference, too, by searching entries near the last entry found. */ | |
175 static int | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
176 find_cache_boundary (struct region_cache *c, int pos) |
11047 | 177 { |
178 int low = 0, high = c->cache_len; | |
179 | |
180 while (low + 1 < high) | |
181 { | |
182 /* mid is always a valid index, because low < high and ">> 1" | |
183 rounds down. */ | |
184 int mid = (low + high) >> 1; | |
185 int boundary = BOUNDARY_POS (c, mid); | |
186 | |
187 if (pos < boundary) | |
188 high = mid; | |
189 else | |
190 low = mid; | |
191 } | |
192 | |
193 /* Some testing. */ | |
194 if (BOUNDARY_POS (c, low) > pos | |
195 || (low + 1 < c->cache_len | |
196 && BOUNDARY_POS (c, low + 1) <= pos)) | |
197 abort (); | |
198 | |
199 return low; | |
200 } | |
201 | |
202 | |
203 | |
204 /* Moving the cache gap around, inserting, and deleting. */ | |
205 | |
206 | |
207 /* Move the gap of cache C to index POS, and make sure it has space | |
208 for at least MIN_SIZE boundaries. */ | |
209 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
210 move_cache_gap (struct region_cache *c, int pos, int min_size) |
11047 | 211 { |
212 /* Copy these out of the cache and into registers. */ | |
213 int gap_start = c->gap_start; | |
214 int gap_len = c->gap_len; | |
215 int buffer_beg = c->buffer_beg; | |
216 int buffer_end = c->buffer_end; | |
217 | |
218 if (pos < 0 | |
219 || pos > c->cache_len) | |
220 abort (); | |
221 | |
222 /* We mustn't ever try to put the gap before the dummy start | |
223 boundary. That must always be start-relative. */ | |
224 if (pos == 0) | |
225 abort (); | |
226 | |
227 /* Need we move the gap right? */ | |
228 while (gap_start < pos) | |
229 { | |
230 /* Copy one boundary from after to before the gap, and | |
231 convert its position to start-relative. */ | |
232 c->boundaries[gap_start].pos | |
233 = (buffer_end | |
234 + c->boundaries[gap_start + gap_len].pos | |
235 - buffer_beg); | |
236 c->boundaries[gap_start].value | |
237 = c->boundaries[gap_start + gap_len].value; | |
238 gap_start++; | |
239 } | |
240 | |
241 /* To enlarge the gap, we need to re-allocate the boundary array, and | |
242 then shift the area after the gap to the new end. Since the cost | |
243 is proportional to the amount of stuff after the gap, we do the | |
244 enlargement here, after a right shift but before a left shift, | |
245 when the portion after the gap is smallest. */ | |
246 if (gap_len < min_size) | |
247 { | |
248 int i; | |
249 | |
250 /* Always make at least NEW_CACHE_GAP elements, as long as we're | |
251 expanding anyway. */ | |
252 if (min_size < NEW_CACHE_GAP) | |
253 min_size = NEW_CACHE_GAP; | |
254 | |
255 c->boundaries = | |
256 (struct boundary *) xrealloc (c->boundaries, | |
257 ((min_size + c->cache_len) | |
258 * sizeof (*c->boundaries))); | |
259 | |
260 /* Some systems don't provide a version of the copy routine that | |
261 can be trusted to shift memory upward into an overlapping | |
262 region. memmove isn't widely available. */ | |
263 min_size -= gap_len; | |
264 for (i = c->cache_len - 1; i >= gap_start; i--) | |
265 { | |
266 c->boundaries[i + min_size].pos = c->boundaries[i + gap_len].pos; | |
267 c->boundaries[i + min_size].value = c->boundaries[i + gap_len].value; | |
268 } | |
269 | |
270 gap_len = min_size; | |
271 } | |
272 | |
273 /* Need we move the gap left? */ | |
274 while (pos < gap_start) | |
275 { | |
276 gap_start--; | |
277 | |
278 /* Copy one region from before to after the gap, and | |
279 convert its position to end-relative. */ | |
280 c->boundaries[gap_start + gap_len].pos | |
281 = c->boundaries[gap_start].pos + buffer_beg - buffer_end; | |
282 c->boundaries[gap_start + gap_len].value | |
283 = c->boundaries[gap_start].value; | |
284 } | |
285 | |
286 /* Assign these back into the cache. */ | |
287 c->gap_start = gap_start; | |
288 c->gap_len = gap_len; | |
289 } | |
290 | |
291 | |
292 /* Insert a new boundary in cache C; it will have cache index INDEX, | |
293 and have the specified POS and VALUE. */ | |
294 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
295 insert_cache_boundary (struct region_cache *c, int index, int pos, int value) |
11047 | 296 { |
297 /* index must be a valid cache index. */ | |
298 if (index < 0 || index > c->cache_len) | |
299 abort (); | |
300 | |
301 /* We must never want to insert something before the dummy first | |
302 boundary. */ | |
303 if (index == 0) | |
304 abort (); | |
305 | |
306 /* We must only be inserting things in order. */ | |
307 if (! (BOUNDARY_POS (c, index-1) < pos | |
308 && (index == c->cache_len | |
309 || pos < BOUNDARY_POS (c, index)))) | |
310 abort (); | |
311 | |
312 /* The value must be different from the ones around it. However, we | |
313 temporarily create boundaries that establish the same value as | |
314 the subsequent boundary, so we're not going to flag that case. */ | |
315 if (BOUNDARY_VALUE (c, index-1) == value) | |
316 abort (); | |
317 | |
318 move_cache_gap (c, index, 1); | |
319 | |
320 c->boundaries[index].pos = pos - c->buffer_beg; | |
321 c->boundaries[index].value = value; | |
322 c->gap_start++; | |
323 c->gap_len--; | |
324 c->cache_len++; | |
325 } | |
326 | |
327 | |
328 /* Delete the i'th entry from cache C if START <= i < END. */ | |
329 | |
330 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
331 delete_cache_boundaries (struct region_cache *c, int start, int end) |
11047 | 332 { |
333 int len = end - start; | |
334 | |
335 /* Gotta be in range. */ | |
336 if (start < 0 | |
337 || end > c->cache_len) | |
338 abort (); | |
339 | |
340 /* Gotta be in order. */ | |
341 if (start > end) | |
342 abort (); | |
343 | |
344 /* Can't delete the dummy entry. */ | |
345 if (start == 0 | |
346 && end >= 1) | |
347 abort (); | |
348 | |
349 /* Minimize gap motion. If we're deleting nothing, do nothing. */ | |
350 if (len == 0) | |
351 ; | |
352 /* If the gap is before the region to delete, delete from the start | |
353 forward. */ | |
354 else if (c->gap_start <= start) | |
355 { | |
356 move_cache_gap (c, start, 0); | |
357 c->gap_len += len; | |
358 } | |
359 /* If the gap is after the region to delete, delete from the end | |
360 backward. */ | |
361 else if (end <= c->gap_start) | |
362 { | |
363 move_cache_gap (c, end, 0); | |
364 c->gap_start -= len; | |
365 c->gap_len += len; | |
366 } | |
367 /* If the gap is in the region to delete, just expand it. */ | |
368 else | |
369 { | |
370 c->gap_start = start; | |
371 c->gap_len += len; | |
372 } | |
373 | |
374 c->cache_len -= len; | |
375 } | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
376 |
11047 | 377 |
378 | |
379 /* Set the value for a region. */ | |
380 | |
381 /* Set the value in cache C for the region START..END to VALUE. */ | |
382 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
383 set_cache_region (struct region_cache *c, int start, int end, int value) |
11047 | 384 { |
385 if (start > end) | |
386 abort (); | |
387 if (start < c->buffer_beg | |
388 || end > c->buffer_end) | |
389 abort (); | |
390 | |
391 /* Eliminate this case; then we can assume that start and end-1 are | |
392 both the locations of real characters in the buffer. */ | |
393 if (start == end) | |
394 return; | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
395 |
11047 | 396 { |
397 /* We need to make sure that there are no boundaries in the area | |
398 between start to end; the whole area will have the same value, | |
399 so those boundaries will not be necessary. | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
400 |
11047 | 401 Let start_ix be the cache index of the boundary governing the |
402 first character of start..end, and let end_ix be the cache | |
403 index of the earliest boundary after the last character in | |
404 start..end. (This tortured terminology is intended to answer | |
405 all the "< or <=?" sort of questions.) */ | |
406 int start_ix = find_cache_boundary (c, start); | |
407 int end_ix = find_cache_boundary (c, end - 1) + 1; | |
408 | |
409 /* We must remember the value established by the last boundary | |
410 before end; if that boundary's domain stretches beyond end, | |
411 we'll need to create a new boundary at end, and that boundary | |
412 must have that remembered value. */ | |
413 int value_at_end = BOUNDARY_VALUE (c, end_ix - 1); | |
414 | |
415 /* Delete all boundaries strictly within start..end; this means | |
416 those whose indices are between start_ix (exclusive) and end_ix | |
417 (exclusive). */ | |
418 delete_cache_boundaries (c, start_ix + 1, end_ix); | |
419 | |
420 /* Make sure we have the right value established going in to | |
421 start..end from the left, and no unnecessary boundaries. */ | |
422 if (BOUNDARY_POS (c, start_ix) == start) | |
423 { | |
424 /* Is this boundary necessary? If no, remove it; if yes, set | |
425 its value. */ | |
426 if (start_ix > 0 | |
427 && BOUNDARY_VALUE (c, start_ix - 1) == value) | |
428 { | |
429 delete_cache_boundaries (c, start_ix, start_ix + 1); | |
430 start_ix--; | |
431 } | |
432 else | |
433 SET_BOUNDARY_VALUE (c, start_ix, value); | |
434 } | |
435 else | |
436 { | |
437 /* Do we need to add a new boundary here? */ | |
438 if (BOUNDARY_VALUE (c, start_ix) != value) | |
439 { | |
440 insert_cache_boundary (c, start_ix + 1, start, value); | |
441 start_ix++; | |
442 } | |
443 } | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
444 |
11047 | 445 /* This is equivalent to letting end_ix float (like a buffer |
446 marker does) with the insertions and deletions we may have | |
447 done. */ | |
448 end_ix = start_ix + 1; | |
449 | |
450 /* Make sure we have the correct value established as we leave | |
451 start..end to the right. */ | |
452 if (end == c->buffer_end) | |
453 /* There is no text after start..end; nothing to do. */ | |
454 ; | |
455 else if (end_ix >= c->cache_len | |
456 || end < BOUNDARY_POS (c, end_ix)) | |
457 { | |
458 /* There is no boundary at end, but we may need one. */ | |
459 if (value_at_end != value) | |
460 insert_cache_boundary (c, end_ix, end, value_at_end); | |
461 } | |
462 else | |
463 { | |
464 /* There is a boundary at end; should it be there? */ | |
465 if (value == BOUNDARY_VALUE (c, end_ix)) | |
466 delete_cache_boundaries (c, end_ix, end_ix + 1); | |
467 } | |
468 } | |
469 } | |
470 | |
471 | |
472 | |
473 /* Interface: Invalidating the cache. Private: Re-validating the cache. */ | |
474 | |
475 /* Indicate that a section of BUF has changed, to invalidate CACHE. | |
476 HEAD is the number of chars unchanged at the beginning of the buffer. | |
477 TAIL is the number of chars unchanged at the end of the buffer. | |
478 NOTE: this is *not* the same as the ending position of modified | |
479 region. | |
480 (This way of specifying regions makes more sense than absolute | |
481 buffer positions in the presence of insertions and deletions; the | |
482 args to pass are the same before and after such an operation.) */ | |
483 void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
484 invalidate_region_cache (struct buffer *buf, struct region_cache *c, int head, int tail) |
11047 | 485 { |
486 /* Let chead = c->beg_unchanged, and | |
487 ctail = c->end_unchanged. | |
488 If z-tail < beg+chead by a large amount, or | |
489 z-ctail < beg+head by a large amount, | |
490 | |
491 then cutting back chead and ctail to head and tail would lose a | |
492 lot of information that we could preserve by revalidating the | |
493 cache before processing this invalidation. Losing that | |
494 information may be more costly than revalidating the cache now. | |
495 So go ahead and call revalidate_region_cache if it seems that it | |
496 might be worthwhile. */ | |
497 if (((BUF_BEG (buf) + c->beg_unchanged) - (BUF_Z (buf) - tail) | |
498 > PRESERVE_THRESHOLD) | |
499 || ((BUF_BEG (buf) + head) - (BUF_Z (buf) - c->end_unchanged) | |
500 > PRESERVE_THRESHOLD)) | |
501 revalidate_region_cache (buf, c); | |
502 | |
503 | |
504 if (head < c->beg_unchanged) | |
505 c->beg_unchanged = head; | |
506 if (tail < c->end_unchanged) | |
507 c->end_unchanged = tail; | |
508 | |
509 /* We now know nothing about the region between the unchanged head | |
510 and the unchanged tail (call it the "modified region"), not even | |
511 its length. | |
512 | |
513 If the modified region has shrunk in size (deletions do this), | |
514 then the cache may now contain boundaries originally located in | |
515 text that doesn't exist any more. | |
516 | |
517 If the modified region has increased in size (insertions do | |
518 this), then there may now be boundaries in the modified region | |
519 whose positions are wrong. | |
520 | |
521 Even calling BOUNDARY_POS on boundaries still in the unchanged | |
522 head or tail may well give incorrect answers now, since | |
523 c->buffer_beg and c->buffer_end may well be wrong now. (Well, | |
524 okay, c->buffer_beg never changes, so boundaries in the unchanged | |
525 head will still be okay. But it's the principle of the thing.) | |
526 | |
527 So things are generally a mess. | |
528 | |
529 But we don't clean up this mess here; that would be expensive, | |
530 and this function gets called every time any buffer modification | |
531 occurs. Rather, we can clean up everything in one swell foop, | |
532 accounting for all the modifications at once, by calling | |
533 revalidate_region_cache before we try to consult the cache the | |
534 next time. */ | |
535 } | |
536 | |
537 | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
538 /* Clean out any cache entries applying to the modified region, and |
11047 | 539 make the positions of the remaining entries accurate again. |
540 | |
541 After calling this function, the mess described in the comment in | |
542 invalidate_region_cache is cleaned up. | |
543 | |
544 This function operates by simply throwing away everything it knows | |
545 about the modified region. It doesn't care exactly which | |
546 insertions and deletions took place; it just tosses it all. | |
547 | |
548 For example, if you insert a single character at the beginning of | |
549 the buffer, and a single character at the end of the buffer (for | |
550 example), without calling this function in between the two | |
551 insertions, then the entire cache will be freed of useful | |
552 information. On the other hand, if you do manage to call this | |
553 function in between the two insertions, then the modified regions | |
554 will be small in both cases, no information will be tossed, and the | |
555 cache will know that it doesn't have knowledge of the first and | |
556 last characters any more. | |
557 | |
558 Calling this function may be expensive; it does binary searches in | |
559 the cache, and causes cache gap motion. */ | |
560 | |
561 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
562 revalidate_region_cache (struct buffer *buf, struct region_cache *c) |
11047 | 563 { |
564 /* The boundaries now in the cache are expressed relative to the | |
565 buffer_beg and buffer_end values stored in the cache. Now, | |
566 buffer_beg and buffer_end may not be the same as BUF_BEG (buf) | |
567 and BUF_Z (buf), so we have two different "bases" to deal with | |
568 --- the cache's, and the buffer's. */ | |
569 | |
570 /* If the entire buffer is still valid, don't waste time. Yes, this | |
571 should be a >, not a >=; think about what beg_unchanged and | |
572 end_unchanged get set to when the only change has been an | |
573 insertion. */ | |
574 if (c->buffer_beg + c->beg_unchanged | |
575 > c->buffer_end - c->end_unchanged) | |
576 return; | |
577 | |
578 /* If all the text we knew about as of the last cache revalidation | |
579 is still there, then all of the information in the cache is still | |
580 valid. Because c->buffer_beg and c->buffer_end are out-of-date, | |
581 the modified region appears from the cache's point of view to be | |
582 a null region located someplace in the buffer. | |
583 | |
584 Now, invalidating that empty string will have no actual affect on | |
585 the cache; instead, we need to update the cache's basis first | |
586 (which will give the modified region the same size in the cache | |
587 as it has in the buffer), and then invalidate the modified | |
588 region. */ | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
589 if (c->buffer_beg + c->beg_unchanged |
11047 | 590 == c->buffer_end - c->end_unchanged) |
591 { | |
592 /* Move the gap so that all the boundaries in the unchanged head | |
593 are expressed beg-relative, and all the boundaries in the | |
594 unchanged tail are expressed end-relative. That done, we can | |
595 plug in the new buffer beg and end, and all the positions | |
596 will be accurate. | |
597 | |
598 The boundary which has jurisdiction over the modified region | |
599 should be left before the gap. */ | |
600 move_cache_gap (c, | |
601 (find_cache_boundary (c, (c->buffer_beg | |
602 + c->beg_unchanged)) | |
603 + 1), | |
604 0); | |
605 | |
606 c->buffer_beg = BUF_BEG (buf); | |
607 c->buffer_end = BUF_Z (buf); | |
608 | |
609 /* Now that the cache's basis has been changed, the modified | |
610 region actually takes up some space in the cache, so we can | |
611 invalidate it. */ | |
612 set_cache_region (c, | |
613 c->buffer_beg + c->beg_unchanged, | |
614 c->buffer_end - c->end_unchanged, | |
615 0); | |
616 } | |
617 | |
618 /* Otherwise, there is a non-empty region in the cache which | |
619 corresponds to the modified region of the buffer. */ | |
620 else | |
621 { | |
622 int modified_ix; | |
623 | |
624 /* These positions are correct, relative to both the cache basis | |
625 and the buffer basis. */ | |
626 set_cache_region (c, | |
627 c->buffer_beg + c->beg_unchanged, | |
628 c->buffer_end - c->end_unchanged, | |
629 0); | |
630 | |
631 /* Now the cache contains only boundaries that are in the | |
632 unchanged head and tail; we've disposed of any boundaries | |
633 whose positions we can't be sure of given the information | |
634 we've saved. | |
635 | |
636 If we put the cache gap between the unchanged head and the | |
637 unchanged tail, we can adjust all the boundary positions at | |
638 once, simply by setting buffer_beg and buffer_end. | |
639 | |
640 The boundary which has jurisdiction over the modified region | |
641 should be left before the gap. */ | |
642 modified_ix = | |
643 find_cache_boundary (c, (c->buffer_beg + c->beg_unchanged)) + 1; | |
644 move_cache_gap (c, modified_ix, 0); | |
645 | |
646 c->buffer_beg = BUF_BEG (buf); | |
647 c->buffer_end = BUF_Z (buf); | |
648 | |
649 /* Now, we may have shrunk the buffer when we changed the basis, | |
650 and brought the boundaries we created for the start and end | |
651 of the modified region together, giving them the same | |
652 position. If that's the case, we should collapse them into | |
653 one boundary. Or we may even delete them both, if the values | |
654 before and after them are the same. */ | |
655 if (modified_ix < c->cache_len | |
656 && (BOUNDARY_POS (c, modified_ix - 1) | |
657 == BOUNDARY_POS (c, modified_ix))) | |
658 { | |
659 int value_after = BOUNDARY_VALUE (c, modified_ix); | |
660 | |
661 /* Should we remove both of the boundaries? Yes, if the | |
662 latter boundary is now establishing the same value that | |
663 the former boundary's predecessor does. */ | |
664 if (modified_ix - 1 > 0 | |
665 && value_after == BOUNDARY_VALUE (c, modified_ix - 2)) | |
666 delete_cache_boundaries (c, modified_ix - 1, modified_ix + 1); | |
667 else | |
668 { | |
669 /* We do need a boundary here; collapse the two | |
670 boundaries into one. */ | |
671 SET_BOUNDARY_VALUE (c, modified_ix - 1, value_after); | |
672 delete_cache_boundaries (c, modified_ix, modified_ix + 1); | |
673 } | |
674 } | |
675 } | |
676 | |
677 /* Now the entire cache is valid. */ | |
678 c->beg_unchanged | |
679 = c->end_unchanged | |
680 = c->buffer_end - c->buffer_beg; | |
681 } | |
682 | |
683 | |
684 /* Interface: Adding information to the cache. */ | |
685 | |
686 /* Assert that the region of BUF between START and END (absolute | |
687 buffer positions) is "known," for the purposes of CACHE (e.g. "has | |
688 no newlines", in the case of the line cache). */ | |
689 void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
690 know_region_cache (struct buffer *buf, struct region_cache *c, int start, int end) |
11047 | 691 { |
692 revalidate_region_cache (buf, c); | |
693 | |
694 set_cache_region (c, start, end, 1); | |
695 } | |
696 | |
697 | |
698 /* Interface: using the cache. */ | |
699 | |
700 /* Return true if the text immediately after POS in BUF is known, for | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
701 the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest |
11047 | 702 position after POS where the knownness changes. */ |
703 int | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
704 region_cache_forward (struct buffer *buf, struct region_cache *c, int pos, int *next) |
11047 | 705 { |
706 revalidate_region_cache (buf, c); | |
707 | |
708 { | |
709 int i = find_cache_boundary (c, pos); | |
710 int i_value = BOUNDARY_VALUE (c, i); | |
711 int j; | |
712 | |
713 /* Beyond the end of the buffer is unknown, by definition. */ | |
714 if (pos >= BUF_Z (buf)) | |
715 { | |
716 if (next) *next = BUF_Z (buf); | |
717 i_value = 0; | |
718 } | |
719 else if (next) | |
720 { | |
721 /* Scan forward from i to find the next differing position. */ | |
722 for (j = i + 1; j < c->cache_len; j++) | |
723 if (BOUNDARY_VALUE (c, j) != i_value) | |
724 break; | |
725 | |
726 if (j < c->cache_len) | |
727 *next = BOUNDARY_POS (c, j); | |
728 else | |
729 *next = BUF_Z (buf); | |
730 } | |
731 | |
732 return i_value; | |
733 } | |
734 } | |
735 | |
736 /* Return true if the text immediately before POS in BUF is known, for | |
737 the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest | |
738 position before POS where the knownness changes. */ | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
739 int region_cache_backward (struct buffer *buf, struct region_cache *c, int pos, int *next) |
11047 | 740 { |
741 revalidate_region_cache (buf, c); | |
742 | |
743 /* Before the beginning of the buffer is unknown, by | |
744 definition. */ | |
745 if (pos <= BUF_BEG (buf)) | |
746 { | |
747 if (next) *next = BUF_BEG (buf); | |
748 return 0; | |
749 } | |
750 | |
751 { | |
752 int i = find_cache_boundary (c, pos - 1); | |
753 int i_value = BOUNDARY_VALUE (c, i); | |
754 int j; | |
755 | |
756 if (next) | |
757 { | |
758 /* Scan backward from i to find the next differing position. */ | |
759 for (j = i - 1; j >= 0; j--) | |
760 if (BOUNDARY_VALUE (c, j) != i_value) | |
761 break; | |
762 | |
763 if (j >= 0) | |
764 *next = BOUNDARY_POS (c, j + 1); | |
765 else | |
766 *next = BUF_BEG (buf); | |
767 } | |
768 | |
769 return i_value; | |
770 } | |
771 } | |
772 | |
773 | |
774 /* Debugging: pretty-print a cache to the standard error output. */ | |
775 | |
776 void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
777 pp_cache (struct region_cache *c) |
11047 | 778 { |
779 int i; | |
780 int beg_u = c->buffer_beg + c->beg_unchanged; | |
781 int end_u = c->buffer_end - c->end_unchanged; | |
782 | |
783 fprintf (stderr, | |
784 "basis: %d..%d modified: %d..%d\n", | |
785 c->buffer_beg, c->buffer_end, | |
786 beg_u, end_u); | |
787 | |
788 for (i = 0; i < c->cache_len; i++) | |
789 { | |
790 int pos = BOUNDARY_POS (c, i); | |
791 | |
792 putc (((pos < beg_u) ? 'v' | |
793 : (pos == beg_u) ? '-' | |
794 : ' '), | |
795 stderr); | |
796 putc (((pos > end_u) ? '^' | |
797 : (pos == end_u) ? '-' | |
798 : ' '), | |
799 stderr); | |
800 fprintf (stderr, "%d : %d\n", pos, BOUNDARY_VALUE (c, i)); | |
801 } | |
802 } | |
52401 | 803 |
804 /* arch-tag: 98c29f3f-2ca2-4e3a-92f0-f2249200a17d | |
805 (do not change this comment) */ |