wimlib.net Git - wimlib/blob - include/wimlib/divsufsort.h

   1 /*
   2  * divsufsort.h for libdivsufsort-lite
   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 /*- Prototypes -*/
  31
  32 /**
  33  * Constructs the suffix array of a given string.
  34  * @param T[0..n-1] The input string.
  35  * @param SA[0..n-1] The output array of suffixes.
  36  * @param n The length of the given string.
  37  * @param bucket_A Temporary array with 256 entries
  38  * @param bucket_B Temporary array with 65536 entries
  39  */
  40 extern void
  41 divsufsort(const unsigned char *T, int *SA, int n,
  42            int *bucket_A, int *bucket_B);
  43
  44 #define DIVSUFSORT_TMP1_SIZE (256 * sizeof(saidx_t))       /* bucket_A  */
  45 #define DIVSUFSORT_TMP2_SIZE (256 * 256 * sizeof(saidx_t)) /* bucket_B  */
  46
  47 typedef int saidx_t;
  48
  49 #endif /* _DIVSUFSORT_H */