annotate src/region-cache.h @ 45126:27e99a48f837

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