comparison src/intervals.c @ 50471:dc1f6aa29285

Add many calls to CHECK_TOTAL_LENGTH. (set_intervals_multibyte_1): When becoming multibyte, adjust right and left child sizes to a whole set of characters. If an interval gets zero total-length, delete it. If an interval consists of just its children, delete one of them.

50470:c7a0b787faef

  if (BUFFERP (parent))
    {
      new->total_length = (BUF_Z (XBUFFER (parent))
			   - BUF_BEG (XBUFFER (parent)));
      BUF_INTERVALS (XBUFFER (parent)) = new;
      new->position = 1;
    }
  else if (STRINGP (parent))
    {
      new->total_length = SCHARS (parent);
      STRING_SET_INTERVALS (parent, new);
      new->position = 0;
    }

  SET_INTERVAL_OBJECT (new, parent);

  if (! NULL_INTERVAL_P (i))
    SET_INTERVAL_PARENT (i, interval);

  /* A's total length is decreased by the length of B and its left child.  */
  interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);

  /* B must have the same total length of A.  */
  B->total_length = old_total;

  return B;
}

/* Assuming that a right child exists, perform the following operation:

  if (! NULL_INTERVAL_P (i))
    SET_INTERVAL_PARENT (i, interval);

  /* A's total length is decreased by the length of B and its right child.  */
  interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);

  /* B must have the same total length of A.  */
  B->total_length = old_total;

  return B;
}

