Runetと英語サイトの両方で、マネージャーのためのシンプルで適切なアイデアを探していました-O（N）アロケーターではなく、適切な記事はまだ見つかりませんでした。 さて、今日はメモリマネージャのより良いアイデアを検討します。継続をcatの下に置きます。
理論
ウィキから：メモリマネージャーは、RAMの割り当てと解放の要求、または（コンピューターアーキテクチャによっては）プロセッサのアドレス空間に特定のメモリ領域を含める要求を処理するコンピュータープログラム（アプリケーションとオペレーティングシステムの両方）の一部です。
この記事を読み続ける前に、私もお勧めします。
Watermakアロケーター
おそらく、すべてのアロケーターの中で最も簡単なのは、Watermark Allocatorです。 その本質はほぼ次のとおりです。メモリ全体がブロックに分割され、ブロックにはこのサイズと前のブロックのサイズ、ブロックのステータス（ビジー/フリー）を含むヘッダーがあり、ブロックのアドレスがわかっているため、O（1）の次と前のブロックのアドレスを取得できます
メモリ割り当て
メモリを割り当てるには、ブロックを実行して、割り当てに必要なメモリのサイズ以上のサイズのブロックを探すだけです。 既に理解したように、O（N）の漸近的な振る舞いは悪いです。メモリ解放
メモリを解放するには、ブロックのステータスを「free」に設定するだけで十分です-O（1）-super！しかし、ご存じのとおり、2つ以上の空きブロックが最適化され、解放されると、隣接するブロックが表示され、1つまたは2つの空きブロックが1つにマージされるホールが形成され始めます。
対数アロケーター
空きブロック間でのみ検索する必要があることを知っています。 無料でのみ実行すると、速度は平均で2倍向上しますが、それでも1つのラインです。 さて、フリーブロックからツリーを整理できる場合、サイズを探してすべてのブロックを実行する必要があるのはなぜですか。 最初は、空きブロックが1つしかないので、バイナリ検索ツリーに空きブロックを追加します。キーはブロックのサイズになります。 したがって、メモリを割り当てるには、必要なサイズ以上のサイズのツリー内のブロックを見つけるだけで十分です。 O（log N）に対して静かにこれを行い、ツリーをたどります。 さらに、ブロックを2つに分割するか、メモリを要求したブロックに完全に渡します。 次に、O（1）のツリーからブロックを削除します。 そして、必要に応じて、残りのブロックをO（log N）の後ろに挿入します。 解放するには、ブロックを挿入し直すだけでよく、断片化を忘れないでください。
単純なツリーを使用する必要はなく、赤黒またはAVLの自己バランスツリーを使用する必要があるのは論理的です。 ブロックツリーを静的配列に格納するか、別の方法でそれを行う方法を見つけることができます。
実際には、コード：
char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); }
幸運と倫理的ハッキング！ 客観的な批判は歓迎します。この記事の目的は、それがアロケーターであると言うことではなく、単純なアロケーターの愚かな実装よりも優れたアロケーターについて話すことです。