src/region-cache.h

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