関数ポインタとコールバック関数

JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワードが出てきているが、この意味を正しく理解しているだろうか？

このような (function()…)は、無名関数と呼ばれている。(=>を使った書き方はアロー関数と呼ばれている)　これは「関数を引数として渡す機能」と、「一度しか使わないような関数にいちいち名前を付けないで関数を使うための機能」であり、このような機能は、関数を引数で渡す機能はC言語では関数ポインタと呼ばれたり、新しいプログラム言語では一般的にラムダ式などと呼ばれる。

// JavaScriptの無名関数の例 3+4=7 を表示
console.log( (function( x , y ) {
                 return x + y ;
              })( 3 , 4 ) ) ; // 無名関数
console.log( ((x,y) => {
                 return x + y ;
              })( 3 , 4 ) ) ; // アロー関数(ラムダ式)

C言語の関数ポインタの仕組みを理解するために、以下のプログラムを示す。

int add( int x , int y ) {
   return x + y ;
}
int mul( int x , int y ) {
   return x * y ;
}
void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = add ;               // f = add( ... ) ; ではないことに注意
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
                 // f( 3 , 4 ) と書いてもいい
   f = mul ;
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}

このプログラムでは、関数ポインタの変数 f を定義している。「 int (*f)( int , int ) ; 」 は、“int型の引数を2つ持つ、返り値がint型の関数”へのポインタであり、「 f = add ; 」では、f に加算する関数addを覚えている。add に実引数を渡す()がないことに注目。C言語であれば、関数ポインタ変数 f には、関数 add の機械語の先頭番地が代入される。

そして、「 (*f)( 3 , 4 ) ; 」により、実引数を3,4にて f の指し示す add を呼び出し、7 が答えとして求まる。

こういう、関数に「自分で作った関数ポインタ」を渡し、その相手側の関数の中で自分で作った関数を呼び出してもらうテクニックは、コールバックとも呼ばれる。コールバック関数を使うC言語の関数で分かり易い物は、クイックソートを行う qsort() 関数だろう。qsort 関数は、引数にデータを比較するための関数を渡すことで、様々な型のデータの並び替えができる。

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

// 整数を比較するコールバック関数
int cmp_int( int* a , int* b ) {
   return *a - *b ;
}
// 実数を比較するコールバック関数
int cmp_double( double* a , double* b ) {
   double ans = *a - *b ;
   if ( ans == 0.0 )
      return 0 ;
   else if ( ans > 0.0 )
      return 1 ;
   else
      return -1 ;
}

// ソート対象の配列
int    array_int[ 5 ] = { 123 , 23 , 45 , 11 , 53 } ;
double array_double[ 4 ] = { 1.23 , 12.3 , 32.1 , 3.21 } ;

