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 old_total
= interval
->total_length
;
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
= B
;
294 interval
->parent
->right
= B
;
295 B
->parent
= interval
->parent
;
297 /* Make B the parent of A */
300 interval
->parent
= B
;
302 /* Make A point to c */
304 if (! NULL_INTERVAL_P (i
))
305 i
->parent
= interval
;
307 /* A's total length is decreased by the length of B and it's left child. */
308 interval
->total_length
-= B
->total_length
- LEFT_TOTAL_LENGTH (interval
);
310 /* B must have the same total length of A. */
311 B
->total_length
= old_total
;
316 /* Assuming that a right child exists, perform the following operation:
326 rotate_left (interval
)
330 INTERVAL B
= interval
->right
;
331 int old_total
= interval
->total_length
;
333 /* Deal with any parent of A; make it point to B. */
334 if (! ROOT_INTERVAL_P (interval
))
335 if (AM_LEFT_CHILD (interval
))
336 interval
->parent
->left
= B
;
338 interval
->parent
->right
= B
;
339 B
->parent
= interval
->parent
;
341 /* Make B the parent of A */
344 interval
->parent
= B
;
346 /* Make A point to c */
348 if (! NULL_INTERVAL_P (i
))
349 i
->parent
= interval
;
351 /* A's total length is decreased by the length of B and it's right child. */
352 interval
->total_length
-= B
->total_length
- RIGHT_TOTAL_LENGTH (interval
);
354 /* B must have the same total length of A. */
355 B
->total_length
= old_total
;
360 /* Balance an interval tree with the assumption that the subtrees
361 themselves are already balanced. */
364 balance_an_interval (i
)
367 register int old_diff
, new_diff
;
371 old_diff
= LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
);
374 new_diff
= i
->total_length
- i
->left
->total_length
375 + RIGHT_TOTAL_LENGTH (i
->left
) - LEFT_TOTAL_LENGTH (i
->left
);
376 if (abs (new_diff
) >= old_diff
)
378 i
= rotate_right (i
);
379 balance_an_interval (i
->right
);
381 else if (old_diff
< 0)
383 new_diff
= i
->total_length
- i
->right
->total_length
384 + LEFT_TOTAL_LENGTH (i
->right
) - RIGHT_TOTAL_LENGTH (i
->right
);
385 if (abs (new_diff
) >= -old_diff
)
388 balance_an_interval (i
->left
);
396 /* Balance INTERVAL, potentially stuffing it back into its parent
399 static INLINE INTERVAL
400 balance_possible_root_interval (interval
)
401 register INTERVAL interval
;
405 if (interval
->parent
== NULL_INTERVAL
)
408 parent
= (Lisp_Object
) (interval
->parent
);
409 interval
= balance_an_interval (interval
);
411 if (XTYPE (parent
) == Lisp_Buffer
)
412 XBUFFER (parent
)->intervals
= interval
;
413 else if (XTYPE (parent
) == Lisp_String
)
414 XSTRING (parent
)->intervals
= interval
;
419 /* Balance the interval tree TREE. Balancing is by weight
420 (the amount of text). */
423 balance_intervals_internal (tree
)
424 register INTERVAL tree
;
426 /* Balance within each side. */
428 balance_intervals (tree
->left
);
430 balance_intervals (tree
->right
);
431 return balance_an_interval (tree
);
434 /* Advertised interface to balance intervals. */
437 balance_intervals (tree
)
440 if (tree
== NULL_INTERVAL
)
441 return NULL_INTERVAL
;
443 return balance_intervals_internal (tree
);
446 /* Split INTERVAL into two pieces, starting the second piece at
447 character position OFFSET (counting from 0), relative to INTERVAL.
448 INTERVAL becomes the left-hand piece, and the right-hand piece
449 (second, lexicographically) is returned.
451 The size and position fields of the two intervals are set based upon
452 those of the original interval. The property list of the new interval
453 is reset, thus it is up to the caller to do the right thing with the
456 Note that this does not change the position of INTERVAL; if it is a root,
457 it is still a root after this operation. */
460 split_interval_right (interval
, offset
)
464 INTERVAL
new = make_interval ();
465 int position
= interval
->position
;
466 int new_length
= LENGTH (interval
) - offset
;
468 new->position
= position
+ offset
;
469 new->parent
= interval
;
471 if (NULL_RIGHT_CHILD (interval
))
473 interval
->right
= new;
474 new->total_length
= new_length
;
479 /* Insert the new node between INTERVAL and its right child. */
480 new->right
= interval
->right
;
481 interval
->right
->parent
= new;
482 interval
->right
= new;
483 new->total_length
= new_length
+ new->right
->total_length
;
485 balance_an_interval (new);
486 balance_possible_root_interval (interval
);
491 /* Split INTERVAL into two pieces, starting the second piece at
492 character position OFFSET (counting from 0), relative to INTERVAL.
493 INTERVAL becomes the right-hand piece, and the left-hand piece
494 (first, lexicographically) is returned.
496 The size and position fields of the two intervals are set based upon
497 those of the original interval. The property list of the new interval
498 is reset, thus it is up to the caller to do the right thing with the
501 Note that this does not change the position of INTERVAL; if it is a root,
502 it is still a root after this operation. */
505 split_interval_left (interval
, offset
)
509 INTERVAL
new = make_interval ();
510 int position
= interval
->position
;
511 int new_length
= offset
;
513 new->position
= interval
->position
;
514 interval
->position
= interval
->position
+ offset
;
515 new->parent
= interval
;
517 if (NULL_LEFT_CHILD (interval
))
519 interval
->left
= new;
520 new->total_length
= new_length
;
525 /* Insert the new node between INTERVAL and its left child. */
526 new->left
= interval
->left
;
527 new->left
->parent
= new;
528 interval
->left
= new;
529 new->total_length
= new_length
+ new->left
->total_length
;
531 balance_an_interval (new);
532 balance_possible_root_interval (interval
);
537 /* Find the interval containing text position POSITION in the text
538 represented by the interval tree TREE. POSITION is a buffer
539 position; the earliest position is 1. If POSITION is at the end of
540 the buffer, return the interval containing the last character.
542 The `position' field, which is a cache of an interval's position,
543 is updated in the interval found. Other functions (e.g., next_interval)
544 will update this cache based on the result of find_interval. */
547 find_interval (tree
, position
)
548 register INTERVAL tree
;
549 register int position
;
551 /* The distance from the left edge of the subtree at TREE
553 register int relative_position
= position
- BEG
;
555 if (NULL_INTERVAL_P (tree
))
556 return NULL_INTERVAL
;
558 if (relative_position
> TOTAL_LENGTH (tree
))
559 abort (); /* Paranoia */
561 tree
= balance_possible_root_interval (tree
);
565 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
569 else if (! NULL_RIGHT_CHILD (tree
)
570 && relative_position
>= (TOTAL_LENGTH (tree
)
571 - RIGHT_TOTAL_LENGTH (tree
)))
573 relative_position
-= (TOTAL_LENGTH (tree
)
574 - RIGHT_TOTAL_LENGTH (tree
));
580 (position
- relative_position
/* the left edge of *tree */
581 + LEFT_TOTAL_LENGTH (tree
)); /* the left edge of this interval */
588 /* Find the succeeding interval (lexicographically) to INTERVAL.
589 Sets the `position' field based on that of INTERVAL (see
593 next_interval (interval
)
594 register INTERVAL interval
;
596 register INTERVAL i
= interval
;
597 register int next_position
;
599 if (NULL_INTERVAL_P (i
))
600 return NULL_INTERVAL
;
601 next_position
= interval
->position
+ LENGTH (interval
);
603 if (! NULL_RIGHT_CHILD (i
))
606 while (! NULL_LEFT_CHILD (i
))
609 i
->position
= next_position
;
613 while (! NULL_PARENT (i
))
615 if (AM_LEFT_CHILD (i
))
618 i
->position
= next_position
;
625 return NULL_INTERVAL
;
628 /* Find the preceding interval (lexicographically) to INTERVAL.
629 Sets the `position' field based on that of INTERVAL (see
633 previous_interval (interval
)
634 register INTERVAL interval
;
637 register position_of_previous
;
639 if (NULL_INTERVAL_P (interval
))
640 return NULL_INTERVAL
;
642 if (! NULL_LEFT_CHILD (interval
))
645 while (! NULL_RIGHT_CHILD (i
))
648 i
->position
= interval
->position
- LENGTH (i
);
653 while (! NULL_PARENT (i
))
655 if (AM_RIGHT_CHILD (i
))
659 i
->position
= interval
->position
- LENGTH (i
);
665 return NULL_INTERVAL
;
669 /* Traverse a path down the interval tree TREE to the interval
670 containing POSITION, adjusting all nodes on the path for
671 an addition of LENGTH characters. Insertion between two intervals
672 (i.e., point == i->position, where i is second interval) means
673 text goes into second interval.
675 Modifications are needed to handle the hungry bits -- after simply
676 finding the interval at position (don't add length going down),
677 if it's the beginning of the interval, get the previous interval
678 and check the hugry bits of both. Then add the length going back up
682 adjust_intervals_for_insertion (tree
, position
, length
)
684 int position
, length
;
686 register int relative_position
;
687 register INTERVAL
this;
689 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
692 /* If inserting at point-max of a buffer, that position
693 will be out of range */
694 if (position
> TOTAL_LENGTH (tree
))
695 position
= TOTAL_LENGTH (tree
);
696 relative_position
= position
;
701 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
703 this->total_length
+= length
;
706 else if (relative_position
> (TOTAL_LENGTH (this)
707 - RIGHT_TOTAL_LENGTH (this)))
709 relative_position
-= (TOTAL_LENGTH (this)
710 - RIGHT_TOTAL_LENGTH (this));
711 this->total_length
+= length
;
716 /* If we are to use zero-length intervals as buffer pointers,
717 then this code will have to change. */
718 this->total_length
+= length
;
719 this->position
= LEFT_TOTAL_LENGTH (this)
720 + position
- relative_position
+ 1;
727 /* Effect an adjustment corresponding to the addition of LENGTH characters
728 of text. Do this by finding the interval containing POSITION in the
729 interval tree TREE, and then adjusting all of it's ancestors by adding
732 If POSITION is the first character of an interval, meaning that point
733 is actually between the two intervals, make the new text belong to
734 the interval which is "sticky".
736 If both intervals are "sticky", then make them belong to the left-most
737 interval. Another possibility would be to create a new interval for
738 this text, and make it have the merged properties of both ends. */
741 adjust_intervals_for_insertion (tree
, position
, length
)
743 int position
, length
;
746 register INTERVAL temp
;
749 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
752 /* If inserting at point-max of a buffer, that position will be out
753 of range. Remember that buffer positions are 1-based. */
754 if (position
>= BEG
+ TOTAL_LENGTH (tree
)){
755 position
= BEG
+ TOTAL_LENGTH (tree
);
759 i
= find_interval (tree
, position
);
761 /* If in middle of an interval which is not sticky either way,
762 we must not just give its properties to the insertion.
763 So split this interval at the insertion point. */
764 if (! (position
== i
->position
|| eobp
)
765 && END_NONSTICKY_P (i
)
766 && ! FRONT_STICKY_P (i
))
768 temp
= split_interval_right (i
, position
- i
->position
);
769 copy_properties (i
, temp
);
773 /* If we are positioned between intervals, check the stickiness of
774 both of them. We have to do this too, if we are at BEG or Z. */
775 if (position
== i
->position
|| eobp
)
777 register INTERVAL prev
;
787 prev
= previous_interval (i
);
789 /* Even if we are positioned between intervals, we default
790 to the left one if it exists. We extend it now and split
791 off a part later, if stickyness demands it. */
792 for (temp
= prev
? prev
: i
;! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
794 temp
->total_length
+= length
;
795 temp
= balance_possible_root_interval (temp
);
798 /* If at least one interval has sticky properties,
799 we check the stickyness property by property. */
800 if (END_NONSTICKY_P (prev
) || FRONT_STICKY_P (i
))
802 Lisp_Object pleft
= NULL_INTERVAL_P (prev
) ? Qnil
: prev
->plist
;
803 Lisp_Object pright
= NULL_INTERVAL_P (i
) ? Qnil
: i
->plist
;
804 struct interval newi
;
806 newi
.plist
= merge_properties_sticky (pleft
, pright
);
808 if(! prev
) /* i.e. position == BEG */
810 if (! intervals_equal (i
, &newi
))
812 i
= split_interval_left (i
, length
);
813 i
->plist
= newi
.plist
;
816 else if (! intervals_equal (prev
, &newi
))
818 prev
= split_interval_right (prev
,
819 position
- prev
->position
);
820 prev
->plist
= newi
.plist
;
821 if (! NULL_INTERVAL_P (i
)
822 && intervals_equal (prev
, i
))
823 merge_interval_right (prev
);
826 /* We will need to update the cache here later. */
828 else if (! prev
&& ! NILP (i
->plist
))
830 /* Just split off a new interval at the left.
831 Since I wasn't front-sticky, the empty plist is ok. */
832 i
= split_interval_left (i
, length
);
836 /* Otherwise just extend the interval. */
839 for (temp
= i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
841 temp
->total_length
+= length
;
842 temp
= balance_possible_root_interval (temp
);
850 merge_properties_sticky (pleft
, pright
)
851 Lisp_Object pleft
, pright
;
853 register Lisp_Object props
= Qnil
, front
= Qnil
, rear
= Qnil
;
855 Lisp_Object lfront
= textget (pleft
, Qfront_sticky
);
856 Lisp_Object lrear
= textget (pleft
, Qrear_nonsticky
);
857 Lisp_Object rfront
= textget (pright
, Qfront_sticky
);
858 Lisp_Object rrear
= textget (pright
, Qrear_nonsticky
);
860 register Lisp_Object tail1
, tail2
, sym
;
862 /* Go through each element of PLEFT. */
863 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
867 /* Sticky properties get special treatment. */
868 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
871 if (CONSP (lrear
) ? NILP (Fmemq (sym
, lrear
)) : NILP (lrear
))
873 /* rear-sticky is dominant, we needn't search in PRIGHT. */
875 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail1
)), props
));
876 if ((CONSP (lfront
) || NILP (lfront
))
877 && ! NILP (Fmemq (sym
, lfront
)))
878 front
= Fcons (sym
, front
);
882 /* Go through PRIGHT, looking for sym. */
883 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
884 if (EQ (sym
, Fcar (tail2
)))
888 ? ! NILP (Fmemq (sym
, rfront
)) : ! NILP (rfront
))
890 /* Nonsticky at the left and sticky at the right,
891 so take the right one. */
892 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
893 front
= Fcons (sym
, front
);
894 if ((CONSP (rrear
) || NILP (rrear
))
895 && ! NILP (Fmemq (sym
, rrear
)))
896 rear
= Fcons (sym
, rear
);
902 /* Now let's see what to keep from PRIGHT. */
903 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
907 /* Sticky properties get special treatment. */
908 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
911 /* If it ain't sticky, we don't take it. */
913 ? NILP (Fmemq (sym
, rfront
)) : NILP (rfront
))
916 /* If sym is in PLEFT we already got it. */
917 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
918 if (EQ (sym
, Fcar (tail1
)))
923 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
924 front
= Fcons (sym
, front
);
925 if ((CONSP (rrear
) || NILP (rrear
))
926 && ! NILP (Fmemq (sym
, rrear
)))
927 rear
= Fcons (sym
, rear
);
931 props
= Fcons (Qfront_sticky
, Fcons (front
, props
));
933 props
= Fcons (Qrear_nonsticky
, Fcons (rear
, props
));
939 /* Delete an node I from its interval tree by merging its subtrees
940 into one subtree which is then returned. Caller is responsible for
941 storing the resulting subtree into its parent. */
947 register INTERVAL migrate
, this;
948 register int migrate_amt
;
950 if (NULL_INTERVAL_P (i
->left
))
952 if (NULL_INTERVAL_P (i
->right
))
956 migrate_amt
= i
->left
->total_length
;
958 this->total_length
+= migrate_amt
;
959 while (! NULL_INTERVAL_P (this->left
))
962 this->total_length
+= migrate_amt
;
964 this->left
= migrate
;
965 migrate
->parent
= this;
970 /* Delete interval I from its tree by calling `delete_node'
971 and properly connecting the resultant subtree.
973 I is presumed to be empty; that is, no adjustments are made
974 for the length of I. */
980 register INTERVAL parent
;
981 int amt
= LENGTH (i
);
983 if (amt
> 0) /* Only used on zero-length intervals now. */
986 if (ROOT_INTERVAL_P (i
))
988 Lisp_Object owner
= (Lisp_Object
) i
->parent
;
989 parent
= delete_node (i
);
990 if (! NULL_INTERVAL_P (parent
))
991 parent
->parent
= (INTERVAL
) owner
;
993 if (XTYPE (owner
) == Lisp_Buffer
)
994 XBUFFER (owner
)->intervals
= parent
;
995 else if (XTYPE (owner
) == Lisp_String
)
996 XSTRING (owner
)->intervals
= parent
;
1004 if (AM_LEFT_CHILD (i
))
1006 parent
->left
= delete_node (i
);
1007 if (! NULL_INTERVAL_P (parent
->left
))
1008 parent
->left
->parent
= parent
;
1012 parent
->right
= delete_node (i
);
1013 if (! NULL_INTERVAL_P (parent
->right
))
1014 parent
->right
->parent
= parent
;
1018 /* Find the interval in TREE corresponding to the relative position
1019 FROM and delete as much as possible of AMOUNT from that interval.
1020 Return the amount actually deleted, and if the interval was
1021 zeroed-out, delete that interval node from the tree.
1023 Note that FROM is actually origin zero, aka relative to the
1024 leftmost edge of tree. This is appropriate since we call ourselves
1025 recursively on subtrees.
1027 Do this by recursing down TREE to the interval in question, and
1028 deleting the appropriate amount of text. */
1031 interval_deletion_adjustment (tree
, from
, amount
)
1032 register INTERVAL tree
;
1033 register int from
, amount
;
1035 register int relative_position
= from
;
1037 if (NULL_INTERVAL_P (tree
))
1041 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
1043 int subtract
= interval_deletion_adjustment (tree
->left
,
1046 tree
->total_length
-= subtract
;
1050 else if (relative_position
>= (TOTAL_LENGTH (tree
)
1051 - RIGHT_TOTAL_LENGTH (tree
)))
1055 relative_position
-= (tree
->total_length
1056 - RIGHT_TOTAL_LENGTH (tree
));
1057 subtract
= interval_deletion_adjustment (tree
->right
,
1060 tree
->total_length
-= subtract
;
1063 /* Here -- this node. */
1066 /* How much can we delete from this interval? */
1067 int my_amount
= ((tree
->total_length
1068 - RIGHT_TOTAL_LENGTH (tree
))
1069 - relative_position
);
1071 if (amount
> my_amount
)
1074 tree
->total_length
-= amount
;
1075 if (LENGTH (tree
) == 0)
1076 delete_interval (tree
);
1081 /* Never reach here. */
1084 /* Effect the adjustments necessary to the interval tree of BUFFER to
1085 correspond to the deletion of LENGTH characters from that buffer
1086 text. The deletion is effected at position START (which is a
1087 buffer position, i.e. origin 1). */
1090 adjust_intervals_for_deletion (buffer
, start
, length
)
1091 struct buffer
*buffer
;
1094 register int left_to_delete
= length
;
1095 register INTERVAL tree
= buffer
->intervals
;
1096 register int deleted
;
1098 if (NULL_INTERVAL_P (tree
))
1101 if (start
> BEG
+ TOTAL_LENGTH (tree
)
1102 || start
+ length
> BEG
+ TOTAL_LENGTH (tree
))
1105 if (length
== TOTAL_LENGTH (tree
))
1107 buffer
->intervals
= NULL_INTERVAL
;
1111 if (ONLY_INTERVAL_P (tree
))
1113 tree
->total_length
-= length
;
1117 if (start
> BEG
+ TOTAL_LENGTH (tree
))
1118 start
= BEG
+ TOTAL_LENGTH (tree
);
1119 while (left_to_delete
> 0)
1121 left_to_delete
-= interval_deletion_adjustment (tree
, start
- 1,
1123 tree
= buffer
->intervals
;
1124 if (left_to_delete
== tree
->total_length
)
1126 buffer
->intervals
= NULL_INTERVAL
;
1132 /* Make the adjustments necessary to the interval tree of BUFFER to
1133 represent an addition or deletion of LENGTH characters starting
1134 at position START. Addition or deletion is indicated by the sign
1138 offset_intervals (buffer
, start
, length
)
1139 struct buffer
*buffer
;
1142 if (NULL_INTERVAL_P (buffer
->intervals
) || length
== 0)
1146 adjust_intervals_for_insertion (buffer
->intervals
, start
, length
);
1148 adjust_intervals_for_deletion (buffer
, start
, -length
);
1151 /* Merge interval I with its lexicographic successor. The resulting
1152 interval is returned, and has the properties of the original
1153 successor. The properties of I are lost. I is removed from the
1157 The caller must verify that this is not the last (rightmost)
1161 merge_interval_right (i
)
1162 register INTERVAL i
;
1164 register int absorb
= LENGTH (i
);
1165 register INTERVAL successor
;
1167 /* Zero out this interval. */
1168 i
->total_length
-= absorb
;
1170 /* Find the succeeding interval. */
1171 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
1174 successor
= i
->right
;
1175 while (! NULL_LEFT_CHILD (successor
))
1177 successor
->total_length
+= absorb
;
1178 successor
= successor
->left
;
1181 successor
->total_length
+= absorb
;
1182 delete_interval (i
);
1187 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
1190 if (AM_LEFT_CHILD (successor
))
1192 successor
= successor
->parent
;
1193 delete_interval (i
);
1197 successor
= successor
->parent
;
1198 successor
->total_length
-= absorb
;
1201 /* This must be the rightmost or last interval and cannot
1202 be merged right. The caller should have known. */
1206 /* Merge interval I with its lexicographic predecessor. The resulting
1207 interval is returned, and has the properties of the original predecessor.
1208 The properties of I are lost. Interval node I is removed from the tree.
1211 The caller must verify that this is not the first (leftmost) interval. */
1214 merge_interval_left (i
)
1215 register INTERVAL i
;
1217 register int absorb
= LENGTH (i
);
1218 register INTERVAL predecessor
;
1220 /* Zero out this interval. */
1221 i
->total_length
-= absorb
;
1223 /* Find the preceding interval. */
1224 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
1225 adding ABSORB as we go. */
1227 predecessor
= i
->left
;
1228 while (! NULL_RIGHT_CHILD (predecessor
))
1230 predecessor
->total_length
+= absorb
;
1231 predecessor
= predecessor
->right
;
1234 predecessor
->total_length
+= absorb
;
1235 delete_interval (i
);
1240 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
1241 subtracting ABSORB. */
1243 if (AM_RIGHT_CHILD (predecessor
))
1245 predecessor
= predecessor
->parent
;
1246 delete_interval (i
);
1250 predecessor
= predecessor
->parent
;
1251 predecessor
->total_length
-= absorb
;
1254 /* This must be the leftmost or first interval and cannot
1255 be merged left. The caller should have known. */
1259 /* Make an exact copy of interval tree SOURCE which descends from
1260 PARENT. This is done by recursing through SOURCE, copying
1261 the current interval and its properties, and then adjusting
1262 the pointers of the copy. */
1265 reproduce_tree (source
, parent
)
1266 INTERVAL source
, parent
;
1268 register INTERVAL t
= make_interval ();
1270 bcopy (source
, t
, INTERVAL_SIZE
);
1271 copy_properties (source
, t
);
1273 if (! NULL_LEFT_CHILD (source
))
1274 t
->left
= reproduce_tree (source
->left
, t
);
1275 if (! NULL_RIGHT_CHILD (source
))
1276 t
->right
= reproduce_tree (source
->right
, t
);
1282 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
1284 /* Make a new interval of length LENGTH starting at START in the
1285 group of intervals INTERVALS, which is actually an interval tree.
1286 Returns the new interval.
1288 Generate an error if the new positions would overlap an existing
1292 make_new_interval (intervals
, start
, length
)
1298 slot
= find_interval (intervals
, start
);
1299 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1300 error ("Interval would overlap");
1302 if (start
== slot
->position
&& length
== LENGTH (slot
))
1305 if (slot
->position
== start
)
1307 /* New right node. */
1308 split_interval_right (slot
, length
);
1312 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1314 /* New left node. */
1315 split_interval_left (slot
, LENGTH (slot
) - length
);
1319 /* Convert interval SLOT into three intervals. */
1320 split_interval_left (slot
, start
- slot
->position
);
1321 split_interval_right (slot
, length
);
1326 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1327 LENGTH is the length of the text in SOURCE.
1329 This is used in insdel.c when inserting Lisp_Strings into the
1330 buffer. The text corresponding to SOURCE is already in the buffer
1331 when this is called. The intervals of new tree are a copy of those
1332 belonging to the string being inserted; intervals are never
1335 If the inserted text had no intervals associated, and we don't
1336 want to inherit the surrounding text's properties, this function
1337 simply returns -- offset_intervals should handle placing the
1338 text in the correct interval, depending on the sticky bits.
1340 If the inserted text had properties (intervals), then there are two
1341 cases -- either insertion happened in the middle of some interval,
1342 or between two intervals.
1344 If the text goes into the middle of an interval, then new
1345 intervals are created in the middle with only the properties of
1346 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1347 which case the new text has the union of its properties and those
1348 of the text into which it was inserted.
1350 If the text goes between two intervals, then if neither interval
1351 had its appropriate sticky property set (front_sticky, rear_sticky),
1352 the new text has only its properties. If one of the sticky properties
1353 is set, then the new text "sticks" to that region and its properties
1354 depend on merging as above. If both the preceding and succeeding
1355 intervals to the new text are "sticky", then the new text retains
1356 only its properties, as if neither sticky property were set. Perhaps
1357 we should consider merging all three sets of properties onto the new
1361 graft_intervals_into_buffer (source
, position
, length
, buffer
, inherit
)
1363 int position
, length
;
1364 struct buffer
*buffer
;
1367 register INTERVAL under
, over
, this, prev
;
1368 register INTERVAL tree
= buffer
->intervals
;
1371 /* If the new text has no properties, it becomes part of whatever
1372 interval it was inserted into. */
1373 if (NULL_INTERVAL_P (source
))
1376 if (!inherit
&& ! NULL_INTERVAL_P (tree
))
1378 XSET (buf
, Lisp_Buffer
, buffer
);
1379 Fset_text_properties (make_number (position
),
1380 make_number (position
+ length
),
1383 if (! NULL_INTERVAL_P (buffer
->intervals
))
1384 buffer
->intervals
= balance_an_interval (buffer
->intervals
);
1388 if (NULL_INTERVAL_P (tree
))
1390 /* The inserted text constitutes the whole buffer, so
1391 simply copy over the interval structure. */
1392 if ((BUF_Z (buffer
) - BUF_BEG (buffer
)) == TOTAL_LENGTH (source
))
1395 XSET (buf
, Lisp_Buffer
, buffer
);
1396 buffer
->intervals
= reproduce_tree (source
, buf
);
1397 /* Explicitly free the old tree here. */
1402 /* Create an interval tree in which to place a copy
1403 of the intervals of the inserted string. */
1406 XSET (buf
, Lisp_Buffer
, buffer
);
1407 tree
= create_root_interval (buf
);
1410 else if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1411 /* If the buffer contains only the new string, but
1412 there was already some interval tree there, then it may be
1413 some zero length intervals. Eventually, do something clever
1414 about inserting properly. For now, just waste the old intervals. */
1416 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1417 /* Explicitly free the old tree here. */
1421 /* Paranoia -- the text has already been added, so this buffer
1422 should be of non-zero length. */
1423 else if (TOTAL_LENGTH (tree
) == 0)
1426 this = under
= find_interval (tree
, position
);
1427 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1429 over
= find_interval (source
, 1);
1431 /* Here for insertion in the middle of an interval.
1432 Split off an equivalent interval to the right,
1433 then don't bother with it any more. */
1435 if (position
> under
->position
)
1437 INTERVAL end_unchanged
1438 = split_interval_left (this, position
- under
->position
);
1439 copy_properties (under
, end_unchanged
);
1440 under
->position
= position
;
1446 prev
= previous_interval (under
);
1447 if (prev
&& !END_NONSTICKY_P (prev
))
1451 /* Insertion is now at beginning of UNDER. */
1453 /* The inserted text "sticks" to the interval `under',
1454 which means it gets those properties.
1455 The properties of under are the result of
1456 adjust_intervals_for_insertion, so stickyness has
1457 already been taken care of. */
1459 while (! NULL_INTERVAL_P (over
))
1461 if (LENGTH (over
) + 1 < LENGTH (under
))
1463 this = split_interval_left (under
, LENGTH (over
));
1464 copy_properties (under
, this);
1468 copy_properties (over
, this);
1470 merge_properties (over
, this);
1472 copy_properties (over
, this);
1473 over
= next_interval (over
);
1476 if (! NULL_INTERVAL_P (buffer
->intervals
))
1477 buffer
->intervals
= balance_an_interval (buffer
->intervals
);
1481 /* Get the value of property PROP from PLIST,
1482 which is the plist of an interval.
1483 We check for direct properties and for categories with property PROP. */
1486 textget (plist
, prop
)
1488 register Lisp_Object prop
;
1490 register Lisp_Object tail
, fallback
;
1493 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1495 register Lisp_Object tem
;
1498 return Fcar (Fcdr (tail
));
1499 if (EQ (tem
, Qcategory
))
1500 fallback
= Fget (Fcar (Fcdr (tail
)), prop
);
1506 /* Get the value of property PROP from PLIST,
1507 which is the plist of an interval.
1508 We check for direct properties only! */
1511 textget_direct (plist
, prop
)
1513 register Lisp_Object prop
;
1515 register Lisp_Object tail
;
1517 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1519 if (EQ (prop
, Fcar (tail
)))
1520 return Fcar (Fcdr (tail
));
1526 /* Set point in BUFFER to POSITION. If the target position is
1527 before an invisible character which is not displayed with a special glyph,
1528 move back to an ok place to display. */
1531 set_point (position
, buffer
)
1532 register int position
;
1533 register struct buffer
*buffer
;
1535 register INTERVAL to
, from
, toprev
, fromprev
, target
;
1537 register Lisp_Object obj
;
1538 int backwards
= (position
< BUF_PT (buffer
)) ? 1 : 0;
1539 int old_position
= buffer
->text
.pt
;
1541 if (position
== buffer
->text
.pt
)
1544 /* Check this now, before checking if the buffer has any intervals.
1545 That way, we can catch conditions which break this sanity check
1546 whether or not there are intervals in the buffer. */
1547 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1550 if (NULL_INTERVAL_P (buffer
->intervals
))
1552 buffer
->text
.pt
= position
;
1556 /* Set TO to the interval containing the char after POSITION,
1557 and TOPREV to the interval containing the char before POSITION.
1558 Either one may be null. They may be equal. */
1559 to
= find_interval (buffer
->intervals
, position
);
1560 if (position
== BUF_BEGV (buffer
))
1562 else if (to
->position
== position
)
1563 toprev
= previous_interval (to
);
1567 buffer_point
= (BUF_PT (buffer
) == BUF_ZV (buffer
)
1568 ? BUF_ZV (buffer
) - 1
1571 /* Set FROM to the interval containing the char after PT,
1572 and FROMPREV to the interval containing the char before PT.
1573 Either one may be null. They may be equal. */
1574 /* We could cache this and save time. */
1575 from
= find_interval (buffer
->intervals
, buffer_point
);
1576 if (buffer_point
== BUF_BEGV (buffer
))
1578 else if (from
->position
== BUF_PT (buffer
))
1579 fromprev
= previous_interval (from
);
1580 else if (buffer_point
!= BUF_PT (buffer
))
1581 fromprev
= from
, from
= 0;
1585 /* Moving within an interval. */
1586 if (to
== from
&& toprev
== fromprev
&& INTERVAL_VISIBLE_P (to
))
1588 buffer
->text
.pt
= position
;
1592 /* If the new position is before an invisible character
1593 that has an `invisible' property of value `hidden',
1594 move forward over all such. */
1595 while (! NULL_INTERVAL_P (to
)
1596 && EQ (textget (to
->plist
, Qinvisible
), Qhidden
)
1597 && ! DISPLAY_INVISIBLE_GLYPH (to
))
1600 to
= next_interval (to
);
1601 if (NULL_INTERVAL_P (to
))
1602 position
= BUF_ZV (buffer
);
1604 position
= to
->position
;
1607 buffer
->text
.pt
= position
;
1609 /* We run point-left and point-entered hooks here, iff the
1610 two intervals are not equivalent. These hooks take
1611 (old_point, new_point) as arguments. */
1612 if (NILP (Vinhibit_point_motion_hooks
)
1613 && (! intervals_equal (from
, to
)
1614 || ! intervals_equal (fromprev
, toprev
)))
1616 Lisp_Object leave_after
, leave_before
, enter_after
, enter_before
;
1619 leave_after
= textget (fromprev
->plist
, Qpoint_left
);
1623 leave_before
= textget (from
->plist
, Qpoint_left
);
1625 leave_before
= Qnil
;
1628 enter_after
= textget (toprev
->plist
, Qpoint_entered
);
1632 enter_before
= textget (to
->plist
, Qpoint_entered
);
1634 enter_before
= Qnil
;
1636 if (! EQ (leave_before
, enter_before
) && !NILP (leave_before
))
1637 call2 (leave_before
, old_position
, position
);
1638 if (! EQ (leave_after
, enter_after
) && !NILP (leave_after
))
1639 call2 (leave_after
, old_position
, position
);
1641 if (! EQ (enter_before
, leave_before
) && !NILP (enter_before
))
1642 call2 (enter_before
, old_position
, position
);
1643 if (! EQ (enter_after
, leave_after
) && !NILP (enter_after
))
1644 call2 (enter_after
, old_position
, position
);
1648 /* Set point temporarily, without checking any text properties. */
1651 temp_set_point (position
, buffer
)
1653 struct buffer
*buffer
;
1655 buffer
->text
.pt
= position
;
1658 /* Return the proper local map for position POSITION in BUFFER.
1659 Use the map specified by the local-map property, if any.
1660 Otherwise, use BUFFER's local map. */
1663 get_local_map (position
, buffer
)
1664 register int position
;
1665 register struct buffer
*buffer
;
1667 register INTERVAL interval
;
1668 Lisp_Object prop
, tem
;
1670 if (NULL_INTERVAL_P (buffer
->intervals
))
1671 return current_buffer
->keymap
;
1673 /* Perhaps we should just change `position' to the limit. */
1674 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1677 interval
= find_interval (buffer
->intervals
, position
);
1678 prop
= textget (interval
->plist
, Qlocal_map
);
1680 return current_buffer
->keymap
;
1682 /* Use the local map only if it is valid. */
1683 tem
= Fkeymapp (prop
);
1687 return current_buffer
->keymap
;
1690 /* Call the modification hook functions in LIST, each with START and END. */
1693 call_mod_hooks (list
, start
, end
)
1694 Lisp_Object list
, start
, end
;
1696 struct gcpro gcpro1
;
1698 while (!NILP (list
))
1700 call2 (Fcar (list
), start
, end
);
1706 /* Check for read-only intervals and signal an error if we find one.
1707 Then check for any modification hooks in the range START up to
1708 (but not including) TO. Create a list of all these hooks in
1709 lexicographic order, eliminating consecutive extra copies of the
1710 same hook. Then call those hooks in order, with START and END - 1
1714 verify_interval_modification (buf
, start
, end
)
1718 register INTERVAL intervals
= buf
->intervals
;
1719 register INTERVAL i
, prev
;
1721 register Lisp_Object prev_mod_hooks
;
1722 Lisp_Object mod_hooks
;
1723 struct gcpro gcpro1
;
1726 prev_mod_hooks
= Qnil
;
1729 if (NULL_INTERVAL_P (intervals
))
1739 /* For an insert operation, check the two chars around the position. */
1743 Lisp_Object before
, after
;
1745 /* Set I to the interval containing the char after START,
1746 and PREV to the interval containing the char before START.
1747 Either one may be null. They may be equal. */
1748 i
= find_interval (intervals
, start
);
1750 if (start
== BUF_BEGV (buf
))
1752 else if (i
->position
== start
)
1753 prev
= previous_interval (i
);
1754 else if (i
->position
< start
)
1756 if (start
== BUF_ZV (buf
))
1759 /* If Vinhibit_read_only is set and is not a list, we can
1760 skip the read_only checks. */
1761 if (NILP (Vinhibit_read_only
) || CONSP (Vinhibit_read_only
))
1763 /* If I and PREV differ we need to check for the read-only
1764 property together with its stickyness. If either I or
1765 PREV are 0, this check is all we need.
1766 We have to take special care, since read-only may be
1767 indirectly defined via the category property. */
1770 if (! NULL_INTERVAL_P (i
))
1772 after
= textget (i
->plist
, Qread_only
);
1774 /* If interval I is read-only and read-only is
1775 front-sticky, inhibit insertion.
1776 Check for read-only as well as category. */
1778 && NILP (Fmemq (after
, Vinhibit_read_only
))
1779 && (! NILP (Fmemq (Qread_only
,
1780 textget (i
->plist
, Qfront_sticky
)))
1781 || (NILP (textget_direct (i
->plist
, Qread_only
))
1782 && ! NILP (Fmemq (Qcategory
,
1785 error ("Attempt to insert within read-only text");
1789 if (! NULL_INTERVAL_P (prev
))
1791 before
= textget (prev
->plist
, Qread_only
);
1793 /* If interval PREV is read-only and read-only isn't
1794 rear-nonsticky, inhibit insertion.
1795 Check for read-only as well as category. */
1797 && NILP (Fmemq (before
, Vinhibit_read_only
))
1798 && NILP (Fmemq (Qread_only
,
1799 textget (prev
->plist
, Qrear_nonsticky
)))
1800 && (! NILP (textget_direct (prev
->plist
,Qread_only
))
1801 || NILP (Fmemq (Qcategory
,
1802 textget (prev
->plist
,
1803 Qrear_nonsticky
)))))
1804 error ("Attempt to insert within read-only text");
1809 else if (! NULL_INTERVAL_P (i
))
1810 before
= after
= textget (i
->plist
, Qread_only
);
1811 if (! NULL_INTERVAL_P (i
) && ! NULL_INTERVAL_P (prev
))
1813 /* If I and PREV differ, neither of them has a sticky
1814 read-only property. It only remains to check, whether
1815 they have a common read-only property. */
1816 if (! NILP (before
) && EQ (before
, after
))
1817 error ("Attempt to insert within read-only text");
1821 /* Run both insert hooks (just once if they're the same). */
1822 if (!NULL_INTERVAL_P (prev
))
1823 prev_mod_hooks
= textget (prev
->plist
, Qinsert_behind_hooks
);
1824 if (!NULL_INTERVAL_P (i
))
1825 mod_hooks
= textget (i
->plist
, Qinsert_in_front_hooks
);
1827 if (! NILP (prev_mod_hooks
))
1828 call_mod_hooks (prev_mod_hooks
, make_number (start
),
1831 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1832 call_mod_hooks (mod_hooks
, make_number (start
), make_number (end
));
1836 /* Loop over intervals on or next to START...END,
1837 collecting their hooks. */
1839 i
= find_interval (intervals
, start
);
1842 if (! INTERVAL_WRITABLE_P (i
))
1843 error ("Attempt to modify read-only text");
1845 mod_hooks
= textget (i
->plist
, Qmodification_hooks
);
1846 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1848 hooks
= Fcons (mod_hooks
, hooks
);
1849 prev_mod_hooks
= mod_hooks
;
1852 i
= next_interval (i
);
1854 /* Keep going thru the interval containing the char before END. */
1855 while (! NULL_INTERVAL_P (i
) && i
->position
< end
);
1858 hooks
= Fnreverse (hooks
);
1859 while (! EQ (hooks
, Qnil
))
1861 call_mod_hooks (Fcar (hooks
), make_number (start
),
1863 hooks
= Fcdr (hooks
);
1869 /* Produce an interval tree reflecting the intervals in
1870 TREE from START to START + LENGTH. */
1873 copy_intervals (tree
, start
, length
)
1877 register INTERVAL i
, new, t
;
1878 register int got
, prevlen
;
1880 if (NULL_INTERVAL_P (tree
) || length
<= 0)
1881 return NULL_INTERVAL
;
1883 i
= find_interval (tree
, start
);
1884 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
1887 /* If there is only one interval and it's the default, return nil. */
1888 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
1889 && DEFAULT_INTERVAL_P (i
))
1890 return NULL_INTERVAL
;
1892 new = make_interval ();
1894 got
= (LENGTH (i
) - (start
- i
->position
));
1895 new->total_length
= length
;
1896 copy_properties (i
, new);
1900 while (got
< length
)
1902 i
= next_interval (i
);
1903 t
= split_interval_right (t
, prevlen
);
1904 copy_properties (i
, t
);
1905 prevlen
= LENGTH (i
);
1909 return balance_an_interval (new);
1912 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1915 copy_intervals_to_string (string
, buffer
, position
, length
)
1916 Lisp_Object string
, buffer
;
1917 int position
, length
;
1919 INTERVAL interval_copy
= copy_intervals (XBUFFER (buffer
)->intervals
,
1921 if (NULL_INTERVAL_P (interval_copy
))
1924 interval_copy
->parent
= (INTERVAL
) string
;
1925 XSTRING (string
)->intervals
= interval_copy
;
1928 #endif /* USE_TEXT_PROPERTIES */