Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(31)

Side by Side Diff: courgette/third_party/divsufsort/divsufsort.cc

Issue 2156223002: [Courgette] Add third party-library: libdivsufsort. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Update checklicenses.py. Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
2 //
3 // For the terms under which this work may be distributed, please see
4 // the adjoining file "LICENSE".
5 //
6 // ChangeLog:
7 // 2016-07-22 - Initial commit and adaption to use PagedArray.
8 // --Samuel Huang <huangs@chromium.org>
9
10 #include "courgette/third_party/divsufsort/divsufsort_private.h"
11
12 #include <stdlib.h>
13
14 #define BUCKET_A_SIZE (ALPHABET_SIZE)
15 #define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
16
17 #define BUCKET_A(_c0) bucket_A[(_c0)]
18 #if ALPHABET_SIZE == 256
19 #define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
20 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
21 #else
22 #define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)])
23 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)])
24 #endif
25
26 namespace divsuf {
27
28 /*- Private Functions -*/
29
30 namespace {
31
32 /* Sorts suffixes of type B*. */
33 saidx_t
34 sort_typeBstar(const sauchar_t *T, saidx_it SA,
35 saidx_t *bucket_A, saidx_t *bucket_B,
36 saidx_t n) {
37 saidx_it PAb, ISAb, buf;
38 saidx_t i, j, k, t, m, bufsize;
39 saint_t c0, c1;
40
41 /* Initialize bucket arrays. */
42 for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; }
43 for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; }
44
45 /* Count the number of occurrences of the first one or two characters of each
46 type A, B and B* suffix. Moreover, store the beginning position of all
47 type B* suffixes into the array SA. */
48 for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {
49 /* type A suffix. */
50 do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1));
51 if(0 <= i) {
52 /* type B* suffix. */
53 ++BUCKET_BSTAR(c0, c1);
54 SA[--m] = i;
55 /* type B suffix. */
56 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
57 ++BUCKET_B(c0, c1);
58 }
59 }
60 }
61 m = n - m;
62 /*
63 note:
64 A type B* suffix is lexicographically smaller than a type B suffix that
65 begins with the same first two characters.
66 */
67
68 /* Calculate the index of start/end point of each bucket. */
69 for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
70 t = i + BUCKET_A(c0);
71 BUCKET_A(c0) = i + j; /* start point */
72 i = t + BUCKET_B(c0, c0);
73 for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
74 j += BUCKET_BSTAR(c0, c1);
75 BUCKET_BSTAR(c0, c1) = j; /* end point */
76 i += BUCKET_B(c0, c1);
77 }
78 }
79
80 if(0 < m) {
81 /* Sort the type B* suffixes by their first two characters. */
82 PAb = SA + n - m; ISAb = SA + m;
83 for(i = m - 2; 0 <= i; --i) {
84 t = PAb[i], c0 = T[t], c1 = T[t + 1];
85 SA[--BUCKET_BSTAR(c0, c1)] = i;
86 }
87 t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
88 SA[--BUCKET_BSTAR(c0, c1)] = m - 1;
89
90 /* Sort the type B* substrings using sssort. */
91 buf = SA + m, bufsize = n - (2 * m);
92 for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
93 for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
94 i = BUCKET_BSTAR(c0, c1);
95 if(1 < (j - i)) {
96 sssort(T, PAb, SA + i, SA + j,
97 buf, bufsize, 2, n, *(SA + i) == (m - 1));
98 }
99 }
100 }
101
102 /* Compute ranks of type B* substrings. */
103 for(i = m - 1; 0 <= i; --i) {
104 if(0 <= SA[i]) {
105 j = i;
106 do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i]));
107 SA[i + 1] = i - j;
108 if(i <= 0) { break; }
109 }
110 j = i;
111 do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0);
112 ISAb[SA[i]] = j;
113 }
114
115 /* Construct the inverse suffix array of type B* suffixes using trsort. */
116 trsort(ISAb, SA, m, 1);
117
118 /* Set the sorted order of tyoe B* suffixes. */
119 for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
120 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { }
121 if(0 <= i) {
122 t = i;
123 for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { }
124 SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
125 }
126 }
127
128 /* Calculate the index of start/end point of each bucket. */
129 BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */
130 for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
131 i = BUCKET_A(c0 + 1) - 1;
132 for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
133 t = i - BUCKET_B(c0, c1);
134 BUCKET_B(c0, c1) = i; /* end point */
135
136 /* Move all type B* suffixes to the correct position. */
137 for(i = t, j = BUCKET_BSTAR(c0, c1);
138 j <= k;
139 --i, --k) { SA[i] = SA[k]; }
140 }
141 BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */
142 BUCKET_B(c0, c0) = i; /* end point */
143 }
144 }
145
146 return m;
147 }
148
149 /* Constructs the suffix array by using the sorted order of type B* suffixes. */
150 void
151 construct_SA(const sauchar_t *T, saidx_it SA,
152 saidx_t *bucket_A, saidx_t *bucket_B,
153 saidx_t n, saidx_t m) {
154 saidx_it i, j, k;
155 saidx_t s;
156 saint_t c0, c1, c2;
157
158 if(0 < m) {
159 /* Construct the sorted order of type B suffixes by using
160 the sorted order of type B* suffixes. */
161 for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
162 /* Scan the suffix array from right to left. */
163 for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
164 j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
165 i <= j;
166 --j) {
167 if(0 < (s = *j)) {
168 assert(T[s] == c1);
169 assert(((s + 1) < n) && (T[s] <= T[s + 1]));
170 assert(T[s - 1] <= T[s]);
171 *j = ~s;
172 c0 = T[--s];
173 if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
174 if(c0 != c2) {
175 if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
176 k = SA + BUCKET_B(c2 = c0, c1);
177 }
178 assert(k < j);
179 *k-- = s;
180 } else {
181 assert(((s == 0) && (T[s] == c1)) || (s < 0));
182 *j = ~s;
183 }
184 }
185 }
186 }
187
188 /* Construct the suffix array by using
189 the sorted order of type B suffixes. */
190 k = SA + BUCKET_A(c2 = T[n - 1]);
191 *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
192 /* Scan the suffix array from left to right. */
193 for(i = SA, j = SA + n; i < j; ++i) {
194 if(0 < (s = *i)) {
195 assert(T[s - 1] >= T[s]);
196 c0 = T[--s];
197 if((s == 0) || (T[s - 1] < c0)) { s = ~s; }
198 if(c0 != c2) {
199 BUCKET_A(c2) = k - SA;
200 k = SA + BUCKET_A(c2 = c0);
201 }
202 assert(i < k);
203 *k++ = s;
204 } else {
205 assert(s < 0);
206 *i = ~s;
207 }
208 }
209 }
210
211 } // namespace
212
213 /*---------------------------------------------------------------------------*/
214
215 /*- Function -*/
216
217 saint_t
218 divsufsort(const sauchar_t *T, saidx_it SA, saidx_t n) {
219 saidx_t *bucket_A, *bucket_B;
220 saidx_t m;
221 saint_t err = 0;
222
223 /* Check arguments. */
224 if((T == NULL) || (SA == NULL) || (n < 0)) { return -1; }
225 else if(n == 0) { return 0; }
226 else if(n == 1) { SA[0] = 0; return 0; }
227 else if(n == 2) { m = (T[0] < T[1]); SA[m ^ 1] = 0, SA[m] = 1; return 0; }
228
229 bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t));
230 bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t));
231
232 /* Suffixsort. */
233 if((bucket_A != NULL) && (bucket_B != NULL)) {
234 m = sort_typeBstar(T, SA, bucket_A, bucket_B, n);
235 construct_SA(T, SA, bucket_A, bucket_B, n, m);
236 } else {
237 err = -2;
238 }
239
240 free(bucket_B);
241 free(bucket_A);
242
243 return err;
244 }
245
246 saint_t divsufsort_include_empty(const sauchar_t *T, saidx_it SA, saidx_t n) {
247 SA[0] = n; // Manually add the empty string suffix.
248 return divsufsort(T, SA + 1, n);
249 }
250
251 } // namespace divsuf
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698