void main() {
   // 整数配列をソート
   qsort( array_int , 5 , sizeof( int ) ,
          (int(*)(const void*,const void*))cmp_int ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~この分かりにくい型キャストが必要なのがC言語の面倒な所
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%d\n" , array_int[ i ] ) ;
   // 実数配列をソート
   qsort( array_double , 4 , sizeof( double ) ,
          (int(*)(const void*,const void*))cmp_double ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%f\n" , array_double[ i ] ) ;
}

無名関数

コールバック関数を使っていると、データを比較するだけの関数とか簡単な短い処理が使われることが多い。こういった処理を実際に使われる処理と離れた別の場所に記述すると、プログラムが読みづらくなる。この場合には、その場で関数の名前を持たない関数(無名関数)を使用する。(C++の無名関数機能は、最近のC++の文法なのでテストには出さない)

void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = []( int x , int y ) { return x + y ; } ; // add を無名関数化
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7

   // mul を無名関数にしてすぐに呼び出す3*4=12 
   printf( "%d¥n" , []( int x , int y ) { return x * y ; }( 3 , 4 ) ) ;
   // メモ：C++11では、ラムダ式=関数オブジェクト
   //      C++14以降は、変数キャプチャなどの機能が追加されている。
}

C++の変数キャプチャとJavaScriptのクロージャ

JavaScript のクロージャ

JavaScriptにおいて、関数オブジェクトの中で、その周囲(レキシカル環境)の局所変数を参照できる機能をクロージャと呼ぶ。クロージャを使うことでグローバルな変数や関数の多用を押さえ、カプセル化ができることから、保守性が高まる。

// JavaScriptにおけるクロージャ
function foo() {
   let a = 12 ; // 局所変数
   console.log( (function( x , y ) {
                    return a + x + y ;  // 無名関数の外側の局所変数aを参照できる
                 })( 3 , 4 ) ) ;
}
foo() ;

C++の変数キャプチャ

C++でも無名関数などでクロージャと同様の処理を書くことができるようにするために変数キャプチャという機能がC++14以降で使うことができる。

// C++のラムダ関数における変数キャプチャ
void main() {
   int a = 12 ;
   printf( "%d\n" ,
           [a]( int x , int y ) {  // 変数キャプチャ[a]の部分
              return a + x + y ;   // 局所変数aをラムダ関数内で参照できる。
           }( 3 , 4 ) ) ;
   return 0 ;
}

Javaでラムダ式を使う例

Javaでも Java8 以降でラムダ式の機能が使えるようになっている。以下のように、ArrayList や Array の全要素に対して処理を行う forEach() メソッドでは、各要素に対して実行する関数を、無名関数として渡すことで、ループを回す繰り返し文を使わずにプログラムを記述できる。

// ArrayList<> の forEach() メソッド (Google Geminiの生成した例)
import java.util.List ;
import java.util.ArrayList ;

public class ForEachExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        // forEachを使ってリストの要素を出力
        names.forEach( name -> System.out.println(name) );
    }               // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 無名関数(ラムダ式)
}                   // 　　型推論のおかげで name の変数宣言も書く必要がない...
                    //    names.forEach( (String name) -> System.out.println( name ) ) ;
-------------------------------------------------------------------------------------
// Array の forEach() メソッド
import java.util.Arrays ;

public class ForEachExample2 {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        // 配列の要素を2倍にして出力
        Arrays.stream(numbers).forEach( number -> System.out.println(number * 2) );
    }                                // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 無名関数(ラムダ式)
}

Javaでは、ラムダ式は 関数型インタフェースと組み合わせて使う必要がある。forEach() メソッドは、Consumer という関数型インタフェースを持ち、引数に書いたラムダ式は、関数型インタフェースの実装として扱われている。
(JavaScriptみたいに、let f = (x) => { return x*x ; } のような単純なラムダ式は使えない)

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

排他処理の実装方法

排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。

ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)

• C言語でのファイルロック(共有ロック,排他ロックの機能あり)
• 共有ロック：他のプロセスの読み込みは許可するけど、書き込みは禁止。
• 排他(占有)ロック：他のプロセスの読み込みも書き込みも禁止する。
• 使い終わったらアンロック。

セマフォの例としては、カウンタセマフォが使われる。

• 対象資源を使用中のプロセスの数を表す、カウンタを使う。
• 初期値0の状態は、だれも使っていない状態。
• 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。

ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。

ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

1. ロッキング方式(悲観的制御)
   先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。
   • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
     
   • ロックの種類
     ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
     この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
   • 2相ロッキングプロトコル
     トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
2. 時刻印方式/タイムスタンプ方式(楽観的制御)
   データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。

ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のようなデータを保存するためのスタック領域と、new 命令で確保されるヒープ領域についてその使われ方などについて理解する。

C言語やJavaでのメモリ領域(静的領域とスタック領域)

C言語では、データ領域は、定数領域、静的変数領域、スタック領域、ヒープ領域 で構成される。また、変数にはスコープという変数が使える範囲がある。

定数領域は、値が変化しないデータが保存される。

静的変数領域は、プログラムが起動したときに確保され、プログラム終了と共にデータが消される。

スタック領域は、関数が呼び出される時に確保され、関数を抜ける時にデータが消される。関数の引数や関数の局所変数などは、この領域に保存される。

#include <stdio.h>

