1 /* Code for doing intervals.
2 Copyright (C) 1991, 1992 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 1, or (at your option)
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Emacs; see the file COPYING. If not, write to
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
23 Have to ensure that we can't put symbol nil on a plist, or some
24 functions may work incorrectly.
26 An idea: Have the owner of the tree keep count of splits and/or
27 insertion lengths (in intervals), and balance after every N.
29 Need to call *_left_hook when buffer is killed.
31 Scan for zero-length, or 0-length to see notes about handling
32 zero length interval-markers.
34 There are comments around about freeing intervals. It might be
35 faster to explicitly free them (put them on the free list) than
43 #include "intervals.h"
47 /* Factor for weight-balancing interval trees. */
48 Lisp_Object interval_balance_threshold
;
50 /* Utility functions for intervals. */
53 /* Create the root interval of some object, a buffer or string. */
56 create_root_interval (parent
)
59 INTERVAL
new = make_interval ();
61 if (XTYPE (parent
) == Lisp_Buffer
)
63 new->total_length
= BUF_Z (XBUFFER (parent
)) - 1;
64 XBUFFER (parent
)->intervals
= new;
66 else if (XTYPE (parent
) == Lisp_String
)
68 new->total_length
= XSTRING (parent
)->size
;
69 XSTRING (parent
)->intervals
= new;
72 new->parent
= (INTERVAL
) parent
;
78 /* Make the interval TARGET have exactly the properties of SOURCE */
81 copy_properties (source
, target
)
82 register INTERVAL source
, target
;
84 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
87 COPY_INTERVAL_CACHE (source
, target
);
88 target
->plist
= Fcopy_sequence (source
->plist
);
91 /* Merge the properties of interval SOURCE into the properties
92 of interval TARGET. */
95 merge_properties (source
, target
)
96 register INTERVAL source
, target
;
98 register Lisp_Object o
, sym
, val
;
100 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
103 MERGE_INTERVAL_CACHE (source
, target
);
106 while (! EQ (o
, Qnil
))
109 val
= Fmemq (sym
, target
->plist
);
115 target
->plist
= Fcons (sym
, Fcons (val
, target
->plist
));
123 /* Return 1 if the two intervals have the same properties,
127 intervals_equal (i0
, i1
)
130 register Lisp_Object i0_cdr
, i0_sym
, i1_val
;
133 if (DEFAULT_INTERVAL_P (i0
) && DEFAULT_INTERVAL_P (i1
))
136 i1_len
= XFASTINT (Flength (i1
->plist
));
137 if (i1_len
& 0x1) /* Paranoia -- plists are always even */
141 while (!NILP (i0_cdr
))
143 /* Lengths of the two plists were unequal */
147 i0_sym
= Fcar (i0_cdr
);
148 i1_val
= Fmemq (i0_sym
, i1
->plist
);
150 /* i0 has something i1 doesn't */
151 if (EQ (i1_val
, Qnil
))
154 /* i0 and i1 both have sym, but it has different values in each */
155 i0_cdr
= Fcdr (i0_cdr
);
156 if (! Fequal (i1_val
, Fcar (i0_cdr
)))
159 i0_cdr
= Fcdr (i0_cdr
);
163 /* Lengths of the two plists were unequal */
172 static int zero_length
;
176 /* Traverse an interval tree TREE, performing FUNCTION on each node.
178 Perhaps we should pass the depth as an argument. */
181 traverse_intervals (tree
, position
, function
)
184 void (* function
) ();
186 if (NULL_INTERVAL_P (tree
))
190 traverse_intervals (tree
->left
, position
, function
);
191 position
+= LEFT_TOTAL_LENGTH (tree
);
192 tree
->position
= position
;
194 position
+= LENGTH (tree
);
195 traverse_intervals (tree
->right
, position
, function
);
200 /* These functions are temporary, for debugging purposes only. */
202 INTERVAL search_interval
, found_interval
;
205 check_for_interval (i
)
208 if (i
== search_interval
)
216 search_for_interval (i
, tree
)
217 register INTERVAL i
, tree
;
221 found_interval
= NULL_INTERVAL
;
222 traverse_intervals (tree
, 1, &check_for_interval
);
223 return found_interval
;
227 inc_interval_count (i
)
244 traverse_intervals (i
, 1, &inc_interval_count
);
250 root_interval (interval
)
253 register INTERVAL i
= interval
;
255 while (! ROOT_INTERVAL_P (i
))
262 /* Assuming that a left child exists, perform the following operation:
272 rotate_right (interval
)
276 INTERVAL B
= interval
->left
;
277 int len
= LENGTH (interval
);
279 /* Deal with any Parent of A; make it point to B. */
280 if (! ROOT_INTERVAL_P (interval
))
281 if (AM_LEFT_CHILD (interval
))
282 interval
->parent
->left
= interval
->left
;
284 interval
->parent
->right
= interval
->left
;
285 interval
->left
->parent
= interval
->parent
;
287 /* B gets the same length as A, since it get A's position in the tree. */
288 interval
->left
->total_length
= interval
->total_length
;
290 /* B becomes the parent of A. */
291 i
= interval
->left
->right
;
292 interval
->left
->right
= interval
;
293 interval
->parent
= interval
->left
;
295 /* A gets c as left child. */
297 if (! NULL_INTERVAL_P (i
))
298 i
->parent
= interval
;
299 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
300 + RIGHT_TOTAL_LENGTH (interval
));
305 /* Assuming that a right child exists, perform the following operation:
315 rotate_left (interval
)
319 INTERVAL B
= interval
->right
;
320 int len
= LENGTH (interval
);
322 /* Deal with the parent of A. */
323 if (! ROOT_INTERVAL_P (interval
))
324 if (AM_LEFT_CHILD (interval
))
325 interval
->parent
->left
= interval
->right
;
327 interval
->parent
->right
= interval
->right
;
328 interval
->right
->parent
= interval
->parent
;
330 /* B must have the same total length of A. */
331 interval
->right
->total_length
= interval
->total_length
;
333 /* Make B the parent of A */
334 i
= interval
->right
->left
;
335 interval
->right
->left
= interval
;
336 interval
->parent
= interval
->right
;
338 /* Make A point to c */
340 if (! NULL_INTERVAL_P (i
))
341 i
->parent
= interval
;
342 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
343 + RIGHT_TOTAL_LENGTH (interval
));
348 /* Split INTERVAL into two pieces, starting the second piece at character
349 position OFFSET (counting from 1), relative to INTERVAL. The right-hand
350 piece (second, lexicographically) is returned.
352 The size and position fields of the two intervals are set based upon
353 those of the original interval. The property list of the new interval
354 is reset, thus it is up to the caller to do the right thing with the
357 Note that this does not change the position of INTERVAL; if it is a root,
358 it is still a root after this operation. */
361 split_interval_right (interval
, offset
)
365 INTERVAL
new = make_interval ();
366 int position
= interval
->position
;
367 int new_length
= LENGTH (interval
) - offset
+ 1;
369 new->position
= position
+ offset
- 1;
370 new->parent
= interval
;
372 if (LEAF_INTERVAL_P (interval
) || NULL_RIGHT_CHILD (interval
))
374 interval
->right
= new;
375 new->total_length
= new_length
;
380 /* Insert the new node between INTERVAL and its right child. */
381 new->right
= interval
->right
;
382 interval
->right
->parent
= new;
383 interval
->right
= new;
385 new->total_length
= new_length
+ new->right
->total_length
;
390 /* Split INTERVAL into two pieces, starting the second piece at character
391 position OFFSET (counting from 1), relative to INTERVAL. The left-hand
392 piece (first, lexicographically) is returned.
394 The size and position fields of the two intervals are set based upon
395 those of the original interval. The property list of the new interval
396 is reset, thus it is up to the caller to do the right thing with the
399 Note that this does not change the position of INTERVAL; if it is a root,
400 it is still a root after this operation. */
403 split_interval_left (interval
, offset
)
407 INTERVAL
new = make_interval ();
408 int position
= interval
->position
;
409 int new_length
= offset
- 1;
411 new->position
= interval
->position
;
412 interval
->position
= interval
->position
+ offset
- 1;
413 new->parent
= interval
;
415 if (NULL_LEFT_CHILD (interval
))
417 interval
->left
= new;
418 new->total_length
= new_length
;
423 /* Insert the new node between INTERVAL and its left child. */
424 new->left
= interval
->left
;
425 new->left
->parent
= new;
426 interval
->left
= new;
427 new->total_length
= LENGTH (new) + LEFT_TOTAL_LENGTH (new);
432 /* Find the interval containing text position POSITION in the text
433 represented by the interval tree TREE. POSITION is relative to
434 the beginning of that text.
436 The `position' field, which is a cache of an interval's position,
437 is updated in the interval found. Other functions (e.g., next_interval)
438 will update this cache based on the result of find_interval. */
441 find_interval (tree
, position
)
442 register INTERVAL tree
;
443 register int position
;
445 register int relative_position
= position
;
447 if (NULL_INTERVAL_P (tree
))
448 return NULL_INTERVAL
;
450 if (position
> TOTAL_LENGTH (tree
))
451 abort (); /* Paranoia */
453 position
= TOTAL_LENGTH (tree
);
458 if (relative_position
<= LEFT_TOTAL_LENGTH (tree
))
462 else if (relative_position
> (TOTAL_LENGTH (tree
)
463 - RIGHT_TOTAL_LENGTH (tree
)))
465 relative_position
-= (TOTAL_LENGTH (tree
)
466 - RIGHT_TOTAL_LENGTH (tree
));
471 tree
->position
= LEFT_TOTAL_LENGTH (tree
)
472 + position
- relative_position
+ 1;
478 /* Find the succeeding interval (lexicographically) to INTERVAL.
479 Sets the `position' field based on that of INTERVAL (see
483 next_interval (interval
)
484 register INTERVAL interval
;
486 register INTERVAL i
= interval
;
487 register int next_position
;
489 if (NULL_INTERVAL_P (i
))
490 return NULL_INTERVAL
;
491 next_position
= interval
->position
+ LENGTH (interval
);
493 if (! NULL_RIGHT_CHILD (i
))
496 while (! NULL_LEFT_CHILD (i
))
499 i
->position
= next_position
;
503 while (! NULL_PARENT (i
))
505 if (AM_LEFT_CHILD (i
))
508 i
->position
= next_position
;
515 return NULL_INTERVAL
;
518 /* Find the preceding interval (lexicographically) to INTERVAL.
519 Sets the `position' field based on that of INTERVAL (see
523 previous_interval (interval
)
524 register INTERVAL interval
;
527 register position_of_previous
;
529 if (NULL_INTERVAL_P (interval
))
530 return NULL_INTERVAL
;
532 if (! NULL_LEFT_CHILD (interval
))
535 while (! NULL_RIGHT_CHILD (i
))
538 i
->position
= interval
->position
- LENGTH (i
);
543 while (! NULL_PARENT (i
))
545 if (AM_RIGHT_CHILD (i
))
549 i
->position
= interval
->position
- LENGTH (i
);
555 return NULL_INTERVAL
;
559 /* Traverse a path down the interval tree TREE to the interval
560 containing POSITION, adjusting all nodes on the path for
561 an addition of LENGTH characters. Insertion between two intervals
562 (i.e., point == i->position, where i is second interval) means
563 text goes into second interval.
565 Modifications are needed to handle the hungry bits -- after simply
566 finding the interval at position (don't add length going down),
567 if it's the beginning of the interval, get the previous interval
568 and check the hugry bits of both. Then add the length going back up
572 adjust_intervals_for_insertion (tree
, position
, length
)
574 int position
, length
;
576 register int relative_position
;
577 register INTERVAL
this;
579 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
582 /* If inserting at point-max of a buffer, that position
583 will be out of range */
584 if (position
> TOTAL_LENGTH (tree
))
585 position
= TOTAL_LENGTH (tree
);
586 relative_position
= position
;
591 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
593 this->total_length
+= length
;
596 else if (relative_position
> (TOTAL_LENGTH (this)
597 - RIGHT_TOTAL_LENGTH (this)))
599 relative_position
-= (TOTAL_LENGTH (this)
600 - RIGHT_TOTAL_LENGTH (this));
601 this->total_length
+= length
;
606 /* If we are to use zero-length intervals as buffer pointers,
607 then this code will have to change. */
608 this->total_length
+= length
;
609 this->position
= LEFT_TOTAL_LENGTH (this)
610 + position
- relative_position
+ 1;
617 /* Effect an adjustment corresponding to the addition of LENGTH characters
618 of text. Do this by finding the interval containing POSITION in the
619 interval tree TREE, and then adjusting all of it's ancestors by adding
622 If POSITION is the first character of an interval, meaning that point
623 is actually between the two intervals, make the new text belong to
624 the interval which is "sticky".
626 If both intervals are "sticky", then make them belong to the left-most
627 interval. Another possibility would be to create a new interval for
628 this text, and make it have the merged properties of both ends. */
631 adjust_intervals_for_insertion (tree
, position
, length
)
633 int position
, length
;
637 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
640 /* If inserting at point-max of a buffer, that position
641 will be out of range. */
642 if (position
> TOTAL_LENGTH (tree
))
643 position
= TOTAL_LENGTH (tree
);
645 i
= find_interval (tree
, position
);
646 /* If we are positioned between intervals, check the stickiness of
648 if (position
== i
->position
651 register prev
= previous_interval (i
);
653 /* If both intervals are sticky here, then default to the
654 left-most one. But perhaps we should create a new
655 interval here instead... */
656 if (END_STICKY (prev
))
660 while (! NULL_INTERVAL_P (i
))
662 i
->total_length
+= length
;
669 /* Delete an node I from its interval tree by merging its subtrees
670 into one subtree which is then returned. Caller is responsible for
671 storing the resulting subtree into its parent. */
677 register INTERVAL migrate
, this;
678 register int migrate_amt
;
680 if (NULL_INTERVAL_P (i
->left
))
682 if (NULL_INTERVAL_P (i
->right
))
686 migrate_amt
= i
->left
->total_length
;
688 this->total_length
+= migrate_amt
;
689 while (! NULL_INTERVAL_P (this->left
))
692 this->total_length
+= migrate_amt
;
694 this->left
= migrate
;
695 migrate
->parent
= this;
700 /* Delete interval I from its tree by calling `delete_node'
701 and properly connecting the resultant subtree.
703 I is presumed to be empty; that is, no adjustments are made
704 for the length of I. */
710 register INTERVAL parent
;
711 int amt
= LENGTH (i
);
713 if (amt
> 0) /* Only used on zero-length intervals now. */
716 if (ROOT_INTERVAL_P (i
))
718 Lisp_Object owner
= (Lisp_Object
) i
->parent
;
719 parent
= delete_node (i
);
720 if (! NULL_INTERVAL_P (parent
))
721 parent
->parent
= (INTERVAL
) owner
;
723 if (XTYPE (owner
) == Lisp_Buffer
)
724 XBUFFER (owner
)->intervals
= parent
;
725 else if (XTYPE (owner
) == Lisp_String
)
726 XSTRING (owner
)->intervals
= parent
;
734 if (AM_LEFT_CHILD (i
))
736 parent
->left
= delete_node (i
);
737 if (! NULL_INTERVAL_P (parent
->left
))
738 parent
->left
->parent
= parent
;
742 parent
->right
= delete_node (i
);
743 if (! NULL_INTERVAL_P (parent
->right
))
744 parent
->right
->parent
= parent
;
748 /* Find the interval in TREE corresponding to the character position FROM
749 and delete as much as possible of AMOUNT from that interval, starting
750 after the relative position of FROM within it. Return the amount
751 actually deleted, and if the interval was zeroed-out, delete that
752 interval node from the tree.
754 Do this by recursing down TREE to the interval in question, and
755 deleting the appropriate amount of text. */
758 interval_deletion_adjustment (tree
, from
, amount
)
759 register INTERVAL tree
;
760 register int from
, amount
;
762 register int relative_position
= from
;
764 if (NULL_INTERVAL_P (tree
))
768 if (relative_position
<= LEFT_TOTAL_LENGTH (tree
))
770 int subtract
= interval_deletion_adjustment (tree
->left
,
773 tree
->total_length
-= subtract
;
777 else if (relative_position
> (TOTAL_LENGTH (tree
)
778 - RIGHT_TOTAL_LENGTH (tree
)))
782 relative_position
-= (tree
->total_length
783 - RIGHT_TOTAL_LENGTH (tree
));
784 subtract
= interval_deletion_adjustment (tree
->right
,
787 tree
->total_length
-= subtract
;
790 /* Here -- this node */
793 /* If this is a zero-length, marker interval, then
796 if (relative_position
== LEFT_TOTAL_LENGTH (tree
) + 1)
798 /* This means we're deleting from the beginning of this interval. */
799 register int my_amount
= LENGTH (tree
);
801 if (amount
< my_amount
)
803 tree
->total_length
-= amount
;
808 tree
->total_length
-= my_amount
;
809 if (LENGTH (tree
) != 0)
810 abort (); /* Paranoia */
812 delete_interval (tree
);
816 else /* Deleting starting in the middle. */
818 register int my_amount
= ((tree
->total_length
819 - RIGHT_TOTAL_LENGTH (tree
))
820 - relative_position
+ 1);
822 if (amount
<= my_amount
)
824 tree
->total_length
-= amount
;
829 tree
->total_length
-= my_amount
;
835 /* Never reach here */
839 /* Effect the adjustments neccessary to the interval tree of BUFFER
840 to correspond to the deletion of LENGTH characters from that buffer
841 text. The deletion is effected at position START (relative to the
845 adjust_intervals_for_deletion (buffer
, start
, length
)
846 struct buffer
*buffer
;
849 register int left_to_delete
= length
;
850 register INTERVAL tree
= buffer
->intervals
;
851 register int deleted
;
853 if (NULL_INTERVAL_P (tree
))
856 if (length
== TOTAL_LENGTH (tree
))
858 buffer
->intervals
= NULL_INTERVAL
;
862 if (ONLY_INTERVAL_P (tree
))
864 tree
->total_length
-= length
;
868 if (start
> TOTAL_LENGTH (tree
))
869 start
= TOTAL_LENGTH (tree
);
870 while (left_to_delete
> 0)
872 left_to_delete
-= interval_deletion_adjustment (tree
, start
,
874 tree
= buffer
->intervals
;
875 if (left_to_delete
== tree
->total_length
)
877 buffer
->intervals
= NULL_INTERVAL
;
883 /* Make the adjustments neccessary to the interval tree of BUFFER to
884 represent an addition or deletion of LENGTH characters starting
885 at position START. Addition or deletion is indicated by the sign
889 offset_intervals (buffer
, start
, length
)
890 struct buffer
*buffer
;
893 if (NULL_INTERVAL_P (buffer
->intervals
) || length
== 0)
897 adjust_intervals_for_insertion (buffer
->intervals
, start
, length
);
899 adjust_intervals_for_deletion (buffer
, start
, -length
);
902 /* Merge interval I with its lexicographic successor. The resulting
903 interval is returned, and has the properties of the original
904 successor. The properties of I are lost. I is removed from the
908 The caller must verify that this is not the last (rightmost)
912 merge_interval_right (i
)
915 register int absorb
= LENGTH (i
);
916 register INTERVAL successor
;
918 /* Zero out this interval. */
919 i
->total_length
-= absorb
;
921 /* Find the succeeding interval. */
922 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
925 successor
= i
->right
;
926 while (! NULL_LEFT_CHILD (successor
))
928 successor
->total_length
+= absorb
;
929 successor
= successor
->left
;
932 successor
->total_length
+= absorb
;
938 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
941 if (AM_LEFT_CHILD (successor
))
943 successor
= successor
->parent
;
948 successor
= successor
->parent
;
949 successor
->total_length
-= absorb
;
952 /* This must be the rightmost or last interval and cannot
953 be merged right. The caller should have known. */
957 /* Merge interval I with its lexicographic predecessor. The resulting
958 interval is returned, and has the properties of the original predecessor.
959 The properties of I are lost. Interval node I is removed from the tree.
962 The caller must verify that this is not the first (leftmost) interval. */
965 merge_interval_left (i
)
968 register int absorb
= LENGTH (i
);
969 register INTERVAL predecessor
;
971 /* Zero out this interval. */
972 i
->total_length
-= absorb
;
974 /* Find the preceding interval. */
975 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
976 adding ABSORB as we go. */
978 predecessor
= i
->left
;
979 while (! NULL_RIGHT_CHILD (predecessor
))
981 predecessor
->total_length
+= absorb
;
982 predecessor
= predecessor
->right
;
985 predecessor
->total_length
+= absorb
;
991 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
992 subtracting ABSORB. */
994 if (AM_RIGHT_CHILD (predecessor
))
996 predecessor
= predecessor
->parent
;
1001 predecessor
= predecessor
->parent
;
1002 predecessor
->total_length
-= absorb
;
1005 /* This must be the leftmost or first interval and cannot
1006 be merged left. The caller should have known. */
1010 /* Make an exact copy of interval tree SOURCE which descends from
1011 PARENT. This is done by recursing through SOURCE, copying
1012 the current interval and its properties, and then adjusting
1013 the pointers of the copy. */
1016 reproduce_tree (source
, parent
)
1017 INTERVAL source
, parent
;
1019 register INTERVAL t
= make_interval ();
1021 bcopy (source
, t
, INTERVAL_SIZE
);
1022 copy_properties (source
, t
);
1024 if (! NULL_LEFT_CHILD (source
))
1025 t
->left
= reproduce_tree (source
->left
, t
);
1026 if (! NULL_RIGHT_CHILD (source
))
1027 t
->right
= reproduce_tree (source
->right
, t
);
1032 /* Make a new interval of length LENGTH starting at START in the
1033 group of intervals INTERVALS, which is actually an interval tree.
1034 Returns the new interval.
1036 Generate an error if the new positions would overlap an existing
1040 make_new_interval (intervals
, start
, length
)
1046 slot
= find_interval (intervals
, start
);
1047 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1048 error ("Interval would overlap");
1050 if (start
== slot
->position
&& length
== LENGTH (slot
))
1053 if (slot
->position
== start
)
1055 /* New right node. */
1056 split_interval_right (slot
, length
+ 1);
1060 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1062 /* New left node. */
1063 split_interval_left (slot
, LENGTH (slot
) - length
+ 1);
1067 /* Convert interval SLOT into three intervals. */
1068 split_interval_left (slot
, start
- slot
->position
+ 1);
1069 split_interval_right (slot
, length
+ 1);
1073 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1075 This is used in insdel.c when inserting Lisp_Strings into
1076 the buffer. The text corresponding to SOURCE is already in
1077 the buffer when this is called. The intervals of new tree are
1078 those belonging to the string being inserted; a copy is not made.
1080 If the inserted text had no intervals associated, this function
1081 simply returns -- offset_intervals should handle placing the
1082 text in the correct interval, depending on the sticky bits.
1084 If the inserted text had properties (intervals), then there are two
1085 cases -- either insertion happened in the middle of some interval,
1086 or between two intervals.
1088 If the text goes into the middle of an interval, then new
1089 intervals are created in the middle with only the properties of
1090 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1091 which case the new text has the union of its properties and those
1092 of the text into which it was inserted.
1094 If the text goes between two intervals, then if neither interval
1095 had its appropriate sticky property set (front_sticky, rear_sticky),
1096 the new text has only its properties. If one of the sticky properties
1097 is set, then the new text "sticks" to that region and its properties
1098 depend on merging as above. If both the preceding and succeding
1099 intervals to the new text are "sticky", then the new text retains
1100 only its properties, as if neither sticky property were set. Perhaps
1101 we should consider merging all three sets of properties onto the new
1105 graft_intervals_into_buffer (source
, position
, buffer
)
1108 struct buffer
*buffer
;
1110 register INTERVAL under
, over
, this;
1111 register INTERVAL tree
= buffer
->intervals
;
1113 /* If the new text has no properties, it becomes part of whatever
1114 interval it was inserted into. */
1115 if (NULL_INTERVAL_P (source
))
1118 /* Paranoia -- the text has already been added, so this buffer
1119 should be of non-zero length. */
1120 if (TOTAL_LENGTH (tree
) == 0)
1123 if (NULL_INTERVAL_P (tree
))
1125 /* The inserted text constitutes the whole buffer, so
1126 simply copy over the interval structure. */
1127 if (BUF_Z (b
) == TOTAL_LENGTH (source
))
1129 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1130 /* Explicitly free the old tree here. */
1135 /* Create an interval tree in which to place a copy
1136 of the intervals of the inserted string. */
1139 XSET (buffer
, Lisp_Buffer
, b
);
1140 create_root_interval (buffer
);
1144 if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1146 /* If the buffer contains only the new string, but
1147 there was already some interval tree there, then it may be
1148 some zero length intervals. Eventually, do something clever
1149 about inserting properly. For now, just waste the old intervals. */
1151 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1152 /* Explicitly free the old tree here. */
1157 this = under
= find_interval (tree
, position
);
1158 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1160 over
= find_interval (source
, 1);
1162 /* Insertion between intervals */
1163 if (position
== under
->position
)
1165 /* First interval -- none precede it. */
1168 if (! FRONT_STICKY (under
))
1169 /* The inserted string keeps its own properties. */
1170 while (! NULL_INTERVAL_P (over
))
1172 position
= LENGTH (over
) + 1;
1173 this = split_interval_left (this, position
);
1174 copy_properties (over
, this);
1175 over
= next_interval (over
);
1178 /* This string "sticks" to the first interval, `under',
1179 which means it gets those properties. */
1180 while (! NULL_INTERVAL_P (over
))
1182 position
= LENGTH (over
) + 1;
1183 this = split_interval_left (this, position
);
1184 copy_properties (under
, this);
1185 if (MERGE_INSERTIONS (under
))
1186 merge_properties (over
, this);
1187 over
= next_interval (over
);
1192 INTERVAL prev
= previous_interval (under
);
1193 if (NULL_INTERVAL_P (prev
))
1196 if (END_STICKY (prev
))
1198 if (FRONT_STICKY (under
))
1199 /* The intervals go inbetween as the two sticky
1200 properties cancel each other. Should we change
1202 while (! NULL_INTERVAL_P (over
))
1204 position
= LENGTH (over
) + 1;
1205 this = split_interval_left (this, position
);
1206 copy_properties (over
, this);
1207 over
= next_interval (over
);
1210 /* The intervals stick to prev */
1211 while (! NULL_INTERVAL_P (over
))
1213 position
= LENGTH (over
) + 1;
1214 this = split_interval_left (this, position
);
1215 copy_properties (prev
, this);
1216 if (MERGE_INSERTIONS (prev
))
1217 merge_properties (over
, this);
1218 over
= next_interval (over
);
1223 if (FRONT_STICKY (under
))
1224 /* The inserted text "sticks" to the interval `under',
1225 which means it gets those properties. */
1226 while (! NULL_INTERVAL_P (over
))
1228 position
= LENGTH (over
) + 1;
1229 this = split_interval_left (this, position
);
1230 copy_properties (under
, this);
1231 if (MERGE_INSERTIONS (under
))
1232 merge_properties (over
, this);
1233 over
= next_interval (over
);
1236 /* The intervals go inbetween */
1237 while (! NULL_INTERVAL_P (over
))
1239 position
= LENGTH (over
) + 1;
1240 this = split_interval_left (this, position
);
1241 copy_properties (over
, this);
1242 over
= next_interval (over
);
1247 buffer
->intervals
= balance_intervals (buffer
->intervals
);
1251 /* Here for insertion in the middle of an interval. */
1253 if (TOTAL_LENGTH (source
) < LENGTH (this))
1255 INTERVAL end_unchanged
1256 = split_interval_right (this, TOTAL_LENGTH (source
) + 1);
1257 copy_properties (under
, end_unchanged
);
1260 position
= position
- tree
->position
+ 1;
1261 while (! NULL_INTERVAL_P (over
))
1263 this = split_interval_right (under
, position
);
1264 copy_properties (over
, this);
1265 if (MERGE_INSERTIONS (under
))
1266 merge_properties (under
, this);
1268 position
= LENGTH (over
) + 1;
1269 over
= next_interval (over
);
1272 buffer
->intervals
= balance_intervals (buffer
->intervals
);
1276 /* Set point in BUFFER to POSITION. If the target position is in
1277 an invisible interval which is not displayed with a special glyph,
1278 skip intervals until we find one. Point may be at the first
1279 position of an invisible interval, if it is displayed with a
1282 This is the only place `PT' is an lvalue in all of emacs. */
1285 set_point (position
, buffer
)
1286 register int position
;
1287 register struct buffer
*buffer
;
1289 register INTERVAL to
, from
, target
;
1290 register int iposition
= position
;
1292 register Lisp_Object obj
;
1293 int backwards
= (position
< BUF_PT (buffer
)) ? 1 : 0;
1294 int old_position
= buffer
->text
.pt
;
1296 if (position
== buffer
->text
.pt
)
1299 if (NULL_INTERVAL_P (buffer
->intervals
))
1301 buffer
->text
.pt
= position
;
1305 /* Perhaps we should just change `position' to the limit. */
1306 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1309 /* Position Z is really one past the last char in the buffer. */
1310 if (position
== BUF_Z (buffer
))
1311 iposition
= position
- 1;
1313 to
= find_interval (buffer
->intervals
, iposition
);
1314 buffer_point
=(BUF_PT (buffer
) == BUF_Z (buffer
)
1315 ? BUF_Z (buffer
) - 1
1318 /* We could cache this and save time. */
1319 from
= find_interval (buffer
->intervals
, buffer_point
);
1321 if (NULL_INTERVAL_P (to
) || NULL_INTERVAL_P (from
))
1322 abort (); /* Paranoia */
1324 /* Moving within an interval */
1325 if (to
== from
&& INTERVAL_VISIBLE_P (to
))
1327 buffer
->text
.pt
= position
;
1331 /* Here for the case of moving into another interval. */
1334 while (! INTERVAL_VISIBLE_P (to
) && ! DISPLAY_INVISIBLE_GLYPH (to
)
1335 && ! NULL_INTERVAL_P (to
))
1336 to
= (backwards
? previous_interval (to
) : next_interval (to
));
1337 if (NULL_INTERVAL_P (to
))
1340 /* Here we know we are actually moving to another interval. */
1341 if (INTERVAL_VISIBLE_P (to
))
1343 /* If we skipped some intervals, go to the closest point
1344 in the interval we've stopped at. */
1346 buffer
->text
.pt
= (backwards
1347 ? to
->position
+ LENGTH (to
) - 1
1350 buffer
->text
.pt
= position
;
1353 buffer
->text
.pt
= to
->position
;
1355 /* We should run point-left and point-entered hooks here, iff the
1356 two intervals are not equivalent. */
1357 if (! intervals_equal (from
, to
))
1361 val
= Fget (Qpoint_left
, from
->plist
);
1363 call2 (val
, old_position
, position
);
1365 val
= Fget (Qpoint_entered
, to
->plist
);
1367 call2 (val
, old_position
, position
);
1371 /* Set point temporarily, without checking any text properties. */
1374 temp_set_point (position
, buffer
)
1376 struct buffer
*buffer
;
1378 buffer
->text
.pt
= position
;
1381 /* Check for read-only intervals and signal an error if we find one.
1382 Then check for any modification hooks in the range START up to
1383 (but not including) TO. Create a list of all these hooks in
1384 lexicographic order, eliminating consecutive extra copies of the
1385 same hook. Then call those hooks in order, with START and END - 1
1389 verify_interval_modification (buf
, start
, end
)
1393 register INTERVAL intervals
= buf
->intervals
;
1394 register INTERVAL i
;
1395 register Lisp_Object hooks
= Qnil
;
1396 register prev_mod_hook
= Qnil
;
1397 register Lisp_Object mod_hook
;
1398 struct gcpro gcpro1
;
1400 if (NULL_INTERVAL_P (intervals
))
1410 if (start
== BUF_Z (buf
))
1412 /* This should not be getting called on empty buffers. */
1413 if (BUF_Z (buf
) == 1)
1416 i
= find_interval (intervals
, start
- 1);
1417 if (! END_STICKY_P (i
))
1421 i
= find_interval (intervals
, start
);
1425 if (! INTERVAL_WRITABLE_P (i
))
1426 error ("Attempt to modify read-only text");
1428 mod_hook
= Fget (Qmodification
, i
->plist
);
1429 if (! NILP (mod_hook
) && ! EQ (mod_hook
, prev_mod_hook
))
1431 hooks
= Fcons (mod_hook
, hooks
);
1432 prev_mod_hook
= mod_hook
;
1435 i
= next_interval (i
);
1437 while (! NULL_INTERVAL_P (i
) && i
->position
<= end
);
1440 hooks
= Fnreverse (hooks
);
1441 while (! EQ (hooks
, Qnil
))
1443 call2 (Fcar (hooks
), start
, end
- 1);
1444 hooks
= Fcdr (hooks
);
1449 /* Balance an interval node if the amount of text in its left and right
1450 subtrees differs by more than the percentage specified by
1451 `interval-balance-threshold'. */
1454 balance_an_interval (i
)
1457 register int total_children_size
= (LEFT_TOTAL_LENGTH (i
)
1458 + RIGHT_TOTAL_LENGTH (i
));
1459 register int threshold
= (XFASTINT (interval_balance_threshold
)
1460 * (total_children_size
/ 100));
1462 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1463 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1464 return rotate_right (i
);
1466 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1467 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1468 return rotate_right (i
);
1471 if (LEFT_TOTAL_LENGTH (i
) >
1472 (RIGHT_TOTAL_LENGTH (i
) + XINT (interval_balance_threshold
)))
1473 return rotate_right (i
);
1475 if (RIGHT_TOTAL_LENGTH (i
) >
1476 (LEFT_TOTAL_LENGTH (i
) + XINT (interval_balance_threshold
)))
1477 return rotate_left (i
);
1483 /* Balance the interval tree TREE. Balancing is by weight
1484 (the amount of text). */
1487 balance_intervals (tree
)
1488 register INTERVAL tree
;
1490 register INTERVAL new_tree
;
1492 if (NULL_INTERVAL_P (tree
))
1493 return NULL_INTERVAL
;
1499 new_tree
= balance_an_interval (new_tree
);
1501 while (new_tree
!= tree
);
1506 /* Produce an interval tree reflecting the intervals in
1507 TREE from START to START + LENGTH. */
1510 copy_intervals (tree
, start
, length
)
1514 register INTERVAL i
, new, t
;
1517 if (NULL_INTERVAL_P (tree
) || length
<= 0)
1518 return NULL_INTERVAL
;
1520 i
= find_interval (tree
, start
);
1521 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
1524 /* If there is only one interval and it's the default, return nil. */
1525 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
1526 && DEFAULT_INTERVAL_P (i
))
1527 return NULL_INTERVAL
;
1529 new = make_interval ();
1531 got
= (LENGTH (i
) - (start
- i
->position
));
1532 new->total_length
= length
;
1533 copy_properties (i
, new);
1536 while (got
< length
)
1538 i
= next_interval (i
);
1539 t
= split_interval_right (t
, got
+ 1);
1540 copy_properties (i
, t
);
1545 t
->total_length
-= (got
- length
);
1547 return balance_intervals (new);
1550 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1553 copy_intervals_to_string (string
, buffer
, position
, length
)
1554 Lisp_Object string
, buffer
;
1555 int position
, length
;
1557 INTERVAL interval_copy
= copy_intervals (XBUFFER (buffer
)->intervals
,
1559 if (NULL_INTERVAL_P (interval_copy
))
1562 interval_copy
->parent
= (INTERVAL
) string
;
1563 XSTRING (string
)->intervals
= interval_copy
;