wincfg: Add swapfile.sys
[wimlib] / src / divsufsort / divsufsort.h
1 /*
2  * divsufsort.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_H
28 #define _DIVSUFSORT_H 1
29
30 #ifdef __cplusplus
31 extern "C" {
32 #endif /* __cplusplus */
33
34 #include <inttypes.h>
35
36 #ifndef DIVSUFSORT_API
37 # ifdef DIVSUFSORT_BUILD_DLL
38 #  define DIVSUFSORT_API 
39 # else
40 #  define DIVSUFSORT_API 
41 # endif
42 #endif
43
44 /*- Datatypes -*/
45 #ifndef SAUCHAR_T
46 #define SAUCHAR_T
47 typedef uint8_t sauchar_t;
48 #endif /* SAUCHAR_T */
49 #ifndef SAINT_T
50 #define SAINT_T
51 typedef int32_t saint_t;
52 #endif /* SAINT_T */
53 #ifndef SAIDX_T
54 #define SAIDX_T
55 typedef int32_t saidx_t;
56 #endif /* SAIDX_T */
57 #ifndef PRIdSAINT_T
58 #define PRIdSAINT_T PRId32
59 #endif /* PRIdSAINT_T */
60 #ifndef PRIdSAIDX_T
61 #define PRIdSAIDX_T PRId32
62 #endif /* PRIdSAIDX_T */
63
64
65 /*- Prototypes -*/
66
67 /**
68  * Constructs the suffix array of a given string.
69  * @param T[0..n-1] The input string.
70  * @param SA[0..n-1] The output array of suffixes.
71  * @param n The length of the given string.
72  * @param bucket_A Temporary space (size >= 256)
73  * @param bucket_B Temporary space (size >= 256 * 256)
74  *
75  * @return 0
76  */
77 DIVSUFSORT_API
78 saint_t
79 divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n,
80      saidx_t *bucket_A, saidx_t *bucket_B);
81
82 #if 0
83
84 /**
85  * Constructs the burrows-wheeler transformed string of a given string.
86  * @param T[0..n-1] The input string.
87  * @param U[0..n-1] The output string. (can be T)
88  * @param A[0..n-1] The temporary array. (can be NULL)
89  * @param n The length of the given string.
90  * @return The primary index if no error occurred, -1 or -2 otherwise.
91  */
92 DIVSUFSORT_API
93 saidx_t
94 divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);
95
96 /**
97  * Returns the version of the divsufsort library.
98  * @return The version number string.
99  */
100 DIVSUFSORT_API
101 const char *
102 divsufsort_version(void);
103
104
105 /**
106  * Constructs the burrows-wheeler transformed string of a given string and suffix array.
107  * @param T[0..n-1] The input string.
108  * @param U[0..n-1] The output string. (can be T)
109  * @param SA[0..n-1] The suffix array. (can be NULL)
110  * @param n The length of the given string.
111  * @param idx The output primary index.
112  * @return 0 if no error occurred, -1 or -2 otherwise.
113  */
114 DIVSUFSORT_API
115 saint_t
116 bw_transform(const sauchar_t *T, sauchar_t *U,
117              saidx_t *SA /* can NULL */,
118              saidx_t n, saidx_t *idx);
119
120 /**
121  * Inverse BW-transforms a given BWTed string.
122  * @param T[0..n-1] The input string.
123  * @param U[0..n-1] The output string. (can be T)
124  * @param A[0..n-1] The temporary array. (can be NULL)
125  * @param n The length of the given string.
126  * @param idx The primary index.
127  * @return 0 if no error occurred, -1 or -2 otherwise.
128  */
129 DIVSUFSORT_API
130 saint_t
131 inverse_bw_transform(const sauchar_t *T, sauchar_t *U,
132                      saidx_t *A /* can NULL */,
133                      saidx_t n, saidx_t idx);
134
135 /**
136  * Checks the correctness of a given suffix array.
137  * @param T[0..n-1] The input string.
138  * @param SA[0..n-1] The input suffix array.
139  * @param n The length of the given string.
140  * @param verbose The verbose mode.
141  * @return 0 if no error occurred.
142  */
143 DIVSUFSORT_API
144 saint_t
145 sufcheck(const sauchar_t *T, const saidx_t *SA, saidx_t n, saint_t verbose);
146
147 /**
148  * Search for the pattern P in the string T.
149  * @param T[0..Tsize-1] The input string.
150  * @param Tsize The length of the given string.
151  * @param P[0..Psize-1] The input pattern string.
152  * @param Psize The length of the given pattern string.
153  * @param SA[0..SAsize-1] The input suffix array.
154  * @param SAsize The length of the given suffix array.
155  * @param idx The output index.
156  * @return The count of matches if no error occurred, -1 otherwise.
157  */
158 DIVSUFSORT_API
159 saidx_t
160 sa_search(const sauchar_t *T, saidx_t Tsize,
161           const sauchar_t *P, saidx_t Psize,
162           const saidx_t *SA, saidx_t SAsize,
163           saidx_t *left);
164
165 /**
166  * Search for the character c in the string T.
167  * @param T[0..Tsize-1] The input string.
168  * @param Tsize The length of the given string.
169  * @param SA[0..SAsize-1] The input suffix array.
170  * @param SAsize The length of the given suffix array.
171  * @param c The input character.
172  * @param idx The output index.
173  * @return The count of matches if no error occurred, -1 otherwise.
174  */
175 DIVSUFSORT_API
176 saidx_t
177 sa_simplesearch(const sauchar_t *T, saidx_t Tsize,
178                 const saidx_t *SA, saidx_t SAsize,
179                 saint_t c, saidx_t *left);
180 #endif
181
182
183 #ifdef __cplusplus
184 } /* extern "C" */
185 #endif /* __cplusplus */
186
187 #endif /* _DIVSUFSORT_H */