わかりました、ここにあるのは、非常によく書かれていないコードの塊です。この投稿で私が行うことは、ソフトウェア考古学と表現するのが最も適切です。
ステップ 1: フォーマットを修正します。
インデントとコンパクトなフォーマットは、誰の役にも立ちません。さまざまなスペースと空の行を挿入する必要があります。コメントは、より読みやすい方法で記述できます。私はそれを修正することから始めます。
同時に、ブレース スタイルを K&R スタイルから変更しています。K&R ブレース スタイルが許容されることに注意してください。これは、私の個人的な好みにすぎません。もう 1 つの個人的な好みは、指している型の隣にポインタ用の * を書くことです。ここでは、(主観的な) スタイルの問題については議論しません。
また、 の型定義Headerは完全に読み取り不能であり、抜本的な修正が必要です。
そして、完全にあいまいなものを見つけました: 関数内で関数プロトタイプを宣言しているようです。Header* morecore(unsigned);. これは非常に古く、非常に貧弱なスタイルであり、C でこれが許可されているかどうかさえわかりません。その関数が何をするにしても、その行を削除してみましょう。他の場所で定義する必要があります。
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* malloc (unsigned nbytes)
{
Header* p;
Header* prevp;
unsigned nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
if ((prevp = freep) == NULL) /* no free list yet */
{
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
さて、実際にコードを読むことができるかもしれません。
ステップ 2: 広く認識されている悪い慣行を取り除く。
このコードは、今日では悪い習慣とみなされているものでいっぱいです。これらはコードの安全性、可読性、およびメンテナンスを危険にさらすため、削除する必要があります。私と同じ慣行を説いている権威への参照が必要な場合は、広く認識されているコーディング標準MISRA-Cを調べてください。
次の悪い慣行を見つけて削除しました。
1)unsignedコードを入力するだけで混乱が生じる可能性があります。これはプログラマーによるタイプミスですか、それとも意図的に書いたものunsigned intですか? unsignedすべてをに置き換える必要がありunsigned intます。しかし、それを行うと、このコンテキストでさまざまなバイナリ データのサイズを指定するために使用されることがわかります。そのような場合に使用する正しい型は C 標準型size_tです。これも本質的には unsigned int ですが、特定のプラットフォームに対して「十分な大きさ」であることが保証されています。このsizeof演算子は type の結果を返しますsize_t。C 標準の実際の malloc の定義を見ると、それはvoid *malloc(size_t size);です。したがってsize_t、使用する最も正しいタイプです。
2) stdlib.h に存在するものと同じ名前を独自の malloc 関数に使用するのは悪い考えです。stdlib.h をインクルードする必要がある場合は、面倒です。経験則として、独自のコードで C 標準ライブラリ関数の識別子名を使用しないでください。名前を kr_malloc に変更します。
3) コードは、すべての静的変数がゼロに初期化されることが保証されているという事実を悪用しています。これは C 標準で明確に定義されていますが、かなり微妙な規則です。すべての statics を明示的に初期化して、誤って初期化するのを忘れていないことを示します。
4) 条件内の代入は危険で読みにくい。これは、古典的な = vs == バグなどのバグにつながる可能性があるため、可能であれば回避する必要があります。
5) 評価の順序が原因で、同じ行に複数の割り当てがあると読みにくく、危険な場合があります。
6) 同じ行に複数の宣言があると、読みにくく危険です。データとポインターの宣言を混在させると、バグが発生する可能性があるからです。各変数は、常に独自の行で宣言してください。
7) すべてのステートメントの後に常に中括弧を使用します。そうしないと、バグ バグ バグにつながります。
8) 特定のポインター型から void* への型キャストは絶対に行わないでください。これは C では不要であり、そうでなければコンパイラが検出したであろうバグを隠してしまう可能性があります。
9) 関数内で複数の return ステートメントを使用することは避けてください。より明確なコードにつながることもありますが、ほとんどの場合、スパゲッティにつながります。コードのままでは、ループを書き直さないと変更できないので、後で修正します。
10) for ループをシンプルに保ちます。それらには、1 つの init ステートメント、1 つのループ条件、および 1 つの反復が含まれている必要があります。コンマ演算子とすべてを含むこの for ループは、非常にあいまいです。繰り返しになりますが、このループを適切なものに書き直す必要があることに気付きました。次にこれを行いますが、今のところは次のとおりです。
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return p+1;
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
return NULL; /* none left */
}
}
} /* for */
}
ステップ 3: あいまいなループを書き直します。
前述の理由によります。このループは永遠に続くことがわかります。割り当てが完了したとき、またはメモリが残っていないときに、関数から戻ることによって終了します。それをループ条件として作成し、リターンを本来あるべき関数の最後に持ち上げます。そして、醜いコンマ演算子を取り除きましょう。
2 つの新しい変数を紹介します。1 つは結果のポインターを保持するための結果変数で、もう 1 つはループを続行するかどうかを追跡するための変数です。bool1999 年以来 C 言語の一部である型を使用して、K&R の心を吹き飛ばします。
(この変更でアルゴリズムを変更していないことを願っています。変更していないと思います)
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevp->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevp = p;
} /* for */
return result;
}
ステップ 4: このがらくたをコンパイルします。
これはK&Rからのものなので、タイプミスでいっぱいです. sizeof(header)する必要がありますsizeof(Header)。セミコロンが抜けています。それらは、freep、prevp と freeptr、prevptr に対して異なる名前を使用しますが、明らかに同じ変数を意味します。後者の方が実際にはより良い名前だったと思うので、それらを使用しましょう。
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freeptr = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevptr;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
prevptr = freeptr;
if (prevptr == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevptr->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freeptr = prevptr;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freeptr) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevptr = p;
} /* for */
return result;
}
そして今、私たちは、多くの危険な慣行がなくても、コンパイルさえできる、ある程度読みやすく、保守しやすいコードを手に入れました! これで、コードが実際に何をしているのかについて実際に考え始めることができます。
構造体 "Header" は、ご想像のとおり、リンクされたリスト内のノードの宣言です。このような各ノードには、次のノードへのポインタが含まれています。morecore 関数も「ラップアラウンド」もよくわかりません。この関数を使用したことはありませんsbrk。しかし、この構造体で指定されているようにヘッダーが割り当てられ、そのヘッダーに続く生データのチャンクも割り当てられると思います。その場合、実際のデータ ポインターがない理由が説明されます。データは、メモリ内で隣接してヘッダーに続くと見なされます。したがって、ノードごとにヘッダーを取得し、ヘッダーに続く生データのチャンクを取得します。
反復自体は非常に簡単です。一度に 1 つのノードで、単一のリンクされたリストを通過します。
ループの最後で、「チャンク」の最後を1つ過ぎたところを指すようにポインターを設定し、それを静的変数に格納して、次回関数が呼び出されたときにプログラムが以前に割り当てたメモリの場所を記憶できるようにします。
彼らはトリックを使用して、ヘッダーがアラインされたメモリ アドレスになるようにしています。プラットフォームのアラインメント要件に対応するのに十分な大きさの変数とともに、すべてのオーバーヘッド情報をユニオンに格納します。したがって、「ptr」のサイズに「size」のサイズを加えたものが小さすぎて正確な位置合わせができない場合、ユニオンは少なくとも sizeof(Align) バイトが割り当てられることを保証します。C標準では構造体/共用体の自動パディングが義務付けられているため、このトリック全体は今日では時代遅れになっていると思います。