Compilation fixes for gcc 3.1, MSVC 6.0 & 7.0
[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 #if !defined(_Vector_h_)
43 #define _Vector_h_
44
45 #if defined(external_templates)
46 #pragma interface
47 #endif
48
49 //ifdef this to nothing if it bothers old broken compilers
50 #define TYPENAME typename
51
52 #if defined(i386_unknown_nt4_0)
53 //turn off 255 char identifier truncation message
54 #pragma warning (disable: 4786)
55 #endif
56
57 #ifdef USE_STL_VECTOR
58 #include <stdlib.h>
59 #include <stl.h>
60 extern "C" {
61 typedef int (*qsort_cmpfunc_t)(const void *, const void *);
62 }
63 #define VECTOR_APPEND(l1, l2)   { for (unsigned int _i=0; _i < (l2).size(); _i++) (l1).push_back((l2)[_i]); }
64 #define VECTOR_SORT(l1, f)      qsort((l1).begin(),(l1).size(),sizeof((l1).front()), (qsort_cmpfunc_t) f);
65 /* #define VECTOR_SORT(l1, f)   stable_sort((l1).begin(),(l1).end(),f); */
66
67 #else
68
69 #define VECTOR_APPEND(l1, l2)   { for (unsigned int _i=0; _i < (l2).size(); _i++) (l1).push_back((l2)[_i]); }
70 #define VECTOR_SORT(l1, f)      l1.sort((qsort_cmpfunc_t)f);
71
72 #ifdef _KERNEL
73 #include <sys/types.h>
74 #include <sys/kmem.h>
75 #include <sys/debug.h> // ASSERT()
76 #define assert ASSERT
77 #else
78 #include <assert.h>
79 #include <stdlib.h>
80 #include <sys/types.h>
81 #endif
82
83 #ifndef _KERNEL
84 extern "C" {
85 typedef int (*qsort_cmpfunc_t)(const void *, const void *);
86 }
87 #endif
88
89
90 #ifndef _KERNEL
91 #include <new.h> // placement (void*) new to coax copy-ctor
92 #elif defined(_LP64)
93 inline void *operator new(unsigned long /* size_t */, void *place) { 
94    return place; 
95 }
96 #else
97 inline void *operator new(unsigned /* size_t does not work */, void *place) { 
98    return place; 
99 }
100 #endif
101
102 #ifndef NULL
103 #define NULL 0
104 #endif
105
106 #if !defined(DO_INLINE_P)
107 #define DO_INLINE_P
108 #endif
109
110 #if !defined(DO_INLINE_F)
111 #define DO_INLINE_F
112 #endif
113
114 template <class T>
115 class vec_stdalloc {
116  public:
117    static T *alloc(unsigned nelems) {
118       const size_t nbytes = nelems * sizeof(T);
119       
120 #ifdef _KERNEL
121       T* result = (T*)kmem_alloc(nbytes, KM_SLEEP);
122       // no need to assert(result) for the kernel due to KM_SLEEP flag
123 #else
124       T* result = (T*)malloc(nbytes);
125       assert(result);
126 #endif
127
128       return result;
129    }
130
131 #ifdef _KERNEL
132    static void free(T *vec, unsigned nelems) {
133       kmem_free(vec, sizeof(T)*nelems);
134    }
135 #else   
136    static void free(T *vec, unsigned /*nelems*/) {
137       ::free(vec);
138    }
139 #endif
140 };
141
142 template<class T, class A=vec_stdalloc<T> >
143 class vector {
144    enum { REMOVEONEELEM = 99999999 };
145  public:
146    // A few typedefs to be compatible with stl algorithms.
147    typedef T        value_type;
148    typedef T*       pointer;
149    typedef const T* const_pointer;
150    typedef T*       iterator;
151    typedef const T* const_iterator;
152    typedef T&       reference;
153    typedef const T& const_reference;
154
155    vector() {
156       data_ = NULL;
157       sz_ = tsz_ = 0;
158    }
159    
160 #ifndef _KERNEL
161    explicit
162 #endif
163    DO_INLINE_F
164    vector(unsigned sz) {
165       // explicit: don't allow this ctor to be used as an implicit conversion from
166       // unsigned to vector<T>.  So, this is disallowed:
167       // vector<T> myvector = 3;
168       // But this is still allowed, of course:
169       // vector<T> myvector(3);
170
171       // note: if you make use of this method, class T must have a default ctor
172       initialize_1(sz, T());
173    }
174    
175    DO_INLINE_F
176    vector(unsigned sz, const T &t) {
177       initialize_1(sz, t);
178    }
179
180    DO_INLINE_F
181    vector(const vector<T, A> &src) {
182       initialize_copy(src.sz_, src.begin(), src.end());
183    }
184
185    DO_INLINE_F
186    vector(const vector<T, A> &src1, const T &src2) {
187       // initialize as: this = src1; this += src2;
188       sz_ = tsz_ = src1.size() + 1;
189       data_ = A::alloc(sz_);
190       assert(data_);
191
192       // copy all of 'src1':
193       copy_into_uninitialized_space(data_, // dest
194                                     src1.begin(), src1.end());
195
196       // copy all of 'src2':
197       (void)new((void*)(data_ + sz_ - 1))T(src2);
198    }
199
200    DO_INLINE_F
201    vector(const vector<T,A> &src1, const vector<T,A> &src2) {
202       // initialize as: this = src1; this += src2;
203       sz_ = tsz_ = src1.size() + src2.size();
204       data_ = A::alloc(sz_);
205       assert(data_);
206       
207       // copy all of 'src1':
208       copy_into_uninitialized_space(data_, // dest
209                                     src1.begin(), src1.end());
210       
211       // copy all of 'src2':
212       copy_into_uninitialized_space(data_ + src1.size(), // dest
213                                     src2.begin(), src2.end());
214    }      
215
216 //  // Sun's version 4.2 compilers can't handle templated methods, but egcs/g++ can
217 //  #ifdef __GNUC__
218 //     template <class OTHERALLOC>
219 //     explicit vector(const vector<T, OTHERALLOC> &src) {
220 //        initialize_copy(src.size(), src.begin(), src.end());
221 //     }
222 //  #endif
223    
224    DO_INLINE_F 
225    ~vector() {
226       destroy();
227    }
228    DO_INLINE_F bool operator==(const vector<T, A> &) const;
229
230    DO_INLINE_F vector<T, A>&  operator=(const vector<T, A> &);
231    DO_INLINE_F vector<T, A>& operator+=(const vector<T, A> &);
232    DO_INLINE_F vector<T, A>& operator+=(const T &);
233    DO_INLINE_F 
234    vector<T, A> operator+(const T &item) const {
235       // A horribly slow routine, so use only when convenience
236       // outshines the performance loss.
237       vector<T, A> result(*this);
238       result += item;
239       return result;
240    }
241
242    DO_INLINE_F
243    reference operator[] (unsigned i) {
244       assert(i < sz_);
245       return *(data_ + i);
246    }
247
248    DO_INLINE_F
249    const_reference operator[] (unsigned i) const {
250       assert(i < sz_);
251       return *(data_ + i);
252    }
253
254    DO_INLINE_F
255    void pop_back() { // fry the last item in the vector
256       shrink(sz_ - 1);
257    }
258
259    DO_INLINE_F vector<T, A>& push_back(const T &);
260    DO_INLINE_F void erase (unsigned start, unsigned end = REMOVEONEELEM);
261    DO_INLINE_F void sort (int (*)(const void *, const void *));
262
263    DO_INLINE_F
264    void swap(vector<T, A> &other) {
265       T *mydata = data_;
266       const unsigned mysz = sz_;
267       const unsigned mytsz = tsz_;
268       
269       data_ = other.data_;
270       sz_ = other.sz_;
271       tsz_ = other.tsz_;
272
273       other.data_ = mydata;
274       other.sz_ = mysz;
275       other.tsz_ = mytsz;
276    }
277
278    DO_INLINE_F reference       front()       { return *begin(); }
279    DO_INLINE_F const_reference front() const { return *begin(); }
280    DO_INLINE_F reference       back()       { return *(end()-1); }
281    DO_INLINE_F const_reference back() const { return *(end()-1); }
282
283    DO_INLINE_F unsigned size() const {return sz_;}
284    
285    DO_INLINE_F void resize(unsigned, bool exact=true);
286       // note: if you use this method, class T must have a default ctor
287       // this method simply calls shrink() or grow(), as appropriate.
288
289    DO_INLINE_F void shrink(unsigned newsize);
290       // doesn't free up any memory, so well suited if you plan to later re-add
291       // to the vector.
292
293    DO_INLINE_F void clear() {if (sz_ > 0) shrink(0);}
294       // prefer clear() to resize(0) because former doesn't require a copy-ctor
295       // Doesn't free up any memory (expects you to add to the vector later).
296       // If you're pretty sure that you're done with vector, then prefer zap()
297       // instead.
298
299    DO_INLINE_F
300    void zap() {
301       // like clear() but truly frees up the vector's memory; 
302       // call when you don't expect to add to the vector any more
303       destroy();
304       sz_ = tsz_ = 0;
305    }
306       
307    DO_INLINE_F void grow(unsigned newsize, bool exact=false);
308       // note: if you use this method, class T must have a default ctor
309
310    DO_INLINE_F void reserve(unsigned nelems) { reserve_exact(nelems); }
311       // for STL compatibility
312    DO_INLINE_F void reserve_exact(unsigned nelems);
313    DO_INLINE_F void reserve_roundup(unsigned nelems);
314    
315    DO_INLINE_F
316    unsigned capacity() const {
317       // capacity()-size() is the # of elems that can be inserted before
318       // reallocation takes place; thus, pointers into the vector remain
319       // valid until then.
320       return tsz_;
321    }
322
323    DO_INLINE_F iterator reserve_for_inplace_construction(unsigned nelems);
324       // allocates uninitialized memory, sets size(), returns iterator to first item.
325       // Use placement void* operator new to initialize in place, eliminating the
326       // need for a ctor,copy-ctor sequence.  For expert users only!
327    
328    DO_INLINE_F iterator append_with_inplace_construction();
329       // Appends a single, totally uninitialized member to the vector.  Bumps up sz_;
330       // reserves as needed.
331    
332    // iteration, stl style:
333    DO_INLINE_F iterator       begin()       { return data_; }
334    DO_INLINE_F const_iterator begin() const { return data_; }
335    DO_INLINE_F iterator       end()       { return begin() + sz_; }
336    DO_INLINE_F const_iterator end() const { return begin() + sz_; }
337
338  private:
339    DO_INLINE_P
340    static void deconstruct_items(T *first, T *last) {
341       for (; first != last; ++first) 
342          first->~T();
343    }
344
345    DO_INLINE_P
346    static void copy_into_uninitialized_space(T *dest, const T *src_first,
347                                              const T *src_last) {
348       // manually call copy-ctor to copy all the items from src to dest, assuming
349       // that dest is uninitialized memory but src is properly initialized.
350                                                 
351       while (src_first != src_last)
352          new((void*)dest++) T(*src_first++);
353    }
354
355    DO_INLINE_P
356    static void copy_1item_into_uninitialized_space(T *dest, const T &src,
357                                                    unsigned n) {
358       while (n--)
359          new((void*)dest++) T(src);
360    }
361
362    DO_INLINE_P void initialize_1(unsigned sz, const T &t);
363    DO_INLINE_P void initialize_copy(unsigned sz, const T *srcfirst, const T *srcend);
364
365    DO_INLINE_P void destroy();
366
367    T*       data_;
368    unsigned sz_;
369    unsigned tsz_;
370 };
371
372 template<class T, class A>
373 DO_INLINE_F
374 vector<T, A>&
375 vector<T, A>::operator=(const vector<T, A>& src) {
376    if (this == &src)
377       return *this;
378
379    bool fryAndRecreate = (src.sz_ > tsz_); // or if alloc/free fns differ...
380
381    if (fryAndRecreate) {
382       // deconstruct the old vector and deallocate it
383       destroy();
384        
385       // allocate the new vector and initialize it
386       initialize_copy(src.sz_, src.begin(), src.end());
387    }
388    else {
389       // deconstruct existing items
390       deconstruct_items(begin(), end());
391        
392       sz_ = src.sz_; // tsz_ left unchanged
393       copy_into_uninitialized_space(data_, // dest
394                                     src.begin(), src.end());
395    }
396
397    return *this;
398 }
399
400 template<class T, class A>
401 DO_INLINE_F
402 vector<T, A>&
403 vector<T, A>::operator+=(const vector<T,A>& src) {
404    const unsigned newsize = sz_ + src.sz_;
405    if (newsize > tsz_)
406       reserve_roundup(newsize);
407    
408    copy_into_uninitialized_space(data_ + sz_, // dest
409                                  src.begin(), src.end());
410
411    sz_ += src.sz_;
412    assert(tsz_ >= sz_); // reserve_roundup() made this so
413
414    return *this;
415 }
416
417 template<class T, class A>
418 DO_INLINE_F
419 vector<T, A>&
420 vector<T, A>::operator+=(const T& t) {
421    const unsigned newsize = sz_ + 1;
422    if (newsize > tsz_)
423       reserve_roundup(newsize);
424    
425    copy_1item_into_uninitialized_space(data_ + sz_, // dest
426                                        t, // src item
427                                        1);
428    sz_++;
429    assert(tsz_ >= sz_); // reserve_roundup() made this so
430
431    return *this;
432 }
433
434 template<class T, class A>
435 DO_INLINE_F
436 vector<T, A>&
437 vector<T, A>::push_back(const T& t) {
438    const unsigned newsize = sz_ + 1;
439    if (newsize > tsz_)
440       reserve_roundup(newsize);
441    
442    copy_1item_into_uninitialized_space(data_ + sz_, // dest
443                                        t, // src item
444                                        1);
445    sz_++;
446    assert(tsz_ >= sz_); // reserve_roundup() made this so
447
448    return *this;
449 }
450
451 template<class T, class A>
452 DO_INLINE_F
453 void vector<T, A>::sort(int (*cmpfunc)(const void *, const void *)) {
454    qsort((void *) data_, sz_, sizeof(T), (qsort_cmpfunc_t)cmpfunc);
455 }
456
457 template<class T, class A>
458 DO_INLINE_F
459 void vector<T, A>::shrink(unsigned newsize) {
460    assert(newsize < sz_);
461    deconstruct_items(begin() + newsize, end());
462    sz_ = newsize;
463 }
464
465 template<class T, class A>
466 DO_INLINE_F
467 void vector<T, A>::grow(unsigned newsize, bool exact) {
468    // reallocate if tsz_ isn't big enough
469    if (exact)
470       reserve_exact(newsize);
471    else
472       reserve_roundup(newsize);
473       
474    copy_1item_into_uninitialized_space(data_ + sz_, // dest
475                                        T(), // src item
476                                        newsize - sz_);
477    sz_ = newsize;
478    assert(tsz_ >= sz_);
479 }
480
481
482 template<class T, class A>
483 DO_INLINE_F
484 void vector<T, A>::resize(unsigned newsize, bool exact) {
485    if (newsize == sz_)
486       ;
487    else if (newsize < sz_)
488       shrink(newsize);
489    else
490       grow(newsize, exact);
491 }
492
493 template<class T, class A>
494 DO_INLINE_F
495 void vector<T, A>::erase(unsigned start, unsigned end) {
496     int origSz = sz_;
497     int emptyIndex = start;
498     if(end == REMOVEONEELEM)  
499         end = start;
500     int copyIndex = end + 1;
501     while(copyIndex<origSz) {
502         data_[emptyIndex++] = data_[copyIndex++];
503     }
504     resize(origSz - (end - start + 1));
505 }
506
507 template<class T, class A>
508 DO_INLINE_P
509 void vector<T, A>::initialize_1(unsigned sz, const T &t) {
510    sz_ = tsz_ = sz;
511    if (sz_ > 0) {
512       data_ = A::alloc(sz_);
513       assert(data_);
514       copy_1item_into_uninitialized_space(data_, t, sz_);
515    }
516    else
517       data_ = NULL;
518 }
519
520 template<class T, class A>
521 DO_INLINE_P
522 void vector<T, A>::initialize_copy(unsigned sz, const T *srcfirst, const T *srclast) {
523    sz_ = tsz_ = sz;
524    if (sz_ > 0) {
525       data_ = A::alloc(sz_);
526       assert(data_ && srcfirst && srclast);
527       copy_into_uninitialized_space(data_, // dest
528                                     srcfirst, srclast);
529    }
530    else
531       data_ = NULL;
532 }
533
534 template<class T, class A>
535 DO_INLINE_P
536 void vector<T, A>::destroy() {
537    if (data_) {
538       deconstruct_items(begin(), end());
539       assert(tsz_ > 0); // it would be too strict to also assert that sz_ > 0
540       A::free(data_, tsz_); // tsz_, not sz_!
541       data_ = NULL; // help purify find mem leaks
542    }
543    else {
544       if(sz_ == 0) assert(tsz_==0);
545    }
546 }
547
548 template<class T, class A>
549 DO_INLINE_F
550 void vector<T, A>::reserve_roundup(unsigned nelems) {
551    // reserve *at least* nelems elements in the vector.
552    assert(nelems >= sz_); // don't call us to shrink the vector!
553
554    if (tsz_ > nelems)
555       return; // nothing needed...(neat optimization)
556
557    // round up 'nelems' to a power of two
558    unsigned roundup_nelems = 1;
559    while (roundup_nelems < nelems)
560       roundup_nelems <<= 1; // multiply by 2
561
562    assert(roundup_nelems >= nelems);
563    
564    reserve_exact(roundup_nelems);
565 }
566
567 template<class T, class A>
568 DO_INLINE_F
569 TYPENAME vector<T, A>::iterator
570 vector<T, A>::append_with_inplace_construction() {
571    reserve_roundup(sz_ + 1);
572       // used to be reserve_exact(), but with huge performance penalty!
573    
574    ++sz_;
575    
576    return end()-1;
577 }
578
579
580 template<class T, class A>
581 DO_INLINE_F
582 TYPENAME vector<T, A>::iterator
583 vector<T, A>::reserve_for_inplace_construction(unsigned nelems) {
584    // NOTE: while I hunt down a certain mem leak, I'm declaring that this
585    // routine must only be called on a default-constructor vector or one that
586    // has been zap()'d (clear(0) or shrink(0) is not sufficient).
587
588    assert(sz_ == 0);
589    assert(tsz_ == 0); // too strong an assert? [see above]
590    assert(data_ == NULL); // too strong an assert? [see above]
591
592    if (nelems > 0) {
593       //   reserve_exact(nelems);
594
595       // we use the following "optimized reserve_exact()" to avoid the need for a
596       // copy-ctor.  If we remove the above asserts then we may not have the luxury
597       // of assuming such a trivial reserve_exact().
598       data_ = A::alloc(nelems); // part 1 of our optimized reserve_exact()
599       tsz_ = nelems; // part 2 of our optimized reserve_exact()
600    }
601    
602    assert(sz_ == 0);
603    assert(tsz_ >= nelems);
604    if (nelems > 0)
605       assert(data_ != NULL);
606
607    sz_ = nelems;
608    
609    return begin();
610 }
611
612 template<class T, class A>
613 DO_INLINE_F
614 void vector<T, A>::reserve_exact(unsigned nelems) {
615    // exact because we're not gonna round up nelems to a power of 2
616    // note: sz_ doesn't change
617
618    assert(nelems >= sz_); // don't use to shrink the vector!
619
620    if (tsz_ >= nelems)
621       return; // nothing needed
622
623    // Alloc new vector
624    T *newdata = A::alloc(nelems);
625
626    // Copy items over, if any
627    if (data_) {
628       assert(tsz_ > 0); // it would be too strict to also assert that sz_ > 0
629       copy_into_uninitialized_space(newdata, // dest
630                                     begin(), end());
631    }
632    else
633       assert(tsz_ == 0 && sz_ == 0);
634
635    // Fry the old vector
636    destroy();
637    
638    // Finalize
639    data_ = newdata;
640    tsz_ = nelems;
641    // note: sz_ doesn't change (on purpose)
642 }
643
644 template<class T, class A>
645 DO_INLINE_P
646 bool
647 find(const vector<T, A> &v, const T &v0, unsigned &l) {
648         unsigned i, sz;
649         sz = v.size();
650         for( i = 0; i < sz; ++i ) {
651                 if( v[ i ] == v0 ) {
652                         l = i;
653                         return true;
654                 }
655         }
656         return false;
657 }
658
659 template<class T, class A>
660 DO_INLINE_P
661 bool vector<T, A>::operator== (const vector<T,A> &) const
662 {
663   return false;
664 }
665
666 #endif /* ifdef USE_STL_VECTOR */
667
668 #endif /* !defined(_Vector_h_) */
669
670
671
672
673
674
675
676