-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 コードの目標の 1 つは、重複するコード ブロックを最小限に抑えることです。

#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。それには少し勉強が必要です。残りは簡単です。

そして、いくつかのテスト ケースを実行するための小さなシェル スクリプトを次に示します。

#!/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 に答える