[openbeos] Re: Performance question - BList vs STL list
- From: Zenja Solaja <solaja@xxxxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Sun, 23 Oct 2005 19:29:26 +1000
Well, I've stumbled onto a bug in BList (SortItems). Examine the following
code:
/* FILE: list.cpp
PROJECT: Experiment
AUTHOR: Zenja Solaja
CREATION DATE: 23 November 2005
DESCRIPTION: BList vs STL list comparison
The lists are of integer type
*/
#include <StorageKit.h> // BList
#include <list> // STL list
#include "stdio.h"
/* Local Data */
const int size = 10;
int sample_data[size] = {10,9,8,7,6,5,4,3,2,1};
/* FUNCTION: int_sort
ARGUMENTS: a, b
RETURN: -1 if a < b
0 if a = b
1 if a > b
DESCRIPTION: Basic sort function
*/
int int_sort(const void *a, const void *b)
{
int *c = (int *) a;
int *d = (int *) d;
if (*c < *d)
return -1;
else if (*c > *d)
return 1;
else
return 0;
}
/* FUNCTION: print_BList
ARGUMENTS: list
RETURN: none
DESCRIPTION: Print all items of a list
*/
void print_BList(BList alist)
{
for (int i=0; i < alist.CountItems(); i++)
{
int *p = (int *)alist.ItemAt(i);
printf("%d,", *p);
}
printf("\n");
}
/* FUNCTION: print_BList
ARGUMENTS: list
RETURN: none
DESCRIPTION: Print all items of a list
*/
void print_STL_list(list <int *> alist)
{
list<int *>::iterator p = alist.begin();
while (p != alist.end())
{
printf("%d,", *(*p));
p++;
}
printf("\n");
}
/* FUNCTION: main
ARGUMENTS:
RETURN: exit code
DESCRIPTION: "If it compiles, ship it..."
*/
int main()
{
int i;
// BList test
BList b_list;
for (i=0; i < size; i++)
b_list.AddItem(&sample_data[i]);
printf("BList before sort:\n");
print_BList(b_list);
// Sort
b_list.SortItems(int_sort);
printf("BList after sort:\n");
print_BList(b_list);
// STL test
list <int *> stl_list;
for (i=0; i < size; i++)
stl_list.push_back(&sample_data[i]);
printf("\nSTL list before sort:\n");
print_STL_list(stl_list);
// Sort
stl_list.sort(int_sort);
printf("STL list after sort:\n");
print_STL_list(stl_list);
return 0;
}
And it's output:
/boot/home/test/List>BeApp
BList before sort:
10,9,8,7,6,5,4,3,2,1,
BList after sort:
10,9,8,7,6,5,4,3,2,1,
STL list before sort:
10,9,8,7,6,5,4,3,2,1,
STL list after sort:
1,2,3,4,5,6,7,8,9,10,
/boot/home/test/List>
It seems that the BList SortItems() function is b0rken (Zeta R1.1). I've
spent all afternoon chasing this bug, and always puzzled why the sorting
function never sorted when using BList. I've switched the algorithm to STL,
and it works. For the life of me, I cannot see anything wrong at my end.
Anyone got any ideas?
Other related posts:
