0

C言語初心者です。コンパイラはgcc-11.0.1、環境はUbuntu21.0.4です。
表題のとおり、思い立って連結リスト(双方向リスト)を実装してみました。実装したのは、リストの要素を表す構造体、リストの生成、追加、削除を行う関数です。そのうち、要素の削除を行う関数でトラブルが起こりました。
トラブルが発生したコードは以下のとおりです。

struct L {
  int element;
  struct L* prev;
  struct L* next;
};
typedef struct L List;

/* リストの生成 */
List* init_list() {
  List* node = (List*)malloc(sizeof(List));
  node->element = 0;
  node->prev = NULL;
  node->next = NULL;
  return node;
}

void insert_list(List* list, int element, int pos) {/* 省略 */}
void insert_last_list(List* list, int element) {/* 省略 */}
void insert_head_list(List* list, int element) {/* 省略 */}

/* リスト要素の削除 */
void erase_list(List* list, int pos) {
  if(list == NULL) return;
  List* node = list;
  while(pos--) {
    node = node->next;
    if(!node) return;
  }
  if(node->prev) node->prev->next = node->next;
  if(node->next) node->next->prev = node->prev;
  free(node);
  node = NULL;
}

int main(int argc, char* argv[]) {
  List* list = init_list();
  list->element = 1;
  for(int i = 2; i <= 10; i++) {               /* リストに1〜10の値を持つ要素が設定される */
    insert_last_list(list, i);
  }

  List* itr = list;
  do {
    printf("%d\n", itr->element);              /* 1~10が改行区切りで表示された */
  } while(itr = itr->next);

  for(int i=9;i>=0;i--) erase_list(list, i);   /* リスト要素をすべて削除 */

  if(!list) {
    printf("List is deleted.\n");              /* こちらが表示されると期待 */
  } else {
    itr = list;
    do{
      printf("%d\n", itr->element);            /* 実際はこちらが実行され、おかしな値が表示 */
    } while(itr = itr->next);
  }
  return 0;
}

main関数内のlistには、erase_list内でNULLが代入されることを期待しましたが、printfで出力すると、明らかにNULLでないアドレス値が表示されました。
見返すと、erase_listの引数として、listをポインタ渡ししなければならないと気づき、以下のようにerase_listを変更しました。結果としては、期待通り1~10が改行区切りで表示された後、"List is deleted."が表示されました。

void erase_list(List** list, int pos) {
  if(list == NULL) return;
  List* node = *list;
  while(pos--) {
    node = node->next;
    if(!node) return;
  }
  if(node->prev) node->prev->next = node->next;
  if(node->next) node->next->prev = node->prev;
  if(!node->prev && !node->next) {     /* prevもnextもNULLなら要素は一つなので、引数で渡されたlistを解放 */
    free(*list);
    *list = NULL;
  } else {                     /* 二重解放しないよう、elseで実行する
    free(node);
    node = NULL;
  }
}

質問は2点です。
1.この変更によって、一応は想定の動作をしているのですが、このコードではどこかでメモリリークはしていないのでしょうか?具体的には、free(node)とfree(*list)によって、リスト要素のために確保したメモリは解放されているのでしょうか?
2.すべてのリスト要素が削除されたときに、先頭要素のアドレスが解放されてかつmain関数内のポインタlistがNULLに設定されることを想定して上記のコード変更をしましたが、これを実現するためのよりスマートな実装方法はありますでしょうか?

2 件の回答 2

2

1.この変更によって、一応は想定の動作をしているのですが、このコードではどこかでメモリリークはしていないのでしょうか? 具体的には、free(node)free(*list) によって、リスト要素のために確保したメモリは解放されているのでしょうか?

gcc には -fsanitize=leak というオプションがあります。

gcc(1)

-fsanitize=leak

 Enable LeakSanitizer, a memory leak detector. This option only matters for linking of executables and the executable is linked against a library that overrides "malloc" and other allocator functions. See https://github.com/google/sanitizers/wiki/AddressSanitizerLeakSanitizer for more details. The run-time behavior can be influenced using the LSAN_OPTIONS environment variable.

$ lsb_release -d
Description:    Ubuntu 21.04
$ gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1) 10.3.0

$ gcc -fsanitize=leak -Wall -Wextra -g -o list list.c
$ ./list
1
:
10
List is deleted.

ここで、最後のノードは free() しない様にしてコンパイル・実行してみます。

for(int i=9;i>=0;i--) erase_list(&list, i);   /* リスト要素をすべて削除 */
// 変更
for(int i=9;i>0;i--) erase_list(&list, i);
$ gcc -fsanitize=leak -Wall -Wextra -g -o list list.c
$ ./list
     :

=================================================================
==695453==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x7f2e0378b5d1 in __interceptor_malloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:56
    #1 0x55ee26c1521e in init_list list.c:14
    #2 0x55ee26c153cc in main list.c:61
    #3 0x7f2e035b7564 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28564)

SUMMARY: LeakSanitizer: 24 byte(s) leaked in 1 allocation(s).
0

A1. コードを精査する時間が無いのでほかの方にお任せ
A2. 「スマート」の定義次第だと思う。
オイラなら空のとき NULL になるような線形リストだけを保持してもあまりうれしくないと思うので、次のようなリスト管理クラス(構造体)を用意する、んではないかな・・・

struct list_manager_type {
    list* top; ///< 先頭要素
    list* bot; ///< 末尾要素
    size_t count; ///< 要素数
};

こうしておくと

  • list* 以外に list_manage_type 分の微小なメモリオーバーヘッドが増える
  • 末尾追加に O(n) のコストがかからない
  • 個数把握に O(n) のコストがかからない
  • リストが空でも list_manage_type は空(NULL)にならないので実装の際に楽できる

リストを使う側からすると、空のリストを特別扱いしたくはないので、その辺の泥臭いあたりを list_manage_type に押し付けることで 使う側は手を抜く ことができるほうがスマート鴨。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。