Mercurial > emacs
comparison src/intervals.c @ 1157:a4a446feb297
Initial revision
author | Joseph Arceneaux <jla@gnu.org> |
---|---|
date | Thu, 17 Sep 1992 02:26:53 +0000 |
parents | |
children | adfaeccad01d |
comparison
equal
deleted
inserted
replaced
1156:2a92ddfaf6ba | 1157:a4a446feb297 |
---|---|
1 /* Code for doing intervals. | |
2 Copyright (C) 1991, 1992 Free Software Foundation, Inc. | |
3 | |
4 This file is part of GNU Emacs. | |
5 | |
6 GNU Emacs is free software; you can redistribute it and/or modify | |
7 it under the terms of the GNU General Public License as published by | |
8 the Free Software Foundation; either version 1, or (at your option) | |
9 any later version. | |
10 | |
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. | |
15 | |
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. */ | |
19 | |
20 | |
21 /* NOTES: | |
22 | |
23 Have to ensure that we can't put symbol nil on a plist, or some | |
24 functions may work incorrectly. | |
25 | |
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. | |
28 | |
29 Need to call *_left_hook when buffer is killed. | |
30 | |
31 Scan for zero-length, or 0-length to see notes about handling | |
32 zero length interval-markers. | |
33 | |
34 There are comments around about freeing intervals. It might be | |
35 faster to explicitly free them (put them on the free list) than | |
36 to GC them. | |
37 | |
38 */ | |
39 | |
40 | |
41 #include "config.h" | |
42 #include "lisp.h" | |
43 #include "intervals.h" | |
44 #include "buffer.h" | |
45 #include "screen.h" | |
46 | |
47 /* Factor for weight-balancing interval trees. */ | |
48 Lisp_Object interval_balance_threshold; | |
49 | |
50 /* Utility functions for intervals. */ | |
51 | |
52 | |
53 /* Create the root interval of some object, a buffer or string. */ | |
54 | |
55 INTERVAL | |
56 create_root_interval (parent) | |
57 Lisp_Object parent; | |
58 { | |
59 INTERVAL new = make_interval (); | |
60 | |
61 if (XTYPE (parent) == Lisp_Buffer) | |
62 { | |
63 new->total_length = BUF_Z (XBUFFER (parent)) - 1; | |
64 XBUFFER (parent)->intervals = new; | |
65 } | |
66 else if (XTYPE (parent) == Lisp_String) | |
67 { | |
68 new->total_length = XSTRING (parent)->size; | |
69 XSTRING (parent)->intervals = new; | |
70 } | |
71 | |
72 new->parent = (INTERVAL) parent; | |
73 new->position = 1; | |
74 | |
75 return new; | |
76 } | |
77 | |
78 /* Make the interval TARGET have exactly the properties of SOURCE */ | |
79 | |
80 void | |
81 copy_properties (source, target) | |
82 register INTERVAL source, target; | |
83 { | |
84 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target)) | |
85 return; | |
86 | |
87 COPY_INTERVAL_CACHE (source, target); | |
88 target->plist = Fcopy_sequence (source->plist); | |
89 } | |
90 | |
91 /* Merge the properties of interval SOURCE into the properties | |
92 of interval TARGET. */ | |
93 | |
94 static void | |
95 merge_properties (source, target) | |
96 register INTERVAL source, target; | |
97 { | |
98 register Lisp_Object o, sym, val; | |
99 | |
100 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target)) | |
101 return; | |
102 | |
103 MERGE_INTERVAL_CACHE (source, target); | |
104 | |
105 o = source->plist; | |
106 while (! EQ (o, Qnil)) | |
107 { | |
108 sym = Fcar (o); | |
109 val = Fmemq (sym, target->plist); | |
110 | |
111 if (NILP (val)) | |
112 { | |
113 o = Fcdr (o); | |
114 val = Fcar (o); | |
115 target->plist = Fcons (sym, Fcons (val, target->plist)); | |
116 o = Fcdr (o); | |
117 } | |
118 else | |
119 o = Fcdr (Fcdr (o)); | |
120 } | |
121 } | |
122 | |
123 /* Return 1 if the two intervals have the same properties, | |
124 0 otherwise. */ | |
125 | |
126 int | |
127 intervals_equal (i0, i1) | |
128 INTERVAL i0, i1; | |
129 { | |
130 register Lisp_Object i0_cdr, i0_sym, i1_val; | |
131 register i1_len; | |
132 | |
133 if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1)) | |
134 return 1; | |
135 | |
136 i1_len = XFASTINT (Flength (i1->plist)); | |
137 if (i1_len & 0x1) /* Paranoia -- plists are always even */ | |
138 abort (); | |
139 i1_len /= 2; | |
140 i0_cdr = i0->plist; | |
141 while (!NILP (i0_cdr)) | |
142 { | |
143 /* Lengths of the two plists were unequal */ | |
144 if (i1_len == 0) | |
145 return 0; | |
146 | |
147 i0_sym = Fcar (i0_cdr); | |
148 i1_val = Fmemq (i0_sym, i1->plist); | |
149 | |
150 /* i0 has something i1 doesn't */ | |
151 if (EQ (i1_val, Qnil)) | |
152 return 0; | |
153 | |
154 /* i0 and i1 both have sym, but it has different values in each */ | |
155 i0_cdr = Fcdr (i0_cdr); | |
156 if (! Fequal (i1_val, Fcar (i0_cdr))) | |
157 return 0; | |
158 | |
159 i0_cdr = Fcdr (i0_cdr); | |
160 i1_len--; | |
161 } | |
162 | |
163 /* Lengths of the two plists were unequal */ | |
164 if (i1_len > 0) | |
165 return 0; | |
166 | |
167 return 1; | |
168 } | |
169 | |
170 static int icount; | |
171 static int idepth; | |
172 static int zero_length; | |
173 | |
174 static int depth; | |
175 | |
176 /* Traverse an interval tree TREE, performing FUNCTION on each node. | |
177 | |
178 Perhaps we should pass the depth as an argument. */ | |
179 | |
180 void | |
181 traverse_intervals (tree, position, function) | |
182 INTERVAL tree; | |
183 int position; | |
184 void (* function) (); | |
185 { | |
186 if (NULL_INTERVAL_P (tree)) | |
187 return; | |
188 | |
189 depth++; | |
190 traverse_intervals (tree->left, position, function); | |
191 position += LEFT_TOTAL_LENGTH (tree); | |
192 tree->position = position; | |
193 (*function) (tree); | |
194 position += LENGTH (tree); | |
195 traverse_intervals (tree->right, position, function); | |
196 depth--; | |
197 } | |
198 | |
199 #if 0 | |
200 /* These functions are temporary, for debugging purposes only. */ | |
201 | |
202 INTERVAL search_interval, found_interval; | |
203 | |
204 void | |
205 check_for_interval (i) | |
206 register INTERVAL i; | |
207 { | |
208 if (i == search_interval) | |
209 { | |
210 found_interval = i; | |
211 icount++; | |
212 } | |
213 } | |
214 | |
215 INTERVAL | |
216 search_for_interval (i, tree) | |
217 register INTERVAL i, tree; | |
218 { | |
219 icount = 0; | |
220 search_interval = i; | |
221 found_interval = NULL_INTERVAL; | |
222 traverse_intervals (tree, 1, &check_for_interval); | |
223 return found_interval; | |
224 } | |
225 | |
226 static void | |
227 inc_interval_count (i) | |
228 INTERVAL i; | |
229 { | |
230 icount++; | |
231 if (LENGTH (i) == 0) | |
232 zero_length++; | |
233 if (depth > idepth) | |
234 idepth = depth; | |
235 } | |
236 | |
237 int | |
238 count_intervals (i) | |
239 register INTERVAL i; | |
240 { | |
241 icount = 0; | |
242 idepth = 0; | |
243 zero_length = 0; | |
244 traverse_intervals (i, 1, &inc_interval_count); | |
245 | |
246 return icount; | |
247 } | |
248 | |
249 static INTERVAL | |
250 root_interval (interval) | |
251 INTERVAL interval; | |
252 { | |
253 register INTERVAL i = interval; | |
254 | |
255 while (! ROOT_INTERVAL_P (i)) | |
256 i = i->parent; | |
257 | |
258 return i; | |
259 } | |
260 #endif | |
261 | |
262 /* Assuming that a left child exists, perform the following operation: | |
263 | |
264 A B | |
265 / \ / \ | |
266 B => A | |
267 / \ / \ | |
268 c c | |
269 */ | |
270 | |
271 static INTERVAL | |
272 rotate_right (interval) | |
273 INTERVAL interval; | |
274 { | |
275 INTERVAL i; | |
276 INTERVAL B = interval->left; | |
277 int len = LENGTH (interval); | |
278 | |
279 /* Deal with any Parent of A; make it point to B. */ | |
280 if (! ROOT_INTERVAL_P (interval)) | |
281 if (AM_LEFT_CHILD (interval)) | |
282 interval->parent->left = interval->left; | |
283 else | |
284 interval->parent->right = interval->left; | |
285 interval->left->parent = interval->parent; | |
286 | |
287 /* B gets the same length as A, since it get A's position in the tree. */ | |
288 interval->left->total_length = interval->total_length; | |
289 | |
290 /* B becomes the parent of A. */ | |
291 i = interval->left->right; | |
292 interval->left->right = interval; | |
293 interval->parent = interval->left; | |
294 | |
295 /* A gets c as left child. */ | |
296 interval->left = i; | |
297 if (! NULL_INTERVAL_P (i)) | |
298 i->parent = interval; | |
299 interval->total_length = (len + LEFT_TOTAL_LENGTH (interval) | |
300 + RIGHT_TOTAL_LENGTH (interval)); | |
301 | |
302 return B; | |
303 } | |
304 | |
305 /* Assuming that a right child exists, perform the following operation: | |
306 | |
307 A B | |
308 / \ / \ | |
309 B => A | |
310 / \ / \ | |
311 c c | |
312 */ | |
313 | |
314 static INTERVAL | |
315 rotate_left (interval) | |
316 INTERVAL interval; | |
317 { | |
318 INTERVAL i; | |
319 INTERVAL B = interval->right; | |
320 int len = LENGTH (interval); | |
321 | |
322 /* Deal with the parent of A. */ | |
323 if (! ROOT_INTERVAL_P (interval)) | |
324 if (AM_LEFT_CHILD (interval)) | |
325 interval->parent->left = interval->right; | |
326 else | |
327 interval->parent->right = interval->right; | |
328 interval->right->parent = interval->parent; | |
329 | |
330 /* B must have the same total length of A. */ | |
331 interval->right->total_length = interval->total_length; | |
332 | |
333 /* Make B the parent of A */ | |
334 i = interval->right->left; | |
335 interval->right->left = interval; | |
336 interval->parent = interval->right; | |
337 | |
338 /* Make A point to c */ | |
339 interval->right = i; | |
340 if (! NULL_INTERVAL_P (i)) | |
341 i->parent = interval; | |
342 interval->total_length = (len + LEFT_TOTAL_LENGTH (interval) | |
343 + RIGHT_TOTAL_LENGTH (interval)); | |
344 | |
345 return B; | |
346 } | |
347 | |
348 /* Split an interval into two. The second (RIGHT) half is returned as | |
349 the new interval. The size and position of the interval being split are | |
350 stored within it, having been found by find_interval (). The properties | |
351 are reset; it is up to the caller to do the right thing. | |
352 | |
353 Note that this does not change the position of INTERVAL; if it is a root, | |
354 it is still a root after this operation. */ | |
355 | |
356 INTERVAL | |
357 split_interval_right (interval, relative_position) | |
358 INTERVAL interval; | |
359 int relative_position; | |
360 { | |
361 INTERVAL new = make_interval (); | |
362 int position = interval->position; | |
363 int new_length = LENGTH (interval) - relative_position + 1; | |
364 | |
365 new->position = position + relative_position - 1; | |
366 new->parent = interval; | |
367 #if 0 | |
368 copy_properties (interval, new); | |
369 #endif | |
370 | |
371 if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval)) | |
372 { | |
373 interval->right = new; | |
374 new->total_length = new_length; | |
375 | |
376 return new; | |
377 } | |
378 | |
379 /* Insert the new node between INTERVAL and its right child. */ | |
380 new->right = interval->right; | |
381 interval->right->parent = new; | |
382 interval->right = new; | |
383 | |
384 new->total_length = new_length + new->right->total_length; | |
385 | |
386 return new; | |
387 } | |
388 | |
389 /* Split an interval into two. The first (LEFT) half is returned as | |
390 the new interval. The size and position of the interval being split | |
391 are stored within it, having been found by find_interval (). The | |
392 properties are reset; it is up to the caller to do the right thing. | |
393 | |
394 Note that this does not change the position of INTERVAL in the tree; if it | |
395 is a root, it is still a root after this operation. */ | |
396 | |
397 INTERVAL | |
398 split_interval_left (interval, relative_position) | |
399 INTERVAL interval; | |
400 int relative_position; | |
401 { | |
402 INTERVAL new = make_interval (); | |
403 int position = interval->position; | |
404 int new_length = relative_position - 1; | |
405 | |
406 #if 0 | |
407 copy_properties (interval, new); | |
408 #endif | |
409 | |
410 new->position = interval->position; | |
411 | |
412 interval->position = interval->position + relative_position - 1; | |
413 new->parent = interval; | |
414 | |
415 if (NULL_LEFT_CHILD (interval)) | |
416 { | |
417 interval->left = new; | |
418 new->total_length = new_length; | |
419 | |
420 return new; | |
421 } | |
422 | |
423 /* Insert the new node between INTERVAL and its left child. */ | |
424 new->left = interval->left; | |
425 new->left->parent = new; | |
426 interval->left = new; | |
427 new->total_length = LENGTH (new) + LEFT_TOTAL_LENGTH (new); | |
428 | |
429 return new; | |
430 } | |
431 | |
432 /* Find the interval containing POSITION in TREE. POSITION is relative | |
433 to the start of TREE. */ | |
434 | |
435 INTERVAL | |
436 find_interval (tree, position) | |
437 register INTERVAL tree; | |
438 register int position; | |
439 { | |
440 register int relative_position = position; | |
441 | |
442 if (NULL_INTERVAL_P (tree)) | |
443 return NULL_INTERVAL; | |
444 | |
445 if (position > TOTAL_LENGTH (tree)) | |
446 abort (); /* Paranoia */ | |
447 #if 0 | |
448 position = TOTAL_LENGTH (tree); | |
449 #endif | |
450 | |
451 while (1) | |
452 { | |
453 if (relative_position <= LEFT_TOTAL_LENGTH (tree)) | |
454 { | |
455 tree = tree->left; | |
456 } | |
457 else if (relative_position > (TOTAL_LENGTH (tree) | |
458 - RIGHT_TOTAL_LENGTH (tree))) | |
459 { | |
460 relative_position -= (TOTAL_LENGTH (tree) | |
461 - RIGHT_TOTAL_LENGTH (tree)); | |
462 tree = tree->right; | |
463 } | |
464 else | |
465 { | |
466 tree->position = LEFT_TOTAL_LENGTH (tree) | |
467 + position - relative_position + 1; | |
468 return tree; | |
469 } | |
470 } | |
471 } | |
472 | |
473 /* Find the succeeding interval (lexicographically) to INTERVAL. | |
474 Sets the `position' field based on that of INTERVAL. | |
475 | |
476 Note that those values are only correct if they were also correct | |
477 in INTERVAL. */ | |
478 | |
479 INTERVAL | |
480 next_interval (interval) | |
481 register INTERVAL interval; | |
482 { | |
483 register INTERVAL i = interval; | |
484 register int next_position; | |
485 | |
486 if (NULL_INTERVAL_P (i)) | |
487 return NULL_INTERVAL; | |
488 next_position = interval->position + LENGTH (interval); | |
489 | |
490 if (! NULL_RIGHT_CHILD (i)) | |
491 { | |
492 i = i->right; | |
493 while (! NULL_LEFT_CHILD (i)) | |
494 i = i->left; | |
495 | |
496 i->position = next_position; | |
497 return i; | |
498 } | |
499 | |
500 while (! NULL_PARENT (i)) | |
501 { | |
502 if (AM_LEFT_CHILD (i)) | |
503 { | |
504 i = i->parent; | |
505 i->position = next_position; | |
506 return i; | |
507 } | |
508 | |
509 i = i->parent; | |
510 } | |
511 | |
512 return NULL_INTERVAL; | |
513 } | |
514 | |
515 /* Find the preceding interval (lexicographically) to INTERVAL. | |
516 Sets the `position' field based on that of INTERVAL. | |
517 | |
518 Note that those values are only correct if they were also correct | |
519 in INTERVAL. */ | |
520 | |
521 INTERVAL | |
522 previous_interval (interval) | |
523 register INTERVAL interval; | |
524 { | |
525 register INTERVAL i; | |
526 register position_of_previous; | |
527 | |
528 if (NULL_INTERVAL_P (interval)) | |
529 return NULL_INTERVAL; | |
530 | |
531 if (! NULL_LEFT_CHILD (interval)) | |
532 { | |
533 i = interval->left; | |
534 while (! NULL_RIGHT_CHILD (i)) | |
535 i = i->right; | |
536 | |
537 i->position = interval->position - LENGTH (i); | |
538 return i; | |
539 } | |
540 | |
541 i = interval; | |
542 while (! NULL_PARENT (i)) | |
543 { | |
544 if (AM_RIGHT_CHILD (i)) | |
545 { | |
546 i = i->parent; | |
547 | |
548 i->position = interval->position - LENGTH (i); | |
549 return i; | |
550 } | |
551 i = i->parent; | |
552 } | |
553 | |
554 return NULL_INTERVAL; | |
555 } | |
556 | |
557 /* Traverse a path down the interval tree TREE to the interval | |
558 containing POSITION, adjusting all nodes on the path for | |
559 an addition of LENGTH characters. Insertion between two intervals | |
560 (i.e., point == i->position, where i is second interval) means | |
561 text goes into second interval. | |
562 | |
563 Modifications are needed to handle the hungry bits -- after simply | |
564 finding the interval at position (don't add length going down), | |
565 if it's the beginning of the interval, get the previous interval | |
566 and check the hugry bits of both. Then add the length going back up | |
567 to the root. */ | |
568 | |
569 static INTERVAL | |
570 adjust_intervals_for_insertion (tree, position, length) | |
571 INTERVAL tree; | |
572 int position, length; | |
573 { | |
574 register int relative_position; | |
575 register INTERVAL this; | |
576 | |
577 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */ | |
578 abort (); | |
579 | |
580 /* If inserting at point-max of a buffer, that position | |
581 will be out of range */ | |
582 if (position > TOTAL_LENGTH (tree)) | |
583 position = TOTAL_LENGTH (tree); | |
584 relative_position = position; | |
585 this = tree; | |
586 | |
587 while (1) | |
588 { | |
589 if (relative_position <= LEFT_TOTAL_LENGTH (this)) | |
590 { | |
591 this->total_length += length; | |
592 this = this->left; | |
593 } | |
594 else if (relative_position > (TOTAL_LENGTH (this) | |
595 - RIGHT_TOTAL_LENGTH (this))) | |
596 { | |
597 relative_position -= (TOTAL_LENGTH (this) | |
598 - RIGHT_TOTAL_LENGTH (this)); | |
599 this->total_length += length; | |
600 this = this->right; | |
601 } | |
602 else | |
603 { | |
604 /* If we are to use zero-length intervals as buffer pointers, | |
605 then this code will have to change. */ | |
606 this->total_length += length; | |
607 this->position = LEFT_TOTAL_LENGTH (this) | |
608 + position - relative_position + 1; | |
609 return tree; | |
610 } | |
611 } | |
612 } | |
613 | |
614 /* Merge interval I with its lexicographic successor. Note that | |
615 this does not deal with the properties, or delete I. */ | |
616 | |
617 INTERVAL | |
618 merge_interval_right (i) | |
619 register INTERVAL i; | |
620 { | |
621 register int absorb = LENGTH (i); | |
622 | |
623 /* Zero out this interval. */ | |
624 i->total_length -= absorb; | |
625 | |
626 /* Find the succeeding interval. */ | |
627 if (! NULL_RIGHT_CHILD (i)) /* It's below us. Add absorb | |
628 as we descend. */ | |
629 { | |
630 i = i->right; | |
631 while (! NULL_LEFT_CHILD (i)) | |
632 { | |
633 i->total_length += absorb; | |
634 i = i->left; | |
635 } | |
636 | |
637 i->total_length += absorb; | |
638 return i; | |
639 } | |
640 | |
641 while (! NULL_PARENT (i)) /* It's above us. Subtract as | |
642 we ascend. */ | |
643 { | |
644 if (AM_LEFT_CHILD (i)) | |
645 { | |
646 i = i->parent; | |
647 return i; | |
648 } | |
649 | |
650 i = i->parent; | |
651 i->total_length -= absorb; | |
652 } | |
653 | |
654 return NULL_INTERVAL; | |
655 } | |
656 | |
657 /* Merge interval I with its lexicographic predecessor. Note that | |
658 this does not deal with the properties, or delete I.*/ | |
659 | |
660 INTERVAL | |
661 merge_interval_left (i) | |
662 register INTERVAL i; | |
663 { | |
664 register int absorb = LENGTH (i); | |
665 | |
666 /* Zero out this interval. */ | |
667 i->total_length -= absorb; | |
668 | |
669 /* Find the preceding interval. */ | |
670 if (! NULL_LEFT_CHILD (i)) /* It's below us. Go down, | |
671 adding ABSORB as we go. */ | |
672 { | |
673 i = i->left; | |
674 while (! NULL_RIGHT_CHILD (i)) | |
675 { | |
676 i->total_length += absorb; | |
677 i = i->right; | |
678 } | |
679 | |
680 i->total_length += absorb; | |
681 return i; | |
682 } | |
683 | |
684 while (! NULL_PARENT (i)) /* It's above us. Go up, | |
685 subtracting ABSORB. */ | |
686 { | |
687 if (AM_RIGHT_CHILD (i)) | |
688 { | |
689 i = i->parent; | |
690 return i; | |
691 } | |
692 | |
693 i = i->parent; | |
694 i->total_length -= absorb; | |
695 } | |
696 | |
697 return NULL_INTERVAL; | |
698 } | |
699 | |
700 /* Delete an interval node from its btree by merging its subtrees | |
701 into one subtree which is returned. Caller is responsible for | |
702 storing the resulting subtree into its parent. */ | |
703 | |
704 static INTERVAL | |
705 delete_node (i) | |
706 register INTERVAL i; | |
707 { | |
708 register INTERVAL migrate, this; | |
709 register int migrate_amt; | |
710 | |
711 if (NULL_INTERVAL_P (i->left)) | |
712 return i->right; | |
713 if (NULL_INTERVAL_P (i->right)) | |
714 return i->left; | |
715 | |
716 migrate = i->left; | |
717 migrate_amt = i->left->total_length; | |
718 this = i->right; | |
719 this->total_length += migrate_amt; | |
720 while (! NULL_INTERVAL_P (this->left)) | |
721 { | |
722 this = this->left; | |
723 this->total_length += migrate_amt; | |
724 } | |
725 this->left = migrate; | |
726 migrate->parent = this; | |
727 | |
728 return i->right; | |
729 } | |
730 | |
731 /* Delete interval I from its tree by calling `delete_node' | |
732 and properly connecting the resultant subtree. | |
733 | |
734 I is presumed to be empty; that is, no adjustments are made | |
735 for the length of I. */ | |
736 | |
737 void | |
738 delete_interval (i) | |
739 register INTERVAL i; | |
740 { | |
741 register INTERVAL parent; | |
742 int amt = LENGTH (i); | |
743 | |
744 if (amt > 0) /* Only used on zero-length intervals now. */ | |
745 abort (); | |
746 | |
747 if (ROOT_INTERVAL_P (i)) | |
748 { | |
749 Lisp_Object owner = (Lisp_Object) i->parent; | |
750 parent = delete_node (i); | |
751 if (! NULL_INTERVAL_P (parent)) | |
752 parent->parent = (INTERVAL) owner; | |
753 | |
754 if (XTYPE (owner) == Lisp_Buffer) | |
755 XBUFFER (owner)->intervals = parent; | |
756 else if (XTYPE (owner) == Lisp_String) | |
757 XSTRING (owner)->intervals = parent; | |
758 else | |
759 abort (); | |
760 | |
761 return; | |
762 } | |
763 | |
764 parent = i->parent; | |
765 if (AM_LEFT_CHILD (i)) | |
766 { | |
767 parent->left = delete_node (i); | |
768 if (! NULL_INTERVAL_P (parent->left)) | |
769 parent->left->parent = parent; | |
770 } | |
771 else | |
772 { | |
773 parent->right = delete_node (i); | |
774 if (! NULL_INTERVAL_P (parent->right)) | |
775 parent->right->parent = parent; | |
776 } | |
777 } | |
778 | |
779 /* Recurse down to the interval containing FROM. Then delete as much | |
780 as possible (up to AMOUNT) from that interval, adjusting parental | |
781 intervals on the way up. If an interval is zeroed out, then | |
782 it is deleted. | |
783 | |
784 Returns the amount deleted. */ | |
785 | |
786 static int | |
787 interval_deletion_adjustment (tree, from, amount) | |
788 register INTERVAL tree; | |
789 register int from, amount; | |
790 { | |
791 register int relative_position = from; | |
792 | |
793 if (NULL_INTERVAL_P (tree)) | |
794 return 0; | |
795 | |
796 /* Left branch */ | |
797 if (relative_position <= LEFT_TOTAL_LENGTH (tree)) | |
798 { | |
799 int subtract = interval_deletion_adjustment (tree->left, | |
800 relative_position, | |
801 amount); | |
802 tree->total_length -= subtract; | |
803 return subtract; | |
804 } | |
805 /* Right branch */ | |
806 else if (relative_position > (TOTAL_LENGTH (tree) | |
807 - RIGHT_TOTAL_LENGTH (tree))) | |
808 { | |
809 int subtract; | |
810 | |
811 relative_position -= (tree->total_length | |
812 - RIGHT_TOTAL_LENGTH (tree)); | |
813 subtract = interval_deletion_adjustment (tree->right, | |
814 relative_position, | |
815 amount); | |
816 tree->total_length -= subtract; | |
817 return subtract; | |
818 } | |
819 /* Here -- this node */ | |
820 else | |
821 { | |
822 /* If this is a zero-length, marker interval, then | |
823 we must skip it. */ | |
824 | |
825 if (relative_position == LEFT_TOTAL_LENGTH (tree) + 1) | |
826 { | |
827 /* This means we're deleting from the beginning of this interval. */ | |
828 register int my_amount = LENGTH (tree); | |
829 | |
830 if (amount < my_amount) | |
831 { | |
832 tree->total_length -= amount; | |
833 return amount; | |
834 } | |
835 else | |
836 { | |
837 tree->total_length -= my_amount; | |
838 if (LENGTH (tree) != 0) | |
839 abort (); /* Paranoia */ | |
840 | |
841 delete_interval (tree); | |
842 return my_amount; | |
843 } | |
844 } | |
845 else /* Deleting starting in the middle. */ | |
846 { | |
847 register int my_amount = ((tree->total_length | |
848 - RIGHT_TOTAL_LENGTH (tree)) | |
849 - relative_position + 1); | |
850 | |
851 if (amount <= my_amount) | |
852 { | |
853 tree->total_length -= amount; | |
854 return amount; | |
855 } | |
856 else | |
857 { | |
858 tree->total_length -= my_amount; | |
859 return my_amount; | |
860 } | |
861 } | |
862 } | |
863 | |
864 abort (); | |
865 } | |
866 | |
867 static void | |
868 adjust_intervals_for_deletion (buffer, start, length) | |
869 struct buffer *buffer; | |
870 int start, length; | |
871 { | |
872 register int left_to_delete = length; | |
873 register INTERVAL tree = buffer->intervals; | |
874 register int deleted; | |
875 | |
876 if (NULL_INTERVAL_P (tree)) | |
877 return; | |
878 | |
879 if (length == TOTAL_LENGTH (tree)) | |
880 { | |
881 buffer->intervals = NULL_INTERVAL; | |
882 return; | |
883 } | |
884 | |
885 if (ONLY_INTERVAL_P (tree)) | |
886 { | |
887 tree->total_length -= length; | |
888 return; | |
889 } | |
890 | |
891 if (start > TOTAL_LENGTH (tree)) | |
892 start = TOTAL_LENGTH (tree); | |
893 while (left_to_delete > 0) | |
894 { | |
895 left_to_delete -= interval_deletion_adjustment (tree, start, | |
896 left_to_delete); | |
897 tree = buffer->intervals; | |
898 if (left_to_delete == tree->total_length) | |
899 { | |
900 buffer->intervals = NULL_INTERVAL; | |
901 return; | |
902 } | |
903 } | |
904 } | |
905 | |
906 /* Note that all intervals in OBJECT after START have slid by LENGTH. */ | |
907 | |
908 INLINE void | |
909 offset_intervals (buffer, start, length) | |
910 struct buffer *buffer; | |
911 int start, length; | |
912 { | |
913 if (NULL_INTERVAL_P (buffer->intervals) || length == 0) | |
914 return; | |
915 | |
916 if (length > 0) | |
917 adjust_intervals_for_insertion (buffer->intervals, start, length); | |
918 else | |
919 adjust_intervals_for_deletion (buffer, start, -length); | |
920 } | |
921 | |
922 static INTERVAL | |
923 reproduce_tree (source, parent) | |
924 INTERVAL source, parent; | |
925 { | |
926 register INTERVAL t = make_interval (); | |
927 | |
928 bcopy (source, t, INTERVAL_SIZE); | |
929 copy_properties (source, t); | |
930 t->parent = parent; | |
931 if (! NULL_LEFT_CHILD (source)) | |
932 t->left = reproduce_tree (source->left, t); | |
933 if (! NULL_RIGHT_CHILD (source)) | |
934 t->right = reproduce_tree (source->right, t); | |
935 | |
936 return t; | |
937 } | |
938 | |
939 static INTERVAL | |
940 make_new_interval (intervals, start, length) | |
941 INTERVAL intervals; | |
942 int start, length; | |
943 { | |
944 INTERVAL slot; | |
945 | |
946 slot = find_interval (intervals, start); | |
947 if (start + length > slot->position + LENGTH (slot)) | |
948 error ("Interval would overlap"); | |
949 | |
950 if (start == slot->position && length == LENGTH (slot)) | |
951 return slot; | |
952 | |
953 if (slot->position == start) | |
954 { | |
955 /* New right node. */ | |
956 split_interval_right (slot, length + 1); | |
957 return slot; | |
958 } | |
959 | |
960 if (slot->position + LENGTH (slot) == start + length) | |
961 { | |
962 /* New left node. */ | |
963 split_interval_left (slot, LENGTH (slot) - length + 1); | |
964 return slot; | |
965 } | |
966 | |
967 /* Convert interval SLOT into three intervals. */ | |
968 split_interval_left (slot, start - slot->position + 1); | |
969 split_interval_right (slot, length + 1); | |
970 return slot; | |
971 } | |
972 | |
973 void | |
974 map_intervals (source, destination, position) | |
975 INTERVAL source, destination; | |
976 int position; | |
977 { | |
978 register INTERVAL i, t; | |
979 | |
980 if (NULL_INTERVAL_P (source)) | |
981 return; | |
982 i = find_interval (destination, position); | |
983 if (NULL_INTERVAL_P (i)) | |
984 return; | |
985 | |
986 t = find_interval (source, 1); | |
987 while (! NULL_INTERVAL_P (t)) | |
988 { | |
989 i = make_new_interval (destination, position, LENGTH (t)); | |
990 position += LENGTH (t); | |
991 copy_properties (t, i); | |
992 t = next_interval (t); | |
993 } | |
994 } | |
995 | |
996 /* Insert the intervals of NEW_TREE into BUFFER at POSITION. | |
997 | |
998 This is used in insdel.c when inserting Lisp_Strings into | |
999 the buffer. The text corresponding to NEW_TREE is already in | |
1000 the buffer when this is called. The intervals of new tree are | |
1001 those belonging to the string being inserted; a copy is not made. | |
1002 | |
1003 If the inserted text had no intervals associated, this function | |
1004 simply returns -- offset_intervals should handle placing the | |
1005 text in the correct interval, depending on the hungry bits. | |
1006 | |
1007 If the inserted text had properties (intervals), then there are two | |
1008 cases -- either insertion happened in the middle of some interval, | |
1009 or between two intervals. | |
1010 | |
1011 If the text goes into the middle of an interval, then new | |
1012 intervals are created in the middle with only the properties of | |
1013 the new text, *unless* the macro MERGE_INSERTIONS is true, in | |
1014 which case the new text has the union of its properties and those | |
1015 of the text into which it was inserted. | |
1016 | |
1017 If the text goes between two intervals, then if neither interval | |
1018 had its appropriate hungry property set (front_hungry, rear_hungry), | |
1019 the new text has only its properties. If one of the hungry properties | |
1020 is set, then the new text "sticks" to that region and its properties | |
1021 depend on merging as above. If both the preceding and succeding | |
1022 intervals to the new text are "hungry", then the new text retains | |
1023 only its properties, as if neither hungry property were set. Perhaps | |
1024 we should consider merging all three sets of properties onto the new | |
1025 text... */ | |
1026 | |
1027 void | |
1028 graft_intervals_into_buffer (new_tree, position, b) | |
1029 INTERVAL new_tree; | |
1030 int position; | |
1031 struct buffer *b; | |
1032 { | |
1033 register INTERVAL under, over, this; | |
1034 register INTERVAL tree = b->intervals; | |
1035 | |
1036 /* If the new text has no properties, it becomes part of whatever | |
1037 interval it was inserted into. */ | |
1038 if (NULL_INTERVAL_P (new_tree)) | |
1039 return; | |
1040 | |
1041 /* Paranoia -- the text has already been added, so this buffer | |
1042 should be of non-zero length. */ | |
1043 if (TOTAL_LENGTH (tree) == 0) | |
1044 abort (); | |
1045 | |
1046 if (NULL_INTERVAL_P (tree)) | |
1047 { | |
1048 /* The inserted text constitutes the whole buffer, so | |
1049 simply copy over the interval structure. */ | |
1050 if (BUF_Z (b) == TOTAL_LENGTH (new_tree)) | |
1051 { | |
1052 b->intervals = reproduce_tree (new_tree, tree->parent); | |
1053 /* Explicitly free the old tree here. */ | |
1054 | |
1055 return; | |
1056 } | |
1057 | |
1058 /* Create an interval tree in which to place a copy | |
1059 of the intervals of the inserted string. */ | |
1060 { | |
1061 Lisp_Object buffer; | |
1062 XSET (buffer, Lisp_Buffer, b); | |
1063 create_root_interval (buffer); | |
1064 } | |
1065 } | |
1066 else | |
1067 if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (new_tree)) | |
1068 | |
1069 /* If the buffer contains only the new string, but | |
1070 there was already some interval tree there, then it may be | |
1071 some zero length intervals. Eventually, do something clever | |
1072 about inserting properly. For now, just waste the old intervals. */ | |
1073 { | |
1074 b->intervals = reproduce_tree (new_tree, tree->parent); | |
1075 /* Explicitly free the old tree here. */ | |
1076 | |
1077 return; | |
1078 } | |
1079 | |
1080 this = under = find_interval (tree, position); | |
1081 if (NULL_INTERVAL_P (under)) /* Paranoia */ | |
1082 abort (); | |
1083 over = find_interval (new_tree, 1); | |
1084 | |
1085 /* Insertion between intervals */ | |
1086 if (position == under->position) | |
1087 { | |
1088 /* First interval -- none precede it. */ | |
1089 if (position == 1) | |
1090 { | |
1091 if (! under->front_hungry) | |
1092 /* The inserted string keeps its own properties. */ | |
1093 while (! NULL_INTERVAL_P (over)) | |
1094 { | |
1095 position = LENGTH (over) + 1; | |
1096 this = split_interval_left (this, position); | |
1097 copy_properties (over, this); | |
1098 over = next_interval (over); | |
1099 } | |
1100 else | |
1101 /* This string sticks to under */ | |
1102 while (! NULL_INTERVAL_P (over)) | |
1103 { | |
1104 position = LENGTH (over) + 1; | |
1105 this = split_interval_left (this, position); | |
1106 copy_properties (under, this); | |
1107 if (MERGE_INSERTIONS (under)) | |
1108 merge_properties (over, this); | |
1109 over = next_interval (over); | |
1110 } | |
1111 } | |
1112 else | |
1113 { | |
1114 INTERVAL prev = previous_interval (under); | |
1115 if (NULL_INTERVAL_P (prev)) | |
1116 abort (); | |
1117 | |
1118 if (prev->rear_hungry) | |
1119 { | |
1120 if (under->front_hungry) | |
1121 /* The intervals go inbetween as the two hungry | |
1122 properties cancel each other. Should we change | |
1123 this policy? */ | |
1124 while (! NULL_INTERVAL_P (over)) | |
1125 { | |
1126 position = LENGTH (over) + 1; | |
1127 this = split_interval_left (this, position); | |
1128 copy_properties (over, this); | |
1129 over = next_interval (over); | |
1130 } | |
1131 else | |
1132 /* The intervals stick to prev */ | |
1133 while (! NULL_INTERVAL_P (over)) | |
1134 { | |
1135 position = LENGTH (over) + 1; | |
1136 this = split_interval_left (this, position); | |
1137 copy_properties (prev, this); | |
1138 if (MERGE_INSERTIONS (prev)) | |
1139 merge_properties (over, this); | |
1140 over = next_interval (over); | |
1141 } | |
1142 } | |
1143 else | |
1144 { | |
1145 if (under->front_hungry) | |
1146 /* The intervals stick to under */ | |
1147 while (! NULL_INTERVAL_P (over)) | |
1148 { | |
1149 position = LENGTH (over) + 1; | |
1150 this = split_interval_left (this, position); | |
1151 copy_properties (under, this); | |
1152 if (MERGE_INSERTIONS (under)) | |
1153 merge_properties (over, this); | |
1154 over = next_interval (over); | |
1155 } | |
1156 else | |
1157 /* The intervals go inbetween */ | |
1158 while (! NULL_INTERVAL_P (over)) | |
1159 { | |
1160 position = LENGTH (over) + 1; | |
1161 this = split_interval_left (this, position); | |
1162 copy_properties (over, this); | |
1163 over = next_interval (over); | |
1164 } | |
1165 } | |
1166 } | |
1167 | |
1168 b->intervals = balance_intervals (b->intervals); | |
1169 return; | |
1170 } | |
1171 | |
1172 /* Here for insertion in the middle of an interval. */ | |
1173 | |
1174 if (TOTAL_LENGTH (new_tree) < LENGTH (this)) | |
1175 { | |
1176 INTERVAL end_unchanged | |
1177 = split_interval_right (this, TOTAL_LENGTH (new_tree) + 1); | |
1178 copy_properties (under, end_unchanged); | |
1179 } | |
1180 | |
1181 position = position - tree->position + 1; | |
1182 while (! NULL_INTERVAL_P (over)) | |
1183 { | |
1184 this = split_interval_right (under, position); | |
1185 copy_properties (over, this); | |
1186 if (MERGE_INSERTIONS (under)) | |
1187 merge_properties (under, this); | |
1188 | |
1189 position = LENGTH (over) + 1; | |
1190 over = next_interval (over); | |
1191 } | |
1192 | |
1193 b->intervals = balance_intervals (b->intervals); | |
1194 return; | |
1195 } | |
1196 | |
1197 /* Intervals can have properties which are hooks to call. Look for | |
1198 the property HOOK on interval I, and if found, call its value as | |
1199 a function.*/ | |
1200 | |
1201 void | |
1202 run_hooks (i, hook) | |
1203 INTERVAL i; | |
1204 Lisp_Object hook; | |
1205 { | |
1206 register Lisp_Object tail = i->plist; | |
1207 register Lisp_Object sym, val; | |
1208 | |
1209 while (! NILP (tail)) | |
1210 { | |
1211 sym = Fcar (tail); | |
1212 if (EQ (sym, hook)) | |
1213 { | |
1214 Lisp_Object begin, end; | |
1215 XFASTINT (begin) = i->position; | |
1216 XFASTINT (end) = i->position + LENGTH (i) - 1; | |
1217 val = Fcar (Fcdr (tail)); | |
1218 call2 (val, begin, end); | |
1219 return; | |
1220 } | |
1221 | |
1222 tail = Fcdr (Fcdr (tail)); | |
1223 } | |
1224 } | |
1225 | |
1226 /* Set point in BUFFER to POSITION. If the target position is in | |
1227 an invisible interval which is not displayed with a special glyph, | |
1228 skip intervals until we find one. Point may be at the first | |
1229 position of an invisible interval, if it is displayed with a | |
1230 special glyph. | |
1231 | |
1232 This is the only place `PT' is an lvalue in all of emacs. */ | |
1233 | |
1234 void | |
1235 set_point (position, buffer) | |
1236 register int position; | |
1237 register struct buffer *buffer; | |
1238 { | |
1239 register INTERVAL to, from, target; | |
1240 register int iposition = position; | |
1241 int buffer_point; | |
1242 register Lisp_Object obj; | |
1243 int backwards = (position < BUF_PT (buffer)) ? 1 : 0; | |
1244 | |
1245 if (position == buffer->text.pt) | |
1246 return; | |
1247 | |
1248 if (NULL_INTERVAL_P (buffer->intervals)) | |
1249 { | |
1250 buffer->text.pt = position; | |
1251 return; | |
1252 } | |
1253 | |
1254 /* Perhaps we should just change `position' to the limit. */ | |
1255 if (position > BUF_Z (buffer) || position < BUF_BEG (buffer)) | |
1256 abort (); | |
1257 | |
1258 /* Position Z is really one past the last char in the buffer. */ | |
1259 if (position == BUF_Z (buffer)) | |
1260 iposition = position - 1; | |
1261 | |
1262 to = find_interval (buffer->intervals, iposition); | |
1263 buffer_point =(BUF_PT (buffer) == BUF_Z (buffer) | |
1264 ? BUF_Z (buffer) - 1 | |
1265 : BUF_PT (buffer)); | |
1266 from = find_interval (buffer->intervals, buffer_point); | |
1267 if (NULL_INTERVAL_P (to) || NULL_INTERVAL_P (from)) | |
1268 abort (); /* Paranoia */ | |
1269 | |
1270 /* Moving within an interval */ | |
1271 if (to == from && INTERVAL_VISIBLE_P (to)) | |
1272 { | |
1273 buffer->text.pt = position; | |
1274 return; | |
1275 } | |
1276 | |
1277 /* Here for the case of moving into another interval. */ | |
1278 | |
1279 target = to; | |
1280 while (! INTERVAL_VISIBLE_P (to) && ! DISPLAY_INVISIBLE_GLYPH (to) | |
1281 && ! NULL_INTERVAL_P (to)) | |
1282 to = (backwards ? previous_interval (to) : next_interval (to)); | |
1283 if (NULL_INTERVAL_P (to)) | |
1284 return; | |
1285 | |
1286 /* Here we know we are actually moving to another interval. */ | |
1287 if (INTERVAL_VISIBLE_P (to)) | |
1288 { | |
1289 /* If we skipped some intervals, go to the closest point | |
1290 in the interval we've stopped at. */ | |
1291 if (to != target) | |
1292 buffer->text.pt = (backwards | |
1293 ? to->position + LENGTH (to) - 1 | |
1294 : to->position); | |
1295 else | |
1296 buffer->text.pt = position; | |
1297 } | |
1298 else | |
1299 buffer->text.pt = to->position; | |
1300 | |
1301 /* We should run point-left and point-entered hooks here, iff the | |
1302 two intervals are not equivalent. */ | |
1303 } | |
1304 | |
1305 /* Check for read-only intervals. Call the modification hooks if any. | |
1306 Check for the range START up to (but not including) TO. | |
1307 | |
1308 First all intervals of the region are checked that they are | |
1309 modifiable, then all the modification hooks are called in | |
1310 lexicographic order. */ | |
1311 | |
1312 void | |
1313 verify_interval_modification (buf, start, end) | |
1314 struct buffer *buf; | |
1315 int start, end; | |
1316 { | |
1317 register INTERVAL intervals = buf->intervals; | |
1318 register INTERVAL i; | |
1319 register Lisp_Object hooks = Qnil; | |
1320 | |
1321 if (NULL_INTERVAL_P (intervals)) | |
1322 return; | |
1323 | |
1324 if (start > end) | |
1325 { | |
1326 int temp = start; | |
1327 start = end; | |
1328 end = temp; | |
1329 } | |
1330 | |
1331 if (start == BUF_Z (buf)) | |
1332 { | |
1333 if (BUF_Z (buf) == 1) | |
1334 abort (); | |
1335 | |
1336 i = find_interval (intervals, start - 1); | |
1337 if (! END_HUNGRY_P (i)) | |
1338 return; | |
1339 } | |
1340 else | |
1341 i = find_interval (intervals, start); | |
1342 | |
1343 do | |
1344 { | |
1345 register Lisp_Object mod_hook; | |
1346 if (! INTERVAL_WRITABLE_P (i)) | |
1347 error ("Attempt to write in a protected interval"); | |
1348 mod_hook = Fget (Qmodification, i->plist); | |
1349 if (! EQ (mod_hook, Qnil)) | |
1350 hooks = Fcons (mod_hook, hooks); | |
1351 i = next_interval (i); | |
1352 } | |
1353 while (! NULL_INTERVAL_P (i) && i->position <= end); | |
1354 | |
1355 hooks = Fnreverse (hooks); | |
1356 while (! EQ (hooks, Qnil)) | |
1357 call2 (Fcar (hooks), i->position, i->position + LENGTH (i) - 1); | |
1358 } | |
1359 | |
1360 /* Balance an interval node if the amount of text in its left and right | |
1361 subtrees differs by more than the percentage specified by | |
1362 `interval-balance-threshold'. */ | |
1363 | |
1364 static INTERVAL | |
1365 balance_an_interval (i) | |
1366 INTERVAL i; | |
1367 { | |
1368 register int total_children_size = (LEFT_TOTAL_LENGTH (i) | |
1369 + RIGHT_TOTAL_LENGTH (i)); | |
1370 register int threshold = (XFASTINT (interval_balance_threshold) | |
1371 * (total_children_size / 100)); | |
1372 | |
1373 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i) | |
1374 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold) | |
1375 return rotate_right (i); | |
1376 | |
1377 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i) | |
1378 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold) | |
1379 return rotate_right (i); | |
1380 | |
1381 #if 0 | |
1382 if (LEFT_TOTAL_LENGTH (i) > | |
1383 (RIGHT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold))) | |
1384 return rotate_right (i); | |
1385 | |
1386 if (RIGHT_TOTAL_LENGTH (i) > | |
1387 (LEFT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold))) | |
1388 return rotate_left (i); | |
1389 #endif | |
1390 | |
1391 return i; | |
1392 } | |
1393 | |
1394 /* Balance the interval tree TREE. Balancing is by weight | |
1395 (the amount of text). */ | |
1396 | |
1397 INTERVAL | |
1398 balance_intervals (tree) | |
1399 register INTERVAL tree; | |
1400 { | |
1401 register INTERVAL new_tree; | |
1402 | |
1403 if (NULL_INTERVAL_P (tree)) | |
1404 return NULL_INTERVAL; | |
1405 | |
1406 new_tree = tree; | |
1407 do | |
1408 { | |
1409 tree = new_tree; | |
1410 new_tree = balance_an_interval (new_tree); | |
1411 } | |
1412 while (new_tree != tree); | |
1413 | |
1414 return new_tree; | |
1415 } | |
1416 | |
1417 /* Produce an interval tree reflecting the interval structure in | |
1418 TREE from START to START + LENGTH. */ | |
1419 | |
1420 static INTERVAL | |
1421 copy_intervals (tree, start, length) | |
1422 INTERVAL tree; | |
1423 int start, length; | |
1424 { | |
1425 register INTERVAL i, new, t; | |
1426 register int got; | |
1427 | |
1428 if (NULL_INTERVAL_P (tree) || length <= 0) | |
1429 return NULL_INTERVAL; | |
1430 | |
1431 i = find_interval (tree, start); | |
1432 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0) | |
1433 abort (); | |
1434 | |
1435 /* If there is only one interval and it's the default, return nil. */ | |
1436 if ((start - i->position + 1 + length) < LENGTH (i) | |
1437 && DEFAULT_INTERVAL_P (i)) | |
1438 return NULL_INTERVAL; | |
1439 | |
1440 new = make_interval (); | |
1441 new->position = 1; | |
1442 got = (LENGTH (i) - (start - i->position)); | |
1443 new->total_length = got; | |
1444 copy_properties (i, new); | |
1445 | |
1446 t = new; | |
1447 while (got < length) | |
1448 { | |
1449 i = next_interval (i); | |
1450 t->right = make_interval (); | |
1451 t->right->parent = t; | |
1452 t->right->position = t->position + got - 1; | |
1453 | |
1454 t = t->right; | |
1455 t->total_length = length - got; | |
1456 copy_properties (i, t); | |
1457 got += LENGTH (i); | |
1458 } | |
1459 | |
1460 if (got > length) | |
1461 t->total_length -= (got - length); | |
1462 | |
1463 return balance_intervals (new); | |
1464 } | |
1465 | |
1466 /* Give buffer SINK the properties of buffer SOURCE from POSITION | |
1467 to END. The properties are attached to SINK starting at position AT. | |
1468 | |
1469 No range checking is done. */ | |
1470 | |
1471 void | |
1472 insert_interval_copy (source, position, end, sink, at) | |
1473 struct buffer *source, *sink; | |
1474 register int position, end, at; | |
1475 { | |
1476 INTERVAL interval_copy = copy_intervals (source->intervals, | |
1477 position, end - position); | |
1478 graft_intervals_into_buffer (interval_copy, at, sink); | |
1479 } | |
1480 | |
1481 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */ | |
1482 | |
1483 void | |
1484 copy_intervals_to_string (string, buffer, position, length) | |
1485 Lisp_Object string, buffer; | |
1486 int position, length; | |
1487 { | |
1488 INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals, | |
1489 position, length); | |
1490 if (NULL_INTERVAL_P (interval_copy)) | |
1491 return; | |
1492 | |
1493 interval_copy->parent = (INTERVAL) string; | |
1494 XSTRING (string)->intervals = interval_copy; | |
1495 } | |
1496 | |
1497 INTERVAL | |
1498 make_string_interval (string, start, length) | |
1499 struct Lisp_String *string; | |
1500 int start, length; | |
1501 { | |
1502 if (start < 1 || start > string->size) | |
1503 error ("Interval index out of range"); | |
1504 if (length < 1 || length > string->size - start + 1) | |
1505 error ("Interval won't fit"); | |
1506 | |
1507 if (length == 0) | |
1508 return NULL_INTERVAL; | |
1509 | |
1510 return make_new_interval (string->intervals, start, length); | |
1511 } | |
1512 | |
1513 /* Create an interval of length LENGTH in buffer BUF at position START. */ | |
1514 | |
1515 INTERVAL | |
1516 make_buffer_interval (buf, start, length) | |
1517 struct buffer *buf; | |
1518 int start, length; | |
1519 { | |
1520 if (start < BUF_BEG (buf) || start > BUF_Z (buf)) | |
1521 error ("Interval index out of range"); | |
1522 if (length < 1 || length > BUF_Z (buf) - start) | |
1523 error ("Interval won't fit"); | |
1524 | |
1525 if (length == 0) | |
1526 return NULL_INTERVAL; | |
1527 | |
1528 return make_new_interval (buf->intervals, start, length); | |
1529 } |