emacs: src/intervals.c comparison

comparison src/intervals.c @ 5415:95882472f2da

(rotate_right, rotate_left): Simplify total_length calculation. Minimize pointer dereferencing. (balance_an_interval): Remove recursive rebalancing. Rebalance precisely when imbalanced. If a rotation is done, rebalance only the node which may have become unbalanced. Iterate until the current node is balanced. (balance_possible_root_interval): New function. (balance_intervals): Move the interation into rebalance_an_interval. (balance_intervals_internal): New subroutine of balance_intervals. (split_interval_right, split_interval_left): Speed up by not checking LEAF_INTERVAL_P. (split_interval_right, split_interval_left, find_interval, adjust_intervals_for_insertion, graft_intervals_into_buffer): Add dynamic rebalancing anywhere a node may become unbalanced. (graft_intervals_into_buffer, copy_intervals): No longer any need to do a full rebalance as the tree stays balanced.

author	Richard M. Stallman <rms@gnu.org>
date	Sun, 02 Jan 1994 19:01:15 +0000
parents	63a865489a1e
children	ceed2e32b303

comparison

equal deleted inserted replaced

-:39f0a30bb163
+:95882472f2da
 rotate_right (interval)
 INTERVAL interval;
 {
 INTERVAL i;
 INTERVAL B = interval->left;
-int len = LENGTH (interval);
+int old_total = interval->total_length;
 /* Deal with any Parent of A;  make it point to B.  */
 if (! ROOT_INTERVAL_P (interval))
 if (AM_LEFT_CHILD (interval))
-interval->parent->left = interval->left;
+interval->parent->left = B;
 else
-interval->parent->right = interval->left;
+interval->parent->right = B;
-interval->left->parent = interval->parent;
+B->parent = interval->parent;
-/* B gets the same length as A, since it get A's position in the tree.  */
+/* Make B the parent of A */
-interval->left->total_length = interval->total_length;
+i = B->right;
+B->right = interval;
-/* B becomes the parent of A.  */
+interval->parent = B;
-i = interval->left->right;
-interval->left->right = interval;
+/* Make A point to c */
-interval->parent = interval->left;
-/* A gets c as left child.  */
 interval->left = i;
 if (! NULL_INTERVAL_P (i))
 i->parent = interval;
-interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
-			    + RIGHT_TOTAL_LENGTH (interval));
+/* A's total length is decreased by the length of B and it's 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:
 A               B
 / \	           / \
 B	   =>     A
 rotate_left (interval)
 INTERVAL interval;
 {
 INTERVAL i;
 INTERVAL B = interval->right;
-int len = LENGTH (interval);
+int old_total = interval->total_length;
-/* Deal with the parent of A.  */
+/* Deal with any parent of A;  make it point to B.  */
 if (! ROOT_INTERVAL_P (interval))
 if (AM_LEFT_CHILD (interval))
-interval->parent->left = interval->right;
+interval->parent->left = B;
 else
-interval->parent->right = interval->right;
+interval->parent->right = B;
-interval->right->parent = interval->parent;
+B->parent = interval->parent;
-/* B must have the same total length of A.  */
-interval->right->total_length = interval->total_length;
 /* Make B the parent of A */
-i = interval->right->left;
+i = B->left;
-interval->right->left = interval;
+B->left = interval;
-interval->parent = interval->right;
+interval->parent = B;
 /* Make A point to c */
 interval->right = i;
 if (! NULL_INTERVAL_P (i))
 i->parent = interval;
-interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
-			    + RIGHT_TOTAL_LENGTH (interval));
+/* A's total length is decreased by the length of B and it's 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
+themselves are already balanced.  */
+static INTERVAL
+balance_an_interval (i)
+INTERVAL i;
+{
+register int old_diff, new_diff;
+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);
+	  balance_an_interval (i->left);
+	}
+else
+	break;
+}
+return i;
+}
+/* Balance INTERVAL, potentially stuffing it back into its parent
+Lisp Object.  */
+static INLINE INTERVAL
+balance_possible_root_interval (interval)
+register INTERVAL interval;
+{
+Lisp_Object parent;
+if (interval->parent == NULL_INTERVAL)
+return interval;
+parent = (Lisp_Object) (interval->parent);
+interval = balance_an_interval (interval);
+if (XTYPE (parent) == Lisp_Buffer)
+XBUFFER (parent)->intervals = interval;
+else if (XTYPE (parent) == Lisp_String)
+XSTRING (parent)->intervals = interval;
+return interval;
+}
+/* Balance the interval tree TREE.  Balancing is by weight
+(the amount of text).  */
+static INTERVAL
+balance_intervals_internal (tree)
+register INTERVAL tree;
+{
+/* Balance within each side.  */
+if (tree->left)
+balance_intervals (tree->left);
+if (tree->right)
+balance_intervals (tree->right);
+return balance_an_interval (tree);
+}
+/* Advertised interface to balance intervals.  */
+INTERVAL
+balance_intervals (tree)
+INTERVAL tree;
+{
+if (tree == NULL_INTERVAL)
+return NULL_INTERVAL;
+return balance_intervals_internal (tree);
 }
 /* Split INTERVAL into two pieces, starting the second piece at
 character position OFFSET (counting from 0), relative to INTERVAL.
 INTERVAL becomes the left-hand piece, and the right-hand piece
 int new_length = LENGTH (interval) - offset;
 new->position = position + offset;
 new->parent = interval;
-if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval))
+if (NULL_RIGHT_CHILD (interval))
 {
 interval->right = new;
 new->total_length = new_length;
 return new;
 /* Insert the new node between INTERVAL and its right child.  */
 new->right = interval->right;
 interval->right->parent = new;
 interval->right = new;
 new->total_length = new_length + new->right->total_length;
