annotate src/region-cache.h @ 72519:3a91203cdb2a

(Incremental Search): Move index entries.
author Richard M. Stallman <rms@gnu.org>
date Fri, 25 Aug 2006 20:33:24 +0000
parents 3bd95f4f2941
children e90d04cd455a c5406394f567
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 /* Header file: Caching facts about regions of the buffer, for optimization.
64770
a0d1312ede66 Update years in copyright notice; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 64084
diff changeset
2 Copyright (C) 1985, 1986, 1993, 1995, 2002, 2003, 2004,
68651
3bd95f4f2941 Update years in copyright notice; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 64770
diff changeset
3 2005, 2006 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
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
7 GNU Emacs is free software; you can redistribute it and/or modify
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
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
9 the Free Software Foundation; either version 2, or (at your option)
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
10 any later version.
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
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
18 along with GNU Emacs; see the file COPYING. If not, write to
64084
a8fa7c632ee4 Update FSF's address.
Lute Kamstra <lute@gnu.org>
parents: 52401
diff changeset
19 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
a8fa7c632ee4 Update FSF's address.
Lute Kamstra <lute@gnu.org>
parents: 52401
diff changeset
20 Boston, MA 02110-1301, USA. */
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
21
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
22
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
23 /* This code was written by Jim Blandy <jimb@cs.oberlin.edu> to help
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
24 GNU Emacs better support the gene editor written for the University
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
25 of Illinois at Urbana-Champagne's Ribosome Database Project (RDP).
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
26
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
27 Emacs implements line operations (finding the beginning/end of the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
28 line, vertical motion, all the redisplay stuff) by searching for
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
29 newlines in the buffer. Usually, this is a good design; it's very
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
30 clean to just represent the buffer as an unstructured string of
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
31 characters, and the lines in most files are very short (less than
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
32 eighty characters), meaning that scanning usually costs about the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
33 same as the overhead of maintaining some more complicated data
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
34 structure.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
35
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
36 However, some applications, like gene editing, make use of very
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
37 long lines --- on the order of tens of kilobytes. In such cases,
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
38 it may well be worthwhile to try to avoid scanning, because the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
39 scans have become two orders of magnitude more expensive. It would
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
40 be nice if this speedup could preserve the simplicity of the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
41 existing data structure, and disturb as little of the existing code
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
42 as possible.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
43
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
44 So here's the tack. We add some caching to the scan_buffer
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
45 function, so that when it searches for a newline, it notes that the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
46 region between the start and end of the search contained no
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
47 newlines; then, the next time around, it consults this cache to see
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
48 if there are regions of text it can skip over completely. The
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
49 buffer modification primitives invalidate this cache.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
50
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
51 (Note: Since the redisplay code needs similar information on
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
52 modified regions of the buffer, we can use the code that helps out
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
53 redisplay as a guide to where we need to add our own code to
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
54 invalidate our cache. prepare_to_modify_buffer seems to be the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
55 central spot.)
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
56
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
57 Note that the cache code itself never mentions newlines
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
58 specifically, so if you wanted to cache other properties of regions
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
59 of the buffer, you could use this code pretty much unchanged. So
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
60 this cache really holds "known/unknown" information --- "I know
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
61 this region has property P" vs. "I don't know if this region has
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
62 property P or not." */
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
63
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
64
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
65 /* Allocate, initialize and return a new, empty region cache. */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
66 struct region_cache *new_region_cache P_ ((void));
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
67
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
68 /* Free a region cache. */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
69 void free_region_cache P_ ((struct region_cache *));
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
70
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
71 /* Assert that the region of BUF between START and END (absolute
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
72 buffer positions) is "known," for the purposes of CACHE (e.g. "has
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
73 no newlines", in the case of the line cache). */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
74 extern void know_region_cache P_ ((struct buffer *BUF,
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
75 struct region_cache *CACHE,
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
76 int START, int END));
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
77
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
78 /* Indicate that a section of BUF has changed, to invalidate CACHE.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
79 HEAD is the number of chars unchanged at the beginning of the buffer.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
80 TAIL is the number of chars unchanged at the end of the buffer.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
81 NOTE: this is *not* the same as the ending position of modified
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
82 region.
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
83 (This way of specifying regions makes more sense than absolute
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
84 buffer positions in the presence of insertions and deletions; the
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
85 args to pass are the same before and after such an operation.) */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
86 extern void invalidate_region_cache P_ ((struct buffer *BUF,
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
87 struct region_cache *CACHE,
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
88 int HEAD, int TAIL));
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
89
49600
23a1cea22d13 Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents: 20349
diff changeset
90 /* The scanning functions.
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
91
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
92 Basically, if you're scanning forward/backward from position POS,
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
93 and region_cache_forward/backward returns true, you can skip all
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
94 the text between POS and *NEXT. And if the function returns false,
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
95 you should examine all the text from POS to *NEXT, and call
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
96 know_region_cache depending on what you find there; this way, you
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
97 might be able to avoid scanning it again. */
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
98
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
99 /* Return true if the text immediately after POS in BUF is known, for
49600
23a1cea22d13 Trailing whitespace deleted.
Juanma Barranquero <lekktu@gmail.com>
parents: 20349
diff changeset
100 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
101 position after POS where the knownness changes. */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
102 extern int region_cache_forward P_ ((struct buffer *BUF,
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
103 struct region_cache *CACHE,
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
104 int POS,
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
105 int *NEXT));
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
106
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
107 /* Return true if the text immediately before POS in BUF is known, for
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
108 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
109 position before POS where the knownness changes. */
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
110 extern int region_cache_backward P_ ((struct buffer *BUF,
11047
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
111 struct region_cache *CACHE,
a6e2398557f6 Initial revision
Karl Heuer <kwzh@gnu.org>
parents:
diff changeset
112 int POS,
20349
6ab8801244c2 Add prototypes.
Andreas Schwab <schwab@suse.de>
parents: 14186
diff changeset
113 int *NEXT));
52401
695cf19ef79e Add arch taglines
Miles Bader <miles@gnu.org>
parents: 49600
diff changeset
114
695cf19ef79e Add arch taglines
Miles Bader <miles@gnu.org>
parents: 49600
diff changeset
115 /* arch-tag: 70f79125-ef22-4f58-9aec-a48ca2791435
695cf19ef79e Add arch taglines
Miles Bader <miles@gnu.org>
parents: 49600
diff changeset
116 (do not change this comment) */