int x = 123 ;            // 静的大域変数
const int y = 234 ;      // 静的大域変数(定数) 再代入不可

void foo() {
    int b = 345 ;        // 動的局所変数
    b++ ;
    printf( "%d %d\n" , x , b ) ;
}

void bar( int a ) {
    int b = 456 ;        // 動的局所変数
    static int c = 789 ; // 静的局所変数
    x++ ; b++ ; c++ ;
    printf( "%d %d %d\n" , x , b , c ) ;
    foo() ;
}

int main() {
    int z = 890 ;        // 動的局所変数
    bar( z ) ;
    bar( z ) ;
    printf( "%d\n" , z ) ;
    return 0 ;
}

// 実行結果
// 124 457 790
// 124 346
// 125 457 791
// 125 346
// 890

大域変数は混乱の元

以下のようなプログラムでは、foo() を実行すると”0 1 2″ と表示され、main の中で foo() を3回呼び出しているので、”012,012,012″と表示されると勘違いするかもしれない。しかし、xが大域変数(Javaでは大域変数は無いけど)であるため、foo() の処理の中で x=3 となっているため、mainの中では、2回目のループが動かないため、”0 1 2″と表示されるだけである。

こういったように、誰もが使える変数を、どこからでも呼び出せる状態にしておくとプログラムの間違いが発生しやすい。

// C言語での大域変数の問題
int x ;
void foo() { // 0 1 2 と出力
   for( x = 0 ; x < 3 ; x++ )
      printf( "%d\n" , x ) ;
}
int main() {  // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
   for( x = 0 ; x < 3 ; x++ )
      foo() ;
   return 0 ;
}

// Javaでの大域変数の問題
public class Main {
    public static int x = 0 ; // 静的クラス変数
    public static void foo() { // 0 1 2 と出力
        for( x = 0 ; x < 3 ; x++ )
            System.out.println( x ) ;
    }
    public static void main(String[] args) throws Exception {
        for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
            foo() ;
    }
}

こういう場合は、正しく局所変数を用いて、関数内でのみ使う変数 x を宣言すれば、上記のような間違いを防ぐことができる。関数内で宣言される変数は関数に入る度にメモリを確保し、関数を抜ける時にメモリ領域が消される。

// C言語での大域変数の解決のために局所変数を使う
void foo() { // 0 1 2 と出力
   int x ;
   for( x = 0 ; x < 3 ; x++ )
      printf( "%d\n" , x ) ;
}
int main() {  // 0 1 2 を出力する処理を 3回繰り返す
   int x ;
   for( x = 0 ; x < 3 ; x++ )
      foo() ;
   return 0 ;
}

// Javaでの大域変数の解決のために局所変数を使う
public class Main {
    public static void foo() { // 0 1 2 と出力
        int x ;
        for( x = 0 ; x < 3 ; x++ )
            System.out.println( x ) ;
    }
    public static void main(String[] args) throws Exception {
        int x ;
        for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返す
            foo() ;
    }
}

一方で、関数が呼び出された回数を確認したい…という用途であれば、下記のように大域変数を使うこともあるが、これだと x を間違って使われる可能性がある。

int x = 0 ;
void foo() {
   x++ ;
   printf( "%d\n" , x ) ;
}
int main() {
   foo() ;
   foo() ;
   return 0 ;
}

このために、C言語では静的局所変数というのがある。関数内で static で宣言された変数は、その関数の中でしか使えないが、プログラムが起動した時に変数領域が作られ初期化され、プログラムが終了した時にデータ領域が消される。

void foo() {
   static int x = 0 ;
   x++ ;
   printf( "%d\n" , x ) ;
}
int main() {
   foo() ;
   foo() ;
}

Javaでは、プログラムの中でデータが間違ってアクセスされることを防ぐために、大域変数という考え方は存在しない。その代わりにクラス内で共通に利用できる変数ということで、静的なクラス変数が用いられる。static なクラス変数は、クラスがロードされた時点でメモリに確保され、プログラム終了まで保持される。

public class MyClass {
    public static int count = 0; // クラス変数

