SDSL 3.0.1
Succinct Data Structure Library
divsufsort.hpp File Reference
#include <algorithm>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

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 = _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 (const uint8_t *T, const saidx_t *p1, const saidx_t *p2, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_insertionsort (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_fixdown (const uint8_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void sdsl::ss_heapsort (const uint8_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * sdsl::ss_median3 (const uint8_t *Td, const saidx_t *PA, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * sdsl::ss_median5 (const uint8_t *Td, const saidx_t *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 (const uint8_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
saidx_t * sdsl::ss_partition (const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mintrosort (const uint8_t *T, const saidx_t *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 (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mergeforward (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_mergebackward (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void sdsl::ss_swapmerge (const uint8_t *T, const saidx_t *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 (const uint8_t *T, const saidx_t *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 (const saidx_t *ISAd, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
void sdsl::tr_fixdown (const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void sdsl::tr_heapsort (const saidx_t *ISAd, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * sdsl::tr_median3 (const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * sdsl::tr_median5 (const saidx_t *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 (const saidx_t *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 (const saidx_t *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, const saidx_t *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, const saidx_t *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, const saidx_t *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 (const uint8_t *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n)
 
template<typename saidx_t >
void sdsl::construct_SA (const uint8_t *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 (const uint8_t *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 (const uint8_t *T, saidx_t *SA, saidx_t n)
 
int32_t sdsl::divsufsort64 (const uint8_t *T, int64_t *SA, int64_t n)
 
template<typename saidx_t >
int sdsl::_compare (const uint8_t *T, saidx_t Tsize, const uint8_t *P, saidx_t Psize, saidx_t suf, saidx_t *match)
 

Macro Definition Documentation

◆ ALPHABET_SIZE

#define ALPHABET_SIZE   (256)

Definition at line 46 of file divsufsort.hpp.

◆ BUCKET_A

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

Definition at line 71 of file divsufsort.hpp.

◆ BUCKET_A_SIZE

#define BUCKET_A_SIZE   (ALPHABET_SIZE)

Definition at line 47 of file divsufsort.hpp.

◆ BUCKET_B

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

Definition at line 73 of file divsufsort.hpp.

◆ BUCKET_B_SIZE

#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)

Definition at line 48 of file divsufsort.hpp.

◆ BUCKET_BSTAR

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

Definition at line 74 of file divsufsort.hpp.

◆ GETIDX

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

◆ MERGE_CHECK

#define MERGE_CHECK (   a,
  b,
 
)
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)
int32_t ss_compare(const uint8_t *T, const saidx_t *p1, const saidx_t *p2, saidx_t depth)
Definition: divsufsort.hpp:193

◆ SS_BLOCKSIZE

#define SS_BLOCKSIZE   (1024)

Definition at line 50 of file divsufsort.hpp.

◆ SS_INSERTIONSORT_THRESHOLD

#define SS_INSERTIONSORT_THRESHOLD   (8)

Definition at line 49 of file divsufsort.hpp.

◆ SS_MISORT_STACKSIZE

#define SS_MISORT_STACKSIZE   (16)

Definition at line 51 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 89 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 95 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 80 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 84 of file divsufsort.hpp.

◆ TR_INSERTIONSORT_THRESHOLD

#define TR_INSERTIONSORT_THRESHOLD   (8)

Definition at line 52 of file divsufsort.hpp.

◆ UINT8_MAX

#define UINT8_MAX   (255)

Definition at line 43 of file divsufsort.hpp.