divsufsort.c File Reference

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

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	divbwt (const unsigned char *T, unsigned char *U, int *A, int n)

Macro Definition Documentation

#define ALPHABET_SIZE   (256)

Definition at line 42 of file divsufsort.c.

#define BUCKET_A

(

_c0)

bucket_A[(_c0)]

Definition at line 114 of file divsufsort.c.

#define BUCKET_A_SIZE   (ALPHABET_SIZE)

Definition at line 44 of file divsufsort.c.

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

Definition at line 116 of file divsufsort.c.

#define BUCKET_B_SIZE   (ALPHABET_SIZE * ALPHABET_SIZE)

Definition at line 45 of file divsufsort.c.

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

Definition at line 117 of file divsufsort.c.

#define GETIDX

(

a)

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

#define INLINE   __inline

Definition at line 37 of file divsufsort.c.

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

Definition at line 86 of file divsufsort.c.

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

Definition at line 83 of file divsufsort.c.

#define SS_BLOCKSIZE   (1024)

Definition at line 63 of file divsufsort.c.

#define SS_INSERTIONSORT_THRESHOLD   (8)

Definition at line 52 of file divsufsort.c.

#define SS_MISORT_STACKSIZE   (16)

Definition at line 69 of file divsufsort.c.

#define SS_SMERGE_STACKSIZE   (32)

Definition at line 73 of file divsufsort.c.

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

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

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

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

#define STACK_SIZE   SS_MISORT_STACKSIZE

#define STACK_SIZE   SS_SMERGE_STACKSIZE

#define STACK_SIZE   TR_STACKSIZE

#define SWAP	(		_a,
			_b
	)		do { t = (_a); (_a) = (_b); (_b) = t; } while(0)

Definition at line 80 of file divsufsort.c.

#define TR_INSERTIONSORT_THRESHOLD   (8)

Definition at line 74 of file divsufsort.c.

#define TR_STACKSIZE   (64)

Definition at line 75 of file divsufsort.c.

Typedef Documentation

typedef struct _trbudget_t trbudget_t

Definition at line 1026 of file divsufsort.c.

Function Documentation

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

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.

Returns

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

Definition at line 1750 of file divsufsort.c.

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

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.

Returns

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

Definition at line 1721 of file divsufsort.c.