00001 //File: $Id$ 00002 // Author: K. John Wu <John.Wu at acm.org> 00003 // Lawrence Berkeley National Laboratory 00004 // Copyright 2000-2012 University of California 00005 #ifndef IBIS_ARRAY_T_H 00006 #define IBIS_ARRAY_T_H 00007 #include "fileManager.h" 00008 #include "horometer.h" 00009 #include <cstddef> // ptrdiff_t 00010 00021 #ifdef __GNUC__ 00022 #pragma interface 00023 #endif 00024 template<class T> class ibis::array_t { 00025 public: 00026 typedef T* iterator; 00027 typedef const T* const_iterator; 00028 typedef T* pointer; 00029 typedef const T* const_pointer; 00030 typedef T& reference; 00031 typedef const T& const_reference; 00032 typedef T value_type; 00033 typedef size_t size_type; 00034 typedef std::ptrdiff_t difference_type; 00035 00036 // constructor and destructor 00037 ~array_t<T>() {freeMemory();} 00038 array_t<T>(); 00039 explicit array_t<T>(size_t n); // donot convert integer to array_t 00040 array_t<T>(size_t n, const T& val); 00041 array_t<T>(const array_t<T>& rhs); 00042 array_t<T>(const std::vector<T>& rhs); 00043 array_t<T>(const array_t<T>& rhs, const size_t begin, 00044 const size_t end=0); 00045 explicit array_t<T>(ibis::fileManager::storage* rhs); 00046 array_t<T>(ibis::fileManager::storage* rhs, 00047 const size_t start, const size_t end); 00048 array_t<T>(const int fdes, const off_t begin, const off_t end); 00049 array_t<T>(const char *fn, const off_t begin, const off_t end); 00050 array_t<T>(const char *fn, const int fdes, 00051 const off_t begin, const off_t end); 00052 array_t<T>(T* addr, size_t nelm); 00053 00054 array_t<T>& operator=(const array_t<T>& rhs); 00055 void copy(const array_t<T>& rhs); 00056 void deepCopy(const array_t<T>& rhs); 00057 00058 // functions for the iterators 00059 T* begin() {return m_begin;}; 00060 T* end() {return m_end;}; 00061 T& front() {return *m_begin;}; 00062 T& back() {return m_end[-1];}; 00063 const T* begin() const {return m_begin;}; 00064 const T* end() const {return m_end;}; 00065 const T& front() const {return *m_begin;}; 00066 const T& back() const {return m_end[-1];}; 00067 00068 bool empty() const {return (m_begin == 0 || m_begin >= m_end);}; 00069 size_t size() const { 00070 return (m_begin > 0 && m_end > m_begin ? m_end - m_begin : 0); 00071 }; 00072 inline void clear(); 00073 00074 void pop_back() {--m_end;}; 00075 void resize(size_t n); 00076 void reserve(size_t n); 00077 void truncate(size_t keep, size_t start); 00078 size_t capacity() const; 00079 inline void swap(array_t<T>& rhs); 00080 inline void push_back(const T& elm); 00081 00082 void deduplicate(); 00083 void sort(array_t<uint32_t> &ind) const; 00084 void topk(uint32_t k, array_t<uint32_t> &ind) const; 00085 void bottomk(uint32_t k, array_t<uint32_t> &ind) const; 00086 uint32_t find(const array_t<uint32_t>& ind, const T& val) const; 00087 size_t find(const T& val) const; 00088 size_t find_upper(const T& val) const; 00089 void stableSort(array_t<T>& tmp); 00090 void stableSort(array_t<uint32_t>& ind) const; 00091 void stableSort(array_t<uint32_t>& ind, array_t<T>& sorted) const; 00092 static void stableSort(array_t<T>& val, array_t<uint32_t>& ind, 00093 array_t<T>& tmp, array_t<uint32_t>& itmp); 00094 00095 bool isSorted() const; 00096 bool isSorted(const array_t<uint32_t>&) const; 00097 bool equal_to(const array_t<T>&) const; 00098 00100 const T& operator[](size_t i) const {return m_begin[i];} 00105 T& operator[](size_t i) {return m_begin[i];}; 00106 void nosharing(); 00108 bool incore() const {return(actual != 0 ? actual->filename() == 0 : false);} 00109 00110 iterator insert(iterator pos, const T& val); 00111 void insert(iterator p, size_t n, const T& val); 00112 void insert(iterator p, const_iterator i, const_iterator j); 00113 00114 // erase one value or a range of values 00115 iterator erase(iterator p); 00116 iterator erase(iterator i, iterator j); 00117 00118 // the IO functions 00119 void read(const char*); 00120 off_t read(const char*, const off_t, const off_t); 00121 off_t read(const int, const off_t, const off_t); 00122 int write(const char*) const; 00123 int write(FILE* fptr) const; 00124 00125 // print internal pointer addresses 00126 void printStatus(std::ostream& out) const; 00127 00134 ibis::fileManager::storage* getStorage() {return actual;} 00135 00136 private: 00137 ibis::fileManager::storage *actual; 00138 T* m_begin; 00139 T* m_end; 00140 // ibis::horometer timer; // a timer to track usage 00141 00142 void freeMemory(); 00143 00145 uint32_t partition(array_t<uint32_t>& ind, uint32_t front, 00146 uint32_t back) const; 00148 void isort(array_t<uint32_t>& ind, uint32_t front, uint32_t back) const; 00150 void hsort(array_t<uint32_t>& ind, uint32_t front, uint32_t back) const; 00152 void qsort(array_t<uint32_t>& ind, uint32_t front, uint32_t back, 00153 uint32_t lvl=0) const; 00154 }; // ibis::array_t 00155 00157 template<class T> 00158 inline void ibis::array_t<T>::clear() { 00159 #if defined(DEBUG) || defined(_DEBUG) 00160 LOGGER(ibis::gVerbose > 10) 00161 << "array_t::clear -- (" << static_cast<const void*>(this) << ", " 00162 << static_cast<const void*>(m_begin) << ") resets m_end from " 00163 << static_cast<const void*>(m_end) << " to " 00164 << static_cast<const void*>(m_begin); 00165 #endif 00166 m_end = m_begin; 00167 } // ibis::array_t<T>::clear 00168 00170 template<class T> 00171 inline void ibis::array_t<T>::swap(array_t<T>& rhs) { 00172 ibis::fileManager::storage *a = rhs.actual; 00173 rhs.actual = actual; 00174 actual = a; 00175 T* b = rhs.m_begin; 00176 rhs.m_begin = m_begin; 00177 m_begin = b; 00178 T* e = rhs.m_end; 00179 rhs.m_end = m_end; 00180 m_end = e; 00181 } // ibis::array_t<T>::swap 00182 00184 template<class T> 00185 inline void ibis::array_t<T>::push_back(const T& elm) { 00186 if (actual == 0) { // allocate storage 00187 actual = new ibis::fileManager::storage(3*sizeof(T)); 00188 actual->beginUse(); 00189 m_begin = (T*)(actual->begin()); 00190 m_end = m_begin + 1; 00191 *m_begin = elm; 00192 } 00193 else if (m_begin != 0 && m_end != 0 && actual->begin() > 0 && 00194 actual->end() > actual->begin() && actual->inUse() <= 1 && 00195 (char*)(m_end+1) <= actual->end()) { // simply add value 00196 *m_end = elm; 00197 ++ m_end; 00198 } 00199 else { // copy-and-swap 00200 const difference_type nexist = (m_end - m_begin); 00201 const size_t newsize = (nexist >= 7 ? nexist : 7) + nexist; 00202 if ((long long) newsize < nexist) { 00203 throw "array_t must have less than 2^31 elements"; 00204 } 00205 00206 array_t<T> tmp(newsize); // allocate new array 00207 tmp.resize(static_cast<size_t>(nexist+1)); 00208 for (difference_type j = 0; j < nexist; ++ j) // copy 00209 tmp.m_begin[j] = m_begin[j]; 00210 tmp.m_begin[nexist] = elm; 00211 swap(tmp); // swap 00212 } 00213 } // ibis::array_t<T>::push_back 00214 00216 template <class T> 00217 inline size_t ibis::array_t<T>::capacity() const { 00218 return (actual != 0 ? (const T*)actual->end() - m_begin : 0); 00219 } // ibis::array_t<T>::capacity 00220 #endif // IBIS_ARRAY_T_H
![]() |