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