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

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