cdata-structuresmallocc11bsearch

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.