# sysinstall - index_sort

Michal Botka michal.botka at seznam.cz
Tue Dec 25 09:02:39 PST 2007

```Hello,
FTP server. After then I tried install some packages by sysinstall, but
reading package data from index was extremely slow. It took more then 6
minutes on my computer (Pentium II 350MHz, 128MB RAM).

I downloaded sysinstall source, in file index.c, on line 418 there is
following code:

/* Use a disgustingly simplistic bubble sort to put our lists in order */
void
index_sort(PkgNodePtr top)
{
PkgNodePtr p, q;

/* Sort everything at the top level */
for (p = top->kids; p; p = p->next) {
for (q = top->kids; q; q = q->next) {
if (q->next && strcmp(q->name, q->next->name) > 0)
swap_nodes(q, q->next);
}
}

/* Now sub-sort everything n levels down */
for (p = top->kids; p; p = p->next) {
if (p->kids)
index_sort(p);
}
}

There is about 15000 packages in index, so it's clear why it was so
slow. I implemented quick sort algorithm and after then it took only
about 6 seconds. My code (new function index_list_qsort and modified
function index_sort):

/* Quick sort algorithm */
void
index_list_qsort(PkgNodePtr first, PkgNodePtr stop)
{
// empty or one-item list is already sorted
if (first == stop || first->next == stop)
return;

// quick sort
PkgNodePtr i, p;
char* pivotName = first->name;
int size1 = 0;
int size2 = 0;
for (p=first, i=p->next; i!=stop; i=i->next) {
if (strcmp(i->name, pivotName)<0) {
p = p->next;
swap_nodes(p,i);
size1++;
} else {
size1++;
}
}
swap_nodes(first,p);

// we handle the shorter part before the longer
// recursion depth never exceeds logarithm of the total list length
if (size1 <= size2) {
index_list_qsort(first,p);
index_list_qsort(p->next,stop);
} else {
index_list_qsort(p->next,stop);
index_list_qsort(first,p);
}
}

/* Use a quick sort to put our lists in order */
void
index_sort(PkgNodePtr top)
{
PkgNodePtr p, q;

/* Sort everything at the top level */
index_list_qsort(top->kids, NULL);

/* Now sub-sort everything n levels down */
for (p = top->kids; p; p = p->next) {
if (p->kids)
index_sort(p);
}
}

I'm just a newbie and know nothing about FreeBSD, but I will be glad if