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

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

任何帮助，将不胜感激。谢谢你。

4

1 回答 1

0

我看了你的代码，我想，“你让这种方式太难了”。我不是想成为一个聪明的驴子，而是考虑下面的代码，它用更少的代码执行相同的功能。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  ;

也许我会因为你做作业而受到批评，我不知道。无论如何，人们都可以从代码中学到一些东西，看看它如何让问题变得更小。

于 2013-10-30T16:46:31.073 回答