csapp：malloc lab 思路

感觉好像没怎么写过lab，一方面是之前lab也没啥好写的，另一方面也是大概老师也不让外传。。

因此对于malloc lab也只是说一些high level的思路和做法（虽然好像还是并不能得到满分ww（只有99雾？妙妙妙，果然还是大佬nb，他终于满了qwq

啊曾经说过绝不写平衡树（必然可以用其他做法替代？），结果这里破防了呜呜呜（卡空间，无stl自闭了
不过至少练了一次treap（至少以后treap还会写点了？qwq

嗯这个文章有个副标题就是“自己选择的路，跪着也要走完”

<del>就是听了第一个a的人（Joker）（啊不他就是安大爷！）的鬼话，入了邪教大坑，写了平衡树，结果全世界链表99+？（果然人如其名。。。</del>

看了下系统底层libc实现也是用链表做的？（虽然并没有怎么看懂，希望如果有哪位大佬看懂了，给我讲一讲qwq

https://hanfeng.ink/post/understand_glibc_malloc/

不过入了平衡树的坑，爬也是要爬完的！

（中间写了无数版本（竟然都没有样例分高呜呜

写之前认真看一遍书感觉是非常有必要的（真是血与泪的教训
写的时候啥也没管，上来直接莽，走了好多弯路qwq（的确有很多优化方法书中已经讲了ww

其实代码还是比较好想（就是debug自闭了他大概占了我95%的时间w

具体实现就是我们考虑想找bestfit，那么这个在链表上最劣O(n)?（好像什么方法都必须最劣O(n)，但似乎极难卡掉qwq
那么我们考虑更优的稳定做法：平衡树（treap）！我们可以稳定在O(logn)时间内找到后继节点。
我们基于平衡树可维护插入删除和查找的性质，将每个free块都放入平衡树中，这样我们可以直接查询和取出 ，但是此时会有非常多的重复元素，一个很简单的思想，就可以把所有重复元素放到同一个点中，维护一个链表，即平衡树维护大小为size的双向链表头即可
这个时候我们考虑删除指定节点就不需要在平衡树上删除，直接在链表删除即可，除非链表清空，我们再在平衡树上删除
插入同理，我们只有查询之后该点不存在才在平衡树上插入（这样省了很多常数

那么这时候再考虑进一步优化时间，我们考虑对小数据（设置size<=80）直接记录对应链表，而不存在线段树中 （因为我们很有可能经常产生和合并这种小碎片

对于平衡树采取尽量不旋转（这样红黑树可能会更好？），因为我们发现旋转的代价较大，即要更新的信息较多（实际测试反而更慢w

第二个时间优化：我们发现频繁sbrk是非常耗时的，那么我们考虑一次扩展一段空间，然后不够用再继续扩充

这里我们均衡了时间和空间，发现400附近的值都还行？（可能是我平衡树常数太大了呜呜呜

（一个magic number：对于数据一个测试点把448变成512效果极佳？

空间的优化：

我们首先发现内存是小于2^32字节的，那么也就是说我们完全可以只存偏移量即可，这样我们就可以将地址压缩为4字节
其次参考csapp书中讲解，footer是可以吞掉的（即我们利用header储存前一块是否use），以及和header共用8字节对齐

合并空闲块：我们对于每次add操作（即产生新的空闲块）都尝试合并相邻的块，（我们这里只考虑前一块和后一块）如果能合并则合并在一起再执行add操作

匹配后分割：我们对于bestfit之后可能会有多余空闲块，那么我们对于>8字节的块直接插入维护的信息之中，那么我们对于8字节的块直接保存原位，等待之后的合并操作即可

一个小优化：每次新sbrk判一下前面块是不是free（加上这个就满了？qwq

具体信息存储：

分配块：

我们对于头部4字节存储信息，即为 （块大小(size)|preUSE(0x2 or 0x0)|USE(0x1)）， 因为我们保证了数据8字节对齐，因此块大小后三位必为0，因此我们可以利用来存储信息

空闲块：

头部4字节信息为 （块大小(size)|preUSE(0x2 or 0x0)|USE(0x0)），尾部4字节信息为指向头部的指针的偏移量
中间信息分为两大类：（以下每一块为4字节(以”|“分割)，从头部之后开始连续空间，以下不特殊说明所有指针全为偏移量）

1）fastbin(size<=80)：
对应链表pre指针 | 对应链表next指针

2）largebin(size>80):
1.平衡树节点：（注：rand后来取消设为0了）
平衡树随机rand | 节点左儿子指针 | 节点右儿子指针 | 对应链表pre | 对应链表next | 平衡树上的父亲指针
2.对应链表节点：
空 | 空 | 空 | 对应链表pre | 对应链表next | 空