xemacs-beta: src/array.h annotate

annotate src/array.h @ 5168:cf900a2f1fa3

extract gap array from extents.c, use in range tables -------------------- ChangeLog entries follow: -------------------- src/ChangeLog addition: 2010-03-22 Ben Wing <ben@xemacs.org> * Makefile.in.in (objs): * array.c: * array.c (gap_array_adjust_markers): * array.c (gap_array_move_gap): * array.c (gap_array_make_gap): * array.c (gap_array_insert_els): * array.c (gap_array_delete_els): * array.c (gap_array_make_marker): * array.c (gap_array_delete_marker): * array.c (gap_array_delete_all_markers): * array.c (gap_array_clone): * array.h: * depend: * emacs.c (main_1): * extents.c: * extents.c (EXTENT_GAP_ARRAY_AT): * extents.c (extent_list_num_els): * extents.c (extent_list_locate): * extents.c (extent_list_at): * extents.c (extent_list_delete_all): * extents.c (allocate_extent_list): * extents.c (syms_of_extents): * extents.h: * extents.h (XEXTENT_LIST_MARKER): * lisp.h: * rangetab.c: * rangetab.c (mark_range_table): * rangetab.c (print_range_table): * rangetab.c (range_table_equal): * rangetab.c (range_table_hash): * rangetab.c (verify_range_table): * rangetab.c (get_range_table_pos): * rangetab.c (Fmake_range_table): * rangetab.c (Fcopy_range_table): * rangetab.c (Fget_range_table): * rangetab.c (put_range_table): * rangetab.c (Fclear_range_table): * rangetab.c (Fmap_range_table): * rangetab.c (unified_range_table_bytes_needed): * rangetab.c (unified_range_table_copy_data): * rangetab.c (unified_range_table_lookup): * rangetab.h: * rangetab.h (struct range_table_entry): * rangetab.h (struct Lisp_Range_Table): * rangetab.h (rangetab_gap_array_at): * symsinit.h: Rename dynarr.c to array.c. Move gap array from extents.c to array.c. Extract dynarr, gap array and stack-like malloc into new file array.h. Rename GAP_ARRAY_NUM_ELS -> gap_array_length(). Add gap_array_at(), gap_array_atp(). Rewrite range table code to use gap arrays. Make put_range_table() smarter so that its operation is O(log n) for adding a localized range. * gc.c (lispdesc_block_size_1): Don't ABORT() when two elements are located at the same place. This will happen with a size-0 gap array -- both parts of the array (before and after gap) are in the same place.

author	Ben Wing <ben@xemacs.org>
date	Mon, 22 Mar 2010 19:12:15 -0500
parents
children	6c6d78781d59

