g********o
发帖数: 30 | 1 问大家一道题，CISCO的。说是要实现一个myMalloc（），每次分配固定的size。固定
的size做起来应该简单不少。解法应该是用两个list，一个记录用过的，一个记录free
的，如果free的有，就把free的头结点去掉，加到used list的头部。假设可以用
malloc一次分配一个MAX_SIZE的大block，如何实现myMalloc和myFree？
这方法是我在事后想到的，不过我在如何初始化这个free list的时候卡住了。请问记
录free list如何初始化，是用n个结点的data来记录每一块内存的位置吗？ |
r*******e
发帖数: 7583 | 2 固定size的相对容易
都不需要额外的list structure，直接在free memory block里做记录
对于每一个free block
在首地址处记录下一个free block的地址，形成一个embedded link list
初始状态：
全局变量FirstFreeBlock指向大block的首地址
对n = MAX_SIZE/size 个blocks，初始化其首地址使其形成链表
myMalloc操作：
rtn = FirstFreeBlock
FirstFreeBlock = FirstFreeBlock->next
return rtn
myFree:
addr->next = FirstFreeBlock
FirstFreeBlock = addr
free
【在 g********o 的大作中提到】
: 问大家一道题，CISCO的。说是要实现一个myMalloc（），每次分配固定的size。固定
: 的size做起来应该简单不少。解法应该是用两个list，一个记录用过的，一个记录free
: 的，如果free的有，就把free的头结点去掉，加到used list的头部。假设可以用
: malloc一次分配一个MAX_SIZE的大block，如何实现myMalloc和myFree？
: 这方法是我在事后想到的，不过我在如何初始化这个free list的时候卡住了。请问记
: 录free list如何初始化，是用n个结点的data来记录每一块内存的位置吗？
|
b******7
发帖数: 92 | 3 #define BLOCK_SIZE 1024
#define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
struct ChunkHead{
ChunkHead * next;
};
#define CHUNK_SIZE ALIGN(sizeof(ChunkHead) + BLOCK_SIZE, sizeof(int))
ChunkHead * firstChunk;
void initChunk(void * addr, size_t size)
{
firstChunk = NULL;
Chunk * pre = NULL;
for(int i = 0; i < size/CHUNK_SIZE; i++)
{
ChunkHead * cur = (ChunkHead *)(addr + i* CHUNK_SIZE);
if( pre != NULL)
pre->next = cur;
else
firstChunk = cur;
pre = cur;
}
if(pre != NULL) pre->next = NULL;
}
void * myMalloc()
{
if(firstChunk == NULL) return NULL;
void * result = firstChunk + sizeof(ChunkHead);
firstChunk = firstChunk->next;
return result;
}
void myFree(void * addr)
{
if(addr == NULL) return;
ChunkHead * cur = (ChunkHead *)(addr - sizeof(ChunkHead));
cur->next = firstChunk;
firstChunk = cur;
} |
g********o
发帖数: 30 | 4
谢谢！
【在 b******7 的大作中提到】
: #define BLOCK_SIZE 1024
: #define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
: struct ChunkHead{
: ChunkHead * next;
: };
: #define CHUNK_SIZE ALIGN(sizeof(ChunkHead) + BLOCK_SIZE, sizeof(int))
: ChunkHead * firstChunk;
: void initChunk(void * addr, size_t size)
: {
: firstChunk = NULL;
|
g********o
发帖数: 30 | 5
谢谢！！！3楼的代码好像正确！
【在 r*******e 的大作中提到】
: 固定size的相对容易
: 都不需要额外的list structure，直接在free memory block里做记录
: 对于每一个free block
: 在首地址处记录下一个free block的地址，形成一个embedded link list
: 初始状态：
: 全局变量FirstFreeBlock指向大block的首地址
: 对n = MAX_SIZE/size 个blocks，初始化其首地址使其形成链表
: myMalloc操作：
: rtn = FirstFreeBlock
: FirstFreeBlock = FirstFreeBlock->next
|
g********o
发帖数: 30 | 6
能不能解释一下没有这句话会怎么样？：
#define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
【在 b******7 的大作中提到】
: #define BLOCK_SIZE 1024
: #define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
: struct ChunkHead{
: ChunkHead * next;
: };
: #define CHUNK_SIZE ALIGN(sizeof(ChunkHead) + BLOCK_SIZE, sizeof(int))
: ChunkHead * firstChunk;
: void initChunk(void * addr, size_t size)
: {
: firstChunk = NULL;
|
b******7
发帖数: 92 | 7 内存对其用的，最常见的按4字节对齐，若不对齐，会导致cpu取数据时多次寻址，效率
有影响。
【在 g********o 的大作中提到】
:
: 能不能解释一下没有这句话会怎么样？：
: #define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
|
y****1
发帖数: 58 | 8 有个疑惑。 谁能解释一下啊？ 谢谢
void initChunk(void * addr, size_t size)
中的 addr 有什么用啊？ 是通过malloc返回的地址吗？
谢谢
【在 b******7 的大作中提到】
: #define BLOCK_SIZE 1024
: #define ALIGN(size,unit) (((size)+(unit-1))/(unit)*(unit))
: struct ChunkHead{
: ChunkHead * next;
: };
: #define CHUNK_SIZE ALIGN(sizeof(ChunkHead) + BLOCK_SIZE, sizeof(int))
: ChunkHead * firstChunk;
: void initChunk(void * addr, size_t size)
: {
: firstChunk = NULL;
|
