问题：封装malloc写一个void *malloc16(int _size);使得其的地址刚好是16对其的，也就是说其返回的地址%16==0。然后封装free写一个void free16(void *p);把malloc16分配的空间给回收。。
malloc和free是这么用的。
char *pc=(char*)malloc(1024);
free(pc);
|
这里我想了好一会儿。
第一个想法：分配空间的时候多分配16个空间，然后指向其第一个地址%16==0的地方，把前面多余的空间释放掉。
A：那你怎么释放它？
想了一会儿。发现不能释放。。
再想了一会儿。
第二个想法：在第一个想法基础上。分配空间的时候多分配16个空间，然后找到其第一个地址%16==0的那个地址，用一个结构体保存其malloc分配的值以及malloc16返回的值，free16的时候根据传进来的值来找是否存在分配过这个值。然后找到malloc的这个值，free掉它。
A：怎么保存这个结构体呢。结构体怎么声明？还是只用一个对象
CHC：使用链表或者其他数据结构。
A：用什么数据结构？
CHC：hash每一个malloc16返回值对应的malloc值。
A：这样是可以的。但是能不能不用数据结构？
又想了一会儿。。
CHC：对于每个malloc16保存一个偏移量，通过这个偏移量找到malloc分配的空间。这个偏移量存放在malloc16返回地址的上一位。
A：你怎么确定它的上一位可以用呢？
对哦。。。如果第一个malloc到的值%16==0那上一位不就越界了吗？
想了一会儿。。
CHC：多分配16*2个空间。malloc出来的地址+16之后再往下找第一个%16==0的那个地址。这个地址的前一位一定是可以用的。
A：哦~你的意思是多申请32个空间，然后来保存偏移量，那 最少 多申请多少空间可以达到这个目标。
想了一会儿。。
CHC：多申请17个空间。。malloc出来的那个地址先+1，然后再找第一个%16==0的地址，返回。
A：那能不能只申请16个空间达到这个目标呢？
想了一会儿。。
CHC：如果它malloc到的第一个地址%16==0的话那它上面的那个空间就没法用到啊？那怎么用。。
A：你再想想。。（看了看时间）哦~时间有点紧，这个地址直接加16就可以。
CHC：
(沃日。我个傻x，怎么这里被自己坑到了啊啊啊啊啊！！！！！)
A：那你写个代码吧。。
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
if((int)p%16==0){
q=p+16;
*(q-1)=16;
}
else {
int cnt=0;q=p;
while((int)q%16!=0){
++cnt;
++q;
}
*(q-1)=cnt;
}
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
A：这个if…else…能不能合成一个写。
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=0;q=p;
while((int)q%16!=0){
++cnt;
++q;
}
if(cnt==0){
q=p+16;
}
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
A：就是不用这个方法。不加if能不能优化。
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=0;q=p;
q=q+((int)q%16==0?16:0);
while((int)q%16!=0){
++cnt;
++q;
}
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
A：哦~这样子。。。也算是用到了if。不用这种方法怎么办。
（沃日。怎么感觉好紧张。。）
A：时间有点紧。其实为什么不加1然后再推呢。
（沃日，突然间反应过来了！！！我X。。。我个傻x。。我勒个去！！！自己绕坑自己了！！！好二。。。）
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=1;q=p;
q=q+1;
while((int)q%16!=0){
++cnt;
++q;
}
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
A：其实那个while也是可以优化的。
CHC：我知道。用个公式推出来。
A：对。就是公式推。
面试过后。。
最终版本。。
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=16-(int)p%16;
q=p+cnt;
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
下面是脑补的几个问题。。
add by 2015.9.18
能不能不用%运算？
CHC：
int align16(int _size){
if((_size&0xF)==0)return 0;
return _size&0xF;
}
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=16-align16((int)p);
q=p+cnt;
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
align16能不能不用if？
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=16-((int)p&0xF);
q=p+cnt;
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
cnt能不能不用-，直接求出？
想了一会儿。。
CHC：
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=(0xF&~((int)p&0xF))+1;
q=p+cnt;
*(q-1)=cnt;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
能不能再化简一点？
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
q=p+1;
int cnt=0xF&(-((int)q&0xF));
q=q+cnt;
*(q-1)=cnt+1;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
还能不能再优化？
void *malloc16(int _size){
char *p=(char*)malloc(_size+16),*q;
int cnt=0xF&(~((int)p&0xF));
q=p+cnt+1;
*(q-1)=cnt+1;
return (void*)q;
}
void free16(void * pt){
char *p=(char*)pt;
p=p-*(p-1);
free(p);
}
|
还能化简任何一个部分吗？
