annotate src/dynarr.c @ 4844:91b3d00e717f

Various cleanups for Dynarr code, from Unicode-internal ws dynarr.c: Add comment explaining Dynarr_largest() use. dynarr.c: In Dynarr_insert_many(), don't call Dynarr_resize() unless we actually need to resize, and note that an assert() that we are inserting at or below the current end could be wrong if code wants to access stuff between `len' and `largest'. dynarr.c: Don't just Dynarr_resize() to the right size; instead use Dynarr_reset() then Dynarr_add_many(), so that the 'len' and 'largest' and such get set properly. dynarr.c, faces.c, gutter.c, lisp.h, lread.c, lrecord.h, redisplay-output.c, redisplay.c: Rename Dynarr member 'cur' to 'len' since it's the length of the dynarr, not really a pointer to a "current insertion point". Use type_checking_assert() instead of just assert() in some places. Add additional assertions (Dynarr_verify*()) to check that we're being given positions within range. Use them in Dynarr_at, Dynarr_atp, etc. New Dynarr_atp_allow_end() for retrieving a pointer to a position that might be the element past the last one. New Dynarr_past_lastp() to retrieve a pointer to the position past the last one, using Dynarr_atp_allow_end(). Change code appropriately to use it. Rename Dynarr_end() to Dynarr_lastp() (pointer to the last element) for clarity, and change code appropriately to use it. Change code appropriately to use Dynarr_begin(). Rewrite Dynarr_add_many(). New version can accept a NULL pointer to mean "reserve space but don't put anything in it". Used by stack_like_malloc().
author Ben Wing <ben@xemacs.org>
date Wed, 13 Jan 2010 04:07:42 -0600
parents 229bd619740a
children 19a72041c5ed
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
1 /* Support for dynamic arrays.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
2 Copyright (C) 1993 Sun Microsystems, Inc.
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
3 Copyright (C) 2002, 2003, 2004, 2005 Ben Wing.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
4
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
5 This file is part of XEmacs.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
6
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
7 XEmacs is free software; you can redistribute it and/or modify it
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
8 under the terms of the GNU General Public License as published by the
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
9 Free Software Foundation; either version 2, or (at your option) any
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
10 later version.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
11
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
15 for more details.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
16
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
18 along with XEmacs; see the file COPYING. If not, write to
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
20 Boston, MA 02111-1307, USA. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
21
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
22 /* Synched up with: Not in FSF. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
23
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
24 /* Written by Ben Wing, December 1993. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
25
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
26 /*
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
27
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
28 A "dynamic array" is a contiguous array of fixed-size elements where there
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
29 is no upper limit (except available memory) on the number of elements in the
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
30 array. Because the elements are maintained contiguously, space is used
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
31 efficiently (no per-element pointers necessary) and random access to a
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
32 particular element is in constant time. At any one point, the block of memory
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
33 that holds the array has an upper limit; if this limit is exceeded, the
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
34 memory is realloc()ed into a new array that is twice as big. Assuming that
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
35 the time to grow the array is on the order of the new size of the array
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
36 block, this scheme has a provably constant amortized time (i.e. average
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
37 time over all additions).
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
38
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
39 When you add elements or retrieve elements, pointers are used. Note that
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
40 the element itself (of whatever size it is), and not the pointer to it,
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
41 is stored in the array; thus you do not have to allocate any heap memory
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
42 on your own. Also, returned pointers are only guaranteed to be valid
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
43 until the next operation that changes the length of the array.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
44
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
45 This is a container object. Declare a dynamic array of a specific type
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
46 as follows:
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
47
2367
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
48 typedef struct
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
49 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
50 Dynarr_declare (mytype);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
51 } mytype_dynarr;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
52
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
53 Use the following functions/macros:
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
54
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
55 void *Dynarr_new(type)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
56 [MACRO] Create a new dynamic-array object, with each element of the
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
57 specified type. The return value is cast to (type##_dynarr).
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
58 This requires following the convention that types are declared in
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
59 such a way that this type concatenation works. In particular, TYPE
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
60 must be a symbol, not an arbitrary C type.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
61
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
62 Dynarr_add(d, el)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
63 [MACRO] Add an element to the end of a dynamic array. EL is a pointer
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
64 to the element; the element itself is stored in the array, however.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
65 No function call is performed unless the array needs to be resized.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
66
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
67 Dynarr_add_many(d, base, len)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
68 [MACRO] Add LEN elements to the end of the dynamic array. The elements
771
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
69 should be contiguous in memory, starting at BASE. If BASE if NULL,
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
70 just make space for the elements; don't actually add them.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
71
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
72 Dynarr_insert_many_at_start(d, base, len)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
73 [MACRO] Append LEN elements to the beginning of the dynamic array.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
74 The elements should be contiguous in memory, starting at BASE.
771
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
75 If BASE if NULL, just make space for the elements; don't actually
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
76 add them.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
77
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
78 Dynarr_insert_many(d, base, len, start)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
79 Insert LEN elements to the dynamic array starting at position
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
80 START. The elements should be contiguous in memory, starting at BASE.
771
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
81 If BASE if NULL, just make space for the elements; don't actually
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
82 add them.
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
83
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
84 Dynarr_delete(d, i)
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
85 [MACRO] Delete an element from the dynamic array at position I.
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
86
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
87 Dynarr_delete_many(d, start, len)
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
88 Delete LEN elements from the dynamic array starting at position
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
89 START.
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
90
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
91 Dynarr_delete_by_pointer(d, p)
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
92 [MACRO] Delete an element from the dynamic array at pointer P,
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
93 which must point within the block of memory that stores the data.
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
94 P should be obtained using Dynarr_atp().
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
95
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
96 int Dynarr_length(d)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
97 [MACRO] Return the number of elements currently in a dynamic array.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
98
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
99 int Dynarr_largest(d)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
100 [MACRO] Return the maximum value that Dynarr_length(d) would
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
101 ever have returned. This is used esp. in the redisplay code,
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
102 which reuses dynarrs for performance reasons.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
103
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
104 type Dynarr_at(d, i)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
105 [MACRO] Return the element at the specified index (no bounds checking
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
106 done on the index). The element itself is returned, not a pointer
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
107 to it.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
108
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
109 type *Dynarr_atp(d, i)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
110 [MACRO] Return a pointer to the element at the specified index (no
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
111 bounds checking done on the index). The pointer may not be valid
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
112 after an element is added to or removed from the array.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
113
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
114 Dynarr_reset(d)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
115 [MACRO] Reset the length of a dynamic array to 0.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
116
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
117 Dynarr_free(d)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
118 Destroy a dynamic array and the memory allocated to it.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
119
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
120 Use the following global variable:
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
121
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
122 Dynarr_min_size
440
8de8e3f6228a Import from CVS: tag r21-2-28
cvs
parents: 428
diff changeset
123 Minimum allowable size for a dynamic array when it is resized.
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
124
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
125 */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
126
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
127 #include <config.h>
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
128 #include "lisp.h"
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
129
440
8de8e3f6228a Import from CVS: tag r21-2-28
cvs
parents: 428
diff changeset
130 static int Dynarr_min_size = 8;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
131
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
132 static void
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
133 Dynarr_realloc (Dynarr *dy, int new_size)
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
134 {
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
135 if (DUMPEDP (dy->base))
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
136 {
3293
168191f9515f [xemacs-hg @ 2006-03-20 21:20:19 by crestani]
crestani
parents: 3210
diff changeset
137 void *new_base = malloc (new_size * dy->elsize);
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
138 memcpy (new_base, dy->base,
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
139 (dy->max < new_size ? dy->max : new_size) * dy->elsize);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
140 dy->base = new_base;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
141 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
142 else
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
143 dy->base = xrealloc (dy->base, new_size * dy->elsize);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
144 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
145
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
146 void *
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
147 Dynarr_newf (int elsize)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
148 {
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
149 Dynarr *d = xnew_and_zero (Dynarr);
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
150 d->elsize = elsize;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
151
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
152 return d;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
153 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
154
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
155 #ifdef NEW_GC
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
156 DEFINE_LRECORD_IMPLEMENTATION ("dynarr", dynarr,
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
157 1, /*dumpable-flag*/
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
158 0, 0, 0, 0, 0,
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
159 0,
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
160 Dynarr);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
161
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
162 static void
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
163 Dynarr_lisp_realloc (Dynarr *dy, int new_size)
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
164 {
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
165 void *new_base = alloc_lrecord_array (dy->elsize, new_size, dy->lisp_imp);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
166 if (dy->base)
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
167 memcpy (new_base, dy->base,
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
168 (dy->max < new_size ? dy->max : new_size) * dy->elsize);
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
169 dy->base = new_base;
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
170 }
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
171
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
172 void *
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
173 Dynarr_lisp_newf (int elsize,
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
174 const struct lrecord_implementation *dynarr_imp,
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
175 const struct lrecord_implementation *imp)
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
176 {
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
177 Dynarr *d = (Dynarr *) alloc_lrecord (sizeof (Dynarr), dynarr_imp);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
178 d->elsize = elsize;
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
179 d->lisp_imp = imp;
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
180
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
181 return d;
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
182 }
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
183 #endif /* not NEW_GC */
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
184
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
185 void
2367
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
186 Dynarr_resize (void *d, Elemcount size)
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
187 {
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
188 int newsize;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
189 double multiplier;
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
190 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
191
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
192 if (dy->max <= 8)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
193 multiplier = 2;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
194 else
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
195 multiplier = 1.5;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
196
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
197 for (newsize = dy->max; newsize < size;)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
198 newsize = max (Dynarr_min_size, (int) (multiplier * newsize));
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
199
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
200 /* Don't do anything if the array is already big enough. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
201 if (newsize > dy->max)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
202 {
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
203 #ifdef NEW_GC
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
204 if (dy->lisp_imp)
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
205 Dynarr_lisp_realloc (dy, newsize);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
206 else
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
207 Dynarr_realloc (dy, newsize);
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
208 #else /* not NEW_GC */
3210
72b7d685c194 [xemacs-hg @ 2006-01-20 17:59:48 by crestani]
crestani
parents: 3092
diff changeset
209 Dynarr_realloc (dy, newsize);
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
210 #endif /* not NEW_GC */
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
211 dy->max = newsize;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
212 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
213 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
214
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
215 /* Add a number of contiguous elements to the array starting at START. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
216 void
442
abe6d1db359e Import from CVS: tag r21-2-36
cvs
parents: 440
diff changeset
217 Dynarr_insert_many (void *d, const void *el, int len, int start)
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
218 {
793
e38acbeb1cae [xemacs-hg @ 2002-03-29 04:46:17 by ben]
ben
parents: 771
diff changeset
219 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
e38acbeb1cae [xemacs-hg @ 2002-03-29 04:46:17 by ben]
ben
parents: 771
diff changeset
220
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
221 if (dy->len + len > dy->max)
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
222 Dynarr_resize (dy, dy->len + len);
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
223 #if 0
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
224 /* WTF? We should be catching these problems. */
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
225 /* Silently adjust start to be valid. */
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
226 if (start > dy->len)
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
227 start = dy->len;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
228 else if (start < 0)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
229 start = 0;
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
230 #else
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
231 /* #### This could conceivably be wrong, if code wants to access stuff
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
232 between len and largest. */
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
233 type_checking_assert (start >= 0 && start <= dy->len);
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
234 #endif
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
235
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
236 if (start != dy->len)
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
237 {
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
238 memmove ((char *) dy->base + (start + len)*dy->elsize,
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
239 (char *) dy->base + start*dy->elsize,
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
240 (dy->len - start)*dy->elsize);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
241 }
771
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
242 if (el)
943eaba38521 [xemacs-hg @ 2002-03-13 08:51:24 by ben]
ben
parents: 665
diff changeset
243 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize);
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
244 dy->len += len;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
245
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
246 if (dy->len > dy->largest)
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
247 dy->largest = dy->len;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
248 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
249
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
250 void
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
251 Dynarr_delete_many (void *d, int start, int len)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
252 {
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
253 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
254
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
255 type_checking_assert (start >= 0 && len >= 0 && start + len <= dy->len);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
256 memmove ((char *) dy->base + start*dy->elsize,
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
257 (char *) dy->base + (start + len)*dy->elsize,
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
258 (dy->len - start - len)*dy->elsize);
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
259 dy->len -= len;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
260 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
261
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
262 void
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
263 Dynarr_free (void *d)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
264 {
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
265 Dynarr *dy = (Dynarr *) d;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
266
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
267 #ifdef NEW_GC
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
268 if (dy->base && !DUMPEDP (dy->base))
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
269 {
4117
229bd619740a [xemacs-hg @ 2007-08-15 11:06:02 by crestani]
crestani
parents: 3293
diff changeset
270 if (!dy->lisp_imp)
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
271 xfree (dy->base, void *);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
272 }
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
273 if(!DUMPEDP (dy))
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
274 {
4117
229bd619740a [xemacs-hg @ 2007-08-15 11:06:02 by crestani]
crestani
parents: 3293
diff changeset
275 if (!dy->lisp_imp)
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
276 xfree (dy, Dynarr *);
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
277 }
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
278 #else /* not NEW_GC */
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
279 if (dy->base && !DUMPEDP (dy->base))
1726
a8d8f419b459 [xemacs-hg @ 2003-09-30 15:26:34 by james]
james
parents: 1318
diff changeset
280 xfree (dy->base, void *);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
281 if(!DUMPEDP (dy))
1726
a8d8f419b459 [xemacs-hg @ 2003-09-30 15:26:34 by james]
james
parents: 1318
diff changeset
282 xfree (dy, Dynarr *);
3092
141c2920ea48 [xemacs-hg @ 2005-11-25 01:41:31 by crestani]
crestani
parents: 2500
diff changeset
283 #endif /* not NEW_GC */
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
284 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
285
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
286 #ifdef MEMORY_USAGE_STATS
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
287
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
288 /* Return memory usage for Dynarr D. The returned value is the total
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
289 amount of bytes actually being used for the Dynarr, including all
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
290 overhead. The extra amount of space in the Dynarr that is
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
291 allocated beyond what was requested is returned in DYNARR_OVERHEAD
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
292 in STATS. The extra amount of space that malloc() allocates beyond
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
293 what was requested of it is returned in MALLOC_OVERHEAD in STATS.
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
294 See the comment above the definition of this structure. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
295
665
fdefd0186b75 [xemacs-hg @ 2001-09-20 06:28:42 by ben]
ben
parents: 647
diff changeset
296 Bytecount
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
297 Dynarr_memory_usage (void *d, struct overhead_stats *stats)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
298 {
665
fdefd0186b75 [xemacs-hg @ 2001-09-20 06:28:42 by ben]
ben
parents: 647
diff changeset
299 Bytecount total = 0;
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
300 Dynarr *dy = (Dynarr *) d;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
301
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
302 /* We have to be a bit tricky here because not all of the
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
303 memory that malloc() will claim as "requested" was actually
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
304 requested. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
305
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
306 if (dy->base)
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
307 {
665
fdefd0186b75 [xemacs-hg @ 2001-09-20 06:28:42 by ben]
ben
parents: 647
diff changeset
308 Bytecount malloc_used = malloced_storage_size (dy->base,
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
309 dy->elsize * dy->max, 0);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
310 /* #### This may or may not be correct. Some Dynarrs would
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
311 prefer that we use dy->len instead of dy->largest here. */
1318
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
312 Bytecount was_requested = dy->elsize * dy->largest;
b531bf8658e9 [xemacs-hg @ 2003-02-21 06:56:46 by ben]
ben
parents: 793
diff changeset
313 Bytecount dynarr_overhead = dy->elsize * (dy->max - dy->largest);
428
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
314
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
315 total += malloc_used;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
316 stats->was_requested += was_requested;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
317 stats->dynarr_overhead += dynarr_overhead;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
318 /* And the remainder must be malloc overhead. */
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
319 stats->malloc_overhead +=
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
320 malloc_used - was_requested - dynarr_overhead;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
321 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
322
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
323 total += malloced_storage_size (d, sizeof (*dy), stats);
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
324
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
325 return total;
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
326 }
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
327
3ecd8885ac67 Import from CVS: tag r21-2-22
cvs
parents:
diff changeset
328 #endif /* MEMORY_USAGE_STATS */
2367
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
329
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
330 /* Version of malloc() that will be extremely efficient when allocation
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
331 nearly always occurs in LIFO (stack) order.
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
332
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
333 #### Perhaps shouldn't be in this file, but where else? */
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
334
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
335 typedef struct
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
336 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
337 Dynarr_declare (char_dynarr *);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
338 } char_dynarr_dynarr;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
339
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
340 char_dynarr_dynarr *stack_like_free_list;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
341 char_dynarr_dynarr *stack_like_in_use_list;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
342
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
343 void *
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
344 stack_like_malloc (Bytecount size)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
345 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
346 char_dynarr *this_one;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
347 if (!stack_like_free_list)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
348 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
349 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr,
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
350 char_dynarr *);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
351 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr,
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
352 char_dynarr *);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
353 }
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
354
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
355 if (Dynarr_length (stack_like_free_list) > 0)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
356 this_one = Dynarr_pop (stack_like_free_list);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
357 else
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
358 this_one = Dynarr_new (char);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
359 Dynarr_add (stack_like_in_use_list, this_one);
4844
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
360 Dynarr_reset (this_one);
91b3d00e717f Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents: 4117
diff changeset
361 Dynarr_add_many (this_one, 0, size);
2367
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
362 return Dynarr_atp (this_one, 0);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
363 }
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
364
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
365 void
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
366 stack_like_free (void *val)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
367 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
368 int len = Dynarr_length (stack_like_in_use_list);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
369 assert (len > 0);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
370 /* The vast majority of times, we will be called in a last-in first-out
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
371 order, and the item at the end of the list will be the one we're
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
372 looking for, so just check for this first and avoid any function
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
373 calls. */
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
374 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, len - 1), 0) == val)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
375 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
376 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
377 Dynarr_add (stack_like_free_list, this_one);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
378 }
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
379 else
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
380 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
381 /* Find the item and delete it. */
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
382 int i;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
383 assert (len >= 2);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
384 for (i = len - 2; i >= 0; i--)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
385 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, i), 0) ==
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
386 val)
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
387 {
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
388 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
389 Dynarr_add (stack_like_free_list, this_one);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
390 Dynarr_delete (stack_like_in_use_list, i);
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
391 return;
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
392 }
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
393
2500
3d8143fc88e1 [xemacs-hg @ 2005-01-24 23:33:30 by ben]
ben
parents: 2367
diff changeset
394 ABORT ();
2367
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
395 }
ecf1ebac70d8 [xemacs-hg @ 2004-11-04 23:05:23 by ben]
ben
parents: 1726
diff changeset
396 }