+balance_an_interval (new);
+balance_possible_root_interval (interval);
 return new;
 }
 /* Split INTERVAL into two pieces, starting the second piece at
 /* Insert the new node between INTERVAL and its left child.  */
 new->left = interval->left;
 new->left->parent = new;
 interval->left = new;
-new->total_length = new_length + LEFT_TOTAL_LENGTH (new);
+new->total_length = new_length + new->left->total_length;
+balance_an_interval (new);
+balance_possible_root_interval (interval);
 return new;
 }
 /* Find the interval containing text position POSITION in the text
 if (NULL_INTERVAL_P (tree))
 return NULL_INTERVAL;
 if (relative_position > TOTAL_LENGTH (tree))
 abort ();			/* Paranoia */
+tree = balance_possible_root_interval (tree);
 while (1)
 {
 if (relative_position < LEFT_TOTAL_LENGTH (tree))
 	{
 	prev = previous_interval (i);
 /* Even if we are positioned between intervals, we default
 	 to the left one if it exists.  We extend it now and split
 	 off a part later, if stickyness demands it.  */
-for (temp = prev ? prev : i; ! NULL_INTERVAL_P (temp); temp = temp->parent)
+for (temp = prev ? prev : i;! NULL_INTERVAL_P (temp); temp = temp->parent)
-	temp->total_length += length;
+	{
+	  temp->total_length += length;
+	  temp = balance_possible_root_interval (temp);
+	}
 /* If at least one interval has sticky properties,
 	 we check the stickyness property by property.  */
 if (END_NONSTICKY_P (prev) || FRONT_STICKY_P (i))
 	{
 /* Otherwise just extend the interval.  */
 else
 {
 for (temp = i; ! NULL_INTERVAL_P (temp); temp = temp->parent)
-	temp->total_length += length;
+	{
+	  temp->total_length += length;
+	  temp = balance_possible_root_interval (temp);
+	}
 }
 return tree;
 }
 	  XSET (buf, Lisp_Buffer, buffer);
 	  Fset_text_properties (make_number (position),
 				make_number (position + length),
 				Qnil, buf);
 	}
+if (! NULL_INTERVAL_P (buffer->intervals))
+	buffer->intervals = balance_an_interval (buffer->intervals);
 return;
 }
 if (NULL_INTERVAL_P (tree))
 {
 else
 	copy_properties (over, this);
 over = next_interval (over);
 }
-buffer->intervals = balance_intervals (buffer->intervals);
+if (! NULL_INTERVAL_P (buffer->intervals))
+buffer->intervals = balance_an_interval (buffer->intervals);
 return;
 }
 /* Get the value of property PROP from PLIST,
 which is the plist of an interval.
 	}
 UNGCPRO;
 }
 }
-/* Balance an interval node if the amount of text in its left and right
-subtrees differs by more than the percentage specified by
-`interval-balance-threshold'.  */
-static INTERVAL
-balance_an_interval (i)
-INTERVAL i;
-{
-register int total_children_size = (LEFT_TOTAL_LENGTH (i)
-				      + RIGHT_TOTAL_LENGTH (i));
-register int threshold = (XFASTINT (interval_balance_threshold)
-			    * (total_children_size / 100));
-/* Balance within each side.  */
-balance_intervals (i->left);
-balance_intervals (i->right);
-if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
-&& (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
-{
-i = rotate_right (i);
-/* If that made it unbalanced the other way, take it back.  */
-if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
-	  && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
-	return rotate_left (i);
-return i;
-}
-if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
-&& (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
-{
-i = rotate_left (i);
-if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
-	  && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
-	return rotate_right (i);
-return i;
-}
-return i;
-}
-/* Balance the interval tree TREE.  Balancing is by weight
-(the amount of text).  */
-INTERVAL
-balance_intervals (tree)
-register INTERVAL tree;
-{
-register INTERVAL new_tree;
-if (NULL_INTERVAL_P (tree))
-return NULL_INTERVAL;
-new_tree = tree;
-do
-{
-tree = new_tree;
-new_tree = balance_an_interval (new_tree);
-}
-while (new_tree != tree);
-return new_tree;
-}
 /* Produce an interval tree reflecting the intervals in
 TREE from START to START + LENGTH.  */
 INTERVAL
 copy_intervals (tree, start, length)
 copy_properties (i, t);
 prevlen = LENGTH (i);
 got += prevlen;
 }
-return balance_intervals (new);
+return balance_an_interval (new);
 }
 /* Give STRING the properties of BUFFER from POSITION to LENGTH.  */
 INLINE void

Mercurial > emacs

comparison src/intervals.c @ 5415:95882472f2da