SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
divsufsort.hpp File Reference
#include <algorithm>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <utility>

Go to the source code of this file.

Classes

struct  sdsl::libdivsufsort_config< int32_t >
 
struct  sdsl::libdivsufsort_config< int64_t >
 
struct  sdsl::_trbudget_t< saidx_t >
 

Namespaces

namespace  sdsl
 Namespace for the succinct data structure library.
 

Macros

#define UINT8_MAX   (255)
 
#define ALPHABET_SIZE   (256)
 
#define BUCKET_A_SIZE   (ALPHABET_SIZE)
 
#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)
 
#define SS_INSERTIONSORT_THRESHOLD   (8)
 
#define SS_BLOCKSIZE   (1024)
 
#define SS_MISORT_STACKSIZE   (16)
 
#define TR_INSERTIONSORT_THRESHOLD   (8)
 
#define BUCKET_A(_c0)   bucket_A[(_c0)]
 
#define BUCKET_B(_c0, _c1)   (bucket_B[((_c1) << 8) | (_c0)])
 
#define BUCKET_BSTAR(_c0, _c1)   (bucket_B[((_c0) << 8) | (_c1)])
 
#define STACK_PUSH(_a, _b, _c, _d)
 
#define STACK_PUSH5(_a, _b, _c, _d, _e)
 
#define STACK_POP(_a, _b, _c, _d)
 
#define STACK_POP5(_a, _b, _c, _d, _e)
 
#define GETIDX(a)   ((0 <= (a)) ? (a) : (~(a)))
 
#define MERGE_CHECK(a, b, c)
 

Typedefs

template<typename saidx_t >
using sdsl::trbudget_t = struct _trbudget_t<saidx_t>
 

Functions

int32_t sdsl::ss_ilg (int32_t n)
 
int32_t sdsl::ss_ilg (int64_t n)
 
template<typename saidx_t >
saidx_t sdsl::ss_isqrt (saidx_t x)
 
