/* suftest.c
Copyright N. Jesper Larsson 1999.
Program to test suffix sorting function. Reads a sequence of bytes
from a file and calls suffixsort. This is the program used in the
experiments in "Faster Suffix Sorting" by N. Jesper Larsson
(njlarsson@avadeaux.net) and Kunihiko Sadakane to time the
suffixsort function in the file qsufsort.c.
As per March 2019, this software is released under a dual license. Anyone
who wishes to make use of it may choose either of the conditions 1 or 2
below:
1. This software may be used freely for any purpose. However, when
distributed, the original source must be clearly stated, and, when the
source code is distributed, the copyright notice must be retained and any
alterations in the code must be clearly marked. No warranty is given
regarding the quality of this software.
2. This is free software: you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any
later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
Public License for more details.
The GNU General Public License can be found at
.
CHANGES:
1999-06-14: Fixed preprocessor conditions so that it's possible to have
CHECK==0 and PRINT==2 simultaneously. Added to comment about PRINT==2.
*/
#include
#include
#include
#ifndef CHECK
/* Nonzero CHECK means check that sort is correct. Very slow for repetitive
files.*/
#define CHECK 0
#endif
#ifndef PRINT
/* 0 for no printing. 1 to print suffix numbers in sorted order. 2 to print
first MAXPRINT characters of each suffix in sorted order (makes sense only
if the input is text and COMPACT is 0).*/
#define PRINT 0
#endif
#ifndef MAXPRINT
#define MAXPRINT 10
#endif
#ifndef COMPACT
/* 0 to use alphabet 0...UCHAR_MAX without checking what appears. 1 to limit
the alphabet to the range l...k-1 that actually appears in the input. 2 to
transform the alphabet into 1...k-1 with no gaps and minimum k, preserving
the order.*/
#define COMPACT 1
#endif
#define MIN(a, b) ((a)<=(b) ? (a) : (b))
void suffixsort(int *x, int *p, int n, int k, int l);
int scmp3(unsigned char *p, unsigned char *q, int *l, int maxl)
{
int i;
i = 0;
while (maxl>0 && *p==*q) {
p++; q++; i++;
maxl--;
}
*l = i;
if (maxl>0) return *p-*q;
return q-p;
}
int main(int argc, char *argv[])
{
int c, i, j, *x, *p, *pi;
int n, k, l;
#if COMPACT==2
unsigned char q[UCHAR_MAX+1];
#endif
unsigned char *s = NULL;
char *fnam;
FILE *f;
if (argc!=2) {
fprintf(stderr, "syntax: suftest file\n");
return 1;
}
fnam=argv[1];
if (! (f=fopen(fnam, "rb"))) {
perror(fnam);
return 1;
}
if (fseek(f, 0L, SEEK_END)) {
perror(fnam);
return 1;
}
n=ftell(f);
if (n==0) {
fprintf(stderr, "%s: file empty\n", fnam);
return 0;
}
p=malloc((n+1)*sizeof *p);
x=malloc((n+1)*sizeof *x);
if (! p || ! x) {
fprintf(stderr, "malloc failed\n");
return 1;
}
#if COMPACT==1
l=UCHAR_MAX;
k=1;
for (rewind(f), pi=x; pi=k)
k=c+1;
}
#else
for (rewind(f), pi=x; pi=0)
fprintf(stderr, "i %d p[i] %d p[i+1] %d\n", i, p[i], p[i+1]);
}
fprintf(stderr, "done.\n");
#endif
#if PRINT
for (i=0; i<=n; ++i) {
#if PRINT==1
printf("%d\n", p[i]);
#else
printf("%3d \"", p[i]);
for (j=p[i]; j