NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Methods | Public Members | Static Public Members | List of all members
nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T > Struct Template Reference

Detailed description

template< uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
struct nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >

This class represents a packed paged text and rank-dictionary supporting parallel bulk insertions.

Template Parameters
SYMBOL_SIZE_Tthe size of the symbols, in bits
BIG_ENDIAN_Tthe endianness with which the packed symbols are stored within a word: true = the first symbols are stored in the most significant bits, false = the first symbols are stored in the least signficant bits

Definition at line 60 of file paged_text.h.

#include <paged_text.h>

Public Types

typedef uint64 word_type
 
typedef PackedStream< const
word_type *, uint8,
SYMBOL_SIZE_T, BIG_ENDIAN_T > 		const_packed_page_type
 
typedef PackedStream
< word_type *, uint8,
SYMBOL_SIZE_T, BIG_ENDIAN_T > 		packed_page_type
 

Public Methods

 PagedText (const uint32 page_size=512 *1024, const uint32 segment_size=128 *1024 *1024, const uint32 occ_intv=128)
 occurrence intervals, in symbols More...
 
 ~PagedText ()
 
uint32 page_count () const
 
uint64 size () const
 
void grow ()
 
word_type * alloc_page ()
 
void release_page (word_type *page)
 
const word_type * get_page (const uint32 i) const
 
uint32 get_page_size (const uint32 i) const
 
uint64 get_page_offset (const uint32 i) const
 
const uint32 * get_occ_page (const uint32 i) const
 
uint32 find_page (const uint64 i) const
 
uint8 operator[] (const uint64 i) const
 
uint64 rank (const uint64 i, const uint8 c) const
 
uint64 rank (const uint32 page_idx, const uint64 i, const uint8 c) const
 
void reserve_pages (const uint32 n_pages)
 
void reserve_free_pages (const uint32 n_pages)
 
void reserve (const uint64 n)
 
uint64 needed_host_memory (const uint64 n) const
 
uint64 needed_device_memory (const uint64 n) const
 
void resize (const uint64 n, const uint8 *c=NULL)
 
void insert (const uint32 n, const uint64 *g, const uint8 *c)
 
const uint64 * symbol_frequencies () const
 
uint64 symbol_frequency (const uint8 c) const
 
void defrag ()
 

Public Members

uint32 m_page_size
 page size, in words More...
 
uint32 m_segment_size
 segment size, in words More...
 
uint32 m_occ_intv
 occurrence interval, in symbols More...
 
uint32 m_occ_intv_w
 occurrence interval, in words More...
 
uint32 m_occ_intv_log
 occurrence interval's logarithm, in symbols More...
 
uint32 m_page_count
 total number of allocated pages More...
 
nvbio::vector< host_tag,
word_type * > 		m_segments
 
nvbio::vector< host_tag,
word_type * > 		m_pages
 
nvbio::vector< host_tag,
word_type * > 		m_new_pages
 
nvbio::vector< host_tag, uint64 > m_offsets
 
nvbio::vector< host_tag, uint64 > m_new_offsets
 
nvbio::vector< host_tag, uint64 > m_counters
 
nvbio::vector< host_tag, uint64 > m_new_counters
 
nvbio::vector< host_tag, uint32 > m_buckets
 
std::vector< word_type * > m_pool
 
uint32 m_pool_size
 
omp_lock_t m_lock
 
uint32 m_count_table [256]
 

Static Public Members

static const uint32 SYMBOL_SIZE = SYMBOL_SIZE_T
 
static const uint32 SYMBOL_COUNT = 1u << SYMBOL_SIZE
 
static const uint32 WORD_SIZE = (8u*sizeof(word_type))
 
static const uint32 SYMBOLS_PER_WORD = WORD_SIZE / SYMBOL_SIZE
 
static const uint32 BIG_ENDIAN = BIG_ENDIAN_T
 
static const uint32 LOG_BUCKET_SIZE = 20u
 
static const uint32 BUCKET_SIZE = 1u << LOG_BUCKET_SIZE
 

Member Typedef Documentation

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
typedef PackedStream<const word_type*,uint8,SYMBOL_SIZE_T,BIG_ENDIAN_T> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::const_packed_page_type

Definition at line 63 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
typedef PackedStream< word_type*,uint8,SYMBOL_SIZE_T,BIG_ENDIAN_T> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::packed_page_type

Definition at line 64 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
typedef uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::word_type

Definition at line 62 of file paged_text.h.

Constructor & Destructor Documentation

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::PagedText ( const uint32  page_size = 512 * 1024,
const uint32  segment_size = 128 * 1024 * 1024,
const uint32  occ_intv = 128 
)

