1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
// FlexArrayTmpl.hh
#ifndef __FLEXARRAY_TMPL_HH_
#define __FLEXARRAY_TMPL_HH_
#ifdef SGI
#include <new.h>
#endif
#include "Arch.h"
// #define DOUBLEWORD 8 // sgi doubleword == -align64 at a minimum
#define DOUBLEWORD 1 // kludge for space efficiency (should allow setting of blocksize
// #define FLEXARRAYDEBUG
/*-------------
Template: FlexArray
Purpose: Simplifies dynamically allocated array management since it contains
array size information and manages array resizing. However, since speed-critical
operations like indexing (the [] operator) are inlined, it adds no speed
penalty for the most common speed-critical operations.
Method Summary:
constructor: The initial "size" is 0 (the size of the array that is accessible
using the indexing operator []. However, the internally allocated size is
a minimum of 8 elements.
[] : Indexing operator. Acts just like [] would for a generic array. Since
it is inlined, there is actually no penalty in performance compared to
using a generic array.
append : Add an element to the end of the array, resizing the array if necessary.
The arrays are allocated in blocks so it doesn't need to realloc on every append.
For arrays < 1024 elements long, it doubles the array size on each realloc. When
larger than 1024 elements, it adds 1024 elements to the array on every realloc.
setSize(): Sets the internal and externally availible array sizes to the
specified size; shrinking a larger internal array if necessary.
getSize(): Return the current externally availible array size. The internal
size may be larger.
---------------*/
template<class T>
class FlexArray {
int size,maxsize;
T *data;
// Internal reallocation procedure.
void grow(int targetSize=1);
public:
// constructor
FlexArray(int sz=0);
// copy constructor
FlexArray(FlexArray<T> &src);
FlexArray<T> &operator=(FlexArray<T> &src);
// destructor
~FlexArray();
inline int getSize(){return size;}
int setSize(int s);
int append(T value);
int append(T *values,int nvals);
#ifdef FLEXARRAYDEBUG
T &operator[](int index){
if(index>=size || index<0) { // range check
printf("FlexArray:: Bad index. Arraysize=%u Index=%u\n",
size,index);
index=0;
}
return (data[index]);
}
#else
inline T &operator[](int index){ return (data[index]); }
#endif
// purge? which forces array delete
inline void purge(){
if(data)
delete[] data;
#ifdef FLEXARRAYDEBUG
else
printf("-----FlexArray.purge(): Data was already 0\n");
printf("****Flexarray.purge() maxsize=%u size=%u data was = %lX\n",
maxsize,size,data);
#endif
data=0;
maxsize=size=0;
}
//inline operator T*() { return data; } // typecasting operator
inline T *getData() { return data; } // sometimes you need direct access to the contained array.
};
template<class T>
FlexArray<T>::FlexArray(int sz):size(sz){
/*
if(sz>DOUBLEWORD) maxsize=sz;
else maxsize=DOUBLEWORD; always allocate in doubleword chunks
data = new T[maxsize];
*/
maxsize=sz; // problem here is that virtually guarauntees reallocation
if(maxsize>0) data = new T[maxsize];
else data = 0;
#ifdef FLEXARRAYDEBUG
printf("****FlexArray constructor: Init with maxsize=%u size=%u data was = %lX\n",
maxsize,size,data);
#endif
}
template<class T>
FlexArray<T>::~FlexArray(){
if(maxsize>0 && data)
delete[] data;
size=maxsize=0;
data=0;
}
template<class T>
void FlexArray<T>::grow(int targetSize){
#ifdef FLEXARRAYDEBUG
printf("****FlexArray.grow(targ=%u): Init with maxsize=%u size=%u data was = %lX\n",
targetSize,maxsize,size,data);
#endif
do{
if(!maxsize) maxsize=1;
//if(maxsize<1024)
maxsize<<=1; // double in size
//else
// maxsize+=1024; // increase by 1k element block
}while(maxsize<targetSize);
//printf("FlexArray::grow(%u)->%u\n",targetSize,maxsize);
T *newdata=new T[maxsize];
// has to do its own copy because realloc is not always compatible with
// new/delete on all machines
if(data){
for(int i=0;i<size;i++)
newdata[i]=data[i];
delete[] data;
}
data=newdata;
#ifdef FLEXARRAYDEBUG
printf("****FlexArray.grow(targ=%u): Changed to maxsize=%u size=%u data was = %lX\n",
targetSize,maxsize,size,data);
#endif
}
template<class T>
FlexArray<T>::FlexArray(FlexArray<T> &src):data(0),size(0),maxsize(0){
setSize(src.getSize());
//puts("\tFlexArray<T>copy constructor***********");
for(int i=0;i<src.getSize();i++)
data[i]=src.data[i];
//this->data[i]=src->data[i];
// (*this)[i]=src[i]; // a full stupid copy!!
#ifdef FLEXARRAYDEBUG
printf("****FlexArray copy constructor: Init with maxsize=%u size=%u data was = %lX\n",
maxsize,size,data);
#endif
}
template<class T>
FlexArray<T> &FlexArray<T>::operator=(FlexArray<T> &src){
if(this == &src) return *this;
setSize(src.getSize());
//puts("\t\tFlexArray<T>copy operator");
for(int i=0;i<src.getSize();i++)
data[i]=src[i]; // a full stupid copy!!
#ifdef FLEXARRAYDEBUG
printf("****FlexArray::=: Copied with maxsize=%u size=%u data was = %lX\n",
maxsize,size,data);
#endif
return *this;
}
template<class T>
int FlexArray<T>::setSize(int s){
#ifdef FLEXARRAYDEBUG
printf("****FlexArray.setSize(%u): Init with maxsize=%u size=%u data was = %lX\n",
s,maxsize,size,data);
#endif
if(s<0) s=0; // make sure size isn't negative
if(s<=maxsize){
size=s;
#ifdef FLEXARRAYDEBUG
printf("****FlexArray.setSize(%u): Changed to maxsize=%u size=%u data was = %lX\n",
s,maxsize,size,data);
#endif
return size; // can't allow shrinkage below current size
}
// otherwise if >, then set array size to exactly requested size
maxsize=s;
T *newdata=new T[maxsize];
if(data){
for(int i=0;i<size && i<maxsize;i++)
newdata[i]=data[i];
delete[] data;
}
data=newdata;
size=maxsize;
#ifdef FLEXARRAYDEBUG
printf("****FlexArray.setSize(%u): Changed to maxsize=%u size=%u data was = %lX\n",
s,maxsize,size,data);
#endif
return size;
}
template<class T>
int FlexArray<T>::append(T value){
if(size>=maxsize) // failsafe check
grow(size+1); // this array only increases in size
data[size++]=value;
return size;
}
template<class T>
int FlexArray<T>::append(T *values,int nvals){
if(size+nvals >= maxsize)
grow(size+nvals);//this array only increases in size
for(int i=0;i<nvals;i++)
data[size++]=values[i];
return size;
}
/*
1) Refcount must be fixed
2) Need to have more flexibility in how the block allocation
is defined (eg. memory allocation blocksize) Use obstacks?
This would require a more global memory pool
*/
#endif // __FLEXARRAY_TMPL_HH_
|
