/* Caching facts about regions of the buffer, for optimization.
- Copyright (C) 1985, 1986, 1987, 1988, 1989, 1993, 1995, 2001, 2002, 2003,
- 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
+
+Copyright (C) 1985-1989, 1993, 1995, 2001-2016 Free Software Foundation,
+Inc.
This file is part of GNU Emacs.
GNU Emacs is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation, either version 3 of the License, or
-(at your option) any later version.
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
#include <config.h>
#include <stdio.h>
-#include <setjmp.h>
#include "lisp.h"
#include "buffer.h"
revalidate_region_cache to see how this helps. */
struct boundary {
- int pos;
+ ptrdiff_t pos;
int value;
};
struct boundary *boundaries;
/* boundaries[gap_start ... gap_start + gap_len - 1] is the gap. */
- int gap_start, gap_len;
+ ptrdiff_t gap_start, gap_len;
/* The number of elements allocated to boundaries, not including the
gap. */
- int cache_len;
+ ptrdiff_t cache_len;
/* The areas that haven't changed since the last time we cleaned out
invalid entries from the cache. These overlap when the buffer is
entirely unchanged. */
- int beg_unchanged, end_unchanged;
+ ptrdiff_t beg_unchanged, end_unchanged;
/* The first and last positions in the buffer. Because boundaries
store their positions relative to the start (BEG) and end (Z) of
Yes, buffer_beg is always 1. It's there for symmetry with
buffer_end and the BEG and BUF_BEG macros. */
- int buffer_beg, buffer_end;
+ ptrdiff_t buffer_beg, buffer_end;
};
/* Return the position of boundary i in cache c. */
preserve that information, instead of throwing it away. */
#define PRESERVE_THRESHOLD (500)
-static void revalidate_region_cache ();
+static void revalidate_region_cache (struct buffer *buf, struct region_cache *c);
\f
/* Interface: Allocating, initializing, and disposing of region caches. */
struct region_cache *
-new_region_cache ()
+new_region_cache (void)
{
- struct region_cache *c
- = (struct region_cache *) xmalloc (sizeof (struct region_cache));
+ struct region_cache *c = xmalloc (sizeof *c);
c->gap_start = 0;
c->gap_len = NEW_CACHE_GAP;
c->cache_len = 0;
- c->boundaries =
- (struct boundary *) xmalloc ((c->gap_len + c->cache_len)
- * sizeof (*c->boundaries));
+ c->boundaries = xmalloc ((c->gap_len + c->cache_len)
+ * sizeof (*c->boundaries));
c->beg_unchanged = 0;
c->end_unchanged = 0;
}
void
-free_region_cache (c)
- struct region_cache *c;
+free_region_cache (struct region_cache *c)
{
xfree (c->boundaries);
xfree (c);
This operation should be logarithmic in the number of cache
entries. It would be nice if it took advantage of locality of
reference, too, by searching entries near the last entry found. */
-static int
-find_cache_boundary (c, pos)
- struct region_cache *c;
- int pos;
+static ptrdiff_t
+find_cache_boundary (struct region_cache *c, ptrdiff_t pos)
{
- int low = 0, high = c->cache_len;
+ ptrdiff_t low = 0, high = c->cache_len;
while (low + 1 < high)
{
/* mid is always a valid index, because low < high and ">> 1"
rounds down. */
- int mid = (low + high) >> 1;
- int boundary = BOUNDARY_POS (c, mid);
+ ptrdiff_t mid = (low >> 1) + (high >> 1) + (low & high & 1);
+ ptrdiff_t boundary = BOUNDARY_POS (c, mid);
if (pos < boundary)
high = mid;
}
/* Some testing. */
- if (BOUNDARY_POS (c, low) > pos
- || (low + 1 < c->cache_len
- && BOUNDARY_POS (c, low + 1) <= pos))
- abort ();
+ eassert (!(BOUNDARY_POS (c, low) > pos
+ || (low + 1 < c->cache_len
+ && BOUNDARY_POS (c, low + 1) <= pos)));
return low;
}
/* Move the gap of cache C to index POS, and make sure it has space
for at least MIN_SIZE boundaries. */
static void
-move_cache_gap (c, pos, min_size)
- struct region_cache *c;
- int pos;
- int min_size;
+move_cache_gap (struct region_cache *c, ptrdiff_t pos, ptrdiff_t min_size)
{
/* Copy these out of the cache and into registers. */
- int gap_start = c->gap_start;
- int gap_len = c->gap_len;
- int buffer_beg = c->buffer_beg;
- int buffer_end = c->buffer_end;
-
- if (pos < 0
- || pos > c->cache_len)
- abort ();
+ ptrdiff_t gap_start = c->gap_start;
+ ptrdiff_t gap_len = c->gap_len;
+ ptrdiff_t buffer_beg = c->buffer_beg;
+ ptrdiff_t buffer_end = c->buffer_end;
/* We mustn't ever try to put the gap before the dummy start
boundary. That must always be start-relative. */
- if (pos == 0)
- abort ();
+ eassert (0 < pos && pos <= c->cache_len);
/* Need we move the gap right? */
while (gap_start < pos)
when the portion after the gap is smallest. */
if (gap_len < min_size)
{
- int i;
-
- /* Always make at least NEW_CACHE_GAP elements, as long as we're
- expanding anyway. */
- if (min_size < NEW_CACHE_GAP)
- min_size = NEW_CACHE_GAP;
+ ptrdiff_t i, nboundaries = c->cache_len;
c->boundaries =
- (struct boundary *) xrealloc (c->boundaries,
- ((min_size + c->cache_len)
- * sizeof (*c->boundaries)));
+ xpalloc (c->boundaries, &nboundaries, min_size - gap_len, -1,
+ sizeof *c->boundaries);
/* Some systems don't provide a version of the copy routine that
can be trusted to shift memory upward into an overlapping
region. memmove isn't widely available. */
- min_size -= gap_len;
+ min_size = nboundaries - c->cache_len - gap_len;
for (i = c->cache_len - 1; i >= gap_start; i--)
{
c->boundaries[i + min_size].pos = c->boundaries[i + gap_len].pos;
}
-/* Insert a new boundary in cache C; it will have cache index INDEX,
+/* Insert a new boundary in cache C; it will have cache index I,
and have the specified POS and VALUE. */
static void
-insert_cache_boundary (c, index, pos, value)
- struct region_cache *c;
- int index;
- int pos, value;
+insert_cache_boundary (struct region_cache *c, ptrdiff_t i, ptrdiff_t pos,
+ int value)
{
- /* index must be a valid cache index. */
- if (index < 0 || index > c->cache_len)
- abort ();
-
- /* We must never want to insert something before the dummy first
- boundary. */
- if (index == 0)
- abort ();
+ /* I must be a valid cache index, and we must never want
+ to insert something before the dummy first boundary. */
+ eassert (0 < i && i <= c->cache_len);
/* We must only be inserting things in order. */
- if (! (BOUNDARY_POS (c, index-1) < pos
- && (index == c->cache_len
- || pos < BOUNDARY_POS (c, index))))
- abort ();
+ eassert ((BOUNDARY_POS (c, i - 1) < pos
+ && (i == c->cache_len
+ || pos < BOUNDARY_POS (c, i))));
/* The value must be different from the ones around it. However, we
temporarily create boundaries that establish the same value as
the subsequent boundary, so we're not going to flag that case. */
- if (BOUNDARY_VALUE (c, index-1) == value)
- abort ();
+ eassert (BOUNDARY_VALUE (c, i - 1) != value);
- move_cache_gap (c, index, 1);
+ move_cache_gap (c, i, 1);
- c->boundaries[index].pos = pos - c->buffer_beg;
- c->boundaries[index].value = value;
+ c->boundaries[i].pos = pos - c->buffer_beg;
+ c->boundaries[i].value = value;
c->gap_start++;
c->gap_len--;
c->cache_len++;
/* Delete the i'th entry from cache C if START <= i < END. */
static void
-delete_cache_boundaries (c, start, end)
- struct region_cache *c;
- int start, end;
+delete_cache_boundaries (struct region_cache *c,
+ ptrdiff_t start, ptrdiff_t end)
{
- int len = end - start;
+ ptrdiff_t len = end - start;
/* Gotta be in range. */
- if (start < 0
- || end > c->cache_len)
- abort ();
+ eassert (0 <= start && end <= c->cache_len);
/* Gotta be in order. */
- if (start > end)
- abort ();
+ eassert (start <= end);
/* Can't delete the dummy entry. */
- if (start == 0
- && end >= 1)
- abort ();
+ eassert (!(start == 0 && end >= 1));
/* Minimize gap motion. If we're deleting nothing, do nothing. */
if (len == 0)
/* Set the value in cache C for the region START..END to VALUE. */
static void
-set_cache_region (c, start, end, value)
- struct region_cache *c;
- int start, end;
- int value;
+set_cache_region (struct region_cache *c,
+ ptrdiff_t start, ptrdiff_t end, int value)
{
- if (start > end)
- abort ();
- if (start < c->buffer_beg
- || end > c->buffer_end)
- abort ();
+ eassert (start <= end);
+ eassert (c->buffer_beg <= start && end <= c->buffer_end);
/* Eliminate this case; then we can assume that start and end-1 are
both the locations of real characters in the buffer. */
index of the earliest boundary after the last character in
start..end. (This tortured terminology is intended to answer
all the "< or <=?" sort of questions.) */
- int start_ix = find_cache_boundary (c, start);
- int end_ix = find_cache_boundary (c, end - 1) + 1;
+ ptrdiff_t start_ix = find_cache_boundary (c, start);
+ ptrdiff_t end_ix = find_cache_boundary (c, end - 1) + 1;
/* We must remember the value established by the last boundary
before end; if that boundary's domain stretches beyond end,
buffer positions in the presence of insertions and deletions; the
args to pass are the same before and after such an operation.) */
void
-invalidate_region_cache (buf, c, head, tail)
- struct buffer *buf;
- struct region_cache *c;
- int head, tail;
+invalidate_region_cache (struct buffer *buf, struct region_cache *c,
+ ptrdiff_t head, ptrdiff_t tail)
{
/* Let chead = c->beg_unchanged, and
ctail = c->end_unchanged.
the cache, and causes cache gap motion. */
static void
-revalidate_region_cache (buf, c)
- struct buffer *buf;
- struct region_cache *c;
+revalidate_region_cache (struct buffer *buf, struct region_cache *c)
{
/* The boundaries now in the cache are expressed relative to the
buffer_beg and buffer_end values stored in the cache. Now,
corresponds to the modified region of the buffer. */
else
{
- int modified_ix;
+ ptrdiff_t modified_ix;
/* These positions are correct, relative to both the cache basis
and the buffer basis. */
buffer positions) is "known," for the purposes of CACHE (e.g. "has
no newlines", in the case of the line cache). */
void
-know_region_cache (buf, c, start, end)
- struct buffer *buf;
- struct region_cache *c;
- int start, end;
+know_region_cache (struct buffer *buf, struct region_cache *c,
+ ptrdiff_t start, ptrdiff_t end)
{
revalidate_region_cache (buf, c);
\f
/* Interface: using the cache. */
-/* Return true if the text immediately after POS in BUF is known, for
- the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest
- position after POS where the knownness changes. */
+/* 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
+ position after POS where the knowledge changes. */
int
-region_cache_forward (buf, c, pos, next)
- struct buffer *buf;
- struct region_cache *c;
- int pos;
- int *next;
+region_cache_forward (struct buffer *buf, struct region_cache *c,
+ ptrdiff_t pos, ptrdiff_t *next)
{
revalidate_region_cache (buf, c);
{
- int i = find_cache_boundary (c, pos);
+ ptrdiff_t i = find_cache_boundary (c, pos);
int i_value = BOUNDARY_VALUE (c, i);
- int j;
+ ptrdiff_t j;
/* Beyond the end of the buffer is unknown, by definition. */
if (pos >= BUF_Z (buf))
}
}
-/* Return true if the text immediately before POS in BUF is known, for
- the purposes of CACHE. If NEXT is non-zero, set *NEXT to the nearest
- position before POS where the knownness changes. */
-int region_cache_backward (buf, c, pos, next)
- struct buffer *buf;
- struct region_cache *c;
- int pos;
- int *next;
+/* Return the value for the text immediately before 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
+ position before POS where the knowledge changes. */
+int
+region_cache_backward (struct buffer *buf, struct region_cache *c,
+ ptrdiff_t pos, ptrdiff_t *next)
{
revalidate_region_cache (buf, c);
}
{
- int i = find_cache_boundary (c, pos - 1);
+ ptrdiff_t i = find_cache_boundary (c, pos - 1);
int i_value = BOUNDARY_VALUE (c, i);
- int j;
+ ptrdiff_t j;
if (next)
{
}
}
-\f
+#ifdef ENABLE_CHECKING
+
/* Debugging: pretty-print a cache to the standard error output. */
+void pp_cache (struct region_cache *) EXTERNALLY_VISIBLE;
void
-pp_cache (c)
- struct region_cache *c;
+pp_cache (struct region_cache *c)
{
- int i;
- int beg_u = c->buffer_beg + c->beg_unchanged;
- int end_u = c->buffer_end - c->end_unchanged;
+ ptrdiff_t i;
+ ptrdiff_t beg_u = c->buffer_beg + c->beg_unchanged;
+ ptrdiff_t end_u = c->buffer_end - c->end_unchanged;
fprintf (stderr,
- "basis: %d..%d modified: %d..%d\n",
+ "basis: %"pD"d..%"pD"d modified: %"pD"d..%"pD"d\n",
c->buffer_beg, c->buffer_end,
beg_u, end_u);
for (i = 0; i < c->cache_len; i++)
{
- int pos = BOUNDARY_POS (c, i);
+ ptrdiff_t pos = BOUNDARY_POS (c, i);
putc (((pos < beg_u) ? 'v'
: (pos == beg_u) ? '-'
: (pos == end_u) ? '-'
: ' '),
stderr);
- fprintf (stderr, "%d : %d\n", pos, BOUNDARY_VALUE (c, i));
+ fprintf (stderr, "%"pD"d : %d\n", pos, BOUNDARY_VALUE (c, i));
}
}
-/* arch-tag: 98c29f3f-2ca2-4e3a-92f0-f2249200a17d
- (do not change this comment) */
+#endif /* ENABLE_CHECKING */