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
|
|
634 If both intervals are "stick", then make them belong to the left-most
|
|
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
|
|
842 /* Recurse down to the interval containing FROM. Then delete as much
|
|
843 as possible (up to AMOUNT) from that interval, adjusting parental
|
|
844 intervals on the way up. If an interval is zeroed out, then
|
|
845 it is deleted.
|
|
846
|
|
847 Returns the amount deleted. */
|
|
848
|
|
849 static int
|
|
850 interval_deletion_adjustment (tree, from, amount)
|
|
851 register INTERVAL tree;
|
|
852 register int from, amount;
|
|
853 {
|
|
854 register int relative_position = from;
|
|
855
|
|
856 if (NULL_INTERVAL_P (tree))
|
|
857 return 0;
|
|
858
|
|
859 /* Left branch */
|
|
860 if (relative_position <= LEFT_TOTAL_LENGTH (tree))
|
|
861 {
|
|
862 int subtract = interval_deletion_adjustment (tree->left,
|
|
863 relative_position,
|
|
864 amount);
|
|
865 tree->total_length -= subtract;
|
|
866 return subtract;
|
|
867 }
|
|
868 /* Right branch */
|
|
869 else if (relative_position > (TOTAL_LENGTH (tree)
|
|
870 - RIGHT_TOTAL_LENGTH (tree)))
|
|
871 {
|
|
872 int subtract;
|
|
873
|
|
874 relative_position -= (tree->total_length
|
|
875 - RIGHT_TOTAL_LENGTH (tree));
|
|
876 subtract = interval_deletion_adjustment (tree->right,
|
|
877 relative_position,
|
|
878 amount);
|
|
879 tree->total_length -= subtract;
|
|
880 return subtract;
|
|
881 }
|
|
882 /* Here -- this node */
|
|
883 else
|
|
884 {
|
|
885 /* If this is a zero-length, marker interval, then
|
|
886 we must skip it. */
|
|
887
|
|
888 if (relative_position == LEFT_TOTAL_LENGTH (tree) + 1)
|
|
889 {
|
|
890 /* This means we're deleting from the beginning of this interval. */
|
|
891 register int my_amount = LENGTH (tree);
|
|
892
|
|
893 if (amount < my_amount)
|
|
894 {
|
|
895 tree->total_length -= amount;
|
|
896 return amount;
|
|
897 }
|
|
898 else
|
|
899 {
|
|
900 tree->total_length -= my_amount;
|
|
901 if (LENGTH (tree) != 0)
|
|
902 abort (); /* Paranoia */
|
|
903
|
|
904 delete_interval (tree);
|
|
905 return my_amount;
|
|
906 }
|
|
907 }
|
|
908 else /* Deleting starting in the middle. */
|
|
909 {
|
|
910 register int my_amount = ((tree->total_length
|
|
911 - RIGHT_TOTAL_LENGTH (tree))
|
|
912 - relative_position + 1);
|
|
913
|
|
914 if (amount <= my_amount)
|
|
915 {
|
|
916 tree->total_length -= amount;
|
|
917 return amount;
|
|
918 }
|
|
919 else
|
|
920 {
|
|
921 tree->total_length -= my_amount;
|
|
922 return my_amount;
|
|
923 }
|
|
924 }
|
|
925 }
|
|
926
|
|
927 abort ();
|
|
928 }
|
|
929
|
|
930 static void
|
|
931 adjust_intervals_for_deletion (buffer, start, length)
|
|
932 struct buffer *buffer;
|
|
933 int start, length;
|
|
934 {
|
|
935 register int left_to_delete = length;
|
|
936 register INTERVAL tree = buffer->intervals;
|
|
937 register int deleted;
|
|
938
|
|
939 if (NULL_INTERVAL_P (tree))
|
|
940 return;
|
|
941
|
|
942 if (length == TOTAL_LENGTH (tree))
|
|
943 {
|
|
944 buffer->intervals = NULL_INTERVAL;
|
|
945 return;
|
|
946 }
|
|
947
|
|
948 if (ONLY_INTERVAL_P (tree))
|
|
949 {
|
|
950 tree->total_length -= length;
|
|
951 return;
|
|
952 }
|
|
953
|
|
954 if (start > TOTAL_LENGTH (tree))
|
|
955 start = TOTAL_LENGTH (tree);
|
|
956 while (left_to_delete > 0)
|
|
957 {
|
|
958 left_to_delete -= interval_deletion_adjustment (tree, start,
|
|
959 left_to_delete);
|
|
960 tree = buffer->intervals;
|
|
961 if (left_to_delete == tree->total_length)
|
|
962 {
|
|
963 buffer->intervals = NULL_INTERVAL;
|
|
964 return;
|
|
965 }
|
|
966 }
|
|
967 }
|
|
968
|
|
969 /* Note that all intervals in OBJECT after START have slid by LENGTH. */
|
|
970
|
|
971 INLINE void
|
|
972 offset_intervals (buffer, start, length)
|
|
973 struct buffer *buffer;
|
|
974 int start, length;
|
|
975 {
|
|
976 if (NULL_INTERVAL_P (buffer->intervals) || length == 0)
|
|
977 return;
|
|
978
|
|
979 if (length > 0)
|
|
980 adjust_intervals_for_insertion (buffer->intervals, start, length);
|
|
981 else
|
|
982 adjust_intervals_for_deletion (buffer, start, -length);
|
|
983 }
|
|
984
|
|
985 static INTERVAL
|
|
986 reproduce_tree (source, parent)
|
|
987 INTERVAL source, parent;
|
|
988 {
|
|
989 register INTERVAL t = make_interval ();
|
|
990
|
|
991 bcopy (source, t, INTERVAL_SIZE);
|
|
992 copy_properties (source, t);
|
|
993 t->parent = parent;
|
|
994 if (! NULL_LEFT_CHILD (source))
|
|
995 t->left = reproduce_tree (source->left, t);
|
|
996 if (! NULL_RIGHT_CHILD (source))
|
|
997 t->right = reproduce_tree (source->right, t);
|
|
998
|
|
999 return t;
|
|
1000 }
|
|
1001
|
|
1002 static INTERVAL
|
|
1003 make_new_interval (intervals, start, length)
|
|
1004 INTERVAL intervals;
|
|
1005 int start, length;
|
|
1006 {
|
|
1007 INTERVAL slot;
|
|
1008
|
|
1009 slot = find_interval (intervals, start);
|
|
1010 if (start + length > slot->position + LENGTH (slot))
|
|
1011 error ("Interval would overlap");
|
|
1012
|
|
1013 if (start == slot->position && length == LENGTH (slot))
|
|
1014 return slot;
|
|
1015
|
|
1016 if (slot->position == start)
|
|
1017 {
|
|
1018 /* New right node. */
|
|
1019 split_interval_right (slot, length + 1);
|
|
1020 return slot;
|
|
1021 }
|
|
1022
|
|
1023 if (slot->position + LENGTH (slot) == start + length)
|
|
1024 {
|
|
1025 /* New left node. */
|
|
1026 split_interval_left (slot, LENGTH (slot) - length + 1);
|
|
1027 return slot;
|
|
1028 }
|
|
1029
|
|
1030 /* Convert interval SLOT into three intervals. */
|
|
1031 split_interval_left (slot, start - slot->position + 1);
|
|
1032 split_interval_right (slot, length + 1);
|
|
1033 return slot;
|
|
1034 }
|
|
1035
|
|
1036 void
|
|
1037 map_intervals (source, destination, position)
|
|
1038 INTERVAL source, destination;
|
|
1039 int position;
|
|
1040 {
|
|
1041 register INTERVAL i, t;
|
|
1042
|
|
1043 if (NULL_INTERVAL_P (source))
|
|
1044 return;
|
|
1045 i = find_interval (destination, position);
|
|
1046 if (NULL_INTERVAL_P (i))
|
|
1047 return;
|
|
1048
|
|
1049 t = find_interval (source, 1);
|
|
1050 while (! NULL_INTERVAL_P (t))
|
|
1051 {
|
|
1052 i = make_new_interval (destination, position, LENGTH (t));
|
|
1053 position += LENGTH (t);
|
|
1054 copy_properties (t, i);
|
|
1055 t = next_interval (t);
|
|
1056 }
|
|
1057 }
|
|
1058
|
|
1059 /* Insert the intervals of NEW_TREE into BUFFER at POSITION.
|
|
1060
|
|
1061 This is used in insdel.c when inserting Lisp_Strings into
|
|
1062 the buffer. The text corresponding to NEW_TREE is already in
|
|
1063 the buffer when this is called. The intervals of new tree are
|
|
1064 those belonging to the string being inserted; a copy is not made.
|
|
1065
|
|
1066 If the inserted text had no intervals associated, this function
|
|
1067 simply returns -- offset_intervals should handle placing the
|
1164
|
1068 text in the correct interval, depending on the sticky bits.
|
1157
|
1069
|
|
1070 If the inserted text had properties (intervals), then there are two
|
|
1071 cases -- either insertion happened in the middle of some interval,
|
|
1072 or between two intervals.
|
|
1073
|
|
1074 If the text goes into the middle of an interval, then new
|
|
1075 intervals are created in the middle with only the properties of
|
|
1076 the new text, *unless* the macro MERGE_INSERTIONS is true, in
|
|
1077 which case the new text has the union of its properties and those
|
|
1078 of the text into which it was inserted.
|
|
1079
|
|
1080 If the text goes between two intervals, then if neither interval
|
1164
|
1081 had its appropriate sticky property set (front_sticky, rear_sticky),
|
|
1082 the new text has only its properties. If one of the sticky properties
|
1157
|
1083 is set, then the new text "sticks" to that region and its properties
|
|
1084 depend on merging as above. If both the preceding and succeding
|
1164
|
1085 intervals to the new text are "sticky", then the new text retains
|
|
1086 only its properties, as if neither sticky property were set. Perhaps
|
1157
|
1087 we should consider merging all three sets of properties onto the new
|
|
1088 text... */
|
|
1089
|
|
1090 void
|
|
1091 graft_intervals_into_buffer (new_tree, position, b)
|
|
1092 INTERVAL new_tree;
|
|
1093 int position;
|
|
1094 struct buffer *b;
|
|
1095 {
|
|
1096 register INTERVAL under, over, this;
|
|
1097 register INTERVAL tree = b->intervals;
|
|
1098
|
|
1099 /* If the new text has no properties, it becomes part of whatever
|
|
1100 interval it was inserted into. */
|
|
1101 if (NULL_INTERVAL_P (new_tree))
|
|
1102 return;
|
|
1103
|
|
1104 /* Paranoia -- the text has already been added, so this buffer
|
|
1105 should be of non-zero length. */
|
|
1106 if (TOTAL_LENGTH (tree) == 0)
|
|
1107 abort ();
|
|
1108
|
|
1109 if (NULL_INTERVAL_P (tree))
|
|
1110 {
|
|
1111 /* The inserted text constitutes the whole buffer, so
|
|
1112 simply copy over the interval structure. */
|
|
1113 if (BUF_Z (b) == TOTAL_LENGTH (new_tree))
|
|
1114 {
|
|
1115 b->intervals = reproduce_tree (new_tree, tree->parent);
|
|
1116 /* Explicitly free the old tree here. */
|
|
1117
|
|
1118 return;
|
|
1119 }
|
|
1120
|
|
1121 /* Create an interval tree in which to place a copy
|
|
1122 of the intervals of the inserted string. */
|
|
1123 {
|
|
1124 Lisp_Object buffer;
|
|
1125 XSET (buffer, Lisp_Buffer, b);
|
|
1126 create_root_interval (buffer);
|
|
1127 }
|
|
1128 }
|
|
1129 else
|
|
1130 if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (new_tree))
|
|
1131
|
|
1132 /* If the buffer contains only the new string, but
|
|
1133 there was already some interval tree there, then it may be
|
|
1134 some zero length intervals. Eventually, do something clever
|
|
1135 about inserting properly. For now, just waste the old intervals. */
|
|
1136 {
|
|
1137 b->intervals = reproduce_tree (new_tree, tree->parent);
|
|
1138 /* Explicitly free the old tree here. */
|
|
1139
|
|
1140 return;
|
|
1141 }
|
|
1142
|
|
1143 this = under = find_interval (tree, position);
|
|
1144 if (NULL_INTERVAL_P (under)) /* Paranoia */
|
|
1145 abort ();
|
|
1146 over = find_interval (new_tree, 1);
|
|
1147
|
|
1148 /* Insertion between intervals */
|
|
1149 if (position == under->position)
|
|
1150 {
|
|
1151 /* First interval -- none precede it. */
|
|
1152 if (position == 1)
|
|
1153 {
|
1164
|
1154 if (! FRONT_STICKY (under))
|
1157
|
1155 /* The inserted string keeps its own properties. */
|
|
1156 while (! NULL_INTERVAL_P (over))
|
|
1157 {
|
|
1158 position = LENGTH (over) + 1;
|
|
1159 this = split_interval_left (this, position);
|
|
1160 copy_properties (over, this);
|
|
1161 over = next_interval (over);
|
|
1162 }
|
|
1163 else
|
|
1164 /* This string sticks to under */
|
|
1165 while (! NULL_INTERVAL_P (over))
|
|
1166 {
|
|
1167 position = LENGTH (over) + 1;
|
|
1168 this = split_interval_left (this, position);
|
|
1169 copy_properties (under, this);
|
|
1170 if (MERGE_INSERTIONS (under))
|
|
1171 merge_properties (over, this);
|
|
1172 over = next_interval (over);
|
|
1173 }
|
|
1174 }
|
|
1175 else
|
|
1176 {
|
|
1177 INTERVAL prev = previous_interval (under);
|
|
1178 if (NULL_INTERVAL_P (prev))
|
|
1179 abort ();
|
|
1180
|
1164
|
1181 if (END_STICKY (prev))
|
1157
|
1182 {
|
1164
|
1183 if (FRONT_STICKY (under))
|
|
1184 /* The intervals go inbetween as the two sticky
|
1157
|
1185 properties cancel each other. Should we change
|
|
1186 this policy? */
|
|
1187 while (! NULL_INTERVAL_P (over))
|
|
1188 {
|
|
1189 position = LENGTH (over) + 1;
|
|
1190 this = split_interval_left (this, position);
|
|
1191 copy_properties (over, this);
|
|
1192 over = next_interval (over);
|
|
1193 }
|
|
1194 else
|
|
1195 /* The intervals stick to prev */
|
|
1196 while (! NULL_INTERVAL_P (over))
|
|
1197 {
|
|
1198 position = LENGTH (over) + 1;
|
|
1199 this = split_interval_left (this, position);
|
|
1200 copy_properties (prev, this);
|
|
1201 if (MERGE_INSERTIONS (prev))
|
|
1202 merge_properties (over, this);
|
|
1203 over = next_interval (over);
|
|
1204 }
|
|
1205 }
|
|
1206 else
|
|
1207 {
|
1164
|
1208 if (FRONT_STICKY (under))
|
1157
|
1209 /* The intervals stick to under */
|
|
1210 while (! NULL_INTERVAL_P (over))
|
|
1211 {
|
|
1212 position = LENGTH (over) + 1;
|
|
1213 this = split_interval_left (this, position);
|
|
1214 copy_properties (under, this);
|
|
1215 if (MERGE_INSERTIONS (under))
|
|
1216 merge_properties (over, this);
|
|
1217 over = next_interval (over);
|
|
1218 }
|
|
1219 else
|
|
1220 /* The intervals go inbetween */
|
|
1221 while (! NULL_INTERVAL_P (over))
|
|
1222 {
|
|
1223 position = LENGTH (over) + 1;
|
|
1224 this = split_interval_left (this, position);
|
|
1225 copy_properties (over, this);
|
|
1226 over = next_interval (over);
|
|
1227 }
|
|
1228 }
|
|
1229 }
|
|
1230
|
|
1231 b->intervals = balance_intervals (b->intervals);
|
|
1232 return;
|
|
1233 }
|
|
1234
|
|
1235 /* Here for insertion in the middle of an interval. */
|
|
1236
|
|
1237 if (TOTAL_LENGTH (new_tree) < LENGTH (this))
|
|
1238 {
|
|
1239 INTERVAL end_unchanged
|
|
1240 = split_interval_right (this, TOTAL_LENGTH (new_tree) + 1);
|
|
1241 copy_properties (under, end_unchanged);
|
|
1242 }
|
|
1243
|
|
1244 position = position - tree->position + 1;
|
|
1245 while (! NULL_INTERVAL_P (over))
|
|
1246 {
|
|
1247 this = split_interval_right (under, position);
|
|
1248 copy_properties (over, this);
|
|
1249 if (MERGE_INSERTIONS (under))
|
|
1250 merge_properties (under, this);
|
|
1251
|
|
1252 position = LENGTH (over) + 1;
|
|
1253 over = next_interval (over);
|
|
1254 }
|
|
1255
|
|
1256 b->intervals = balance_intervals (b->intervals);
|
|
1257 return;
|
|
1258 }
|
|
1259
|
|
1260 /* Intervals can have properties which are hooks to call. Look for
|
|
1261 the property HOOK on interval I, and if found, call its value as
|
|
1262 a function.*/
|
|
1263
|
|
1264 void
|
|
1265 run_hooks (i, hook)
|
|
1266 INTERVAL i;
|
|
1267 Lisp_Object hook;
|
|
1268 {
|
|
1269 register Lisp_Object tail = i->plist;
|
|
1270 register Lisp_Object sym, val;
|
|
1271
|
|
1272 while (! NILP (tail))
|
|
1273 {
|
|
1274 sym = Fcar (tail);
|
|
1275 if (EQ (sym, hook))
|
|
1276 {
|
|
1277 Lisp_Object begin, end;
|
|
1278 XFASTINT (begin) = i->position;
|
|
1279 XFASTINT (end) = i->position + LENGTH (i) - 1;
|
|
1280 val = Fcar (Fcdr (tail));
|
|
1281 call2 (val, begin, end);
|
|
1282 return;
|
|
1283 }
|
|
1284
|
|
1285 tail = Fcdr (Fcdr (tail));
|
|
1286 }
|
|
1287 }
|
|
1288
|
|
1289 /* Set point in BUFFER to POSITION. If the target position is in
|
|
1290 an invisible interval which is not displayed with a special glyph,
|
|
1291 skip intervals until we find one. Point may be at the first
|
|
1292 position of an invisible interval, if it is displayed with a
|
|
1293 special glyph.
|
|
1294
|
|
1295 This is the only place `PT' is an lvalue in all of emacs. */
|
|
1296
|
|
1297 void
|
|
1298 set_point (position, buffer)
|
|
1299 register int position;
|
|
1300 register struct buffer *buffer;
|
|
1301 {
|
|
1302 register INTERVAL to, from, target;
|
|
1303 register int iposition = position;
|
|
1304 int buffer_point;
|
|
1305 register Lisp_Object obj;
|
|
1306 int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
|
|
1307
|
|
1308 if (position == buffer->text.pt)
|
|
1309 return;
|
|
1310
|
|
1311 if (NULL_INTERVAL_P (buffer->intervals))
|
|
1312 {
|
|
1313 buffer->text.pt = position;
|
|
1314 return;
|
|
1315 }
|
|
1316
|
|
1317 /* Perhaps we should just change `position' to the limit. */
|
|
1318 if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
|
|
1319 abort ();
|
|
1320
|
|
1321 /* Position Z is really one past the last char in the buffer. */
|
|
1322 if (position == BUF_Z (buffer))
|
|
1323 iposition = position - 1;
|
|
1324
|
|
1325 to = find_interval (buffer->intervals, iposition);
|
|
1326 buffer_point =(BUF_PT (buffer) == BUF_Z (buffer)
|
|
1327 ? BUF_Z (buffer) - 1
|
|
1328 : BUF_PT (buffer));
|
|
1329 from = find_interval (buffer->intervals, buffer_point);
|
|
1330 if (NULL_INTERVAL_P (to) || NULL_INTERVAL_P (from))
|
|
1331 abort (); /* Paranoia */
|
|
1332
|
|
1333 /* Moving within an interval */
|
|
1334 if (to == from && INTERVAL_VISIBLE_P (to))
|
|
1335 {
|
|
1336 buffer->text.pt = position;
|
|
1337 return;
|
|
1338 }
|
|
1339
|
|
1340 /* Here for the case of moving into another interval. */
|
|
1341
|
|
1342 target = to;
|
|
1343 while (! INTERVAL_VISIBLE_P (to) && ! DISPLAY_INVISIBLE_GLYPH (to)
|
|
1344 && ! NULL_INTERVAL_P (to))
|
|
1345 to = (backwards ? previous_interval (to) : next_interval (to));
|
|
1346 if (NULL_INTERVAL_P (to))
|
|
1347 return;
|
|
1348
|
|
1349 /* Here we know we are actually moving to another interval. */
|
|
1350 if (INTERVAL_VISIBLE_P (to))
|
|
1351 {
|
|
1352 /* If we skipped some intervals, go to the closest point
|
|
1353 in the interval we've stopped at. */
|
|
1354 if (to != target)
|
|
1355 buffer->text.pt = (backwards
|
|
1356 ? to->position + LENGTH (to) - 1
|
|
1357 : to->position);
|
|
1358 else
|
|
1359 buffer->text.pt = position;
|
|
1360 }
|
|
1361 else
|
|
1362 buffer->text.pt = to->position;
|
|
1363
|
|
1364 /* We should run point-left and point-entered hooks here, iff the
|
|
1365 two intervals are not equivalent. */
|
|
1366 }
|
|
1367
|
|
1368 /* Check for read-only intervals. Call the modification hooks if any.
|
|
1369 Check for the range START up to (but not including) TO.
|
|
1370
|
|
1371 First all intervals of the region are checked that they are
|
|
1372 modifiable, then all the modification hooks are called in
|
|
1373 lexicographic order. */
|
|
1374
|
|
1375 void
|
|
1376 verify_interval_modification (buf, start, end)
|
|
1377 struct buffer *buf;
|
|
1378 int start, end;
|
|
1379 {
|
|
1380 register INTERVAL intervals = buf->intervals;
|
|
1381 register INTERVAL i;
|
|
1382 register Lisp_Object hooks = Qnil;
|
|
1383
|
|
1384 if (NULL_INTERVAL_P (intervals))
|
|
1385 return;
|
|
1386
|
|
1387 if (start > end)
|
|
1388 {
|
|
1389 int temp = start;
|
|
1390 start = end;
|
|
1391 end = temp;
|
|
1392 }
|
|
1393
|
|
1394 if (start == BUF_Z (buf))
|
|
1395 {
|
|
1396 if (BUF_Z (buf) == 1)
|
|
1397 abort ();
|
|
1398
|
|
1399 i = find_interval (intervals, start - 1);
|
1164
|
1400 if (! END_STICKY_P (i))
|
1157
|
1401 return;
|
|
1402 }
|
|
1403 else
|
|
1404 i = find_interval (intervals, start);
|
|
1405
|
|
1406 do
|
|
1407 {
|
|
1408 register Lisp_Object mod_hook;
|
|
1409 if (! INTERVAL_WRITABLE_P (i))
|
|
1410 error ("Attempt to write in a protected interval");
|
|
1411 mod_hook = Fget (Qmodification, i->plist);
|
|
1412 if (! EQ (mod_hook, Qnil))
|
|
1413 hooks = Fcons (mod_hook, hooks);
|
|
1414 i = next_interval (i);
|
|
1415 }
|
|
1416 while (! NULL_INTERVAL_P (i) && i->position <= end);
|
|
1417
|
|
1418 hooks = Fnreverse (hooks);
|
|
1419 while (! EQ (hooks, Qnil))
|
|
1420 call2 (Fcar (hooks), i->position, i->position + LENGTH (i) - 1);
|
|
1421 }
|
|
1422
|
|
1423 /* Balance an interval node if the amount of text in its left and right
|
|
1424 subtrees differs by more than the percentage specified by
|
|
1425 `interval-balance-threshold'. */
|
|
1426
|
|
1427 static INTERVAL
|
|
1428 balance_an_interval (i)
|
|
1429 INTERVAL i;
|
|
1430 {
|
|
1431 register int total_children_size = (LEFT_TOTAL_LENGTH (i)
|
|
1432 + RIGHT_TOTAL_LENGTH (i));
|
|
1433 register int threshold = (XFASTINT (interval_balance_threshold)
|
|
1434 * (total_children_size / 100));
|
|
1435
|
|
1436 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
|
|
1437 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
|
|
1438 return rotate_right (i);
|
|
1439
|
|
1440 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
|
|
1441 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
|
|
1442 return rotate_right (i);
|
|
1443
|
|
1444 #if 0
|
|
1445 if (LEFT_TOTAL_LENGTH (i) >
|
|
1446 (RIGHT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
|
|
1447 return rotate_right (i);
|
|
1448
|
|
1449 if (RIGHT_TOTAL_LENGTH (i) >
|
|
1450 (LEFT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
|
|
1451 return rotate_left (i);
|
|
1452 #endif
|
|
1453
|
|
1454 return i;
|
|
1455 }
|
|
1456
|
|
1457 /* Balance the interval tree TREE. Balancing is by weight
|
|
1458 (the amount of text). */
|
|
1459
|
|
1460 INTERVAL
|
|
1461 balance_intervals (tree)
|
|
1462 register INTERVAL tree;
|
|
1463 {
|
|
1464 register INTERVAL new_tree;
|
|
1465
|
|
1466 if (NULL_INTERVAL_P (tree))
|
|
1467 return NULL_INTERVAL;
|
|
1468
|
|
1469 new_tree = tree;
|
|
1470 do
|
|
1471 {
|
|
1472 tree = new_tree;
|
|
1473 new_tree = balance_an_interval (new_tree);
|
|
1474 }
|
|
1475 while (new_tree != tree);
|
|
1476
|
|
1477 return new_tree;
|
|
1478 }
|
|
1479
|
|
1480 /* Produce an interval tree reflecting the interval structure in
|
|
1481 TREE from START to START + LENGTH. */
|
|
1482
|
|
1483 static INTERVAL
|
|
1484 copy_intervals (tree, start, length)
|
|
1485 INTERVAL tree;
|
|
1486 int start, length;
|
|
1487 {
|
|
1488 register INTERVAL i, new, t;
|
|
1489 register int got;
|
|
1490
|
|
1491 if (NULL_INTERVAL_P (tree) || length <= 0)
|
|
1492 return NULL_INTERVAL;
|
|
1493
|
|
1494 i = find_interval (tree, start);
|
|
1495 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
|
|
1496 abort ();
|
|
1497
|
|
1498 /* If there is only one interval and it's the default, return nil. */
|
|
1499 if ((start - i->position + 1 + length) < LENGTH (i)
|
|
1500 && DEFAULT_INTERVAL_P (i))
|
|
1501 return NULL_INTERVAL;
|
|
1502
|
|
1503 new = make_interval ();
|
|
1504 new->position = 1;
|
|
1505 got = (LENGTH (i) - (start - i->position));
|
|
1506 new->total_length = got;
|
|
1507 copy_properties (i, new);
|
|
1508
|
|
1509 t = new;
|
|
1510 while (got < length)
|
|
1511 {
|
|
1512 i = next_interval (i);
|
|
1513 t->right = make_interval ();
|
|
1514 t->right->parent = t;
|
|
1515 t->right->position = t->position + got - 1;
|
|
1516
|
|
1517 t = t->right;
|
|
1518 t->total_length = length - got;
|
|
1519 copy_properties (i, t);
|
|
1520 got += LENGTH (i);
|
|
1521 }
|
|
1522
|
|
1523 if (got > length)
|
|
1524 t->total_length -= (got - length);
|
|
1525
|
|
1526 return balance_intervals (new);
|
|
1527 }
|
|
1528
|
|
1529 /* Give buffer SINK the properties of buffer SOURCE from POSITION
|
|
1530 to END. The properties are attached to SINK starting at position AT.
|
|
1531
|
|
1532 No range checking is done. */
|
|
1533
|
|
1534 void
|
|
1535 insert_interval_copy (source, position, end, sink, at)
|
|
1536 struct buffer *source, *sink;
|
|
1537 register int position, end, at;
|
|
1538 {
|
|
1539 INTERVAL interval_copy = copy_intervals (source->intervals,
|
|
1540 position, end - position);
|
|
1541 graft_intervals_into_buffer (interval_copy, at, sink);
|
|
1542 }
|
|
1543
|
|
1544 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
|
|
1545
|
|
1546 void
|
|
1547 copy_intervals_to_string (string, buffer, position, length)
|
|
1548 Lisp_Object string, buffer;
|
|
1549 int position, length;
|
|
1550 {
|
|
1551 INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals,
|
|
1552 position, length);
|
|
1553 if (NULL_INTERVAL_P (interval_copy))
|
|
1554 return;
|
|
1555
|
|
1556 interval_copy->parent = (INTERVAL) string;
|
|
1557 XSTRING (string)->intervals = interval_copy;
|
|
1558 }
|
|
1559
|
|
1560 INTERVAL
|
|
1561 make_string_interval (string, start, length)
|
|
1562 struct Lisp_String *string;
|
|
1563 int start, length;
|
|
1564 {
|
|
1565 if (start < 1 || start > string->size)
|
|
1566 error ("Interval index out of range");
|
|
1567 if (length < 1 || length > string->size - start + 1)
|
|
1568 error ("Interval won't fit");
|
|
1569
|
|
1570 if (length == 0)
|
|
1571 return NULL_INTERVAL;
|
|
1572
|
|
1573 return make_new_interval (string->intervals, start, length);
|
|
1574 }
|
|
1575
|
|
1576 /* Create an interval of length LENGTH in buffer BUF at position START. */
|
|
1577
|
|
1578 INTERVAL
|
|
1579 make_buffer_interval (buf, start, length)
|
|
1580 struct buffer *buf;
|
|
1581 int start, length;
|
|
1582 {
|
|
1583 if (start < BUF_BEG (buf) || start > BUF_Z (buf))
|
|
1584 error ("Interval index out of range");
|
|
1585 if (length < 1 || length > BUF_Z (buf) - start)
|
|
1586 error ("Interval won't fit");
|
|
1587
|
|
1588 if (length == 0)
|
|
1589 return NULL_INTERVAL;
|
|
1590
|
|
1591 return make_new_interval (buf->intervals, start, length);
|
|
1592 }
|