Valgrind給出無效的免費錯誤信息

Question

我有一個散列表，它是一個桶指針數組（節點在這個項目中被稱爲桶）。散列表使用鏈接列表鏈接來避免衝突。這裏是我的數據結構：

typedef struct bucket { 
    char *key; 
    void *value; 
    struct bucket *next; 
} Bucket; 

typedef struct { 
    int key_count; 
    int table_size; 
    void (*free_value)(void *); 
    Bucket **buckets; 
} Table; 

Valgrind是給我一個無效的free（）的錯誤信息，在行：table->free_value(curr->value); 在該方法中：

/* Removes a bucket consisting of a key and value pair */ 
int remove_entry(Table * table, const char *key) { 
    unsigned int hc = 0; 
    int found = 0; 
    Bucket *curr; 
    Bucket *prev; 
    if (table == NULL || key == NULL) { 
    return FAIL; 
    } 
    hc = hash_code(key)%(table->table_size); 
    if (table->buckets[hc] != NULL) { 
    curr = table->buckets[hc]; 
    prev = NULL; 
    while (curr != NULL) { 
     if (strcmp(curr->key, key) == 0) { 
     found = 1; 
     if (table->free_value != NULL && curr->value != NULL) { 
      table->free_value(curr->value); 
      if (curr == table->buckets[hc]) { 
      table->buckets[hc] = curr->next; 
      free(curr->key); 
      free(curr); 
      curr = NULL; 
      (table->key_count)--; 
      return SUCC; 
      } 
      prev->next = curr->next; 
      free(curr->key); 
      free(curr); 
      curr = NULL; 
      (table->key_count)--; 
      return SUCC; 
     } else { 
      if (curr == table->buckets[hc]) { 
      table->buckets[hc] = curr->next; 
      free(curr->key); 
      free(curr); 
      curr = NULL; 
      (table->key_count)--; 
      return SUCC; 
      } 
      prev->next = curr->next; 
      free(curr->key); 
      free(curr); 
      curr = NULL; 
      (table->key_count)--; 
      return SUCC; 
     } 
     } 
     prev = curr; 
     curr = curr->next; 
    } 
    } 
    if (found == 0) { 
    return FAIL; 
    } 
    return SUCC; 
} 

我不知道它爲什麼這麼說。這裏是我的put（）方法：

/* Puts a key value pair in. If the key exists, the value is updated, otherwise the pair is added. */ 
int put(Table *table, const char *key, void *value) { 
    unsigned int hc = 0; 
    Bucket *curr; 
    Bucket *new_bucket; 
    char *copy_key; 

    if (table == NULL || key == NULL) { 
    return FAIL; 
    } 

    copy_key = malloc(sizeof(strlen(key) + 1)); 
    if (copy_key == NULL) { 
    return FAIL; 
    } 
    strcpy(copy_key, key); 

    hc = hash_code(key)%(table->table_size); 
    if (table->buckets[hc] != NULL) { 
    curr = table->buckets[hc]; 
    while (curr != NULL) { 
     if (strcmp(curr->key, key) == 0) { 
     if (curr->value != NULL && value != NULL) { 
      table->free_value(curr->value); /* Getting the invalid free error here again */ 
     } 
     curr->value = value; 
     free(copy_key); 
     return SUCC; 
     } 
     curr = curr->next; 
    } 
    curr = table->buckets[hc]; 
    new_bucket = malloc(sizeof(*new_bucket)); 
    if (new_bucket == NULL) { 
     free(copy_key); 
     return FAIL; 
    } 
    new_bucket->value = value; 
    new_bucket->key = copy_key; 
    new_bucket->next = curr; 
    table->buckets[hc] = new_bucket; 
    (table->key_count)++; 
    return SUCC; 
    } else if (table->buckets[hc] == NULL) { 
    new_bucket = malloc(sizeof(*new_bucket)); 
    if (new_bucket == NULL) { 
     free(copy_key); 
     return FAIL; 
    } 
    new_bucket->value = value; 
    new_bucket->key = copy_key; 
    table->buckets[hc] = new_bucket; 
    table->buckets[hc]->next = NULL; 
    (table->key_count)++; 
    return SUCC; 
    } 
    free(copy_key); 
    return FAIL; 
} 

任何幫助，將不勝感激。謝謝。

Answer 1

我看着你的代碼，我想，「你這樣做太難了」。我不想成爲一自作聰明，但考慮下面的代碼執行相同的功能與少得多的代碼。 C代碼的一個目標是最小化重複的代碼塊。

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <string.h> 
#include <unistd.h> 

