我使用以下代码创建一个新节点并将其插入到链表中,随后释放它们。
// the node
struct node
{
int data;
struct node *next;
};
// returns a pointer to a new node with data
struct node *new_node(int data)
{
struct node *node;
node = malloc(sizeof(struct node));
node->data = data;
node->next = NULL;
return node;
}
// insert node at front of list
void push(struct node **head, int data)
{
struct node *node = new_node(data);
node->next = *head;
*head = node;
}
// free the list, deallocate each node's memory
void delete_list(struct node** head)
{
if(*head == NULL)
return;
struct node *next = NULL;
next = (*head)->next;
while(next != NULL)
{
next = (*head)->next;
// print address of the memory released
printf("Freeing %dn", (int)*head);
free(*head);
*head = next;
}
}
现在,结构体在我的机器中是8个字节(4字节的int
和4字节的指针)。现在,我对以下的事情有点不确定,所以请帮助我:
当我顺序调用
push()
时,内存是连续分配的吗?总是这样吗?我猜不可能,因为堆中的内存可以被分片。假设分配的内存是连续的,那么它将间隔8字节,因为
struct
的大小是8字节。在我的机器上,当我打印被释放内存的地址时,每次执行时打印的内存地址间隔为16字节。为什么?Freeing 148025480 Freeing 148025464 Freeing 148025448 Freeing 148025432 Freeing 148025416 Freeing 148025400 Freeing 148025384 Freeing 148025368 Freeing 148025352 <empty list>
现在,如果内存没有连续分配给我们的整数数组(堆非常碎片化,内存需求相当大),并且我们使用指针算术通过每次将地址增加4来处理数组的每个元素(或者无论
int
的大小是多少),我们不应该运行到一些内存不是由我们的程序保留,抛出程序吗?或者运行时环境是否足够聪明来处理这个问题,因为编译器不能,因为它不知道内存将如何分配。操作系统会处理这个问题吗?
每次调用new_node
,它都会调用malloc()
。
你不能(或者不应该)预测malloc()
会在哪里找到你的内存。它依赖于操作系统和运行时。
在特定的操作系统上运行,在某些情况下,您可能会观察到连续调用malloc()
的分配是连续的。但是,这种行为可能会在加载、内核更新、libc实现的更改或所有其他条件下发生变化。
您可以假设单个调用malloc()
分配的内存块是连续的(至少,就程序看到的指针而言)。你的程序不应该假设任何关于连续性的事情。
如果这真的困扰您,您可以在自己的代码中负责更多的内存管理—而不是为每个节点调用malloc()
,而是在开始时调用它并获得更大的内存块。对new_node的后续调用可以使用该块的一部分。如果您用完了该块中的空间,您可以malloc()
另一个块(可能不会与第一个块相邻)或realloc()
来扩展(可能移动)它。
你可能会发现所有这些都让你的代码变得更复杂——这取决于你是否有好处来解决这个问题。Hotspot Java VM的作者基本上是这样做的——他们在执行开始时malloc()
大块内存,然后当Java程序需要内存时,它使用自己的例程来分配该块的一部分,而不是调用malloc()
和free()
。
关于#2,调用malloc
的结果不完全连续的一个原因可能是元数据:当您请求x
字节时,malloc
实现可能会为内部记录进程分配一点额外的内存(标记块的大小,指向其他空闲块的指针等)。因此,对于8字节的请求实际上可能导致内部分配16字节,因此在连续分配之间存在16字节的间隔。
如果使用malloc
分配内存,返回的内存将始终是连续的。
malloc
两次,则不能保证两个分配将被放置在彼此旁边,即使两个malloc
调用相邻也不能保证。
当使用malloc()分配内存时,您会看到内存分配中有1个字大小的差距,即额外分配16个字节。这是正常的,因为这是由于我们可能想要使用free()方法来释放内存。在执行释放操作时,free()方法将额外的空间用作暂存空间。
Let say we have the following 2D array:
1 2 3
4 5 6
7 8 9
数组的起始地址是448(也是'1'的内存地址)那么"1"、"4"、"7"的内存地址分别为448、480、512,计算方法如下:
448 + (3 x 4) + 4 + 16 = 480
Here, we have:
448 - Address of the previous block
3 - Number of columns or number of items in the array
4 - Size of int (I'm assuming the array as integer array)
4 - Extra four bytes because size of int is 4 bytes. So the last int address + 4
16 - As left by the malloc for free() function