enum
{
BUCK = ~(~0u>>1), /* high bit */
MAXI = ~0u>>1, /* biggest int */
};
typedef int Elem;
static void qsort2(Elem*, Elem*, int n);
static int ssortit(int a[], int p[], int s[], int q[], int n, int h, int *pe, int nbuck);
static void lift(int si, int q[], int i);
int sharedlen(int i, int j, int s[], int q[]);
int
ssort(int a[], int s[], int n)
{
int i, l;
int c, cc, ncc, lab, cum, nbuck;
int k;
int *p = 0;
int result = 0;
int *q = 0;
int *al;
int *pl;
# define finish(r) if(1){result=r; goto out;}else
for(k=0,i=0; i<n; i++)
if(a[i] > k)
k = a[i]; /* max element */
k++;
if(k>n)
finish(2);
nbuck = 0;
p = malloc(n*sizeof(int));
if(p == 0)
finish(1);
lab = 0; /* (2) create p and label a */
cum = 0;
i = 0;
for(c = 0; c < k; c++){
for(cc = pl[c]; cc != -1; cc = ncc){
ncc = al[cc];
al[cc] = lab;
cum++;
p[i++] = cc;
}
if(lab + 1 == cum) {
i--;
} else {
p[i-1] |= BUCK;
nbuck++;
}
if(s) {
s[lab] = 0;
lift(0, q, lab);
}
lab = cum;
}
ssortit(a, p, s, q, n, 1, p+i, nbuck);
memcpy(a, p, n*sizeof(int));
out:
free(p);
free(q);
return result;
}
/*
* calculate the suffix array for the bytes in buf,
* terminated by a unique end marker less than any character in buf
* returns the index of the identity permutation,
* and -1 if there was an error.
*/
int
ssortbyte(uchar buf[], int p[], int s[], int n)
{
int *a, *q, buckets[256*256];
int i, last, lastc, cum, c, cc, ncc, lab, id, nbuck;
a = malloc((n+1)*sizeof(int));
if(a == nil)
return -1;
memset(buckets, -1, sizeof(buckets));
c = buf[n-1] << 8;
last = c;
for(i = n - 2; i >= 0; i--){
c = (buf[i] << 8) | (c >> 8);
a[i] = buckets[c];
buckets[c] = i;
}
/*
* end of string comes before anything else
*/
a[n] = 0;
if(s) {
s[0] = 0;
lift(0, q, 0);
}
lab = 1;
cum = 1;
i = 0;
lastc = 1; /* won't match c & 0xff00 for any c */
nbuck = 0;
for(c = 0; c < 256*256; c++) {
/*
* last character is followed by unique end of string
*/
if(c == last) {
a[n-1] = lab;
if(s) {
s[lab] = 0;
lift(0, q, lab);
}
cum++;
lab++;
lastc = c & 0xff00;
}
id = ssortit(a, p, s, q, n+1, 2, p+i, nbuck);
free(a);
free(q);
return id;
}
/*
* can get an interval for the shared lengths from [h,3h) by recording h
* rather than h + sharedlen(..) when relabelling. if so, no calls to lift are needed.
*/
static int
ssortit(int a[], int p[], int shared[], int q[], int n, int h, int *pe, int nbuck)
{
int *s, *ss, *packing, *sorting;
int v, sv, vv, packed, lab, t, i;
for(; h < n && p < pe; h=2*h) {
packing = p;
nbuck = 0;
/*
* reconstuct the permutation matrix
* return index of the entire string
*/
v = a[0];
for(i = 0; i < n; i++)
p[a[i]] = i;
return v;
}
/* Propagate a new entry s[i], with value si, into q[]. */
static void
lift(int si, int q[], int i)
{
for(i >>= 1; q[i] > si; i &= ~-i) /* squash the low 1-bit */
q[i] = si;
}
/*
* Find in s[] the minimum value over the interval i<=k<=j, using
* tree q[] to do logarithmic, rather than linear search
*/
int
sharedlen(int i, int j, int s[], int q[])
{
int k, v;
int min = MAXI;
int max = 0;
if(i > j) { /* swap i & j */
i ^= j;
j ^= i;
i ^= j;
}
i++;
while(i <= j && min > max) {
k = i & -i;
if(i & 1)
v = s[i];
else
v = q[i>>1];
if(i+k > j+1) {
if(v > max)
max = v;
if(s[i] < min)
min = s[i];
i++;
} else {
if(v < min)
min = v;
i += k;
}
}
return min;
}
/*
* qsort specialized for sorting permutations based on successors
*/
static void
vecswap2(Elem *a, Elem *b, int n)
{
while (n-- > 0) {
Elem t = *a;
*a++ = *b;
*b++ = t;
}
}
#define swap2(a, b) { t = *(a); *(a) = *(b); *(b) = t; }
#define ptr2char(i, asucc) (asucc[*(i)])