An example of code copying (IvanHoe) ?
Posted: Thu Jan 27, 2011 3:19 am
So in the RobboBase compression code of IvanHoe, there's a comment at one point:
Now compare those two files. It seems like the RobboBase version has managed to rewrite much of it to avoid a lot of the pointer arithmetic, and they have no need of the "transform" operation with an initial bucketsort (presumably the data is already sufficiently pre-processed), but other than that, there appears to be a large commonality of code. Whether or not it is "copying" is a different matter.
Here is an example (from the main functions of each):Similarly, compare MainSorter to sort_split, PivotSelectionValue to choose_pivot, SelectionSorter to select_sort_split, and SamePacket to update_group.
The Larsson-Sadakane algorithm for computing suffix trees seems to be indicated. This is included in the "Robbo_suffix.c" file. Looking at Larsson's homepage, I find http://www.larsson.dogma.net/qsufsort.c as the code coming out of their paper.Suffix_fare (bufI, indici, pro); /* larsson plus sadakane */
Now compare those two files. It seems like the RobboBase version has managed to rewrite much of it to avoid a lot of the pointer arithmetic, and they have no need of the "transform" operation with an initial bucketsort (presumably the data is already sufficiently pre-processed), but other than that, there appears to be a large commonality of code. Whether or not it is "copying" is a different matter.
Here is an example (from the main functions of each):
Code: Select all
while (*I>=-n) {
pi=I; /* pi is first position of group.*/
sl=0; /* sl is negated length of sorted groups.*/
do {
if ((s=*pi)<0) {
pi-=s; /* skip over sorted group.*/
sl+=s; /* add negated length to sl.*/
} else {
if (sl) {
*(pi+sl)=sl; /* combine sorted groups before pi.*/
sl=0;
}
pk=I+V[s]+1; /* pk-1 is last position of unsorted group.*/
sort_split(pi, pk-pi);
pi=pk; /* next group.*/
}
} while (pi<=I+n);
if (sl) /* if the array ends with a sorted group.*/
*(pi+sl)=sl; /* combine sorted groups at end of I.*/
h=2*h; /* double sorted-depth.*/
}Code: Select all
while (IDX[0] > -N)
{
w = 0;
sort_run = 0;
while (w < N)
{
ind = IDX[w];
if (ind < 0)
{
w += -ind;
sort_run += -ind;
}
else
{
if (sort_run)
{
IDX[w - sort_run] = -sort_run; /* negate for packet */
sort_run = 0;
}
MainSorter (IDX, AUX, N, h, w, AUX[ind]);
w = AUX[ind] + 1;
}
}
if (sort_run)
IDX[w - sort_run] = -sort_run;
h <<= 1; /* double */
}
