Bsearch and junk values in the comparison function

Question

I have the following program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>

#define DICT_BUFSIZE 64

int compar(const void * a, const void * b)
{
    const char* c1 = (const char*)a;
    const char* c2 = (const char*)b;

    printf("c1: %s | c2: %s\n", c1, c2);

    return strcmp(c1, c2);
}

int main (void)
{
    FILE*     fdict;
    uint32_t  i;
    char**    dict = NULL;
    size_t    size = 0;
    size_t    size_alloced = 0;
    char      buf[DICT_BUFSIZE];

    fdict = fopen("/usr/share/dict/words", "r");
    if (!fdict) {
        printf("Could not open \"%s\": %s\n", "usr/share/dict/words", strerror(errno));
        exit(1);
    }

    for (i = 0; fgets(buf, DICT_BUFSIZE, fdict); ++i) {
        size_t len;

        if (i == size_alloced) {
            dict = realloc(dict, (i +50000) * sizeof(*dict));
            size_alloced += 50000;
        }
        len = strlen(buf);
        dict[i] = malloc(len);

        memcpy(dict[i], buf, len -1);
        dict[i][len -1] = '\0';
    }
    size = i;

    //for (i = 0; i < size; i++)
        //printf("%s\n", dict[i]);

    if(bsearch("company", dict, size, sizeof(*dict), compar))
        printf("Found!\n");

    for (i = 0; i < size; ++i)
        free(dict[i]);
    free(dict);

    fclose(fdict);

    return 0;
}

In the "compar" function the "c1" variable (the key to be searched) is displayed correctly, however there's junk output in the v2 variable.

Here's a sample output:

c1: company | c2: ���
c1: company | c2: �$z
c1: company | c2: ��I
c1: company | c2: ��7
c1: company | c2: P�.
c1: company | c2: �b3
c1: company | c2: �1
c1: company | c2: P�/
c1: company | c2: ��0
c1: company | c2: PC0
c1: company | c2: @g0
c1: company | c2:  y0
c1: company | c2: 0�0
c1: company | c2: ��0
c1: company | c2: `�0
c1: company | c2: ��0
c1: company | c2: 
c1: company | c2: P�0

I cannot understand this behaviour.

Answer 1

If you were searching an array of int, you'd be converting the const void * arguments to your compare function to int *, would you not?

You're searching an array of char *, so you need to be converting the const void * arguments to char ** — and you need to pass a char ** argument for the value to be found.

The changes required to your code are minimal but crucial:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>

#define DICT_BUFSIZE 64

static int compar(const void *a, const void *b)
{
    const char *c1 = *(const char **)a;
    const char *c2 = *(const char **)b;

    printf("c1: %s | c2: %s\n", c1, c2);

    return strcmp(c1, c2);
}

int main (void)
{
    FILE*     fdict;
    uint32_t  i;
    char**    dict = NULL;
    size_t    size = 0;
    size_t    size_alloced = 0;
    char      buf[DICT_BUFSIZE];
    const char *file = "/usr/share/dict/words";

    fdict = fopen(file, "r");
    if (!fdict) {
        printf("Could not open \"%s\": %s\n", file, strerror(errno));
        exit(1);
    }

    for (i = 0; fgets(buf, DICT_BUFSIZE, fdict); ++i) {
        size_t len;

        if (i == size_alloced) {
            dict = realloc(dict, (i +50000) * sizeof(*dict));
            size_alloced += 50000;
        }
        len = strlen(buf);
        dict[i] = malloc(len);

        memcpy(dict[i], buf, len -1);
        dict[i][len -1] = '\0';
    }
    size = i;

    //for (i = 0; i < size; i++)
        //printf("%s\n", dict[i]);

    const char *search = "company";
    if(bsearch(&search, dict, size, sizeof(*dict), compar))
        printf("Found!\n");

    for (i = 0; i < size; ++i)
        free(dict[i]);
    free(dict);

    fclose(fdict);

    return 0;
}

The comparator function now expects two char ** values, and captures the string that each of those points to.

The first argument to the call needs to be the address of a char * variable; hence the addition of variable const char *search = "company";.

Minor cleanups include make the comparator function static (mainly to satisfy my pedantic default compilation options — though it is best if functions are declared before they're defined), and using variable const char *file = "/usr/share/dict/words"; to avoid (near) repetition between the call to fopen() and the error message.

Sample output (run on a Mac with macOS Sierra 10.12.3):

c1: company | c2: modifier
c1: company | c2: eagle
c1: company | c2: Canarian
c1: company | c2: counteridea
c1: company | c2: citropten
c1: company | c2: compulsoriness
c1: company | c2: coelenteric
c1: company | c2: Colossian
c1: company | c2: commonable
c1: company | c2: compilation
c1: company | c2: compagination
c1: company | c2: compatriot
c1: company | c2: comparition
c1: company | c2: comparable
c1: company | c2: companionate
c1: company | c2: companionway
c1: company | c2: comparability
c1: company | c2: company
Found!