1 /* Code for doing intervals.
2 Copyright (C) 1993 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 2, 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 /* The rest of the file is within this conditional. */
48 #ifdef USE_TEXT_PROPERTIES
50 /* Factor for weight-balancing interval trees. */
51 Lisp_Object interval_balance_threshold
;
53 Lisp_Object
merge_properties_sticky ();
55 /* Utility functions for intervals. */
58 /* Create the root interval of some object, a buffer or string. */
61 create_root_interval (parent
)
66 CHECK_IMPURE (parent
);
68 new = make_interval ();
70 if (XTYPE (parent
) == Lisp_Buffer
)
72 new->total_length
= (BUF_Z (XBUFFER (parent
))
73 - BUF_BEG (XBUFFER (parent
)));
74 XBUFFER (parent
)->intervals
= new;
76 else if (XTYPE (parent
) == Lisp_String
)
78 new->total_length
= XSTRING (parent
)->size
;
79 XSTRING (parent
)->intervals
= new;
82 new->parent
= (INTERVAL
) parent
;
88 /* Make the interval TARGET have exactly the properties of SOURCE */
91 copy_properties (source
, target
)
92 register INTERVAL source
, target
;
94 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
97 COPY_INTERVAL_CACHE (source
, target
);
98 target
->plist
= Fcopy_sequence (source
->plist
);
101 /* Merge the properties of interval SOURCE into the properties
102 of interval TARGET. That is to say, each property in SOURCE
103 is added to TARGET if TARGET has no such property as yet. */
106 merge_properties (source
, target
)
107 register INTERVAL source
, target
;
109 register Lisp_Object o
, sym
, val
;
111 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
114 MERGE_INTERVAL_CACHE (source
, target
);
117 while (! EQ (o
, Qnil
))
120 val
= Fmemq (sym
, target
->plist
);
126 target
->plist
= Fcons (sym
, Fcons (val
, target
->plist
));
134 /* Return 1 if the two intervals have the same properties,
138 intervals_equal (i0
, i1
)
141 register Lisp_Object i0_cdr
, i0_sym
, i1_val
;
144 if (DEFAULT_INTERVAL_P (i0
) && DEFAULT_INTERVAL_P (i1
))
147 if (DEFAULT_INTERVAL_P (i0
) || DEFAULT_INTERVAL_P (i1
))
150 i1_len
= XFASTINT (Flength (i1
->plist
));
151 if (i1_len
& 0x1) /* Paranoia -- plists are always even */
155 while (!NILP (i0_cdr
))
157 /* Lengths of the two plists were unequal. */
161 i0_sym
= Fcar (i0_cdr
);
162 i1_val
= Fmemq (i0_sym
, i1
->plist
);
164 /* i0 has something i1 doesn't. */
165 if (EQ (i1_val
, Qnil
))
168 /* i0 and i1 both have sym, but it has different values in each. */
169 i0_cdr
= Fcdr (i0_cdr
);
170 if (! EQ (Fcar (Fcdr (i1_val
)), Fcar (i0_cdr
)))
173 i0_cdr
= Fcdr (i0_cdr
);
177 /* Lengths of the two plists were unequal. */
186 static int zero_length
;
188 /* Traverse an interval tree TREE, performing FUNCTION on each node.
189 Pass FUNCTION two args: an interval, and ARG. */
192 traverse_intervals (tree
, position
, depth
, function
, arg
)
195 void (* function
) ();
198 if (NULL_INTERVAL_P (tree
))
201 traverse_intervals (tree
->left
, position
, depth
+ 1, function
, arg
);
202 position
+= LEFT_TOTAL_LENGTH (tree
);
203 tree
->position
= position
;
204 (*function
) (tree
, arg
);
205 position
+= LENGTH (tree
);
206 traverse_intervals (tree
->right
, position
, depth
+ 1, function
, arg
);
210 /* These functions are temporary, for debugging purposes only. */
212 INTERVAL search_interval
, found_interval
;
215 check_for_interval (i
)
218 if (i
== search_interval
)
226 search_for_interval (i
, tree
)
227 register INTERVAL i
, tree
;
231 found_interval
= NULL_INTERVAL
;
232 traverse_intervals (tree
, 1, 0, &check_for_interval
, Qnil
);
233 return found_interval
;
237 inc_interval_count (i
)
254 traverse_intervals (i
, 1, 0, &inc_interval_count
, Qnil
);
260 root_interval (interval
)
263 register INTERVAL i
= interval
;
265 while (! ROOT_INTERVAL_P (i
))
272 /* Assuming that a left child exists, perform the following operation:
282 rotate_right (interval
)
286 INTERVAL B
= interval
->left
;
287 int len
= LENGTH (interval
);
289 /* Deal with any Parent of A; make it point to B. */
290 if (! ROOT_INTERVAL_P (interval
))
291 if (AM_LEFT_CHILD (interval
))
292 interval
->parent
->left
= interval
->left
;
294 interval
->parent
->right
= interval
->left
;
295 interval
->left
->parent
= interval
->parent
;
297 /* B gets the same length as A, since it get A's position in the tree. */
298 interval
->left
->total_length
= interval
->total_length
;
300 /* B becomes the parent of A. */
301 i
= interval
->left
->right
;
302 interval
->left
->right
= interval
;
303 interval
->parent
= interval
->left
;
305 /* A gets c as left child. */
307 if (! NULL_INTERVAL_P (i
))
308 i
->parent
= interval
;
309 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
310 + RIGHT_TOTAL_LENGTH (interval
));
315 /* Assuming that a right child exists, perform the following operation:
325 rotate_left (interval
)
329 INTERVAL B
= interval
->right
;
330 int len
= LENGTH (interval
);
332 /* Deal with the parent of A. */
333 if (! ROOT_INTERVAL_P (interval
))
334 if (AM_LEFT_CHILD (interval
))
335 interval
->parent
->left
= interval
->right
;
337 interval
->parent
->right
= interval
->right
;
338 interval
->right
->parent
= interval
->parent
;
340 /* B must have the same total length of A. */
341 interval
->right
->total_length
= interval
->total_length
;
343 /* Make B the parent of A */
344 i
= interval
->right
->left
;
345 interval
->right
->left
= interval
;
346 interval
->parent
= interval
->right
;
348 /* Make A point to c */
350 if (! NULL_INTERVAL_P (i
))
351 i
->parent
= interval
;
352 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
353 + RIGHT_TOTAL_LENGTH (interval
));
358 /* Split INTERVAL into two pieces, starting the second piece at
359 character position OFFSET (counting from 0), relative to INTERVAL.
360 INTERVAL becomes the left-hand piece, and the right-hand piece
361 (second, lexicographically) is returned.
363 The size and position fields of the two intervals are set based upon
364 those of the original interval. The property list of the new interval
365 is reset, thus it is up to the caller to do the right thing with the
368 Note that this does not change the position of INTERVAL; if it is a root,
369 it is still a root after this operation. */
372 split_interval_right (interval
, offset
)
376 INTERVAL
new = make_interval ();
377 int position
= interval
->position
;
378 int new_length
= LENGTH (interval
) - offset
;
380 new->position
= position
+ offset
;
381 new->parent
= interval
;
383 if (LEAF_INTERVAL_P (interval
) || NULL_RIGHT_CHILD (interval
))
385 interval
->right
= new;
386 new->total_length
= new_length
;
391 /* Insert the new node between INTERVAL and its right child. */
392 new->right
= interval
->right
;
393 interval
->right
->parent
= new;
394 interval
->right
= new;
396 new->total_length
= new_length
+ new->right
->total_length
;
401 /* Split INTERVAL into two pieces, starting the second piece at
402 character position OFFSET (counting from 0), relative to INTERVAL.
403 INTERVAL becomes the right-hand piece, and the left-hand piece
404 (first, lexicographically) is returned.
406 The size and position fields of the two intervals are set based upon
407 those of the original interval. The property list of the new interval
408 is reset, thus it is up to the caller to do the right thing with the
411 Note that this does not change the position of INTERVAL; if it is a root,
412 it is still a root after this operation. */
415 split_interval_left (interval
, offset
)
419 INTERVAL
new = make_interval ();
420 int position
= interval
->position
;
421 int new_length
= offset
;
423 new->position
= interval
->position
;
424 interval
->position
= interval
->position
+ offset
;
425 new->parent
= interval
;
427 if (NULL_LEFT_CHILD (interval
))
429 interval
->left
= new;
430 new->total_length
= new_length
;
435 /* Insert the new node between INTERVAL and its left child. */
436 new->left
= interval
->left
;
437 new->left
->parent
= new;
438 interval
->left
= new;
439 new->total_length
= new_length
+ LEFT_TOTAL_LENGTH (new);
444 /* Find the interval containing text position POSITION in the text
445 represented by the interval tree TREE. POSITION is a buffer
446 position; the earliest position is 1. If POSITION is at the end of
447 the buffer, return the interval containing the last character.
449 The `position' field, which is a cache of an interval's position,
450 is updated in the interval found. Other functions (e.g., next_interval)
451 will update this cache based on the result of find_interval. */
454 find_interval (tree
, position
)
455 register INTERVAL tree
;
456 register int position
;
458 /* The distance from the left edge of the subtree at TREE
460 register int relative_position
= position
- BEG
;
462 if (NULL_INTERVAL_P (tree
))
463 return NULL_INTERVAL
;
465 if (relative_position
> TOTAL_LENGTH (tree
))
466 abort (); /* Paranoia */
470 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
474 else if (! NULL_RIGHT_CHILD (tree
)
475 && relative_position
>= (TOTAL_LENGTH (tree
)
476 - RIGHT_TOTAL_LENGTH (tree
)))
478 relative_position
-= (TOTAL_LENGTH (tree
)
479 - RIGHT_TOTAL_LENGTH (tree
));
485 (position
- relative_position
/* the left edge of *tree */
486 + LEFT_TOTAL_LENGTH (tree
)); /* the left edge of this interval */
493 /* Find the succeeding interval (lexicographically) to INTERVAL.
494 Sets the `position' field based on that of INTERVAL (see
498 next_interval (interval
)
499 register INTERVAL interval
;
501 register INTERVAL i
= interval
;
502 register int next_position
;
504 if (NULL_INTERVAL_P (i
))
505 return NULL_INTERVAL
;
506 next_position
= interval
->position
+ LENGTH (interval
);
508 if (! NULL_RIGHT_CHILD (i
))
511 while (! NULL_LEFT_CHILD (i
))
514 i
->position
= next_position
;
518 while (! NULL_PARENT (i
))
520 if (AM_LEFT_CHILD (i
))
523 i
->position
= next_position
;
530 return NULL_INTERVAL
;
533 /* Find the preceding interval (lexicographically) to INTERVAL.
534 Sets the `position' field based on that of INTERVAL (see
538 previous_interval (interval
)
539 register INTERVAL interval
;
542 register position_of_previous
;
544 if (NULL_INTERVAL_P (interval
))
545 return NULL_INTERVAL
;
547 if (! NULL_LEFT_CHILD (interval
))
550 while (! NULL_RIGHT_CHILD (i
))
553 i
->position
= interval
->position
- LENGTH (i
);
558 while (! NULL_PARENT (i
))
560 if (AM_RIGHT_CHILD (i
))
564 i
->position
= interval
->position
- LENGTH (i
);
570 return NULL_INTERVAL
;
574 /* Traverse a path down the interval tree TREE to the interval
575 containing POSITION, adjusting all nodes on the path for
576 an addition of LENGTH characters. Insertion between two intervals
577 (i.e., point == i->position, where i is second interval) means
578 text goes into second interval.
580 Modifications are needed to handle the hungry bits -- after simply
581 finding the interval at position (don't add length going down),
582 if it's the beginning of the interval, get the previous interval
583 and check the hugry bits of both. Then add the length going back up
587 adjust_intervals_for_insertion (tree
, position
, length
)
589 int position
, length
;
591 register int relative_position
;
592 register INTERVAL
this;
594 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
597 /* If inserting at point-max of a buffer, that position
598 will be out of range */
599 if (position
> TOTAL_LENGTH (tree
))
600 position
= TOTAL_LENGTH (tree
);
601 relative_position
= position
;
606 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
608 this->total_length
+= length
;
611 else if (relative_position
> (TOTAL_LENGTH (this)
612 - RIGHT_TOTAL_LENGTH (this)))
614 relative_position
-= (TOTAL_LENGTH (this)
615 - RIGHT_TOTAL_LENGTH (this));
616 this->total_length
+= length
;
621 /* If we are to use zero-length intervals as buffer pointers,
622 then this code will have to change. */
623 this->total_length
+= length
;
624 this->position
= LEFT_TOTAL_LENGTH (this)
625 + position
- relative_position
+ 1;
632 /* Effect an adjustment corresponding to the addition of LENGTH characters
633 of text. Do this by finding the interval containing POSITION in the
634 interval tree TREE, and then adjusting all of it's ancestors by adding
637 If POSITION is the first character of an interval, meaning that point
638 is actually between the two intervals, make the new text belong to
639 the interval which is "sticky".
641 If both intervals are "sticky", then make them belong to the left-most
642 interval. Another possibility would be to create a new interval for
643 this text, and make it have the merged properties of both ends. */
646 adjust_intervals_for_insertion (tree
, position
, length
)
648 int position
, length
;
651 register INTERVAL temp
;
654 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
657 /* If inserting at point-max of a buffer, that position will be out
658 of range. Remember that buffer positions are 1-based. */
659 if (position
>= BEG
+ TOTAL_LENGTH (tree
)){
660 position
= BEG
+ TOTAL_LENGTH (tree
);
664 i
= find_interval (tree
, position
);
666 /* If in middle of an interval which is not sticky either way,
667 we must not just give its properties to the insertion.
668 So split this interval at the insertion point. */
669 if (! (position
== i
->position
|| eobp
)
670 && END_NONSTICKY_P (i
)
671 && ! FRONT_STICKY_P (i
))
673 temp
= split_interval_right (i
, position
- i
->position
);
674 copy_properties (i
, temp
);
678 /* If we are positioned between intervals, check the stickiness of
679 both of them. We have to do this too, if we are at BEG or Z. */
680 if (position
== i
->position
|| eobp
)
682 register INTERVAL prev
;
692 prev
= previous_interval (i
);
694 /* Even if we are positioned between intervals, we default
695 to the left one if it exists. We extend it now and split
696 off a part later, if stickyness demands it. */
697 for (temp
= prev
? prev
: i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
698 temp
->total_length
+= length
;
700 /* If at least one interval has sticky properties,
701 we check the stickyness property by property. */
702 if (END_NONSTICKY_P (prev
) || FRONT_STICKY_P (i
))
704 Lisp_Object pleft
= NULL_INTERVAL_P (prev
) ? Qnil
: prev
->plist
;
705 Lisp_Object pright
= NULL_INTERVAL_P (i
) ? Qnil
: i
->plist
;
706 struct interval newi
;
708 newi
.plist
= merge_properties_sticky (pleft
, pright
);
710 if(! prev
) /* i.e. position == BEG */
712 if (! intervals_equal (i
, &newi
))
714 i
= split_interval_left (i
, length
);
715 i
->plist
= newi
.plist
;
718 else if (! intervals_equal (prev
, &newi
))
720 prev
= split_interval_right (prev
,
721 position
- prev
->position
);
722 prev
->plist
= newi
.plist
;
723 if (! NULL_INTERVAL_P (i
)
724 && intervals_equal (prev
, i
))
725 merge_interval_right (prev
);
728 /* We will need to update the cache here later. */
730 else if (! prev
&& ! NILP (i
->plist
))
732 /* Just split off a new interval at the left.
733 Since I wasn't front-sticky, the empty plist is ok. */
734 i
= split_interval_left (i
, length
);
738 /* Otherwise just extend the interval. */
741 for (temp
= i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
742 temp
->total_length
+= length
;
749 merge_properties_sticky (pleft
, pright
)
750 Lisp_Object pleft
, pright
;
752 register Lisp_Object props
= Qnil
, front
= Qnil
, rear
= Qnil
;
754 Lisp_Object lfront
= textget (pleft
, Qfront_sticky
);
755 Lisp_Object lrear
= textget (pleft
, Qrear_nonsticky
);
756 Lisp_Object rfront
= textget (pright
, Qfront_sticky
);
757 Lisp_Object rrear
= textget (pright
, Qrear_nonsticky
);
759 register Lisp_Object tail1
, tail2
, sym
;
761 /* Go through each element of PLEFT. */
762 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
766 /* Sticky properties get special treatment. */
767 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
770 if (CONSP (lrear
) ? NILP (Fmemq (sym
, lrear
)) : NILP (lrear
))
772 /* rear-sticky is dominant, we needn't search in PRIGHT. */
774 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail1
)), props
));
775 if ((CONSP (lfront
) || NILP (lfront
))
776 && ! NILP (Fmemq (sym
, lfront
)))
777 front
= Fcons (sym
, front
);
781 /* Go through PRIGHT, looking for sym. */
782 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
783 if (EQ (sym
, Fcar (tail2
)))
787 ? ! NILP (Fmemq (sym
, rfront
)) : ! NILP (rfront
))
789 /* Nonsticky at the left and sticky at the right,
790 so take the right one. */
791 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
792 front
= Fcons (sym
, front
);
793 if ((CONSP (rrear
) || NILP (rrear
))
794 && ! NILP (Fmemq (sym
, rrear
)))
795 rear
= Fcons (sym
, rear
);
801 /* Now let's see what to keep from PRIGHT. */
802 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
806 /* Sticky properties get special treatment. */
807 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
810 /* If it ain't sticky, we don't take it. */
812 ? NILP (Fmemq (sym
, rfront
)) : NILP (rfront
))
815 /* If sym is in PLEFT we already got it. */
816 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
817 if (EQ (sym
, Fcar (tail1
)))
822 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
823 front
= Fcons (sym
, front
);
824 if ((CONSP (rrear
) || NILP (rrear
))
825 && ! NILP (Fmemq (sym
, rrear
)))
826 rear
= Fcons (sym
, rear
);
830 props
= Fcons (Qfront_sticky
, Fcons (front
, props
));
832 props
= Fcons (Qrear_nonsticky
, Fcons (rear
, props
));
838 /* Delete an node I from its interval tree by merging its subtrees
839 into one subtree which is then returned. Caller is responsible for
840 storing the resulting subtree into its parent. */
846 register INTERVAL migrate
, this;
847 register int migrate_amt
;
849 if (NULL_INTERVAL_P (i
->left
))
851 if (NULL_INTERVAL_P (i
->right
))
855 migrate_amt
= i
->left
->total_length
;
857 this->total_length
+= migrate_amt
;
858 while (! NULL_INTERVAL_P (this->left
))
861 this->total_length
+= migrate_amt
;
863 this->left
= migrate
;
864 migrate
->parent
= this;
869 /* Delete interval I from its tree by calling `delete_node'
870 and properly connecting the resultant subtree.
872 I is presumed to be empty; that is, no adjustments are made
873 for the length of I. */
879 register INTERVAL parent
;
880 int amt
= LENGTH (i
);
882 if (amt
> 0) /* Only used on zero-length intervals now. */
885 if (ROOT_INTERVAL_P (i
))
887 Lisp_Object owner
= (Lisp_Object
) i
->parent
;
888 parent
= delete_node (i
);
889 if (! NULL_INTERVAL_P (parent
))
890 parent
->parent
= (INTERVAL
) owner
;
892 if (XTYPE (owner
) == Lisp_Buffer
)
893 XBUFFER (owner
)->intervals
= parent
;
894 else if (XTYPE (owner
) == Lisp_String
)
895 XSTRING (owner
)->intervals
= parent
;
903 if (AM_LEFT_CHILD (i
))
905 parent
->left
= delete_node (i
);
906 if (! NULL_INTERVAL_P (parent
->left
))
907 parent
->left
->parent
= parent
;
911 parent
->right
= delete_node (i
);
912 if (! NULL_INTERVAL_P (parent
->right
))
913 parent
->right
->parent
= parent
;
917 /* Find the interval in TREE corresponding to the relative position
918 FROM and delete as much as possible of AMOUNT from that interval.
919 Return the amount actually deleted, and if the interval was
920 zeroed-out, delete that interval node from the tree.
922 Note that FROM is actually origin zero, aka relative to the
923 leftmost edge of tree. This is appropriate since we call ourselves
924 recursively on subtrees.
926 Do this by recursing down TREE to the interval in question, and
927 deleting the appropriate amount of text. */
930 interval_deletion_adjustment (tree
, from
, amount
)
931 register INTERVAL tree
;
932 register int from
, amount
;
934 register int relative_position
= from
;
936 if (NULL_INTERVAL_P (tree
))
940 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
942 int subtract
= interval_deletion_adjustment (tree
->left
,
945 tree
->total_length
-= subtract
;
949 else if (relative_position
>= (TOTAL_LENGTH (tree
)
950 - RIGHT_TOTAL_LENGTH (tree
)))
954 relative_position
-= (tree
->total_length
955 - RIGHT_TOTAL_LENGTH (tree
));
956 subtract
= interval_deletion_adjustment (tree
->right
,
959 tree
->total_length
-= subtract
;
962 /* Here -- this node. */
965 /* How much can we delete from this interval? */
966 int my_amount
= ((tree
->total_length
967 - RIGHT_TOTAL_LENGTH (tree
))
968 - relative_position
);
970 if (amount
> my_amount
)
973 tree
->total_length
-= amount
;
974 if (LENGTH (tree
) == 0)
975 delete_interval (tree
);
980 /* Never reach here. */
983 /* Effect the adjustments necessary to the interval tree of BUFFER to
984 correspond to the deletion of LENGTH characters from that buffer
985 text. The deletion is effected at position START (which is a
986 buffer position, i.e. origin 1). */
989 adjust_intervals_for_deletion (buffer
, start
, length
)
990 struct buffer
*buffer
;
993 register int left_to_delete
= length
;
994 register INTERVAL tree
= buffer
->intervals
;
995 register int deleted
;
997 if (NULL_INTERVAL_P (tree
))
1000 if (start
> BEG
+ TOTAL_LENGTH (tree
)
1001 || start
+ length
> BEG
+ TOTAL_LENGTH (tree
))
1004 if (length
== TOTAL_LENGTH (tree
))
1006 buffer
->intervals
= NULL_INTERVAL
;
1010 if (ONLY_INTERVAL_P (tree
))
1012 tree
->total_length
-= length
;
1016 if (start
> BEG
+ TOTAL_LENGTH (tree
))
1017 start
= BEG
+ TOTAL_LENGTH (tree
);
1018 while (left_to_delete
> 0)
1020 left_to_delete
-= interval_deletion_adjustment (tree
, start
- 1,
1022 tree
= buffer
->intervals
;
1023 if (left_to_delete
== tree
->total_length
)
1025 buffer
->intervals
= NULL_INTERVAL
;
1031 /* Make the adjustments necessary to the interval tree of BUFFER to
1032 represent an addition or deletion of LENGTH characters starting
1033 at position START. Addition or deletion is indicated by the sign
1037 offset_intervals (buffer
, start
, length
)
1038 struct buffer
*buffer
;
1041 if (NULL_INTERVAL_P (buffer
->intervals
) || length
== 0)
1045 adjust_intervals_for_insertion (buffer
->intervals
, start
, length
);
1047 adjust_intervals_for_deletion (buffer
, start
, -length
);
1050 /* Merge interval I with its lexicographic successor. The resulting
1051 interval is returned, and has the properties of the original
1052 successor. The properties of I are lost. I is removed from the
1056 The caller must verify that this is not the last (rightmost)
1060 merge_interval_right (i
)
1061 register INTERVAL i
;
1063 register int absorb
= LENGTH (i
);
1064 register INTERVAL successor
;
1066 /* Zero out this interval. */
1067 i
->total_length
-= absorb
;
1069 /* Find the succeeding interval. */
1070 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
1073 successor
= i
->right
;
1074 while (! NULL_LEFT_CHILD (successor
))
1076 successor
->total_length
+= absorb
;
1077 successor
= successor
->left
;
1080 successor
->total_length
+= absorb
;
1081 delete_interval (i
);
1086 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
1089 if (AM_LEFT_CHILD (successor
))
1091 successor
= successor
->parent
;
1092 delete_interval (i
);
1096 successor
= successor
->parent
;
1097 successor
->total_length
-= absorb
;
1100 /* This must be the rightmost or last interval and cannot
1101 be merged right. The caller should have known. */
1105 /* Merge interval I with its lexicographic predecessor. The resulting
1106 interval is returned, and has the properties of the original predecessor.
1107 The properties of I are lost. Interval node I is removed from the tree.
1110 The caller must verify that this is not the first (leftmost) interval. */
1113 merge_interval_left (i
)
1114 register INTERVAL i
;
1116 register int absorb
= LENGTH (i
);
1117 register INTERVAL predecessor
;
1119 /* Zero out this interval. */
1120 i
->total_length
-= absorb
;
1122 /* Find the preceding interval. */
1123 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
1124 adding ABSORB as we go. */
1126 predecessor
= i
->left
;
1127 while (! NULL_RIGHT_CHILD (predecessor
))
1129 predecessor
->total_length
+= absorb
;
1130 predecessor
= predecessor
->right
;
1133 predecessor
->total_length
+= absorb
;
1134 delete_interval (i
);
1139 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
1140 subtracting ABSORB. */
1142 if (AM_RIGHT_CHILD (predecessor
))
1144 predecessor
= predecessor
->parent
;
1145 delete_interval (i
);
1149 predecessor
= predecessor
->parent
;
1150 predecessor
->total_length
-= absorb
;
1153 /* This must be the leftmost or first interval and cannot
1154 be merged left. The caller should have known. */
1158 /* Make an exact copy of interval tree SOURCE which descends from
1159 PARENT. This is done by recursing through SOURCE, copying
1160 the current interval and its properties, and then adjusting
1161 the pointers of the copy. */
1164 reproduce_tree (source
, parent
)
1165 INTERVAL source
, parent
;
1167 register INTERVAL t
= make_interval ();
1169 bcopy (source
, t
, INTERVAL_SIZE
);
1170 copy_properties (source
, t
);
1172 if (! NULL_LEFT_CHILD (source
))
1173 t
->left
= reproduce_tree (source
->left
, t
);
1174 if (! NULL_RIGHT_CHILD (source
))
1175 t
->right
= reproduce_tree (source
->right
, t
);
1181 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
1183 /* Make a new interval of length LENGTH starting at START in the
1184 group of intervals INTERVALS, which is actually an interval tree.
1185 Returns the new interval.
1187 Generate an error if the new positions would overlap an existing
1191 make_new_interval (intervals
, start
, length
)
1197 slot
= find_interval (intervals
, start
);
1198 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1199 error ("Interval would overlap");
1201 if (start
== slot
->position
&& length
== LENGTH (slot
))
1204 if (slot
->position
== start
)
1206 /* New right node. */
1207 split_interval_right (slot
, length
);
1211 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1213 /* New left node. */
1214 split_interval_left (slot
, LENGTH (slot
) - length
);
1218 /* Convert interval SLOT into three intervals. */
1219 split_interval_left (slot
, start
- slot
->position
);
1220 split_interval_right (slot
, length
);
1225 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1226 LENGTH is the length of the text in SOURCE.
1228 This is used in insdel.c when inserting Lisp_Strings into the
1229 buffer. The text corresponding to SOURCE is already in the buffer
1230 when this is called. The intervals of new tree are a copy of those
1231 belonging to the string being inserted; intervals are never
1234 If the inserted text had no intervals associated, and we don't
1235 want to inherit the surrounding text's properties, this function
1236 simply returns -- offset_intervals should handle placing the
1237 text in the correct interval, depending on the sticky bits.
1239 If the inserted text had properties (intervals), then there are two
1240 cases -- either insertion happened in the middle of some interval,
1241 or between two intervals.
1243 If the text goes into the middle of an interval, then new
1244 intervals are created in the middle with only the properties of
1245 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1246 which case the new text has the union of its properties and those
1247 of the text into which it was inserted.
1249 If the text goes between two intervals, then if neither interval
1250 had its appropriate sticky property set (front_sticky, rear_sticky),
1251 the new text has only its properties. If one of the sticky properties
1252 is set, then the new text "sticks" to that region and its properties
1253 depend on merging as above. If both the preceding and succeeding
1254 intervals to the new text are "sticky", then the new text retains
1255 only its properties, as if neither sticky property were set. Perhaps
1256 we should consider merging all three sets of properties onto the new
1260 graft_intervals_into_buffer (source
, position
, length
, buffer
, inherit
)
1262 int position
, length
;
1263 struct buffer
*buffer
;
1266 register INTERVAL under
, over
, this, prev
;
1267 register INTERVAL tree
= buffer
->intervals
;
1270 /* If the new text has no properties, it becomes part of whatever
1271 interval it was inserted into. */
1272 if (NULL_INTERVAL_P (source
))
1277 XSET (buf
, Lisp_Buffer
, buffer
);
1278 Fset_text_properties (make_number (position
),
1279 make_number (position
+ length
),
1285 if (NULL_INTERVAL_P (tree
))
1287 /* The inserted text constitutes the whole buffer, so
1288 simply copy over the interval structure. */
1289 if ((BUF_Z (buffer
) - BUF_BEG (buffer
)) == TOTAL_LENGTH (source
))
1292 XSET (buf
, Lisp_Buffer
, buffer
);
1293 buffer
->intervals
= reproduce_tree (source
, buf
);
1294 /* Explicitly free the old tree here. */
1299 /* Create an interval tree in which to place a copy
1300 of the intervals of the inserted string. */
1303 XSET (buf
, Lisp_Buffer
, buffer
);
1304 tree
= create_root_interval (buf
);
1307 else if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1308 /* If the buffer contains only the new string, but
1309 there was already some interval tree there, then it may be
1310 some zero length intervals. Eventually, do something clever
1311 about inserting properly. For now, just waste the old intervals. */
1313 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1314 /* Explicitly free the old tree here. */
1318 /* Paranoia -- the text has already been added, so this buffer
1319 should be of non-zero length. */
1320 else if (TOTAL_LENGTH (tree
) == 0)
1323 this = under
= find_interval (tree
, position
);
1324 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1326 over
= find_interval (source
, 1);
1328 /* Here for insertion in the middle of an interval.
1329 Split off an equivalent interval to the right,
1330 then don't bother with it any more. */
1332 if (position
> under
->position
)
1334 INTERVAL end_unchanged
1335 = split_interval_left (this, position
- under
->position
);
1336 copy_properties (under
, end_unchanged
);
1337 under
->position
= position
;
1343 prev
= previous_interval (under
);
1344 if (prev
&& !END_NONSTICKY_P (prev
))
1348 /* Insertion is now at beginning of UNDER. */
1350 /* The inserted text "sticks" to the interval `under',
1351 which means it gets those properties.
1352 The properties of under are the result of
1353 adjust_intervals_for_insertion, so stickyness has
1354 already been taken care of. */
1356 while (! NULL_INTERVAL_P (over
))
1358 if (LENGTH (over
) + 1 < LENGTH (under
))
1360 this = split_interval_left (under
, LENGTH (over
));
1361 copy_properties (under
, this);
1365 copy_properties (over
, this);
1367 merge_properties (over
, this);
1369 copy_properties (over
, this);
1370 over
= next_interval (over
);
1373 buffer
->intervals
= balance_intervals (buffer
->intervals
);
1377 /* Get the value of property PROP from PLIST,
1378 which is the plist of an interval.
1379 We check for direct properties and for categories with property PROP. */
1382 textget (plist
, prop
)
1384 register Lisp_Object prop
;
1386 register Lisp_Object tail
, fallback
;
1389 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1391 register Lisp_Object tem
;
1394 return Fcar (Fcdr (tail
));
1395 if (EQ (tem
, Qcategory
))
1396 fallback
= Fget (Fcar (Fcdr (tail
)), prop
);
1402 /* Get the value of property PROP from PLIST,
1403 which is the plist of an interval.
1404 We check for direct properties only! */
1407 textget_direct (plist
, prop
)
1409 register Lisp_Object prop
;
1411 register Lisp_Object tail
;
1413 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1415 if (EQ (prop
, Fcar (tail
)))
1416 return Fcar (Fcdr (tail
));
1422 /* Set point in BUFFER to POSITION. If the target position is
1423 before an invisible character which is not displayed with a special glyph,
1424 move back to an ok place to display. */
1427 set_point (position
, buffer
)
1428 register int position
;
1429 register struct buffer
*buffer
;
1431 register INTERVAL to
, from
, toprev
, fromprev
, target
;
1433 register Lisp_Object obj
;
1434 int backwards
= (position
< BUF_PT (buffer
)) ? 1 : 0;
1435 int old_position
= buffer
->text
.pt
;
1437 if (position
== buffer
->text
.pt
)
1440 /* Check this now, before checking if the buffer has any intervals.
1441 That way, we can catch conditions which break this sanity check
1442 whether or not there are intervals in the buffer. */
1443 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1446 if (NULL_INTERVAL_P (buffer
->intervals
))
1448 buffer
->text
.pt
= position
;
1452 /* Set TO to the interval containing the char after POSITION,
1453 and TOPREV to the interval containing the char before POSITION.
1454 Either one may be null. They may be equal. */
1455 to
= find_interval (buffer
->intervals
, position
);
1456 if (position
== BUF_BEGV (buffer
))
1458 else if (to
->position
== position
)
1459 toprev
= previous_interval (to
);
1463 buffer_point
= (BUF_PT (buffer
) == BUF_ZV (buffer
)
1464 ? BUF_ZV (buffer
) - 1
1467 /* Set FROM to the interval containing the char after PT,
1468 and FROMPREV to the interval containing the char before PT.
1469 Either one may be null. They may be equal. */
1470 /* We could cache this and save time. */
1471 from
= find_interval (buffer
->intervals
, buffer_point
);
1472 if (buffer_point
== BUF_BEGV (buffer
))
1474 else if (from
->position
== BUF_PT (buffer
))
1475 fromprev
= previous_interval (from
);
1476 else if (buffer_point
!= BUF_PT (buffer
))
1477 fromprev
= from
, from
= 0;
1481 /* Moving within an interval. */
1482 if (to
== from
&& toprev
== fromprev
&& INTERVAL_VISIBLE_P (to
))
1484 buffer
->text
.pt
= position
;
1488 /* If the new position is before an invisible character
1489 that has an `invisible' property of value `hidden',
1490 move forward over all such. */
1491 while (! NULL_INTERVAL_P (to
)
1492 && EQ (textget (to
->plist
, Qinvisible
), Qhidden
)
1493 && ! DISPLAY_INVISIBLE_GLYPH (to
))
1496 to
= next_interval (to
);
1497 if (NULL_INTERVAL_P (to
))
1498 position
= BUF_ZV (buffer
);
1500 position
= to
->position
;
1503 buffer
->text
.pt
= position
;
1505 /* We run point-left and point-entered hooks here, iff the
1506 two intervals are not equivalent. These hooks take
1507 (old_point, new_point) as arguments. */
1508 if (NILP (Vinhibit_point_motion_hooks
)
1509 && (! intervals_equal (from
, to
)
1510 || ! intervals_equal (fromprev
, toprev
)))
1512 Lisp_Object leave_after
, leave_before
, enter_after
, enter_before
;
1515 leave_after
= textget (fromprev
->plist
, Qpoint_left
);
1519 leave_before
= textget (from
->plist
, Qpoint_left
);
1521 leave_before
= Qnil
;
1524 enter_after
= textget (toprev
->plist
, Qpoint_entered
);
1528 enter_before
= textget (to
->plist
, Qpoint_entered
);
1530 enter_before
= Qnil
;
1532 if (! EQ (leave_before
, enter_before
) && !NILP (leave_before
))
1533 call2 (leave_before
, old_position
, position
);
1534 if (! EQ (leave_after
, enter_after
) && !NILP (leave_after
))
1535 call2 (leave_after
, old_position
, position
);
1537 if (! EQ (enter_before
, leave_before
) && !NILP (enter_before
))
1538 call2 (enter_before
, old_position
, position
);
1539 if (! EQ (enter_after
, leave_after
) && !NILP (enter_after
))
1540 call2 (enter_after
, old_position
, position
);
1544 /* Set point temporarily, without checking any text properties. */
1547 temp_set_point (position
, buffer
)
1549 struct buffer
*buffer
;
1551 buffer
->text
.pt
= position
;
1554 /* Return the proper local map for position POSITION in BUFFER.
1555 Use the map specified by the local-map property, if any.
1556 Otherwise, use BUFFER's local map. */
1559 get_local_map (position
, buffer
)
1560 register int position
;
1561 register struct buffer
*buffer
;
1563 register INTERVAL interval
;
1564 Lisp_Object prop
, tem
;
1566 if (NULL_INTERVAL_P (buffer
->intervals
))
1567 return current_buffer
->keymap
;
1569 /* Perhaps we should just change `position' to the limit. */
1570 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1573 interval
= find_interval (buffer
->intervals
, position
);
1574 prop
= textget (interval
->plist
, Qlocal_map
);
1576 return current_buffer
->keymap
;
1578 /* Use the local map only if it is valid. */
1579 tem
= Fkeymapp (prop
);
1583 return current_buffer
->keymap
;
1586 /* Call the modification hook functions in LIST, each with START and END. */
1589 call_mod_hooks (list
, start
, end
)
1590 Lisp_Object list
, start
, end
;
1592 struct gcpro gcpro1
;
1594 while (!NILP (list
))
1596 call2 (Fcar (list
), start
, end
);
1602 /* Check for read-only intervals and signal an error if we find one.
1603 Then check for any modification hooks in the range START up to
1604 (but not including) TO. Create a list of all these hooks in
1605 lexicographic order, eliminating consecutive extra copies of the
1606 same hook. Then call those hooks in order, with START and END - 1
1610 verify_interval_modification (buf
, start
, end
)
1614 register INTERVAL intervals
= buf
->intervals
;
1615 register INTERVAL i
, prev
;
1617 register Lisp_Object prev_mod_hooks
;
1618 Lisp_Object mod_hooks
;
1619 struct gcpro gcpro1
;
1622 prev_mod_hooks
= Qnil
;
1625 if (NULL_INTERVAL_P (intervals
))
1635 /* For an insert operation, check the two chars around the position. */
1639 Lisp_Object before
, after
;
1641 /* Set I to the interval containing the char after START,
1642 and PREV to the interval containing the char before START.
1643 Either one may be null. They may be equal. */
1644 i
= find_interval (intervals
, start
);
1646 if (start
== BUF_BEGV (buf
))
1648 else if (i
->position
== start
)
1649 prev
= previous_interval (i
);
1650 else if (i
->position
< start
)
1652 if (start
== BUF_ZV (buf
))
1655 /* If Vinhibit_read_only is set and is not a list, we can
1656 skip the read_only checks. */
1657 if (NILP (Vinhibit_read_only
) || CONSP (Vinhibit_read_only
))
1659 /* If I and PREV differ we need to check for the read-only
1660 property together with its stickyness. If either I or
1661 PREV are 0, this check is all we need.
1662 We have to take special care, since read-only may be
1663 indirectly defined via the category property. */
1666 if (! NULL_INTERVAL_P (i
))
1668 after
= textget (i
->plist
, Qread_only
);
1670 /* If interval I is read-only and read-only is
1671 front-sticky, inhibit insertion.
1672 Check for read-only as well as category. */
1674 && NILP (Fmemq (after
, Vinhibit_read_only
))
1675 && (! NILP (Fmemq (Qread_only
,
1676 textget (i
->plist
, Qfront_sticky
)))
1677 || (NILP (textget_direct (i
->plist
, Qread_only
))
1678 && ! NILP (Fmemq (Qcategory
,
1681 error ("Attempt to insert within read-only text");
1685 if (! NULL_INTERVAL_P (prev
))
1687 before
= textget (prev
->plist
, Qread_only
);
1689 /* If interval PREV is read-only and read-only isn't
1690 rear-nonsticky, inhibit insertion.
1691 Check for read-only as well as category. */
1693 && NILP (Fmemq (before
, Vinhibit_read_only
))
1694 && NILP (Fmemq (Qread_only
,
1695 textget (prev
->plist
, Qrear_nonsticky
)))
1696 && (! NILP (textget_direct (prev
->plist
,Qread_only
))
1697 || NILP (Fmemq (Qcategory
,
1698 textget (prev
->plist
,
1699 Qrear_nonsticky
)))))
1700 error ("Attempt to insert within read-only text");
1705 else if (! NULL_INTERVAL_P (i
))
1706 before
= after
= textget (i
->plist
, Qread_only
);
1707 if (! NULL_INTERVAL_P (i
) && ! NULL_INTERVAL_P (prev
))
1709 /* If I and PREV differ, neither of them has a sticky
1710 read-only property. It only remains to check, whether
1711 they have a common read-only property. */
1712 if (! NILP (before
) && EQ (before
, after
))
1713 error ("Attempt to insert within read-only text");
1717 /* Run both insert hooks (just once if they're the same). */
1718 if (!NULL_INTERVAL_P (prev
))
1719 prev_mod_hooks
= textget (prev
->plist
, Qinsert_behind_hooks
);
1720 if (!NULL_INTERVAL_P (i
))
1721 mod_hooks
= textget (i
->plist
, Qinsert_in_front_hooks
);
1723 if (! NILP (prev_mod_hooks
))
1724 call_mod_hooks (prev_mod_hooks
, make_number (start
),
1727 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1728 call_mod_hooks (mod_hooks
, make_number (start
), make_number (end
));
1732 /* Loop over intervals on or next to START...END,
1733 collecting their hooks. */
1735 i
= find_interval (intervals
, start
);
1738 if (! INTERVAL_WRITABLE_P (i
))
1739 error ("Attempt to modify read-only text");
1741 mod_hooks
= textget (i
->plist
, Qmodification_hooks
);
1742 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1744 hooks
= Fcons (mod_hooks
, hooks
);
1745 prev_mod_hooks
= mod_hooks
;
1748 i
= next_interval (i
);
1750 /* Keep going thru the interval containing the char before END. */
1751 while (! NULL_INTERVAL_P (i
) && i
->position
< end
);
1754 hooks
= Fnreverse (hooks
);
1755 while (! EQ (hooks
, Qnil
))
1757 call_mod_hooks (Fcar (hooks
), make_number (start
),
1759 hooks
= Fcdr (hooks
);
1765 /* Balance an interval node if the amount of text in its left and right
1766 subtrees differs by more than the percentage specified by
1767 `interval-balance-threshold'. */
1770 balance_an_interval (i
)
1773 register int total_children_size
= (LEFT_TOTAL_LENGTH (i
)
1774 + RIGHT_TOTAL_LENGTH (i
));
1775 register int threshold
= (XFASTINT (interval_balance_threshold
)
1776 * (total_children_size
/ 100));
1778 /* Balance within each side. */
1779 balance_intervals (i
->left
);
1780 balance_intervals (i
->right
);
1782 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1783 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1785 i
= rotate_right (i
);
1786 /* If that made it unbalanced the other way, take it back. */
1787 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1788 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1789 return rotate_left (i
);
1793 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1794 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1796 i
= rotate_left (i
);
1797 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1798 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1799 return rotate_right (i
);
1806 /* Balance the interval tree TREE. Balancing is by weight
1807 (the amount of text). */
1810 balance_intervals (tree
)
1811 register INTERVAL tree
;
1813 register INTERVAL new_tree
;
1815 if (NULL_INTERVAL_P (tree
))
1816 return NULL_INTERVAL
;
1822 new_tree
= balance_an_interval (new_tree
);
1824 while (new_tree
!= tree
);
1829 /* Produce an interval tree reflecting the intervals in
1830 TREE from START to START + LENGTH. */
1833 copy_intervals (tree
, start
, length
)
1837 register INTERVAL i
, new, t
;
1838 register int got
, prevlen
;
1840 if (NULL_INTERVAL_P (tree
) || length
<= 0)
1841 return NULL_INTERVAL
;
1843 i
= find_interval (tree
, start
);
1844 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
1847 /* If there is only one interval and it's the default, return nil. */
1848 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
1849 && DEFAULT_INTERVAL_P (i
))
1850 return NULL_INTERVAL
;
1852 new = make_interval ();
1854 got
= (LENGTH (i
) - (start
- i
->position
));
1855 new->total_length
= length
;
1856 copy_properties (i
, new);
1860 while (got
< length
)
1862 i
= next_interval (i
);
1863 t
= split_interval_right (t
, prevlen
);
1864 copy_properties (i
, t
);
1865 prevlen
= LENGTH (i
);
1869 return balance_intervals (new);
1872 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1875 copy_intervals_to_string (string
, buffer
, position
, length
)
1876 Lisp_Object string
, buffer
;
1877 int position
, length
;
1879 INTERVAL interval_copy
= copy_intervals (XBUFFER (buffer
)->intervals
,
1881 if (NULL_INTERVAL_P (interval_copy
))
1884 interval_copy
->parent
= (INTERVAL
) string
;
1885 XSTRING (string
)->intervals
= interval_copy
;
1888 #endif /* USE_TEXT_PROPERTIES */