/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 2003-2011 AT&T Intellectual Property *
* and is licensed under the *
* Eclipse Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
* *
* Information and Software Systems Research *
* AT&T Research *
* Florham Park NJ *
* *
* Phong Vo <kpv@research.att.com> *
* *
***********************************************************************/
#include "vchdr.h"
/* Counting bucket sort.
** Return the number of distinct bytes. The bckt[] argument returns
** the cumulative counts of all bytes. Thus, bckt[0] is the count
** of byte 0, bckt[1] is the cumulative count of 0 and 1, and so on.
**
** Written by Kiem-Phong Vo.
*/
#if __STD_C
#else
ssize_t n; /* # of indices */
#endif
{
ssize_t i, p, c;
/* count byte frequencies */
if(list) /* sort using secondary predictor */
{ for(p = 0; p < n; ++p)
}
else /* unsorted permutation was the identity */
{ for(p = 0; p < n; ++p)
}
for(p = 0, i = 0; i < 256; ++i) /* starting positions */
{ if((c = bckt[i]) > 0)
distinct += 1;
bckt[i] = p;
p += c;
}
if(list) /* sorting a sublist of indices */
{ for(p = 0; p < n; ++p)
}
else /* sorting all indices */
{ for(p = 0; p < n; ++p)
}
return distinct;
}
#if 0
/* some intermediate versions of Vcodex used this implementation and became
** incompatible with earlier version of Vctable. So this is saved here in case
** we ever need to deal with data compressed with such versions.
*/
#if __STD_C
#else
/* == NULL: sorting 0,1,...n-1 */
ssize_t n; /* # of elements to be sorted */
#endif
{
/* count byte frequencies */
for(p = 0; p < n; ++p)
bckt[c] += 1;
}
/* set starting positions for each bucket */
{ if((i = bckt[c]) <= 0)
continue;
bckt[c] = p; p += i;
}
/* now sort them into place */
for(p = 0; p < n; ++p)
}
return distinct;
}
#endif