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 /* Utility functions for intervals. */
56 /* Create the root interval of some object, a buffer or string. */
59 create_root_interval (parent
)
64 CHECK_IMPURE (parent
);
66 new = make_interval ();
68 if (XTYPE (parent
) == Lisp_Buffer
)
70 new->total_length
= (BUF_Z (XBUFFER (parent
))
71 - BUF_BEG (XBUFFER (parent
)));
72 XBUFFER (parent
)->intervals
= new;
74 else if (XTYPE (parent
) == Lisp_String
)
76 new->total_length
= XSTRING (parent
)->size
;
77 XSTRING (parent
)->intervals
= new;
80 new->parent
= (INTERVAL
) parent
;
86 /* Make the interval TARGET have exactly the properties of SOURCE */
89 copy_properties (source
, target
)
90 register INTERVAL source
, target
;
92 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
95 COPY_INTERVAL_CACHE (source
, target
);
96 target
->plist
= Fcopy_sequence (source
->plist
);
99 /* Merge the properties of interval SOURCE into the properties
100 of interval TARGET. That is to say, each property in SOURCE
101 is added to TARGET if TARGET has no such property as yet. */
104 merge_properties (source
, target
)
105 register INTERVAL source
, target
;
107 register Lisp_Object o
, sym
, val
;
109 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
112 MERGE_INTERVAL_CACHE (source
, target
);
115 while (! EQ (o
, Qnil
))
118 val
= Fmemq (sym
, target
->plist
);
124 target
->plist
= Fcons (sym
, Fcons (val
, target
->plist
));
132 /* Return 1 if the two intervals have the same properties,
136 intervals_equal (i0
, i1
)
139 register Lisp_Object i0_cdr
, i0_sym
, i1_val
;
142 if (DEFAULT_INTERVAL_P (i0
) && DEFAULT_INTERVAL_P (i1
))
145 if (DEFAULT_INTERVAL_P (i0
) || DEFAULT_INTERVAL_P (i1
))
148 i1_len
= XFASTINT (Flength (i1
->plist
));
149 if (i1_len
& 0x1) /* Paranoia -- plists are always even */
153 while (!NILP (i0_cdr
))
155 /* Lengths of the two plists were unequal. */
159 i0_sym
= Fcar (i0_cdr
);
160 i1_val
= Fmemq (i0_sym
, i1
->plist
);
162 /* i0 has something i1 doesn't. */
163 if (EQ (i1_val
, Qnil
))
166 /* i0 and i1 both have sym, but it has different values in each. */
167 i0_cdr
= Fcdr (i0_cdr
);
168 if (! EQ (Fcar (Fcdr (i1_val
)), Fcar (i0_cdr
)))
171 i0_cdr
= Fcdr (i0_cdr
);
175 /* Lengths of the two plists were unequal. */
184 static int zero_length
;
186 /* Traverse an interval tree TREE, performing FUNCTION on each node.
187 Pass FUNCTION two args: an interval, and ARG. */
190 traverse_intervals (tree
, position
, depth
, function
, arg
)
193 void (* function
) ();
196 if (NULL_INTERVAL_P (tree
))
199 traverse_intervals (tree
->left
, position
, depth
+ 1, function
, arg
);
200 position
+= LEFT_TOTAL_LENGTH (tree
);
201 tree
->position
= position
;
202 (*function
) (tree
, arg
);
203 position
+= LENGTH (tree
);
204 traverse_intervals (tree
->right
, position
, depth
+ 1, function
, arg
);
208 /* These functions are temporary, for debugging purposes only. */
210 INTERVAL search_interval
, found_interval
;
213 check_for_interval (i
)
216 if (i
== search_interval
)
224 search_for_interval (i
, tree
)
225 register INTERVAL i
, tree
;
229 found_interval
= NULL_INTERVAL
;
230 traverse_intervals (tree
, 1, 0, &check_for_interval
, Qnil
);
231 return found_interval
;
235 inc_interval_count (i
)
252 traverse_intervals (i
, 1, 0, &inc_interval_count
, Qnil
);
258 root_interval (interval
)
261 register INTERVAL i
= interval
;
263 while (! ROOT_INTERVAL_P (i
))
270 /* Assuming that a left child exists, perform the following operation:
280 rotate_right (interval
)
284 INTERVAL B
= interval
->left
;
285 int len
= LENGTH (interval
);
287 /* Deal with any Parent of A; make it point to B. */
288 if (! ROOT_INTERVAL_P (interval
))
289 if (AM_LEFT_CHILD (interval
))
290 interval
->parent
->left
= interval
->left
;
292 interval
->parent
->right
= interval
->left
;
293 interval
->left
->parent
= interval
->parent
;
295 /* B gets the same length as A, since it get A's position in the tree. */
296 interval
->left
->total_length
= interval
->total_length
;
298 /* B becomes the parent of A. */
299 i
= interval
->left
->right
;
300 interval
->left
->right
= interval
;
301 interval
->parent
= interval
->left
;
303 /* A gets c as left child. */
305 if (! NULL_INTERVAL_P (i
))
306 i
->parent
= interval
;
307 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
308 + RIGHT_TOTAL_LENGTH (interval
));
313 /* Assuming that a right child exists, perform the following operation:
323 rotate_left (interval
)
327 INTERVAL B
= interval
->right
;
328 int len
= LENGTH (interval
);
330 /* Deal with the parent of A. */
331 if (! ROOT_INTERVAL_P (interval
))
332 if (AM_LEFT_CHILD (interval
))
333 interval
->parent
->left
= interval
->right
;
335 interval
->parent
->right
= interval
->right
;
336 interval
->right
->parent
= interval
->parent
;
338 /* B must have the same total length of A. */
339 interval
->right
->total_length
= interval
->total_length
;
341 /* Make B the parent of A */
342 i
= interval
->right
->left
;
343 interval
->right
->left
= interval
;
344 interval
->parent
= interval
->right
;
346 /* Make A point to c */
348 if (! NULL_INTERVAL_P (i
))
349 i
->parent
= interval
;
350 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
351 + RIGHT_TOTAL_LENGTH (interval
));
356 /* Split INTERVAL into two pieces, starting the second piece at
357 character position OFFSET (counting from 0), relative to INTERVAL.
358 INTERVAL becomes the left-hand piece, and the right-hand piece
359 (second, lexicographically) is returned.
361 The size and position fields of the two intervals are set based upon
362 those of the original interval. The property list of the new interval
363 is reset, thus it is up to the caller to do the right thing with the
366 Note that this does not change the position of INTERVAL; if it is a root,
367 it is still a root after this operation. */
370 split_interval_right (interval
, offset
)
374 INTERVAL
new = make_interval ();
375 int position
= interval
->position
;
376 int new_length
= LENGTH (interval
) - offset
;
378 new->position
= position
+ offset
;
379 new->parent
= interval
;
381 if (LEAF_INTERVAL_P (interval
) || NULL_RIGHT_CHILD (interval
))
383 interval
->right
= new;
384 new->total_length
= new_length
;
389 /* Insert the new node between INTERVAL and its right child. */
390 new->right
= interval
->right
;
391 interval
->right
->parent
= new;
392 interval
->right
= new;
394 new->total_length
= new_length
+ new->right
->total_length
;
399 /* Split INTERVAL into two pieces, starting the second piece at
400 character position OFFSET (counting from 0), relative to INTERVAL.
401 INTERVAL becomes the right-hand piece, and the left-hand piece
402 (first, lexicographically) is returned.
404 The size and position fields of the two intervals are set based upon
405 those of the original interval. The property list of the new interval
406 is reset, thus it is up to the caller to do the right thing with the
409 Note that this does not change the position of INTERVAL; if it is a root,
410 it is still a root after this operation. */
413 split_interval_left (interval
, offset
)
417 INTERVAL
new = make_interval ();
418 int position
= interval
->position
;
419 int new_length
= offset
;
421 new->position
= interval
->position
;
422 interval
->position
= interval
->position
+ offset
;
423 new->parent
= interval
;
425 if (NULL_LEFT_CHILD (interval
))
427 interval
->left
= new;
428 new->total_length
= new_length
;
433 /* Insert the new node between INTERVAL and its left child. */
434 new->left
= interval
->left
;
435 new->left
->parent
= new;
436 interval
->left
= new;
437 new->total_length
= new_length
+ LEFT_TOTAL_LENGTH (new);
442 /* Find the interval containing text position POSITION in the text
443 represented by the interval tree TREE. POSITION is a buffer
444 position; the earliest position is 1. If POSITION is at the end of
445 the buffer, return the interval containing the last character.
447 The `position' field, which is a cache of an interval's position,
448 is updated in the interval found. Other functions (e.g., next_interval)
449 will update this cache based on the result of find_interval. */
452 find_interval (tree
, position
)
453 register INTERVAL tree
;
454 register int position
;
456 /* The distance from the left edge of the subtree at TREE
458 register int relative_position
= position
- BEG
;
460 if (NULL_INTERVAL_P (tree
))
461 return NULL_INTERVAL
;
463 if (relative_position
> TOTAL_LENGTH (tree
))
464 abort (); /* Paranoia */
468 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
472 else if (! NULL_RIGHT_CHILD (tree
)
473 && relative_position
>= (TOTAL_LENGTH (tree
)
474 - RIGHT_TOTAL_LENGTH (tree
)))
476 relative_position
-= (TOTAL_LENGTH (tree
)
477 - RIGHT_TOTAL_LENGTH (tree
));
483 (position
- relative_position
/* the left edge of *tree */
484 + LEFT_TOTAL_LENGTH (tree
)); /* the left edge of this interval */
491 /* Find the succeeding interval (lexicographically) to INTERVAL.
492 Sets the `position' field based on that of INTERVAL (see
496 next_interval (interval
)
497 register INTERVAL interval
;
499 register INTERVAL i
= interval
;
500 register int next_position
;
502 if (NULL_INTERVAL_P (i
))
503 return NULL_INTERVAL
;
504 next_position
= interval
->position
+ LENGTH (interval
);
506 if (! NULL_RIGHT_CHILD (i
))
509 while (! NULL_LEFT_CHILD (i
))
512 i
->position
= next_position
;
516 while (! NULL_PARENT (i
))
518 if (AM_LEFT_CHILD (i
))
521 i
->position
= next_position
;
528 return NULL_INTERVAL
;
531 /* Find the preceding interval (lexicographically) to INTERVAL.
532 Sets the `position' field based on that of INTERVAL (see
536 previous_interval (interval
)
537 register INTERVAL interval
;
540 register position_of_previous
;
542 if (NULL_INTERVAL_P (interval
))
543 return NULL_INTERVAL
;
545 if (! NULL_LEFT_CHILD (interval
))
548 while (! NULL_RIGHT_CHILD (i
))
551 i
->position
= interval
->position
- LENGTH (i
);
556 while (! NULL_PARENT (i
))
558 if (AM_RIGHT_CHILD (i
))
562 i
->position
= interval
->position
- LENGTH (i
);
568 return NULL_INTERVAL
;
572 /* Traverse a path down the interval tree TREE to the interval
573 containing POSITION, adjusting all nodes on the path for
574 an addition of LENGTH characters. Insertion between two intervals
575 (i.e., point == i->position, where i is second interval) means
576 text goes into second interval.
578 Modifications are needed to handle the hungry bits -- after simply
579 finding the interval at position (don't add length going down),
580 if it's the beginning of the interval, get the previous interval
581 and check the hugry bits of both. Then add the length going back up
585 adjust_intervals_for_insertion (tree
, position
, length
)
587 int position
, length
;
589 register int relative_position
;
590 register INTERVAL
this;
592 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
595 /* If inserting at point-max of a buffer, that position
596 will be out of range */
597 if (position
> TOTAL_LENGTH (tree
))
598 position
= TOTAL_LENGTH (tree
);
599 relative_position
= position
;
604 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
606 this->total_length
+= length
;
609 else if (relative_position
> (TOTAL_LENGTH (this)
610 - RIGHT_TOTAL_LENGTH (this)))
612 relative_position
-= (TOTAL_LENGTH (this)
613 - RIGHT_TOTAL_LENGTH (this));
614 this->total_length
+= length
;
619 /* If we are to use zero-length intervals as buffer pointers,
620 then this code will have to change. */
621 this->total_length
+= length
;
622 this->position
= LEFT_TOTAL_LENGTH (this)
623 + position
- relative_position
+ 1;
630 /* Effect an adjustment corresponding to the addition of LENGTH characters
631 of text. Do this by finding the interval containing POSITION in the
632 interval tree TREE, and then adjusting all of it's ancestors by adding
635 If POSITION is the first character of an interval, meaning that point
636 is actually between the two intervals, make the new text belong to
637 the interval which is "sticky".
639 If both intervals are "sticky", then make them belong to the left-most
640 interval. Another possibility would be to create a new interval for
641 this text, and make it have the merged properties of both ends. */
644 adjust_intervals_for_insertion (tree
, position
, length
)
646 int position
, length
;
649 register INTERVAL temp
;
652 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
655 /* If inserting at point-max of a buffer, that position will be out
656 of range. Remember that buffer positions are 1-based. */
657 if (position
>= BEG
+ TOTAL_LENGTH (tree
)){
658 position
= BEG
+ TOTAL_LENGTH (tree
);
662 i
= find_interval (tree
, position
);
664 /* If in middle of an interval which is not sticky either way,
665 we must not just give its properties to the insertion.
666 So split this interval at the insertion point. */
667 if (! (position
== i
->position
|| eobp
)
668 && END_NONSTICKY_P (i
)
669 && ! FRONT_STICKY_P (i
))
671 temp
= split_interval_right (i
, position
- i
->position
);
672 copy_properties (i
, temp
);
676 /* If we are positioned between intervals, check the stickiness of
677 both of them. We have to do this too, if we are at BEG or Z. */
678 if (position
== i
->position
|| eobp
)
680 register INTERVAL prev
;
690 prev
= previous_interval (i
);
692 /* Even if we are positioned between intervals, we default
693 to the left one if it exists. We extend it now and split
694 off a part later, if stickyness demands it. */
695 for (temp
= prev
? prev
: i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
696 temp
->total_length
+= length
;
698 /* If at least one interval has sticky properties,
699 we check the stickyness property by property. */
700 if (END_NONSTICKY_P (prev
) || FRONT_STICKY_P (i
))
702 Lisp_Object pleft
= NULL_INTERVAL_P (prev
) ? Qnil
: prev
->plist
;
703 Lisp_Object pright
= NULL_INTERVAL_P (i
) ? Qnil
: i
->plist
;
704 struct interval newi
;
706 newi
.plist
= merge_properties_sticky (pleft
, pright
);
708 if(! prev
) /* i.e. position == BEG */
710 if (! intervals_equal (i
, &newi
))
712 i
= split_interval_left (i
, length
);
713 i
->plist
= newi
.plist
;
716 else if (! intervals_equal (prev
, &newi
))
718 prev
= split_interval_right (prev
,
719 position
- prev
->position
);
720 prev
->plist
= newi
.plist
;
721 if (! NULL_INTERVAL_P (i
)
722 && intervals_equal (prev
, i
))
723 merge_interval_right (prev
);
726 /* We will need to update the cache here later. */
728 else if (! prev
&& ! NILP (i
->plist
))
730 /* Just split off a new interval at the left.
731 Since I wasn't front-sticky, the empty plist is ok. */
732 i
= split_interval_left (i
, length
);
736 /* Otherwise just extend the interval. */
739 for (temp
= i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
740 temp
->total_length
+= length
;
747 merge_properties_sticky (pleft
, pright
)
748 Lisp_Object pleft
, pright
;
750 register Lisp_Object props
= Qnil
, front
= Qnil
, rear
= Qnil
;
752 Lisp_Object lfront
= textget (pleft
, Qfront_sticky
);
753 Lisp_Object lrear
= textget (pleft
, Qrear_nonsticky
);
754 Lisp_Object rfront
= textget (pright
, Qfront_sticky
);
755 Lisp_Object rrear
= textget (pright
, Qrear_nonsticky
);
757 register Lisp_Object tail1
, tail2
, sym
;
759 /* Go through each element of PLEFT. */
760 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
764 /* Sticky properties get special treatment. */
765 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
768 if (CONSP (lrear
) ? NILP (Fmemq (sym
, lrear
)) : NILP (lrear
))
770 /* rear-sticky is dominant, we needn't search in PRIGHT. */
772 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail1
)), props
));
773 if ((CONSP (lfront
) || NILP (lfront
))
774 && ! NILP (Fmemq (sym
, lfront
)))
775 front
= Fcons (sym
, front
);
779 /* Go through PRIGHT, looking for sym. */
780 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
781 if (EQ (sym
, Fcar (tail2
)))
785 ? ! NILP (Fmemq (sym
, rfront
)) : ! NILP (rfront
))
787 /* Nonsticky at the left and sticky at the right,
788 so take the right one. */
789 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
790 front
= Fcons (sym
, front
);
791 if ((CONSP (rrear
) || NILP (rrear
))
792 && ! NILP (Fmemq (sym
, rrear
)))
793 rear
= Fcons (sym
, rear
);
799 /* Now let's see what to keep from PRIGHT. */
800 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
804 /* Sticky properties get special treatment. */
805 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
808 /* If it ain't sticky, we don't take it. */
810 ? NILP (Fmemq (sym
, rfront
)) : NILP (rfront
))
813 /* If sym is in PLEFT we already got it. */
814 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
815 if (EQ (sym
, Fcar (tail1
)))
820 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
821 front
= Fcons (sym
, front
);
822 if ((CONSP (rrear
) || NILP (rrear
))
823 && ! NILP (Fmemq (sym
, rrear
)))
824 rear
= Fcons (sym
, rear
);
828 props
= Fcons (Qfront_sticky
, Fcons (front
, props
));
830 props
= Fcons (Qrear_nonsticky
, Fcons (rear
, props
));
836 /* Delete an node I from its interval tree by merging its subtrees
837 into one subtree which is then returned. Caller is responsible for
838 storing the resulting subtree into its parent. */
844 register INTERVAL migrate
, this;
845 register int migrate_amt
;
847 if (NULL_INTERVAL_P (i
->left
))
849 if (NULL_INTERVAL_P (i
->right
))
853 migrate_amt
= i
->left
->total_length
;
855 this->total_length
+= migrate_amt
;
856 while (! NULL_INTERVAL_P (this->left
))
859 this->total_length
+= migrate_amt
;
861 this->left
= migrate
;
862 migrate
->parent
= this;
867 /* Delete interval I from its tree by calling `delete_node'
868 and properly connecting the resultant subtree.
870 I is presumed to be empty; that is, no adjustments are made
871 for the length of I. */
877 register INTERVAL parent
;
878 int amt
= LENGTH (i
);
880 if (amt
> 0) /* Only used on zero-length intervals now. */
883 if (ROOT_INTERVAL_P (i
))
885 Lisp_Object owner
= (Lisp_Object
) i
->parent
;
886 parent
= delete_node (i
);
887 if (! NULL_INTERVAL_P (parent
))
888 parent
->parent
= (INTERVAL
) owner
;
890 if (XTYPE (owner
) == Lisp_Buffer
)
891 XBUFFER (owner
)->intervals
= parent
;
892 else if (XTYPE (owner
) == Lisp_String
)
893 XSTRING (owner
)->intervals
= parent
;
901 if (AM_LEFT_CHILD (i
))
903 parent
->left
= delete_node (i
);
904 if (! NULL_INTERVAL_P (parent
->left
))
905 parent
->left
->parent
= parent
;
909 parent
->right
= delete_node (i
);
910 if (! NULL_INTERVAL_P (parent
->right
))
911 parent
->right
->parent
= parent
;
915 /* Find the interval in TREE corresponding to the relative position
916 FROM and delete as much as possible of AMOUNT from that interval.
917 Return the amount actually deleted, and if the interval was
918 zeroed-out, delete that interval node from the tree.
920 Note that FROM is actually origin zero, aka relative to the
921 leftmost edge of tree. This is appropriate since we call ourselves
922 recursively on subtrees.
924 Do this by recursing down TREE to the interval in question, and
925 deleting the appropriate amount of text. */
928 interval_deletion_adjustment (tree
, from
, amount
)
929 register INTERVAL tree
;
930 register int from
, amount
;
932 register int relative_position
= from
;
934 if (NULL_INTERVAL_P (tree
))
938 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
940 int subtract
= interval_deletion_adjustment (tree
->left
,
943 tree
->total_length
-= subtract
;
947 else if (relative_position
>= (TOTAL_LENGTH (tree
)
948 - RIGHT_TOTAL_LENGTH (tree
)))
952 relative_position
-= (tree
->total_length
953 - RIGHT_TOTAL_LENGTH (tree
));
954 subtract
= interval_deletion_adjustment (tree
->right
,
957 tree
->total_length
-= subtract
;
960 /* Here -- this node. */
963 /* How much can we delete from this interval? */
964 int my_amount
= ((tree
->total_length
965 - RIGHT_TOTAL_LENGTH (tree
))
966 - relative_position
);
968 if (amount
> my_amount
)
971 tree
->total_length
-= amount
;
972 if (LENGTH (tree
) == 0)
973 delete_interval (tree
);
978 /* Never reach here. */
981 /* Effect the adjustments necessary to the interval tree of BUFFER to
982 correspond to the deletion of LENGTH characters from that buffer
983 text. The deletion is effected at position START (which is a
984 buffer position, i.e. origin 1). */
987 adjust_intervals_for_deletion (buffer
, start
, length
)
988 struct buffer
*buffer
;
991 register int left_to_delete
= length
;
992 register INTERVAL tree
= buffer
->intervals
;
993 register int deleted
;
995 if (NULL_INTERVAL_P (tree
))
998 if (start
> BEG
+ TOTAL_LENGTH (tree
)
999 || start
+ length
> BEG
+ TOTAL_LENGTH (tree
))
1002 if (length
== TOTAL_LENGTH (tree
))
1004 buffer
->intervals
= NULL_INTERVAL
;
1008 if (ONLY_INTERVAL_P (tree
))
1010 tree
->total_length
-= length
;
1014 if (start
> BEG
+ TOTAL_LENGTH (tree
))
1015 start
= BEG
+ TOTAL_LENGTH (tree
);
1016 while (left_to_delete
> 0)
1018 left_to_delete
-= interval_deletion_adjustment (tree
, start
- 1,
1020 tree
= buffer
->intervals
;
1021 if (left_to_delete
== tree
->total_length
)
1023 buffer
->intervals
= NULL_INTERVAL
;
1029 /* Make the adjustments necessary to the interval tree of BUFFER to
1030 represent an addition or deletion of LENGTH characters starting
1031 at position START. Addition or deletion is indicated by the sign
1035 offset_intervals (buffer
, start
, length
)
1036 struct buffer
*buffer
;
1039 if (NULL_INTERVAL_P (buffer
->intervals
) || length
== 0)
1043 adjust_intervals_for_insertion (buffer
->intervals
, start
, length
);
1045 adjust_intervals_for_deletion (buffer
, start
, -length
);
1048 /* Merge interval I with its lexicographic successor. The resulting
1049 interval is returned, and has the properties of the original
1050 successor. The properties of I are lost. I is removed from the
1054 The caller must verify that this is not the last (rightmost)
1058 merge_interval_right (i
)
1059 register INTERVAL i
;
1061 register int absorb
= LENGTH (i
);
1062 register INTERVAL successor
;
1064 /* Zero out this interval. */
1065 i
->total_length
-= absorb
;
1067 /* Find the succeeding interval. */
1068 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
1071 successor
= i
->right
;
1072 while (! NULL_LEFT_CHILD (successor
))
1074 successor
->total_length
+= absorb
;
1075 successor
= successor
->left
;
1078 successor
->total_length
+= absorb
;
1079 delete_interval (i
);
1084 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
1087 if (AM_LEFT_CHILD (successor
))
1089 successor
= successor
->parent
;
1090 delete_interval (i
);
1094 successor
= successor
->parent
;
1095 successor
->total_length
-= absorb
;
1098 /* This must be the rightmost or last interval and cannot
1099 be merged right. The caller should have known. */
1103 /* Merge interval I with its lexicographic predecessor. The resulting
1104 interval is returned, and has the properties of the original predecessor.
1105 The properties of I are lost. Interval node I is removed from the tree.
1108 The caller must verify that this is not the first (leftmost) interval. */
1111 merge_interval_left (i
)
1112 register INTERVAL i
;
1114 register int absorb
= LENGTH (i
);
1115 register INTERVAL predecessor
;
1117 /* Zero out this interval. */
1118 i
->total_length
-= absorb
;
1120 /* Find the preceding interval. */
1121 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
1122 adding ABSORB as we go. */
1124 predecessor
= i
->left
;
1125 while (! NULL_RIGHT_CHILD (predecessor
))
1127 predecessor
->total_length
+= absorb
;
1128 predecessor
= predecessor
->right
;
1131 predecessor
->total_length
+= absorb
;
1132 delete_interval (i
);
1137 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
1138 subtracting ABSORB. */
1140 if (AM_RIGHT_CHILD (predecessor
))
1142 predecessor
= predecessor
->parent
;
1143 delete_interval (i
);
1147 predecessor
= predecessor
->parent
;
1148 predecessor
->total_length
-= absorb
;
1151 /* This must be the leftmost or first interval and cannot
1152 be merged left. The caller should have known. */
1156 /* Make an exact copy of interval tree SOURCE which descends from
1157 PARENT. This is done by recursing through SOURCE, copying
1158 the current interval and its properties, and then adjusting
1159 the pointers of the copy. */
1162 reproduce_tree (source
, parent
)
1163 INTERVAL source
, parent
;
1165 register INTERVAL t
= make_interval ();
1167 bcopy (source
, t
, INTERVAL_SIZE
);
1168 copy_properties (source
, t
);
1170 if (! NULL_LEFT_CHILD (source
))
1171 t
->left
= reproduce_tree (source
->left
, t
);
1172 if (! NULL_RIGHT_CHILD (source
))
1173 t
->right
= reproduce_tree (source
->right
, t
);
1179 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
1181 /* Make a new interval of length LENGTH starting at START in the
1182 group of intervals INTERVALS, which is actually an interval tree.
1183 Returns the new interval.
1185 Generate an error if the new positions would overlap an existing
1189 make_new_interval (intervals
, start
, length
)
1195 slot
= find_interval (intervals
, start
);
1196 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1197 error ("Interval would overlap");
1199 if (start
== slot
->position
&& length
== LENGTH (slot
))
1202 if (slot
->position
== start
)
1204 /* New right node. */
1205 split_interval_right (slot
, length
);
1209 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1211 /* New left node. */
1212 split_interval_left (slot
, LENGTH (slot
) - length
);
1216 /* Convert interval SLOT into three intervals. */
1217 split_interval_left (slot
, start
- slot
->position
);
1218 split_interval_right (slot
, length
);
1223 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1225 This is used in insdel.c when inserting Lisp_Strings into the
1226 buffer. The text corresponding to SOURCE is already in the buffer
1227 when this is called. The intervals of new tree are a copy of those
1228 belonging to the string being inserted; intervals are never
1231 If the inserted text had no intervals associated, this function
1232 simply returns -- offset_intervals should handle placing the
1233 text in the correct interval, depending on the sticky bits.
1235 If the inserted text had properties (intervals), then there are two
1236 cases -- either insertion happened in the middle of some interval,
1237 or between two intervals.
1239 If the text goes into the middle of an interval, then new
1240 intervals are created in the middle with only the properties of
1241 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1242 which case the new text has the union of its properties and those
1243 of the text into which it was inserted.
1245 If the text goes between two intervals, then if neither interval
1246 had its appropriate sticky property set (front_sticky, rear_sticky),
1247 the new text has only its properties. If one of the sticky properties
1248 is set, then the new text "sticks" to that region and its properties
1249 depend on merging as above. If both the preceding and succeeding
1250 intervals to the new text are "sticky", then the new text retains
1251 only its properties, as if neither sticky property were set. Perhaps
1252 we should consider merging all three sets of properties onto the new
1256 graft_intervals_into_buffer (source
, position
, buffer
, inherit
)
1259 struct buffer
*buffer
;
1262 register INTERVAL under
, over
, this, prev
;
1263 register INTERVAL tree
= buffer
->intervals
;
1266 /* If the new text has no properties, it becomes part of whatever
1267 interval it was inserted into. */
1268 if (NULL_INTERVAL_P (source
))
1271 if (NULL_INTERVAL_P (tree
))
1273 /* The inserted text constitutes the whole buffer, so
1274 simply copy over the interval structure. */
1275 if ((BUF_Z (buffer
) - BUF_BEG (buffer
)) == TOTAL_LENGTH (source
))
1278 XSET (buf
, Lisp_Buffer
, buffer
);
1279 buffer
->intervals
= reproduce_tree (source
, buf
);
1280 /* Explicitly free the old tree here. */
1285 /* Create an interval tree in which to place a copy
1286 of the intervals of the inserted string. */
1289 XSET (buf
, Lisp_Buffer
, buffer
);
1290 tree
= create_root_interval (buf
);
1293 else if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1294 /* If the buffer contains only the new string, but
1295 there was already some interval tree there, then it may be
1296 some zero length intervals. Eventually, do something clever
1297 about inserting properly. For now, just waste the old intervals. */
1299 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1300 /* Explicitly free the old tree here. */
1304 /* Paranoia -- the text has already been added, so this buffer
1305 should be of non-zero length. */
1306 else if (TOTAL_LENGTH (tree
) == 0)
1309 this = under
= find_interval (tree
, position
);
1310 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1312 over
= find_interval (source
, 1);
1314 /* Here for insertion in the middle of an interval.
1315 Split off an equivalent interval to the right,
1316 then don't bother with it any more. */
1318 if (position
> under
->position
)
1320 INTERVAL end_unchanged
1321 = split_interval_left (this, position
- under
->position
);
1322 copy_properties (under
, end_unchanged
);
1323 under
->position
= position
;
1329 prev
= previous_interval (under
);
1330 if (prev
&& !END_NONSTICKY_P (prev
))
1334 /* Insertion is now at beginning of UNDER. */
1336 /* The inserted text "sticks" to the interval `under',
1337 which means it gets those properties.
1338 The properties of under are the result of
1339 adjust_intervals_for_insertion, so stickyness has
1340 already been taken care of. */
1342 while (! NULL_INTERVAL_P (over
))
1344 if (LENGTH (over
) + 1 < LENGTH (under
))
1346 this = split_interval_left (under
, LENGTH (over
));
1347 copy_properties (under
, this);
1351 copy_properties (over
, this);
1353 merge_properties (over
, this);
1355 copy_properties (over
, this);
1356 over
= next_interval (over
);
1359 buffer
->intervals
= balance_intervals (buffer
->intervals
);
1363 /* Get the value of property PROP from PLIST,
1364 which is the plist of an interval.
1365 We check for direct properties and for categories with property PROP. */
1368 textget (plist
, prop
)
1370 register Lisp_Object prop
;
1372 register Lisp_Object tail
, fallback
;
1375 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1377 register Lisp_Object tem
;
1380 return Fcar (Fcdr (tail
));
1381 if (EQ (tem
, Qcategory
))
1382 fallback
= Fget (Fcar (Fcdr (tail
)), prop
);
1388 /* Get the value of property PROP from PLIST,
1389 which is the plist of an interval.
1390 We check for direct properties only! */
1393 textget_direct (plist
, prop
)
1395 register Lisp_Object prop
;
1397 register Lisp_Object tail
;
1399 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1401 if (EQ (prop
, Fcar (tail
)))
1402 return Fcar (Fcdr (tail
));
1408 /* Set point in BUFFER to POSITION. If the target position is
1409 before an invisible character which is not displayed with a special glyph,
1410 move back to an ok place to display. */
1413 set_point (position
, buffer
)
1414 register int position
;
1415 register struct buffer
*buffer
;
1417 register INTERVAL to
, from
, toprev
, fromprev
, target
;
1419 register Lisp_Object obj
;
1420 int backwards
= (position
< BUF_PT (buffer
)) ? 1 : 0;
1421 int old_position
= buffer
->text
.pt
;
1423 if (position
== buffer
->text
.pt
)
1426 /* Check this now, before checking if the buffer has any intervals.
1427 That way, we can catch conditions which break this sanity check
1428 whether or not there are intervals in the buffer. */
1429 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1432 if (NULL_INTERVAL_P (buffer
->intervals
))
1434 buffer
->text
.pt
= position
;
1438 /* Set TO to the interval containing the char after POSITION,
1439 and TOPREV to the interval containing the char before POSITION.
1440 Either one may be null. They may be equal. */
1441 to
= find_interval (buffer
->intervals
, position
);
1442 if (position
== BUF_BEGV (buffer
))
1444 else if (to
->position
== position
)
1445 toprev
= previous_interval (to
);
1449 buffer_point
= (BUF_PT (buffer
) == BUF_ZV (buffer
)
1450 ? BUF_ZV (buffer
) - 1
1453 /* Set FROM to the interval containing the char after PT,
1454 and FROMPREV to the interval containing the char before PT.
1455 Either one may be null. They may be equal. */
1456 /* We could cache this and save time. */
1457 from
= find_interval (buffer
->intervals
, buffer_point
);
1458 if (buffer_point
== BUF_BEGV (buffer
))
1460 else if (from
->position
== BUF_PT (buffer
))
1461 fromprev
= previous_interval (from
);
1462 else if (buffer_point
!= BUF_PT (buffer
))
1463 fromprev
= from
, from
= 0;
1467 /* Moving within an interval. */
1468 if (to
== from
&& toprev
== fromprev
&& INTERVAL_VISIBLE_P (to
))
1470 buffer
->text
.pt
= position
;
1474 /* If the new position is before an invisible character
1475 that has an `invisible' property of value `hidden',
1476 move forward over all such. */
1477 while (! NULL_INTERVAL_P (to
)
1478 && EQ (textget (to
->plist
, Qinvisible
), Qhidden
)
1479 && ! DISPLAY_INVISIBLE_GLYPH (to
))
1482 to
= next_interval (to
);
1483 if (NULL_INTERVAL_P (to
))
1484 position
= BUF_ZV (buffer
);
1486 position
= to
->position
;
1489 buffer
->text
.pt
= position
;
1491 /* We run point-left and point-entered hooks here, iff the
1492 two intervals are not equivalent. These hooks take
1493 (old_point, new_point) as arguments. */
1494 if (NILP (Vinhibit_point_motion_hooks
)
1495 && (! intervals_equal (from
, to
)
1496 || ! intervals_equal (fromprev
, toprev
)))
1498 Lisp_Object leave_after
, leave_before
, enter_after
, enter_before
;
1501 leave_after
= textget (fromprev
->plist
, Qpoint_left
);
1505 leave_before
= textget (from
->plist
, Qpoint_left
);
1507 leave_before
= Qnil
;
1510 enter_after
= textget (toprev
->plist
, Qpoint_entered
);
1514 enter_before
= textget (to
->plist
, Qpoint_entered
);
1516 enter_before
= Qnil
;
1518 if (! EQ (leave_before
, enter_before
) && !NILP (leave_before
))
1519 call2 (leave_before
, old_position
, position
);
1520 if (! EQ (leave_after
, enter_after
) && !NILP (leave_after
))
1521 call2 (leave_after
, old_position
, position
);
1523 if (! EQ (enter_before
, leave_before
) && !NILP (enter_before
))
1524 call2 (enter_before
, old_position
, position
);
1525 if (! EQ (enter_after
, leave_after
) && !NILP (enter_after
))
1526 call2 (enter_after
, old_position
, position
);
1530 /* Set point temporarily, without checking any text properties. */
1533 temp_set_point (position
, buffer
)
1535 struct buffer
*buffer
;
1537 buffer
->text
.pt
= position
;
1540 /* Return the proper local map for position POSITION in BUFFER.
1541 Use the map specified by the local-map property, if any.
1542 Otherwise, use BUFFER's local map. */
1545 get_local_map (position
, buffer
)
1546 register int position
;
1547 register struct buffer
*buffer
;
1549 register INTERVAL interval
;
1550 Lisp_Object prop
, tem
;
1552 if (NULL_INTERVAL_P (buffer
->intervals
))
1553 return current_buffer
->keymap
;
1555 /* Perhaps we should just change `position' to the limit. */
1556 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1559 interval
= find_interval (buffer
->intervals
, position
);
1560 prop
= textget (interval
->plist
, Qlocal_map
);
1562 return current_buffer
->keymap
;
1564 /* Use the local map only if it is valid. */
1565 tem
= Fkeymapp (prop
);
1569 return current_buffer
->keymap
;
1572 /* Call the modification hook functions in LIST, each with START and END. */
1575 call_mod_hooks (list
, start
, end
)
1576 Lisp_Object list
, start
, end
;
1578 struct gcpro gcpro1
;
1580 while (!NILP (list
))
1582 call2 (Fcar (list
), start
, end
);
1588 /* Check for read-only intervals and signal an error if we find one.
1589 Then check for any modification hooks in the range START up to
1590 (but not including) TO. Create a list of all these hooks in
1591 lexicographic order, eliminating consecutive extra copies of the
1592 same hook. Then call those hooks in order, with START and END - 1
1596 verify_interval_modification (buf
, start
, end
)
1600 register INTERVAL intervals
= buf
->intervals
;
1601 register INTERVAL i
, prev
;
1603 register Lisp_Object prev_mod_hooks
;
1604 Lisp_Object mod_hooks
;
1605 struct gcpro gcpro1
;
1608 prev_mod_hooks
= Qnil
;
1611 if (NULL_INTERVAL_P (intervals
))
1621 /* For an insert operation, check the two chars around the position. */
1625 Lisp_Object before
, after
;
1627 /* Set I to the interval containing the char after START,
1628 and PREV to the interval containing the char before START.
1629 Either one may be null. They may be equal. */
1630 i
= find_interval (intervals
, start
);
1632 if (start
== BUF_BEGV (buf
))
1634 else if (i
->position
== start
)
1635 prev
= previous_interval (i
);
1636 else if (i
->position
< start
)
1638 if (start
== BUF_ZV (buf
))
1641 /* If Vinhibit_read_only is set and is not a list, we can
1642 skip the read_only checks. */
1643 if (NILP (Vinhibit_read_only
) || CONSP (Vinhibit_read_only
))
1645 /* If I and PREV differ we need to check for the read-only
1646 property together with its stickyness. If either I or
1647 PREV are 0, this check is all we need.
1648 We have to take special care, since read-only may be
1649 indirectly defined via the category property. */
1652 if (! NULL_INTERVAL_P (i
))
1654 after
= textget (i
->plist
, Qread_only
);
1656 /* If interval I is read-only and read-only is
1657 front-sticky, inhibit insertion.
1658 Check for read-only as well as category. */
1660 && NILP (Fmemq (after
, Vinhibit_read_only
))
1661 && (! NILP (Fmemq (Qread_only
,
1662 textget (i
->plist
, Qfront_sticky
)))
1663 || (NILP (textget_direct (i
->plist
, Qread_only
))
1664 && ! NILP (Fmemq (Qcategory
,
1667 error ("Attempt to insert within read-only text");
1671 if (! NULL_INTERVAL_P (prev
))
1673 before
= textget (prev
->plist
, Qread_only
);
1675 /* If interval PREV is read-only and read-only isn't
1676 rear-nonsticky, inhibit insertion.
1677 Check for read-only as well as category. */
1679 && NILP (Fmemq (before
, Vinhibit_read_only
))
1680 && NILP (Fmemq (Qread_only
,
1681 textget (prev
->plist
, Qrear_nonsticky
)))
1682 && (! NILP (textget_direct (prev
->plist
,Qread_only
))
1683 || NILP (Fmemq (Qcategory
,
1684 textget (prev
->plist
,
1685 Qrear_nonsticky
)))))
1686 error ("Attempt to insert within read-only text");
1691 else if (! NULL_INTERVAL_P (i
))
1692 before
= after
= textget (i
->plist
, Qread_only
);
1693 if (! NULL_INTERVAL_P (i
) && ! NULL_INTERVAL_P (prev
))
1695 /* If I and PREV differ, neither of them has a sticky
1696 read-only property. It only remains to check, whether
1697 they have a common read-only property. */
1698 if (! NILP (before
) && EQ (before
, after
))
1699 error ("Attempt to insert within read-only text");
1703 /* Run both insert hooks (just once if they're the same). */
1704 if (!NULL_INTERVAL_P (prev
))
1705 prev_mod_hooks
= textget (prev
->plist
, Qinsert_behind_hooks
);
1706 if (!NULL_INTERVAL_P (i
))
1707 mod_hooks
= textget (i
->plist
, Qinsert_in_front_hooks
);
1709 if (! NILP (prev_mod_hooks
))
1710 call_mod_hooks (prev_mod_hooks
, make_number (start
),
1713 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1714 call_mod_hooks (mod_hooks
, make_number (start
), make_number (end
));
1718 /* Loop over intervals on or next to START...END,
1719 collecting their hooks. */
1721 i
= find_interval (intervals
, start
);
1724 if (! INTERVAL_WRITABLE_P (i
))
1725 error ("Attempt to modify read-only text");
1727 mod_hooks
= textget (i
->plist
, Qmodification_hooks
);
1728 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1730 hooks
= Fcons (mod_hooks
, hooks
);
1731 prev_mod_hooks
= mod_hooks
;
1734 i
= next_interval (i
);
1736 /* Keep going thru the interval containing the char before END. */
1737 while (! NULL_INTERVAL_P (i
) && i
->position
< end
);
1740 hooks
= Fnreverse (hooks
);
1741 while (! EQ (hooks
, Qnil
))
1743 call_mod_hooks (Fcar (hooks
), make_number (start
),
1745 hooks
= Fcdr (hooks
);
1751 /* Balance an interval node if the amount of text in its left and right
1752 subtrees differs by more than the percentage specified by
1753 `interval-balance-threshold'. */
1756 balance_an_interval (i
)
1759 register int total_children_size
= (LEFT_TOTAL_LENGTH (i
)
1760 + RIGHT_TOTAL_LENGTH (i
));
1761 register int threshold
= (XFASTINT (interval_balance_threshold
)
1762 * (total_children_size
/ 100));
1764 /* Balance within each side. */
1765 balance_intervals (i
->left
);
1766 balance_intervals (i
->right
);
1768 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1769 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1771 i
= rotate_right (i
);
1772 /* If that made it unbalanced the other way, take it back. */
1773 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1774 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1775 return rotate_left (i
);
1779 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1780 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1782 i
= rotate_left (i
);
1783 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1784 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1785 return rotate_right (i
);
1792 /* Balance the interval tree TREE. Balancing is by weight
1793 (the amount of text). */
1796 balance_intervals (tree
)
1797 register INTERVAL tree
;
1799 register INTERVAL new_tree
;
1801 if (NULL_INTERVAL_P (tree
))
1802 return NULL_INTERVAL
;
1808 new_tree
= balance_an_interval (new_tree
);
1810 while (new_tree
!= tree
);
1815 /* Produce an interval tree reflecting the intervals in
1816 TREE from START to START + LENGTH. */
1819 copy_intervals (tree
, start
, length
)
1823 register INTERVAL i
, new, t
;
1824 register int got
, prevlen
;
1826 if (NULL_INTERVAL_P (tree
) || length
<= 0)
1827 return NULL_INTERVAL
;
1829 i
= find_interval (tree
, start
);
1830 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
1833 /* If there is only one interval and it's the default, return nil. */
1834 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
1835 && DEFAULT_INTERVAL_P (i
))
1836 return NULL_INTERVAL
;
1838 new = make_interval ();
1840 got
= (LENGTH (i
) - (start
- i
->position
));
1841 new->total_length
= length
;
1842 copy_properties (i
, new);
1846 while (got
< length
)
1848 i
= next_interval (i
);
1849 t
= split_interval_right (t
, prevlen
);
1850 copy_properties (i
, t
);
1851 prevlen
= LENGTH (i
);
1855 return balance_intervals (new);
1858 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1861 copy_intervals_to_string (string
, buffer
, position
, length
)
1862 Lisp_Object string
, buffer
;
1863 int position
, length
;
1865 INTERVAL interval_copy
= copy_intervals (XBUFFER (buffer
)->intervals
,
1867 if (NULL_INTERVAL_P (interval_copy
))
1870 interval_copy
->parent
= (INTERVAL
) string
;
1871 XSTRING (string
)->intervals
= interval_copy
;
1874 #endif /* USE_TEXT_PROPERTIES */