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