X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/7c92db56e023d20be00bb60a4d0e5814e9f334d7..2bc7a79bdc1e9bbbe8d50583313068e7db272a97:/src/intervals.c diff --git a/src/intervals.c b/src/intervals.c index 3d30e21c3e..0922a074a9 100644 --- a/src/intervals.c +++ b/src/intervals.c @@ -62,7 +62,8 @@ create_root_interval (parent) if (XTYPE (parent) == Lisp_Buffer) { - new->total_length = BUF_Z (XBUFFER (parent)) - 1; + new->total_length = (BUF_Z (XBUFFER (parent)) + - BUF_BEG (XBUFFER (parent))); XBUFFER (parent)->intervals = new; } else if (XTYPE (parent) == Lisp_String) @@ -159,7 +160,7 @@ intervals_equal (i0, i1) /* i0 and i1 both have sym, but it has different values in each */ i0_cdr = Fcdr (i0_cdr); - if (! Fequal (i1_val, Fcar (i0_cdr))) + if (! EQ (i1_val, Fcar (i0_cdr))) return 0; i0_cdr = Fcdr (i0_cdr); @@ -347,9 +348,10 @@ rotate_left (interval) return B; } -/* Split INTERVAL into two pieces, starting the second piece at character - position OFFSET (counting from 1), relative to INTERVAL. The right-hand - piece (second, lexicographically) is returned. +/* Split INTERVAL into two pieces, starting the second piece at + character position OFFSET (counting from 0), relative to INTERVAL. + INTERVAL becomes the left-hand piece, and the right-hand piece + (second, lexicographically) is returned. The size and position fields of the two intervals are set based upon those of the original interval. The property list of the new interval @@ -366,9 +368,9 @@ split_interval_right (interval, offset) { INTERVAL new = make_interval (); int position = interval->position; - int new_length = LENGTH (interval) - offset + 1; + int new_length = LENGTH (interval) - offset; - new->position = position + offset - 1; + new->position = position + offset; new->parent = interval; if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval)) @@ -389,9 +391,10 @@ split_interval_right (interval, offset) return new; } -/* Split INTERVAL into two pieces, starting the second piece at character - position OFFSET (counting from 1), relative to INTERVAL. The left-hand - piece (first, lexicographically) is returned. +/* Split INTERVAL into two pieces, starting the second piece at + character position OFFSET (counting from 0), relative to INTERVAL. + INTERVAL becomes the right-hand piece, and the left-hand piece + (first, lexicographically) is returned. The size and position fields of the two intervals are set based upon those of the original interval. The property list of the new interval @@ -408,10 +411,10 @@ split_interval_left (interval, offset) { INTERVAL new = make_interval (); int position = interval->position; - int new_length = offset - 1; + int new_length = offset; new->position = interval->position; - interval->position = interval->position + offset - 1; + interval->position = interval->position + offset; new->parent = interval; if (NULL_LEFT_CHILD (interval)) @@ -432,8 +435,9 @@ split_interval_left (interval, offset) } /* Find the interval containing text position POSITION in the text - represented by the interval tree TREE. POSITION is relative to - the beginning of that text. + represented by the interval tree TREE. POSITION is a buffer + position; the earliest position is 1. If POSITION is at the end of + the buffer, return the interval containing the last character. The `position' field, which is a cache of an interval's position, is updated in the interval found. Other functions (e.g., next_interval) @@ -444,25 +448,25 @@ find_interval (tree, position) register INTERVAL tree; register int position; { - register int relative_position = position; + /* The distance from the left edge of the subtree at TREE + to POSITION. */ + register int relative_position = position - BEG; if (NULL_INTERVAL_P (tree)) return NULL_INTERVAL; - if (position > TOTAL_LENGTH (tree)) + if (relative_position > TOTAL_LENGTH (tree)) abort (); /* Paranoia */ -#if 0 - position = TOTAL_LENGTH (tree); -#endif while (1) { - if (relative_position <= LEFT_TOTAL_LENGTH (tree)) + if (relative_position < LEFT_TOTAL_LENGTH (tree)) { tree = tree->left; } - else if (relative_position > (TOTAL_LENGTH (tree) - - RIGHT_TOTAL_LENGTH (tree))) + else if (! NULL_RIGHT_CHILD (tree) + && relative_position >= (TOTAL_LENGTH (tree) + - RIGHT_TOTAL_LENGTH (tree))) { relative_position -= (TOTAL_LENGTH (tree) - RIGHT_TOTAL_LENGTH (tree)); @@ -470,8 +474,10 @@ find_interval (tree, position) } else { - tree->position = LEFT_TOTAL_LENGTH (tree) - + position - relative_position + 1; + tree->position = + (position - relative_position /* the left edge of *tree */ + + LEFT_TOTAL_LENGTH (tree)); /* the left edge of this interval */ + return tree; } } @@ -639,16 +645,16 @@ adjust_intervals_for_insertion (tree, position, length) if (TOTAL_LENGTH (tree) == 0) /* Paranoia */ abort (); - /* If inserting at point-max of a buffer, that position - will be out of range. */ - if (position > TOTAL_LENGTH (tree)) - position = TOTAL_LENGTH (tree); + /* If inserting at point-max of a buffer, that position will be out + of range. Remember that buffer positions are 1-based. */ + if (position > BEG + TOTAL_LENGTH (tree)) + position = BEG + TOTAL_LENGTH (tree); i = find_interval (tree, position); /* If we are positioned between intervals, check the stickiness of both of them. */ if (position == i->position - && position != 1) + && position != BEG) { register INTERVAL prev = previous_interval (i); @@ -747,11 +753,14 @@ delete_interval (i) } } -/* Find the interval in TREE corresponding to the character position FROM - and delete as much as possible of AMOUNT from that interval, starting - after the relative position of FROM within it. Return the amount - actually deleted, and if the interval was zeroed-out, delete that - interval node from the tree. +/* Find the interval in TREE corresponding to the relative position + FROM and delete as much as possible of AMOUNT from that interval. + Return the amount actually deleted, and if the interval was + zeroed-out, delete that interval node from the tree. + + Note that FROM is actually origin zero, aka relative to the + leftmost edge of tree. This is appropriate since we call ourselves + recursively on subtrees. Do this by recursing down TREE to the interval in question, and deleting the appropriate amount of text. */ @@ -767,7 +776,7 @@ interval_deletion_adjustment (tree, from, amount) return 0; /* Left branch */ - if (relative_position <= LEFT_TOTAL_LENGTH (tree)) + if (relative_position < LEFT_TOTAL_LENGTH (tree)) { int subtract = interval_deletion_adjustment (tree->left, relative_position, @@ -776,8 +785,8 @@ interval_deletion_adjustment (tree, from, amount) return subtract; } /* Right branch */ - else if (relative_position > (TOTAL_LENGTH (tree) - - RIGHT_TOTAL_LENGTH (tree))) + else if (relative_position >= (TOTAL_LENGTH (tree) + - RIGHT_TOTAL_LENGTH (tree))) { int subtract; @@ -792,55 +801,28 @@ interval_deletion_adjustment (tree, from, amount) /* Here -- this node */ else { - /* If this is a zero-length, marker interval, then - we must skip it. */ - - if (relative_position == LEFT_TOTAL_LENGTH (tree) + 1) - { - /* This means we're deleting from the beginning of this interval. */ - register int my_amount = LENGTH (tree); - - if (amount < my_amount) - { - tree->total_length -= amount; - return amount; - } - else - { - tree->total_length -= my_amount; - if (LENGTH (tree) != 0) - abort (); /* Paranoia */ - - delete_interval (tree); - return my_amount; - } - } - else /* Deleting starting in the middle. */ - { - register int my_amount = ((tree->total_length - - RIGHT_TOTAL_LENGTH (tree)) - - relative_position + 1); - - if (amount <= my_amount) - { - tree->total_length -= amount; - return amount; - } - else - { - tree->total_length -= my_amount; - return my_amount; - } - } + /* How much can we delete from this interval? */ + int my_amount = ((tree->total_length + - RIGHT_TOTAL_LENGTH (tree)) + - relative_position); + + if (amount > my_amount) + amount = my_amount; + + tree->total_length -= amount; + if (LENGTH (tree) == 0) + delete_interval (tree); + + return amount; } /* Never reach here */ } -/* Effect the adjustments necessary to the interval tree of BUFFER - to correspond to the deletion of LENGTH characters from that buffer - text. The deletion is effected at position START (relative to the - buffer). */ +/* Effect the adjustments necessary to the interval tree of BUFFER to + correspond to the deletion of LENGTH characters from that buffer + text. The deletion is effected at position START (which is a + buffer position, i.e. origin 1). */ static void adjust_intervals_for_deletion (buffer, start, length) @@ -854,6 +836,10 @@ adjust_intervals_for_deletion (buffer, start, length) if (NULL_INTERVAL_P (tree)) return; + if (start > BEG + TOTAL_LENGTH (tree) + || start + length > BEG + TOTAL_LENGTH (tree)) + abort (); + if (length == TOTAL_LENGTH (tree)) { buffer->intervals = NULL_INTERVAL; @@ -866,11 +852,11 @@ adjust_intervals_for_deletion (buffer, start, length) return; } - if (start > TOTAL_LENGTH (tree)) - start = TOTAL_LENGTH (tree); + if (start > BEG + TOTAL_LENGTH (tree)) + start = BEG + TOTAL_LENGTH (tree); while (left_to_delete > 0) { - left_to_delete -= interval_deletion_adjustment (tree, start, + left_to_delete -= interval_deletion_adjustment (tree, start - 1, left_to_delete); tree = buffer->intervals; if (left_to_delete == tree->total_length) @@ -1030,6 +1016,9 @@ reproduce_tree (source, parent) return t; } +#if 0 +/* Nobody calls this. Perhaps it's a vestige of an earlier design. */ + /* Make a new interval of length LENGTH starting at START in the group of intervals INTERVALS, which is actually an interval tree. Returns the new interval. @@ -1054,29 +1043,31 @@ make_new_interval (intervals, start, length) if (slot->position == start) { /* New right node. */ - split_interval_right (slot, length + 1); + split_interval_right (slot, length); return slot; } if (slot->position + LENGTH (slot) == start + length) { /* New left node. */ - split_interval_left (slot, LENGTH (slot) - length + 1); + split_interval_left (slot, LENGTH (slot) - length); return slot; } /* Convert interval SLOT into three intervals. */ - split_interval_left (slot, start - slot->position + 1); - split_interval_right (slot, length + 1); + split_interval_left (slot, start - slot->position); + split_interval_right (slot, length); return slot; } +#endif /* Insert the intervals of SOURCE into BUFFER at POSITION. - This is used in insdel.c when inserting Lisp_Strings into - the buffer. The text corresponding to SOURCE is already in - the buffer when this is called. The intervals of new tree are - those belonging to the string being inserted; a copy is not made. + This is used in insdel.c when inserting Lisp_Strings into the + buffer. The text corresponding to SOURCE is already in the buffer + when this is called. The intervals of new tree are a copy of those + belonging to the string being inserted; intervals are never + shared. If the inserted text had no intervals associated, this function simply returns -- offset_intervals should handle placing the @@ -1121,7 +1112,7 @@ graft_intervals_into_buffer (source, position, buffer) { /* The inserted text constitutes the whole buffer, so simply copy over the interval structure. */ - if (BUF_Z (buffer) == TOTAL_LENGTH (source)) + if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source)) { buffer->intervals = reproduce_tree (source, tree->parent); /* Explicitly free the old tree here. */ @@ -1167,7 +1158,7 @@ graft_intervals_into_buffer (source, position, buffer) if (position > under->position) { INTERVAL end_unchanged - = split_interval_left (this, position - under->position + 1); + = split_interval_left (this, position - under->position); copy_properties (under, end_unchanged); under->position = position; prev = 0; @@ -1186,9 +1177,8 @@ graft_intervals_into_buffer (source, position, buffer) which means it gets those properties. */ while (! NULL_INTERVAL_P (over)) { - position = LENGTH (over) + 1; - if (position < LENGTH (under)) - this = split_interval_left (under, position); + if (LENGTH (over) + 1 < LENGTH (under)) + this = split_interval_left (under, LENGTH (over)); else this = under; copy_properties (over, this); @@ -1244,7 +1234,6 @@ set_point (position, buffer) register struct buffer *buffer; { register INTERVAL to, from, toprev, fromprev, target; - register int iposition = position; int buffer_point; register Lisp_Object obj; int backwards = (position < BUF_PT (buffer)) ? 1 : 0; @@ -1265,20 +1254,14 @@ set_point (position, buffer) return; } - /* Position Z is really one past the last char in the buffer. */ - if (position == BUF_ZV (buffer)) - iposition = position - 1; - /* Set TO to the interval containing the char after POSITION, and TOPREV to the interval containing the char before POSITION. Either one may be null. They may be equal. */ - to = find_interval (buffer->intervals, iposition); + to = find_interval (buffer->intervals, position); if (position == BUF_BEGV (buffer)) toprev = 0; else if (to->position == position) toprev = previous_interval (to); - else if (iposition != position) - toprev = to, to = 0; else toprev = to; @@ -1390,10 +1373,6 @@ get_local_map (position, buffer) if (position > BUF_Z (buffer) || position < BUF_BEG (buffer)) abort (); - /* Position Z is really one past the last char in the buffer. */ - if (position == BUF_ZV (buffer)) - return current_buffer->keymap; - interval = find_interval (buffer->intervals, position); prop = textget (interval->plist, Qlocal_map); if (NILP (prop)) @@ -1465,8 +1444,7 @@ verify_interval_modification (buf, start, end) /* Set I to the interval containing the char after START, and PREV to the interval containing the char before START. Either one may be null. They may be equal. */ - i = find_interval (intervals, - (start == BUF_ZV (buf) ? start - 1 : start)); + i = find_interval (intervals, start); if (start == BUF_BEGV (buf)) prev = 0; @@ -1498,11 +1476,11 @@ verify_interval_modification (buf, start, end) error ("Attempt to insert within read-only text"); } - /* Run both mod hooks (just once if they're the same). */ + /* Run both insert hooks (just once if they're the same). */ if (!NULL_INTERVAL_P (prev)) - prev_mod_hooks = textget (prev->plist, Qmodification_hooks); + prev_mod_hooks = textget (prev->plist, Qinsert_behind_hooks); if (!NULL_INTERVAL_P (i)) - mod_hooks = textget (i->plist, Qmodification_hooks); + mod_hooks = textget (i->plist, Qinsert_in_front_hooks); GCPRO1 (mod_hooks); if (! NILP (prev_mod_hooks)) call_mod_hooks (prev_mod_hooks, make_number (start), @@ -1644,7 +1622,7 @@ copy_intervals (tree, start, length) while (got < length) { i = next_interval (i); - t = split_interval_right (t, prevlen + 1); + t = split_interval_right (t, prevlen); copy_properties (i, t); prevlen = LENGTH (i); got += prevlen;