1157
|
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 }
|