Thread: bsearch problem

Here's what I'm trying to do. I have a char pointer that contains a pagefile size of records in it that I've read from disk. This file is a binary file. From this I am trying to bsearch the pointer.

So, in essence each record in the file is 50 bytes long, with a pageFile being read in at a time.

my bsearch is as follows, where sid is the id that I'm searching on and dest is the char pointer with 50 * pageSize bytes of data:

bsearch(&sid, dest, pageSize, 50, comparator);

this is my comparator function:

Code:

unsigned int comparator(const void* a, const void* b)
{
   char* ca = (char*)a;
   char* cb = (char*)b;

   unsigned int ta = 0;
   unsigned int tb = 0;

   /* the 16th element is where the id starts, thats what I'm 
       searching on */
   memcpy(&ta, &(ca[16]), sizeof(unsigned int));
   memcpy(&tb, &(cb[16]), sizeof(unsigned int));

   return (ta - tb);
}

I have verified that the data is complete, but for some reason, there is garbage data in ca, but in cb the correct data is present. Even more bizarre is I'm not getting any segfaults to indicate that there is in fact garbage data about.

Disregard this. I was tired of trying to debug it so I just whipped up my own binary search.

No. sid is an unsigned int that i'm searching for in the dest character array (which is 50 * pageSize long where pageSize is one of 100, 1000, or 10000). I didn't use qsort as we were not permitted to.

I tried various methods including copying the data to a struct and passing an array of structs in, but it all resulted in the same garbage data in the first variable, but the correct data in the second variable.

In the end I just implemented my own binary search function, that performs fairly fast. I'll come back to this after i hand in my assignment but for know, as long as it works i'm gonna go with my implementation.

Well, that would be the problem then. sid needs to be an object that you're looking for (and you're looking for 50-byte objects with the key at byte 16, not ints).

Originally Posted by tabstop

Well, that would be the problem then. sid needs to be an object that you're looking for (and you're looking for 50-byte objects with the key at byte 16, not ints).

Thanks. This was the first time using bsearch, I should of done more research.

I was under the assumption that the data passed in the second argument was the data that was being passed as both param1 and param2 in the comparator function. Silly me, the first param is actually the key were searching on. Do'h!

This following change fixed it:

Code:

unsigned int comparator(const void* a, const void* b)
{
   int* ia = (int*)a;
   char* cb = (char *)b;
   int ib;

   memcpy(&ib, &(cb[16]), sizeof(unsigned int));

   return (*ia) - ib;
}