OLD | NEW |
1 // Copyright 2003, 2004 Colin Percival | 1 // Copyright 2003, 2004 Colin Percival |
2 // All rights reserved | 2 // All rights reserved |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted providing that the following conditions | 5 // modification, are permitted providing that the following conditions |
6 // are met: | 6 // are met: |
7 // 1. Redistributions of source code must retain the above copyright | 7 // 1. Redistributions of source code must retain the above copyright |
8 // notice, this list of conditions and the following disclaimer. | 8 // notice, this list of conditions and the following disclaimer. |
9 // 2. Redistributions in binary form must reproduce the above copyright | 9 // 2. Redistributions in binary form must reproduce the above copyright |
10 // notice, this list of conditions and the following disclaimer in the | 10 // notice, this list of conditions and the following disclaimer in the |
(...skipping 30 matching lines...) Expand all Loading... |
41 // http://www.larsson.dogma.net/qsufsort.c | 41 // http://www.larsson.dogma.net/qsufsort.c |
42 // --Samuel Huang <huangs@chromium.org> | 42 // --Samuel Huang <huangs@chromium.org> |
43 | 43 |
44 // Copyright 2016 The Chromium Authors. All rights reserved. | 44 // Copyright 2016 The Chromium Authors. All rights reserved. |
45 // Use of this source code is governed by a BSD-style license that can be | 45 // Use of this source code is governed by a BSD-style license that can be |
46 // found in the LICENSE file. | 46 // found in the LICENSE file. |
47 | 47 |
48 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ | 48 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |
49 #define COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ | 49 #define COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |
50 | 50 |
51 namespace courgette { | |
52 namespace qsuf { | 51 namespace qsuf { |
53 | 52 |
54 // ------------------------------------------------------------------------ | 53 // ------------------------------------------------------------------------ |
55 // | 54 // |
56 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the | 55 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the |
57 // code formatting and variable names. The changes from the original are: | 56 // code formatting and variable names. The changes from the original are: |
58 // (1) replacing tabs with spaces, | 57 // (1) replacing tabs with spaces, |
59 // (2) indentation and spacing, | 58 // (2) indentation and spacing, |
60 // (3) using 'const', | 59 // (3) using 'const', |
61 // (4) changing the V and I parameters from int* to template <typename T>. | 60 // (4) changing the V and I parameters from int* to template <typename T>. |
62 // (5) optimizing split() and search(); fix styles. | 61 // (5) optimizing split(); fix styles. |
| 62 // (6) moving matchlen() and search() to a separate file. |
63 // | 63 // |
64 // The code appears to be a rewritten version of the suffix array algorithm | 64 // The code appears to be a rewritten version of the suffix array algorithm |
65 // presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko | 65 // presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko |
66 // Sadakane, special cased for bytes. | 66 // Sadakane, special cased for bytes. |
67 | 67 |
68 namespace { | 68 namespace { |
69 | 69 |
70 template <typename T> | 70 template <typename T> |
71 T median3(const T& a, const T& b, const T& c) { | 71 T median3(const T& a, const T& b, const T& c) { |
72 if (a < b) | 72 if (a < b) |
(...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
214 }; | 214 }; |
215 | 215 |
216 for (i = 0; i < oldsize + 1; i++) | 216 for (i = 0; i < oldsize + 1; i++) |
217 I[V[i]] = i; | 217 I[V[i]] = i; |
218 } | 218 } |
219 | 219 |
220 // End of 'verbatim' code. | 220 // End of 'verbatim' code. |
221 // ------------------------------------------------------------------------ | 221 // ------------------------------------------------------------------------ |
222 | 222 |
223 } // namespace qsuf | 223 } // namespace qsuf |
224 } // namespace courgette | |
225 | 224 |
226 #endif // COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ | 225 #endif // COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |
OLD | NEW |