跳表中文件读取分配的void指针内存释放及读文件优化问题

我通过文件加载数据填充跳表结构，经LeakSanitizer检测发现，分配的字符串存在内存泄漏。这些字符串以void*类型的item存储，直接释放会导致程序异常（跳表仍需使用这些数据），每读取一行就会产生一处字节泄漏，泄漏日志如下：

=================================================================
==12111==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 86031 byte(s) in 711 object(s) allocated from:
    #0 0x7ff09a17c867 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55dd7970854b in load_dictionary (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main+0x154b)
    #2 0x55dd797086da in main (/home/matteo/Scrivania/Algo/laboratorio-algoritmi-2021-2022-main/Esercizio 2/ex2/build/main+0x16da)
    #3 0x7ff099ec9d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

同时，文件读取过程耗时极长（5-10分钟无进展），想知道更高效的读取方式。

以下是相关代码：

结构体定义 #

struct _SkipList {
    Node *head;
    unsigned int max_level;
    int (*compare)(void*, void*);
};
struct _Node {
    Node **next;
    unsigned int size;
    void *item;
};

字典加载函数 #

static unsigned int load_dictionary(char *filename,SkipList *list )
{
  unsigned int words_count = 0;
  FILE *fp = fopen(filename, "r");
  char *line = NULL;
  size_t len = 0;

  if (list == NULL)
  {
    list = create_skip_list();
  }
  char *word;
  while (getline(&line, &len, fp) != -1)
  {
    words_count++;
    word = malloc((len + 1) * sizeof(char));
    strcpy(word, line);
    strtok(word,"\n");
    insert_skip_list(list, word);
  }
  
  free(line);
  fclose(fp);
  return words_count;
}

跳表创建函数 #

SkipList* create_skip_list(){
    SkipList *list = malloc(sizeof(SkipList));
    list->max_level = 0;
    list->compare = NULL;
    list->head = create_head_node(NULL,MAX_HEIGHT);
    return list;
}

头节点创建函数 #

Node* create_head_node(void* item, int level){
    if(level <1)
        return NULL;

    Node *node = malloc(sizeof(Node));
    if(node == NULL){
        printf("error malloc node\r\n");
        /* Returning here prevent the program from accessing non allocated
         * memory. */
        return NULL;
    }

    node->item = item;
    node->size = level;

    node->next = (Node**)malloc(level * sizeof(Node *));
    if (!node->next) {
        printf("error malloc node next\r\n");
        free(node);
        return NULL;
    }

    for (int i = 0; i < level; i++)
    {
        node->next[i] = NULL;
    }

    return node;
}

节点数组删除函数 #

void delete_node_array(Node* node){
   if(node == NULL) return; 
   delete_node_array(node->next[0]);
   node = free_node(node);
}

跳表删除函数 #

SkipList* delete_skip_list(SkipList *list){
    if(list == NULL) return NULL;
    delete_node_array(list->head);
    free(list);
    list=NULL;
    return list;
}

节点释放函数 #

Node* free_node(Node *node){
    
    free(node->next);
    free(node);
    node = NULL;
    return node;
    
}

跳表插入函数 #

int insert_skip_list(SkipList* list,void* item){
    
    if (list == NULL || item ==NULL) return -1;
    Node* node = create_node(item,random_level()); //is the same of create_head_node but without the initial check of the null Item
    if(node == NULL){
        printf("\nisert_skip_list:error malloc node");
        return -1;
    }
   
    if(node->size > list->max_level){
        list->max_level = node->size;
    }
    
    Node *x = list->head;
    for (int k = list->max_level-1; k >= 0; k--)
    {
        if(x->next[k] == NULL || strcmp(item,x->next[k]->item) < 0 ){
            if(k < node->size){
                node->next[k] = x->next[k];
                x->next[k] = node;
            }
        }else{
            x = x->next[k];
            k++;
        }
    }
    return 0;
}

一、修复内存泄漏问题 #

泄漏核心原因：free_node函数仅释放了节点本身和next指针数组，未释放节点中存储的item（即你分配的字符串）。修改释放逻辑即可解决：

1. 更新free_node函数，增加item释放逻辑：

Node* free_node(Node *node){
    if (node == NULL) return NULL;
    // 头节点的item为NULL，需判断避免空指针解引用
    if (node->item != NULL) {
        free(node->item);
    }
    free(node->next);
    free(node);
    return NULL;
}

2. 确保程序结束时调用delete_skip_list销毁跳表，此时递归遍历所有节点的delete_node_array会触发修改后的free_node，同时释放节点和对应的字符串，彻底解决内存泄漏。

二、优化文件读取速度 #

当前读取慢的主要原因是getline频繁动态分配内存，加上多次系统调用IO。可通过以下方式优化：

1. 预分配缓冲区+批量读取 #

static unsigned int load_dictionary(char *filename, SkipList *list )
{
    unsigned int words_count = 0;
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        return 0;
    }

    // 预分配64KB缓冲区，减少IO系统调用次数
    char buf[65536];
    size_t bytes_read;
    char *ptr;
    char *newline;

    if (list == NULL) {
        list = create_skip_list();
    }

    while ((bytes_read = fread(buf, 1, sizeof(buf), fp)) > 0) {
        ptr = buf;
        while (ptr < buf + bytes_read) {
            newline = strchr(ptr, '\n');
            if (newline == NULL) {
                // 缓冲区末尾无换行，将剩余内容移到开头，下次继续读取
                memmove(buf, ptr, buf + bytes_read - ptr);
                bytes_read = buf + bytes_read - ptr;
                break;
            }
            // 计算行长度，去掉换行符
            size_t line_len = newline - ptr;
            char *word = malloc(line_len + 1);
            if (word) {
                strncpy(word, ptr, line_len);
                word[line_len] = '\0';
                insert_skip_list(list, word);
                words_count++;
            }
            ptr = newline + 1;
        }
    }

    // 处理最后一行无换行的情况
    if (bytes_read > 0) {
        char *word = malloc(bytes_read + 1);
        if (word) {
            strncpy(word, buf, bytes_read);
            word[bytes_read] = '\0';
            insert_skip_list(list, word);
            words_count++;
        }
    }

    fclose(fp);
    return words_count;
}

2. 辅助优化点 #

• 给跳表设置正确的比较函数：list->compare = (int(*)(void*,void*))strcmp;，避免插入时硬编码strcmp，同时保证逻辑一致性。
• 检查random_level实现，确保生成的层级分布合理，避免跳表层级过高导致插入效率下降。

内容的提问来源于stack exchange，提问作者Matteo Pagliarello