Obstack

概要

• object の stack
• メモリプール(chunk)を用いたメモリ管理パッケージ。
• 本を積み重ねて置いておくようなイメージで、オブジェクトを積み重ねて保存する。
• 一度積み重ねたオブジェクトのアドレスは動かさない。(これ重要)
• オブジェクトの中身を変更することは可能
• オブジェクトを格納するある程度の大きさの領域をchunkと呼ぶ、 chunkの初期サイズは4KBである。
• chunkのサイズは足りなくなったら、サイズを大きくする(grow)ことができる。
• growした場合も、割り当て済みobject のアドレスは維持する。つまり以前のchunkも解放せずにとっておく。

gcc-0.9 での使用用途

• treeでは、ノードの領域をmake_nodeでobstack_allocを使用して確保している。グローバルなbinding_level用のobstack と それ以外のbinding_level 用のobstackの二つを利用している。
• specsファイルの読み込み。

データ構造

 182                                 /* these #defines keep it brief */
 183 #define _Ll struct obstack_chunk
 184 #define _LL (8)                 /* _L length in chars */
 185 
 186 struct obstack_chunk            /* Lives at front of each chunk. */
 187 {
 188   char  *obstack_l_limit;       /* 1 past end of this chunk */
 189   _Ll   *obstack_l_prev;        /* address of prior chunk or NULL */

• obstack_l_0 はオブジェクトの先頭を指すために使う。4なのは32bitにアラインするためだと思う。配列の引数を使っている箇所は無し。

 190   char  obstack_l_0[4];         /* objects begin here */
 191 };

 201 struct obstack          /* control current object in current chunk */
 202 {
 203   long  chunk_size;             /* preferred size to allocate chunks in */
 204   _Ll*  chunk;                  /* address of current struct obstack_chunk */
 205   char  *object_base;           /* address of object we are building */
 206   char  *next_free;             /* where to add next char to current object */
 207   char  *chunk_limit;           /* address of char after current chunk */
 208   int   temp;                   /* Temporary for some macros.  */
 209   int   alignment_mask;         /* Mask of alignment for each object. */
 210 };

API

• 内部でobstack_finishが実行されるAPI

obstack_init (struct obstack *) obstackの初期化 4KBのchunkを確保する。
obstack_alloc (struct obstatc *, int length)  長さを指定してobjectを格納する領域を確保する。中身は未初期化。
obstack_copy (struct obstack * , void *adr , int length) 指定した長さの領域を確保して、その領域に指定したアドレスからデータをコピーする。
obstack_copy0 (struct obstack * , void *adr , int length) 指定した長さの領域を確保して、その領域に指定したアドレスからデータをコピーし、最後にNULL文字(0)を配置する。
obstack_free (struct obstack *, void *obj) objで指定したアドレス以降に確保した領域を解放する。

• 内部でobstack_finishが実行されないAPI

obstack_blank (struct obstatc *, int length) 長さを指定して領域を確保する。中身は未初期化。
obstack_begin () 
obstack_grow () 指定した長さの領域を確保して、その領域に指定したアドレスからデータをコピーする。
obstack_grow0 () 指定した長さの領域を確保して、その領域に指定したアドレスからデータをコピーし、最後にNULL文字(0)を配置する。
obstack_1grow () chunkに１文字追加する。
obstack_room ()
obstack_finish (struct obstack *) 4バイトアラインする。

• 内部API

_obstack_begin ()
_obstack_newchunk ()
_obstack_free ()

• gcc-0.9で使っていないAPI

obstack_1grow_fast ()
obstack_blank_fast ()

ドキュメント

