1 /* $Id$ */
2 /*
3 * Copyright (c) 1990-1996 Sam Leffler
4 * Copyright (c) 1991-1996 Silicon Graphics, Inc.
5 * HylaFAX is a trademark of Silicon Graphics
6 *
7 * Permission to use, copy, modify, distribute, and sell this software and
8 * its documentation for any purpose is hereby granted without fee, provided
9 * that (i) the above copyright notices and this permission notice appear in
10 * all copies of the software and related documentation, and (ii) the names of
11 * Sam Leffler and Silicon Graphics may not be used in any advertising or
12 * publicity relating to the software without the specific, prior written
13 * permission of Sam Leffler and Silicon Graphics.
14 *
15 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
17 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
18 *
19 * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
20 * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
21 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
22 * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
23 * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
24 * OF THIS SOFTWARE.
25 */
26 #include "Array.h"
27 #include <stdlib.h>
28
29 #define that (*this)
30
fxArray(u_short esize,u_int initlength)31 fxArray::fxArray(u_short esize, u_int initlength)
32 {
33 num = maxi = initlength * esize;
34 elementsize = esize;
35 if (maxi != 0)
36 data = malloc((u_int) maxi);
37 else
38 data = 0;
39 // Don't create the elements because the subclass will do that, because
40 // we can't call a virtual from within this constructor.
41 }
42
fxArray(const fxArray & other)43 fxArray::fxArray(const fxArray & other)
44 {
45 num = other.num;
46 maxi = other.num;
47 elementsize = other.elementsize;
48 data = 0;
49 getmem();
50 copyElements(other.data,data,num);
51 }
52
fxArray(u_int esize,u_int n,void * d)53 fxArray::fxArray(u_int esize, u_int n, void * d)
54 {
55 elementsize=esize;
56 num=maxi=n;
57 data=d;
58 }
59
~fxArray()60 fxArray::~fxArray()
61 {
62 if (data)
63 free((void*) data);
64 }
65
66 void
destroy()67 fxArray::destroy()
68 {
69 if (num != 0) destroyElements(data,num);
70 }
71
length() const72 u_int fxArray::length() const { return num/elementsize; }
73
74 void
append(void const * item)75 fxArray::append(void const * item) {
76 assert(num<=maxi);
77 if (num == maxi) expand();
78 copyElements(item, data + num, elementsize);
79 num += elementsize;
80 }
81
82 void
append(const fxArray & a)83 fxArray::append(const fxArray & a) {
84 assert(elementsize == a.elementsize);
85 u_int length = a.num;
86 if (length > 0) {
87 if (num + length > maxi) {
88 maxi = num + length;
89 getmem();
90 }
91 copyElements(a.data, data+num, length);
92 num += length;
93 }
94 }
95
96 void
remove(u_int start,u_int length)97 fxArray::remove(u_int start, u_int length) {
98 if (length>0) {
99 start *= elementsize;
100 length *= elementsize;
101 assert(start+length <= num);
102 destroyElements(data+start,length);
103 if (start+length < num) {
104 memmove((void*)(data + start),
105 (void*)(data + start+length), num - (start+length));
106 // we don't use copyElements because they are just being moved.
107 }
108 num -= length;
109 // we don't destroy the end elements because they still exist; they've
110 // just been moved.
111 }
112 }
113
114 void
resize(u_int length)115 fxArray::resize(u_int length) {
116 length *= elementsize;
117 maxi = length;
118 if (length>num) {
119 getmem();
120 createElements(data + num, length - num);
121 } else if (num>length) {
122 destroyElements(data + length, num - length);
123 getmem();
124 }
125 num = length;
126 }
127
128 void
setMaxLength(u_int length)129 fxArray::setMaxLength(u_int length)
130 {
131 length *= elementsize;
132 length = fxmax(length,num);
133 if (maxi != length) {
134 maxi = length;
135 getmem();
136 }
137 }
138
139 void
createElements(void *,u_int)140 fxArray::createElements(void*, u_int)
141 {
142 }
143
144 void
destroyElements(void *,u_int)145 fxArray::destroyElements(void*, u_int)
146 {
147 }
148
149 void
copyElements(const void * source,void * dest,u_int length) const150 fxArray::copyElements(const void * source, void * dest, u_int length) const
151 {
152 memmove(dest,source,length);
153 }
154
155 int
compareElements(const void * e1,const void * e2) const156 fxArray::compareElements(const void * e1, const void * e2) const
157 {
158 return memcmp(e1,e2,elementsize);
159 }
160
161 void
expand()162 fxArray::expand()
163 { // by default, grab 4 more element spaces
164 maxi += elementsize*4;
165 getmem();
166 }
167
168 // this function keeps `data' up to date when maxi has just been changed
169 void
getmem()170 fxArray::getmem()
171 {
172 if (maxi == 0) {
173 if (data)
174 free((void*) data);
175 data = 0;
176 } else {
177 if (data)
178 data = realloc(data,maxi);
179 else
180 data = malloc(maxi);
181 }
182 }
183
184 void
insert(fxArray const & a,u_int posn)185 fxArray::insert(fxArray const & a, u_int posn)
186 {
187 u_int length = a.num;
188 if (a.length()>0) {
189 assert(elementsize == a.elementsize);
190 posn *= elementsize;
191 assert(posn <= num);
192 if (maxi < num + length) {
193 maxi = num + length;
194 getmem();
195 }
196 if (posn < num) {
197 memmove((void*)(data+posn+length), (void*)(data+posn), num-posn);
198 // we don't need to do a copyElements because we're not
199 // making new copies of objects, we're just moving
200 // existing ones.
201 }
202 copyElements(a.data, data+posn, length);
203 num += length;
204 }
205 }
206
207 void
insert(void const * item,u_int posn)208 fxArray::insert(void const * item, u_int posn)
209 {
210 posn *= elementsize;
211 assert(posn <= num);
212 if (maxi <= num) {
213 maxi = num+elementsize;
214 getmem();
215 }
216 if (posn<num) {
217 memmove((void*)(data+posn+(u_int)elementsize),
218 (void*)(data+posn), num-posn);
219 }
220 copyElements(item, data+posn, elementsize);
221 num += elementsize;
222 }
223
224 #define TEMPSIZE 1024
225
226 void
swap(u_int p1,u_int p2)227 fxArray::swap(u_int p1, u_int p2)
228 {
229 char buffer[TEMPSIZE];
230 void *tmp;
231 p1 *= elementsize;
232 p2 *= elementsize;
233 if (elementsize>TEMPSIZE) tmp=malloc(elementsize);
234 else tmp = buffer;
235 memcpy(tmp,(void*)(data+p1),elementsize);
236 memcpy((void*)(data+p1),(void*)(data+p2),elementsize);
237 memcpy((void*)(data+p2),tmp,elementsize);
238 }
239
240 u_int
find(void const * item,u_int start) const241 fxArray::find(void const * item, u_int start) const
242 {
243 assert(start*elementsize <= num);
244 fxAddress p = data + (u_int)(start*elementsize);
245 while (p < data + num) {
246 if (0 == compareElements(item,p)) return start;
247 p = p+elementsize;
248 start++;
249 }
250 return fx_invalidArrayIndex;
251 }
252
253 void
qsortInternal(u_int l,u_int r,void * tmp)254 fxArray::qsortInternal(u_int l, u_int r, void * tmp)
255 {
256 register u_int i=l;
257 register u_int k=r+1;
258 u_int e = elementsize;
259
260 assert(k<=length());
261
262 void * item = that[l];
263
264 for (;;) {
265 for (;;) {
266 if(i>=r)break;
267 ++i;
268 if (compareElements(that[i],item) >= 0) break;
269 }
270 for (;;) {
271 if (k<=l) break;
272 --k;
273 if (compareElements(that[k],item) <= 0) break;
274 }
275 if (i>=k) break;
276
277 memcpy(tmp,that[i],e);
278 memcpy(that[i],that[k],e);
279 memcpy(that[k],tmp,e);
280 }
281 memcpy(tmp,that[l],e);
282 memcpy(that[l],that[k],e);
283 memcpy(that[k],tmp,e);
284 if (k && l<k-1) qsortInternal(l,k-1,tmp);
285 if (k+1 < r) qsortInternal(k+1,r,tmp);
286 }
287
288 #define SMALLBUFFERSIZE 32
289
290 void
qsort(u_int posn,u_int len)291 fxArray::qsort(u_int posn, u_int len)
292 {
293 if (len == 0) return;
294 char smallbuffer[SMALLBUFFERSIZE];
295 assert(posn+len <= num);
296 void *tmp = (elementsize > SMALLBUFFERSIZE)
297 ? malloc(elementsize)
298 : smallbuffer;
299 qsortInternal(posn,posn+len-1,tmp);
300 if (tmp != smallbuffer) free(tmp);
301 }
302
303 void
qsort()304 fxArray::qsort()
305 {
306 qsort(0,length());
307 }
308
309 void *
raw_extract(u_int start,u_int len) const310 fxArray::raw_extract(u_int start, u_int len) const
311 {
312 if (len == 0) return 0;
313 start *= elementsize;
314 len *= elementsize;
315 assert(start+len<=num);
316 void * ret = malloc(len);
317 copyElements(data+start, ret, len);
318 return ret;
319 }
320
321 void *
raw_cut(u_int start,u_int len)322 fxArray::raw_cut(u_int start, u_int len)
323 {
324 if (len == 0) return 0;
325 start *= elementsize;
326 len *= elementsize;
327 assert(start+len <= num);
328 void * ret = malloc(len);
329 // we don't copy because we aren't making copies, we're just
330 // moving existing elements from one array to another.
331 memcpy(ret, (void*)(data+start), len);
332 if (start+len < num) {
333 // we don't use copyElements because they are just being moved.
334 memmove((void*)(data + start),
335 (void*)(data + start+len), num - (start+len));
336 }
337 num -= len;
338 return ret;
339 }
340
341 void *
raw_copy() const342 fxArray::raw_copy() const
343 {
344 if (num == 0) return 0;
345 void * ret = malloc(num);
346 copyElements(data,ret,num);
347 return ret;
348 }
349
350 void *
raw_head(u_int len) const351 fxArray::raw_head(u_int len) const
352 {
353 if (len == 0) return 0;
354 assert(len <= num);
355 return raw_extract(0,len);
356 }
357
358 void *
raw_tail(u_int len) const359 fxArray::raw_tail(u_int len) const
360 {
361 if (len == 0) return 0;
362 len *= elementsize;
363 assert(len <= num);
364 void * ret = malloc(len);
365 copyElements(data+(num-len), ret, len);
366 return ret;
367 }
368