diff options
author | Ken Raeburn <raeburn@raeburn.org> | 2000-03-22 21:44:05 +0000 |
---|---|---|
committer | Ken Raeburn <raeburn@raeburn.org> | 2000-03-22 21:44:05 +0000 |
commit | e88c2b513bf83ba08355f938a5b8df69081c75d7 (patch) | |
tree | 277ab863858f82e24b204fed40851955df022379 | |
parent | d5b0f8349987623c711301dba68a95e9c76204b2 (diff) | |
download | emacs-e88c2b513bf83ba08355f938a5b8df69081c75d7.tar.gz |
Changes towards better type safety regarding intervals, primarily
regarding the "parent" handle. These just separate out the different
usages based on the type of parent (interval vs lisp object); later
changes will do type checking and enforcement.
* intervals.h (NULL_INTERVAL): Cast to INTERVAL type.
(INT_LISPLIKE): New macro.
(NULL_INTERVAL_P): Use it.
(INTERVAL_HAS_PARENT, INTERVAL_HAS_OBJECT, SET_INTERVAL_PARENT,
SET_INTERVAL_OBJECT, INTERVAL_PARENT, COPY_INTERVAL_PARENT,
GET_INTERVAL_OBJECT, INTERVAL_PARENT_OR_NULL): New macros.
* alloc.c (make_interval, gc_sweep): Use new macros; eliminate all
explicit references to "parent" field of struct interval and
associated unclean type conversions.
* intervals.c (create_root_interval, root_interval, rotate_right,
rotate_left, balance_possible_root_interval, split_interval_right,
split_interval_left, interval_start_pos, find_interval,
next_interval, previous_interval, update_interval,
adjust_intervals_for_insertion, delete_node, delete_interval,
adjust_intervals_for_deletion, merge_interval_right,
merge_interval_left, reproduce_tree, graft_intervals_into_buffer,
copy_intervals_to_string): Likewise.
* intervals.h (AM_LEFT_CHILD, AM_RIGHT_CHILD, RESET_INTERVAL):
Likewise.
* syntax.c (update_syntax_table): Likewise.
* intervals.c (reproduce_tree_obj): New function, like
reproduce_tree but takes a Lisp_Object for the parent. Declare
with prototype.
(graft_intervals_into_buffer): Use it when appropriate.
(reproduce_tree): Declare with prototype.
(balance_possible_root_interval): Check that the parent is a lisp
object before trying to examine its type.
-rw-r--r-- | src/ChangeLog | 32 | ||||
-rw-r--r-- | src/alloc.c | 6 | ||||
-rw-r--r-- | src/intervals.c | 133 | ||||
-rw-r--r-- | src/intervals.h | 49 | ||||
-rw-r--r-- | src/syntax.c | 10 |
5 files changed, 159 insertions, 71 deletions
diff --git a/src/ChangeLog b/src/ChangeLog index 1d1916b24bc..3ee198fecd3 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,35 @@ +2000-03-22 Ken Raeburn <raeburn@gnu.org> + + * intervals.h (NULL_INTERVAL): Cast to INTERVAL type. + (INT_LISPLIKE): New macro. + (NULL_INTERVAL_P): Use it. + (INTERVAL_HAS_PARENT, INTERVAL_HAS_OBJECT, SET_INTERVAL_PARENT, + SET_INTERVAL_OBJECT, INTERVAL_PARENT, COPY_INTERVAL_PARENT, + GET_INTERVAL_OBJECT, INTERVAL_PARENT_OR_NULL): New macros. + + * alloc.c (make_interval, gc_sweep): Use new macros; eliminate all + explicit references to "parent" field of struct interval and + associated unclean type conversions. + * intervals.c (create_root_interval, root_interval, rotate_right, + rotate_left, balance_possible_root_interval, split_interval_right, + split_interval_left, interval_start_pos, find_interval, + next_interval, previous_interval, update_interval, + adjust_intervals_for_insertion, delete_node, delete_interval, + adjust_intervals_for_deletion, merge_interval_right, + merge_interval_left, reproduce_tree, graft_intervals_into_buffer, + copy_intervals_to_string): Likewise. + * intervals.h (AM_LEFT_CHILD, AM_RIGHT_CHILD, RESET_INTERVAL): + Likewise. + * syntax.c (update_syntax_table): Likewise. + + * intervals.c (reproduce_tree_obj): New function, like + reproduce_tree but takes a Lisp_Object for the parent. Declare + with prototype. + (graft_intervals_into_buffer): Use it when appropriate. + (reproduce_tree): Declare with prototype. + (balance_possible_root_interval): Check that the parent is a lisp + object before trying to examine its type. + 2000-03-22 Gerd Moellmann <gerd@gnu.org> * xfaces.c (lface_same_font_attributes_p): Compare font attributes diff --git a/src/alloc.c b/src/alloc.c index ba8b3ffd6ed..3027e08b467 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -711,7 +711,7 @@ make_interval () if (interval_free_list) { val = interval_free_list; - interval_free_list = interval_free_list->parent; + interval_free_list = INTERVAL_PARENT (interval_free_list); } else { @@ -4215,7 +4215,7 @@ gc_sweep () { if (! XMARKBIT (iblk->intervals[i].plist)) { - iblk->intervals[i].parent = interval_free_list; + SET_INTERVAL_PARENT (&iblk->intervals[i], interval_free_list); interval_free_list = &iblk->intervals[i]; this_free++; } @@ -4233,7 +4233,7 @@ gc_sweep () { *iprev = iblk->next; /* Unhook from the free list. */ - interval_free_list = iblk->intervals[0].parent; + interval_free_list = INTERVAL_PARENT (&iblk->intervals[0]); lisp_free (iblk); n_interval_blocks--; } diff --git a/src/intervals.c b/src/intervals.c index bba25d7de8c..2a03abbb762 100644 --- a/src/intervals.c +++ b/src/intervals.c @@ -54,6 +54,8 @@ Boston, MA 02111-1307, USA. */ #define min(x, y) ((x) < (y) ? (x) : (y)) Lisp_Object merge_properties_sticky (); +static INTERVAL reproduce_tree P_ ((INTERVAL, INTERVAL)); +static INTERVAL reproduce_tree_obj P_ ((INTERVAL, Lisp_Object)); /* Utility functions for intervals. */ @@ -84,7 +86,7 @@ create_root_interval (parent) new->position = 0; } - new->parent = (INTERVAL) XFASTINT (parent); + SET_INTERVAL_OBJECT (new, parent); return new; } @@ -269,7 +271,7 @@ root_interval (interval) register INTERVAL i = interval; while (! ROOT_INTERVAL_P (i)) - i = i->parent; + i = INTERVAL_PARENT (i); return i; } @@ -296,21 +298,21 @@ rotate_right (interval) if (! ROOT_INTERVAL_P (interval)) { if (AM_LEFT_CHILD (interval)) - interval->parent->left = B; + INTERVAL_PARENT (interval)->left = B; else - interval->parent->right = B; + INTERVAL_PARENT (interval)->right = B; } - B->parent = interval->parent; + COPY_INTERVAL_PARENT (B, interval); /* Make B the parent of A */ i = B->right; B->right = interval; - interval->parent = B; + SET_INTERVAL_PARENT (interval, B); /* Make A point to c */ interval->left = i; if (! NULL_INTERVAL_P (i)) - i->parent = interval; + SET_INTERVAL_PARENT (i, interval); /* A's total length is decreased by the length of B and its left child. */ interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval); @@ -342,21 +344,21 @@ rotate_left (interval) if (! ROOT_INTERVAL_P (interval)) { if (AM_LEFT_CHILD (interval)) - interval->parent->left = B; + INTERVAL_PARENT (interval)->left = B; else - interval->parent->right = B; + INTERVAL_PARENT (interval)->right = B; } - B->parent = interval->parent; + COPY_INTERVAL_PARENT (B, interval); /* Make B the parent of A */ i = B->left; B->left = interval; - interval->parent = B; + SET_INTERVAL_PARENT (interval, B); /* Make A point to c */ interval->right = i; if (! NULL_INTERVAL_P (i)) - i->parent = interval; + SET_INTERVAL_PARENT (i, interval); /* A's total length is decreased by the length of B and its right child. */ interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval); @@ -411,17 +413,25 @@ balance_possible_root_interval (interval) register INTERVAL interval; { Lisp_Object parent; + int have_parent = 0; - if (interval->parent == NULL_INTERVAL) + if (!INTERVAL_HAS_OBJECT (interval) && !INTERVAL_HAS_PARENT (interval)) return interval; - XSETFASTINT (parent, (EMACS_INT) interval->parent); + if (INTERVAL_HAS_OBJECT (interval)) + { + have_parent = 1; + GET_INTERVAL_OBJECT (parent, interval); + } interval = balance_an_interval (interval); - if (BUFFERP (parent)) - BUF_INTERVALS (XBUFFER (parent)) = interval; - else if (STRINGP (parent)) - XSTRING (parent)->intervals = interval; + if (have_parent) + { + if (BUFFERP (parent)) + BUF_INTERVALS (XBUFFER (parent)) = interval; + else if (STRINGP (parent)) + XSTRING (parent)->intervals = interval; + } return interval; } @@ -476,7 +486,7 @@ split_interval_right (interval, offset) int new_length = LENGTH (interval) - offset; new->position = position + offset; - new->parent = interval; + SET_INTERVAL_PARENT (new, interval); if (NULL_RIGHT_CHILD (interval)) { @@ -487,7 +497,7 @@ split_interval_right (interval, offset) { /* Insert the new node between INTERVAL and its right child. */ new->right = interval->right; - interval->right->parent = new; + SET_INTERVAL_PARENT (interval->right, new); interval->right = new; new->total_length = new_length + new->right->total_length; balance_an_interval (new); @@ -521,7 +531,7 @@ split_interval_left (interval, offset) new->position = interval->position; interval->position = interval->position + offset; - new->parent = interval; + SET_INTERVAL_PARENT (new, interval); if (NULL_LEFT_CHILD (interval)) { @@ -532,7 +542,7 @@ split_interval_left (interval, offset) { /* Insert the new node between INTERVAL and its left child. */ new->left = interval->left; - new->left->parent = new; + SET_INTERVAL_PARENT (new->left, new); interval->left = new; new->total_length = new_length + new->left->total_length; balance_an_interval (new); @@ -560,7 +570,7 @@ interval_start_pos (source) if (NULL_INTERVAL_P (source)) return 0; - XSETFASTINT (parent, (EMACS_INT) source->parent); + GET_INTERVAL_OBJECT (parent, source); if (BUFFERP (parent)) return BUF_BEG (XBUFFER (parent)); return 0; @@ -584,15 +594,18 @@ find_interval (tree, position) /* The distance from the left edge of the subtree at TREE to POSITION. */ register int relative_position; - Lisp_Object parent; if (NULL_INTERVAL_P (tree)) return NULL_INTERVAL; - XSETFASTINT (parent, (EMACS_INT) tree->parent); relative_position = position; - if (BUFFERP (parent)) - relative_position -= BUF_BEG (XBUFFER (parent)); + if (INTERVAL_HAS_OBJECT (tree)) + { + Lisp_Object parent; + GET_INTERVAL_OBJECT (parent, tree); + if (BUFFERP (parent)) + relative_position -= BUF_BEG (XBUFFER (parent)); + } if (relative_position > TOTAL_LENGTH (tree)) abort (); /* Paranoia */ @@ -653,12 +666,12 @@ next_interval (interval) { if (AM_LEFT_CHILD (i)) { - i = i->parent; + i = INTERVAL_PARENT (i); i->position = next_position; return i; } - i = i->parent; + i = INTERVAL_PARENT (i); } return NULL_INTERVAL; @@ -692,12 +705,12 @@ previous_interval (interval) { if (AM_RIGHT_CHILD (i)) { - i = i->parent; + i = INTERVAL_PARENT (i); i->position = interval->position - LENGTH (i); return i; } - i = i->parent; + i = INTERVAL_PARENT (i); } return NULL_INTERVAL; @@ -728,7 +741,7 @@ update_interval (i, pos) else if (NULL_PARENT (i)) error ("Point before start of properties"); else - i = i->parent; + i = INTERVAL_PARENT (i); continue; } else if (pos >= INTERVAL_LAST_POS (i)) @@ -743,7 +756,7 @@ update_interval (i, pos) else if (NULL_PARENT (i)) error ("Point after end of properties"); else - i = i->parent; + i = INTERVAL_PARENT (i); continue; } else @@ -838,7 +851,7 @@ adjust_intervals_for_insertion (tree, position, length) if (TOTAL_LENGTH (tree) == 0) /* Paranoia */ abort (); - XSETFASTINT (parent, (EMACS_INT) tree->parent); + GET_INTERVAL_OBJECT (parent, tree); offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0); /* If inserting at point-max of a buffer, that position will be out @@ -944,7 +957,7 @@ adjust_intervals_for_insertion (tree, position, length) /* Even if we are positioned between intervals, we default to the left one if it exists. We extend it now and split off a part later, if stickiness demands it. */ - for (temp = prev ? prev : i;! NULL_INTERVAL_P (temp); temp = temp->parent) + for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp)) { temp->total_length += length; temp = balance_possible_root_interval (temp); @@ -1000,7 +1013,7 @@ adjust_intervals_for_insertion (tree, position, length) /* Otherwise just extend the interval. */ else { - for (temp = i; ! NULL_INTERVAL_P (temp); temp = temp->parent) + for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp)) { temp->total_length += length; temp = balance_possible_root_interval (temp); @@ -1208,7 +1221,7 @@ delete_node (i) this->total_length += migrate_amt; } this->left = migrate; - migrate->parent = this; + SET_INTERVAL_PARENT (migrate, this); return i->right; } @@ -1232,10 +1245,10 @@ delete_interval (i) if (ROOT_INTERVAL_P (i)) { Lisp_Object owner; - XSETFASTINT (owner, (EMACS_INT) i->parent); + GET_INTERVAL_OBJECT (owner, i); parent = delete_node (i); if (! NULL_INTERVAL_P (parent)) - parent->parent = (INTERVAL) XFASTINT (owner); + SET_INTERVAL_OBJECT (parent, owner); if (BUFFERP (owner)) BUF_INTERVALS (XBUFFER (owner)) = parent; @@ -1247,18 +1260,18 @@ delete_interval (i) return; } - parent = i->parent; + parent = INTERVAL_PARENT (i); if (AM_LEFT_CHILD (i)) { parent->left = delete_node (i); if (! NULL_INTERVAL_P (parent->left)) - parent->left->parent = parent; + SET_INTERVAL_PARENT (parent->left, parent); } else { parent->right = delete_node (i); if (! NULL_INTERVAL_P (parent->right)) - parent->right->parent = parent; + SET_INTERVAL_PARENT (parent->right, parent); } } @@ -1343,7 +1356,7 @@ adjust_intervals_for_deletion (buffer, start, length) Lisp_Object parent; int offset; - XSETFASTINT (parent, (EMACS_INT) tree->parent); + GET_INTERVAL_OBJECT (parent, tree); offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0); if (NULL_INTERVAL_P (tree)) @@ -1440,12 +1453,12 @@ merge_interval_right (i) { if (AM_LEFT_CHILD (successor)) { - successor = successor->parent; + successor = INTERVAL_PARENT (successor); delete_interval (i); return successor; } - successor = successor->parent; + successor = INTERVAL_PARENT (successor); successor->total_length -= absorb; } @@ -1493,12 +1506,12 @@ merge_interval_left (i) { if (AM_RIGHT_CHILD (predecessor)) { - predecessor = predecessor->parent; + predecessor = INTERVAL_PARENT (predecessor); delete_interval (i); return predecessor; } - predecessor = predecessor->parent; + predecessor = INTERVAL_PARENT (predecessor); predecessor->total_length -= absorb; } @@ -1520,7 +1533,25 @@ reproduce_tree (source, parent) bcopy (source, t, INTERVAL_SIZE); copy_properties (source, t); - t->parent = parent; + SET_INTERVAL_PARENT (t, parent); + if (! NULL_LEFT_CHILD (source)) + t->left = reproduce_tree (source->left, t); + if (! NULL_RIGHT_CHILD (source)) + t->right = reproduce_tree (source->right, t); + + return t; +} + +static INTERVAL +reproduce_tree_obj (source, parent) + INTERVAL source; + Lisp_Object parent; +{ + register INTERVAL t = make_interval (); + + bcopy (source, t, INTERVAL_SIZE); + copy_properties (source, t); + SET_INTERVAL_OBJECT (t, parent); if (! NULL_LEFT_CHILD (source)) t->left = reproduce_tree (source->left, t); if (! NULL_RIGHT_CHILD (source)) @@ -1654,7 +1685,7 @@ graft_intervals_into_buffer (source, position, length, buffer, inherit) { Lisp_Object buf; XSETBUFFER (buf, buffer); - BUF_INTERVALS (buffer) = reproduce_tree (source, buf); + BUF_INTERVALS (buffer) = reproduce_tree_obj (source, buf); BUF_INTERVALS (buffer)->position = 1; /* Explicitly free the old tree here? */ @@ -1676,7 +1707,7 @@ graft_intervals_into_buffer (source, position, length, buffer, inherit) some zero length intervals. Eventually, do something clever about inserting properly. For now, just waste the old intervals. */ { - BUF_INTERVALS (buffer) = reproduce_tree (source, tree->parent); + BUF_INTERVALS (buffer) = reproduce_tree (source, INTERVAL_PARENT (tree)); BUF_INTERVALS (buffer)->position = 1; /* Explicitly free the old tree here. */ @@ -2236,7 +2267,7 @@ copy_intervals_to_string (string, buffer, position, length) if (NULL_INTERVAL_P (interval_copy)) return; - interval_copy->parent = (INTERVAL) XFASTINT (string); + SET_INTERVAL_OBJECT (interval_copy, string); XSTRING (string)->intervals = interval_copy; } diff --git a/src/intervals.h b/src/intervals.h index 234df7d4112..eb50d723784 100644 --- a/src/intervals.h +++ b/src/intervals.h @@ -22,7 +22,7 @@ Boston, MA 02111-1307, USA. */ #include "dispextern.h" #endif -#define NULL_INTERVAL 0 +#define NULL_INTERVAL ((INTERVAL)0) #define INTERVAL_DEFAULT NULL_INTERVAL /* These are macros for dealing with the interval tree. */ @@ -37,14 +37,13 @@ Boston, MA 02111-1307, USA. */ Lisp_String pointer (meaning it points to the owner of this interval tree). */ #ifdef NO_UNION_TYPE -#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL \ - || BUFFERP ((Lisp_Object)(i)) \ - || STRINGP ((Lisp_Object)(i))) +#define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object)(i)) \ + || STRINGP ((Lisp_Object)(i))) #else -#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL \ - || BUFFERP ((Lisp_Object){(EMACS_INT)(i)}) \ - || STRINGP ((Lisp_Object){(EMACS_INT)(i)})) +#define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object){(EMACS_INT)(i)}) \ + || STRINGP ((Lisp_Object){(EMACS_INT)(i)})) #endif +#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL || INT_LISPLIKE (i)) /* True if this interval has no right child. */ #define NULL_RIGHT_CHILD(i) ((i)->right == NULL_INTERVAL) @@ -56,12 +55,12 @@ Boston, MA 02111-1307, USA. */ #define NULL_PARENT(i) (NULL_INTERVAL_P ((i)->parent)) /* True if this interval is the left child of some other interval. */ -#define AM_LEFT_CHILD(i) (! NULL_INTERVAL_P ((i)->parent) \ - && (i)->parent->left == (i)) +#define AM_LEFT_CHILD(i) (! NULL_PARENT (i) \ + && INTERVAL_PARENT (i)->left == (i)) /* True if this interval is the right child of some other interval. */ -#define AM_RIGHT_CHILD(i) (! NULL_INTERVAL_P ((i)->parent) \ - && (i)->parent->right == (i)) +#define AM_RIGHT_CHILD(i) (! NULL_PARENT (i) \ + && INTERVAL_PARENT (i)->right == (i)) /* True if this interval has no children. */ #define LEAF_INTERVAL_P(i) ((i)->left == NULL_INTERVAL \ @@ -103,12 +102,38 @@ Boston, MA 02111-1307, USA. */ or having no properties. */ #define DEFAULT_INTERVAL_P(i) (NULL_INTERVAL_P (i) || EQ ((i)->plist, Qnil)) +/* Test what type of parent we have. Three possibilities: another + interval, a buffer or string object, or NULL_INTERVAL. */ +#define INTERVAL_HAS_PARENT(i) ((i)->parent && ! INT_LISPLIKE ((i)->parent)) +#define INTERVAL_HAS_OBJECT(i) ((i)->parent && INT_LISPLIKE ((i)->parent)) + +/* Set/get parent of an interval. + + The choice of macros is dependent on the type needed. Don't add + casts to get around this, it will break some development work in + progress. */ +#define SET_INTERVAL_PARENT(i,p) ((i)->parent = (p)) +#define SET_INTERVAL_OBJECT(i,o) ((i)->parent = (INTERVAL) XFASTINT (o)) +#define INTERVAL_PARENT(i) ((i)->parent) +/* Because XSETFASTINT has to be used, this can't simply be + value-returning. */ +#define GET_INTERVAL_OBJECT(d,s) XSETFASTINT((d), (EMACS_INT) (s)->parent) + +/* Make the parent of D be whatever the parent of S is, regardless of + type. This is used when balancing an interval tree. */ +#define COPY_INTERVAL_PARENT(d,s) ((d)->parent = (s)->parent) + +/* Get the parent interval, if any, otherwise a null pointer. Useful + for walking up to the root in a "for" loop; use this to get the + "next" value, and test the result to see if it's NULL_INTERVAL. */ +#define INTERVAL_PARENT_OR_NULL(i) (INTERVAL_HAS_PARENT (i) ? INTERVAL_PARENT (i) : 0) + /* Reset this interval to its vanilla, or no-property state. */ #define RESET_INTERVAL(i) \ { \ (i)->total_length = (i)->position = 0; \ (i)->left = (i)->right = NULL_INTERVAL; \ - (i)->parent = NULL_INTERVAL; \ + SET_INTERVAL_PARENT (i, NULL_INTERVAL); \ (i)->write_protect = 0; \ (i)->visible = 0; \ (i)->front_sticky = (i)->rear_sticky = 0; \ diff --git a/src/syntax.c b/src/syntax.c index 167e20ebed5..496693f7b23 100644 --- a/src/syntax.c +++ b/src/syntax.c @@ -140,14 +140,14 @@ update_syntax_table (charpos, count, init, object) while (!NULL_PARENT (i)) { if (AM_RIGHT_CHILD (i)) - i->parent->position = i->position + INTERVAL_PARENT (i)->position = i->position - LEFT_TOTAL_LENGTH (i) + TOTAL_LENGTH (i) /* right end */ - - TOTAL_LENGTH (i->parent) - + LEFT_TOTAL_LENGTH (i->parent); + - TOTAL_LENGTH (INTERVAL_PARENT (i)) + + LEFT_TOTAL_LENGTH (INTERVAL_PARENT (i)); else - i->parent->position = i->position - LEFT_TOTAL_LENGTH (i) + INTERVAL_PARENT (i)->position = i->position - LEFT_TOTAL_LENGTH (i) + TOTAL_LENGTH (i); - i = i->parent; + i = INTERVAL_PARENT (i); } i = gl_state.forward_i; gl_state.b_property = i->position - 1 - gl_state.offset; |