source: trunk/lib/symtab/arrays/HeapArray.h @ 1229

Last change on this file since 1229 was 1229, checked in by vla24, 8 years ago

Reorganized SymbolTable? library

File size: 9.6 KB
Line 
1/*
2 *  HeapArray.h
3 *
4 *  Created on: 24-Oct-2009
5 *  Author: ksherdy
6 *  Version: 0.9
7 *  Description: WARNING SSE specific implementation. See below for a description of the compile time #define flags.
8 * 
9 *               Heap allocated, dynamic, 1D array with 'chunk_size' * sizeof(Type) bytes memory allocation, and aligned memory allocations.
10 *
11 *               The methods of HeapArray use the signatures of the STL Vector class to allow performance comparison with STL Vector for performance evaluation.       
12 *
13 *               HeapArray allocates sizeof(__128mi) chunks of memory based on max_elems and template parameter type.
14 *               This approach allows variable byte length insertions but iteration through array contents in sizeof(__m128i) chunks,
15 *               without the need to provide additional padding and without segmentation faults.
16 *               
17 *               For example, allocates sufficient space to iterate array contents in sizeof(__m128i) chunks.
18 *
19 *               HeapArray<unsigned char> ary(17,sizeof(__m128i),16);
20 *               for(int i=0;i<17;i++)
21 *               {      unsigned char c = 56;
22 *                       ary.push_back(c);
23 *               }
24 *               for(int i=0;i<ary.size();i+=sizeof(__m128i))
25 *               {       __m128i * p = (__m128i*)&ary.get(i); 
26 *                       print_simd_register("p", *p);
27 *               }     
28 *
29 *               'chunk_size' is defined as the number of elements in a chunk, e.g. chunk_size = 4 implies 4 elements of a specific C++ type are allocated,
30 *               for example, 4 char, 4 int, 4 long...
31 *
32 *               The memory allocation strategy is to first allocate 'chunk_size' * sizeof(Type) number of bytes and then to allocate multiples of that value.
33 *                                                                                              // max_elems  - minimum number of elements in initial allocation, constructor rounds up to chunk multiples
34 *               HeapArray(max_elems, chunk_size, byte_alignment);                              // chuck_size - number of elements allocated in a chunk 
35 *               HeapArray<unsigned char>  heap_ary0(1,sizeof(__m128i),sizeof(__m128i));        // allocates 1 16 byte chunks of memory to hold at least 1 unsigned char
36 *               HeapArray<unsigned char> heap_ary1(2,sizeof(__m128i),sizeof(__m128i));         // allocates 1 16 byte chunks of memory to hold at least 1 unsigned char
37 *               HeapArray<unsigned char> heap_ary2(15,sizeof(__m128i),sizeof(__m128i));        // allocates 1 16 byte chunks of memory to hold at least 1 unsigned char
38 *               HeapArray<unsigned char> heap_ary3(16,sizeof(__m128i),sizeof(__m128i));        // allocates 1 16 byte chunks of memory to hold at least 1 unsigned char
39 *               HeapArray<unsigned char> heap_ary4(17,sizeof(__m128i),sizeof(__m128i));        // allocates 2 16 byte chunks of memory to hold at least 17 unsigned char
40 *               HeapArray<unsigned char> heap_ary5(16,sizeof(__m128i)*4,sizeof(__m128i));      // allocates 1 64 byte chunk of memory to hold at least 16 unsigned char
41 *               HeapArray<size_t> heap_ary6(1,sizeof(__m128i),sizeof(__m128i));                // allocates 1 16*sizeof(size_t) byte chunks of memory to hold at least 1 size_t
42 *               HeapArray<size_t> heap_ary7(5,sizeof(__m128i),sizeof(__m128i));                // allocates 2 16*sizeof(size_t) byte chunks of memory to hold at least 5 size_t
43 *               
44 *               Memory de-allocated on destruction only.
45 *               
46 *               Calling clear() sets the current element size to zero but does *not* deallocate memory.
47 *               
48 *               The semantics for bounds checking is that a bounds check is performed
49 *               for each of the push_back method variants.
50 *               
51 *               Bounds checking is optionally performed for all other interface methods -- get(), set(),... --
52 *               which may potentially violate array boundaries but that the programmer may
53 *               be aware of and not require. If the BOUNDS_CHECK preprocessor directive is defined at compile time
54 *               then a boundary check is performed for all interface methods.
55 *   
56 */
57
58#ifndef HEAPARRAY_H_
59#define HEAPARRAY_H_
60
61// COMPILE TIME FLAGS
62//
63//#define HEAPARRAY_DEBUG       // Print debug information to standard out.
64//#define BOUNDS_CHECK          // Perform boundary value checking for set, get, size, resize, clear, ...
65//#define INIT_ZEROES           // Use a default initialization value of 0.
66//#define INIT_ONES             // Use a default initialization value of 1.
67
68#include <mm_malloc.h>
69#include <memory.h>
70#include <cstdlib>
71#include <stdint.h>
72#include <iostream>
73using namespace std;
74
75template <typename T>
76class HeapArray {
77
78public:
79       
80        // Allocates 'max_elems' elements rounded up to the next multiple of chunk_size bytes.
81        HeapArray(size_t max_elems=0, size_t chunk_size=1, size_t byte_alignment=16);
82        ~HeapArray();
83
84        // Push a single item. Performs bounds checks. Allocates memory if required. Copy Value.
85        inline void push_back(const T value); 
86       
87        // Push multiple items. Performs bounds checks. Allocates memory if required. Copy value.
88        inline void push_back(const T * value, const size_t count); 
89       
90        // Push multiple items and advance. Performs bounds checks. Allocates memory if required. Copy value.
91        inline void push_back_adv(const T * value, const size_t count, const size_t adv_count); 
92       
93        // WARNING: No bounds checking performed unless BOUNDS_CHECK is defined. Allocates memory if required.
94        inline void set(const size_t idx, T value);
95       
96        // WARNING: No bounds checking performed unless BOUNDS_CHECK is defined.
97        inline T & get(const size_t idx) const;
98       
99        // Returns current size.
100        inline size_t size() const {return crt_elems_;}
101
102        // If next_size > current size the array expanded to contain at least next_size elements.
103        // The current size is updated to next_size. New elements are default initialized.
104        size_t resize(const size_t next_size);
105       
106        // If next_size > current size the array expanded to contain space for at least next_size elements.
107        // The current size is *not* updated.
108        size_t reserve(const size_t next_size);
109       
110        // Clear
111        inline void clear() {crt_elems_ = 0;}
112       
113private:
114        // Private Copy Constructor / Assignment Operator
115        HeapArray(const HeapArray & ary);
116        HeapArray & operator=(const HeapArray &);
117
118        void expand(size_t next_size); 
119       
120        size_t max_elems_;              // capacity     
121        size_t chunk_size_;             // allocation chunk size
122        size_t byte_alignment_;         // byte alignment
123        size_t crt_elems_;              // current element count
124        T * ary_;
125};
126
127template <typename T>
128HeapArray<T>::HeapArray(size_t max_elems, size_t chunk_size, size_t byte_alignment) {
129
130        chunk_size_ = (0 == chunk_size) ? 1 : chunk_size; 
131       
132        if (0 == max_elems) {
133                max_elems = 1;
134        } 
135   
136        if((max_elems % chunk_size) == 0) {
137                max_elems_ = max_elems;
138        } else {
139                max_elems_ = (max_elems + chunk_size) - (max_elems % chunk_size); 
140        }
141                       
142        byte_alignment_ = (0 == byte_alignment) ? 1 : byte_alignment;
143        crt_elems_ = 0;
144       
145#ifdef HEAPARRAY_DEBUG
146        cout << "HeapArray<T>::HeapArray(" << max_elems_ << ")" << endl;
147#endif
148
149        ary_ = (T*)_mm_malloc(max_elems_ * sizeof(T), byte_alignment_);
150       
151        if(ary_ == NULL) { cerr << "HeapArray<T>::HeapArray(). Out of memory." << endl; exit(1);}       
152
153#ifdef INIT_ZEROES
154        memset(ary_,0,sizeof(T)*max_elems_);   
155#endif
156
157#ifdef INIT_ONES
158        memset(ary_,-1,sizeof(T)*max_elems_);   
159#endif
160       
161}
162
163template <typename T>
164HeapArray<T>::~HeapArray() {
165        _mm_free(ary_);
166               
167#ifdef HEAPARRAY_DEBUG 
168        cout << "HeapArray<T>::~HeapArray()" << endl;
169#endif         
170}
171
172template <typename T>
173inline void HeapArray<T>::push_back(const T value){
174
175        if(crt_elems_ >= max_elems_) {
176                size_t next_size = max_elems_ << 1; 
177                expand(next_size);
178        }
179        ary_[crt_elems_] = value;
180        crt_elems_++;
181} 
182
183template <typename T>
184inline void HeapArray<T>::push_back(const T * value, const size_t count) { 
185        if((crt_elems_ + count) >= max_elems_) {
186                size_t next_size = max_elems_ << 1; 
187                next_size += count; 
188                expand(next_size);
189        }
190       
191        memcpy(&ary_[crt_elems_], value, count * sizeof(T));
192        crt_elems_ += count;
193}
194
195template <typename T>
196inline void HeapArray<T>::push_back_adv(const T * value, const size_t count, const size_t adv_count) {
197        if((crt_elems_ + (count + adv_count)) >= max_elems_) {
198                size_t next_size = max_elems_ << 1; 
199                next_size += (count + adv_count); 
200                expand(next_size);
201        }
202
203        memcpy(&ary_[crt_elems_], value, count * sizeof(T));
204        crt_elems_ += (count + adv_count);
205} 
206
207template <typename T>
208inline void HeapArray<T>::set(const size_t idx, T value){
209#ifdef BOUNDS_CHECK
210        if(idx >= max_elems_) {
211                cerr << "HeapArray<T>::set(" << idx << ", " << value << "). " << "Column index out of range." << endl;
212                exit(1);
213        }       
214#endif
215        ary_[idx] = value;
216}
217
218template <typename T>
219inline T & HeapArray<T>::get(const size_t idx) const{
220#ifdef BOUNDS_CHECK
221        if(idx >= max_elems_) {
222                cerr << "HeapArray<T>::get(" << idx << "). " << "Column index out of range." << endl;
223                exit(1);
224        }       
225#endif
226        return ary_[idx];                       
227}
228
229template <typename T>
230size_t HeapArray<T>::resize(const size_t next_size) {
231       
232        if(next_size > max_elems_) {   
233                expand(next_size);
234               
235        }
236        crt_elems_ = max_elems_;       
237       
238        return crt_elems_;
239}
240
241template <typename T>
242size_t HeapArray<T>::reserve(const size_t next_size) {
243
244        if(next_size > max_elems_) {   
245                expand(next_size);
246        }
247        return max_elems_;
248}
249
250template <typename T>
251void HeapArray<T>::expand(const size_t next_size) {
252       
253        //size_t size = (1 == chunk_size_) ? next_size : ((next_size + chunk_size_) - (next_size % chunk_size_)); // expand to a chunk_size_ boundary
254       
255#ifdef HEAPARRAY_DEBUG 
256        cout << "HeapArray<T>::resize(" << next_size << ")" << endl;
257#endif
258
259        T * temp = (T*)_mm_malloc(next_size  * sizeof(T), byte_alignment_);
260       
261        if(temp== NULL) { cerr << "HeapArray<T>::HeapArray(). Out of memory." << endl; exit(1);}
262
263        memcpy(temp,ary_,sizeof(T)*max_elems_);
264        _mm_free(ary_);
265
266    ary_ = NULL;
267        ary_ = temp;
268
269        #ifdef INIT_ZEROES
270                memset(ary_+ max_elems_,0, sizeof(T)*(next_size-max_elems_));   
271        #endif
272       
273        #ifdef INIT_ONES
274                memset(ary_+ max_elems_,-1, sizeof(T)*(next_size-max_elems_)); 
275        #endif
276
277        max_elems_ = next_size;
278}
279
280#endif /*HEAPARRAY_H_*/
Note: See TracBrowser for help on using the repository browser.