ハッシュサイズ変更のメモリリークC

Question

初めてのポスターで、Cでオープンアドレスハッシュライブラリのサイズを変更しようとしています。サイズ5 - >サイズ11から移動することから、新しいハッシュを作成し、古い要素をすべて新しいものに入れて、この新しいハッシュに古いハッシュポイントを持たせようとします。

ので、任意のサイズ変更時に、この古いハッシュを解放しようとすると問題がresize_OPENに私は古いハッシュキーを解放することができ、あるが、私は実際にワンセグ断層運動せずに（（old_H）無料）old_hash自身を解放することはできませんよ私はいつも古いハッシュのmemリークを持っています。各リサイズに対して、48バイトのハッシュオブジェクトをリークします。

私のput関数とresize_OPENは、すべてのサイズ変更が行われる場所です。

void put(Hash *H, int cur_key, int cur_value) { 
    int gen_key = 0; 
    if (cur_key < 0) 
     cur_key = cur_key * -1; 
    gen_key = cur_key % H->cur_size; 

    // Linear probing once around for a spot 
    k_v *new_node = createKV(cur_key, cur_value, 0); 

    while (1) { 
     // Inserting new key 
     if (!H->key_value[gen_key] || (H->key_value[gen_key]->k == INT_MIN)) { 
      H->num_elem++; 
      H->key_value[gen_key] = new_node; 
      break; 
     // Overwriting key 
     } else if (H->key_value[gen_key]->k == new_node->k) { 
      swap(&H->key_value[gen_key], &new_node); 
      free(new_node); 
      return; 
     } 

     // Robin hood hashing 

     // If the distance of the current key has probed less, swap and insert the curr key 
     // now that the new key is inserted  
     if (H->key_value[gen_key]->distance < new_node->distance) { 
      swap(&H->key_value[gen_key], &new_node); 
      gen_key = cur_key % H->cur_size; 
      // Don't increment distance until next check 
      new_node->distance--; 
     } 
     gen_key++; 
     new_node->distance++; 

     if (gen_key >= H->cur_size) 
      gen_key = 0; 

     // If we reach the probe limit, resize the hash 
     if (new_node->distance >= H->probe_limit) { 
      Hash *new_H = resize_OPEN(H); 
      *H = *new_H; 
      gen_key = new_node->k % H->cur_size; 
     } 
    } 

    if (H->num_elem >= H->to_resize) { 
     if (H->type == OPEN_ADDR) { 
      Hash *new_H = resize_OPEN(H); 
      *H = *new_H; 
     } else { 
      resize(H); 
     } 
    } 
    return; 
} 

マイサイズ変更機能

Hash *resize_OPEN(Hash *old_H) { 
    Hash *new_H = createHash(2 * old_H->cur_size); 

    for (int i = 0; i < old_H->cur_size; i++) { 
     if (old_H->key_value[i] && old_H->key_value[i]->k != INT_MIN) { 
      int k = old_H->key_value[i]->k; 
      int v = old_H->key_value[i]->v; 
      put(new_H, k, v); 
      free(old_H->key_value[i]); 
     } 
    } 

    free(old_H->key_value); 
    // How do I free the old hash here? free(old_H) will seg fault 
    return new_H; 
} 

EDIT：私は混乱のために申し訳ありませんが、より良い説明しようとしました。

typedef struct k_v { 
    int k; 
    int v; 
    int distance; 
} k_v; 

typedef struct Hash { 
    int cur_size; 
    int num_elem;  
    k_v **key_value;  // Open addressing   
    int to_resize;   // Elements to resize 
    int probe_limit; 
    double load_factor; 
} Hash; 

A memory leak example of when I insert 5 elements into a size 5 hash (one resize occuring)

Hash *createHash(int starting_size) {   
    // Get the next prime size 
    int index = 0; 
    for (; index < PRIME; index++) { 
     if (prime_size[index] >= starting_size) { 
      starting_size = prime_size[index]; 
      break; 
     } 
    } 

    Hash *new_hash = (Hash *)malloc(SIZE_hash); 

    new_hash->key_value = (k_v **)calloc(starting_size, SIZE_kv); 
    new_hash->probe_limit = log_prime[index]; 
    new_hash->cur_size = starting_size; 
    new_hash->num_elem = 0; 
    new_hash->load_factor = DEFAULT_LF; // Default load factor (change at 0.75 = N/size) 

    new_hash->to_resize = resize_default[index]; 

    return new_hash; 
} 

Answer 1

機能resize_OPEN()でメモリリークがあります：あなたは、最上位の呼び出し元のコンテキストでH変数のアドレスを渡されていなかったので

• はresize_OPEN()は、必要がありますHash構造体*old_Hを更新します。新しく割り当てられた構造体を解放します。

• しかしながら、この方法はむしろ混乱しやすく、エラーを起こしやすく、すべてのキー/値ノードを再割り当てすることに注意してください。より大きな配列を割り当てて、新しいハッシュサイズに沿ってキー/値ノードを再ディスパッチし、古いテーブルを解放することで、余分な割り当てと奇妙な構造体コピーの必要性を取り除くことができます。

• メモリ割り当ての失敗はテストされません。 malloc()とcalloc()のラッパーを使用してエラーをテストし、エラー時にエラーメッセージを表示して中止することをお勧めします。このmalloc()またはダイのアプローチは、未定義の動作よりも優れています。 put機能から

  // resize_OPEN reallocates the hash table to a larger size 
  // memory allocation failures are not tested. 
  void resize_OPEN(Hash *old_H) { 
      Hash *new_H = createHash(2 * old_H->cur_size); 
  
      for (int i = 0; i < old_H->cur_size; i++) { 
       if (old_H->key_value[i] && old_H->key_value[i]->k != INT_MIN) { 
        int k = old_H->key_value[i]->k; 
        int v = old_H->key_value[i]->v; 
        put(new_H, k, v); 
        free(old_H->key_value[i]); 
       } 
      } 
  
      free(old_H->key_value); 
      *old_H = *new_H; 
      free(new_H); 
  } 
  

  は、この関数を呼び出し、このよう：

  あり

   ... 
       // If we reach the probe limit, resize the hash 
       if (new_node->distance >= H->probe_limit) { 
        resize_OPEN(H); 
        gen_key = new_node->k % H->cur_size; 
       } 
      } 
  
      if (H->num_elem >= H->to_resize) { 
       if (H->type == OPEN_ADDR) { 
        resize_OPEN(H); 
       } else { 
        resize(H); 
       } 
      } 
      ... 
  

  このようなラッパーは、通常はここでxmalloc()、xcalloc() ...

は簡単な修正であると命名されていますあなたのコードに他の問題があるかもしれませんが、必要な情報はほとんど投稿しましたが、簡単にコンパイルしてテストできるフォームはありませんでした。非常に少数のプログラマーが、複雑な問題にコード断片だけを読み込ませることはできません。さらに、いくつかの問題は定義やコードを他の場所に隠す可能性があるため、Minimal, Complete, and Verifiable Exampleを付けずに正しい診断を行うことは不可能です。