/* Balance an interval tree with the assumption that the subtrees

  while (1)
    {
      old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
      if (old_diff > 0)
	{
	  new_diff = i->total_length - i->left->total_length
	    + RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
	  if (abs (new_diff) >= old_diff)
	    break;
	  i = rotate_right (i);
	  balance_an_interval (i->right);
	}
      else if (old_diff < 0)
	{
	  new_diff = i->total_length - i->right->total_length
	    + LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
	  if (abs (new_diff) >= -old_diff)
	    break;
	  i = rotate_left (i);

  if (NULL_RIGHT_CHILD (interval))
    {
      interval->right = new;
      new->total_length = new_length;
    }
  else
    {
      /* Insert the new node between INTERVAL and its right child.  */
      new->right = interval->right;
      SET_INTERVAL_PARENT (interval->right, new);
      interval->right = new;
      new->total_length = new_length + new->right->total_length;
      balance_an_interval (new);
    }

  balance_possible_root_interval (interval);

  if (NULL_LEFT_CHILD (interval))
    {
      interval->left = new;
      new->total_length = new_length;
    }
  else
    {
      /* Insert the new node between INTERVAL and its left child.  */
      new->left = interval->left;
      SET_INTERVAL_PARENT (new->left, new);
      interval->left = new;
      new->total_length = new_length + new->left->total_length;
      balance_an_interval (new);
    }

  balance_possible_root_interval (interval);

  while (1)
    {
      if (relative_position <= LEFT_TOTAL_LENGTH (this))
	{
	  this->total_length += length;
	  this = this->left;
	}
      else if (relative_position > (TOTAL_LENGTH (this)
				    - RIGHT_TOTAL_LENGTH (this)))
	{
	  relative_position -= (TOTAL_LENGTH (this)
				- RIGHT_TOTAL_LENGTH (this));
	  this->total_length += length;
	  this = this->right;
	}
      else
	{
	  /* If we are to use zero-length intervals as buffer pointers,
	     then this code will have to change.  */
	  this->total_length += length;
	  this->position = LEFT_TOTAL_LENGTH (this)
	                   + position - relative_position + 1;
	  return tree;
	}
    }

	 to the left one if it exists.  We extend it now and split
	 off a part later, if stickiness demands it.  */
      for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
	{
	  temp->total_length += length;
	  temp = balance_possible_root_interval (temp);
	}

      /* If at least one interval has sticky properties,
	 we check the stickiness property by property.

  else
    {
      for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
	{
	  temp->total_length += length;
	  temp = balance_possible_root_interval (temp);
	}
    }

  return tree;

  while (! NULL_INTERVAL_P (this->left))
    {
      this = this->left;
      this->total_length += migrate_amt;
    }
  this->left = migrate;
  SET_INTERVAL_PARENT (migrate, this);

  return i->right;
}

    {
      int subtract = interval_deletion_adjustment (tree->left,
						   relative_position,
						   amount);
      tree->total_length -= subtract;
      return subtract;
    }
  /* Right branch */
  else if (relative_position >= (TOTAL_LENGTH (tree)
				 - RIGHT_TOTAL_LENGTH (tree)))

			    - RIGHT_TOTAL_LENGTH (tree));
      subtract = interval_deletion_adjustment (tree->right,
					       relative_position,
					       amount);
      tree->total_length -= subtract;
      return subtract;
    }
  /* Here -- this node.  */
  else
    {

      if (amount > my_amount)
	amount = my_amount;

      tree->total_length -= amount;
      if (LENGTH (tree) == 0)
	delete_interval (tree);

      return amount;
    }

    }

  if (ONLY_INTERVAL_P (tree))
    {
      tree->total_length -= length;
      return;
    }

  if (start > offset + TOTAL_LENGTH (tree))
    start = offset + TOTAL_LENGTH (tree);

  register int absorb = LENGTH (i);
  register INTERVAL successor;

  /* Zero out this interval.  */
  i->total_length -= absorb;

  /* Find the succeeding interval.  */
  if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
				      as we descend.  */
    {
      successor = i->right;
      while (! NULL_LEFT_CHILD (successor))
	{
	  successor->total_length += absorb;
	  successor = successor->left;
	}

      successor->total_length += absorb;
      delete_interval (i);
      return successor;
    }

  successor = i;

	  return successor;
	}

      successor = INTERVAL_PARENT (successor);
      successor->total_length -= absorb;
    }

  /* This must be the rightmost or last interval and cannot
     be merged right.  The caller should have known.  */
  abort ();

  register int absorb = LENGTH (i);
  register INTERVAL predecessor;

  /* Zero out this interval.  */
  i->total_length -= absorb;

  /* Find the preceding interval.  */
  if (! NULL_LEFT_CHILD (i))	/* It's below us. Go down,
				   adding ABSORB as we go.  */
    {
      predecessor = i->left;
      while (! NULL_RIGHT_CHILD (predecessor))
	{
	  predecessor->total_length += absorb;
	  predecessor = predecessor->right;
	}

      predecessor->total_length += absorb;
      delete_interval (i);
      return predecessor;
    }

  predecessor = i;

	  return predecessor;
	}

      predecessor = INTERVAL_PARENT (predecessor);
      predecessor->total_length -= absorb;
    }

  /* This must be the leftmost or first interval and cannot
     be merged left.  The caller should have known.  */
  abort ();

  new = make_interval ();
  new->position = 0;
  got = (LENGTH (i) - (start - i->position));
  new->total_length = length;
  copy_properties (i, new);

  t = new;
  prevlen = got;
  while (got < length)

  /* Fix the length of this interval.  */
  if (multi_flag)
    i->total_length = end - start;
  else
    i->total_length = end_byte - start_byte;

  /* Recursively fix the length of the subintervals.  */
  if (i->left)
    {
      int left_end, left_end_byte;

      if (multi_flag)
	{
	  left_end_byte = start_byte + LEFT_TOTAL_LENGTH (i);
	  left_end = BYTE_TO_CHAR (left_end_byte);
	}
      else
	{
	  left_end = start + LEFT_TOTAL_LENGTH (i);
	  left_end_byte = CHAR_TO_BYTE (left_end);

    {
      int right_start_byte, right_start;

      if (multi_flag)
	{
	  right_start_byte = end_byte - RIGHT_TOTAL_LENGTH (i);
	  right_start = BYTE_TO_CHAR (right_start_byte);
	}
      else
	{
	  right_start = end - RIGHT_TOTAL_LENGTH (i);
	  right_start_byte = CHAR_TO_BYTE (right_start);

      set_intervals_multibyte_1 (i->right, multi_flag,
				 right_start, right_start_byte,
				 end, end_byte);
    }
}

/* Update the intervals of the current buffer
   to fit the contents as multibyte (if MULTI_FLAG is 1)
   or to fit them as non-multibyte (if MULTI_FLAG is 0).  */

50471:dc1f6aa29285

  if (BUFFERP (parent))
    {
      new->total_length = (BUF_Z (XBUFFER (parent))
			   - BUF_BEG (XBUFFER (parent)));
      CHECK_TOTAL_LENGTH (new);
      BUF_INTERVALS (XBUFFER (parent)) = new;
      new->position = 1;
    }
  else if (STRINGP (parent))
    {
      new->total_length = SCHARS (parent);
      CHECK_TOTAL_LENGTH (new);
      STRING_SET_INTERVALS (parent, new);
      new->position = 0;
    }

  SET_INTERVAL_OBJECT (new, parent);

  if (! NULL_INTERVAL_P (i))
    SET_INTERVAL_PARENT (i, interval);

  /* A's total length is decreased by the length of B and its left child.  */
  interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
  CHECK_TOTAL_LENGTH (interval);

  /* B must have the same total length of A.  */
  B->total_length = old_total;
  CHECK_TOTAL_LENGTH (B);

  return B;
}

/* Assuming that a right child exists, perform the following operation:

  if (! NULL_INTERVAL_P (i))
    SET_INTERVAL_PARENT (i, interval);

  /* A's total length is decreased by the length of B and its right child.  */
  interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
  CHECK_TOTAL_LENGTH (interval);

  /* B must have the same total length of A.  */
  B->total_length = old_total;
  CHECK_TOTAL_LENGTH (B);

  return B;
}