rev	line source
5168 cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	1 /* Header for arrays (dynarrs, gap arrays, etc.).
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	2 Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	3 Copyright (C) 1996, 2001, 2002, 2004, 2005, 2009, 2010 Ben Wing.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	4
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	5 This file is part of XEmacs.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	6
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	7 XEmacs is free software; you can redistribute it and/or modify it
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	8 under the terms of the GNU General Public License as published by the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	9 Free Software Foundation; either version 2, or (at your option) any
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	10 later version.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	11
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	15 for more details.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	16
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	17 You should have received a copy of the GNU General Public License
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	18 along with XEmacs; see the file COPYING. If not, write to
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	20 Boston, MA 02111-1307, USA. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	21
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	22 /* Synched up with: Not in FSF. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	23
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	24 /* This file has been Mule-ized, Ben Wing, 10-13-04. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	25
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	26 #ifndef INCLUDED_array_h_
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	27 #define INCLUDED_array_h_
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	28
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	29 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	30 / Definition of dynamic arrays (dynarrs) /
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	31 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	32
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	33 BEGIN_C_DECLS
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	34
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	35 /*********** Dynarr declaration ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	36
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	37 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	38 #define DECLARE_DYNARR_LISP_IMP() \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	39 const struct lrecord_implementation *lisp_imp;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	40 #else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	41 #define DECLARE_DYNARR_LISP_IMP()
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	42 #endif
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	43
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	44 #ifdef ERROR_CHECK_DYNARR
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	45 #define DECLARE_DYNARR_LOCKED() \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	46 int locked;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	47 #else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	48 #define DECLARE_DYNARR_LOCKED()
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	49 #endif
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	50
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	51 #define Dynarr_declare(type) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	52 struct lrecord_header header; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	53 type *base; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	54 DECLARE_DYNARR_LISP_IMP () \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	55 DECLARE_DYNARR_LOCKED () \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	56 int elsize_; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	57 int len_; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	58 int largest_; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	59 int max_
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	60
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	61 typedef struct dynarr
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	62 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	63 Dynarr_declare (void);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	64 } Dynarr;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	65
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	66 #define XD_DYNARR_DESC(base_type, sub_desc) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	67 { XD_BLOCK_PTR, offsetof (base_type, base), \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	68 XD_INDIRECT(1, 0), {sub_desc} }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	69 { XD_INT, offsetof (base_type, len_) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	70 { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	71 { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	72
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	73 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	74 #define XD_LISP_DYNARR_DESC(base_type, sub_desc) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	75 { XD_LISP_OBJECT_BLOCK_PTR, offsetof (base_type, base), \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	76 XD_INDIRECT(1, 0), {sub_desc} }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	77 { XD_INT, offsetof (base_type, len_) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	78 { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	79 { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	80 #endif /* NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	81
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	82 /*********** Dynarr verification ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	83
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	84 /* Dynarr locking and verification.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	85
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	86 [I] VERIFICATION
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	87
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	88 Verification routines simply return their basic argument, possibly
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	89 casted, but in the process perform some verification on it, aborting if
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	90 the verification fails. The verification routines take FILE and LINE
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	91 parameters, and use them to output the file and line of the caller
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	92 when an abort occurs, rather than the file and line of the inline
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	93 function, which is less than useful.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	94
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	95 There are three basic types of verification routines:
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	96
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	97 (1) Verify the dynarr itself. This verifies the basic invariant
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	98 involving the length/size values:
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	99
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	100 0 <= Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	101
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	102 (2) Verify the dynarr itself prior to modifying it. This performs
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	103 the same verification as previously, but also checks that the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	104 dynarr is not locked (see below).
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	105
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	106 (3) Verify a dynarr position. Unfortunately we have to have
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	107 different verification routines depending on which kind of operation
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	108 is being performed:
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	109
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	110 (a) For Dynarr_at(), we check that the POS is bounded by Dynarr_largest(),
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	111 i.e. 0 <= POS < Dynarr_largest().
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	112 (b) For Dynarr_atp_allow_end(), we also have to allow
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	113 POS == Dynarr_largest().
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	114 (c) For Dynarr_atp(), we behave largely like Dynarr_at() but make a
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	115 special exception when POS == 0 and Dynarr_largest() == 0 -- see
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	116 comment below.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	117 (d) Some other routines contain the POS verification within their code,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	118 and make the check 0 <= POS < Dynarr_length() or
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	119 0 <= POS <= Dynarr_length().
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	120
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	121 #### It is not well worked-out whether and in what circumstances it's
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	122 allowed to use a position that is between Dynarr_length() and
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	123 Dynarr_largest(). The ideal solution is to never allow this, and require
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	124 instead that code first change the length before accessing higher
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	125 positions. That would require looking through all the code that accesses
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	126 dynarrs and fixing it appropriately (especially redisplay code, and
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	127 especially redisplay code in the vicinity of a reference to
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	128 Dynarr_largest(), since such code usually checks explicitly to see whether
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	129 there is extra stuff between Dynarr_length() and Dynarr_largest().)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	130
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	131 [II] LOCKING
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	132
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	133 The idea behind dynarr locking is simple: Locking a dynarr prevents
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	134 any modification from occurring, or rather, leads to an abort upon
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	135 any attempt to modify a dynarr.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	136
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	137 Dynarr locking was originally added to catch some sporadic and hard-to-
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	138 debug crashes in the redisplay code where dynarrs appeared to be getting
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	139 corrupted in an unexpected fashion. The solution was to lock the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	140 dynarrs that were getting corrupted (in this case, the display-line
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	141 dynarrs) around calls to routines that weren't supposed to be changing
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	142 these dynarrs but might somehow be calling code that modified them.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	143 This eventually revealed that there was a reentrancy problem with
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	144 redisplay that involved the QUIT mechanism and the processing done in
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	145 order to determine whether C-g had been pressed -- this processing
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	146 involves retrieving, processing and queueing pending events to see
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	147 whether any of them result in a C-g keypress. However, at least under
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	148 MS Windows this can result in redisplay being called reentrantly.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	149 For more info:--
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	150
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	151 (Info-goto-node "(internals)Critical Redisplay Sections")
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	152
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	153 */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	154
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	155 #ifdef ERROR_CHECK_DYNARR
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	156 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	157 int
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	158 Dynarr_verify_pos_at (void d, Elemcount pos, const Ascbyte file, int line)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	159 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	160 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	161 Dynarr dy = (Dynarr ) d;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	162 /* We use `largest', not `len', because the redisplay code often
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	163 accesses stuff between len and largest. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	164 assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	165 return pos;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	166 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	167
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	168 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	169 int
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	170 Dynarr_verify_pos_atp (void d, Elemcount pos, const Ascbyte file, int line)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	171 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	172 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	173 Dynarr dy = (Dynarr ) d;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	174 /* We use `largest', not `len', because the redisplay code often
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	175 accesses stuff between len and largest. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	176 /* [[ Code will often do something like ...
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	177
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	178 val = make_bit_vector_from_byte_vector (Dynarr_atp (dyn, 0),
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	179 Dynarr_length (dyn));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	180
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	181 which works fine when the Dynarr_length is non-zero, but when zero,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	182 the result of Dynarr_atp() not only points past the end of the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	183 allocated array, but the array may not have ever been allocated and
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	184 hence the return value is NULL. But the length of 0 causes the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	185 pointer to never get checked. These can occur throughout the code
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	186 so we put in a special check. --ben ]]
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	187
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	188 Update: The common idiom `Dynarr_atp (dyn, 0)' has been changed to
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	189 `Dynarr_begin (dyn)'. Possibly this special check at POS 0 can be
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	190 done only for Dynarr_begin() not for general Dynarr_atp(). --ben */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	191 if (pos == 0 && dy->len_ == 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	192 return pos;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	193 /* #### It's vaguely possible that some code could legitimately want to
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	194 retrieve a pointer to the position just past the end of dynarr memory.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	195 This could happen with Dynarr_atp() but not Dynarr_at(). If so, it
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	196 will trigger this assert(). In such cases, it should be obvious that
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	197 the code wants to do this; rather than relaxing the assert, we should
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	198 probably create a new macro Dynarr_atp_allow_end() which is like
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	199 Dynarr_atp() but which allows for pointing at invalid addresses -- we
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	200 really want to check for cases of accessing just past the end of
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	201 memory, which is a likely off-by-one problem to occur and will usually
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	202 not trigger a protection fault (instead, you'll just get random
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	203 behavior, possibly overwriting other memory, which is bad). --ben */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	204 assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	205 return pos;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	206 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	207
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	208 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	209 int
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	210 Dynarr_verify_pos_atp_allow_end (void d, Elemcount pos, const Ascbyte file,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	211 int line)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	212 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	213 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	214 Dynarr dy = (Dynarr ) d;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	215 /* We use `largest', not `len', because the redisplay code often
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	216 accesses stuff between len and largest.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	217 We also allow referencing the very end, past the end of allocated
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	218 legitimately space. See comments in Dynarr_verify_pos_atp.()*/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	219 assert_at_line (pos >= 0 && pos <= dy->largest_, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	220 return pos;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	221 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	222
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	223 #else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	224 #define Dynarr_verify_pos_at(d, pos, file, line) (pos)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	225 #define Dynarr_verify_pos_atp(d, pos, file, line) (pos)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	226 #define Dynarr_verify_pos_atp_allow_end(d, pos, file, line) (pos)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	227 #endif /* ERROR_CHECK_DYNARR */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	228
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	229 #ifdef ERROR_CHECK_DYNARR
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	230 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	231 Dynarr *
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	232 Dynarr_verify_1 (void d, const Ascbyte file, int line)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	233 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	234 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	235 Dynarr dy = (Dynarr ) d;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	236 assert_at_line (dy->len_ >= 0 && dy->len_ <= dy->largest_ &&
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	237 dy->largest_ <= dy->max_, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	238 return dy;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	239 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	240
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	241 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	242 Dynarr *
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	243 Dynarr_verify_mod_1 (void d, const Ascbyte file, int line)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	244 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	245 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	246 Dynarr dy = (Dynarr ) d;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	247 assert_at_line (!dy->locked, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	248 return Dynarr_verify_1 (d, file, line);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	249 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	250
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	251 #define Dynarr_verify(d) Dynarr_verify_1 (d, __FILE__, __LINE__)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	252 #define Dynarr_verify_mod(d) Dynarr_verify_mod_1 (d, __FILE__, __LINE__)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	253
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	254 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	255 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	256 Dynarr_lock (void *d)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	257 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	258 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	259 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	260 dy->locked = 1;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	261 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	262
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	263 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	264 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	265 Dynarr_unlock (void *d)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	266 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	267 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	268 Dynarr *dy = Dynarr_verify (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	269 assert (dy->locked);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	270 dy->locked = 0;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	271 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	272
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	273 #else /* not ERROR_CHECK_DYNARR */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	274
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	275 #define Dynarr_verify(d) ((Dynarr *) d)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	276 #define Dynarr_verify_mod(d) ((Dynarr *) d)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	277 #define Dynarr_lock(d) DO_NOTHING
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	278 #define Dynarr_unlock(d) DO_NOTHING
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	279
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	280 #endif /* ERROR_CHECK_DYNARR */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	281
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	282 /*********** Dynarr creation ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	283
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	284 MODULE_API void *Dynarr_newf (Bytecount elsize);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	285 MODULE_API void Dynarr_free (void *d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	286
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	287 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	288 MODULE_API void *Dynarr_lisp_newf (Bytecount elsize,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	289 const struct lrecord_implementation
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	290 *dynarr_imp,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	291 const struct lrecord_implementation *imp);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	292
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	293 #define Dynarr_lisp_new(type, dynarr_imp, imp) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	294 ((type##_dynarr *) Dynarr_lisp_newf (sizeof (type), dynarr_imp, imp))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	295 #define Dynarr_lisp_new2(dynarr_type, type, dynarr_imp, imp) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	296 ((dynarr_type *) Dynarr_lisp_newf (sizeof (type)), dynarr_imp, imp)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	297 #endif /* NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	298 #define Dynarr_new(type) ((type##_dynarr *) Dynarr_newf (sizeof (type)))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	299 #define Dynarr_new2(dynarr_type, type) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	300 ((dynarr_type *) Dynarr_newf (sizeof (type)))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	301
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	302 /*********** Dynarr access ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	303
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	304 #ifdef ERROR_CHECK_DYNARR
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	305 #define Dynarr_at(d, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	306 ((d)->base[Dynarr_verify_pos_at (d, pos, __FILE__, __LINE__)])
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	307 #define Dynarr_atp_allow_end(d, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	308 (&((d)->base[Dynarr_verify_pos_atp_allow_end (d, pos, __FILE__, __LINE__)]))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	309 #define Dynarr_atp(d, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	310 (&((d)->base[Dynarr_verify_pos_atp (d, pos, __FILE__, __LINE__)]))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	311 #else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	312 #define Dynarr_at(d, pos) ((d)->base[pos])
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	313 #define Dynarr_atp(d, pos) (&Dynarr_at (d, pos))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	314 #define Dynarr_atp_allow_end(d, pos) Dynarr_atp (d, pos)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	315 #endif
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	316
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	317 /* Old #define Dynarr_atp(d, pos) (&Dynarr_at (d, pos)) */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	318 #define Dynarr_begin(d) Dynarr_atp (d, 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	319 #define Dynarr_lastp(d) Dynarr_atp (d, Dynarr_length (d) - 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	320 #define Dynarr_past_lastp(d) Dynarr_atp_allow_end (d, Dynarr_length (d))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	321
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	322
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	323 /*********** Dynarr length/size retrieval and setting ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	324
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	325 /* Retrieve the length of a dynarr. The `+ 0' is to ensure that this cannot
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	326 be used as an lvalue. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	327 #define Dynarr_length(d) (Dynarr_verify (d)->len_ + 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	328 /* Retrieve the largest ever length seen of a dynarr. The `+ 0' is to
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	329 ensure that this cannot be used as an lvalue. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	330 #define Dynarr_largest(d) (Dynarr_verify (d)->largest_ + 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	331 /* Retrieve the number of elements that fit in the currently allocated
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	332 space. The `+ 0' is to ensure that this cannot be used as an lvalue. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	333 #define Dynarr_max(d) (Dynarr_verify (d)->max_ + 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	334 /* Return the size in bytes of an element in a dynarr. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	335 #define Dynarr_elsize(d) (Dynarr_verify (d)->elsize_ + 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	336 /* Retrieve the advertised memory usage of a dynarr, i.e. the number of
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	337 bytes occupied by the elements in the dynarr, not counting any overhead. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	338 #define Dynarr_sizeof(d) (Dynarr_length (d) * Dynarr_elsize (d))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	339
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	340 /* Actually set the length of a dynarr. This is a low-level routine that
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	341 should not be directly used; use Dynarr_set_length() or
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	342 Dynarr_set_lengthr() instead. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	343 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	344 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	345 Dynarr_set_length_1 (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	346 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	347 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	348 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	349 dynarr_checking_assert (len >= 0 && len <= Dynarr_max (dy));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	350 /* Use the raw field references here otherwise we get a crash because
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	351 we've set the length but not yet fixed up the largest value. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	352 dy->len_ = len;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	353 if (dy->len_ > dy->largest_)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	354 dy->largest_ = dy->len_;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	355 (void) Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	356 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	357
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	358 /* "Restricted set-length": Set the length of dynarr D to LEN,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	359 which must be in the range [0, Dynarr_largest(d)]. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	360
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	361 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	362 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	363 Dynarr_set_lengthr (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	364 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	365 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	366 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	367 dynarr_checking_assert (len >= 0 && len <= Dynarr_largest (dy));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	368 Dynarr_set_length_1 (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	369 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	370
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	371 /* "Restricted increment": Increment the length of dynarr D by 1; the resulting
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	372 length must be in the range [0, Dynarr_largest(d)]. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	373
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	374 #define Dynarr_incrementr(d) Dynarr_set_lengthr (d, Dynarr_length (d) + 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	375
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	376
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	377 MODULE_API void Dynarr_resize (void *d, Elemcount size);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	378
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	379 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	380 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	381 Dynarr_resize_to_fit (void *d, Elemcount size)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	382 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	383 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	384 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	385 if (size > Dynarr_max (dy))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	386 Dynarr_resize (dy, size);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	387 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	388
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	389 #define Dynarr_resize_to_add(d, numels) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	390 Dynarr_resize_to_fit (d, Dynarr_length (d) + numels)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	391
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	392 /* This is an optimization. This is like Dynarr_set_length() but the length
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	393 is guaranteed to be at least as big as the existing length. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	394
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	395 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	396 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	397 Dynarr_increase_length (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	398 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	399 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	400 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	401 dynarr_checking_assert (len >= Dynarr_length (dy));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	402 Dynarr_resize_to_fit (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	403 Dynarr_set_length_1 (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	404 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	405
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	406 /* Set the length of dynarr D to LEN. If the length increases, resize as
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	407 necessary to fit. (NOTE: This will leave uninitialized memory. If you
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	408 aren't planning on immediately overwriting the memory, use
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	409 Dynarr_set_length_and_zero() to zero out all the memory that would
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	410 otherwise be uninitialized.) */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	411
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	412 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	413 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	414 Dynarr_set_length (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	415 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	416 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	417 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	418 Elemcount old_len = Dynarr_length (dy);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	419 if (old_len >= len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	420 Dynarr_set_lengthr (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	421 else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	422 Dynarr_increase_length (d, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	423 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	424
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	425 #define Dynarr_increment(d) Dynarr_increase_length (d, Dynarr_length (d) + 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	426
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	427 /* Zero LEN contiguous elements starting at POS. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	428
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	429 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	430 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	431 Dynarr_zero_many (void *d, Elemcount pos, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	432 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	433 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	434 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	435 memset ((Rawbyte ) dy->base + posDynarr_elsize (dy), 0,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	436 len*Dynarr_elsize (dy));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	437 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	438
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	439 /* This is an optimization. This is like Dynarr_set_length_and_zero() but
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	440 the length is guaranteed to be at least as big as the existing
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	441 length. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	442
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	443 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	444 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	445 Dynarr_increase_length_and_zero (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	446 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	447 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	448 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	449 Elemcount old_len = Dynarr_length (dy);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	450 Dynarr_increase_length (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	451 Dynarr_zero_many (dy, old_len, len - old_len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	452 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	453
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	454 /* Set the length of dynarr D to LEN. If the length increases, resize as
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	455 necessary to fit and zero out all the elements between the old and new
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	456 lengths. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	457
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	458 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	459 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	460 Dynarr_set_length_and_zero (void *d, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	461 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	462 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	463 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	464 Elemcount old_len = Dynarr_length (dy);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	465 if (old_len >= len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	466 Dynarr_set_lengthr (dy, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	467 else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	468 Dynarr_increase_length_and_zero (d, len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	469 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	470
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	471 /* Reset the dynarr's length to 0. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	472 #define Dynarr_reset(d) Dynarr_set_lengthr (d, 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	473
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	474 #ifdef MEMORY_USAGE_STATS
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	475 struct usage_stats;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	476 Bytecount Dynarr_memory_usage (void d, struct usage_stats stats);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	477 #endif
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	478
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	479 /*********** Adding/deleting elements to/from a dynarr ***********/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	480
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	481 /* Set the Lisp implementation of the element at POS in dynarr D. Only
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	482 does this if the dynarr holds Lisp objects of a particular type (the
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	483 objects themselves, not pointers to them), and only under NEW_GC. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	484
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	485 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	486 #define DYNARR_SET_LISP_IMP(d, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	487 do { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	488 if ((d)->lisp_imp) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	489 set_lheader_implementation \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	490 ((struct lrecord_header *)&(((d)->base)[pos]), (d)->lisp_imp); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	491 } while (0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	492 #else
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	493 #define DYNARR_SET_LISP_IMP(d, pos) DO_NOTHING
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	494 #endif /* (not) NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	495
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	496 /* Add Element EL to the end of dynarr D. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	497
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	498 #define Dynarr_add(d, el) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	499 do { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	500 Elemcount _da_pos = Dynarr_length (d); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	501 (void) Dynarr_verify_mod (d); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	502 Dynarr_increment (d); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	503 ((d)->base)[_da_pos] = (el); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	504 DYNARR_SET_LISP_IMP (d, _da_pos); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	505 } while (0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	506
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	507 /* Set EL as the element at position POS in dynarr D.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	508 Expand the dynarr as necessary so that its length is enough to include
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	509 position POS within it, and zero out any new elements created as a
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	510 result of expansion, other than the one at POS. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	511
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	512 #define Dynarr_set(d, pos, el) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	513 do { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	514 Elemcount _ds_pos = (pos); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	515 (void) Dynarr_verify_mod (d); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	516 if (Dynarr_length (d) < _ds_pos + 1) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	517 Dynarr_increase_length_and_zero (d, _ds_pos + 1); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	518 ((d)->base)[_ds_pos] = (el); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	519 DYNARR_SET_LISP_IMP (d, _ds_pos); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	520 } while (0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	521
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	522 /* Add LEN contiguous elements, stored at BASE, to dynarr D. If BASE is
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	523 NULL, reserve space but don't store anything. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	524
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	525 DECLARE_INLINE_HEADER (
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	526 void
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	527 Dynarr_add_many (void d, const void base, Elemcount len)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	528 )
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	529 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	530 /* This duplicates Dynarr_insert_many to some extent; but since it is
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	531 called so often, it seemed useful to remove the unnecessary stuff
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	532 from that function and to make it inline */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	533 Dynarr *dy = Dynarr_verify_mod (d);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	534 Elemcount pos = Dynarr_length (dy);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	535 Dynarr_increase_length (dy, Dynarr_length (dy) + len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	536 if (base)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	537 memcpy ((Rawbyte ) dy->base + posDynarr_elsize (dy), base,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	538 len*Dynarr_elsize (dy));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	539 }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	540
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	541 /* Insert LEN elements, currently pointed to by BASE, into dynarr D
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	542 starting at position POS. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	543
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	544 MODULE_API void Dynarr_insert_many (void d, const void base, Elemcount len,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	545 Elemcount pos);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	546
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	547 /* Prepend LEN elements, currently pointed to by BASE, to the beginning. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	548
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	549 #define Dynarr_prepend_many(d, base, len) Dynarr_insert_many (d, base, len, 0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	550
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	551 /* Add literal string S to dynarr D, which should hold chars or unsigned
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	552 chars. The final zero byte is not stored. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	553
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	554 #define Dynarr_add_literal_string(d, s) Dynarr_add_many (d, s, sizeof (s) - 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	555
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	556 /* Convert Lisp string S to an external encoding according to CODESYS and
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	557 add to dynarr D, which should hold chars or unsigned chars. No final
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	558 zero byte is appended. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	559
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	560 /* #### This should be an inline function but LISP_STRING_TO_SIZED_EXTERNAL
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	561 isn't declared yet. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	562
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	563 #define Dynarr_add_ext_lisp_string(d, s, codesys) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	564 do { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	565 Lisp_Object dyna_ls_s = (s); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	566 Lisp_Object dyna_ls_cs = (codesys); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	567 Extbyte *dyna_ls_eb; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	568 Bytecount dyna_ls_bc; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	569 \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	570 LISP_STRING_TO_SIZED_EXTERNAL (dyna_ls_s, dyna_ls_eb, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	571 dyna_ls_bc, dyna_ls_cs); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	572 Dynarr_add_many (d, dyna_ls_eb, dyna_ls_bc); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	573 } while (0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	574
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	575 /* Delete LEN elements starting at position POS. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	576
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	577 MODULE_API void Dynarr_delete_many (void *d, Elemcount pos, Elemcount len);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	578
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	579 /* Pop off (i.e. delete) the last element from the dynarr and return it */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	580
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	581 #define Dynarr_pop(d) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	582 (dynarr_checking_assert (Dynarr_length (d) > 0), \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	583 Dynarr_verify_mod (d)->len_--, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	584 Dynarr_at (d, Dynarr_length (d)))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	585
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	586 /* Delete the item at POS */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	587
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	588 #define Dynarr_delete(d, pos) Dynarr_delete_many (d, pos, 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	589
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	590 /* Delete the item located at memory address P, which must be a `type *'
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	591 pointer, where `type' is the type of the elements of the dynarr. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	592 #define Dynarr_delete_by_pointer(d, p) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	593 Dynarr_delete_many (d, (p) - ((d)->base), 1)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	594
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	595 /* Delete all elements that are numerically equal to EL. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	596
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	597 #define Dynarr_delete_object(d, el) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	598 do \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	599 { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	600 REGISTER int i; \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	601 for (i = Dynarr_length (d) - 1; i >= 0; i--) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	602 { \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	603 if (el == Dynarr_at (d, i)) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	604 Dynarr_delete_many (d, i, 1); \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	605 } \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	606 } while (0)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	607
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	608
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	609 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	610 / Stack-like malloc/free /
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	611 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	612
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	613 void *stack_like_malloc (Bytecount size);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	614 void stack_like_free (void *val);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	615
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	616
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	617
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	618 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	619 / Gap array /
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	620 /************************************************************************/
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	621
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	622 /* Holds a marker that moves as elements in the array are inserted and
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	623 deleted, similar to standard markers. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	624
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	625 typedef struct gap_array_marker
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	626 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	627 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	628 NORMAL_LISP_OBJECT_HEADER header;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	629 #endif /* NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	630 int pos;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	631 struct gap_array_marker *next;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	632 } Gap_Array_Marker;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	633
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	634
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	635 /* Holds a "gap array", which is an array of elements with a gap located
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	636 in it. Insertions and deletions with a high degree of locality
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	637 are very fast, essentially in constant time. Array positions as
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	638 used and returned in the gap array functions are independent of
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	639 the gap. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	640
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	641 /* Layout of gap array:
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	642
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	643 <------ gap ------><---- gapsize ----><----- numels - gap ---->
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	644 <---------------------- numels + gapsize --------------------->
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	645
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	646 For marking purposes, we use two extra variables computed from
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	647 the others -- the offset to the data past the gap, plus the number
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	648 of elements in that data:
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	649
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	650 offset_past_gap = elsize * (gap + gapsize)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	651 els_past_gap = numels - gap
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	652 */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	653
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	654
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	655 typedef struct gap_array
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	656 {
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	657 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	658 NORMAL_LISP_OBJECT_HEADER header;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	659 int is_lisp;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	660 #endif /* NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	661 Elemcount gap;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	662 Elemcount gapsize;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	663 Elemcount numels;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	664 Bytecount elsize;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	665 /* Redundant numbers computed from the others, for marking purposes */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	666 Bytecount offset_past_gap;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	667 Elemcount els_past_gap;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	668 Gap_Array_Marker *markers;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	669 /* this is a stretchy array */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	670 char array[1];
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	671 } Gap_Array;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	672
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	673 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	674 struct gap_array_marker;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	675
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	676 DECLARE_LISP_OBJECT (gap_array_marker, struct gap_array_marker);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	677 #define XGAP_ARRAY_MARKER(x) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	678 XRECORD (x, gap_array_marker, struct gap_array_marker)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	679 #define wrap_gap_array_marker(p) wrap_record (p, gap_array_marker)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	680 #define GAP_ARRAY_MARKERP(x) RECORDP (x, gap_array_marker)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	681 #define CHECK_GAP_ARRAY_MARKER(x) CHECK_RECORD (x, gap_array_marker)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	682 #define CONCHECK_GAP_ARRAY_MARKER(x) CONCHECK_RECORD (x, gap_array_marker)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	683
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	684 struct gap_array;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	685
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	686 DECLARE_LISP_OBJECT (gap_array, struct gap_array);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	687 #define XGAP_ARRAY(x) XRECORD (x, gap_array, struct gap_array)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	688 #define wrap_gap_array(p) wrap_record (p, gap_array)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	689 #define GAP_ARRAYP(x) RECORDP (x, gap_array)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	690 #define CHECK_GAP_ARRAY(x) CHECK_RECORD (x, gap_array)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	691 #define CONCHECK_GAP_ARRAY(x) CONCHECK_RECORD (x, gap_array)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	692 #endif /* NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	693
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	694 #ifdef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	695 #define XD_GAP_ARRAY_MARKER_DESC \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	696 { XD_LISP_OBJECT, offsetof (Gap_Array, markers) }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	697 #else /* not NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	698 #define XD_GAP_ARRAY_MARKER_DESC \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	699 { XD_BLOCK_PTR, offsetof (Gap_Array, markers), 1, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	700 { &gap_array_marker_description }, XD_FLAG_NO_KKCC }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	701 #endif /* not NEW_GC */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	702
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	703 #define XD_GAP_ARRAY_DESC(sub_desc) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	704 { XD_ELEMCOUNT, offsetof (Gap_Array, gap) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	705 { XD_BYTECOUNT, offsetof (Gap_Array, offset_past_gap) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	706 { XD_ELEMCOUNT, offsetof (Gap_Array, els_past_gap) }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	707 XD_GAP_ARRAY_MARKER_DESC, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	708 { XD_BLOCK_ARRAY, offsetof (Gap_Array, array), XD_INDIRECT (0, 0), \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	709 { sub_desc } }, \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	710 { XD_BLOCK_ARRAY, XD_INDIRECT (1, offsetof (Gap_Array, array)), \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	711 XD_INDIRECT (2, 0), { sub_desc } }
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	712
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	713 /* Convert a "memory position" (i.e. taking the gap into account) into
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	714 the address of the element at (i.e. after) that position. "Memory
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	715 positions" are only used internally and are of type Memxpos.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	716 "Array positions" are used externally and are of type Elemcount. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	717 #define GAP_ARRAY_MEMEL_ADDR(ga, memel) ((ga)->array + (ga)->elsize*(memel))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	718
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	719 /* Number of elements currently in a gap array */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	720 #define gap_array_length(ga) ((ga)->numels)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	721
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	722 #define gap_array_gappos(ga) ((ga)->gap)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	723 #define gap_array_gapsize(ga) ((ga)->gapsize)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	724
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	725 #define GAP_ARRAY_ARRAY_TO_MEMORY_POS_1(pos, gappos, gapsize) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	726 ((pos) < gappos ? (pos) : (pos) + gapsize)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	727
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	728 #define GAP_ARRAY_ARRAY_TO_MEMORY_POS(ga, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	729 GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (pos, (ga)->gap, (ga)->gapsize)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	730
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	731 #define GAP_ARRAY_MEMORY_TO_ARRAY_POS(ga, pos) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	732 ((pos) <= (ga)->gap ? (pos) : (pos) - (ga)->gapsize)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	733
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	734 /* Return a pointer to the element at a given position. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	735 #define gap_array_atp(ga, pos, type) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	736 ((type *) GAP_ARRAY_MEMEL_ADDR (ga, GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos)))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	737
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	738 /* Return the element at a given position. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	739 #define gap_array_at(ga, pos, type) (*gap_array_atp (ga, pos, type))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	740
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	741 /* Return a pointer to the beginning of memory storage for the gap array.
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	742 Note this is NOT the same as gap_array_atp(ga, 0, type) because that
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	743 will skip forward past the gap if the gap is at position 0. */
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	744 #define gap_array_begin(ga, type) ((type *) ((ga)->array))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	745
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	746 #ifndef NEW_GC
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	747 extern const struct sized_memory_description lispobj_gap_array_description;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	748 extern const struct sized_memory_description gap_array_marker_description;
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	749 #endif
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	750
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	751 Bytecount gap_array_byte_size (Gap_Array *ga);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	752 Gap_Array gap_array_insert_els (Gap_Array ga, Elemcount pos, void *elptr,
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	753 Elemcount numels);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	754 void gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	755 #define gap_array_delete_all_els(ga) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	756 gap_array_delete_els (ga, 0, gap_array_length (ga))
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	757 Gap_Array_Marker gap_array_make_marker (Gap_Array ga, Elemcount pos);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	758 void gap_array_delete_marker (Gap_Array ga, Gap_Array_Marker m);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	759 void gap_array_delete_all_markers (Gap_Array *ga);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	760 void gap_array_move_marker (Gap_Array ga, Gap_Array_Marker m, Elemcount pos);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	761 #define gap_array_marker_pos(ga, m) \
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	762 GAP_ARRAY_MEMORY_TO_ARRAY_POS (ga, (m)->pos)
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	763 Gap_Array *make_gap_array (Elemcount elsize, int USED_IF_NEW_GC (do_lisp));
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	764 Gap_Array gap_array_clone (Gap_Array ga);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	765 void free_gap_array (Gap_Array *ga);
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	766
cf900a2f1fa3 extract gap array from extents.c, use in range tables Ben Wing <ben@xemacs.org> parents: diff changeset	767 #endif /* INCLUDED_lrecordt_h_ */

Mercurial > hg > xemacs-beta

annotate src/array.h @ 5168:cf900a2f1fa3