bsearch() для массива строк в C

Question

Я реализую код на C, чтобы скопировать строку в массив символов (строка), а затем выполнить поиск по нему. Но неожиданно bsearch возвращает false для результатов, которые должны быть правдой. Я предполагаю, что это как-то связано с тем, как я вставляю строку в первую очередь во время вставки. Вы можете рассматривать это как вставку и поиск на листовом узле дерева.

Я кодирую это в многофайловой структуре, поэтому не могу опубликовать весь код. размещение соответствующих частей

Структура массива строк для упрощения визуализации -

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 ]
       ]

функция для вставки -

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
    }
}

код для поиска -

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, используемая в функции вставки -

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 */
}

В случае, если кому-то интересно, что в ключе, вот как массив ключей заполняется раньше и функция set / get вызывается с индивидуальным ключом каждый раз (функции set / get вызывают вышеуказанные функции)

код для трассировки загрузки из файла для генерации массива ключей - (ключи хранятся в __samples)

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;
}

PS: эта часть была написана не мной, а моим руководителем при создании фреймворка.

В чем может быть проблема? Я немного погуглил, но положительных результатов пока нет.

Благодарю вас!

Answer 1

Вы не можете пройти strcmp() в качестве функции сравнения для bsearch(), Эта функция должна брать указатели на элементы для сравнения (в этом случае указатель на указатель на строку, хотя фактический тип аргументов функций должен быть const void *), в то время как strcmp() ожидает указатель на строку. Есть дополнительный уровень косвенности, с которым он не справляется.

Вы не показываете функцию, но cstring_cmp() функция, которую вы используете с qsort() может быть использован.

Первый аргумент bsearch() функция сравнения - указатель, данный как ключ, второй аргумент - указатель на текущий элемент сравниваемого массива, где с qsort() Функция сравнения, оба аргумента являются указателями на элементы. Так что, если вы сделаете ключевой аргумент bsearch() указатель на то, что вы ищете, оба будут работать с одной и той же функцией. Другими словами, bsearch(&key, ...) это хорошо, bsearch(key, ...) нет. Вы также можете иметь bsearch()-специфическая функция сравнения, которая будет работать с этим вторым случаем. См. /questions/15153917/problema-s-ispolzovaniem-bsearch-s-massivom-strok/15153923#15153923 для примера.