/* Balance an interval tree with the assumption that the subtrees

  while (1)
    {
      old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
      if (old_diff > 0)
	{
	  /* Since the left child is longer, there must be one.  */
	  new_diff = i->total_length - i->left->total_length
	    + RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
	  if (abs (new_diff) >= old_diff)
	    break;
	  i = rotate_right (i);
	  balance_an_interval (i->right);
	}
      else if (old_diff < 0)
	{
	  /* Since the right child is longer, there must be one.  */
	  new_diff = i->total_length - i->right->total_length
	    + LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
	  if (abs (new_diff) >= -old_diff)
	    break;
	  i = rotate_left (i);

  if (NULL_RIGHT_CHILD (interval))
    {
      interval->right = new;
      new->total_length = new_length;
      CHECK_TOTAL_LENGTH (new);
    }
  else
    {
      /* Insert the new node between INTERVAL and its right child.  */
      new->right = interval->right;
      SET_INTERVAL_PARENT (interval->right, new);
      interval->right = new;
      new->total_length = new_length + new->right->total_length;
      CHECK_TOTAL_LENGTH (new);
      balance_an_interval (new);
    }

  balance_possible_root_interval (interval);

  if (NULL_LEFT_CHILD (interval))
    {
      interval->left = new;
      new->total_length = new_length;
      CHECK_TOTAL_LENGTH (new);
    }
  else
    {
      /* Insert the new node between INTERVAL and its left child.  */
      new->left = interval->left;
      SET_INTERVAL_PARENT (new->left, new);
      interval->left = new;
      new->total_length = new_length + new->left->total_length;
      CHECK_TOTAL_LENGTH (new);
      balance_an_interval (new);
    }

  balance_possible_root_interval (interval);

  while (1)
    {
      if (relative_position <= LEFT_TOTAL_LENGTH (this))
	{
	  this->total_length += length;
	  CHECK_TOTAL_LENGTH (this);
	  this = this->left;
	}
      else if (relative_position > (TOTAL_LENGTH (this)
				    - RIGHT_TOTAL_LENGTH (this)))
	{
	  relative_position -= (TOTAL_LENGTH (this)
				- RIGHT_TOTAL_LENGTH (this));
	  this->total_length += length;
	  CHECK_TOTAL_LENGTH (this);
	  this = this->right;
	}
      else
	{
	  /* If we are to use zero-length intervals as buffer pointers,
	     then this code will have to change.  */
	  this->total_length += length;
	  CHECK_TOTAL_LENGTH (this);
	  this->position = LEFT_TOTAL_LENGTH (this)
	                   + position - relative_position + 1;
	  return tree;
	}
    }

	 to the left one if it exists.  We extend it now and split
	 off a part later, if stickiness demands it.  */
      for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
	{
	  temp->total_length += length;
	  CHECK_TOTAL_LENGTH (temp);
	  temp = balance_possible_root_interval (temp);
	}

      /* If at least one interval has sticky properties,
	 we check the stickiness property by property.

  else
    {
      for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
	{
	  temp->total_length += length;
	  CHECK_TOTAL_LENGTH (temp);
	  temp = balance_possible_root_interval (temp);
	}
    }

  return tree;

  while (! NULL_INTERVAL_P (this->left))
    {
      this = this->left;
      this->total_length += migrate_amt;
    }
  CHECK_TOTAL_LENGTH (this);
  this->left = migrate;
  SET_INTERVAL_PARENT (migrate, this);

  return i->right;
}

    {
      int subtract = interval_deletion_adjustment (tree->left,
						   relative_position,
						   amount);
      tree->total_length -= subtract;
      CHECK_TOTAL_LENGTH (tree);
      return subtract;
    }
  /* Right branch */
  else if (relative_position >= (TOTAL_LENGTH (tree)
				 - RIGHT_TOTAL_LENGTH (tree)))

			    - RIGHT_TOTAL_LENGTH (tree));
      subtract = interval_deletion_adjustment (tree->right,
					       relative_position,
					       amount);
      tree->total_length -= subtract;
      CHECK_TOTAL_LENGTH (tree);
      return subtract;
    }
  /* Here -- this node.  */
  else
    {

      if (amount > my_amount)
	amount = my_amount;

      tree->total_length -= amount;
      CHECK_TOTAL_LENGTH (tree);
      if (LENGTH (tree) == 0)
	delete_interval (tree);

      return amount;
    }

    }

  if (ONLY_INTERVAL_P (tree))
    {
      tree->total_length -= length;
      CHECK_TOTAL_LENGTH (tree);
      return;
    }

  if (start > offset + TOTAL_LENGTH (tree))
    start = offset + TOTAL_LENGTH (tree);

  register int absorb = LENGTH (i);
  register INTERVAL successor;

  /* Zero out this interval.  */
  i->total_length -= absorb;
  CHECK_TOTAL_LENGTH (i);

  /* Find the succeeding interval.  */
  if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
				      as we descend.  */
    {
      successor = i->right;
      while (! NULL_LEFT_CHILD (successor))
	{
	  successor->total_length += absorb;
	  CHECK_TOTAL_LENGTH (successor);
	  successor = successor->left;
	}

      successor->total_length += absorb;
      CHECK_TOTAL_LENGTH (successor);
      delete_interval (i);
      return successor;
    }

  successor = i;

	  return successor;
	}

      successor = INTERVAL_PARENT (successor);
      successor->total_length -= absorb;
      CHECK_TOTAL_LENGTH (successor);
    }

  /* This must be the rightmost or last interval and cannot
     be merged right.  The caller should have known.  */
  abort ();

  register int absorb = LENGTH (i);
  register INTERVAL predecessor;

  /* Zero out this interval.  */
  i->total_length -= absorb;
  CHECK_TOTAL_LENGTH (i);

  /* Find the preceding interval.  */
  if (! NULL_LEFT_CHILD (i))	/* It's below us. Go down,
				   adding ABSORB as we go.  */
    {
      predecessor = i->left;
      while (! NULL_RIGHT_CHILD (predecessor))
	{
	  predecessor->total_length += absorb;
	  CHECK_TOTAL_LENGTH (predecessor);
	  predecessor = predecessor->right;
	}

      predecessor->total_length += absorb;
      CHECK_TOTAL_LENGTH (predecessor);
      delete_interval (i);
      return predecessor;
    }

  predecessor = i;

	  return predecessor;
	}

      predecessor = INTERVAL_PARENT (predecessor);
      predecessor->total_length -= absorb;
      CHECK_TOTAL_LENGTH (predecessor);
    }

  /* This must be the leftmost or first interval and cannot
     be merged left.  The caller should have known.  */
  abort ();

  new = make_interval ();
  new->position = 0;
  got = (LENGTH (i) - (start - i->position));
  new->total_length = length;
  CHECK_TOTAL_LENGTH (new);
  copy_properties (i, new);

  t = new;
  prevlen = got;
  while (got < length)

  /* Fix the length of this interval.  */
  if (multi_flag)
    i->total_length = end - start;
  else
    i->total_length = end_byte - start_byte;
  CHECK_TOTAL_LENGTH (i);

  if (TOTAL_LENGTH (i) == 0)
    {
      delete_interval (i);
      return;
    }

  /* Recursively fix the length of the subintervals.  */
  if (i->left)
    {
      int left_end, left_end_byte;

      if (multi_flag)
	{
	  int temp;
	  left_end_byte = start_byte + LEFT_TOTAL_LENGTH (i);
	  left_end = BYTE_TO_CHAR (left_end_byte);

	  temp = CHAR_TO_BYTE (left_end);

	  /* If LEFT_END_BYTE is in the middle of a character,
	     adjust it and LEFT_END to a char boundary.  */ 
	  if (left_end_byte > temp)
	    {
	      left_end_byte = temp;
	    }
	  if (left_end_byte < temp)
	    {
	      left_end--;
	      left_end_byte = CHAR_TO_BYTE (left_end);
	    }
	}
      else
	{
	  left_end = start + LEFT_TOTAL_LENGTH (i);
	  left_end_byte = CHAR_TO_BYTE (left_end);

    {
      int right_start_byte, right_start;

      if (multi_flag)
	{
	  int temp;

	  right_start_byte = end_byte - RIGHT_TOTAL_LENGTH (i);
	  right_start = BYTE_TO_CHAR (right_start_byte);

	  /* If RIGHT_START_BYTE is in the middle of a character,
	     adjust it and RIGHT_START to a char boundary.  */ 
	  temp = CHAR_TO_BYTE (right_start);

	  if (right_start_byte < temp)
	    {
	      right_start_byte = temp;
	    }
	  if (right_start_byte > temp)
	    {
	      right_start++;
	      right_start_byte = CHAR_TO_BYTE (right_start);
	    }
	}
      else
	{
	  right_start = end - RIGHT_TOTAL_LENGTH (i);
	  right_start_byte = CHAR_TO_BYTE (right_start);

      set_intervals_multibyte_1 (i->right, multi_flag,
				 right_start, right_start_byte,
				 end, end_byte);
    }

  /* Rounding to char boundaries can theoretically ake this interval
     spurious.  If so, delete one child, and copy its property list
     to this interval.  */
  if (LEFT_TOTAL_LENGTH (i) + RIGHT_TOTAL_LENGTH (i) >= TOTAL_LENGTH (i))
    {
      if ((i)->left)
	{
	  (i)->plist = (i)->left->plist;
	  (i)->left->total_length = 0;
	  delete_interval ((i)->left);
	}
      else
	{
	  (i)->plist = (i)->right->plist;
	  (i)->right->total_length = 0;
	  delete_interval ((i)->right);
	}
    }
}

/* Update the intervals of the current buffer
   to fit the contents as multibyte (if MULTI_FLAG is 1)
   or to fit them as non-multibyte (if MULTI_FLAG is 0).  */