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