|
0
|
1 /* Simple 'n' stupid dynamic-array module.
|
|
|
2 Copyright (C) 1993 Sun Microsystems, Inc.
|
|
|
3
|
|
|
4 This file is part of XEmacs.
|
|
|
5
|
|
|
6 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 2, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with XEmacs; see the file COPYING. If not, write to
|
|
|
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
19 Boston, MA 02111-1307, USA. */
|
|
|
20
|
|
|
21 /* Synched up with: Not in FSF. */
|
|
|
22
|
|
|
23 /* Written by Ben Wing, December 1993. */
|
|
|
24
|
|
|
25 /*
|
|
|
26
|
|
|
27 A "dynamic array" is a contiguous array of fixed-size elements where there
|
|
|
28 is no upper limit (except available memory) on the number of elements in the
|
|
|
29 array. Because the elements are maintained contiguously, space is used
|
|
|
30 efficiently (no per-element pointers necessary) and random access to a
|
|
|
31 particular element is in constant time. At any one point, the block of memory
|
|
|
32 that holds the array has an upper limit; if this limit is exceeded, the
|
|
|
33 memory is realloc()ed into a new array that is twice as big. Assuming that
|
|
|
34 the time to grow the array is on the order of the new size of the array
|
|
|
35 block, this scheme has a provably constant amortized time (i.e. average
|
|
|
36 time over all additions).
|
|
|
37
|
|
|
38 When you add elements or retrieve elements, pointers are used. Note that
|
|
|
39 the element itself (of whatever size it is), and not the pointer to it,
|
|
|
40 is stored in the array; thus you do not have to allocate any heap memory
|
|
|
41 on your own. Also, returned pointers are only guaranteed to be valid
|
|
|
42 until the next operation that changes the length of the array.
|
|
|
43
|
|
|
44 This is a container object. Declare a dynamic array of a specific type
|
|
|
45 as follows:
|
|
|
46
|
|
380
|
47 typedef struct
|
|
0
|
48 {
|
|
|
49 Dynarr_declare (mytype);
|
|
185
|
50 } mytype_dynarr;
|
|
0
|
51
|
|
|
52 Use the following functions/macros:
|
|
|
53
|
|
|
54 void *Dynarr_new(type)
|
|
|
55 [MACRO] Create a new dynamic-array object, with each element of the
|
|
185
|
56 specified type. The return value is cast to (type##_dynarr).
|
|
|
57 This requires following the convention that types are declared in
|
|
|
58 such a way that this type concatenation works. In particular, TYPE
|
|
|
59 must be a symbol, not an arbitrary C type.
|
|
0
|
60
|
|
|
61 Dynarr_add(d, el)
|
|
|
62 [MACRO] Add an element to the end of a dynamic array. EL is a pointer
|
|
|
63 to the element; the element itself is stored in the array, however.
|
|
|
64 No function call is performed unless the array needs to be resized.
|
|
|
65
|
|
|
66 Dynarr_add_many(d, base, len)
|
|
|
67 [MACRO] Add LEN elements to the end of the dynamic array. The elements
|
|
|
68 should be contiguous in memory, starting at BASE.
|
|
|
69
|
|
|
70 Dynarr_insert_many_at_start(d, base, len)
|
|
|
71 [MACRO] Append LEN elements to the beginning of the dynamic array.
|
|
|
72 The elements should be contiguous in memory, starting at BASE.
|
|
|
73
|
|
|
74 Dynarr_insert_many(d, base, len, start)
|
|
380
|
75 Insert LEN elements to the dynamic array starting at position
|
|
0
|
76 START. The elements should be contiguous in memory, starting at BASE.
|
|
|
77
|
|
|
78 int Dynarr_length(d)
|
|
|
79 [MACRO] Return the number of elements currently in a dynamic array.
|
|
|
80
|
|
185
|
81 int Dynarr_largest(d)
|
|
|
82 [MACRO] Return the maximum value that Dynarr_length(d) would
|
|
|
83 ever have returned.
|
|
|
84
|
|
0
|
85 type Dynarr_at(d, i)
|
|
|
86 [MACRO] Return the element at the specified index (no bounds checking
|
|
|
87 done on the index). The element itself is returned, not a pointer
|
|
|
88 to it.
|
|
|
89
|
|
|
90 type *Dynarr_atp(d, i)
|
|
|
91 [MACRO] Return a pointer to the element at the specified index (no
|
|
|
92 bounds checking done on the index). The pointer may not be valid
|
|
|
93 after an element is added to or removed from the array.
|
|
|
94
|
|
|
95 Dynarr_reset(d)
|
|
|
96 [MACRO] Reset the length of a dynamic array to 0.
|
|
|
97
|
|
|
98 Dynarr_free(d)
|
|
|
99 Destroy a dynamic array and the memory allocated to it.
|
|
|
100
|
|
|
101 Use the following global variable:
|
|
|
102
|
|
|
103 Dynarr_min_size
|
|
412
|
104 Minimum allowable size for a dynamic array when it is resized. The
|
|
|
105 default is 32 and does not normally need to be changed.
|
|
0
|
106
|
|
|
107 */
|
|
|
108
|
|
|
109 #include <config.h>
|
|
|
110 #include "lisp.h"
|
|
|
111
|
|
412
|
112 int Dynarr_min_size = 1;
|
|
0
|
113
|
|
424
|
114 static void
|
|
|
115 Dynarr_realloc (Dynarr *dy, int new_size)
|
|
|
116 {
|
|
|
117 if (DUMPEDP (dy->base))
|
|
|
118 {
|
|
|
119 void *new_base = malloc (new_size);
|
|
|
120 memcpy (new_base, dy->base, dy->max > new_size ? new_size : dy->max);
|
|
|
121 dy->base = new_base;
|
|
|
122 }
|
|
|
123 else
|
|
|
124 dy->base = xrealloc (dy->base, new_size);
|
|
|
125 }
|
|
|
126
|
|
0
|
127 void *
|
|
|
128 Dynarr_newf (int elsize)
|
|
|
129 {
|
|
185
|
130 Dynarr *d = xnew_and_zero (Dynarr);
|
|
0
|
131 d->elsize = elsize;
|
|
|
132
|
|
|
133 return d;
|
|
|
134 }
|
|
|
135
|
|
|
136 void
|
|
|
137 Dynarr_resize (void *d, int size)
|
|
|
138 {
|
|
|
139 int newsize;
|
|
|
140 double multiplier;
|
|
|
141 Dynarr *dy = (Dynarr *) d;
|
|
|
142
|
|
|
143 if (dy->max <= 8)
|
|
|
144 multiplier = 2;
|
|
|
145 else
|
|
|
146 multiplier = 1.5;
|
|
|
147
|
|
|
148 for (newsize = dy->max; newsize < size;)
|
|
272
|
149 newsize = max (Dynarr_min_size, (int) (multiplier * newsize));
|
|
0
|
150
|
|
|
151 /* Don't do anything if the array is already big enough. */
|
|
|
152 if (newsize > dy->max)
|
|
|
153 {
|
|
424
|
154 Dynarr_realloc (dy, newsize*dy->elsize);
|
|
0
|
155 dy->max = newsize;
|
|
|
156 }
|
|
|
157 }
|
|
|
158
|
|
|
159 /* Add a number of contiguous elements to the array starting at START. */
|
|
|
160 void
|
|
412
|
161 Dynarr_insert_many (void *d, CONST void *el, int len, int start)
|
|
0
|
162 {
|
|
|
163 Dynarr *dy = (Dynarr *) d;
|
|
|
164
|
|
|
165 Dynarr_resize (dy, dy->cur+len);
|
|
|
166 /* Silently adjust start to be valid. */
|
|
|
167 if (start > dy->cur)
|
|
|
168 start = dy->cur;
|
|
|
169 else if (start < 0)
|
|
|
170 start = 0;
|
|
|
171
|
|
|
172 if (start != dy->cur)
|
|
|
173 {
|
|
|
174 memmove ((char *) dy->base + (start + len)*dy->elsize,
|
|
|
175 (char *) dy->base + start*dy->elsize,
|
|
|
176 (dy->cur - start)*dy->elsize);
|
|
|
177 }
|
|
|
178 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize);
|
|
|
179 dy->cur += len;
|
|
|
180
|
|
|
181 if (dy->cur > dy->largest)
|
|
|
182 dy->largest = dy->cur;
|
|
|
183 }
|
|
|
184
|
|
|
185 void
|
|
|
186 Dynarr_delete_many (void *d, int start, int len)
|
|
|
187 {
|
|
|
188 Dynarr *dy = (Dynarr *) d;
|
|
|
189
|
|
|
190 assert (start >= 0 && len >= 0 && start + len <= dy->cur);
|
|
|
191 memmove ((char *) dy->base + start*dy->elsize,
|
|
|
192 (char *) dy->base + (start + len)*dy->elsize,
|
|
|
193 (dy->cur - start - len)*dy->elsize);
|
|
|
194 dy->cur -= len;
|
|
|
195 }
|
|
|
196
|
|
|
197 void
|
|
|
198 Dynarr_free (void *d)
|
|
|
199 {
|
|
|
200 Dynarr *dy = (Dynarr *) d;
|
|
|
201
|
|
424
|
202 if (dy->base && !DUMPEDP (dy->base))
|
|
0
|
203 xfree (dy->base);
|
|
424
|
204 if(!DUMPEDP (dy))
|
|
|
205 xfree (dy);
|
|
0
|
206 }
|
|
|
207
|
|
|
208 #ifdef MEMORY_USAGE_STATS
|
|
|
209
|
|
|
210 /* Return memory usage for Dynarr D. The returned value is the total
|
|
|
211 amount of bytes actually being used for the Dynarr, including all
|
|
|
212 overhead. The extra amount of space in the Dynarr that is
|
|
|
213 allocated beyond what was requested is returned in DYNARR_OVERHEAD
|
|
|
214 in STATS. The extra amount of space that malloc() allocates beyond
|
|
|
215 what was requested of it is returned in MALLOC_OVERHEAD in STATS.
|
|
|
216 See the comment above the definition of this structure. */
|
|
|
217
|
|
272
|
218 size_t
|
|
0
|
219 Dynarr_memory_usage (void *d, struct overhead_stats *stats)
|
|
|
220 {
|
|
272
|
221 size_t total = 0;
|
|
0
|
222 Dynarr *dy = (Dynarr *) d;
|
|
|
223
|
|
|
224 /* We have to be a bit tricky here because not all of the
|
|
|
225 memory that malloc() will claim as "requested" was actually
|
|
|
226 requested. */
|
|
|
227
|
|
|
228 if (dy->base)
|
|
|
229 {
|
|
272
|
230 size_t malloc_used = malloced_storage_size (dy->base,
|
|
|
231 dy->elsize * dy->max, 0);
|
|
0
|
232 /* #### This may or may not be correct. Some Dynarrs would
|
|
|
233 prefer that we use dy->cur instead of dy->largest here. */
|
|
|
234 int was_requested = dy->elsize * dy->largest;
|
|
|
235 int dynarr_overhead = dy->elsize * (dy->max - dy->largest);
|
|
|
236
|
|
|
237 total += malloc_used;
|
|
|
238 stats->was_requested += was_requested;
|
|
|
239 stats->dynarr_overhead += dynarr_overhead;
|
|
|
240 /* And the remainder must be malloc overhead. */
|
|
|
241 stats->malloc_overhead +=
|
|
|
242 malloc_used - was_requested - dynarr_overhead;
|
|
|
243 }
|
|
|
244
|
|
|
245 total += malloced_storage_size (d, sizeof (*dy), stats);
|
|
|
246
|
|
|
247 return total;
|
|
|
248 }
|
|
|
249
|
|
185
|
250 #endif /* MEMORY_USAGE_STATS */
|
