Problem getting bsearch to work

[tpekar]

I am trying to get the binary search library function to work for a dynamically created structure array.  It crashes with the dreaded "Windows encountered a problem and cannot continue" message.  Can anyone tell me what I have done wrong?  Here is my code:

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
typedef struct name {
  char first[10];
  char middle[10];
} Name;
Name **names;
char *firsts[5]={"alicia","anna","tim","tom","tonya"};
char *middles[5]={"louise","anne","joseph","bayne","marie"};
int i;
Name *ptr;
main(int argc, char *argv[]) {
int compare(Name *name1, Name *name2);
names=malloc(5*sizeof(char *));
for (i=0;i<5;i++) {
  names[i]=malloc(sizeof(Name));
  strcpy(names[i]->first,firsts[i]);
  strcpy(names[i]->middle,middles[i]);
}
ptr=bsearch("tom",names,5,sizeof(Name),compare);
if (ptr!=NULL) printf("ptr->middle=%s|", ptr->middle);
 else printf("\nnot found\n");
}

compare(Name *name1, Name *name2) {
return strcmp(* (char**) name1->first, * (char **) name2->first);
}


[jj2007]

Here is a modified example from http://www.cplusplus.com/reference/cstdlib/bsearch
It works, but the behaviour is weird - check the order of comparisons, and try commenting out the qsort. Here is the output with the qsort:

Comparing 20 with 10
Comparing 20 with 10
Comparing 30 with 10
Comparing 30 with 20
Comparing 40 with 10
Comparing 40 with 30
Comparing 50 with 10
Comparing 50 with 40
Comparing 60 with 10
Comparing 60 with 50
Comparing 41 with 40
Comparing 41 with 60
Comparing 41 with 50
41 is not in the array.

For comparison, here the output when compiled with VS C++ 2010:

Comparing 20 with 10
Comparing 30 with 20
Comparing 40 with 30
Comparing 50 with 40
Comparing 60 with 50
Comparing 20 with 10
Comparing 30 with 20
Comparing 40 with 30
Comparing 50 with 40
Comparing 20 with 10
Comparing 30 with 20
Comparing 40 with 30
Comparing 20 with 10
Comparing 30 with 20
Comparing 20 with 10
Comparing 41 with 30
Comparing 41 with 50
Comparing 41 with 40
41 is not in the array.

Code: [Select]

#include <stdio.h>      /* printf */
#include <conio.h>      /* _getch */
#include <stdlib.h>     /* qsort, bsearch, NULL */
#pragma warn(disable:2007)    // assembly not portable
#pragma warn(disable:2216)    // retval never used

int compareints (const void * a, const void * b)
{
  int v1, v2;
  _asm mov eax, a;
  _asm mov eax, [eax];
  _asm mov v1, eax;

  _asm mov eax, b;
  _asm mov eax, [eax];
  _asm mov v2, eax;

  printf ("Comparing %x with %x\n",v1, v2);
  return ( *(int*)a - *(int*)b);
}

int values[] = { 0x10, 0x20, 0x30, 0x40, 0x50, 0x60 };

int main (void)
{
  int * pItem;
  int key = 0x41; // 41 is not in the array
  qsort (values, 6, sizeof (int), compareints);
  pItem = (int*) bsearch (&key, &values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%x is in the array.\n",*pItem);
  else
    printf ("%x is not in the array.\n",key);
    _getch();
  return 0;
}

[TimoVJL]

You are mixing pointer and pointers to pointers

this is working compare function for that example:

Code: [Select]

int compare(const void * name1, const void * name2)
{
//printf("%p %p %s %s\n", name1, name2, (char*)name1, (*(Name **)name2)->first);
return strcmp((char *)name1, (*(Name **)name2)->first);
}and calling that function

Code: [Select]

Name **ptr = bsearch("tom", names, 5, sizeof(Name*), compare);

Code: [Select]

printf("ptr->middle='%s'\n", (*ptr)->middle);

[tpekar]

Thanks Timovjl.  That worked.  I have been studying the changes you made and I think I understand some of them.  The reason for 'Name **ptr' before bsearch is because I defined ptr as a Name type pointer, hence the pointer to a pointer to receive the void pointer defined for bsearch, which would explain the dereferencing of ptr before ->middle in the next statement.  But the return statement for the compare function has really got me stumped.  The first argument, name1,  is case as a character pointer.  But the second argument is a dereferenced Name type pointer to a pointer, name2.  Why are they different when defined the same, as character pointers, in the strcmp function?

[TimoVJL]

If you give Name **names as parameter to bsearch it returns same kind of member from that array, Name * ?
If you give char * type key parameter to that function, you see it in compare function as first void parameter.
That second parameter is Name * as it is in array member.
That size must be sizeof(Name*) as Name** is array of pointers.