r*****e
发帖数: 146 | 1 如何实现 malloc？对于面试而言，应该写到什么深度？ 谢谢! |
b***m
发帖数: 5987 | 2 看数据结构与算法内存分配那一章。
【在 r*****e 的大作中提到】
: 如何实现 malloc？对于面试而言，应该写到什么深度？ 谢谢!
|
r*****e
发帖数: 146 | 3 谢谢！ 放狗一搜这个名字的书，中文的英文的，太多了，你说的是 Aho 和 Ullman 写
的那本？ |
b***m
发帖数: 5987 | 4 很多应该都有，我看的是Adam Drozdek写的。
【在 r*****e 的大作中提到】
: 谢谢！ 放狗一搜这个名字的书，中文的英文的，太多了，你说的是 Aho 和 Ullman 写
: 的那本？
|
d*******u
发帖数: 186 | 5 问题是malloc, free很复杂，好像不太可能用30~50行程序实现。
【在 b***m 的大作中提到】
: 很多应该都有，我看的是Adam Drozdek写的。
|
M**u
发帖数: 10158 | 6 最简单的话，用freelist就可以了
其实linux里面也是用brk/sbrk实现的
【在 r*****e 的大作中提到】
: 如何实现 malloc？对于面试而言，应该写到什么深度？ 谢谢!
|
b***m
发帖数: 5987 | 7 对，所以被面上就是撞大运了，偏偏我还遇到过两回。。。
【在 d*******u 的大作中提到】
: 问题是malloc, free很复杂，好像不太可能用30~50行程序实现。
|
y*******g
发帖数: 6599 | 8 看需要怎么实现吧，我记得c programming language那本书也有一个例子关于malloc的
好像没太复杂
【在 d*******u 的大作中提到】
: 问题是malloc, free很复杂，好像不太可能用30~50行程序实现。
|
r*****e
发帖数: 146 | 9 奥，谢谢你推荐的书。既然大牛都遇到了，随手写一个让我们好好观摩学习学习吧:)
【在 b***m 的大作中提到】
: 对，所以被面上就是撞大运了，偏偏我还遇到过两回。。。
|
d*******u
发帖数: 186 | 10 From c programming language:
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
//The Align field is never used; it just forces each header to be
aligned on a worst-case boundary.
Align x; /* force alignment of blocks */
};
typedef union header Header;
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
/* free: put block ap in free list */
void free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break; /* freed block at start or end of arena */
if (bp + bp->s.size == p->s.ptr)
{ /* join to upper nbr */
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
}
else
bp->s.ptr = p->s.ptr;
if (p + p->s.size == bp)
{ /* join to lower nbr */
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
up = (Header *) cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
Header *moreroce(unsigned);
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
if ((prevp = freep) == NULL)
{ /* no free list yet */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
//not empty now.
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits)
{ /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else
{ /* allocate tail end */
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
} |
r*****e
发帖数: 146 | 11 谢谢高人指点，好好研读一下。。。
【在 d*******u 的大作中提到】
: From c programming language:
: typedef long Align; /* for alignment to long boundary */
: union header { /* block header */
: struct {
: union header *ptr; /* next block if on free list */
: unsigned size; /* size of this block */
: } s;
: //The Align field is never used; it just forces each header to be
: aligned on a worst-case boundary.
: Align x; /* force alignment of blocks */
|
