Вы, безусловно, можете создать двусвязный список, вообще не используя динамическое выделение памяти; это просто нетрадиционно.
#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 (наименее недавно использованная). Вместо того, чтобы иметь данные непосредственно в структуре двусвязного списка, как в этом примере, элемент data
будет указывать на запись в пуле буферов. Затем вы можете добавлять и удалять записи из списка, ничего не меняя в основной структуре данных, с которой связан ваш список.
Если palloc()
является распределителем памяти в пуле, преимущество его использования по сравнению с malloc()
заключается в том, что вы можете освободить всю память, выделенную для данного пула, с помощью одного вызова функции, вместо того, чтобы самостоятельно управлять всеми отдельными освобождениями. Иногда распределитель пула будет более эффективным, чем отдельное выделение памяти с помощью malloc()
; он может выделять большой массив структуры фиксированного размера, а затем распределять записи по запросу, уменьшая количество выделений и тем самым уменьшая количество накладных расходов.
person
Jonathan Leffler
schedule
20.10.2012