第20章 考验

是啊，所以需要一些新东西了。

李林握了握拳头，闭上眼睛，回想起这些天来自己的所学所思。

首先，他想到的是自己在现代编程中见过的——

內存对齐技术。

对齐到2的冪次，用地址本身来编码信息。

再结合之前胡云程提过的“细胞”，两个思路撞在一起，解法也就应运而生了。

伙伴算法。

將內存按2的冪次分割成块。

当请求来临，找到刚好大於等於请求大小的块。

如果块太大，就一分为二，“伙伴对伙伴”，直到大小合適。

回收的时候，检查伙伴是否也空閒，如果是就合併回去。

最关键的是，计算伙伴地址不需要遍歷，不需要查表。

只需要一次位运算。

於是，李林在方格纸上重新画了一遍。

这次不再是长长的炼表，而是一棵二叉树。

每个节点都有它的伙伴，每个伙伴都在一个固定的位置上等它。

他用位运算代替了浮点和除法，用地址本身作为定位伙伴的坐標。

方格纸上，一棵由箭头组成的二叉树缓缓展开。

从根到叶，从小到大，每一对伙伴节点都互相呼应。

里奇第一次露出了惊讶的表情。

他盯著那张方格纸，沉默了好一会儿，才呢喃道，

“不是炼表，是树吗……好，太好了。”

里奇不由自主地鼓起掌来，抬起头看著李林，

“能做到这一步，你其实已经算是通过考验了。”

李林闻言，还没来及高兴，就听到里奇的后半句——

“但是，孩子，我不知道你来自哪里、也不知道你要去往何方。”

李林：？

不是，你这话说的就好像……

李林皱起眉头，下意识后退了一步。

里奇笑了笑，眼中闪过一道精光，

“我唯一知道的事情是，你，真的让我兴奋起来了。”

【检测到考验已通过，即將脱离模擬考验……】

“哦，真是有趣，这也是计算机的一种吗？”

隨著里奇轻轻挥手，李林眼前蓝色的光幕竟然消失了——

【&%*#￥%%】

系统提示变成了一串乱码。

“不要著急，再陪我待会儿吧，孩子。”

考验没有结束。

“速度可以了。”

里奇敲了几下键盘，方格纸上又起了变化。

有几块內存被標记为“已分配”，每一块上面都掛著一个指针。

“但我的同事不小心写了一段代码，错误地释放了同一个对象两次。”

free(ptr); free(ptr);

同一块內存，被释放了两次。

一瞬间，方格纸被染成血红。

第二次释放触发了已经合併的伙伴节点，指针指向了已经被重新分配出去的地址。

错误像连锁闪电一样从一个节点蔓延到所有节点，整棵二叉树开始崩塌。

那些串联的箭头一根接一根地断裂、消散。

“你该如何应对呢？”

不是，哥们儿。

什么叫考完试，考官拉著我不让走啊？

李林额头微微冒汗。