00001 //File: $Id$ 00002 // Author: K. John Wu <John.Wu at acm.org> 00003 // Lawrence Berkeley National Laboratory 00004 // Copyright 2000-2011 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(); 00084 void sort(array_t<uint32_t> &ind) const; 00086 void topk(uint32_t k, array_t<uint32_t> &ind) const; 00088 void bottomk(uint32_t k, array_t<uint32_t> &ind) const; 00089 uint32_t find(const array_t<uint32_t>& ind, const T& val) const; 00091 size_t find(const T& val) const; 00093 size_t find_upper(const T& val) const; 00097 void stableSort(array_t<T>& tmp); 00100 void stableSort(array_t<uint32_t>& ind) const; 00103 void stableSort(array_t<uint32_t>& ind, array_t<T>& sorted) const; 00104 static void stableSort(array_t<T>& val, array_t<uint32_t>& ind, 00105 array_t<T>& tmp, array_t<uint32_t>& itmp); 00106 00108 const T& operator[](size_t i) const {return m_begin[i];} 00113 T& operator[](size_t i) {return m_begin[i];}; 00116 void nosharing(); 00118 bool incore() const {return(actual != 0 ? actual->filename() == 0 : false);} 00119 00120 iterator insert(iterator pos, const T& val); 00121 void insert(iterator p, size_t n, const T& val); 00122 void insert(iterator p, const_iterator i, const_iterator j); 00123 00124 // erase one value or a range of values 00125 iterator erase(iterator p); 00126 iterator erase(iterator i, iterator j); 00127 00128 // the IO functions 00129 void read(const char*); 00130 off_t read(const int fdes, const off_t begin, 00131 const off_t end); 00132 void write(const char*) const; 00133 void write(FILE* fptr) const; 00134 00135 // print internal pointer addresses 00136 void printStatus(std::ostream& out) const; 00137 00144 ibis::fileManager::storage* getStorage() {return actual;} 00145 00146 private: 00147 ibis::fileManager::storage *actual; 00148 T* m_begin; 00149 T* m_end; 00150 // ibis::horometer timer; // a timer to track usage 00151 00152 void freeMemory(); 00153 00155 uint32_t partition(array_t<uint32_t>& ind, uint32_t front, 00156 uint32_t back) const; 00158 void isort(array_t<uint32_t>& ind, uint32_t front, uint32_t back) const; 00160 void hsort(array_t<uint32_t>& ind, uint32_t front, uint32_t back) const; 00162 void qsort(array_t<uint32_t>& ind, uint32_t front, uint32_t back, 00163 uint32_t lvl=0) const; 00164 }; 00165 00167 template<class T> 00168 inline void ibis::array_t<T>::clear() { 00169 #if defined(DEBUG) || defined(_DEBUG) 00170 LOGGER(ibis::gVerbose > 10) 00171 << "array_t::clear -- (" << static_cast<const void*>(this) << ", " 00172 << static_cast<const void*>(m_begin) << ") resets m_end from " 00173 << static_cast<const void*>(m_end) << " to " 00174 << static_cast<const void*>(m_begin); 00175 #endif 00176 m_end = m_begin; 00177 } // ibis::array_t<T>::clear 00178 00180 template<class T> 00181 inline void ibis::array_t<T>::swap(array_t<T>& rhs) { 00182 ibis::fileManager::storage *a = rhs.actual; 00183 rhs.actual = actual; 00184 actual = a; 00185 T* b = rhs.m_begin; 00186 rhs.m_begin = m_begin; 00187 m_begin = b; 00188 T* e = rhs.m_end; 00189 rhs.m_end = m_end; 00190 m_end = e; 00191 } // ibis::array_t<T>::swap 00192 00194 template<class T> 00195 inline void ibis::array_t<T>::push_back(const T& elm) { 00196 if (actual == 0) { // allocate storage 00197 actual = new ibis::fileManager::storage(3*sizeof(T)); 00198 actual->beginUse(); 00199 m_begin = (T*)(actual->begin()); 00200 m_end = m_begin + 1; 00201 *m_begin = elm; 00202 } 00203 else if (m_begin != 0 && m_end != 0 && actual->begin() > 0 && 00204 actual->end() > actual->begin() && actual->inUse() <= 1 && 00205 (char*)(m_end+1) <= actual->end()) { // simply add value 00206 *m_end = elm; 00207 ++ m_end; 00208 } 00209 else { // copy-and-swap 00210 const difference_type nexist = (m_end - m_begin); 00211 const size_t newsize = (nexist >= 7 ? nexist : 7) + nexist; 00212 if ((long long) newsize < nexist) { 00213 throw "array_t must have less than 2^31 elements"; 00214 } 00215 00216 array_t<T> tmp(newsize); // allocate new array 00217 tmp.resize(static_cast<size_t>(nexist+1)); 00218 for (difference_type j = 0; j < nexist; ++ j) // copy 00219 tmp.m_begin[j] = m_begin[j]; 00220 tmp.m_begin[nexist] = elm; 00221 swap(tmp); // swap 00222 } 00223 } // ibis::array_t<T>::push_back 00224 00226 template <class T> 00227 inline size_t ibis::array_t<T>::capacity() const { 00228 return (actual != 0 ? (const T*)actual->end() - m_begin : 0); 00229 } // ibis::array_t<T>::capacity 00230 #endif // IBIS_ARRAY_T_H
![]() |