comparison src/region-cache.c @ 110507:875202ac5b45

Fix use of int instead of EMACS_INT in search.c and region-cache.c. indent.c (compute_motion): Use EMACS_INT for arguments to region_cache_forward. region-cache.c (struct boundary, struct region_cache): Use EMACS_INT for positions. (find_cache_boundary, move_cache_gap, insert_cache_boundary) (delete_cache_boundaries, set_cache_region) (invalidate_region_cache, know_region_cache) (region_cache_forward, region_cache_backward, pp_cache): Use EMACS_INT for buffer positions. region-cache.h (know_region_cache, invalidate_region_cache) (region_cache_forward, region_cache_backward): Adjust prototypes. search.c (string_match_1, fast_c_string_match_ignore_case) (looking_at_1, scan_buffer, scan_newline) (find_next_newline_no_quit, find_before_next_newline) (search_command, trivial_regexp_p, search_buffer, simple_search) (boyer_moore, wordify, Freplace_match): Use EMACS_INT for buffer and string positions and length. lisp.h (scan_buffer, scan_newline, find_next_newline_no_quit) (find_before_next_newline): Adjust prototypes.

110506:2cac83f5f8bc

   positions after the gap are stored relative to BUF_Z (buf) (thus
   they're <= 0).  Look at BOUNDARY_POS to see this in action.  See
   revalidate_region_cache to see how this helps.  */

struct boundary {
  int pos;
  int value;
};

struct region_cache {
  /* A sorted array of locations where the known-ness of the buffer
     changes.  */
  struct boundary *boundaries;

  /* boundaries[gap_start ... gap_start + gap_len - 1] is the gap.  */
  int gap_start, gap_len;

  /* The number of elements allocated to boundaries, not including the
     gap.  */
  int 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;

  /* The first and last positions in the buffer.  Because boundaries
     store their positions relative to the start (BEG) and end (Z) of
     the buffer, knowing these positions allows us to accurately
     interpret positions without having to pass the buffer structure
     or its endpoints around all the time.

     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;
};

/* Return the position of boundary i in cache c.  */
#define BOUNDARY_POS(c, i) \
  ((i) < (c)->gap_start \

   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 (struct region_cache *c, int pos)
{
  int 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);

      if (pos < boundary)
        high = mid;
      else
        low = mid;

/* 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 (struct region_cache *c, int pos, int 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 ();

     is proportional to the amount of stuff after the gap, we do the
     enlargement here, after a right shift but before a left shift,
     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;

/* Insert a new boundary in cache C; it will have cache index INDEX,
   and have the specified POS and VALUE.  */
static void
insert_cache_boundary (struct region_cache *c, int index, int pos, int value)
{
  /* index must be a valid cache index.  */
  if (index < 0 || index > c->cache_len)
    abort ();

/* Delete the i'th entry from cache C if START <= i < END.  */

static void
delete_cache_boundaries (struct region_cache *c, int start, int end)
{
  int len = end - start;

  /* Gotta be in range.  */
  if (start < 0
      || end > c->cache_len)
    abort ();


/* Set the value for a region.  */

/* Set the value in cache C for the region START..END to VALUE.  */
static void
set_cache_region (struct region_cache *c, int start, int end, int value)
{
  if (start > end)
    abort ();
  if (start < c->buffer_beg
      || end   > c->buffer_end)

      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.)  */
void
invalidate_region_cache (struct buffer *buf, struct region_cache *c, int head, int tail)
{
  /* Let chead = c->beg_unchanged, and
         ctail = c->end_unchanged.
     If z-tail < beg+chead by a large amount, or
        z-ctail < beg+head by a large amount,

/* 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).  */
void
know_region_cache (struct buffer *buf, struct region_cache *c, int start, int end)
{
  revalidate_region_cache (buf, c);

  set_cache_region (c, start, end, 1);
}

/* 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.  */
int
region_cache_forward (struct buffer *buf, struct region_cache *c, int pos, int *next)
{
  revalidate_region_cache (buf, c);

  {
    int i = find_cache_boundary (c, pos);

}

/* 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 (struct buffer *buf, struct region_cache *c, int pos, int *next)
{
  revalidate_region_cache (buf, c);

  /* Before the beginning of the buffer is unknown, by
     definition. */

void
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;

  fprintf (stderr,
           "basis: %d..%d    modified: %d..%d\n",
           c->buffer_beg, c->buffer_end,
           beg_u, end_u);

110507:875202ac5b45

   positions after the gap are stored relative to BUF_Z (buf) (thus
   they're <= 0).  Look at BOUNDARY_POS to see this in action.  See
   revalidate_region_cache to see how this helps.  */

struct boundary {
  EMACS_INT pos;
  int value;
};

struct region_cache {
  /* A sorted array of locations where the known-ness of the buffer
     changes.  */
  struct boundary *boundaries;

  /* boundaries[gap_start ... gap_start + gap_len - 1] is the gap.  */
  EMACS_INT gap_start, gap_len;

  /* The number of elements allocated to boundaries, not including the
     gap.  */
  int 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.  */
  EMACS_INT 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
     the buffer, knowing these positions allows us to accurately
     interpret positions without having to pass the buffer structure
     or its endpoints around all the time.

     Yes, buffer_beg is always 1.  It's there for symmetry with
     buffer_end and the BEG and BUF_BEG macros.  */
  EMACS_INT buffer_beg, buffer_end;
};

/* Return the position of boundary i in cache c.  */
#define BOUNDARY_POS(c, i) \
  ((i) < (c)->gap_start \

   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 (struct region_cache *c, EMACS_INT pos)
{
  int 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;
      EMACS_INT boundary = BOUNDARY_POS (c, mid);

      if (pos < boundary)
        high = mid;
      else
        low = mid;

/* 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 (struct region_cache *c, EMACS_INT pos, int min_size)
{
  /* Copy these out of the cache and into registers.  */
  EMACS_INT gap_start = c->gap_start;
  EMACS_INT gap_len = c->gap_len;
  EMACS_INT buffer_beg = c->buffer_beg;
  EMACS_INT buffer_end = c->buffer_end;

  if (pos < 0
      || pos > c->cache_len)
    abort ();

     is proportional to the amount of stuff after the gap, we do the
     enlargement here, after a right shift but before a left shift,
     when the portion after the gap is smallest.  */
  if (gap_len < min_size)
    {
      EMACS_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;

/* Insert a new boundary in cache C; it will have cache index INDEX,
   and have the specified POS and VALUE.  */
static void
insert_cache_boundary (struct region_cache *c, int index, EMACS_INT pos,
		       int value)
{
  /* index must be a valid cache index.  */
  if (index < 0 || index > c->cache_len)
    abort ();

/* Delete the i'th entry from cache C if START <= i < END.  */

static void
delete_cache_boundaries (struct region_cache *c,
			 EMACS_INT start, EMACS_INT end)
{
  EMACS_INT len = end - start;

  /* Gotta be in range.  */
  if (start < 0
      || end > c->cache_len)
    abort ();


/* Set the value for a region.  */

/* Set the value in cache C for the region START..END to VALUE.  */
static void
set_cache_region (struct region_cache *c,
		  EMACS_INT start, EMACS_INT end, int value)
{
  if (start > end)
    abort ();
  if (start < c->buffer_beg
      || end   > c->buffer_end)

      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.)  */
void
invalidate_region_cache (struct buffer *buf, struct region_cache *c,
			 EMACS_INT head, EMACS_INT tail)
{
  /* Let chead = c->beg_unchanged, and
         ctail = c->end_unchanged.
     If z-tail < beg+chead by a large amount, or
        z-ctail < beg+head by a large amount,

/* 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).  */
void
know_region_cache (struct buffer *buf, struct region_cache *c,
		   EMACS_INT start, EMACS_INT end)
{
  revalidate_region_cache (buf, c);

  set_cache_region (c, start, end, 1);
}

/* 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.  */
int
region_cache_forward (struct buffer *buf, struct region_cache *c,
		      EMACS_INT pos, EMACS_INT *next)
{
  revalidate_region_cache (buf, c);

  {
    int i = find_cache_boundary (c, pos);

}

/* 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 (struct buffer *buf, struct region_cache *c,
			   EMACS_INT pos, EMACS_INT *next)
{
  revalidate_region_cache (buf, c);

  /* Before the beginning of the buffer is unknown, by
     definition. */

void
pp_cache (struct region_cache *c)
{
  int i;
  EMACS_INT beg_u = c->buffer_beg + c->beg_unchanged;
  EMACS_INT end_u = c->buffer_end - c->end_unchanged;

  fprintf (stderr,
           "basis: %d..%d    modified: %d..%d\n",
           c->buffer_beg, c->buffer_end,
           beg_u, end_u);