3

双方向リンク リスト データ構造を使用して、バッファー マネージャーに置換ポリシーを実装しようとしています。

しかし、私の C プログラムには連結リスト ライブラリがないため、データ構造を自分で定義しただけです。

問題は、二重リンクリストを使用するために[動的?]メモリ割り当てを避けることはできますか?

palloc()の代わりに使用する利点は何malloc()ですか?

4

1 に答える 1

5

動的メモリ割り当てをまったく使用しなくても、二重リンク リストを確実に作成できます。そうするのは慣習的です。

#include <stdio.h>
#include <assert.h>
#include <inttypes.h>

enum { NODEBUG = 0, DEBUG = 1 };

static const int debug = NODEBUG;

typedef struct DList DList;
struct DList
{
    int    data;
    DList *next;
    DList *prev;
};

enum { MAX_DLIST = 100 };
struct DList dlist[MAX_DLIST];

static void add_node(DList *head, DList *node)
{
    assert(head != 0 && node != 0);
    if (head->next == 0)
    {
        assert(head->prev == 0);
        head->next = node;
        head->prev = node;
        node->next = head;
        node->prev = head;
    }
    else
    {
        assert(head->prev != 0);
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
}

static void diagnode(DList *node)
{
    if (debug)
        printf(" (T = 0x%.12" PRIXPTR ", N = 0x%.12" PRIXPTR ", P = 0x%.12" PRIXPTR ")\n",
               (uintptr_t)node, (uintptr_t)node->next, (uintptr_t)node->prev);
}

static void print_list(DList *head)
{
    assert(head != 0);
    printf("List:");
    if (head->next != 0)
    {
        DList *node;
        int counter = 0;
        if (debug)
            printf("\nHEAD");
        diagnode(head);
        for (node = head->next; node != head; node = node->next)
        {
            printf(" %3d", node->data);
            diagnode(node);
            assert(counter++ < MAX_DLIST);
        }
    }
    printf(" <EOL>\n");
}

int main(void)
{
    DList head = { 0, 0, 0 };

    for (int i = 0; i < MAX_DLIST; i++)
    {
        dlist[i].data = (i * 13 + 7) % 100;
        add_node(&head, &dlist[i]);
        if (debug)
            print_list(&head);
    }
    print_list(&head);
}

目に見えるメモリ割り当てではありません！データ バッファーの固定配列があるバッファー マネージャーのようなものがあるが、LRU (Least-Recently Used) 置換ポリシーが必要な場合は、この変形を使用できます。この例のように双方向にリンクされたリスト構造にデータを直接配置する代わりに、data要素はバッファー プール内のエントリを指します。その後、リストがリンクされているメインのデータ構造を変更することなく、リストのエントリを追加および削除できます。

がプールされたメモリ アロケータである場合palloc()、それを使用する利点はmalloc()、特定のプールに割り当てられたすべてのメモリを 1 回の関数呼び出しで解放できることです。個別のすべての解放を自分で管理する必要はありません。ときどき、プール アロケータは、別のメモリ割り当てよりも効率的malloc()です。固定サイズの構造体の大きな配列を割り当ててから、要求に応じてエントリを分配することで、割り当ての数を減らし、それによってオーバーヘッドの量を減らすことができます。

于 2012-10-20T18:48:20.443 に答える