1/* 2 * divsufsort_private.h for libdivsufsort 3 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person 6 * obtaining a copy of this software and associated documentation 7 * files (the "Software"), to deal in the Software without 8 * restriction, including without limitation the rights to use, 9 * copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following 12 * conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 24 * OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 27#ifndef _DIVSUFSORT_PRIVATE_H 28#define _DIVSUFSORT_PRIVATE_H 1 29 30#ifdef __cplusplus 31extern "C" { 32#endif /* __cplusplus */ 33 34#if HAVE_CONFIG_H 35# include "config.h" 36#endif 37#include <assert.h> 38#include <stdio.h> 39#if HAVE_STRING_H 40# include <string.h> 41#endif 42#if HAVE_STDLIB_H 43# include <stdlib.h> 44#endif 45#if HAVE_MEMORY_H 46# include <memory.h> 47#endif 48#if HAVE_STDDEF_H 49# include <stddef.h> 50#endif 51#if HAVE_STRINGS_H 52# include <strings.h> 53#endif 54#if HAVE_INTTYPES_H 55# include <inttypes.h> 56#else 57# if HAVE_STDINT_H 58# include <stdint.h> 59# endif 60#endif 61#if defined(BUILD_DIVSUFSORT64) 62# include "divsufsort64.h" 63# ifndef SAIDX_T 64# define SAIDX_T 65# define saidx_t saidx64_t 66# endif /* SAIDX_T */ 67# ifndef PRIdSAIDX_T 68# define PRIdSAIDX_T PRIdSAIDX64_T 69# endif /* PRIdSAIDX_T */ 70# define divsufsort divsufsort64 71# define divbwt divbwt64 72# define divsufsort_version divsufsort64_version 73# define bw_transform bw_transform64 74# define inverse_bw_transform inverse_bw_transform64 75# define sufcheck sufcheck64 76# define sa_search sa_search64 77# define sa_simplesearch sa_simplesearch64 78# define sssort sssort64 79# define trsort trsort64 80#else 81# include "divsufsort.h" 82#endif 83 84 85/*- Constants -*/ 86#if !defined(UINT8_MAX) 87# define UINT8_MAX (255) 88#endif /* UINT8_MAX */ 89#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) 90# undef ALPHABET_SIZE 91#endif 92#if !defined(ALPHABET_SIZE) 93# define ALPHABET_SIZE (UINT8_MAX + 1) 94#endif 95/* for divsufsort.c */ 96#define BUCKET_A_SIZE (ALPHABET_SIZE) 97#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE) 98/* for sssort.c */ 99#if defined(SS_INSERTIONSORT_THRESHOLD) 100# if SS_INSERTIONSORT_THRESHOLD < 1 101# undef SS_INSERTIONSORT_THRESHOLD 102# define SS_INSERTIONSORT_THRESHOLD (1) 103# endif 104#else 105# define SS_INSERTIONSORT_THRESHOLD (8) 106#endif 107#if defined(SS_BLOCKSIZE) 108# if SS_BLOCKSIZE < 0 109# undef SS_BLOCKSIZE 110# define SS_BLOCKSIZE (0) 111# elif 32768 <= SS_BLOCKSIZE 112# undef SS_BLOCKSIZE 113# define SS_BLOCKSIZE (32767) 114# endif 115#else 116# define SS_BLOCKSIZE (1024) 117#endif 118/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ 119#if SS_BLOCKSIZE == 0 120# if defined(BUILD_DIVSUFSORT64) 121# define SS_MISORT_STACKSIZE (96) 122# else 123# define SS_MISORT_STACKSIZE (64) 124# endif 125#elif SS_BLOCKSIZE <= 4096 126# define SS_MISORT_STACKSIZE (16) 127#else 128# define SS_MISORT_STACKSIZE (24) 129#endif 130#if defined(BUILD_DIVSUFSORT64) 131# define SS_SMERGE_STACKSIZE (64) 132#else 133# define SS_SMERGE_STACKSIZE (32) 134#endif 135/* for trsort.c */ 136#define TR_INSERTIONSORT_THRESHOLD (8) 137#if defined(BUILD_DIVSUFSORT64) 138# define TR_STACKSIZE (96) 139#else 140# define TR_STACKSIZE (64) 141#endif 142 143 144/*- Macros -*/ 145#ifndef SWAP 146# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0) 147#endif /* SWAP */ 148#ifndef MIN 149# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b)) 150#endif /* MIN */ 151#ifndef MAX 152# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b)) 153#endif /* MAX */ 154#define STACK_PUSH(_a, _b, _c, _d)\ 155 do {\ 156 assert(ssize < STACK_SIZE);\ 157 stack[ssize].a = (_a), stack[ssize].b = (_b),\ 158 stack[ssize].c = (_c), stack[ssize++].d = (_d);\ 159 } while(0) 160#define STACK_PUSH5(_a, _b, _c, _d, _e)\ 161 do {\ 162 assert(ssize < STACK_SIZE);\ 163 stack[ssize].a = (_a), stack[ssize].b = (_b),\ 164 stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\ 165 } while(0) 166#define STACK_POP(_a, _b, _c, _d)\ 167 do {\ 168 assert(0 <= ssize);\ 169 if(ssize == 0) { return; }\ 170 (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ 171 (_c) = stack[ssize].c, (_d) = stack[ssize].d;\ 172 } while(0) 173#define STACK_POP5(_a, _b, _c, _d, _e)\ 174 do {\ 175 assert(0 <= ssize);\ 176 if(ssize == 0) { return; }\ 177 (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ 178 (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\ 179 } while(0) 180/* for divsufsort.c */ 181#define BUCKET_A(_c0) bucket_A[(_c0)] 182#if ALPHABET_SIZE == 256 183#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)]) 184#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)]) 185#else 186#define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)]) 187#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)]) 188#endif 189 190 191/*- Private Prototypes -*/ 192/* sssort.c */ 193void 194sssort(const sauchar_t *Td, const saidx_t *PA, 195 saidx_t *first, saidx_t *last, 196 saidx_t *buf, saidx_t bufsize, 197 saidx_t depth, saidx_t n, saint_t lastsuffix); 198/* trsort.c */ 199void 200trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth); 201 202 203#ifdef __cplusplus 204} /* extern "C" */ 205#endif /* __cplusplus */ 206 207#endif /* _DIVSUFSORT_PRIVATE_H */ 208