'Program received signal SIGSEGV, Segmentation fault.'の解決

Question

前提・実現したいこと

オープンアドレス法というハッシュ法をCで実装しようとしています.

環境はWindows10上のUbuntu 20.04.2 LTSです.

エラーメッセージはgdbを利用してトレースした際に出たものです.

open_addressing.cのcreate_dict関数に問題があることはわかるのですが,具体的な箇所がわからず困っています.

わかる方いましたらお願いします.

発生している問題・エラーメッセージ

$ ./a.out
Breakpoint 1, main () at main_open_addressing.c:5
5       int main(void) {
(gdb) step
6         DictOpenAddr *test_dict = create_dict(10);
(gdb) step
create_dict (len=0) at open_addressing.c:7
warning: Source file is more recent than executable.
7       {
(gdb) step
8         DictOpenAddr *dictopenaddr = (DictOpenAddr *)malloc(sizeof(DictOpenAddr));
(gdb) step
Dictionary created!
Program received signal SIGSEGV, Segmentation fault.

該当のソースコード

<open_addresing.c>

#include <stdio.h>
#include <stdlib.h>
#include "open_addressing.h"
#include "main_open_addressing.c"

DictOpenAddr *create_dict(int len)
{
  DictOpenAddr *dictopenaddr = (DictOpenAddr *)malloc(sizeof(DictOpenAddr));

  dictopenaddr->H = (DictData *)malloc(sizeof(DictData) * len);
  dictopenaddr->B = len;

  for (int i=0; i < len; i++)
  {
    dictopenaddr->H[i].name = -1;
    dictopenaddr->H[i].state = EMPTY;
  }

  printf("Dictionary created!\n");
 
  return dictopenaddr;
}

int h(DictOpenAddr *dict, int d, int count){

  int hash = d % (dict->B);
  
  hash = (hash + count) % (dict->B);

  return hash;
}

void insert_hash(DictOpenAddr *dict, int d)
{
  if (search_hash(dict,d) != -1 )
  {
    return ;
  }

  int count = 0;
  int b = h(dict,d,count);
  int init_b = b;

  while (b != init_b){
    if (dict->H[b].state == EMPTY || dict->H[b].state == DELETED)
  {
    dict->H[b].name = d;
    dict->H[b].state = OCCUPIED;
  }

  count += 1;
  b = h(dict,d,count);
  }
  
  fprintf(stderr, "Cannot be inserted.\n");
}

int search_hash(DictOpenAddr *dict, int d)
{
  int count = 0;
  int b = h(dict,d,count);
  int init_b = b;

  while (b != init_b){
     if (dict->H[b].state == OCCUPIED)
  {
    if (dict->H[b].name == d)
    {
      return b;
    }
    
  }

  else if ((dict->H)[b].state == EMPTY)
  {
    return -1;
  }

  count += 1;

  b = h(dict,d,count);
  
    
  }
    return -1;
  }  

void delete_hash(DictOpenAddr *dict, int d)
{
  int b = search_hash(dict,d);
  if (b != -1)
  {
    (dict->H)[b].state = DELETED;
  }
}

void display(DictOpenAddr *dict)
{
  int i = 0;
 
  while (i<dict->B){
    switch (dict->H[i].state)
  {
  case EMPTY:
    printf("e");
  case DELETED:
    printf("d");
  case OCCUPIED:
    printf("%d",dict->H[i].name);
  }
  i++;
  }
}

void delete_dict(DictOpenAddr *dict){
  free(dict);
  printf("Dictionary deleted!");
}

<open_addresing.h>

#ifndef INCLUDE_GUARD_OPEN_ADDRESSING_H
#define INCLUDE_GUARD_OPEN_ADDRESSING_H

typedef enum state {
  EMPTY,
  DELETED,
  OCCUPIED
} State;

typedef struct dict_data {
  int name;
  State state;
} DictData;

typedef struct dict_open_addr {
  DictData *H;
  int B;
} DictOpenAddr;

DictOpenAddr *create_dict(int len);
int h(DictOpenAddr *dict, int d, int count);
void insert_hash(DictOpenAddr *dict, int d);
int search_hash(DictOpenAddr *dict, int d);
void delete_hash(DictOpenAddr *dict, int d);
void display(DictOpenAddr *dict);
void delete_dict(DictOpenAddr *dict);

#endif  // INCLUDE_GUARD_OPEN_ADDRESSING_H

<main_open_addresing.c>

#include <stdio.h>
#include <stdlib.h>
#include "open_addressing.h"

int main(void) {
  DictOpenAddr *test_dict = create_dict(10);

  insert_hash(test_dict, 1);
  insert_hash(test_dict, 2);
  insert_hash(test_dict, 3);
  insert_hash(test_dict, 11);
  insert_hash(test_dict, 12);
  insert_hash(test_dict, 21);
  display(test_dict);

  printf("Search 1 ...\t%d\n", search_hash(test_dict, 1));
  printf("Search 2 ...\t%d\n", search_hash(test_dict, 2));
  printf("Search 21 ...\t%d\n", search_hash(test_dict, 21));
  printf("Search 5 ...\t%d\n", search_hash(test_dict, 5));

  delete_hash(test_dict, 3);
  display(test_dict);

  delete_hash(test_dict, 11);
  display(test_dict);

  delete_dict(test_dict);

  return EXIT_SUCCESS;
}

Answer 1

C言語ってのは、実行時のエラーチェックは基本的に行いません
そのため、実行時のエラーというのは、たまたまそこでその内容で引っかかっただけ、なんで、発生場所やエラー内容はそのまま信用できないのが普通です。

ってことで、あなたのコードの中でアクセス違反や異常アクセスがあります。
ガンバってその場所を特定しましょう。

＃コードが一部しか提示されてないので、言えるのはここまで

Comments

[Mellonn]

自分が訂正している箇所(create_dict)以外にアクセスに関する問題がある可能性があるということですね.
訂正してコード全体を載せます.自分でも見直します.

[y_waiwai]

メモリ破壊があるために、プログラムが暴走して、たまたまそのSIGSEGVで止まった、というところでしょうね。

Answer 2

そのcreate_dictならdictopenaddrの指す先はmallocで確保しとく必要がある。
変数定義の時に、初期化を伴う様にすれば気付きやすいかも。

Comments

[Mellonn]

dictopenaddr先の領域もmallocで確保しておきました.

[Mellonn]

↑修正後のことです

[matukeso]

warning: Source file is more recent than executable
ソース変更しただけでコンパイルしてないオチ？

[Mellonn]

コンパイルし直しました
質問文にあるように,'Dictionary created!'の出力まではいきましたが,その直後にSegmentation faultが出ました

[matukeso]

cc -c -o open_addressing.o open_addressing.c
./a.out
今度はリンクしてないオチ？というかビルド方法わからないの？

[Mellonn]

Makefile(open_addressing: open_addressing.o main_open_addressing.o)をmakeして,/a.outを行っているのですが,何か足りない作業などありますか?

[matukeso]

なんでそのMakefileでa.outになるの？
./open_addressingじゃなくて？
(.c.o:ルールがある前提)

[Mellonn]

Makefile上でtypoがありました
修正して,makeしてみたところ
cc -c -o open_addressing.o open_addressing.c
cc -c -o main_open_addressing.o main_open_addressing.c
cc open_addressing.o main_open_addressing.o -o open_addressing
/usr/bin/ld: main_open_addressing.o: in function `main':
main_open_addressing.c:(.text+0x0): multiple definition of `main'; open_addressing.o:open_addressing.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status
make: *** [<builtin>: open_addressing] Error 1

[matukeso]

そのリンカエラーによれば、open_addressing.cとmain_open_addressing両方にmain関数が書いてある事になるんですが、、

[Mellonn]

すいません。open_addressing.cにmain_open_addressing.cをインクルードしていたのが原因みたいでした

Answer 3

DictOpenAddr *dictopenaddr;// 初期化されていないポインタが指す(不正な)要素に

dictopenaddr->H = DDp;// 値を
dictopenaddr->B = len;// 代入しています

Comments

[Mellonn]

修正して,ポインタdictopenaddrもmallocで初期化しておきました

[episteme]

それにより問題は解決しなかったってことですか?

[Mellonn]

再度修正した質問文にあるように,'Dictionary created!'の出力まではいきましたが,その直後にSegmentation faultが出ました

[episteme]

gdbのいう通り、printf(nchr); が問題なんでしょうよ。
# ...おっと、いつのまにか質問が変わってる

[Mellonn]

switch文は修正しました.
質問内容は解決しました.ありがとうございました.

[episteme]

解決したならcloseしといて。

Answer 4

DictOpenAddr型のメモリ領域を確保したことで解決

Comments

[int32_t]

自分だけの力で解決したのでなければ、他の方による回答からベストアンサーを選んでください。