• obstack.h に書いてあるSummary

  98 /* Summary:
  99 
 100 All the apparent functions defined here are macros. The idea
 101 is that you would use these pre-tested macros to solve a
 102 very specific set of problems, and they would run fast.
 103 Caution: no side-effects in arguments please!! They may be
 104 evaluated MANY times!!

ここで定義されているす見せかけの関数はすべてマクロである。 このアイデアは、非常に特定の集合の問題の解決するために事前テスト済みのマクロを使用するということである。そして、このマクロは非常に早く動作する。

注意：引数には副作用のある書き方をしてはいならない。それらは複数回を評価されるかもしれない！

(訳注：引数に hoge++ とか書くと、何回も足されるよ、ってこと)

 105 
 106 These macros operate a stack of objects.  Each object starts life
 107 small, and may grow to maturity.  (Consider building a word syllable
 108 by syllable.)  An object can move while it is growing.  Once it has
 109 been "finished" it never changes address again.  So the "top of the
 110 stack" is typically an immature growing object, while the rest of the
 111 stack is of mature, fixed size and fixed address objects.

これらのマクロは、オブジェクトのスタックを操作する。 各オブジェクトには、小さな人生を開始し、満期まで大きくなることがある。 （音節で単語音節を構築することを検討してください。） オブジェクトが成長している間、オブジェクトは移動することができる。 一度それが "finished" の処理をされたら、再びアドレスを変更することはない。 スタックの最上部は、一般的に未熟な成長中のオブジェクトである。 スタックの残りの部分は成熟し、固定サイズと固定アドレスのオブジェクトである。

 112 
 113 These routines grab large chunks of memory, using a function you
 114 supply, called `obstack_chunk_alloc'.  On occasion, they free chunks,
 115 by calling `obstack_chunk_free'.  You must define them and declare
 116 them before using any obstack macros.

これらのルーチンは、`obstack_chunk_alloc'と呼ばれるあなたが供給する関数(訳注 mallocみたいな関数)を使用して、メモリの大きなchunkをつかむ。 機会に、`obstack_chunk_free'を呼び出すことによって、chunks を解放する。 あなたはそれらを定義して、任意のオブスタックマクロを使用する前に宣言する必要があります。

 117 
 118 Each independent stack is represented by a `struct obstack'.
 119 Each of the obstack macros expects a pointer to such a structure
 120 as the first argument.

それぞれ独立したスタックは‘struct obstack'で表されます。それぞれのobstackマクロは、最初の引数にobstack構造体へのポインタを期待しています。

 121 
 122 One motivation for this package is the problem of growing char strings
 123 in symbol tables.  Unless you are "facist pig with a read-only mind"
 124 [Gosper's immortal quote from HAKMEM item 154, out of context] you
 125 would not like to put any arbitrary upper limit on the length of your
 126 symbols.

このパッケージを作った一つの動機は、シンボルテーブルにあるcharの文字列を成長させる問題である。 あなたは"読み取り専用の心を持ったfacist豚"でない限り、 [出力コンテキストのHAKMEMアイテム154からゴスパーの不滅の引用より] あなたのシンボルの長さに任意の上限を置くのが好きではないと思います。

 127 
 128 In practice this often means you will build many short symbols and a
 129 few long symbols.  At the time you are reading a symbol you don't know
 130 how long it is.  One traditional method is to read a symbol into a
 131 buffer, realloc()ating the buffer every time you try to read a symbol
 132 that is longer than the buffer.  This is beaut, but you still will
 133 want to copy the symbol from the buffer to a more permanent
 134 symbol-table entry say about half the time.

実際には、これは多くの場合は、多くの短いシンボルと少数の長いシンボルを構築することを意味する。 ある時点であなたはそれがどのくらいの長さか分からない記号を読んでいる。 一つの伝統的な方法は、バッファにあなたがバッファより長いシンボルを読み取るしようとするたびにrealloc()をつかってバッファを確保し、にシンボルを読むことである。 これは素晴らしいものですが、あなたはまだバッファから、より恒久的なシンボル·テーブル·エントリにシンボルをコピーすることになるでしょうと、約半分の時間と言う。

 135 
 136 With obstacks, you can work differently.  Use one obstack for all symbol
 137 names.  As you read a symbol, grow the name in the obstack gradually.
 138 When the name is complete, finalize it.  Then, if the symbol exists already,
 139 free the newly read name.

obstacksを使用すると、異なる動作をすることができる。 すべてのシンボル名に対して1つのobstackを使用してください。 シンボルを読み取るように、徐々にobstack内の名前を育てる。 名前が完了したら、それをファイナライズする。 シンボルが既に存在する場合は、その新たに読んだ名前を解放する。

 140 
 141 The way we do this is to take a large chunk, allocating memory from
 142 low addresses.  When you want to build a aymbol in the chunk you just
 143 add chars above the current "high water mark" in the chunk.  When you
 144 have finished adding chars, because you got to the end of the symbol,
 145 you know how long the chars are, and you can create a new object.
 146 Mostly the chars will not burst over the highest address of the chunk,
 147 because you would typically expect a chunk to be (say) 100 times as
 148 long as an average object.

我々がこれを行う方法は、下位アドレスからメモリを割り当て、大きなchunkを確保することです。 あなたはchunkのなかにシンボルを構築したいとき、ちょうどチャンクに現在の "ハイウォーターマーク"の上に文字を追加します。 あなたはシンボルの最後を得たので、文字がどのように長い間知っている。文字の追加が完了したら、あなたは、新しいオブジェクトを作成することができる。 あなたは通常、チャンクは限り平均オブジェクトとして（言う）の100倍であることが期待されるので、ほとんど文字は、チャンクの最上位アドレスにわたって破裂しません。

 149 
 150 In case that isn't clear, when we have enough chars to make up
 151 the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
 152 so we just point to it where it lies.  No moving of chars is
 153 needed and this is the second win: potentially long strings need
 154 never be explicitly shuffled. Once an object is formed, it does not
 155 change its address during its lifetime.

ケースで我々はオブジェクトを構成するのに十分な文字を持っているときに、彼らはすでにCHUNK（保証）内で連続してそう、それがどこにあるか、我々はそれを指して、明確ではありません。 いいえ文字の移動は必要ありません、これは2勝目です：潜在的に長い文字列を明示的にシャッフルされることはありませんが必要です。オブジェクトが形成されると、その有効期間中に、アドレスを変更しない。

 156 
 157 When the chars burst over a chunk boundary, we allocate a larger
 158 chunk, and then copy the partly formed object from the end of the old
 159 chunk to the beggining of the new larger chunk.  We then carry on
 160 accreting characters to the end of the object as we normaly would.

文字がチャンク境界をバーストするとき、我々はより大きなチャンクを割り当ててから、古いチャンクの終わりから新しい大きなチャンクのbegginingの一部に形成されたオブジェクトをコピーします。我々は、我々はnormalyと同じようにオブジェクトの末尾に文字を降着に運ぶ。

 161 
 162 A special macro is provided to add a single char at a time to a
 163 growing object.  This allows the use of register variables, which
 164 break the ordinary 'growth' macro.

特別なマクロが成長するオブジェクトに一度に1つの文字を追加するために設けられている。 これは普通の'成長'マクロを破るレジスタ変数の使用を可能にする。

 165 
 166 Summary:
 167         We allocate large chunks.
 168         We carve out one object at a time from the current chunk.
 169         Once carved, an object never moves.
 170         We are free to append data of any size to the currently
 171           growing object.
 172         Exactly one object is growing in an obstack at any one time.
 173         You can run one obstack per control block.
 174         You may have as many control blocks as you dare.
 175         Because of the way we do it, you can `unwind' a obstack
 176           back to a previous state. (You may remove objects much
 177           as you would with a stack.)
 178 */

Summary

• 我々は大きなchunksを割り当てる。
• 我々は現在のchunkから一度に1つのオブジェクトを刻む。         
• 一度刻まれたオブジェクトが移動することはない。        
• 現在成長しているオブジェクトに対しては、任意サイズのデータ​​を追加してよい。         
• 正確に1つのオブジェクトには、任意の一時点でobstackに成長しています。         
• あなたがコントロールブロックごとにobstackを実行することができます。         
• あなたがあえて、できるだけ多くの制御ブロックを持っている可能性があります。         
• なぜなら我々はそれを行う方法のは、 あなたはobstackを戻って以前の状態に'まき戻す'ことができる。 （あなたは、はるかにあなたは、スタックと同じようにオブジェクトを削除することがあります。）

外部情報

• glibc ドキュメントの Obstacksのページ
  • http://www.gnu.org/software/libc/manual/html_node/Obstacks.html
• Wikipedia の Obstack
  • http://en.wikipedia.org/wiki/Obstack
• メモリー管理の内側
  • http://www.ibm.com/developerworks/jp/linux/library/l-memory/
• Obstacks
  • http://www.cinsk.org/wiki/Obstacks
  • Korean ですが一番分かりやすい解説記事でした。