#define SUCC 0 
#define FAIL 1 

typedef struct bucket { 
    char *key; 
    void *value; 
    struct bucket *next; 
} Bucket; 

typedef struct { 
    int key_count; 
    int table_size; 
    void (*free_value)(void *); 
    Bucket **buckets; 
} Table; 

unsigned int hash_code(const char *key) { // dummy stupid hash function 
    unsigned int hash = 0; 
    while(*key) { 
     hash += *key++; 
    } 
    return hash; 
} 

/* Puts a key value pair in. If the key exists, the value is updated, otherwise the pair is added. */ 
int put(Table *table, const char *key, void *value) { 

    if(table == 0 || key == 0) { 
     return FAIL; 
    } 

    unsigned int hc = hash_code(key)%(table->table_size); 
    Bucket **prev = &table->buckets[hc]; 
    Bucket *curr = *prev; 
    while(curr && strcmp(curr->key, key)) { 
     prev = &curr->next; 
     curr = curr->next; 
    } 

    if(curr) { 
     if(table->free_value && curr->value) { 
      table->free_value(curr->value); 
     } 
     curr->value = value; 
    } else { 
     Bucket *p = malloc(sizeof(*p)); 
     if(p == 0) { 
      return FAIL; 
     } 
     if((p->key = strdup(key)) == 0) { 
      free(p); 
      return FAIL; 
     } 
     *prev = p; 
     p->next = 0; 
     p->value = value; 
     table->key_count++; 
    } 
    return SUCC; 
} 

/* Removes a bucket consisting of a key and value pair */ 
int remove_entry(Table * table, const char *key) { 

    if (table == NULL || key == NULL) { 
     return FAIL; 
    } 

    unsigned int hc = hash_code(key)%(table->table_size); 
    Bucket **prev = &table->buckets[hc]; 
    Bucket *curr = *prev; 
    while(curr && strcmp(curr->key, key)) { 
     prev = &curr->next; 
     curr = curr->next; 
    } 

    if(curr == 0) { 
     return FAIL; 
    } 

    if(table->free_value && curr->value) { 
     table->free_value(curr->value); 
    } 
    *prev = curr->next; 
    free(curr->key); 
    free(curr); 
    table->key_count--; 
    return SUCC; 
} 

void print_table(Table *table, FILE *file) { 
    printf("table key_count=%d {\n", table->key_count); 
    for(int i = 0; i != table->table_size; i++) { 
     if(table->buckets[i]) { 
      printf("[%d]", i); 
      for(Bucket *b = table->buckets[i]; b; b = b->next) { 
       printf(" %s", b->key); 
      } 
      printf("\n"); 
     } 
    } 
    printf("}\n"); 
} 

int main(int argc, char **argv) { 
    Bucket *buckets[100] = { 0 }; 
    Table table; 
    table.table_size = 100; 
    table.key_count = 0; 
    table.free_value = 0; 
    table.buckets = buckets; 

    int ch; 
    while((ch = getopt(argc, argv, "p:r:x")) != -1) { 
     switch(ch) { 
      case 'p': 
       printf("put %s\n", optarg); 
       put(&table, optarg, optarg); 
       break; 
      case 'r': 
       printf("remove %s\n", optarg); 
       remove_entry(&table, optarg); 
       break; 
      case 'x': 
       print_table(&table, stdout); 
       break; 
     } 
    } 
    printf("done\n"); 
    print_table(&table, stdout); 
    return 0; 
} 

唯一的「聰明」部分是Bucket **prev發生了什麼。這需要一點研究。其餘的應該是直截了當的。

而且這裏有一個小的shell腳本來運行一些測試情況：

#!/bin/csh -f 

set valgrind = valgrind 
set valgrind = "" 

cc -Wall hash.c -o hash 
$valgrind ./hash -pa ; # add "a" 
$valgrind ./hash -pa -ra ; # add "a" rm "a" 
$valgrind ./hash -pab -pba ; # same bucket 
$valgrind ./hash -pab -pba -rab ; # same bucket 
$valgrind ./hash -pab -pba -rba ; # same bucket 
$valgrind ./hash -pab -pab ; # add "ab" twice 
$valgrind ./hash -pba -pab -pab -pab ; 

也許我會得到一些高射炮做功課，我不知道。無論如何，人們可以從代碼中學到一些東西，看看它是如何使問題變得更小的。