divsufsort.c File Reference

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

Include dependency graph for divsufsort.c:

Go to the source code of this file.

Classes
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)   do { t = (_a); (_a) = (_b); (_b) = t; } while(0)
#define	MIN(_a, _b)   (((_a) < (_b)) ? (_a) : (_b))
#define	MAX(_a, _b)   (((_a) > (_b)) ? (_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)   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_SIZE   SS_MISORT_STACKSIZE
#define	STACK_SIZE   SS_SMERGE_STACKSIZE
#define	GETIDX(a)   ((0 <= (a)) ? (a) : (~(a)))
#define	MERGE_CHECK(a, b, c)
#define	STACK_SIZE   TR_STACKSIZE

Typedefs
typedef struct _trbudget_t	trbudget_t

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)

Definition at line 56 of file divsufsort.c.

BUCKET_A

#define BUCKET_A

(

_c0

)

bucket_A[(_c0)]

Definition at line 128 of file divsufsort.c.

BUCKET_A_SIZE

#define BUCKET_A_SIZE   (ALPHABET_SIZE)

Definition at line 58 of file divsufsort.c.

BUCKET_B

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

Definition at line 130 of file divsufsort.c.

BUCKET_B_SIZE

#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)

Definition at line 59 of file divsufsort.c.

BUCKET_BSTAR

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

Definition at line 131 of file divsufsort.c.

GETIDX

#define GETIDX

(

a

)

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

INLINE

#define INLINE   __inline

Definition at line 50 of file divsufsort.c.

MAX

#define MAX	(		_a,
			_b
	)		(((_a) > (_b)) ? (_a) : (_b))

Definition at line 100 of file divsufsort.c.

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
	)		(((_a) < (_b)) ? (_a) : (_b))

Definition at line 97 of file divsufsort.c.

SS_BLOCKSIZE

#define SS_BLOCKSIZE   (1024)

Definition at line 77 of file divsufsort.c.

SS_INSERTIONSORT_THRESHOLD

#define SS_INSERTIONSORT_THRESHOLD   (8)

Definition at line 66 of file divsufsort.c.

SS_MISORT_STACKSIZE

#define SS_MISORT_STACKSIZE   (16)

Definition at line 83 of file divsufsort.c.

SS_SMERGE_STACKSIZE

#define SS_SMERGE_STACKSIZE   (32)

Definition at line 87 of file divsufsort.c.

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 114 of file divsufsort.c.

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 121 of file divsufsort.c.

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)

Definition at line 102 of file divsufsort.c.

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)

Definition at line 108 of file divsufsort.c.

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
	)		do { t = (_a); (_a) = (_b); (_b) = t; } while(0)

Definition at line 94 of file divsufsort.c.

TR_INSERTIONSORT_THRESHOLD

#define TR_INSERTIONSORT_THRESHOLD   (8)

Definition at line 88 of file divsufsort.c.

TR_STACKSIZE

#define TR_STACKSIZE   (64)

Definition at line 89 of file divsufsort.c.

Typedef Documentation

trbudget_t

typedef struct _trbudget_t trbudget_t

Definition at line 1040 of file divsufsort.c.

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.

Definition at line 1876 of file divsufsort.c.

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.

Definition at line 1847 of file divsufsort.c.