@comment $OpenXM: OpenXM/src/asir-doc/int-parts/gc.texi,v 1.1 2001/04/23 05:45:35 noro Exp $
@chapter メモリ管理

@section メモリ管理機構

@code{risa} におけるメモリ管理は, [Boehm,Weiser] によるものを用いている. 
このメモリ管理機構の特徴は, タグ付けを必要とせず, 自動的にガーベッジコレ
クション(GC) を行なうことである. 従ってユーザは必要な領域を取りっぱなし
にしてよい. 欠点としては, 一回の GC ですべてのガーベッジを回収できるとは
かぎらないことと, コンパクションを行なわないことであるが, 実用上十分な機
能を持つ. メモリ割り当て器に現れるマクロはすべてこのメモリ管理のもとでメ
モリの割り当てを行なっている. GC は, その時点における, スタック, レジス
タ, 静的領域からマーキングを始め, これにより到達できない領域をすべて回収
する. コンパイラの最適化により, 最初領域の先頭を指していたポインタが, 領
域の内部を指している場合にも, GC 正しくその領域が使用中と判断する.

注意すべきことは, 通常の @code{malloc()} により割り当てられた領域内はス
キャンされないことである. よって, @code{malloc()} は, その他の C のライ
ブラリの中から呼ばれる場合を除いて使用は避けなければならない. また, 一つ
の領域は, 複数の領域から参照されている可能性があるため, ユーザが開放する
ことは危険である. ただし, 作業用のバッファなど, 明らかに他からの参照がな
いものに関しては開放して構わない. メモリ管理関係の主な函数は次の通り.

@example
void GC_init()
初期化ルーチン. 起動時に実行する. 

void *GC_malloc(int n)
n bytes の領域を割り当てる. 領域は 0 で初期化される. 

void *GC_malloc_atomic(int n)
ポインタを含むことがないと保証される n bytes の領域を割り当てる.

GC_free(void *p)
p の指す領域を開放する. Risa では, ある領域がどこからどの位指されている
か一般には判断できないので, 通常はこの関数が使用されることはない. 
関数内で割り当てたバッファの開放などに用いることはできる. 
@end example
@noindent
通常は @code{GC_malloc()} を使用するが, 多倍長数用の領域など, 内部にポイ
ンタを含まないことが分かっている領域用に @code{GC_malloc_atomic()} が用
意されている. GC ルーチンは, @code{GC_malloc_atomic()} により割り当てら
れた領域の内部はスキャンしないので, GC の効率が良くなる. 


@section Risa におけるメモリの使用

Risa における各演算関数について共通の振舞いとして, 結果として生成される
object の内部で, 入力である object の各部への参照が行われている可能性
がある, ということがある. 

次の例は, 多項式の加算関数である. この中で, 例えば先頭の項の次数が異なる
場合には, 係数(へのポインタ)がそのまま結果にコピーされている. また, 
引数の一方の次数係数リストの末尾までたどった時に, 一方の次数係数リストが
残っている場合には, その残りがそのまま結果の次数係数リストにつながれる. 

@example
#include "ca.h"

void addp(vl,p1,p2,pr)
VL vl;
P p1,p2,*pr;
@{
  DCP dc1,dc2,dcr0,dcr;
  V v1,v2;
  P t;

  if ( !p1 ) 
    *pr = p2;
  else if ( !p2 ) 
    *pr = p1;
  else if ( NUM(p1) )
    if ( NUM(p2) ) 
      addnum(vl,p1,p2,pr);
    else 
      addpq(p2,p1,pr);
  else if ( NUM(p2) ) 
    addpq(p1,p2,pr);
  else if ( ( v1 = VR(p1) ) ==  ( v2 = VR(p2) ) ) @{
    for ( dc1 = DC(p1), dc2 = DC(p2), dcr0 = 0; dc1 && dc2; )
      switch ( cmpq(DEG(dc1),DEG(dc2)) ) @{
        case 0: 
          addp(vl,COEF(dc1),COEF(dc2),&t);
          if ( t )  @{
            NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc1); COEF(dcr) = t;
          @}
          dc1 = NEXT(dc1); dc2 = NEXT(dc2); break;
        case 1:
          NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc1); COEF(dcr) = COEF(dc1);
          dc1 = NEXT(dc1); break;
        case -1:
          NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc2); COEF(dcr) = COEF(dc2);
          dc2 = NEXT(dc2); break;
      @}
    if ( !dcr0 ) 
      if ( dc1 )
        dcr0 = dc1;
      else if ( dc2 ) 
        dcr0 = dc2;
      else @{
        *pr = 0;
        return;
      @}
    else 
      if ( dc1 ) 
        NEXT(dcr) = dc1;
      else if ( dc2 ) 
        NEXT(dcr) = dc2;
      else 
        NEXT(dcr) = 0;
    MKP(v1,dcr0,*pr);
  @} else @{
    while ( v1 != VR(vl) && v2 != VR(vl) ) 
      vl = NEXT(vl);
    if ( v1 == VR(vl) ) 
      addptoc(vl,p1,p2,pr);
    else 
      addptoc(vl,p2,p1,pr);
  @}
@}
@end example

このように, Risa の演算関数では, 一見不要になった中間的な結果でも, その
部分式が最終結果に用いられていることがあるため, 注意が必要である. 特に, 
配列を書き換える必要がある場合などには, 配列そのものを新しく生成して, 成
分をコピーしてから用いる必要がある.