array_t.h
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

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive