Commit | Line | Data |
---|---|---|
b9c5136f | 1 | /* Header file: Caching facts about regions of the buffer, for optimization. |
73b0cd50 | 2 | Copyright (C) 1985-1986, 1993, 1995, 2001-2011 Free Software Foundation, Inc. |
b9c5136f KH |
3 | |
4 | This file is part of GNU Emacs. | |
5 | ||
b9b1cc14 | 6 | GNU Emacs is free software: you can redistribute it and/or modify |
b9c5136f | 7 | it under the terms of the GNU General Public License as published by |
b9b1cc14 GM |
8 | the Free Software Foundation, either version 3 of the License, or |
9 | (at your option) any later version. | |
b9c5136f KH |
10 | |
11 | GNU Emacs is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
b9b1cc14 | 17 | along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */ |
b9c5136f KH |
18 | |
19 | ||
20 | /* This code was written by Jim Blandy <jimb@cs.oberlin.edu> to help | |
21 | GNU Emacs better support the gene editor written for the University | |
22 | of Illinois at Urbana-Champagne's Ribosome Database Project (RDP). | |
23 | ||
24 | Emacs implements line operations (finding the beginning/end of the | |
25 | line, vertical motion, all the redisplay stuff) by searching for | |
26 | newlines in the buffer. Usually, this is a good design; it's very | |
27 | clean to just represent the buffer as an unstructured string of | |
28 | characters, and the lines in most files are very short (less than | |
29 | eighty characters), meaning that scanning usually costs about the | |
30 | same as the overhead of maintaining some more complicated data | |
31 | structure. | |
32 | ||
33 | However, some applications, like gene editing, make use of very | |
34 | long lines --- on the order of tens of kilobytes. In such cases, | |
35 | it may well be worthwhile to try to avoid scanning, because the | |
36 | scans have become two orders of magnitude more expensive. It would | |
37 | be nice if this speedup could preserve the simplicity of the | |
38 | existing data structure, and disturb as little of the existing code | |
39 | as possible. | |
40 | ||
41 | So here's the tack. We add some caching to the scan_buffer | |
42 | function, so that when it searches for a newline, it notes that the | |
43 | region between the start and end of the search contained no | |
44 | newlines; then, the next time around, it consults this cache to see | |
45 | if there are regions of text it can skip over completely. The | |
46 | buffer modification primitives invalidate this cache. | |
47 | ||
48 | (Note: Since the redisplay code needs similar information on | |
49 | modified regions of the buffer, we can use the code that helps out | |
50 | redisplay as a guide to where we need to add our own code to | |
51 | invalidate our cache. prepare_to_modify_buffer seems to be the | |
52 | central spot.) | |
53 | ||
54 | Note that the cache code itself never mentions newlines | |
55 | specifically, so if you wanted to cache other properties of regions | |
56 | of the buffer, you could use this code pretty much unchanged. So | |
57 | this cache really holds "known/unknown" information --- "I know | |
58 | this region has property P" vs. "I don't know if this region has | |
59 | property P or not." */ | |
60 | ||
61 | ||
62 | /* Allocate, initialize and return a new, empty region cache. */ | |
383e0970 | 63 | struct region_cache *new_region_cache (void); |
b9c5136f KH |
64 | |
65 | /* Free a region cache. */ | |
383e0970 | 66 | void free_region_cache (struct region_cache *); |
b9c5136f KH |
67 | |
68 | /* Assert that the region of BUF between START and END (absolute | |
69 | buffer positions) is "known," for the purposes of CACHE (e.g. "has | |
70 | no newlines", in the case of the line cache). */ | |
383e0970 J |
71 | extern void know_region_cache (struct buffer *BUF, |
72 | struct region_cache *CACHE, | |
c098fdb8 | 73 | EMACS_INT START, EMACS_INT END); |
b9c5136f KH |
74 | |
75 | /* Indicate that a section of BUF has changed, to invalidate CACHE. | |
76 | HEAD is the number of chars unchanged at the beginning of the buffer. | |
77 | TAIL is the number of chars unchanged at the end of the buffer. | |
78 | NOTE: this is *not* the same as the ending position of modified | |
79 | region. | |
80 | (This way of specifying regions makes more sense than absolute | |
81 | buffer positions in the presence of insertions and deletions; the | |
82 | args to pass are the same before and after such an operation.) */ | |
383e0970 J |
83 | extern void invalidate_region_cache (struct buffer *BUF, |
84 | struct region_cache *CACHE, | |
c098fdb8 | 85 | EMACS_INT HEAD, EMACS_INT TAIL); |
b9c5136f | 86 | |
177c0ea7 | 87 | /* The scanning functions. |
b9c5136f KH |
88 | |
89 | Basically, if you're scanning forward/backward from position POS, | |
90 | and region_cache_forward/backward returns true, you can skip all | |
91 | the text between POS and *NEXT. And if the function returns false, | |
92 | you should examine all the text from POS to *NEXT, and call | |
93 | know_region_cache depending on what you find there; this way, you | |
94 | might be able to avoid scanning it again. */ | |
95 | ||
96 | /* Return true if the text immediately after POS in BUF is known, for | |
177c0ea7 | 97 | the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest |
b9c5136f | 98 | position after POS where the knownness changes. */ |
383e0970 J |
99 | extern int region_cache_forward (struct buffer *BUF, |
100 | struct region_cache *CACHE, | |
c098fdb8 EZ |
101 | EMACS_INT POS, |
102 | EMACS_INT *NEXT); | |
b9c5136f KH |
103 | |
104 | /* Return true if the text immediately before POS in BUF is known, for | |
105 | the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest | |
106 | position before POS where the knownness changes. */ | |
383e0970 J |
107 | extern int region_cache_backward (struct buffer *BUF, |
108 | struct region_cache *CACHE, | |
c098fdb8 EZ |
109 | EMACS_INT POS, |
110 | EMACS_INT *NEXT); | |
ab5796a9 | 111 |