ResizeArrayRaw.h

Go to the documentation of this file.
00001 
00007 /*
00008   Data storage class for ResizeArray and related container classes.
00009   Copy and assignment copy raw pointers, use copy() to copy data.
00010   Destructor does not delete data, call free first.
00011 */
00012 
00013 
00014 #ifndef RESIZEARRAYRAW_H
00015 #define RESIZEARRAYRAW_H
00016 
00017 #include <new>
00018 #include <string.h>
00019 #include "common.h"
00020 
00021 #define ResizeArrayGrowthFactor 1.5
00022 #define ResizeArrayMinSize 8
00023 
00024 // Need this juju to use templated friend below
00025 template <class Type> class ResizeArray;
00026 template <class Type> class SortableResizeArray;
00027 template <class Type> class SortedArray;
00028 template <class Type> class UniqueSortedArray;
00029 template <class Type> class ResizeArrayIter;
00030 
00031 // Class assumes that one can bit move objects
00032 // around on array.  This will be true
00033 // as long as object has no pointers to itself.
00034 template <class Elem> class ResizeArrayRaw {
00035 
00036   private:
00037     Elem *array;
00038     unsigned char *varray;
00039 
00040     // Use of int (int32) is safe for counting elements.
00041     int arraySize;
00042     int allocSize;
00043 
00044     // No constructor run on new elements
00045     // arraySize is not adjusted, only allocSize
00046     void resizeRaw(int size) {
00047       if (size <= allocSize) return;
00048   
00049       // Note that ResizeArrayGrowthFactor is type double so the
00050       // multiplication below is also done in double.
00051       // Assuming int32, the conversion from double overflows at
00052       //   allocSize = 1431655765
00053       // Conditional remains safe if overflow causes RHS < 0.
00054       if (size < (int)(allocSize*ResizeArrayGrowthFactor)) {
00055         size = (int)(allocSize*ResizeArrayGrowthFactor);
00056       }
00057       // The next conditional will test true either for very small or
00058       // unallocated arrays or if the above conditional causes overflow.
00059       if ( (size-allocSize) < ResizeArrayMinSize) {
00060         // Overflow occurs here only when allocSize is within
00061         // ResizeArrayMinSize of 2^31.
00062         size = allocSize+ResizeArrayMinSize;
00063       }
00064 
00065       // Align everything to 64-byte boundaries (if possible).
00066       // Use of sizeof below promotes expression to type size_t.
00067       unsigned char *tmpv = new unsigned char[size*sizeof(Elem)+63];
00068       //Elem *tmpa = (Elem *)((((long)tmpv)+63L)&(-64L));
00069       // Someday we might need this alternate form.
00070       //
00071       // The following pointer manipulation is dangerous. We should use
00072       // reinterpret_cast<uintptr_t> or equivalent to convert tmpv+63
00073       // to an unsigned integer type before doing bitwise and operation.
00074       //
00075       // The 63 value (64-byte alignment) aligns for AVX-512 registers.
00076       // Would be better to use a macro or maybe even a template parameter
00077       // instead of hard-coding the alignment.  With a template parameter,
00078       // we could override the alignment where optimization warrants or
00079       // target builds towards a particular alignment, e.g., AVX needs
00080       // only 32-byte alignment.
00081       Elem *tmpa = (Elem *)(tmpv+63 - (((long)(tmpv+63))&(63L)));
00082       if (arraySize) CmiMemcpy((void *)tmpa, (void *)array, sizeof(Elem)*arraySize);
00083   
00084       if (allocSize) delete[] varray;
00085       varray = tmpv;
00086       array = tmpa;
00087       allocSize = size;
00088     }
00089 
00090     friend class ResizeArray<Elem>;
00091     friend class SortableResizeArray<Elem>;
00092     friend class SortedArray<Elem>;
00093     friend class UniqueSortedArray<Elem>;
00094     friend class ResizeArrayIter<Elem>;
00095 
00096     inline int size(void) const { return arraySize; }
00097     inline Elem &operator[](int index) const { return array[index]; }
00098 
00099     // DMK - MIC Support - Allow us to see the buffer's size, not just how much of it is used
00100     #if NAMD_MIC != 0
00101       inline int bufSize(void) const { return allocSize; }
00102     #endif
00103 
00104     // Default constructor 
00105     ResizeArrayRaw(void) : 
00106       array((Elem *)0), varray((unsigned char *)0), arraySize(0), allocSize(0) { }
00107 
00108     // Encap a pre-existing array
00109     ResizeArrayRaw( Elem * * const array, int arraySize, int allocSize) {
00110       if (allocSize < arraySize) allocSize = arraySize;
00111       this->allocSize = allocSize;
00112       this->arraySize = arraySize;
00113       varray = (unsigned char *)*array;
00114       this->array = (Elem *)*array;
00115       *array = 0;
00116     }
00117   
00118     // copy data
00119     void copy(const ResizeArrayRaw<Elem> &rar ) {
00120   
00121       // Clean up this array
00122       resize(0);
00123       resizeRaw(rar.size());
00124   
00125       CmiMemcpy((void*)array, (void*)rar.array, sizeof(Elem)*rar.size());
00126       arraySize = rar.size();
00127     }
00128   
00129     // Properly constructs default object on new elements
00130     // Properly destructs on removed elements
00131     // arraySize is properly updated
00132     void resize(int size) {
00133       int i;
00134   
00135       if (size < arraySize) {
00136         for (i=size; i<arraySize; i++) {
00137           array[i].~Elem();
00138         }
00139       } else if (size > arraySize) {
00140         resizeRaw(size);
00141         for (i=arraySize; i<size; i++) {
00142           new ((void *)&array[i]) Elem;
00143         }
00144       }
00145       arraySize = size;
00146     }
00147   
00148     // needed for ResizeArray destructor
00149     void free(void) {
00150       for (int i=0; i < arraySize; i++) {
00151         array[i].~Elem();
00152       }
00153       delete[] varray;
00154     }
00155   
00156     // resize to 0 and free storage
00157     void clear(void) {
00158       free();
00159       array = 0;
00160       varray = 0;
00161       arraySize = 0;
00162       allocSize = 0;
00163     }
00164 
00165     inline int del(int index, int number) {
00166       int i;
00167   
00168       // Fix up number to delete if deletes off end of array
00169       if (index >= arraySize) {
00170         number=0; // for inline sake, don't have multiple returns
00171       } else if (index+number-1 > arraySize) {
00172         number = index-arraySize+1;
00173       }
00174   
00175       // Destruct objects to be deleted
00176       for (i=index; i < index+number; i++) {
00177         array[i].~Elem();
00178       }
00179   
00180       // Shift down
00181       memmove((void *)(array+index),
00182          (void *)(array+index+number),
00183          (arraySize-number-index)*sizeof(Elem));
00184       
00185       // fixup size of array
00186       arraySize -= number;
00187       return(number);
00188     }
00189   
00190     
00191     // Insert element in array
00192     // If index is over the end of array, default
00193     // constructor should be run over blank elements to pad.
00194     inline void ins(const Elem &e, int index) {
00195       // Size array depending if index is in current array or reaches beyond.
00196       if (index < arraySize) {
00197         resizeRaw(arraySize+1);
00198         // Shift up
00199         memmove((void *)(array+index+1),
00200           (void *)(array+index),
00201           (arraySize-index)*sizeof(Elem));
00202       } else {
00203         resizeRaw(index+1);
00204       }
00205       
00206       // Write in new element via assignment - allows any refcounting
00207       // etc. to take place correctly!
00208       new((void *)&array[index]) Elem;
00209       array[index] = e;
00210     
00211       // Take care of fill and setting correct arraySize 
00212       if (index > arraySize) {
00213         for (Elem *tmp = array+arraySize; tmp < array+index; tmp++) {
00214           new ((void *)tmp) Elem;
00215         }
00216         arraySize = index+1;
00217       } else {
00218         arraySize++;
00219       }
00220     }
00221 
00222     inline int find(const Elem &e) const {
00223       for (int i=0; i<arraySize; i++) {
00224         if (array[i] == e) return i;
00225       }
00226       return -1;
00227     }
00228 };      // end template definition
00229 
00230 #endif

Generated on Sat Jan 20 01:17:14 2018 for NAMD by  doxygen 1.4.7