bsearch() on an array of strings in C

I am implementing a code in C so as to copy a string in an array of characters ( string ) and then later do a bsearch on it. But unexpectedly the bsearch returns false for results that should be true. I am guessing it has something to do with how i am inserting the string in the first place during insert. You could consider this as insertion and search on the leaf node of a btree.

I am coding this in a multi - file framework so cant post all code. posting relevant parts

Structure of the array of strings for easier visualization -

array of strings ( array of array of chars ) 
                            --
                          0 -- array of characters ( size may be 5 )  
                          1 -- array of characters ( size may be 7 ) 
                          2 -- array of characters ( size may be 10 )

or

keys = [
         [ s t r i n g 1 ]
         [ s t r i n g T w o ]
         [ s t r i n g T H R E E ]
       ]

function to insert -

void insert_in_leaf_node(struct leaf_node * node, u32 len, u8 * key){
    if (node->no_of_keys > 1 ) {
       if (!search_in_fat(node, len, key)) {
            node->keys[node->no_of_keys] = (char *) malloc(sizeof(char) * len);
            strncpy(node->keys[node->no_of_keys], (char *) key, len);                                                              // copy key to array
            node->keys[node->no_of_keys][len] = '\0';
            node->no_of_keys += 1;
            qsort(node->keys, (size_t) node->no_of_keys, sizeof(char *), cstring_cmp);                                          // sort alphabetically to enable bsearch later
        }
    } else {
        node->keys[node->no_of_keys] = (char *) malloc(sizeof(char) * len);
        strncpy(node->keys[node->no_of_keys], (char *) key, len);                                                              // copy key to array
        node->keys[node->no_of_keys][len] = '\0';
        node->no_of_keys += 1;
        qsort(node->keys, (size_t) node->no_of_keys, sizeof(char *), cstring_cmp);                                          // sort alphabetically to enable bsearch later
    }
}

code to search -

bool search_in_fat(struct leaf_node * node, u32 len, u8 * key){
    if(!bsearch(key,node->keys,(size_t)node->no_of_keys, sizeof( char * ),(int(*)(const void*,const void*)) strcmp)) return false;
    return true;
}

cstring_cmp functione used in insert function -

int cstring_cmp(const void *a, const void *b)
{
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    return strcmp(*ia, *ib);
    /* strcmp functions works exactly as expected from
    comparison function */
}

In case anyone is wondering whats in key, here is how a key array is populated earlier and a set / get function is called with indivisual key each time ( the set / get functions call the above functions )

code for trace load from file to generate array of keys - ( __samples holds the keys )

bool
load_trace(const char * const filename)
{
  char * buf = NULL;
  size_t size = 0;
  FILE * fin = fopen(filename, "r");
  if (fin == NULL) return false;
  u64 i = 0;
  // count for lines
  while (getline(&buf, &size, fin) >= 1) {
    i++;
  }
  rewind(fin);
  __samples = malloc(sizeof(char *) * i);
  __sizes = malloc(sizeof(u32) * i);
  __nr_samples = i;
  ssize_t len = 0;
  i = 0;
  while ((len = getline(&buf, &size, fin)) >= 1) {
    if (buf[len-1] == '\n') { // remove trailing '\n'
      len--;
      buf[len] = '\0';
    }
    __samples[i] = strdup(buf);
    __sizes[i] = len;
    i++;
  }
  free(buf);
  fclose(fin);
  return true;
}

P.S : this part was not coded by me, but by my senior when building the framework.

What could be the problem? I have done quite a bit of googling but no positive results yet.

Thank You!

Solution

You can't pass strcmp() as the comparison function for bsearch(). That function needs to take pointers to the elements to compare (In this case a pointer to a pointer to a string, though the actual type of the functions arguments need to be const void *), while strcmp() expects a pointer to a string. There's an extra layer of indirection that it doesn't handle.

You don't show the function, but the cstring_cmp() function you use with qsort() can probably be used.

The first argument of the bsearch() comparison function is the pointer given as the key, the second argument is a pointer to the current element of the array being compared, where with a qsort() comparison function, both arguments are pointers to elements. So if you make the key argument to bsearch() a pointer to the thing you're looking for, both will work with the same function. In other words, bsearch(&key, ...) is good, bsearch(key, ...) isn't. You can also have a bsearch()-specific comparison function that will work with that second case. See https://stackoverflow.com/a/15824981/9952196 for an example.