wimlib.net Git - wimlib/blob - divsufsort_private.h

   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 */