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
|
1164
|
348 /* Split INTERVAL into two pieces, starting the second piece at character
|
|
349 position OFFSET (counting from 1), relative to INTERVAL. The right-hand
|
|
350 piece (second, lexicographically) is returned.
|
|
351
|
|
352 The size and position fields of the two intervals are set based upon
|
|
353 those of the original interval. The property list of the new interval
|
|
354 is reset, thus it is up to the caller to do the right thing with the
|
|
355 result.
|
1157
|
356
|
|
357 Note that this does not change the position of INTERVAL; if it is a root,
|
|
358 it is still a root after this operation. */
|
|
359
|
|
360 INTERVAL
|
1164
|
361 split_interval_right (interval, offset)
|
1157
|
362 INTERVAL interval;
|
1164
|
363 int offset;
|
1157
|
364 {
|
|
365 INTERVAL new = make_interval ();
|
|
366 int position = interval->position;
|
1164
|
367 int new_length = LENGTH (interval) - offset + 1;
|
1157
|
368
|
1164
|
369 new->position = position + offset - 1;
|
1157
|
370 new->parent = interval;
|
|
371 #if 0
|
|
372 copy_properties (interval, new);
|
|
373 #endif
|
|
374
|
|
375 if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval))
|
|
376 {
|
|
377 interval->right = new;
|
|
378 new->total_length = new_length;
|
|
379
|
|
380 return new;
|
|
381 }
|
|
382
|
|
383 /* Insert the new node between INTERVAL and its right child. */
|
|
384 new->right = interval->right;
|
|
385 interval->right->parent = new;
|
|
386 interval->right = new;
|
|
387
|
|
388 new->total_length = new_length + new->right->total_length;
|
|
389
|
|
390 return new;
|
|
391 }
|
|
392
|
1164
|
393 /* Split INTERVAL into two pieces, starting the second piece at character
|
|
394 position OFFSET (counting from 1), relative to INTERVAL. The left-hand
|
|
395 piece (first, lexicographically) is returned.
|
1157
|
396
|
1164
|
397 The size and position fields of the two intervals are set based upon
|
|
398 those of the original interval. The property list of the new interval
|
|
399 is reset, thus it is up to the caller to do the right thing with the
|
|
400 result.
|
|
401
|
|
402 Note that this does not change the position of INTERVAL; if it is a root,
|
|
403 it is still a root after this operation. */
|
1157
|
404
|
|
405 INTERVAL
|
1164
|
406 split_interval_left (interval, offset)
|
1157
|
407 INTERVAL interval;
|
1164
|
408 int offset;
|
1157
|
409 {
|
|
410 INTERVAL new = make_interval ();
|
|
411 int position = interval->position;
|
1164
|
412 int new_length = offset - 1;
|
1157
|
413
|
|
414 #if 0
|
|
415 copy_properties (interval, new);
|
|
416 #endif
|
|
417
|
|
418 new->position = interval->position;
|
|
419
|
1164
|
420 interval->position = interval->position + offset - 1;
|
1157
|
421 new->parent = interval;
|
|
422
|
|
423 if (NULL_LEFT_CHILD (interval))
|
|
424 {
|
|
425 interval->left = new;
|
|
426 new->total_length = new_length;
|
|
427
|
|
428 return new;
|
|
429 }
|
|
430
|
|
431 /* Insert the new node between INTERVAL and its left child. */
|
|
432 new->left = interval->left;
|
|
433 new->left->parent = new;
|
|
434 interval->left = new;
|
|
435 new->total_length = LENGTH (new) + LEFT_TOTAL_LENGTH (new);
|
|
436
|
|
437 return new;
|
|
438 }
|
|
439
|
1164
|
440 /* Find the interval containing text position POSITION in the text
|
|
441 represented by the interval tree TREE. POSITION is relative to
|
|
442 the beginning of that text.
|
1157
|
443
|
1164
|
444 The `position' field, which is a cache of an interval's position,
|
|
445 is updated in the interval found. Other functions (e.g., next_interval)
|
|
446 will update this cache based on the result of find_interval. */
|
|
447
|
|
448 INLINE INTERVAL
|
1157
|
449 find_interval (tree, position)
|
|
450 register INTERVAL tree;
|
|
451 register int position;
|
|
452 {
|
|
453 register int relative_position = position;
|
|
454
|
|
455 if (NULL_INTERVAL_P (tree))
|
|
456 return NULL_INTERVAL;
|
|
457
|
|
458 if (position > TOTAL_LENGTH (tree))
|
|
459 abort (); /* Paranoia */
|
|
460 #if 0
|
|
461 position = TOTAL_LENGTH (tree);
|
|
462 #endif
|
|
463
|
|
464 while (1)
|
|
465 {
|
|
466 if (relative_position <= LEFT_TOTAL_LENGTH (tree))
|
|
467 {
|
|
468 tree = tree->left;
|
|
469 }
|
|
470 else if (relative_position > (TOTAL_LENGTH (tree)
|
|
471 - RIGHT_TOTAL_LENGTH (tree)))
|
|
472 {
|
|
473 relative_position -= (TOTAL_LENGTH (tree)
|
|
474 - RIGHT_TOTAL_LENGTH (tree));
|
|
475 tree = tree->right;
|
|
476 }
|
|
477 else
|
|
478 {
|
|
479 tree->position = LEFT_TOTAL_LENGTH (tree)
|
|
480 + position - relative_position + 1;
|
|
481 return tree;
|
|
482 }
|
|
483 }
|
|
484 }
|
|
485
|
|
486 /* Find the succeeding interval (lexicographically) to INTERVAL.
|
1164
|
487 Sets the `position' field based on that of INTERVAL (see
|
|
488 find_interval). */
|
1157
|
489
|
|
490 INTERVAL
|
|
491 next_interval (interval)
|
|
492 register INTERVAL interval;
|
|
493 {
|
|
494 register INTERVAL i = interval;
|
|
495 register int next_position;
|
|
496
|
|
497 if (NULL_INTERVAL_P (i))
|
|
498 return NULL_INTERVAL;
|
|
499 next_position = interval->position + LENGTH (interval);
|
|
500
|
|
501 if (! NULL_RIGHT_CHILD (i))
|
|
502 {
|
|
503 i = i->right;
|
|
504 while (! NULL_LEFT_CHILD (i))
|
|
505 i = i->left;
|
|
506
|
|
507 i->position = next_position;
|
|
508 return i;
|
|
509 }
|
|
510
|
|
511 while (! NULL_PARENT (i))
|
|
512 {
|
|
513 if (AM_LEFT_CHILD (i))
|
|
514 {
|
|
515 i = i->parent;
|
|
516 i->position = next_position;
|
|
517 return i;
|
|
518 }
|
|
519
|
|
520 i = i->parent;
|
|
521 }
|
|
522
|
|
523 return NULL_INTERVAL;
|
|
524 }
|
|
525
|
|
526 /* Find the preceding interval (lexicographically) to INTERVAL.
|
1164
|
527 Sets the `position' field based on that of INTERVAL (see
|
|
528 find_interval). */
|
1157
|
529
|
|
530 INTERVAL
|
|
531 previous_interval (interval)
|
|
532 register INTERVAL interval;
|
|
533 {
|
|
534 register INTERVAL i;
|
|
535 register position_of_previous;
|
|
536
|
|
537 if (NULL_INTERVAL_P (interval))
|
|
538 return NULL_INTERVAL;
|
|
539
|
|
540 if (! NULL_LEFT_CHILD (interval))
|
|
541 {
|
|
542 i = interval->left;
|
|
543 while (! NULL_RIGHT_CHILD (i))
|
|
544 i = i->right;
|
|
545
|
|
546 i->position = interval->position - LENGTH (i);
|
|
547 return i;
|
|
548 }
|
|
549
|
|
550 i = interval;
|
|
551 while (! NULL_PARENT (i))
|
|
552 {
|
|
553 if (AM_RIGHT_CHILD (i))
|
|
554 {
|
|
555 i = i->parent;
|
|
556
|
|
557 i->position = interval->position - LENGTH (i);
|
|
558 return i;
|
|
559 }
|
|
560 i = i->parent;
|
|
561 }
|
|
562
|
|
563 return NULL_INTERVAL;
|
|
564 }
|
|
565
|
1164
|
566 #if 0
|
1157
|
567 /* Traverse a path down the interval tree TREE to the interval
|
|
568 containing POSITION, adjusting all nodes on the path for
|
|
569 an addition of LENGTH characters. Insertion between two intervals
|
|
570 (i.e., point == i->position, where i is second interval) means
|
|
571 text goes into second interval.
|
|
572
|
|
573 Modifications are needed to handle the hungry bits -- after simply
|
|
574 finding the interval at position (don't add length going down),
|
|
575 if it's the beginning of the interval, get the previous interval
|
|
576 and check the hugry bits of both. Then add the length going back up
|
|
577 to the root. */
|
|
578
|
|
579 static INTERVAL
|
|
580 adjust_intervals_for_insertion (tree, position, length)
|
|
581 INTERVAL tree;
|
|
582 int position, length;
|
|
583 {
|
|
584 register int relative_position;
|
|
585 register INTERVAL this;
|
|
586
|
|
587 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
|
|
588 abort ();
|
|
589
|
|
590 /* If inserting at point-max of a buffer, that position
|
|
591 will be out of range */
|
|
592 if (position > TOTAL_LENGTH (tree))
|
|
593 position = TOTAL_LENGTH (tree);
|
|
594 relative_position = position;
|
|
595 this = tree;
|
|
596
|
|
597 while (1)
|
|
598 {
|
|
599 if (relative_position <= LEFT_TOTAL_LENGTH (this))
|
|
600 {
|
|
601 this->total_length += length;
|
|
602 this = this->left;
|
|
603 }
|
|
604 else if (relative_position > (TOTAL_LENGTH (this)
|
|
605 - RIGHT_TOTAL_LENGTH (this)))
|
|
606 {
|
|
607 relative_position -= (TOTAL_LENGTH (this)
|
|
608 - RIGHT_TOTAL_LENGTH (this));
|
|
609 this->total_length += length;
|
|
610 this = this->right;
|
|
611 }
|
|
612 else
|
|
613 {
|
|
614 /* If we are to use zero-length intervals as buffer pointers,
|
|
615 then this code will have to change. */
|
|
616 this->total_length += length;
|
|
617 this->position = LEFT_TOTAL_LENGTH (this)
|
|
618 + position - relative_position + 1;
|
|
619 return tree;
|
|
620 }
|
|
621 }
|
|
622 }
|
1164
|
623 #endif
|
|
624
|
|
625 /* Effect an adjustment corresponding to the addition of LENGTH characters
|
|
626 of text. Do this by finding the interval containing POSITION in the
|
|
627 interval tree TREE, and then adjusting all of it's ancestors by adding
|
|
628 LENGTH to them.
|
|
629
|
|
630 If POSITION is the first character of an interval, meaning that point
|
|
631 is actually between the two intervals, make the new text belong to
|
|
632 the interval which is "sticky".
|
|
633
|
1189
|
634 If both intervals are "sticky", then make them belong to the left-most
|
1164
|
635 interval. Another possibility would be to create a new interval for
|
|
636 this text, and make it have the merged properties of both ends. */
|
|
637
|
|
638 static INTERVAL
|
|
639 adjust_intervals_for_insertion (tree, position, length)
|
|
640 INTERVAL tree;
|
|
641 int position, length;
|
|
642 {
|
|
643 register INTERVAL i;
|
|
644
|
|
645 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
|
|
646 abort ();
|
|
647
|
|
648 /* If inserting at point-max of a buffer, that position
|
|
649 will be out of range. */
|
|
650 if (position > TOTAL_LENGTH (tree))
|
|
651 position = TOTAL_LENGTH (tree);
|
|
652
|
|
653 i = find_interval (tree, position);
|
|
654 /* If we are positioned between intervals, check the stickiness of
|
|
655 both of them. */
|
|
656 if (position == i->position
|
|
657 && position != 1)
|
|
658 {
|
|
659 register prev = previous_interval (i);
|
|
660
|
|
661 /* If both intervals are sticky here, then default to the
|
|
662 left-most one. But perhaps we should create a new
|
|
663 interval here instead... */
|
|
664 if (END_STICKY (prev))
|
|
665 i = prev;
|
|
666 }
|
|
667
|
|
668 while (! NULL_INTERVAL_P (i))
|
|
669 {
|
|
670 i->total_length += length;
|
|
671 i = i->parent
|
|
672 }
|
|
673
|
|
674 return tree;
|
|
675 }
|
1157
|
676
|
|
677 /* Merge interval I with its lexicographic successor. Note that
|
|
678 this does not deal with the properties, or delete I. */
|
|
679
|
|
680 INTERVAL
|
|
681 merge_interval_right (i)
|
|
682 register INTERVAL i;
|
|
683 {
|
|
684 register int absorb = LENGTH (i);
|
|
685
|
|
686 /* Zero out this interval. */
|
|
687 i->total_length -= absorb;
|
|
688
|
|
689 /* Find the succeeding interval. */
|
|
690 if (! NULL_RIGHT_CHILD (i)) /* It's below us. Add absorb
|
|
691 as we descend. */
|
|
692 {
|
|
693 i = i->right;
|
|
694 while (! NULL_LEFT_CHILD (i))
|
|
695 {
|
|
696 i->total_length += absorb;
|
|
697 i = i->left;
|
|
698 }
|
|
699
|
|
700 i->total_length += absorb;
|
|
701 return i;
|
|
702 }
|
|
703
|
|
704 while (! NULL_PARENT (i)) /* It's above us. Subtract as
|
|
705 we ascend. */
|
|
706 {
|
|
707 if (AM_LEFT_CHILD (i))
|
|
708 {
|
|
709 i = i->parent;
|
|
710 return i;
|
|
711 }
|
|
712
|
|
713 i = i->parent;
|
|
714 i->total_length -= absorb;
|
|
715 }
|
|
716
|
|
717 return NULL_INTERVAL;
|
|
718 }
|
|
719
|
|
720 /* Merge interval I with its lexicographic predecessor. Note that
|
|
721 this does not deal with the properties, or delete I.*/
|
|
722
|
|
723 INTERVAL
|
|
724 merge_interval_left (i)
|
|
725 register INTERVAL i;
|
|
726 {
|
|
727 register int absorb = LENGTH (i);
|
|
728
|
|
729 /* Zero out this interval. */
|
|
730 i->total_length -= absorb;
|
|
731
|
|
732 /* Find the preceding interval. */
|
|
733 if (! NULL_LEFT_CHILD (i)) /* It's below us. Go down,
|
|
734 adding ABSORB as we go. */
|
|
735 {
|
|
736 i = i->left;
|
|
737 while (! NULL_RIGHT_CHILD (i))
|
|
738 {
|
|
739 i->total_length += absorb;
|
|
740 i = i->right;
|
|
741 }
|
|
742
|
|
743 i->total_length += absorb;
|
|
744 return i;
|
|
745 }
|
|
746
|
|
747 while (! NULL_PARENT (i)) /* It's above us. Go up,
|
|
748 subtracting ABSORB. */
|
|
749 {
|
|
750 if (AM_RIGHT_CHILD (i))
|
|
751 {
|
|
752 i = i->parent;
|
|
753 return i;
|
|
754 }
|
|
755
|
|
756 i = i->parent;
|
|
757 i->total_length -= absorb;
|
|
758 }
|
|
759
|
|
760 return NULL_INTERVAL;
|
|
761 }
|
|
762
|
1164
|
763 /* Delete an node I from its interval tree by merging its subtrees
|
|
764 into one subtree which is then returned. Caller is responsible for
|
1157
|
765 storing the resulting subtree into its parent. */
|
|
766
|
|
767 static INTERVAL
|
|
768 delete_node (i)
|
|
769 register INTERVAL i;
|
|
770 {
|
|
771 register INTERVAL migrate, this;
|
|
772 register int migrate_amt;
|
|
773
|
|
774 if (NULL_INTERVAL_P (i->left))
|
|
775 return i->right;
|
|
776 if (NULL_INTERVAL_P (i->right))
|
|
777 return i->left;
|
|
778
|
|
779 migrate = i->left;
|
|
780 migrate_amt = i->left->total_length;
|
|
781 this = i->right;
|
|
782 this->total_length += migrate_amt;
|
|
783 while (! NULL_INTERVAL_P (this->left))
|
|
784 {
|
|
785 this = this->left;
|
|
786 this->total_length += migrate_amt;
|
|
787 }
|
|
788 this->left = migrate;
|
|
789 migrate->parent = this;
|
|
790
|
|
791 return i->right;
|
|
792 }
|
|
793
|
|
794 /* Delete interval I from its tree by calling `delete_node'
|
|
795 and properly connecting the resultant subtree.
|
|
796
|
|
797 I is presumed to be empty; that is, no adjustments are made
|
|
798 for the length of I. */
|
|
799
|
|
800 void
|
|
801 delete_interval (i)
|
|
802 register INTERVAL i;
|
|
803 {
|
|
804 register INTERVAL parent;
|
|
805 int amt = LENGTH (i);
|
|
806
|
|
807 if (amt > 0) /* Only used on zero-length intervals now. */
|
|
808 abort ();
|
|
809
|
|
810 if (ROOT_INTERVAL_P (i))
|
|
811 {
|
|
812 Lisp_Object owner = (Lisp_Object) i->parent;
|
|
813 parent = delete_node (i);
|
|
814 if (! NULL_INTERVAL_P (parent))
|
|
815 parent->parent = (INTERVAL) owner;
|
|
816
|
|
817 if (XTYPE (owner) == Lisp_Buffer)
|
|
818 XBUFFER (owner)->intervals = parent;
|
|
819 else if (XTYPE (owner) == Lisp_String)
|
|
820 XSTRING (owner)->intervals = parent;
|
|
821 else
|
|
822 abort ();
|
|
823
|
|
824 return;
|
|
825 }
|
|
826
|
|
827 parent = i->parent;
|
|
828 if (AM_LEFT_CHILD (i))
|
|
829 {
|
|
830 parent->left = delete_node (i);
|
|
831 if (! NULL_INTERVAL_P (parent->left))
|
|
832 parent->left->parent = parent;
|
|
833 }
|
|
834 else
|
|
835 {
|
|
836 parent->right = delete_node (i);
|
|
837 if (! NULL_INTERVAL_P (parent->right))
|
|
838 parent->right->parent = parent;
|
|
839 }
|
|
840 }
|
|
841
|
1189
|
842 /* Find the interval in TREE corresponding to the character position FROM
|
|
843 and delete as much as possible of AMOUNT from that interval, starting
|
|
844 after the relative position of FROM within it. Return the amount
|
|
845 actually deleted, and if the interval was zeroed-out, delete that
|
|
846 interval node from the tree.
|
1157
|
847
|
1189
|
848 Do this by recursing down TREE to the interval in question, and
|
|
849 deleting the appropriate amount of text. */
|
1157
|
850
|
|
851 static int
|
|
852 interval_deletion_adjustment (tree, from, amount)
|
|
853 register INTERVAL tree;
|
|
854 register int from, amount;
|
|
855 {
|
|
856 register int relative_position = from;
|
|
857
|
|
858 if (NULL_INTERVAL_P (tree))
|
|
859 return 0;
|
|
860
|
|
861 /* Left branch */
|
|
862 if (relative_position <= LEFT_TOTAL_LENGTH (tree))
|
|
863 {
|
|
864 int subtract = interval_deletion_adjustment (tree->left,
|
|
865 relative_position,
|
|
866 amount);
|
|
867 tree->total_length -= subtract;
|
|
868 return subtract;
|
|
869 }
|
|
870 /* Right branch */
|
|
871 else if (relative_position > (TOTAL_LENGTH (tree)
|
|
872 - RIGHT_TOTAL_LENGTH (tree)))
|
|
873 {
|
|
874 int subtract;
|
|
875
|
|
876 relative_position -= (tree->total_length
|
|
877 - RIGHT_TOTAL_LENGTH (tree));
|
|
878 subtract = interval_deletion_adjustment (tree->right,
|
|
879 relative_position,
|
|
880 amount);
|
|
881 tree->total_length -= subtract;
|
|
882 return subtract;
|
|
883 }
|
|
884 /* Here -- this node */
|
|
885 else
|
|
886 {
|
|
887 /* If this is a zero-length, marker interval, then
|
|
888 we must skip it. */
|
|
889
|
|
890 if (relative_position == LEFT_TOTAL_LENGTH (tree) + 1)
|
|
891 {
|
|
892 /* This means we're deleting from the beginning of this interval. */
|
|
893 register int my_amount = LENGTH (tree);
|
|
894
|
|
895 if (amount < my_amount)
|
|
896 {
|
|
897 tree->total_length -= amount;
|
|
898 return amount;
|
|
899 }
|
|
900 else
|
|
901 {
|
|
902 tree->total_length -= my_amount;
|
|
903 if (LENGTH (tree) != 0)
|
|
904 abort (); /* Paranoia */
|
|
905
|
|
906 delete_interval (tree);
|
|
907 return my_amount;
|
|
908 }
|
|
909 }
|
|
910 else /* Deleting starting in the middle. */
|
|
911 {
|
|
912 register int my_amount = ((tree->total_length
|
|
913 - RIGHT_TOTAL_LENGTH (tree))
|
|
914 - relative_position + 1);
|
|
915
|
|
916 if (amount <= my_amount)
|
|
917 {
|
|
918 tree->total_length -= amount;
|
|
919 return amount;
|
|
920 }
|
|
921 else
|
|
922 {
|
|
923 tree->total_length -= my_amount;
|
|
924 return my_amount;
|
|
925 }
|
|
926 }
|
|
927 }
|
|
928
|
1189
|
929 /* Never reach here */
|
1157
|
930 abort ();
|
|
931 }
|
|
932
|
1189
|
933 /* Effect the adjustments neccessary to the interval tree of BUFFER
|
|
934 to correspond to the deletion of LENGTH characters from that buffer
|
|
935 text. The deletion is effected at position START (relative to the
|
|
936 buffer). */
|
|
937
|
1157
|
938 static void
|
|
939 adjust_intervals_for_deletion (buffer, start, length)
|
|
940 struct buffer *buffer;
|
|
941 int start, length;
|
|
942 {
|
|
943 register int left_to_delete = length;
|
|
944 register INTERVAL tree = buffer->intervals;
|
|
945 register int deleted;
|
|
946
|
|
947 if (NULL_INTERVAL_P (tree))
|
|
948 return;
|
|
949
|
|
950 if (length == TOTAL_LENGTH (tree))
|
|
951 {
|
|
952 buffer->intervals = NULL_INTERVAL;
|
|
953 return;
|
|
954 }
|
|
955
|
|
956 if (ONLY_INTERVAL_P (tree))
|
|
957 {
|
|
958 tree->total_length -= length;
|
|
959 return;
|
|
960 }
|
|
961
|
|
962 if (start > TOTAL_LENGTH (tree))
|
|
963 start = TOTAL_LENGTH (tree);
|
|
964 while (left_to_delete > 0)
|
|
965 {
|
|
966 left_to_delete -= interval_deletion_adjustment (tree, start,
|
|
967 left_to_delete);
|
|
968 tree = buffer->intervals;
|
|
969 if (left_to_delete == tree->total_length)
|
|
970 {
|
|
971 buffer->intervals = NULL_INTERVAL;
|
|
972 return;
|
|
973 }
|
|
974 }
|
|
975 }
|
|
976
|
1189
|
977 /* Make the adjustments neccessary to the interval tree of BUFFER to
|
|
978 represent an addition or deletion of LENGTH characters starting
|
|
979 at position START. Addition or deletion is indicated by the sign
|
|
980 of LENGTH. */
|
1157
|
981
|
|
982 INLINE void
|
|
983 offset_intervals (buffer, start, length)
|
|
984 struct buffer *buffer;
|
|
985 int start, length;
|
|
986 {
|
|
987 if (NULL_INTERVAL_P (buffer->intervals) || length == 0)
|
|
988 return;
|
|
989
|
|
990 if (length > 0)
|
|
991 adjust_intervals_for_insertion (buffer->intervals, start, length);
|
|
992 else
|
|
993 adjust_intervals_for_deletion (buffer, start, -length);
|
|
994 }
|
|
995
|
1189
|
996 /* Make an exact copy of interval tree SOURCE which descends from
|
|
997 PARENT. This is done by recursing through SOURCE, copying
|
|
998 the current interval and its properties, and then adjusting
|
|
999 the pointers of the copy. */
|
|
1000
|
1157
|
1001 static INTERVAL
|
|
1002 reproduce_tree (source, parent)
|
|
1003 INTERVAL source, parent;
|
|
1004 {
|
|
1005 register INTERVAL t = make_interval ();
|
|
1006
|
|
1007 bcopy (source, t, INTERVAL_SIZE);
|
|
1008 copy_properties (source, t);
|
|
1009 t->parent = parent;
|
|
1010 if (! NULL_LEFT_CHILD (source))
|
|
1011 t->left = reproduce_tree (source->left, t);
|
|
1012 if (! NULL_RIGHT_CHILD (source))
|
|
1013 t->right = reproduce_tree (source->right, t);
|
|
1014
|
|
1015 return t;
|
|
1016 }
|
|
1017
|
1189
|
1018 /* Make a new interval of length LENGTH starting at START in the
|
|
1019 group of intervals INTERVALS, which is actually an interval tree.
|
|
1020 Returns the new interval.
|
|
1021
|
|
1022 Generate an error if the new positions would overlap an existing
|
|
1023 interval. */
|
|
1024
|
1157
|
1025 static INTERVAL
|
|
1026 make_new_interval (intervals, start, length)
|
|
1027 INTERVAL intervals;
|
|
1028 int start, length;
|
|
1029 {
|
|
1030 INTERVAL slot;
|
|
1031
|
|
1032 slot = find_interval (intervals, start);
|
|
1033 if (start + length > slot->position + LENGTH (slot))
|
|
1034 error ("Interval would overlap");
|
|
1035
|
|
1036 if (start == slot->position && length == LENGTH (slot))
|
|
1037 return slot;
|
|
1038
|
|
1039 if (slot->position == start)
|
|
1040 {
|
|
1041 /* New right node. */
|
|
1042 split_interval_right (slot, length + 1);
|
|
1043 return slot;
|
|
1044 }
|
|
1045
|
|
1046 if (slot->position + LENGTH (slot) == start + length)
|
|
1047 {
|
|
1048 /* New left node. */
|
|
1049 split_interval_left (slot, LENGTH (slot) - length + 1);
|
|
1050 return slot;
|
|
1051 }
|
|
1052
|
|
1053 /* Convert interval SLOT into three intervals. */
|
|
1054 split_interval_left (slot, start - slot->position + 1);
|
|
1055 split_interval_right (slot, length + 1);
|
|
1056 return slot;
|
|
1057 }
|
|
1058
|
|
1059 void
|
|
1060 map_intervals (source, destination, position)
|
|
1061 INTERVAL source, destination;
|
|
1062 int position;
|
|
1063 {
|
|
1064 register INTERVAL i, t;
|
|
1065
|
|
1066 if (NULL_INTERVAL_P (source))
|
|
1067 return;
|
|
1068 i = find_interval (destination, position);
|
|
1069 if (NULL_INTERVAL_P (i))
|
|
1070 return;
|
|
1071
|
|
1072 t = find_interval (source, 1);
|
|
1073 while (! NULL_INTERVAL_P (t))
|
|
1074 {
|
|
1075 i = make_new_interval (destination, position, LENGTH (t));
|
|
1076 position += LENGTH (t);
|
|
1077 copy_properties (t, i);
|
|
1078 t = next_interval (t);
|
|
1079 }
|
|
1080 }
|
|
1081
|
|
1082 /* Insert the intervals of NEW_TREE into BUFFER at POSITION.
|
|
1083
|
|
1084 This is used in insdel.c when inserting Lisp_Strings into
|
|
1085 the buffer. The text corresponding to NEW_TREE is already in
|
|
1086 the buffer when this is called. The intervals of new tree are
|
|
1087 those belonging to the string being inserted; a copy is not made.
|
|
1088
|
|
1089 If the inserted text had no intervals associated, this function
|
|
1090 simply returns -- offset_intervals should handle placing the
|
1164
|
1091 text in the correct interval, depending on the sticky bits.
|
1157
|
1092
|
|
1093 If the inserted text had properties (intervals), then there are two
|
|
1094 cases -- either insertion happened in the middle of some interval,
|
|
1095 or between two intervals.
|
|
1096
|
|
1097 If the text goes into the middle of an interval, then new
|
|
1098 intervals are created in the middle with only the properties of
|
|
1099 the new text, *unless* the macro MERGE_INSERTIONS is true, in
|
|
1100 which case the new text has the union of its properties and those
|
|
1101 of the text into which it was inserted.
|
|
1102
|
|
1103 If the text goes between two intervals, then if neither interval
|
1164
|
1104 had its appropriate sticky property set (front_sticky, rear_sticky),
|
|
1105 the new text has only its properties. If one of the sticky properties
|
1157
|
1106 is set, then the new text "sticks" to that region and its properties
|
|
1107 depend on merging as above. If both the preceding and succeding
|
1164
|
1108 intervals to the new text are "sticky", then the new text retains
|
|
1109 only its properties, as if neither sticky property were set. Perhaps
|
1157
|
1110 we should consider merging all three sets of properties onto the new
|
|
1111 text... */
|
|
1112
|
|
1113 void
|
|
1114 graft_intervals_into_buffer (new_tree, position, b)
|
|
1115 INTERVAL new_tree;
|
|
1116 int position;
|
|
1117 struct buffer *b;
|
|
1118 {
|
|
1119 register INTERVAL under, over, this;
|
|
1120 register INTERVAL tree = b->intervals;
|
|
1121
|
|
1122 /* If the new text has no properties, it becomes part of whatever
|
|
1123 interval it was inserted into. */
|
|
1124 if (NULL_INTERVAL_P (new_tree))
|
|
1125 return;
|
|
1126
|
|
1127 /* Paranoia -- the text has already been added, so this buffer
|
|
1128 should be of non-zero length. */
|
|
1129 if (TOTAL_LENGTH (tree) == 0)
|
|
1130 abort ();
|
|
1131
|
|
1132 if (NULL_INTERVAL_P (tree))
|
|
1133 {
|
|
1134 /* The inserted text constitutes the whole buffer, so
|
|
1135 simply copy over the interval structure. */
|
|
1136 if (BUF_Z (b) == TOTAL_LENGTH (new_tree))
|
|
1137 {
|
|
1138 b->intervals = reproduce_tree (new_tree, tree->parent);
|
|
1139 /* Explicitly free the old tree here. */
|
|
1140
|
|
1141 return;
|
|
1142 }
|
|
1143
|
|
1144 /* Create an interval tree in which to place a copy
|
|
1145 of the intervals of the inserted string. */
|
|
1146 {
|
|
1147 Lisp_Object buffer;
|
|
1148 XSET (buffer, Lisp_Buffer, b);
|
|
1149 create_root_interval (buffer);
|
|
1150 }
|
|
1151 }
|
|
1152 else
|
|
1153 if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (new_tree))
|
|
1154
|
|
1155 /* If the buffer contains only the new string, but
|
|
1156 there was already some interval tree there, then it may be
|
|
1157 some zero length intervals. Eventually, do something clever
|
|
1158 about inserting properly. For now, just waste the old intervals. */
|
|
1159 {
|
|
1160 b->intervals = reproduce_tree (new_tree, tree->parent);
|
|
1161 /* Explicitly free the old tree here. */
|
|
1162
|
|
1163 return;
|
|
1164 }
|
|
1165
|
|
1166 this = under = find_interval (tree, position);
|
|
1167 if (NULL_INTERVAL_P (under)) /* Paranoia */
|
|
1168 abort ();
|
|
1169 over = find_interval (new_tree, 1);
|
|
1170
|
|
1171 /* Insertion between intervals */
|
|
1172 if (position == under->position)
|
|
1173 {
|
|
1174 /* First interval -- none precede it. */
|
|
1175 if (position == 1)
|
|
1176 {
|
1164
|
1177 if (! FRONT_STICKY (under))
|
1157
|
1178 /* The inserted string keeps its own properties. */
|
|
1179 while (! NULL_INTERVAL_P (over))
|
|
1180 {
|
|
1181 position = LENGTH (over) + 1;
|
|
1182 this = split_interval_left (this, position);
|
|
1183 copy_properties (over, this);
|
|
1184 over = next_interval (over);
|
|
1185 }
|
|
1186 else
|
|
1187 /* This string sticks to under */
|
|
1188 while (! NULL_INTERVAL_P (over))
|
|
1189 {
|
|
1190 position = LENGTH (over) + 1;
|
|
1191 this = split_interval_left (this, position);
|
|
1192 copy_properties (under, this);
|
|
1193 if (MERGE_INSERTIONS (under))
|
|
1194 merge_properties (over, this);
|
|
1195 over = next_interval (over);
|
|
1196 }
|
|
1197 }
|
|
1198 else
|
|
1199 {
|
|
1200 INTERVAL prev = previous_interval (under);
|
|
1201 if (NULL_INTERVAL_P (prev))
|
|
1202 abort ();
|
|
1203
|
1164
|
1204 if (END_STICKY (prev))
|
1157
|
1205 {
|
1164
|
1206 if (FRONT_STICKY (under))
|
|
1207 /* The intervals go inbetween as the two sticky
|
1157
|
1208 properties cancel each other. Should we change
|
|
1209 this policy? */
|
|
1210 while (! NULL_INTERVAL_P (over))
|
|
1211 {
|
|
1212 position = LENGTH (over) + 1;
|
|
1213 this = split_interval_left (this, position);
|
|
1214 copy_properties (over, this);
|
|
1215 over = next_interval (over);
|
|
1216 }
|
|
1217 else
|
|
1218 /* The intervals stick to prev */
|
|
1219 while (! NULL_INTERVAL_P (over))
|
|
1220 {
|
|
1221 position = LENGTH (over) + 1;
|
|
1222 this = split_interval_left (this, position);
|
|
1223 copy_properties (prev, this);
|
|
1224 if (MERGE_INSERTIONS (prev))
|
|
1225 merge_properties (over, this);
|
|
1226 over = next_interval (over);
|
|
1227 }
|
|
1228 }
|
|
1229 else
|
|
1230 {
|
1164
|
1231 if (FRONT_STICKY (under))
|
1157
|
1232 /* The intervals stick to under */
|
|
1233 while (! NULL_INTERVAL_P (over))
|
|
1234 {
|
|
1235 position = LENGTH (over) + 1;
|
|
1236 this = split_interval_left (this, position);
|
|
1237 copy_properties (under, this);
|
|
1238 if (MERGE_INSERTIONS (under))
|
|
1239 merge_properties (over, this);
|
|
1240 over = next_interval (over);
|
|
1241 }
|
|
1242 else
|
|
1243 /* The intervals go inbetween */
|
|
1244 while (! NULL_INTERVAL_P (over))
|
|
1245 {
|
|
1246 position = LENGTH (over) + 1;
|
|
1247 this = split_interval_left (this, position);
|
|
1248 copy_properties (over, this);
|
|
1249 over = next_interval (over);
|
|
1250 }
|
|
1251 }
|
|
1252 }
|
|
1253
|
|
1254 b->intervals = balance_intervals (b->intervals);
|
|
1255 return;
|
|
1256 }
|
|
1257
|
|
1258 /* Here for insertion in the middle of an interval. */
|
|
1259
|
|
1260 if (TOTAL_LENGTH (new_tree) < LENGTH (this))
|
|
1261 {
|
|
1262 INTERVAL end_unchanged
|
|
1263 = split_interval_right (this, TOTAL_LENGTH (new_tree) + 1);
|
|
1264 copy_properties (under, end_unchanged);
|
|
1265 }
|
|
1266
|
|
1267 position = position - tree->position + 1;
|
|
1268 while (! NULL_INTERVAL_P (over))
|
|
1269 {
|
|
1270 this = split_interval_right (under, position);
|
|
1271 copy_properties (over, this);
|
|
1272 if (MERGE_INSERTIONS (under))
|
|
1273 merge_properties (under, this);
|
|
1274
|
|
1275 position = LENGTH (over) + 1;
|
|
1276 over = next_interval (over);
|
|
1277 }
|
|
1278
|
|
1279 b->intervals = balance_intervals (b->intervals);
|
|
1280 return;
|
|
1281 }
|
|
1282
|
|
1283 /* Intervals can have properties which are hooks to call. Look for
|
|
1284 the property HOOK on interval I, and if found, call its value as
|
|
1285 a function.*/
|
|
1286
|
|
1287 void
|
|
1288 run_hooks (i, hook)
|
|
1289 INTERVAL i;
|
|
1290 Lisp_Object hook;
|
|
1291 {
|
|
1292 register Lisp_Object tail = i->plist;
|
|
1293 register Lisp_Object sym, val;
|
|
1294
|
|
1295 while (! NILP (tail))
|
|
1296 {
|
|
1297 sym = Fcar (tail);
|
|
1298 if (EQ (sym, hook))
|
|
1299 {
|
|
1300 Lisp_Object begin, end;
|
|
1301 XFASTINT (begin) = i->position;
|
|
1302 XFASTINT (end) = i->position + LENGTH (i) - 1;
|
|
1303 val = Fcar (Fcdr (tail));
|
|
1304 call2 (val, begin, end);
|
|
1305 return;
|
|
1306 }
|
|
1307
|
|
1308 tail = Fcdr (Fcdr (tail));
|
|
1309 }
|
|
1310 }
|
|
1311
|
|
1312 /* Set point in BUFFER to POSITION. If the target position is in
|
|
1313 an invisible interval which is not displayed with a special glyph,
|
|
1314 skip intervals until we find one. Point may be at the first
|
|
1315 position of an invisible interval, if it is displayed with a
|
|
1316 special glyph.
|
|
1317
|
|
1318 This is the only place `PT' is an lvalue in all of emacs. */
|
|
1319
|
|
1320 void
|
|
1321 set_point (position, buffer)
|
|
1322 register int position;
|
|
1323 register struct buffer *buffer;
|
|
1324 {
|
|
1325 register INTERVAL to, from, target;
|
|
1326 register int iposition = position;
|
|
1327 int buffer_point;
|
|
1328 register Lisp_Object obj;
|
|
1329 int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
|
|
1330
|
|
1331 if (position == buffer->text.pt)
|
|
1332 return;
|
|
1333
|
|
1334 if (NULL_INTERVAL_P (buffer->intervals))
|
|
1335 {
|
|
1336 buffer->text.pt = position;
|
|
1337 return;
|
|
1338 }
|
|
1339
|
|
1340 /* Perhaps we should just change `position' to the limit. */
|
|
1341 if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
|
|
1342 abort ();
|
|
1343
|
|
1344 /* Position Z is really one past the last char in the buffer. */
|
|
1345 if (position == BUF_Z (buffer))
|
|
1346 iposition = position - 1;
|
|
1347
|
|
1348 to = find_interval (buffer->intervals, iposition);
|
|
1349 buffer_point =(BUF_PT (buffer) == BUF_Z (buffer)
|
|
1350 ? BUF_Z (buffer) - 1
|
|
1351 : BUF_PT (buffer));
|
|
1352 from = find_interval (buffer->intervals, buffer_point);
|
|
1353 if (NULL_INTERVAL_P (to) || NULL_INTERVAL_P (from))
|
|
1354 abort (); /* Paranoia */
|
|
1355
|
|
1356 /* Moving within an interval */
|
|
1357 if (to == from && INTERVAL_VISIBLE_P (to))
|
|
1358 {
|
|
1359 buffer->text.pt = position;
|
|
1360 return;
|
|
1361 }
|
|
1362
|
|
1363 /* Here for the case of moving into another interval. */
|
|
1364
|
|
1365 target = to;
|
|
1366 while (! INTERVAL_VISIBLE_P (to) && ! DISPLAY_INVISIBLE_GLYPH (to)
|
|
1367 && ! NULL_INTERVAL_P (to))
|
|
1368 to = (backwards ? previous_interval (to) : next_interval (to));
|
|
1369 if (NULL_INTERVAL_P (to))
|
|
1370 return;
|
|
1371
|
|
1372 /* Here we know we are actually moving to another interval. */
|
|
1373 if (INTERVAL_VISIBLE_P (to))
|
|
1374 {
|
|
1375 /* If we skipped some intervals, go to the closest point
|
|
1376 in the interval we've stopped at. */
|
|
1377 if (to != target)
|
|
1378 buffer->text.pt = (backwards
|
|
1379 ? to->position + LENGTH (to) - 1
|
|
1380 : to->position);
|
|
1381 else
|
|
1382 buffer->text.pt = position;
|
|
1383 }
|
|
1384 else
|
|
1385 buffer->text.pt = to->position;
|
|
1386
|
|
1387 /* We should run point-left and point-entered hooks here, iff the
|
|
1388 two intervals are not equivalent. */
|
|
1389 }
|
|
1390
|
|
1391 /* Check for read-only intervals. Call the modification hooks if any.
|
|
1392 Check for the range START up to (but not including) TO.
|
|
1393
|
|
1394 First all intervals of the region are checked that they are
|
|
1395 modifiable, then all the modification hooks are called in
|
|
1396 lexicographic order. */
|
|
1397
|
|
1398 void
|
|
1399 verify_interval_modification (buf, start, end)
|
|
1400 struct buffer *buf;
|
|
1401 int start, end;
|
|
1402 {
|
|
1403 register INTERVAL intervals = buf->intervals;
|
|
1404 register INTERVAL i;
|
|
1405 register Lisp_Object hooks = Qnil;
|
|
1406
|
|
1407 if (NULL_INTERVAL_P (intervals))
|
|
1408 return;
|
|
1409
|
|
1410 if (start > end)
|
|
1411 {
|
|
1412 int temp = start;
|
|
1413 start = end;
|
|
1414 end = temp;
|
|
1415 }
|
|
1416
|
|
1417 if (start == BUF_Z (buf))
|
|
1418 {
|
|
1419 if (BUF_Z (buf) == 1)
|
|
1420 abort ();
|
|
1421
|
|
1422 i = find_interval (intervals, start - 1);
|
1164
|
1423 if (! END_STICKY_P (i))
|
1157
|
1424 return;
|
|
1425 }
|
|
1426 else
|
|
1427 i = find_interval (intervals, start);
|
|
1428
|
|
1429 do
|
|
1430 {
|
|
1431 register Lisp_Object mod_hook;
|
|
1432 if (! INTERVAL_WRITABLE_P (i))
|
|
1433 error ("Attempt to write in a protected interval");
|
|
1434 mod_hook = Fget (Qmodification, i->plist);
|
|
1435 if (! EQ (mod_hook, Qnil))
|
|
1436 hooks = Fcons (mod_hook, hooks);
|
|
1437 i = next_interval (i);
|
|
1438 }
|
|
1439 while (! NULL_INTERVAL_P (i) && i->position <= end);
|
|
1440
|
|
1441 hooks = Fnreverse (hooks);
|
|
1442 while (! EQ (hooks, Qnil))
|
|
1443 call2 (Fcar (hooks), i->position, i->position + LENGTH (i) - 1);
|
|
1444 }
|
|
1445
|
|
1446 /* Balance an interval node if the amount of text in its left and right
|
|
1447 subtrees differs by more than the percentage specified by
|
|
1448 `interval-balance-threshold'. */
|
|
1449
|
|
1450 static INTERVAL
|
|
1451 balance_an_interval (i)
|
|
1452 INTERVAL i;
|
|
1453 {
|
|
1454 register int total_children_size = (LEFT_TOTAL_LENGTH (i)
|
|
1455 + RIGHT_TOTAL_LENGTH (i));
|
|
1456 register int threshold = (XFASTINT (interval_balance_threshold)
|
|
1457 * (total_children_size / 100));
|
|
1458
|
|
1459 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
|
|
1460 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
|
|
1461 return rotate_right (i);
|
|
1462
|
|
1463 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
|
|
1464 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
|
|
1465 return rotate_right (i);
|
|
1466
|
|
1467 #if 0
|
|
1468 if (LEFT_TOTAL_LENGTH (i) >
|
|
1469 (RIGHT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
|
|
1470 return rotate_right (i);
|
|
1471
|
|
1472 if (RIGHT_TOTAL_LENGTH (i) >
|
|
1473 (LEFT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
|
|
1474 return rotate_left (i);
|
|
1475 #endif
|
|
1476
|
|
1477 return i;
|
|
1478 }
|
|
1479
|
|
1480 /* Balance the interval tree TREE. Balancing is by weight
|
|
1481 (the amount of text). */
|
|
1482
|
|
1483 INTERVAL
|
|
1484 balance_intervals (tree)
|
|
1485 register INTERVAL tree;
|
|
1486 {
|
|
1487 register INTERVAL new_tree;
|
|
1488
|
|
1489 if (NULL_INTERVAL_P (tree))
|
|
1490 return NULL_INTERVAL;
|
|
1491
|
|
1492 new_tree = tree;
|
|
1493 do
|
|
1494 {
|
|
1495 tree = new_tree;
|
|
1496 new_tree = balance_an_interval (new_tree);
|
|
1497 }
|
|
1498 while (new_tree != tree);
|
|
1499
|
|
1500 return new_tree;
|
|
1501 }
|
|
1502
|
|
1503 /* Produce an interval tree reflecting the interval structure in
|
|
1504 TREE from START to START + LENGTH. */
|
|
1505
|
|
1506 static INTERVAL
|
|
1507 copy_intervals (tree, start, length)
|
|
1508 INTERVAL tree;
|
|
1509 int start, length;
|
|
1510 {
|
|
1511 register INTERVAL i, new, t;
|
|
1512 register int got;
|
|
1513
|
|
1514 if (NULL_INTERVAL_P (tree) || length <= 0)
|
|
1515 return NULL_INTERVAL;
|
|
1516
|
|
1517 i = find_interval (tree, start);
|
|
1518 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
|
|
1519 abort ();
|
|
1520
|
|
1521 /* If there is only one interval and it's the default, return nil. */
|
|
1522 if ((start - i->position + 1 + length) < LENGTH (i)
|
|
1523 && DEFAULT_INTERVAL_P (i))
|
|
1524 return NULL_INTERVAL;
|
|
1525
|
|
1526 new = make_interval ();
|
|
1527 new->position = 1;
|
|
1528 got = (LENGTH (i) - (start - i->position));
|
|
1529 new->total_length = got;
|
|
1530 copy_properties (i, new);
|
|
1531
|
|
1532 t = new;
|
|
1533 while (got < length)
|
|
1534 {
|
|
1535 i = next_interval (i);
|
|
1536 t->right = make_interval ();
|
|
1537 t->right->parent = t;
|
|
1538 t->right->position = t->position + got - 1;
|
|
1539
|
|
1540 t = t->right;
|
|
1541 t->total_length = length - got;
|
|
1542 copy_properties (i, t);
|
|
1543 got += LENGTH (i);
|
|
1544 }
|
|
1545
|
|
1546 if (got > length)
|
|
1547 t->total_length -= (got - length);
|
|
1548
|
|
1549 return balance_intervals (new);
|
|
1550 }
|
|
1551
|
|
1552 /* Give buffer SINK the properties of buffer SOURCE from POSITION
|
|
1553 to END. The properties are attached to SINK starting at position AT.
|
|
1554
|
|
1555 No range checking is done. */
|
|
1556
|
|
1557 void
|
|
1558 insert_interval_copy (source, position, end, sink, at)
|
|
1559 struct buffer *source, *sink;
|
|
1560 register int position, end, at;
|
|
1561 {
|
|
1562 INTERVAL interval_copy = copy_intervals (source->intervals,
|
|
1563 position, end - position);
|
|
1564 graft_intervals_into_buffer (interval_copy, at, sink);
|
|
1565 }
|
|
1566
|
|
1567 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
|
|
1568
|
|
1569 void
|
|
1570 copy_intervals_to_string (string, buffer, position, length)
|
|
1571 Lisp_Object string, buffer;
|
|
1572 int position, length;
|
|
1573 {
|
|
1574 INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals,
|
|
1575 position, length);
|
|
1576 if (NULL_INTERVAL_P (interval_copy))
|
|
1577 return;
|
|
1578
|
|
1579 interval_copy->parent = (INTERVAL) string;
|
|
1580 XSTRING (string)->intervals = interval_copy;
|
|
1581 }
|
|
1582
|
|
1583 INTERVAL
|
|
1584 make_string_interval (string, start, length)
|
|
1585 struct Lisp_String *string;
|
|
1586 int start, length;
|
|
1587 {
|
|
1588 if (start < 1 || start > string->size)
|
|
1589 error ("Interval index out of range");
|
|
1590 if (length < 1 || length > string->size - start + 1)
|
|
1591 error ("Interval won't fit");
|
|
1592
|
|
1593 if (length == 0)
|
|
1594 return NULL_INTERVAL;
|
|
1595
|
|
1596 return make_new_interval (string->intervals, start, length);
|
|
1597 }
|
|
1598
|
|
1599 /* Create an interval of length LENGTH in buffer BUF at position START. */
|
|
1600
|
|
1601 INTERVAL
|
|
1602 make_buffer_interval (buf, start, length)
|
|
1603 struct buffer *buf;
|
|
1604 int start, length;
|
|
1605 {
|
|
1606 if (start < BUF_BEG (buf) || start > BUF_Z (buf))
|
|
1607 error ("Interval index out of range");
|
|
1608 if (length < 1 || length > BUF_Z (buf) - start)
|
|
1609 error ("Interval won't fit");
|
|
1610
|
|
1611 if (length == 0)
|
|
1612 return NULL_INTERVAL;
|
|
1613
|
|
1614 return make_new_interval (buf->intervals, start, length);
|
|
1615 }
|