Mercurial > emacs
annotate src/region-cache.c @ 112429:6e50030da731
Some copyright.el updates.
* lisp/emacs-lisp/copyright.el (copyright-find-copyright): New function,
split out from copyright-update-year.
(copyright-update): Don't mess with the GPL version if we don't own the
copyright. Update license regexp, and remove no longer needed
Esperanto stuff.
author | Glenn Morris <rgm@gnu.org> |
---|---|
date | Sat, 22 Jan 2011 14:09:09 -0800 |
parents | ef719132ddfa |
children |
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, |
112218
376148b31b5e
Add 2011 to FSF/AIST copyright years.
Glenn Morris <rgm@gnu.org>
parents:
106815
diff
changeset
|
3 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 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 { | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
65 EMACS_INT pos; |
11047 | 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. */ | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
75 EMACS_INT gap_start, gap_len; |
11047 | 76 |
77 /* The number of elements allocated to boundaries, not including the | |
78 gap. */ | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
79 EMACS_INT cache_len; |
11047 | 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. */ | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
84 EMACS_INT beg_unchanged, end_unchanged; |
11047 | 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. */ | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
94 EMACS_INT buffer_beg, buffer_end; |
11047 | 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. */ | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
175 static EMACS_INT |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
176 find_cache_boundary (struct region_cache *c, EMACS_INT pos) |
11047 | 177 { |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
178 EMACS_INT low = 0, high = c->cache_len; |
11047 | 179 |
180 while (low + 1 < high) | |
181 { | |
182 /* mid is always a valid index, because low < high and ">> 1" | |
183 rounds down. */ | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
184 EMACS_INT mid = (low + high) >> 1; |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
185 EMACS_INT boundary = BOUNDARY_POS (c, mid); |
11047 | 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 | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
210 move_cache_gap (struct region_cache *c, EMACS_INT pos, EMACS_INT min_size) |
11047 | 211 { |
212 /* Copy these out of the cache and into registers. */ | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
213 EMACS_INT gap_start = c->gap_start; |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
214 EMACS_INT gap_len = c->gap_len; |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
215 EMACS_INT buffer_beg = c->buffer_beg; |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
216 EMACS_INT buffer_end = c->buffer_end; |
11047 | 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 { | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
248 EMACS_INT i; |
11047 | 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 | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
295 insert_cache_boundary (struct region_cache *c, EMACS_INT index, EMACS_INT pos, |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
296 int value) |
11047 | 297 { |
298 /* index must be a valid cache index. */ | |
299 if (index < 0 || index > c->cache_len) | |
300 abort (); | |
301 | |
302 /* We must never want to insert something before the dummy first | |
303 boundary. */ | |
304 if (index == 0) | |
305 abort (); | |
306 | |
307 /* We must only be inserting things in order. */ | |
308 if (! (BOUNDARY_POS (c, index-1) < pos | |
309 && (index == c->cache_len | |
310 || pos < BOUNDARY_POS (c, index)))) | |
311 abort (); | |
312 | |
313 /* The value must be different from the ones around it. However, we | |
314 temporarily create boundaries that establish the same value as | |
315 the subsequent boundary, so we're not going to flag that case. */ | |
316 if (BOUNDARY_VALUE (c, index-1) == value) | |
317 abort (); | |
318 | |
319 move_cache_gap (c, index, 1); | |
320 | |
321 c->boundaries[index].pos = pos - c->buffer_beg; | |
322 c->boundaries[index].value = value; | |
323 c->gap_start++; | |
324 c->gap_len--; | |
325 c->cache_len++; | |
326 } | |
327 | |
328 | |
329 /* Delete the i'th entry from cache C if START <= i < END. */ | |
330 | |
331 static void | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
332 delete_cache_boundaries (struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
333 EMACS_INT start, EMACS_INT end) |
11047 | 334 { |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
335 EMACS_INT len = end - start; |
11047 | 336 |
337 /* Gotta be in range. */ | |
338 if (start < 0 | |
339 || end > c->cache_len) | |
340 abort (); | |
341 | |
342 /* Gotta be in order. */ | |
343 if (start > end) | |
344 abort (); | |
345 | |
346 /* Can't delete the dummy entry. */ | |
347 if (start == 0 | |
348 && end >= 1) | |
349 abort (); | |
350 | |
351 /* Minimize gap motion. If we're deleting nothing, do nothing. */ | |
352 if (len == 0) | |
353 ; | |
354 /* If the gap is before the region to delete, delete from the start | |
355 forward. */ | |
356 else if (c->gap_start <= start) | |
357 { | |
358 move_cache_gap (c, start, 0); | |
359 c->gap_len += len; | |
360 } | |
361 /* If the gap is after the region to delete, delete from the end | |
362 backward. */ | |
363 else if (end <= c->gap_start) | |
364 { | |
365 move_cache_gap (c, end, 0); | |
366 c->gap_start -= len; | |
367 c->gap_len += len; | |
368 } | |
369 /* If the gap is in the region to delete, just expand it. */ | |
370 else | |
371 { | |
372 c->gap_start = start; | |
373 c->gap_len += len; | |
374 } | |
375 | |
376 c->cache_len -= len; | |
377 } | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
378 |
11047 | 379 |
380 | |
381 /* Set the value for a region. */ | |
382 | |
383 /* Set the value in cache C for the region START..END to VALUE. */ | |
384 static void | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
385 set_cache_region (struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
386 EMACS_INT start, EMACS_INT end, int value) |
11047 | 387 { |
388 if (start > end) | |
389 abort (); | |
390 if (start < c->buffer_beg | |
391 || end > c->buffer_end) | |
392 abort (); | |
393 | |
394 /* Eliminate this case; then we can assume that start and end-1 are | |
395 both the locations of real characters in the buffer. */ | |
396 if (start == end) | |
397 return; | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
398 |
11047 | 399 { |
400 /* We need to make sure that there are no boundaries in the area | |
401 between start to end; the whole area will have the same value, | |
402 so those boundaries will not be necessary. | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
403 |
11047 | 404 Let start_ix be the cache index of the boundary governing the |
405 first character of start..end, and let end_ix be the cache | |
406 index of the earliest boundary after the last character in | |
407 start..end. (This tortured terminology is intended to answer | |
408 all the "< or <=?" sort of questions.) */ | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
409 EMACS_INT start_ix = find_cache_boundary (c, start); |
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
410 EMACS_INT end_ix = find_cache_boundary (c, end - 1) + 1; |
11047 | 411 |
412 /* We must remember the value established by the last boundary | |
413 before end; if that boundary's domain stretches beyond end, | |
414 we'll need to create a new boundary at end, and that boundary | |
415 must have that remembered value. */ | |
416 int value_at_end = BOUNDARY_VALUE (c, end_ix - 1); | |
417 | |
418 /* Delete all boundaries strictly within start..end; this means | |
419 those whose indices are between start_ix (exclusive) and end_ix | |
420 (exclusive). */ | |
421 delete_cache_boundaries (c, start_ix + 1, end_ix); | |
422 | |
423 /* Make sure we have the right value established going in to | |
424 start..end from the left, and no unnecessary boundaries. */ | |
425 if (BOUNDARY_POS (c, start_ix) == start) | |
426 { | |
427 /* Is this boundary necessary? If no, remove it; if yes, set | |
428 its value. */ | |
429 if (start_ix > 0 | |
430 && BOUNDARY_VALUE (c, start_ix - 1) == value) | |
431 { | |
432 delete_cache_boundaries (c, start_ix, start_ix + 1); | |
433 start_ix--; | |
434 } | |
435 else | |
436 SET_BOUNDARY_VALUE (c, start_ix, value); | |
437 } | |
438 else | |
439 { | |
440 /* Do we need to add a new boundary here? */ | |
441 if (BOUNDARY_VALUE (c, start_ix) != value) | |
442 { | |
443 insert_cache_boundary (c, start_ix + 1, start, value); | |
444 start_ix++; | |
445 } | |
446 } | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
447 |
11047 | 448 /* This is equivalent to letting end_ix float (like a buffer |
449 marker does) with the insertions and deletions we may have | |
450 done. */ | |
451 end_ix = start_ix + 1; | |
452 | |
453 /* Make sure we have the correct value established as we leave | |
454 start..end to the right. */ | |
455 if (end == c->buffer_end) | |
456 /* There is no text after start..end; nothing to do. */ | |
457 ; | |
458 else if (end_ix >= c->cache_len | |
459 || end < BOUNDARY_POS (c, end_ix)) | |
460 { | |
461 /* There is no boundary at end, but we may need one. */ | |
462 if (value_at_end != value) | |
463 insert_cache_boundary (c, end_ix, end, value_at_end); | |
464 } | |
465 else | |
466 { | |
467 /* There is a boundary at end; should it be there? */ | |
468 if (value == BOUNDARY_VALUE (c, end_ix)) | |
469 delete_cache_boundaries (c, end_ix, end_ix + 1); | |
470 } | |
471 } | |
472 } | |
473 | |
474 | |
475 | |
476 /* Interface: Invalidating the cache. Private: Re-validating the cache. */ | |
477 | |
478 /* Indicate that a section of BUF has changed, to invalidate CACHE. | |
479 HEAD is the number of chars unchanged at the beginning of the buffer. | |
480 TAIL is the number of chars unchanged at the end of the buffer. | |
481 NOTE: this is *not* the same as the ending position of modified | |
482 region. | |
483 (This way of specifying regions makes more sense than absolute | |
484 buffer positions in the presence of insertions and deletions; the | |
485 args to pass are the same before and after such an operation.) */ | |
486 void | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
487 invalidate_region_cache (struct buffer *buf, struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
488 EMACS_INT head, EMACS_INT tail) |
11047 | 489 { |
490 /* Let chead = c->beg_unchanged, and | |
491 ctail = c->end_unchanged. | |
492 If z-tail < beg+chead by a large amount, or | |
493 z-ctail < beg+head by a large amount, | |
494 | |
495 then cutting back chead and ctail to head and tail would lose a | |
496 lot of information that we could preserve by revalidating the | |
497 cache before processing this invalidation. Losing that | |
498 information may be more costly than revalidating the cache now. | |
499 So go ahead and call revalidate_region_cache if it seems that it | |
500 might be worthwhile. */ | |
501 if (((BUF_BEG (buf) + c->beg_unchanged) - (BUF_Z (buf) - tail) | |
502 > PRESERVE_THRESHOLD) | |
503 || ((BUF_BEG (buf) + head) - (BUF_Z (buf) - c->end_unchanged) | |
504 > PRESERVE_THRESHOLD)) | |
505 revalidate_region_cache (buf, c); | |
506 | |
507 | |
508 if (head < c->beg_unchanged) | |
509 c->beg_unchanged = head; | |
510 if (tail < c->end_unchanged) | |
511 c->end_unchanged = tail; | |
512 | |
513 /* We now know nothing about the region between the unchanged head | |
514 and the unchanged tail (call it the "modified region"), not even | |
515 its length. | |
516 | |
517 If the modified region has shrunk in size (deletions do this), | |
518 then the cache may now contain boundaries originally located in | |
519 text that doesn't exist any more. | |
520 | |
521 If the modified region has increased in size (insertions do | |
522 this), then there may now be boundaries in the modified region | |
523 whose positions are wrong. | |
524 | |
525 Even calling BOUNDARY_POS on boundaries still in the unchanged | |
526 head or tail may well give incorrect answers now, since | |
527 c->buffer_beg and c->buffer_end may well be wrong now. (Well, | |
528 okay, c->buffer_beg never changes, so boundaries in the unchanged | |
529 head will still be okay. But it's the principle of the thing.) | |
530 | |
531 So things are generally a mess. | |
532 | |
533 But we don't clean up this mess here; that would be expensive, | |
534 and this function gets called every time any buffer modification | |
535 occurs. Rather, we can clean up everything in one swell foop, | |
536 accounting for all the modifications at once, by calling | |
537 revalidate_region_cache before we try to consult the cache the | |
538 next time. */ | |
539 } | |
540 | |
541 | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
542 /* Clean out any cache entries applying to the modified region, and |
11047 | 543 make the positions of the remaining entries accurate again. |
544 | |
545 After calling this function, the mess described in the comment in | |
546 invalidate_region_cache is cleaned up. | |
547 | |
548 This function operates by simply throwing away everything it knows | |
549 about the modified region. It doesn't care exactly which | |
550 insertions and deletions took place; it just tosses it all. | |
551 | |
552 For example, if you insert a single character at the beginning of | |
553 the buffer, and a single character at the end of the buffer (for | |
554 example), without calling this function in between the two | |
555 insertions, then the entire cache will be freed of useful | |
556 information. On the other hand, if you do manage to call this | |
557 function in between the two insertions, then the modified regions | |
558 will be small in both cases, no information will be tossed, and the | |
559 cache will know that it doesn't have knowledge of the first and | |
560 last characters any more. | |
561 | |
562 Calling this function may be expensive; it does binary searches in | |
563 the cache, and causes cache gap motion. */ | |
564 | |
565 static void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
566 revalidate_region_cache (struct buffer *buf, struct region_cache *c) |
11047 | 567 { |
568 /* The boundaries now in the cache are expressed relative to the | |
569 buffer_beg and buffer_end values stored in the cache. Now, | |
570 buffer_beg and buffer_end may not be the same as BUF_BEG (buf) | |
571 and BUF_Z (buf), so we have two different "bases" to deal with | |
572 --- the cache's, and the buffer's. */ | |
573 | |
574 /* If the entire buffer is still valid, don't waste time. Yes, this | |
575 should be a >, not a >=; think about what beg_unchanged and | |
576 end_unchanged get set to when the only change has been an | |
577 insertion. */ | |
578 if (c->buffer_beg + c->beg_unchanged | |
579 > c->buffer_end - c->end_unchanged) | |
580 return; | |
581 | |
582 /* If all the text we knew about as of the last cache revalidation | |
583 is still there, then all of the information in the cache is still | |
584 valid. Because c->buffer_beg and c->buffer_end are out-of-date, | |
585 the modified region appears from the cache's point of view to be | |
586 a null region located someplace in the buffer. | |
587 | |
588 Now, invalidating that empty string will have no actual affect on | |
589 the cache; instead, we need to update the cache's basis first | |
590 (which will give the modified region the same size in the cache | |
591 as it has in the buffer), and then invalidate the modified | |
592 region. */ | |
49600
23a1cea22d13
Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents:
44621
diff
changeset
|
593 if (c->buffer_beg + c->beg_unchanged |
11047 | 594 == c->buffer_end - c->end_unchanged) |
595 { | |
596 /* Move the gap so that all the boundaries in the unchanged head | |
597 are expressed beg-relative, and all the boundaries in the | |
598 unchanged tail are expressed end-relative. That done, we can | |
599 plug in the new buffer beg and end, and all the positions | |
600 will be accurate. | |
601 | |
602 The boundary which has jurisdiction over the modified region | |
603 should be left before the gap. */ | |
604 move_cache_gap (c, | |
605 (find_cache_boundary (c, (c->buffer_beg | |
606 + c->beg_unchanged)) | |
607 + 1), | |
608 0); | |
609 | |
610 c->buffer_beg = BUF_BEG (buf); | |
611 c->buffer_end = BUF_Z (buf); | |
612 | |
613 /* Now that the cache's basis has been changed, the modified | |
614 region actually takes up some space in the cache, so we can | |
615 invalidate it. */ | |
616 set_cache_region (c, | |
617 c->buffer_beg + c->beg_unchanged, | |
618 c->buffer_end - c->end_unchanged, | |
619 0); | |
620 } | |
621 | |
622 /* Otherwise, there is a non-empty region in the cache which | |
623 corresponds to the modified region of the buffer. */ | |
624 else | |
625 { | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
626 EMACS_INT modified_ix; |
11047 | 627 |
628 /* These positions are correct, relative to both the cache basis | |
629 and the buffer basis. */ | |
630 set_cache_region (c, | |
631 c->buffer_beg + c->beg_unchanged, | |
632 c->buffer_end - c->end_unchanged, | |
633 0); | |
634 | |
635 /* Now the cache contains only boundaries that are in the | |
636 unchanged head and tail; we've disposed of any boundaries | |
637 whose positions we can't be sure of given the information | |
638 we've saved. | |
639 | |
640 If we put the cache gap between the unchanged head and the | |
641 unchanged tail, we can adjust all the boundary positions at | |
642 once, simply by setting buffer_beg and buffer_end. | |
643 | |
644 The boundary which has jurisdiction over the modified region | |
645 should be left before the gap. */ | |
646 modified_ix = | |
647 find_cache_boundary (c, (c->buffer_beg + c->beg_unchanged)) + 1; | |
648 move_cache_gap (c, modified_ix, 0); | |
649 | |
650 c->buffer_beg = BUF_BEG (buf); | |
651 c->buffer_end = BUF_Z (buf); | |
652 | |
653 /* Now, we may have shrunk the buffer when we changed the basis, | |
654 and brought the boundaries we created for the start and end | |
655 of the modified region together, giving them the same | |
656 position. If that's the case, we should collapse them into | |
657 one boundary. Or we may even delete them both, if the values | |
658 before and after them are the same. */ | |
659 if (modified_ix < c->cache_len | |
660 && (BOUNDARY_POS (c, modified_ix - 1) | |
661 == BOUNDARY_POS (c, modified_ix))) | |
662 { | |
663 int value_after = BOUNDARY_VALUE (c, modified_ix); | |
664 | |
665 /* Should we remove both of the boundaries? Yes, if the | |
666 latter boundary is now establishing the same value that | |
667 the former boundary's predecessor does. */ | |
668 if (modified_ix - 1 > 0 | |
669 && value_after == BOUNDARY_VALUE (c, modified_ix - 2)) | |
670 delete_cache_boundaries (c, modified_ix - 1, modified_ix + 1); | |
671 else | |
672 { | |
673 /* We do need a boundary here; collapse the two | |
674 boundaries into one. */ | |
675 SET_BOUNDARY_VALUE (c, modified_ix - 1, value_after); | |
676 delete_cache_boundaries (c, modified_ix, modified_ix + 1); | |
677 } | |
678 } | |
679 } | |
680 | |
681 /* Now the entire cache is valid. */ | |
682 c->beg_unchanged | |
683 = c->end_unchanged | |
684 = c->buffer_end - c->buffer_beg; | |
685 } | |
686 | |
687 | |
688 /* Interface: Adding information to the cache. */ | |
689 | |
690 /* Assert that the region of BUF between START and END (absolute | |
691 buffer positions) is "known," for the purposes of CACHE (e.g. "has | |
692 no newlines", in the case of the line cache). */ | |
693 void | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
694 know_region_cache (struct buffer *buf, struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
695 EMACS_INT start, EMACS_INT end) |
11047 | 696 { |
697 revalidate_region_cache (buf, c); | |
698 | |
699 set_cache_region (c, start, end, 1); | |
700 } | |
701 | |
702 | |
703 /* Interface: using the cache. */ | |
704 | |
705 /* 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
|
706 the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest |
11047 | 707 position after POS where the knownness changes. */ |
708 int | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
709 region_cache_forward (struct buffer *buf, struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
710 EMACS_INT pos, EMACS_INT *next) |
11047 | 711 { |
712 revalidate_region_cache (buf, c); | |
713 | |
714 { | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
715 EMACS_INT i = find_cache_boundary (c, pos); |
11047 | 716 int i_value = BOUNDARY_VALUE (c, i); |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
717 EMACS_INT j; |
11047 | 718 |
719 /* Beyond the end of the buffer is unknown, by definition. */ | |
720 if (pos >= BUF_Z (buf)) | |
721 { | |
722 if (next) *next = BUF_Z (buf); | |
723 i_value = 0; | |
724 } | |
725 else if (next) | |
726 { | |
727 /* Scan forward from i to find the next differing position. */ | |
728 for (j = i + 1; j < c->cache_len; j++) | |
729 if (BOUNDARY_VALUE (c, j) != i_value) | |
730 break; | |
731 | |
732 if (j < c->cache_len) | |
733 *next = BOUNDARY_POS (c, j); | |
734 else | |
735 *next = BUF_Z (buf); | |
736 } | |
737 | |
738 return i_value; | |
739 } | |
740 } | |
741 | |
742 /* Return true if the text immediately before POS in BUF is known, for | |
743 the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest | |
744 position before POS where the knownness changes. */ | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
745 int region_cache_backward (struct buffer *buf, struct region_cache *c, |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
746 EMACS_INT pos, EMACS_INT *next) |
11047 | 747 { |
748 revalidate_region_cache (buf, c); | |
749 | |
750 /* Before the beginning of the buffer is unknown, by | |
751 definition. */ | |
752 if (pos <= BUF_BEG (buf)) | |
753 { | |
754 if (next) *next = BUF_BEG (buf); | |
755 return 0; | |
756 } | |
757 | |
758 { | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
759 EMACS_INT i = find_cache_boundary (c, pos - 1); |
11047 | 760 int i_value = BOUNDARY_VALUE (c, i); |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
761 EMACS_INT j; |
11047 | 762 |
763 if (next) | |
764 { | |
765 /* Scan backward from i to find the next differing position. */ | |
766 for (j = i - 1; j >= 0; j--) | |
767 if (BOUNDARY_VALUE (c, j) != i_value) | |
768 break; | |
769 | |
770 if (j >= 0) | |
771 *next = BOUNDARY_POS (c, j + 1); | |
772 else | |
773 *next = BUF_BEG (buf); | |
774 } | |
775 | |
776 return i_value; | |
777 } | |
778 } | |
779 | |
780 | |
781 /* Debugging: pretty-print a cache to the standard error output. */ | |
782 | |
783 void | |
109126
aec1143e8d85
Convert (most) functions in src to standard C.
Dan Nicolaescu <dann@ics.uci.edu>
parents:
106815
diff
changeset
|
784 pp_cache (struct region_cache *c) |
11047 | 785 { |
786 int i; | |
110507
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
787 EMACS_INT beg_u = c->buffer_beg + c->beg_unchanged; |
875202ac5b45
Fix use of int instead of EMACS_INT in search.c and region-cache.c.
Eli Zaretskii <eliz@gnu.org>
parents:
109126
diff
changeset
|
788 EMACS_INT end_u = c->buffer_end - c->end_unchanged; |
11047 | 789 |
790 fprintf (stderr, | |
110554
e49fcbdc458f
Fix int/EMACS_INT in eval.c and indent.c, correct previous changes.
Eli Zaretskii <eliz@gnu.org>
parents:
110549
diff
changeset
|
791 "basis: %ld..%ld modified: %ld..%ld\n", |
e49fcbdc458f
Fix int/EMACS_INT in eval.c and indent.c, correct previous changes.
Eli Zaretskii <eliz@gnu.org>
parents:
110549
diff
changeset
|
792 (long)c->buffer_beg, (long)c->buffer_end, |
e49fcbdc458f
Fix int/EMACS_INT in eval.c and indent.c, correct previous changes.
Eli Zaretskii <eliz@gnu.org>
parents:
110549
diff
changeset
|
793 (long)beg_u, (long)end_u); |
11047 | 794 |
795 for (i = 0; i < c->cache_len; i++) | |
796 { | |
110549
f3ee3c073b92
Fix EMACS_INT/int conversion in region-cache.c.
Lars Magne Ingebrigtsen <larsi@gnus.org>
parents:
110507
diff
changeset
|
797 EMACS_INT pos = BOUNDARY_POS (c, i); |
11047 | 798 |
799 putc (((pos < beg_u) ? 'v' | |
800 : (pos == beg_u) ? '-' | |
801 : ' '), | |
802 stderr); | |
803 putc (((pos > end_u) ? '^' | |
804 : (pos == end_u) ? '-' | |
805 : ' '), | |
806 stderr); | |
110554
e49fcbdc458f
Fix int/EMACS_INT in eval.c and indent.c, correct previous changes.
Eli Zaretskii <eliz@gnu.org>
parents:
110549
diff
changeset
|
807 fprintf (stderr, "%ld : %d\n", (long)pos, BOUNDARY_VALUE (c, i)); |
11047 | 808 } |
809 } | |
52401 | 810 |