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 31 extern "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 */ 193 void 194 sssort(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 */ 199 void 200 trsort(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