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