occurrence intervals, in symbols

constructor

Parameters
page_sizepage size, in bytes
segment_sizesegment size, in bytes

Definition at line 269 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::~PagedText ( )

destructor

Definition at line 289 of file paged_text_inl.h.

Member Function Documentation

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::word_type * nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::alloc_page ( )

alloc a new page

Definition at line 334 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::defrag ( )
inline

defragment the pages

Definition at line 1159 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::find_page ( const uint64  i) const
inline

find the page containing the i-th entry

Definition at line 1274 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32* nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::get_occ_page ( const uint32  i) const
inline

return the i-th occurrence table page

Definition at line 120 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const word_type* nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::get_page ( const uint32  i) const
inline

return the i-th page

Definition at line 108 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::get_page_offset ( const uint32  i) const
inline

return the size of the i-th page

Definition at line 116 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::get_page_size ( const uint32  i) const
inline

return the size of the i-th page

Definition at line 112 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::grow ( )

alloc new pages

Definition at line 298 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::insert ( const uint32  n,
const uint64 *  g,
const uint8 *  c 
)
inline

perform a batch of parallel insertions

Definition at line 933 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::needed_device_memory ( const uint64  n) const
inline

needed device memory

Definition at line 156 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::needed_host_memory ( const uint64  n) const

needed host memory

Definition at line 482 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint8 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::operator[] ( const uint64  i) const

indexing operator - return the i-th symbol

Definition at line 376 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::page_count ( ) const
inline

return the current page count

Definition at line 88 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::rank ( const uint64  i,
const uint8  c 
) const

compute the rank of c in [0,i]

Definition at line 392 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::rank ( const uint32  page_idx,
const uint64  i,
const uint8  c 
) const

compute the rank of c in [0,i]

Definition at line 409 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::release_page ( word_type *  page)

release a page

Definition at line 357 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::reserve ( const uint64  n)

reserve

Definition at line 474 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::reserve_free_pages ( const uint32  n_pages)

reserve free pages

Definition at line 463 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::reserve_pages ( const uint32  n_pages)

reserve

Definition at line 445 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
void nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::resize ( const uint64  n,
const uint8 *  c = NULL 
)

resize and optionally copy a given vector

Definition at line 496 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::size ( void  ) const
inline

return the current size

Definition at line 92 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint64 * nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::symbol_frequencies ( ) const
inline

global symbol frequencies

Definition at line 1266 of file paged_text_inl.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint64 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::symbol_frequency ( const uint8  c) const
inline

global symbol frequency

Definition at line 172 of file paged_text.h.

Member Data Documentation

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::BIG_ENDIAN = BIG_ENDIAN_T
static

Definition at line 70 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::BUCKET_SIZE = 1u << LOG_BUCKET_SIZE
static

Definition at line 73 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::LOG_BUCKET_SIZE = 20u
static

Definition at line 72 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,uint32> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_buckets

Definition at line 191 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_count_table[256]

Definition at line 195 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,uint64> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_counters

Definition at line 189 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
omp_lock_t nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_lock

Definition at line 194 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,uint64> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_new_counters

Definition at line 190 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,uint64> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_new_offsets

Definition at line 188 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,word_type*> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_new_pages

Definition at line 186 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_occ_intv

occurrence interval, in symbols

Definition at line 180 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_occ_intv_log

occurrence interval's logarithm, in symbols

Definition at line 182 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_occ_intv_w

occurrence interval, in words

Definition at line 181 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,uint64> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_offsets

Definition at line 187 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_page_count

total number of allocated pages

Definition at line 183 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_page_size

page size, in words

Definition at line 178 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,word_type*> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_pages

Definition at line 185 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
std::vector<word_type*> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_pool

Definition at line 192 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_pool_size

Definition at line 193 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_segment_size

segment size, in words

Definition at line 179 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
nvbio::vector<host_tag,word_type*> nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::m_segments

Definition at line 184 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::SYMBOL_COUNT = 1u << SYMBOL_SIZE
static

Definition at line 67 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::SYMBOL_SIZE = SYMBOL_SIZE_T
static

Definition at line 66 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::SYMBOLS_PER_WORD = WORD_SIZE / SYMBOL_SIZE
static

Definition at line 69 of file paged_text.h.

template<uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T>
const uint32 nvbio::PagedText< SYMBOL_SIZE_T, BIG_ENDIAN_T >::WORD_SIZE = (8u*sizeof(word_type))
static

Definition at line 68 of file paged_text.h.

The documentation for this struct was generated from the following files:
Generated on Wed Feb 25 2015 08:33:49 for NVBIO by   doxygen 1.8.4