    public static void main(String[] args) {
        MyClass.count++; // インスタンスを作らずにアクセス
        System.out.println(MyClass.count);
    }
}

スタック領域

スタック領域は、ここまでに述べた様に「関数を呼び出す際にメモリ領域が確保・初期化され、関数が終わるとメモリ領域は消される。

以下のような main から bar() , foo() が呼び出される処理では、

1. 関数呼び出し時には、戻り番地の保存、実引数の確保が行われ、
2. 関数に入った時点で局所変数の領域が確保される。
3. 関数が終わると、実引数・局所変数の領域が消され、スタックから取り出された戻り番地に処理を移行する。

このような関数呼び出しでは、最後(Last)に確保した変数が最初(First)に忘れればいいというデータなので、Last In First Out の スタック構造が使われる。

ヒープ領域

リスト処理のようなプログラムでは、データを覚える領域は、関数が終わった後も使われる領域なので、局所変数のように「関数が終わったらそのデータの場所が不要になる」といったLast In First Out のようなスタックで管理することは難しい。

データを確保したメモリがどの時点まで使われるのか解らない場合、スタック構造を使うことはできない。こういったデータは、ヒープメモリ(ヒープ領域)を用いる。

C言語であれば、ヒープメモリの場所の確保には malloc() 関数が用いられ、不要となった時に free() 関数でメモリの開放が必要である。free() を忘れたプログラムが、ずっと動いた状態になると再利用されないメモリ領域が発生(メモリリーク)し、その領域が大量になると、他のプログラムに悪影響がでてくる。(最悪、仮想メモリの利用でスワッピングが多発するかもしれない)

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

struct A {        // class A {
    int data ;    //    int data ;
} ;               // }

int main() {
    struct A * ptr = (struct A*)malloc( sizeof( struct A ) ) ;
    // ptr = new A ;

    ptr->data = 123 ;
    // ptr.data = 123 ;
    
    free( ptr ) ;
    // Javaでは free() は不要
    return 0 ;
}

共有の発生したデータの扱い

C言語では、ヒープメモリの管理するには色々と複雑なことが発生する。

例えば、以下のようなリストの和集合のプログラムをC言語とJavaで示す。

このプログラムでは、リスト a, b の和集合を c に代入している。また、不要となったリストを捨てるために list_free() という関数を作成している。ただし Java では、不要となったメモリ領域の開放は不要だが、C言語との対比のために next に null を代入する処理で代用してある。

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

struct List {
    int          data ;
    struct List* next ;
} ;

struct List* newListNode( int x , struct List* p ) {
    struct List* ans = (struct List*)malloc( sizeof( struct List ) ) ;
    if ( ans != NULL ) {
        ans->data = x ;
        ans->next = p ;
    }
    return ans ;
}

void list_print( struct List* p ) {
    for( ; p != NULL ; p = p->next )
        printf( "%d " , p->data ) ;
    printf( "\n" ) ;
}
int find( struct List* p , int key ) {
    for( ; p != NULL ; p = p->next )
        if ( p->data == key )
            return 1 ;
    return 0 ;
}
struct List* list_union( struct List* a , struct List* b ) {
    struct List* ans = a ;
    for( ; b != NULL ; b = b->next )
        if ( !find( a , b->data ) )
            ans = newListNode( b->data , ans ) ;
    return ans ;
}
void list_free( struct List* p ) {
    if ( p != NULL ) {
        list_free( p->next ) ;
        printf( "*%d " , p->data ) ;
        free( p ) ;
    }
}
int main(void){
    struct List* a = newListNode( 11 , newListNode( 22 , NULL ) ) ;
    struct List* b = newListNode( 11 , newListNode( 33 , NULL ) ) ;
    
    struct List* c = list_union( a , b ) ;
    list_print( a ) ;
    list_print( b ) ;
    list_print( c ) ;
    
    list_free( c ) ;
    list_free( b ) ;
    list_free( a ) ;
    
    return 0 ;  // free(): double free detected in tcache 2
                // Aborted (core dumped)
}

