パスワードを忘れた? アカウント作成

tarosuke (2403) の日記

2005 年 01 月 28 日
午前 03:37

talosという名の俺OS

n木の管理アルゴリズムが固まる。ページとの連携がまーだあやふやだがなー。詳しくは後で。とりあえず判定するのは、その階層で複数のブロックを必要とするかどうかとそれだけの連続した空きがあるかどうか、空きブロックがあるかどうか、サブブロックに納まるかどうか、先頭ブロックが空いててそこに納まるかどうか、の順番。

まー、これだけ書いときゃ思い出せるだろ。

--
って思ったんだけど...

「サブブロックに収まるかどうか」判定するのではなく「ブロックに割り当てたと仮定して、余りがサブブロックのサイズを越えているかどうか」を判定する。これで全サブブロックを使ってしまうときはブロックを割り当てることになる。

...ん~。なーんかスマートじゃないな...

サブブロック判定をなしにして再帰に持ち込んで「要求サイズが全ブロックを使うときは戻り値で通知」。

...まだまだ無駄が...

先頭ブロックが入ると領域が連続でなくなるので後ろの空きブロックから割り当て。余りが最小ブロックサイズを越えている間は再帰して領域を分割。

...これかな?無駄が最小になるし。
# なーんか別の分野のアルゴリズムに酷似してるなぁ...立体の境界を8分割するアレに...

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

人生の大半の問題はスルー力で解決する -- スルー力研究専門家

処理中...