Mercurial > hg > xemacs-beta

comparison src/dynarr.c @ 4967:0d4c9d0f6a8d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 19a72041c5ed
children 16112448d484
comparison
equal deleted inserted replaced
4966:48b63cd88a21 4967:0d4c9d0f6a8d
155 { 155 {
156 if (DUMPEDP (dy->base)) 156 if (DUMPEDP (dy->base))
157 { 157 {
158 void *new_base = malloc (new_size * dy->elsize); 158 void *new_base = malloc (new_size * dy->elsize);
159 memcpy (new_base, dy->base, 159 memcpy (new_base, dy->base,
160 (dy->max < new_size ? dy->max : new_size) * dy->elsize); 160 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
161 dy->elsize);
161 dy->base = new_base; 162 dy->base = new_base;
162 } 163 }
163 else 164 else
164 dy->base = xrealloc (dy->base, new_size * dy->elsize); 165 dy->base = xrealloc (dy->base, new_size * dy->elsize);
165 } 166 }
184 Dynarr_lisp_realloc (Dynarr *dy, int new_size) 185 Dynarr_lisp_realloc (Dynarr *dy, int new_size)
185 { 186 {
186 void *new_base = alloc_lrecord_array (dy->elsize, new_size, dy->lisp_imp); 187 void *new_base = alloc_lrecord_array (dy->elsize, new_size, dy->lisp_imp);
187 if (dy->base) 188 if (dy->base)
188 memcpy (new_base, dy->base, 189 memcpy (new_base, dy->base,
189 (dy->max < new_size ? dy->max : new_size) * dy->elsize); 190 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
191 dy->elsize);
190 dy->base = new_base; 192 dy->base = new_base;
191 } 193 }
192 194
193 void * 195 void *
194 Dynarr_lisp_newf (int elsize, 196 Dynarr_lisp_newf (int elsize,
208 { 210 {
209 int newsize; 211 int newsize;
210 double multiplier; 212 double multiplier;
211 Dynarr *dy = (Dynarr *) Dynarr_verify (d); 213 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
212 214
213 if (dy->max <= 8) 215 if (Dynarr_max (dy) <= 8)
214 multiplier = 2; 216 multiplier = 2;
215 else 217 else
216 multiplier = 1.5; 218 multiplier = 1.5;
217 219
218 for (newsize = dy->max; newsize < size;) 220 for (newsize = Dynarr_max (dy); newsize < size;)
219 newsize = max (Dynarr_min_size, (int) (multiplier * newsize)); 221 newsize = max (Dynarr_min_size, (int) (multiplier * newsize));
220 222
221 /* Don't do anything if the array is already big enough. */ 223 /* Don't do anything if the array is already big enough. */
222 if (newsize > dy->max) 224 if (newsize > Dynarr_max (dy))
223 { 225 {
224 #ifdef NEW_GC 226 #ifdef NEW_GC
225 if (dy->lisp_imp) 227 if (dy->lisp_imp)
226 Dynarr_lisp_realloc (dy, newsize); 228 Dynarr_lisp_realloc (dy, newsize);
227 else 229 else
228 Dynarr_realloc (dy, newsize); 230 Dynarr_realloc (dy, newsize);
229 #else /* not NEW_GC */ 231 #else /* not NEW_GC */
230 Dynarr_realloc (dy, newsize); 232 Dynarr_realloc (dy, newsize);
231 #endif /* not NEW_GC */ 233 #endif /* not NEW_GC */
232 dy->max = newsize; 234 dy->max_ = newsize;
233 } 235 }
234 } 236 }
235 237
236 /* Add a number of contiguous elements to the array starting at START. */ 238 /* Add a number of contiguous elements to the array starting at START. */
237 void 239 void
238 Dynarr_insert_many (void *d, const void *el, int len, int start) 240 Dynarr_insert_many (void *d, const void *el, int len, int start)
239 { 241 {
240 Dynarr *dy = (Dynarr *) Dynarr_verify (d); 242 Dynarr *dy = Dynarr_verify_mod (d);
241 243
242 if (dy->len + len > dy->max) 244 Dynarr_resize_if (dy, len);
243 Dynarr_resize (dy, dy->len + len); 245
244 #if 0
245 /* WTF? We should be catching these problems. */
246 /* Silently adjust start to be valid. */
247 if (start > dy->len)
248 start = dy->len;
249 else if (start < 0)
250 start = 0;
251 #else
252 /* #### This could conceivably be wrong, if code wants to access stuff 246 /* #### This could conceivably be wrong, if code wants to access stuff
253 between len and largest. */ 247 between len and largest. */
254 type_checking_assert (start >= 0 && start <= dy->len); 248 structure_checking_assert (start >= 0 && start <= Dynarr_length (dy));
255 #endif 249
256 250 if (start != Dynarr_length (dy))
257 if (start != dy->len)
258 { 251 {
259 memmove ((char *) dy->base + (start + len)*dy->elsize, 252 memmove ((char *) dy->base + (start + len)*dy->elsize,
260 (char *) dy->base + start*dy->elsize, 253 (char *) dy->base + start*dy->elsize,
261 (dy->len - start)*dy->elsize); 254 (Dynarr_length (dy) - start)*dy->elsize);
262 } 255 }
256 /* Some functions call us with a value of 0 to mean "reserve space but
257 don't write into it" */
263 if (el) 258 if (el)
264 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize); 259 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize);
265 dy->len += len; 260
266 261 Dynarr_set_length_1 (dy, Dynarr_length (dy) + len);
267 if (dy->len > dy->largest) 262 (void) Dynarr_verify_mod (dy);
268 dy->largest = dy->len;
269 } 263 }
270 264
271 void 265 void
272 Dynarr_delete_many (void *d, int start, int len) 266 Dynarr_delete_many (void *d, int start, int len)
273 { 267 {
274 Dynarr *dy = (Dynarr *) Dynarr_verify (d); 268 Dynarr *dy = Dynarr_verify_mod (d);
275 269
276 type_checking_assert (start >= 0 && len >= 0 && start + len <= dy->len); 270 structure_checking_assert (start >= 0 && len >= 0 &&
271 start + len <= Dynarr_length (dy));
272
277 memmove ((char *) dy->base + start*dy->elsize, 273 memmove ((char *) dy->base + start*dy->elsize,
278 (char *) dy->base + (start + len)*dy->elsize, 274 (char *) dy->base + (start + len)*dy->elsize,
279 (dy->len - start - len)*dy->elsize); 275 (Dynarr_length (dy) - start - len)*dy->elsize);
280 dy->len -= len; 276
277 Dynarr_set_length_1 (dy, Dynarr_length (dy) - len);
278 (void) Dynarr_verify_mod (dy);
281 } 279 }
282 280
283 void 281 void
284 Dynarr_free (void *d) 282 Dynarr_free (void *d)
285 { 283 {
324 memory that malloc() will claim as "requested" was actually 322 memory that malloc() will claim as "requested" was actually
325 requested. */ 323 requested. */
326 324
327 if (dy->base) 325 if (dy->base)
328 { 326 {
329 Bytecount malloc_used = malloced_storage_size (dy->base, 327 Bytecount malloc_used =
330 dy->elsize * dy->max, 0); 328 malloced_storage_size (dy->base, dy->elsize * Dynarr_max (dy), 0);
331 /* #### This may or may not be correct. Some Dynarrs would 329 /* #### This may or may not be correct. Some Dynarrs would
332 prefer that we use dy->len instead of dy->largest here. */ 330 prefer that we use dy->len instead of dy->largest here. */
333 Bytecount was_requested = dy->elsize * dy->largest; 331 Bytecount was_requested = dy->elsize * Dynarr_largest (dy);
334 Bytecount dynarr_overhead = dy->elsize * (dy->max - dy->largest); 332 Bytecount dynarr_overhead =
333 dy->elsize * (Dynarr_max (dy) - Dynarr_largest (dy));
335 334
336 total += malloc_used; 335 total += malloc_used;
337 stats->was_requested += was_requested; 336 stats->was_requested += was_requested;
338 stats->dynarr_overhead += dynarr_overhead; 337 stats->dynarr_overhead += dynarr_overhead;
339 /* And the remainder must be malloc overhead. */ 338 /* And the remainder must be malloc overhead. */
378 else 377 else
379 this_one = Dynarr_new (char); 378 this_one = Dynarr_new (char);
380 Dynarr_add (stack_like_in_use_list, this_one); 379 Dynarr_add (stack_like_in_use_list, this_one);
381 Dynarr_reset (this_one); 380 Dynarr_reset (this_one);
382 Dynarr_add_many (this_one, 0, size); 381 Dynarr_add_many (this_one, 0, size);
383 return Dynarr_atp (this_one, 0); 382 return Dynarr_begin (this_one);
384 } 383 }
385 384
386 void 385 void
387 stack_like_free (void *val) 386 stack_like_free (void *val)
388 { 387 {
390 assert (len > 0); 389 assert (len > 0);
391 /* The vast majority of times, we will be called in a last-in first-out 390 /* The vast majority of times, we will be called in a last-in first-out
392 order, and the item at the end of the list will be the one we're 391 order, and the item at the end of the list will be the one we're
393 looking for, so just check for this first and avoid any function 392 looking for, so just check for this first and avoid any function
394 calls. */ 393 calls. */
395 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, len - 1), 0) == val) 394 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, len - 1)) == val)
396 { 395 {
397 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list); 396 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
398 Dynarr_add (stack_like_free_list, this_one); 397 Dynarr_add (stack_like_free_list, this_one);
399 } 398 }
400 else 399 else
401 { 400 {
402 /* Find the item and delete it. */ 401 /* Find the item and delete it. */
403 int i; 402 int i;
404 assert (len >= 2); 403 assert (len >= 2);
405 for (i = len - 2; i >= 0; i--) 404 for (i = len - 2; i >= 0; i--)
406 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, i), 0) == 405 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, i)) ==
407 val) 406 val)
408 { 407 {
409 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i); 408 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
410 Dynarr_add (stack_like_free_list, this_one); 409 Dynarr_add (stack_like_free_list, this_one);
411 Dynarr_delete (stack_like_in_use_list, i); 410 Dynarr_delete (stack_like_in_use_list, i);