I am having trouble with this bsearch. Im pretty sure that I've isolated the problem to the number of bytes parameter that bsearch takes in. The data array is a scrabble dictionary and I'm 100% sure that the entire dictionary is loaded into memory, but when I use bsearch to try to find if a particular word is in the dictionary, it only works for words before 'wontedly' even though the dictionary's last word is 'zzz' so some words starting with 'w' 'x' 'y' and 'z' are not able to be found. It's almost as if the bsearch function can not see the end of the array, even though it's there. Another thing of note is that in my comparison function i print out what bsearch has passed to it to see what words are being compared, and it seems that on the first comparison, bsearch does not send the middle value which is something like 'lunkheads', instead, it is starting at 'lodge' which is not the middle word in the dictionary. 16 bytes is the number I put in, through trial and error that seems to work. The issue is that I do not know what the length of each element in the array is, or at least I think that's the issue.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define LEN 128
int search(const void *usr_word,const void *words);
struct data_t {
int nval; /* current number of values in array */
int max; /* allocated number of values */
char **data; /* the data array */
};
enum {INIT = 1, GROW = 2};
int main(void)
{
FILE *fp = fopen("scrabble.txt", "r");
assert(fp);
char *usr_word = NULL;
char buf[LEN];
int i = 0;
char number[LEN];
char* item = NULL;
struct data_t *data = malloc(sizeof(struct data_t));
data->nval = INIT;
data->max = INIT;
data->data = NULL;
while (fgets(buf, LEN, fp)) {
if (data->data == NULL) {
data->data = malloc(strlen(buf) - 1);
assert(data->data);
}
else if (data->nval > data->max) {
data->data = realloc(data->data, GROW * data->max * LEN);
assert(data->data);
data->max = GROW * data->max;
}
data->data[i] = strndup(buf, strlen(buf) - 1);
i++;
data->nval++;
}
/* overcounted */
data->nval--;
printf("Enter word: ");
fgets(buf, LEN, stdin);
usr_word = strndup(buf, strlen(buf)-1);
/*search for word*/
item = (char *) bsearch(usr_word, data->data[0], data->nval, 16, search);
if (item != NULL)
printf("\n%s is valid\n", item);
else if (item == NULL)
printf("\n%s is not valid\n", usr_word);
return 0;
}
int search(const void *usr_word,const void *words)
{
printf("%s | %s | %d\n", (char *)usr_word,(char *) words, strcmp(usr_word,words));
return strcmp(usr_word,words);
}
Okay, there are multiple problems with your code all originating from your misunderstanding of char ** which is used in struct data_t.data.
char ** is array of pointers to pointers. it is not array of strings in any way.
This means the following:
data->data = malloc(strlen(buf) - 1);
should be replaced with the following:
data->data = malloc(sizeof(char *) * (data->nval));
same with realloc:
data->data = realloc(data->data, GROW * data->max * LEN);
replace with
data->data = realloc(data->data, GROW * data->max * sizeof(char *));
next, bsearch invocation:
item = (char *) bsearch(usr_word, data->data[0], data->nval, 16, search);
replace with:
item = (char **) bsearch(usr_word, data->data, data->nval, sizeof(char*), search);
see how i replaced 16 with sizeof(char*)? this is because bsearch is applied to char **, e.g. array of char *, hence, elementary bsearch item is char *. Hence, return value from bsearch is pointer to elementary item, e.g. pointer tochar *, e.g.char **`.
quote from manpage:
The bsearch() function returns a pointer to a matching member of the array
next is printf:
printf("\n%s is valid\n", item);
i replacing with: printf("\n%s is valid\n", *item);
*item instead of item is due to the same reason - bsearch returns us pointer to what it have found. We need to resolve this pointer into real value.
And finally your search:
printf("%s | %s | %d\n", (char *)usr_word,(char *) words, strcmp(usr_word,words));
return strcmp(usr_word,words);
again, use correct level of pointers - we have two-level and we need one-level:
printf("%s | %s | %d\n", (char *)usr_word,*(char **) words, strcmp(usr_word,words));
return strcmp(usr_word,*(char**)words);
For your convinience, here's the whole program which works:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define LEN 128
int search(const void *usr_word,const void *words);
struct data_t {
int nval; /* current number of values in array */
int max; /* allocated number of values */
char **data; /* the data array */
};
enum {INIT = 1, GROW = 2};
int main(void)
{
FILE *fp = fopen("scrabble.txt", "r");
assert(fp);
char *usr_word = NULL;
char buf[LEN];
int i = 0;
char number[LEN];
char** item = NULL;
struct data_t *data = malloc(sizeof(struct data_t));
data->nval = INIT;
data->max = INIT;
data->data = NULL;
while (fgets(buf, LEN, fp)) {
if (data->data == NULL) {
data->data = malloc(sizeof(char *) * (data->nval));
assert(data->data);
}
else if (data->nval > data->max) {
data->data = realloc(data->data, GROW * data->max * sizeof(char *));
assert(data->data);
data->max = GROW * data->max;
}
data->data[i] = strndup(buf, strlen(buf) - 1);
i++;
data->nval++;
}
/* overcounted */
data->nval--;
printf("Enter word: ");
fgets(buf, LEN, stdin);
usr_word = strndup(buf, strlen(buf)-1);
/*search for word*/
item = (char **) bsearch(usr_word, data->data, data->nval, sizeof(char*), search);
if (item != NULL)
printf("\n%s is valid\n", *item);
else if (item == NULL)
printf("\n%s is not valid\n", usr_word);
for(i=0;i<data->nval;++i) free(data->data[i]);
free(data->data);
free(data);
free(usr_word);
return 0;
}
int search(const void *usr_word,const void *words)
{
printf("%s | %s | %d\n", (char *)usr_word,*(char **) words, strcmp(usr_word,words));
return strcmp(usr_word,*(char**)words);
}