removed compiler warning; added a member which removes (erase) an element
[dyninst.git] / common / h / Vector.h
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /************************************************************************
43  * Vector.h: resizable vectors.
44  * $Id: Vector.h,v 1.14 2001/08/23 14:43:11 schendel Exp $
45 ************************************************************************/
46
47
48 \f
49
50
51 #if !defined(_Vector_h_)
52 #define _Vector_h_
53
54 #if defined(external_templates)
55 #pragma interface
56 #endif
57
58 \f
59
60 /************************************************************************
61  * header files.
62 ************************************************************************/
63
64 #include <assert.h>
65 #include <stdlib.h>
66
67 #ifdef USE_STL_VECTOR
68
69 #include <stl.h>
70
71 extern "C" {
72 typedef int (*qsort_cmpfunc_t)(const void *, const void *);
73 }
74
75 #define VECTOR_APPEND(l1, l2)   { for (unsigned int _i=0; _i < (l2).size(); _i++) (l1).push_back((l2)[_i]); }
76
77 #define VECTOR_SORT(l1, f)      qsort((l1).begin(),(l1).size(),sizeof((l1).front()), (qsort_cmpfunc_t) f);
78 /* #define VECTOR_SORT(l1, f)   stable_sort((l1).begin(),(l1).end(),f); */
79
80 #else
81
82 #define VECTOR_APPEND(l1, l2)   { for (unsigned int _i=0; _i < (l2).size(); _i++) (l1).push_back((l2)[_i]); }
83
84 #define VECTOR_SORT(l1, f)      l1.sort((qsort_cmpfunc_t)f);
85
86 \f
87
88 /************************************************************************
89  * template<class T> class Vector
90 ************************************************************************/
91
92 #if !defined(DO_INLINE_P)
93 #define DO_INLINE_P
94 #endif
95
96 #if !defined(DO_INLINE_F)
97 #define DO_INLINE_F
98 #endif
99
100 template<class T>
101 class vector {
102     enum { REMOVEONEELEM = 99999999 };
103 public:
104     DO_INLINE_F vector (unsigned =0);
105     DO_INLINE_F vector (unsigned, const T &);
106     DO_INLINE_F vector (const vector<T> &);
107     DO_INLINE_F ~vector ();
108
109     DO_INLINE_F vector<T>&  operator= (const vector<T> &);
110
111     // These two should be elimindated as non-standard
112 #ifndef BPATCH_LIBRARY
113     DO_INLINE_F vector<T>& operator+= (const vector<T> &);
114     DO_INLINE_F vector<T>& operator+= (const T &);
115 #endif
116
117     DO_INLINE_F vector<T>& push_back(const T &); 
118
119     DO_INLINE_F T&         operator[] (unsigned) const;
120     DO_INLINE_F bool       operator== (const vector<T> &) const;
121     DO_INLINE_F unsigned         size () const;
122     DO_INLINE_F void           resize (unsigned);
123
124     /*
125     DO_INLINE_F vector<T>&     insert (unsigned, const vector<T> &);
126     DO_INLINE_F vector<T>&     insert (unsigned, const T &);
127     */
128
129     // The order of the elements in the array is preserved after the erase.
130     // Passing just a start index will erase just the one element at the
131     // index start.  The elements that are removed are not destroyed by this
132     // method.
133     DO_INLINE_F void   erase (unsigned start, unsigned end = REMOVEONEELEM);
134
135     DO_INLINE_F void             sort (int (*)(const void *, const void *));
136
137 private:
138     DO_INLINE_P void  create (unsigned);
139     DO_INLINE_P void    init (const T &);
140     DO_INLINE_P void    copy (unsigned, const T *);
141     DO_INLINE_P void destroy ();
142
143     T*       data_;
144     unsigned sz_;
145     unsigned tsz_;
146 };
147
148 template<class T>
149 DO_INLINE_F
150 vector<T>::vector(unsigned sz)
151     : data_(0), sz_(0), tsz_(0) {
152     create(sz);
153 }
154
155 template<class T>
156 DO_INLINE_F
157 vector<T>::vector(unsigned sz, const T& v0)
158     : data_(0), sz_(0), tsz_(0) {
159     create(sz);
160     init(v0);
161 }
162
163
164 template<class T>
165 DO_INLINE_F
166 vector<T>::vector(const vector<T>& v)
167     : data_(0), sz_(0), tsz_(0) {
168     create(v.sz_);
169     copy(v.sz_, v.data_);
170 }
171
172 template<class T>
173 DO_INLINE_F
174 vector<T>::~vector() {
175     destroy();
176 }
177
178 template<class T>
179 DO_INLINE_F
180 vector<T>&
181 vector<T>::operator=(const vector<T>& v) {
182     if (this == &v) {
183         return *this;
184     }
185     destroy();
186     create(v.sz_);
187     copy(v.sz_, v.data_);
188     return *this;
189 }
190
191
192 #ifndef BPATCH_LIBRARY
193 template<class T>
194 DO_INLINE_F
195 vector<T>&
196 vector<T>::operator+=(const vector<T>& v) {
197     unsigned osz = sz_;
198     resize(osz + v.sz_);
199     for (unsigned i = osz; i < sz_; ++i) {
200         data_[i] = v.data_[i-osz];
201     }
202     return *this;
203 }
204
205 template<class T>
206 DO_INLINE_F
207 vector<T>&
208 vector<T>::operator+=(const T& v0) {
209     resize(sz_+1);
210     data_[sz_-1] = v0;
211     return *this;
212 }
213 #endif
214
215 template<class T>
216 DO_INLINE_F
217 vector<T>&
218 vector<T>::push_back(const T& v0) {
219     resize(sz_+1);
220     data_[sz_-1] = v0;
221     return *this;
222 }
223 /*
224 template<class T>
225 DO_INLINE_F
226 vector<T>&
227 vector<T>::insert(unsigned l, const vector<T>& v) {
228         unsigned osz = sz_, i;
229         resize(osz+v.sz_);
230         if( l > osz )
231                 l = osz ;
232         if( osz != 0 ) {
233                 for(i = osz-1; i >= l; --i ) {
234                         data_[i+v.sz_] = data_[i];
235                 }
236         }
237         for(i = l; i < l+v.sz_; ++i ) {
238                 data_[i] = v.data_[i-l];
239         }
240     return *this;
241 }
242
243 template<class T>
244 DO_INLINE_F
245 vector<T>&
246 vector<T>::insert(unsigned l, const T& v0) {
247         unsigned osz = sz_, i;
248         resize(osz+1);
249         if( l > osz )
250                 l = osz;
251         if( osz != 0 ) {
252                 for(i = osz-1; i >= l; --i ) {
253                         data_[i+1] = data_[i];
254                 }
255         }
256         data_[l] = v0;
257     return *this;
258 }
259 */
260
261 template<class T>
262 DO_INLINE_F
263 void
264 vector<T>::erase(unsigned start, unsigned end) {
265     int origSz = sz_;
266     int emptyIndex = start;
267     if(end == REMOVEONEELEM)  
268         end = start;
269     int copyIndex = end + 1;
270     while(copyIndex<origSz) {
271         data_[emptyIndex++] = data_[copyIndex++];
272     }
273     resize(origSz - (end - start + 1));
274 }
275
276 template<class T>
277 DO_INLINE_F
278 T&
279 vector<T>::operator[](unsigned i) const {
280     assert(i < sz_);
281     return data_[i];
282 }
283
284 template<class T>
285 DO_INLINE_F
286 bool
287 vector<T>::operator==(const vector<T>& v) const {
288     if (sz_ != v.sz_) {
289         return false;
290     }
291 // TODO
292 #if defined(notdef)
293     for (unsigned i = 0; i < sz_; i++) {
294         if (!(data_[i] == v.data_[i])) {
295             return false;
296         }
297     }
298 #endif
299     return true;
300 }
301
302 template<class T>
303 DO_INLINE_F
304 unsigned
305 vector<T>::size() const {
306     return sz_;
307 }
308
309 template<class T>
310 DO_INLINE_F
311 void
312 vector<T>::resize(unsigned sz) {
313     if (tsz_ == 0) {
314         create(sz);
315     }
316     else if (tsz_ >= sz) {
317         sz_ = sz;
318     }
319     else {
320         T*       odata = data_;
321         unsigned osz   = sz_;
322         unsigned nsz   = (((2*tsz_)>sz)?(2*tsz_):(sz));
323
324         data_ = new T[nsz];
325         tsz_  = nsz;
326         sz_   = sz;
327
328         for (unsigned i = 0; i < osz; ++i) {
329             data_[i] = odata[i];
330         }
331         delete[] odata;
332
333         sz_ = sz;
334     }
335 }
336
337 extern "C" {
338 typedef int (*qsort_cmpfunc_t)(const void *, const void *);
339 }
340
341 template<class T>
342 DO_INLINE_F
343 void
344 vector<T>::sort(int (*cmpfunc)(const void *, const void *)) {
345     qsort((void *) data_, sz_, sizeof(T), (qsort_cmpfunc_t)cmpfunc);
346 }
347
348 template<class T>
349 DO_INLINE_P
350 void
351 vector<T>::create(unsigned sz) {
352     if (sz > 0) {
353         data_ = new T[sz];
354     }
355     sz_ = tsz_ = sz;
356 }
357
358 template<class T>
359 DO_INLINE_P
360 void
361 vector<T>::init(const T& v0) {
362     for (unsigned i = 0; i < sz_; ++i) {
363         data_[i] = v0;
364     }
365 }
366
367 template<class T>
368 DO_INLINE_P
369 void
370 vector<T>::copy(unsigned sz, const T* data) {
371     for (unsigned i = 0; i < sz; ++i) {
372         data_[i] = data[i];
373     }
374 }
375
376 template<class T>
377 DO_INLINE_P
378 void
379 vector<T>::destroy() {
380     delete[] data_; data_ = 0;
381     sz_ = tsz_ = 0;
382 }
383
384 template<class T>
385 DO_INLINE_P
386 bool
387 find(const vector<T> &v, const T &v0, unsigned &l) {
388         unsigned i, sz;
389         sz = v.size();
390         for( i = 0; i < sz; ++i ) {
391                 if( v[ i ] == v0 ) {
392                         l = i;
393                         return true;
394                 }
395         }
396         return false;
397 }
398
399 #endif
400
401 #endif /* !defined(_Vector_h_) */