1303275Sdelphij/* 2303275Sdelphij * divsufsort_private.h for libdivsufsort 3303275Sdelphij * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. 4303275Sdelphij * 5303275Sdelphij * Permission is hereby granted, free of charge, to any person 6303275Sdelphij * obtaining a copy of this software and associated documentation 7303275Sdelphij * files (the "Software"), to deal in the Software without 8303275Sdelphij * restriction, including without limitation the rights to use, 9303275Sdelphij * copy, modify, merge, publish, distribute, sublicense, and/or sell 10303275Sdelphij * copies of the Software, and to permit persons to whom the 11303275Sdelphij * Software is furnished to do so, subject to the following 12303275Sdelphij * conditions: 13303275Sdelphij * 14303275Sdelphij * The above copyright notice and this permission notice shall be 15303275Sdelphij * included in all copies or substantial portions of the Software. 16303275Sdelphij * 17303275Sdelphij * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18303275Sdelphij * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 19303275Sdelphij * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20303275Sdelphij * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 21303275Sdelphij * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 22303275Sdelphij * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 23303275Sdelphij * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 24303275Sdelphij * OTHER DEALINGS IN THE SOFTWARE. 25303275Sdelphij */ 26303275Sdelphij 27303275Sdelphij#ifndef _DIVSUFSORT_PRIVATE_H 28303275Sdelphij#define _DIVSUFSORT_PRIVATE_H 1 29303275Sdelphij 30303275Sdelphij#ifdef __cplusplus 31303275Sdelphijextern "C" { 32303275Sdelphij#endif /* __cplusplus */ 33303275Sdelphij 34303275Sdelphij#if HAVE_CONFIG_H 35303275Sdelphij# include "config.h" 36303275Sdelphij#endif 37303275Sdelphij#include <assert.h> 38303275Sdelphij#include <stdio.h> 39303275Sdelphij#if HAVE_STRING_H 40303275Sdelphij# include <string.h> 41303275Sdelphij#endif 42303275Sdelphij#if HAVE_STDLIB_H 43303275Sdelphij# include <stdlib.h> 44303275Sdelphij#endif 45303275Sdelphij#if HAVE_MEMORY_H 46303275Sdelphij# include <memory.h> 47303275Sdelphij#endif 48303275Sdelphij#if HAVE_STDDEF_H 49303275Sdelphij# include <stddef.h> 50303275Sdelphij#endif 51303275Sdelphij#if HAVE_STRINGS_H 52303275Sdelphij# include <strings.h> 53303275Sdelphij#endif 54303275Sdelphij#if HAVE_INTTYPES_H 55303275Sdelphij# include <inttypes.h> 56303275Sdelphij#else 57303275Sdelphij# if HAVE_STDINT_H 58303275Sdelphij# include <stdint.h> 59303275Sdelphij# endif 60303275Sdelphij#endif 61303275Sdelphij#if defined(BUILD_DIVSUFSORT64) 62303275Sdelphij# include "divsufsort64.h" 63303275Sdelphij# ifndef SAIDX_T 64303275Sdelphij# define SAIDX_T 65303275Sdelphij# define saidx_t saidx64_t 66303275Sdelphij# endif /* SAIDX_T */ 67303275Sdelphij# ifndef PRIdSAIDX_T 68303275Sdelphij# define PRIdSAIDX_T PRIdSAIDX64_T 69303275Sdelphij# endif /* PRIdSAIDX_T */ 70303275Sdelphij# define divsufsort divsufsort64 71303275Sdelphij# define divbwt divbwt64 72303275Sdelphij# define divsufsort_version divsufsort64_version 73303275Sdelphij# define bw_transform bw_transform64 74303275Sdelphij# define inverse_bw_transform inverse_bw_transform64 75303275Sdelphij# define sufcheck sufcheck64 76303275Sdelphij# define sa_search sa_search64 77303275Sdelphij# define sa_simplesearch sa_simplesearch64 78303275Sdelphij# define sssort sssort64 79303275Sdelphij# define trsort trsort64 80303275Sdelphij#else 81303275Sdelphij# include "divsufsort.h" 82303275Sdelphij#endif 83303275Sdelphij 84303275Sdelphij 85303275Sdelphij/*- Constants -*/ 86303275Sdelphij#if !defined(UINT8_MAX) 87303275Sdelphij# define UINT8_MAX (255) 88303275Sdelphij#endif /* UINT8_MAX */ 89303275Sdelphij#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) 90303275Sdelphij# undef ALPHABET_SIZE 91303275Sdelphij#endif 92303275Sdelphij#if !defined(ALPHABET_SIZE) 93303275Sdelphij# define ALPHABET_SIZE (UINT8_MAX + 1) 94303275Sdelphij#endif 95303275Sdelphij/* for divsufsort.c */ 96303275Sdelphij#define BUCKET_A_SIZE (ALPHABET_SIZE) 97303275Sdelphij#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE) 98303275Sdelphij/* for sssort.c */ 99303275Sdelphij#if defined(SS_INSERTIONSORT_THRESHOLD) 100303275Sdelphij# if SS_INSERTIONSORT_THRESHOLD < 1 101303275Sdelphij# undef SS_INSERTIONSORT_THRESHOLD 102303275Sdelphij# define SS_INSERTIONSORT_THRESHOLD (1) 103303275Sdelphij# endif 104303275Sdelphij#else 105303275Sdelphij# define SS_INSERTIONSORT_THRESHOLD (8) 106303275Sdelphij#endif 107303275Sdelphij#if defined(SS_BLOCKSIZE) 108303275Sdelphij# if SS_BLOCKSIZE < 0 109303275Sdelphij# undef SS_BLOCKSIZE 110303275Sdelphij# define SS_BLOCKSIZE (0) 111303275Sdelphij# elif 32768 <= SS_BLOCKSIZE 112303275Sdelphij# undef SS_BLOCKSIZE 113303275Sdelphij# define SS_BLOCKSIZE (32767) 114303275Sdelphij# endif 115303275Sdelphij#else 116303275Sdelphij# define SS_BLOCKSIZE (1024) 117303275Sdelphij#endif 118303275Sdelphij/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ 119303275Sdelphij#if SS_BLOCKSIZE == 0 120303275Sdelphij# if defined(BUILD_DIVSUFSORT64) 121303275Sdelphij# define SS_MISORT_STACKSIZE (96) 122303275Sdelphij# else 123303275Sdelphij# define SS_MISORT_STACKSIZE (64) 124303275Sdelphij# endif 125303275Sdelphij#elif SS_BLOCKSIZE <= 4096 126303275Sdelphij# define SS_MISORT_STACKSIZE (16) 127303275Sdelphij#else 128303275Sdelphij# define SS_MISORT_STACKSIZE (24) 129303275Sdelphij#endif 130303275Sdelphij#if defined(BUILD_DIVSUFSORT64) 131303275Sdelphij# define SS_SMERGE_STACKSIZE (64) 132303275Sdelphij#else 133303275Sdelphij# define SS_SMERGE_STACKSIZE (32) 134303275Sdelphij#endif 135303275Sdelphij/* for trsort.c */ 136303275Sdelphij#define TR_INSERTIONSORT_THRESHOLD (8) 137303275Sdelphij#if defined(BUILD_DIVSUFSORT64) 138303275Sdelphij# define TR_STACKSIZE (96) 139303275Sdelphij#else 140303275Sdelphij# define TR_STACKSIZE (64) 141303275Sdelphij#endif 142303275Sdelphij 143303275Sdelphij 144303275Sdelphij/*- Macros -*/ 145303275Sdelphij#ifndef SWAP 146303275Sdelphij# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0) 147303275Sdelphij#endif /* SWAP */ 148303275Sdelphij#ifndef MIN 149303275Sdelphij# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b)) 150303275Sdelphij#endif /* MIN */ 151303275Sdelphij#ifndef MAX 152303275Sdelphij# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b)) 153303275Sdelphij#endif /* MAX */ 154303275Sdelphij#define STACK_PUSH(_a, _b, _c, _d)\ 155303275Sdelphij do {\ 156303275Sdelphij assert(ssize < STACK_SIZE);\ 157303275Sdelphij stack[ssize].a = (_a), stack[ssize].b = (_b),\ 158303275Sdelphij stack[ssize].c = (_c), stack[ssize++].d = (_d);\ 159303275Sdelphij } while(0) 160303275Sdelphij#define STACK_PUSH5(_a, _b, _c, _d, _e)\ 161303275Sdelphij do {\ 162303275Sdelphij assert(ssize < STACK_SIZE);\ 163303275Sdelphij stack[ssize].a = (_a), stack[ssize].b = (_b),\ 164303275Sdelphij stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\ 165303275Sdelphij } while(0) 166303275Sdelphij#define STACK_POP(_a, _b, _c, _d)\ 167303275Sdelphij do {\ 168303275Sdelphij assert(0 <= ssize);\ 169303275Sdelphij if(ssize == 0) { return; }\ 170303275Sdelphij (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ 171303275Sdelphij (_c) = stack[ssize].c, (_d) = stack[ssize].d;\ 172303275Sdelphij } while(0) 173303275Sdelphij#define STACK_POP5(_a, _b, _c, _d, _e)\ 174303275Sdelphij do {\ 175303275Sdelphij assert(0 <= ssize);\ 176303275Sdelphij if(ssize == 0) { return; }\ 177303275Sdelphij (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ 178303275Sdelphij (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\ 179303275Sdelphij } while(0) 180303275Sdelphij/* for divsufsort.c */ 181303275Sdelphij#define BUCKET_A(_c0) bucket_A[(_c0)] 182303275Sdelphij#if ALPHABET_SIZE == 256 183303275Sdelphij#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)]) 184303275Sdelphij#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)]) 185303275Sdelphij#else 186303275Sdelphij#define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)]) 187303275Sdelphij#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)]) 188303275Sdelphij#endif 189303275Sdelphij 190303275Sdelphij 191303275Sdelphij/*- Private Prototypes -*/ 192303275Sdelphij/* sssort.c */ 193303275Sdelphijvoid 194303275Sdelphijsssort(const sauchar_t *Td, const saidx_t *PA, 195303275Sdelphij saidx_t *first, saidx_t *last, 196303275Sdelphij saidx_t *buf, saidx_t bufsize, 197303275Sdelphij saidx_t depth, saidx_t n, saint_t lastsuffix); 198303275Sdelphij/* trsort.c */ 199303275Sdelphijvoid 200303275Sdelphijtrsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth); 201303275Sdelphij 202303275Sdelphij 203303275Sdelphij#ifdef __cplusplus 204303275Sdelphij} /* extern "C" */ 205303275Sdelphij#endif /* __cplusplus */ 206303275Sdelphij 207303275Sdelphij#endif /* _DIVSUFSORT_PRIVATE_H */ 208