template<typename saidx_t >
int32_t sdsl::ss_compare (uint8_t const *T, saidx_t const *p1, saidx_t const *p2, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_insertionsort (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_fixdown (uint8_t const *Td, saidx_t const *PA, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void sdsl::ss_heapsort (uint8_t const *Td, saidx_t const *PA, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * sdsl::ss_median3 (uint8_t const *Td, saidx_t const *PA, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * sdsl::ss_median5 (uint8_t const *Td, saidx_t const *PA, saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5)
 
template<typename saidx_t >
saidx_t * sdsl::ss_pivot (uint8_t const *Td, saidx_t const *PA, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
saidx_t * sdsl::ss_partition (saidx_t const *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mintrosort (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_blockswap (saidx_t *a, saidx_t *b, saidx_t n)
 
template<typename saidx_t >
void sdsl::ss_rotate (saidx_t *first, saidx_t *middle, saidx_t *last)
 
template<typename saidx_t >
void sdsl::ss_inplacemerge (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mergeforward (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mergebackward (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_swapmerge (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth)
 
template<typename saidx_t >
void sdsl::sssort (uint8_t const *T, saidx_t const *PA, saidx_t *first, saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth, saidx_t n, int32_t lastsuffix)
 
int32_t sdsl::tr_ilg (int32_t n)
 
int32_t sdsl::tr_ilg (int64_t n)
 
template<typename saidx_t >
void sdsl::tr_insertionsort (saidx_t const *ISAd, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
void sdsl::tr_fixdown (saidx_t const *ISAd, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void sdsl::tr_heapsort (saidx_t const *ISAd, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * sdsl::tr_median3 (saidx_t const *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * sdsl::tr_median5 (saidx_t const *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5)
 
template<typename saidx_t >
saidx_t * sdsl::tr_pivot (saidx_t const *ISAd, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
void sdsl::trbudget_init (trbudget_t< saidx_t > *budget, saidx_t chance, saidx_t incval)
 
template<typename saidx_t >
int32_t sdsl::trbudget_check (trbudget_t< saidx_t > *budget, saidx_t size)
 
template<typename saidx_t >
void sdsl::tr_partition (saidx_t const *ISAd, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t **pa, saidx_t **pb, saidx_t v)
 
template<typename saidx_t >
void sdsl::tr_copy (saidx_t *ISA, saidx_t const *SA, saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::tr_partialcopy (saidx_t *ISA, saidx_t const *SA, saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::tr_introsort (saidx_t *ISA, saidx_t const *ISAd, saidx_t *SA, saidx_t *first, saidx_t *last, trbudget_t< saidx_t > *budget)
 
template<typename saidx_t >
void sdsl::trsort (saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth)
 
template<typename saidx_t >
saidx_t sdsl::sort_typeBstar (uint8_t const *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n)
 
template<typename saidx_t >
void sdsl::construct_SA (uint8_t const *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n, saidx_t m)
 
template<typename saidx_t >
saidx_t sdsl::construct_BWT (uint8_t const *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n, saidx_t m)
 
template<typename saidx_t >
int32_t sdsl::divsufsort (uint8_t const *T, saidx_t *SA, saidx_t n)
 
int32_t sdsl::divsufsort64 (uint8_t const *T, int64_t *SA, int64_t n)
 
template<typename saidx_t >
int sdsl::_compare (uint8_t const *T, saidx_t Tsize, uint8_t const *P, saidx_t Psize, saidx_t suf, saidx_t *match)
 

Macro Definition Documentation

◆ ALPHABET_SIZE

#define ALPHABET_SIZE   (256)

Definition at line 48 of file divsufsort.hpp.

◆ BUCKET_A

#define BUCKET_A ( _c0)    bucket_A[(_c0)]

Definition at line 73 of file divsufsort.hpp.

◆ BUCKET_A_SIZE

#define BUCKET_A_SIZE   (ALPHABET_SIZE)

Definition at line 49 of file divsufsort.hpp.

◆ BUCKET_B

#define BUCKET_B ( _c0,
_c1 )   (bucket_B[((_c1) << 8) | (_c0)])

Definition at line 75 of file divsufsort.hpp.

◆ BUCKET_B_SIZE

#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)

Definition at line 50 of file divsufsort.hpp.

◆ BUCKET_BSTAR

#define BUCKET_BSTAR ( _c0,
_c1 )   (bucket_B[((_c0) << 8) | (_c1)])

Definition at line 76 of file divsufsort.hpp.

◆ GETIDX

#define GETIDX ( a)    ((0 <= (a)) ? (a) : (~(a)))

◆ MERGE_CHECK

#define MERGE_CHECK ( a,
b,
c )
Value:
do \
{ \
if (((c)&1) || (((c)&2) && (ss_compare(T, PA + GETIDX(*((a)-1)), PA + *(a), depth) == 0))) \
{ \
*(a) = ~*(a); \
} \
if (((c)&4) && ((ss_compare(T, PA + GETIDX(*((b)-1)), PA + *(b), depth) == 0))) \
{ \
*(b) = ~*(b); \
} \
} \
while (0)
#define GETIDX(a)

◆ SS_BLOCKSIZE

#define SS_BLOCKSIZE   (1024)

Definition at line 52 of file divsufsort.hpp.

◆ SS_INSERTIONSORT_THRESHOLD

#define SS_INSERTIONSORT_THRESHOLD   (8)

Definition at line 51 of file divsufsort.hpp.

◆ SS_MISORT_STACKSIZE

#define SS_MISORT_STACKSIZE   (16)

Definition at line 53 of file divsufsort.hpp.

◆ STACK_POP

#define STACK_POP ( _a,
_b,
_c,
_d )
Value:
do \
{ \
assert(0 <= ssize); \
if (ssize == 0) \
{ \
return; \
} \
(_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, (_d) = stack[ssize].d; \
} \
while (0)

Definition at line 95 of file divsufsort.hpp.

◆ STACK_POP5

#define STACK_POP5 ( _a,
_b,
_c,
_d,
_e )
Value:
do \
{ \
assert(0 <= ssize); \
if (ssize == 0) \
{ \
return; \
} \
(_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, (_d) = stack[ssize].d, \
(_e) = stack[ssize].e; \
} \
while (0)

Definition at line 106 of file divsufsort.hpp.

◆ STACK_PUSH

#define STACK_PUSH ( _a,
_b,
_c,
_d )
Value:
do \
{ \
stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c), stack[ssize++].d = (_d); \
} \
while (0)

Definition at line 82 of file divsufsort.hpp.

◆ STACK_PUSH5

#define STACK_PUSH5 ( _a,
_b,
_c,
_d,
_e )
Value:
do \
{ \
stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c), stack[ssize].d = (_d), \
stack[ssize++].e = (_e); \
} \
while (0)

Definition at line 88 of file divsufsort.hpp.

◆ TR_INSERTIONSORT_THRESHOLD

#define TR_INSERTIONSORT_THRESHOLD   (8)

Definition at line 54 of file divsufsort.hpp.

◆ UINT8_MAX

#define UINT8_MAX   (255)

Definition at line 45 of file divsufsort.hpp.