region-cache.h 5.15 KB
Newer Older
Karl Heuer's avatar
Karl Heuer committed
1
/* Header file: Caching facts about regions of the buffer, for optimization.
2

Paul Eggert's avatar
Paul Eggert committed
3
Copyright (C) 1985-1986, 1993, 1995, 2001-2015 Free Software Foundation,
4
Inc.
Karl Heuer's avatar
Karl Heuer committed
5 6 7

This file is part of GNU Emacs.

8
GNU Emacs is free software: you can redistribute it and/or modify
Karl Heuer's avatar
Karl Heuer committed
9
it under the terms of the GNU General Public License as published by
10 11
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Karl Heuer's avatar
Karl Heuer committed
12 13 14 15 16 17 18

GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
19
along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
Karl Heuer's avatar
Karl Heuer committed
20

21 22
#ifndef EMACS_REGION_CACHE_H
#define EMACS_REGION_CACHE_H
Karl Heuer's avatar
Karl Heuer committed
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

/* This code was written by Jim Blandy <jimb@cs.oberlin.edu> to help
   GNU Emacs better support the gene editor written for the University
   of Illinois at Urbana-Champagne's Ribosome Database Project (RDP).

   Emacs implements line operations (finding the beginning/end of the
   line, vertical motion, all the redisplay stuff) by searching for
   newlines in the buffer.  Usually, this is a good design; it's very
   clean to just represent the buffer as an unstructured string of
   characters, and the lines in most files are very short (less than
   eighty characters), meaning that scanning usually costs about the
   same as the overhead of maintaining some more complicated data
   structure.

   However, some applications, like gene editing, make use of very
   long lines --- on the order of tens of kilobytes.  In such cases,
   it may well be worthwhile to try to avoid scanning, because the
   scans have become two orders of magnitude more expensive.  It would
   be nice if this speedup could preserve the simplicity of the
   existing data structure, and disturb as little of the existing code
   as possible.

45
   So here's the tack.  We add some caching to the find_newline
Karl Heuer's avatar
Karl Heuer committed
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
   function, so that when it searches for a newline, it notes that the
   region between the start and end of the search contained no
   newlines; then, the next time around, it consults this cache to see
   if there are regions of text it can skip over completely.  The
   buffer modification primitives invalidate this cache.

   (Note: Since the redisplay code needs similar information on
   modified regions of the buffer, we can use the code that helps out
   redisplay as a guide to where we need to add our own code to
   invalidate our cache.  prepare_to_modify_buffer seems to be the
   central spot.)

   Note that the cache code itself never mentions newlines
   specifically, so if you wanted to cache other properties of regions
   of the buffer, you could use this code pretty much unchanged.  So
   this cache really holds "known/unknown" information --- "I know
   this region has property P" vs. "I don't know if this region has
   property P or not."  */

65
struct buffer;
Karl Heuer's avatar
Karl Heuer committed
66 67

/* Allocate, initialize and return a new, empty region cache.  */
Jan D's avatar
Jan D committed
68
struct region_cache *new_region_cache (void);
Karl Heuer's avatar
Karl Heuer committed
69 70

/* Free a region cache.  */
Jan D's avatar
Jan D committed
71
void free_region_cache (struct region_cache *);
Karl Heuer's avatar
Karl Heuer committed
72 73 74 75

/* Assert that the region of BUF between START and END (absolute
   buffer positions) is "known," for the purposes of CACHE (e.g. "has
   no newlines", in the case of the line cache).  */
Jan D's avatar
Jan D committed
76 77
extern void know_region_cache (struct buffer *BUF,
                               struct region_cache *CACHE,
78
                               ptrdiff_t START, ptrdiff_t END);
Karl Heuer's avatar
Karl Heuer committed
79 80 81 82 83 84 85 86 87

/* Indicate that a section of BUF has changed, to invalidate CACHE.
   HEAD is the number of chars unchanged at the beginning of the buffer.
   TAIL is the number of chars unchanged at the end of the buffer.
      NOTE: this is *not* the same as the ending position of modified
      region.
   (This way of specifying regions makes more sense than absolute
   buffer positions in the presence of insertions and deletions; the
   args to pass are the same before and after such an operation.)  */
Jan D's avatar
Jan D committed
88 89
extern void invalidate_region_cache (struct buffer *BUF,
                                     struct region_cache *CACHE,
90
                                     ptrdiff_t HEAD, ptrdiff_t TAIL);
Karl Heuer's avatar
Karl Heuer committed
91

92
/* The scanning functions.
Karl Heuer's avatar
Karl Heuer committed
93 94

   Basically, if you're scanning forward/backward from position POS,
95 96
   and region_cache_forward/backward returns nonzero, you can skip all
   the text between POS and *NEXT.  And if the function returns zero,
Karl Heuer's avatar
Karl Heuer committed
97 98 99 100
   you should examine all the text from POS to *NEXT, and call
   know_region_cache depending on what you find there; this way, you
   might be able to avoid scanning it again.  */

101 102 103
/* Return the value for the text immediately after POS in BUF if the value
   is known, for the purposes of CACHE, and return zero otherwise.
   If NEXT is non-zero, set *NEXT to the nearest
Paul Eggert's avatar
Paul Eggert committed
104
   position after POS where the knowledge changes.  */
105 106 107 108 109 110
extern int region_cache_forward (struct buffer *buf, struct region_cache *c,
				 ptrdiff_t pos, ptrdiff_t *next);

/* Likewise, except before POS rather than after POS.  */
extern int region_cache_backward (struct buffer *buf, struct region_cache *c,
				  ptrdiff_t pos, ptrdiff_t *next);
111 112

#endif /* EMACS_REGION_CACHE_H */