对于"边界标识法"的一个疑问，感觉foot节点是多余的

cdsfiui

严蔚敏的<<数据结构>>第8.3是将边界标识法，(boundary tag method)，我没搞清楚foot节点到底有什么作用:
既然可分配空间是用双向链表标识的，我们都知道双向聊表可以双向访问，那么当前结点通过llink访问前驱节点，通过rlink访问后继节点，就完全可以了。
那么foot节点存在的意义是什么? 我认为不是必须存在的，因为要求下一个节点的位置，直接llink或者rlink跳转就可以了，为什么还要foot呢?

还请指教!

MMMIX

回复 1# cdsfiui


    确实不是必须的，从图上看，只是为了方便找到空闲块的头。BTW，Glibc malloc 用的就是 boundary tag method，可以找出来参考下。

cdsfiui

回复 2# MMMIX


    要找到空闲块的头，用llink/rlink查找前驱/后继节点就可以了啊，为什么用这个foot能方便查找呢?
    谢谢。

MMMIX

cdsfiui 发表于 2016-07-09 14:06
回复 2# MMMIX

要找到空闲块的头，用llink/rlink查找前驱/后继节点就可以了啊，为什么用这个foot能方便查找呢?

你要是只有一个空闲块的结尾地址呢？没有它的大小，你怎么找到该块的开头？ 例如说在释放一个块的时候，若是要检查是否要和前面的块合并，这时候有 foot 就很方便了，不然的话你还得在空闲列表中搜索一遍。

cdsfiui

回复 4# MMMIX


    看是否要和前面的块合并，我通过llink找到前面块的head，看它的tag就行了。并不需要重新查找一遍空闲块列表吧?
    还是没有太跟上你的节奏，可否继续解释一下?

MMMIX

cdsfiui 发表于 2016-07-09 22:58
回复 4# MMMIX

看是否要和前面的块合并，我通过llink找到前面块的head，看它的tag就行了。并不需要重新查找一遍空闲块列表吧?

我说的前面的块，是在内存（地址）中和当前块挨着的块，不是链表中的前面的块。