77625


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

[code]

    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;
    }
    
[/code]

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

[code]

    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;
      }
    }
    
[/code]

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


CC BY-SA 4.0
2021-06-16T14:49:57.647
77600
2021-06-17T08:36:13.577
44216
question
c アルゴリズム
C言語で連結リストの作成をしましたが、要素削除の実装でメモリ解放でトラブルを連発しました。一応動くようにはなりましたが、このコードで問題はあるでしょうか？


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

[code]

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

こうしておくと

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

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


CC BY-SA 4.0
2021-06-17T03:36:34.753
77616
2021-06-17T03:36:34.753
8589
77600
answer


> 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.
[code]

    $ 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.
    
[/code]

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

[code]

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

[code]

    $ 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).
    
[/code]


CC BY-SA 4.0
2021-06-17T08:36:13.577
77625
2021-06-17T08:36:13.577
77600
answer