divsufsort.c File Reference

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "divsufsort.h"

Data Structures
struct	_trbudget_t

Macros
#define	INLINE   __inline
#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	SS_SMERGE_STACKSIZE   (32)
#define	TR_INSERTIONSORT_THRESHOLD   (8)
#define	TR_STACKSIZE   (64)
#define	SWAP(_a, _b)
#define	MIN(_a, _b)
#define	MAX(_a, _b)
#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	BUCKET_A(_c0)
#define	BUCKET_B(_c0, _c1)
#define	BUCKET_BSTAR(_c0, _c1)
#define	STACK_SIZE   SS_MISORT_STACKSIZE
#define	STACK_SIZE   SS_SMERGE_STACKSIZE
#define	GETIDX(a)
#define	MERGE_CHECK(a, b, c)
#define	STACK_SIZE   TR_STACKSIZE

Functions
int	divsufsort (const unsigned char *T, int *SA, int n, int openMP)
int	divbwt (const unsigned char *T, unsigned char *U, int *A, int n, unsigned char *num_indexes, int *indexes, int openMP)

Macro Definition Documentation

ALPHABET_SIZE

#define ALPHABET_SIZE   (256)

BUCKET_A

#define BUCKET_A

(

_c0

)

Value:

bucket_A[(_c0)]

BUCKET_A_SIZE

#define BUCKET_A_SIZE   (ALPHABET_SIZE)

BUCKET_B

#define BUCKET_B	(		_c0,
			_c1 )

Value:

(bucket_B[((_c1) << 8) | (_c0)])

BUCKET_B_SIZE

#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)

BUCKET_BSTAR

#define BUCKET_BSTAR	(		_c0,
			_c1 )

Value:

(bucket_B[((_c0) << 8) | (_c1)])

GETIDX

#define GETIDX

(

a

)

Value:

((0 <= (a)) ? (a) : (~(a)))

INLINE

#define INLINE   __inline

MAX

#define MAX	(		_a,
			_b )

Value:

(((_a) > (_b)) ? (_a) : (_b))

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)

MIN

#define MIN	(		_a,
			_b )

Value:

(((_a) < (_b)) ? (_a) : (_b))

SS_BLOCKSIZE

#define SS_BLOCKSIZE   (1024)

SS_INSERTIONSORT_THRESHOLD

#define SS_INSERTIONSORT_THRESHOLD   (8)

SS_MISORT_STACKSIZE

#define SS_MISORT_STACKSIZE   (16)

SS_SMERGE_STACKSIZE

#define SS_SMERGE_STACKSIZE   (32)

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)

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)

STACK_PUSH

#define STACK_PUSH	(		_a,
			_b,
			_c,
			_d )

Value:

  do {\
    assert(ssize < STACK_SIZE);\
    stack[ssize].a = (_a), stack[ssize].b = (_b),\
    stack[ssize].c = (_c), stack[ssize++].d = (_d);\
  } while(0)

STACK_PUSH5

#define STACK_PUSH5	(		_a,
			_b,
			_c,
			_d,
			_e )

Value:

  do {\
    assert(ssize < STACK_SIZE);\
    stack[ssize].a = (_a), stack[ssize].b = (_b),\
    stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\
  } while(0)

STACK_SIZE [1/3]

#define STACK_SIZE   SS_MISORT_STACKSIZE

STACK_SIZE [2/3]

#define STACK_SIZE   SS_SMERGE_STACKSIZE

STACK_SIZE [3/3]

#define STACK_SIZE   TR_STACKSIZE

SWAP

#define SWAP	(		_a,
			_b )

Value:

do { t = (_a); (_a) = (_b); (_b) = t; } while(0)

TR_INSERTIONSORT_THRESHOLD

#define TR_INSERTIONSORT_THRESHOLD   (8)

TR_STACKSIZE

#define TR_STACKSIZE   (64)

Function Documentation

divbwt()

int divbwt	(	const unsigned char *	T,
		unsigned char *	U,
		int *	A,
		int	n,
		unsigned char *	num_indexes,
		int *	indexes,
		int	openMP )

Constructs the burrows-wheeler transformed string of a given string.

Parameters

T	[0..n-1] The input string.
U	[0..n-1] The output string. (can be T)
A	[0..n-1] The temporary array. (can be NULL)
n	The length of the given string.
num_indexes	The length of secondary indexes array. (can be NULL)
indexes	The secondary indexes array. (can be NULL)
openMP	enables OpenMP optimization.

Returns

The primary index if no error occurred, -1 or -2 otherwise.

divsufsort()

int divsufsort	(	const unsigned char *	T,
		int *	SA,
		int	n,
		int	openMP )

Constructs the suffix array of a given string.

Parameters

T	[0..n-1] The input string.
SA	[0..n-1] The output array of suffixes.
n	The length of the given string.
openMP	enables OpenMP optimization.

Returns

0 if no error occurred, -1 or -2 otherwise.