Mercurial > hg > xemacs-beta
diff src/lisp.h @ 4967:0d4c9d0f6a8d
rewrite dynarr code
-------------------- ChangeLog entries follow: --------------------
src/ChangeLog addition:
2010-02-03 Ben Wing <ben@xemacs.org>
* device-x.c (x_get_resource_prefix):
* device-x.c (Fx_get_resource):
* device-x.c (Fx_get_resource_prefix):
* device-x.c (Fx_put_resource):
* dialog-msw.c:
* dialog-msw.c (handle_question_dialog_box):
* dired-msw.c (mswindows_sort_files):
* dired-msw.c (mswindows_get_files):
* extents.c (extent_fragment_sort_by_priority):
* extents.c (Fset_extent_parent):
* file-coding.c (coding_reader):
* file-coding.c (coding_writer):
* file-coding.c (gzip_convert):
* frame.c (generate_title_string):
* gutter.c (calculate_gutter_size_from_display_lines):
* indent.c (vmotion_1):
* lread.c (read_bit_vector):
* mule-coding.c (iso2022_decode):
* rangetab.c:
* rangetab.c (Fcopy_range_table):
* rangetab.c (Fget_range_table):
* rangetab.c (unified_range_table_copy_data):
* redisplay-msw.c (mswindows_output_string):
* redisplay-output.c (output_display_line):
* redisplay-output.c (redisplay_move_cursor):
* redisplay-output.c (redisplay_clear_bottom_of_window):
* redisplay-tty.c (tty_output_ichar_dynarr):
* redisplay-tty.c (set_foreground_to):
* redisplay-tty.c (set_background_to):
* redisplay-xlike-inc.c (XLIKE_output_string):
* redisplay.c (redisplay_window_text_width_string):
* redisplay.c (redisplay_text_width_string):
* redisplay.c (create_text_block):
* redisplay.c (SET_CURRENT_MODE_CHARS_PIXSIZE):
* redisplay.c (generate_fstring_runes):
* redisplay.c (regenerate_modeline):
* redisplay.c (ensure_modeline_generated):
* redisplay.c (real_current_modeline_height):
* redisplay.c (create_string_text_block):
* redisplay.c (regenerate_window):
* redisplay.c (REGEN_INC_FIND_START_END):
* redisplay.c (point_visible):
* redisplay.c (redisplay_window):
* redisplay.c (mark_glyph_block_dynarr):
* redisplay.c (line_start_cache_start):
* redisplay.c (start_with_line_at_pixpos):
* redisplay.c (update_line_start_cache):
* redisplay.c (glyph_to_pixel_translation):
* redisplay.c (pixel_to_glyph_translation):
* sysdep.c (qxe_readdir):
* text.c (dfc_convert_to_external_format):
* text.c (dfc_convert_to_internal_format):
* toolbar-common.c (common_output_toolbar_button):
* window.c (window_modeline_height):
* window.c (Fwindow_last_line_visible_height):
* window.c (window_displayed_height):
* window.c (window_scroll):
* window.c (get_current_pixel_pos):
Use Dynarr_begin() in place of Dynarr_atp (foo, 0).
* dynarr.c (Dynarr_realloc):
* dynarr.c (Dynarr_lisp_realloc):
* dynarr.c (Dynarr_resize):
* dynarr.c (Dynarr_insert_many):
* dynarr.c (Dynarr_delete_many):
* dynarr.c (Dynarr_memory_usage):
* dynarr.c (stack_like_malloc):
* dynarr.c (stack_like_free):
* lisp.h:
* lisp.h (DECLARE_DYNARR_LISP_IMP):
* lisp.h (XD_DYNARR_DESC):
* lisp.h (Dynarr_pop):
* gutter.c (output_gutter):
* redisplay-output.c (sync_rune_structs):
* redisplay-output.c (redisplay_output_window):
Redo the dynarr code, add greater checks.
Rename the `len', `largest' and `max' members to `len_',
`largest_' and `max_' to try and catch existing places that might
directly modify these values. Make new accessors Dynarr_largest()
and Dynarr_max() and make them and existing Dynarr_length() be
non-lvalues by adding '+ 0' to them; fix a couple of places in the
redisplay code that tried to modify the length directly by setting
Dynarr_length(). Use the accessors whenever possible even in the
dynarr code itself. The accessors also verify that 0 <= len <=
largest <= max. Rename settor function Dynarr_set_size() to
Dynarr_set_length() and use it more consistently; also create
lower-level Dynarr_set_length_1(). This latter function should be
the only function that directly modifies the `len_' member of a
Dynarr, and in the process makes sure that the `largest' value is
kept correct.
Consistently use ERROR_CHECK_STRUCTURES instead of
ERROR_CHECK_TYPES for error-checking code. Reintroduce the
temporarily disabled verification code on the positions of
Dynarr_at(), Dynarr_atp() and Dynarr_atp_past_end().
Also create Dynarr_resize_if() in place of a repeated
code fragment. Clean up all the functions that modify Dynarrs to
use the new macros and functions and verify the correctness of the
Dynarr both before and after the change.
Note that there are two kinds of verification -- one for accessing
and one for modifying. The difference is that the modify
verification additionally checks to make sure that the Dynarr
isn't locked. (This is used in redisplay to check for problems
with reentrancy.)
* lrecord.h: Move XD_DYNARR_DESC to lisp.h, grouping with the dynarr code.
author | Ben Wing <ben@xemacs.org> |
---|---|
date | Wed, 03 Feb 2010 20:51:18 -0600 |
parents | 48b63cd88a21 |
children | cbe181529c34 |
line wrap: on
line diff
--- a/src/lisp.h Mon Feb 01 14:11:36 2010 -0600 +++ b/src/lisp.h Wed Feb 03 20:51:18 2010 -0600 @@ -1697,71 +1697,64 @@ END_C_DECLS -/************************************************************************/ -/** Definitions of basic Lisp objects **/ +#include "lrecord.h" + /************************************************************************/ - -#include "lrecord.h" +/** Definitions of dynamic arrays (Dynarrs) and other allocators **/ +/************************************************************************/ BEGIN_C_DECLS -/* ------------------------ dynamic arrays ------------------- */ +/************* Dynarr declaration *************/ #ifdef NEW_GC +#define DECLARE_DYNARR_LISP_IMP() \ + const struct lrecord_implementation *lisp_imp; +#else +#define DECLARE_DYNARR_LISP_IMP() +#endif + #ifdef ERROR_CHECK_STRUCTURES -#define Dynarr_declare(type) \ - struct lrecord_header header; \ - type *base; \ - const struct lrecord_implementation *lisp_imp; \ - int locked; \ - int elsize; \ - int len; \ - int largest; \ - int max +#define DECLARE_DYNARR_LOCKED() \ + int locked; #else -#define Dynarr_declare(type) \ - struct lrecord_header header; \ - type *base; \ - const struct lrecord_implementation *lisp_imp; \ - int elsize; \ - int len; \ - int largest; \ - int max -#endif /* ERROR_CHECK_STRUCTURES */ -#else /* not NEW_GC */ -#ifdef ERROR_CHECK_STRUCTURES -#define Dynarr_declare(type) \ - struct lrecord_header header; \ - type *base; \ - int locked; \ - int elsize; \ - int len; \ - int largest; \ - int max -#else -#define Dynarr_declare(type) \ - struct lrecord_header header; \ - type *base; \ - int elsize; \ - int len; \ - int largest; \ - int max -#endif /* ERROR_CHECK_STRUCTURES */ -#endif /* not NEW_GC */ +#define DECLARE_DYNARR_LOCKED() +#endif + +#define Dynarr_declare(type) \ + struct lrecord_header header; \ + type *base; \ + DECLARE_DYNARR_LISP_IMP () \ + DECLARE_DYNARR_LOCKED () \ + int elsize; \ + int len_; \ + int largest_; \ + int max_ typedef struct dynarr { Dynarr_declare (void); } Dynarr; -MODULE_API void *Dynarr_newf (int elsize); -MODULE_API void Dynarr_resize (void *dy, Elemcount size); -MODULE_API void Dynarr_insert_many (void *d, const void *el, int len, - int start); -MODULE_API void Dynarr_delete_many (void *d, int start, int len); -MODULE_API void Dynarr_free (void *d); - -#ifdef ERROR_CHECK_TYPES +#define XD_DYNARR_DESC(base_type, sub_desc) \ + { XD_BLOCK_PTR, offsetof (base_type, base), \ + XD_INDIRECT(1, 0), {sub_desc} }, \ + { XD_INT, offsetof (base_type, len_) }, \ + { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \ + { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) } + +#ifdef NEW_GC +#define XD_LISP_DYNARR_DESC(base_type, sub_desc) \ + { XD_LISP_OBJECT_BLOCK_PTR, offsetof (base_type, base), \ + XD_INDIRECT(1, 0), {sub_desc} }, \ + { XD_INT, offsetof (base_type, len_) }, \ + { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \ + { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) } +#endif /* NEW_GC */ + +/************* Dynarr verification *************/ + +#ifdef ERROR_CHECK_STRUCTURES DECLARE_INLINE_HEADER ( int Dynarr_verify_pos_at (void *d, int pos, const Ascbyte *file, int line) @@ -1770,7 +1763,7 @@ Dynarr *dy = (Dynarr *) d; /* We use `largest', not `len', because the redisplay code often accesses stuff between len and largest. */ - assert_at_line (pos >= 0 && pos < dy->largest, file, line); + assert_at_line (pos >= 0 && pos < dy->largest_, file, line); return pos; } @@ -1793,7 +1786,7 @@ hence the return value is NULL. But the length of 0 causes the pointer to never get checked. These can occur throughout the code so we put in a special check. */ - if (pos == 0 && dy->len == 0) + if (pos == 0 && dy->len_ == 0) return pos; /* #### It's vaguely possible that some code could legitimately want to retrieve a pointer to the position just past the end of dynarr memory. @@ -1806,7 +1799,7 @@ memory, which is a likely off-by-one problem to occur and will usually not trigger a protection fault (instead, you'll just get random behavior, possibly overwriting other memory, which is bad). */ - assert_at_line (pos >= 0 && pos < dy->largest, file, line); + assert_at_line (pos >= 0 && pos < dy->largest_, file, line); return pos; } @@ -1821,7 +1814,7 @@ accesses stuff between len and largest. We also allow referencing the very end, past the end of allocated legitimately space. See comments in Dynarr_verify_pos_atp.()*/ - assert_at_line (pos >= 0 && pos <= dy->largest, file, line); + assert_at_line (pos >= 0 && pos <= dy->largest_, file, line); return pos; } @@ -1829,7 +1822,53 @@ #define Dynarr_verify_pos_at(d, pos, file, line) (pos) #define Dynarr_verify_pos_atp(d, pos, file, line) (pos) #define Dynarr_verify_pos_atp_allow_end(d, pos, file, line) (pos) -#endif /* ERROR_CHECK_TYPES */ +#endif /* ERROR_CHECK_STRUCTURES */ + +#ifdef ERROR_CHECK_STRUCTURES +DECLARE_INLINE_HEADER ( +Dynarr * +Dynarr_verify_1 (void *d, const Ascbyte *file, int line) +) +{ + Dynarr *dy = (Dynarr *) d; + assert_at_line (dy->len_ >= 0 && dy->len_ <= dy->largest_ && + dy->largest_ <= dy->max_, file, line); + return dy; +} + +DECLARE_INLINE_HEADER ( +Dynarr * +Dynarr_verify_mod_1 (void *d, const Ascbyte *file, int line) +) +{ + Dynarr *dy = (Dynarr *) d; + assert_at_line (!dy->locked, file, line); + return Dynarr_verify_1 (d, file, line); +} + +#define Dynarr_verify(d) Dynarr_verify_1 (d, __FILE__, __LINE__) +#define Dynarr_verify_mod(d) Dynarr_verify_mod_1 (d, __FILE__, __LINE__) +#define Dynarr_lock(d) \ +do { \ + Dynarr *dy = Dynarr_verify_mod (d); \ + dy->locked = 1; \ +} while (0) +#define Dynarr_unlock(d) \ +do { \ + Dynarr *dy = Dynarr_verify (d); \ + dy->locked = 0; \ +} while (0) +#else +#define Dynarr_verify(d) (d) +#define Dynarr_verify_mod(d) (d) +#define Dynarr_lock(d) DO_NOTHING +#define Dynarr_unlock(d) DO_NOTHING +#endif /* ERROR_CHECK_STRUCTURES */ + +/************* Dynarr creation *************/ + +MODULE_API void *Dynarr_newf (int elsize); +MODULE_API void Dynarr_free (void *d); #ifdef NEW_GC MODULE_API void *Dynarr_lisp_newf (int elsize, @@ -1846,7 +1885,9 @@ #define Dynarr_new2(dynarr_type, type) \ ((dynarr_type *) Dynarr_newf (sizeof (type))) -#ifdef ERROR_CHECK_TYPES_GCC_NOT_BROKEN +/************* Dynarr access *************/ + +#ifdef ERROR_CHECK_STRUCTURES /* Enabling this leads to crashes in Cygwin 1.7, gcc 3.4.4 */ #define Dynarr_at(d, pos) \ ((d)->base[Dynarr_verify_pos_at (d, pos, __FILE__, __LINE__)]) @@ -1864,46 +1905,97 @@ #define Dynarr_begin(d) Dynarr_atp (d, 0) #define Dynarr_lastp(d) Dynarr_atp (d, Dynarr_length (d) - 1) #define Dynarr_past_lastp(d) Dynarr_atp_allow_end (d, Dynarr_length (d)) -#define Dynarr_sizeof(d) ((d)->len * (d)->elsize) - -#ifdef ERROR_CHECK_STRUCTURES -DECLARE_INLINE_HEADER ( -Dynarr * -Dynarr_verify_1 (void *d, const Ascbyte *file, int line) -) -{ - Dynarr *dy = (Dynarr *) d; - assert_at_line (dy->len >= 0 && dy->len <= dy->largest && - dy->largest <= dy->max, file, line); - return dy; -} - -DECLARE_INLINE_HEADER ( -Dynarr * -Dynarr_verify_mod_1 (void *d, const Ascbyte *file, int line) -) -{ - Dynarr *dy = (Dynarr *) d; - assert_at_line (!dy->locked, file, line); - assert_at_line (dy->len >= 0 && dy->len <= dy->largest && - dy->largest <= dy->max, file, line); - return dy; -} - -#define Dynarr_verify(d) Dynarr_verify_1 (d, __FILE__, __LINE__) -#define Dynarr_verify_mod(d) Dynarr_verify_mod_1 (d, __FILE__, __LINE__) -#define Dynarr_lock(d) (Dynarr_verify_mod (d)->locked = 1) -#define Dynarr_unlock(d) ((d)->locked = 0) -#else -#define Dynarr_verify(d) (d) -#define Dynarr_verify_mod(d) (d) -#define Dynarr_lock(d) -#define Dynarr_unlock(d) -#endif /* ERROR_CHECK_STRUCTURES */ - -#define Dynarr_length(d) (Dynarr_verify (d)->len) -#define Dynarr_largest(d) (Dynarr_verify (d)->largest) -#define Dynarr_reset(d) (Dynarr_verify_mod (d)->len = 0) + + +/************* Dynarr length/size retrieval and setting *************/ + +/* Retrieve the length of a Dynarr. The `+ 0' is to ensure that this cannot + be used as an lvalue. */ +#define Dynarr_length(d) (Dynarr_verify (d)->len_ + 0) +/* Retrieve the largest ever length seen of a Dynarr. The `+ 0' is to + ensure that this cannot be used as an lvalue. */ +#define Dynarr_largest(d) (Dynarr_verify (d)->largest_ + 0) +/* Retrieve the number of elements that fit in the currently allocated + space. The `+ 0' is to ensure that this cannot be used as an lvalue. */ +#define Dynarr_max(d) (Dynarr_verify (d)->max_ + 0) +/* Retrieve the advertised memory usage of a Dynarr, i.e. the number of + bytes occupied by the elements in the Dynarr, not counting any overhead. */ +#define Dynarr_sizeof(d) (Dynarr_length (d) * (d)->elsize) +/* Actually set the length of a Dynarr. This is a low-level routine that + should not be directly used; use Dynarr_set_length() instead if you need + to, but be very careful when doing so! */ +#define Dynarr_set_length_1(d, n) \ +do { \ + Elemcount _dsl1_n = (n); \ + structure_checking_assert (_dsl1_n >= 0 && _dsl1_n <= Dynarr_max (d)); \ + (void) Dynarr_verify_mod (d); \ + (d)->len_ = _dsl1_n; \ + /* Use the raw field references here otherwise we get a crash because \ + we've set the length but not yet fixed up the largest value. */ \ + if ((d)->len_ > (d)->largest_) \ + (d)->largest_ = (d)->len_; \ + (void) Dynarr_verify_mod (d); \ +} while (0) + +/* The following two defines will get you into real trouble if you aren't + careful. But they can save a lot of execution time when used wisely. */ +#define Dynarr_set_length(d, n) \ +do { \ + Elemcount _dsl_n = (n); \ + structure_checking_assert (_dsl_n >= 0 && _dsl_n <= Dynarr_largest (d)); \ + Dynarr_set_length_1 (d, _dsl_n); \ +} while (0) +#define Dynarr_increment(d) \ + Dynarr_set_length (d, Dynarr_length (d) + 1) + +/* Reset the Dynarr's length to 0. */ +#define Dynarr_reset(d) Dynarr_set_length (d, 0) + +MODULE_API void Dynarr_resize (void *dy, Elemcount size); + +#define Dynarr_resize_if(d, numels) \ +do { \ + Elemcount _dri_numels = (numels); \ + if (Dynarr_length (d) + _dri_numels > Dynarr_max (d)) \ + Dynarr_resize (d, Dynarr_length (d) + _dri_numels); \ +} while (0) + +#ifdef MEMORY_USAGE_STATS +struct overhead_stats; +Bytecount Dynarr_memory_usage (void *d, struct overhead_stats *stats); +#endif + +/************* Adding/deleting elements to/from a Dynarr *************/ + +#ifdef NEW_GC +#define Dynarr_add(d, el) \ +do { \ + const struct lrecord_implementation *imp = (d)->lisp_imp; \ + (void) Dynarr_verify_mod (d); \ + Dynarr_resize_if (d, 1); \ + ((d)->base)[Dynarr_length (d)] = (el); \ + if (imp) \ + set_lheader_implementation \ + ((struct lrecord_header *)&(((d)->base)[Dynarr_length (d)]), imp); \ + Dynarr_set_length_1 (d, Dynarr_length (d) + 1); \ + (void) Dynarr_verify_mod (d); \ +} while (0) +#else /* not NEW_GC */ +#define Dynarr_add(d, el) \ +do { \ + (void) Dynarr_verify_mod (d); \ + Dynarr_resize_if (d, 1); \ + ((d)->base)[Dynarr_length (d)] = (el); \ + Dynarr_set_length_1 (d, Dynarr_length (d) + 1); \ + (void) Dynarr_verify_mod (d); \ +} while (0) +#endif /* not NEW_GC */ + + +MODULE_API void Dynarr_insert_many (void *d, const void *el, int len, + int start); +MODULE_API void Dynarr_delete_many (void *d, int start, int len); + #define Dynarr_insert_many_at_start(d, el, len) \ Dynarr_insert_many (d, el, len, 0) #define Dynarr_add_literal_string(d, s) Dynarr_add_many (d, s, sizeof (s) - 1) @@ -1919,30 +2011,6 @@ Dynarr_add_many (d, dyna_ls_eb, dyna_ls_bc); \ } while (0) -#ifdef NEW_GC -#define Dynarr_add(d, el) \ -do { \ - const struct lrecord_implementation *imp = (d)->lisp_imp; \ - if (Dynarr_verify_mod (d)->len >= (d)->max) \ - Dynarr_resize ((d), (d)->len+1); \ - ((d)->base)[(d)->len] = (el); \ - \ - if (imp) \ - set_lheader_implementation \ - ((struct lrecord_header *)&(((d)->base)[(d)->len]), imp); \ - \ - (d)->len++; \ - if ((d)->len > (d)->largest) \ - (d)->largest = (d)->len; \ -} while (0) -#else /* not NEW_GC */ -#define Dynarr_add(d, el) ( \ - Dynarr_verify_mod (d)->len >= (d)->max ? Dynarr_resize ((d), (d)->len+1) : \ - (void) 0, \ - ((d)->base)[(d)->len++] = (el), \ - (d)->len > (d)->largest ? (d)->largest = (d)->len : (int) 0) -#endif /* not NEW_GC */ - /* Add LEN contiguous elements to a Dynarr */ DECLARE_INLINE_HEADER ( @@ -1953,33 +2021,20 @@ /* This duplicates Dynarr_insert_many to some extent; but since it is called so often, it seemed useful to remove the unnecessary stuff from that function and to make it inline */ - Dynarr *dy = (Dynarr *) Dynarr_verify (d); - - if (dy->len + len > dy->max) - Dynarr_resize (dy, dy->len + len); + Dynarr *dy = Dynarr_verify_mod (d); + Dynarr_resize_if (dy, len); /* Some functions call us with a value of 0 to mean "reserve space but don't write into it" */ if (el) - memcpy ((char *) dy->base + dy->len*dy->elsize, el, len*dy->elsize); - dy->len += len; - - if (dy->len > dy->largest) - dy->largest = dy->len; + memcpy ((char *) dy->base + Dynarr_sizeof (dy), el, len*dy->elsize); + Dynarr_set_length_1 (dy, Dynarr_length (dy) + len); + (void) Dynarr_verify_mod (dy); } -/* The following defines will get you into real trouble if you aren't - careful. But they can save a lot of execution time when used wisely. */ -#define Dynarr_increment(d) (Dynarr_verify_mod (d)->len++) -#define Dynarr_set_size(d, n) \ -do { \ - Bytecount _dss_n = (n); \ - structure_checking_assert (_dss_n >= 0 && _dss_n <= (d)->largest); \ - Dynarr_verify_mod (d)->len = _dss_n; \ -} while (0) - #define Dynarr_pop(d) \ - (assert ((d)->len > 0), Dynarr_verify_mod (d)->len--, \ - Dynarr_at (d, (d)->len)) + (structure_checking_assert (Dynarr_length (d) > 0), \ + Dynarr_verify_mod (d)->len_--, \ + Dynarr_at (d, Dynarr_length (d))) #define Dynarr_delete(d, i) Dynarr_delete_many (d, i, 1) #define Dynarr_delete_by_pointer(d, p) \ Dynarr_delete_many (d, (p) - ((d)->base), 1) @@ -1995,17 +2050,7 @@ } \ } while (0) -#ifdef MEMORY_USAGE_STATS -struct overhead_stats; -Bytecount Dynarr_memory_usage (void *d, struct overhead_stats *stats); -#endif - -void *stack_like_malloc (Bytecount size); -void stack_like_free (void *val); - -/* ------------------------------- */ -/* Dynarr typedefs */ -/* ------------------------------- */ +/************* Dynarr typedefs *************/ /* Dynarr typedefs -- basic types first */ @@ -2130,6 +2175,17 @@ Dynarr_declare (Lisp_Object *); } Lisp_Object_ptr_dynarr; + +/************* Stack-like malloc/free: Another allocator *************/ + +void *stack_like_malloc (Bytecount size); +void stack_like_free (void *val); + + +/************************************************************************/ +/** Definitions of other basic Lisp objects **/ +/************************************************************************/ + /*------------------------------ unbound -------------------------------*/ /* Qunbound is a special Lisp_Object (actually of type