• C言語でリストの和集合

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int x , ListNode p ) {
        this.data = x ;
        this.next = p ;
    }
}

public class Main {
    public static void list_print( ListNode p ) {
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    public static boolean find( ListNode p , int key ) {
        for( ; p != null ; p = p.next )
            if ( p.data == key )
                return true ;
        return false ;
    }
    public static ListNode list_union( ListNode a , ListNode b ) {
        ListNode ans = a ;
        for( ; b != null ; b = b.next )
            if ( !find( a , b.data ) )
                ans = new ListNode( b.data , ans ) ;
        return ans ;
    }
    public static void list_free( ListNode p ) {
        if ( p != null ) {
            list_free( p.next ) ;
            System.out.print( "*" + p.data + " " ) ;
            p.next = null ;
        }
    }
    public static void main(String[] args) throws Exception {
        ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
        ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
        
        ListNode c = list_union( a , b ) ; // 33,11,22
        
        list_print( a ) ;
        list_print( b ) ;
        list_print( c ) ;
        
        list_free( c ) ; System.out.println() ;
        list_free( b ) ; System.out.println() ;
        list_free( a ) ;
    }
}

• Javaでリストの和集合

このプログラムを実行すると、c には和集合のリストが出来上がるが、33の先のデータは a とデータの一部を共有している。

この状態で、リスト全体を消すための list_free(c); list_free(b); list_free(a); を実行すると、list_free(c) の時点で a の先のリストは解放されている。このため、list_free(a) を実行すると、解放済みのデータ領域をさらに解放する処理が行われるが、すでに存在していないデータを消す処理が実行できない。

C言語のプログラムを動かすと、プログラム実行時にエラーが発生する。しかし、Java で書かれた「ほぼ同様」のプログラムは問題なく動作する。

参照カウンタ法

上記の問題は、a の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

• データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
• 処理の中で共有が発生すると、参照カウンタをカウントアップする。
• データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。

// 参照カウンタの説明用プログラム
class ListNode {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   ListNode     next ; // 次のポインタ
   ListNode( int x , ListNode p ) {
      this.refc = 0 ;
      this.data = x ;
      this.next = p ;
   }
} ;

public class Main {
   public static ListNode copy( ListNode p ) {
      p.refc++ ;  // 共有が発生したら参照カウンタを増やす。
      return p ;
   }
   // 集合和を求める処理
   public static ListNode list_union( ListNode a , ListNode b )
   {
      ListNode ans = copy( a ) ;
      //             ~~~~~~~~~共有が発生するのでrefc++
      for( ; b != null ; b = b.next )
         if ( !find( ans , b.data ) )
            ans = new ListNode( b.data , ans ) ;
      return ans ;
   }
   public static void list_del( ListNode p ) {  // 再帰で全廃棄
      if ( p != null
           && --(p.refc) <= 0 ) {    // 参照カウンタを減らし
         //   ~~~~~~~~~~
         list_del( p.next ) ;        // 0ならば本当に消す
         free( p ) ;
      }//~~~~~~~~~ Javaでは存在しない関数(説明用) 
   }
   public static void main(String[] args) throws Exception { 
      ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
      ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
      ListNode c = list_union( a , b ) ;

   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( c ) ;
   list_del( b ) ;
   list_del( a ) ;
}

ただし、Java ではこういった処理を記述しなくても、内部で参照カウンタ法を実行しているため、このような処理を書く必要はない。

unix i-nodeで使われている参照カウンタ

unixのファイルシステムの基本的構造 i-node では、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。

以下に、unix 環境で 参照カウンタがどのように使われているのか、コマンドで説明していく。

$ echo a > a.txt
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
          ~~~ # ここが参照カウンタの値
$ ln a.txt b.txt      # ハードリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが増えているのが分かる
$ rm a.txt            # 元ファイルを消す
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが減っている
$ ln -s b.txt c.txt   # シンボリックリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ rm b.txt            # 元ファイルを消す
$ ls -al *.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ cat c.txt           # c.txt は存在するけどその先の実体 b.txt は存在しない
cat: c.txt: そのようなファイルやディレクトリはありません