https://yq.aliyun.com/articles/38307
https://yq.aliyun.com/ziliao/132720
http://blog.liyiwei.cn/%E3%80%8A%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA%E3%80%8B%E8%AF%BB%E4%B9%A6%E7%AC%94%E8%AE%B0%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/
为避免系统调用malloc,free, php内核使用内存池来管理已经分配或释放的内存
小内存 数组+链表
大内存 树+链表
存放的是还未使用的内存，以及释放的内存（也可以看做未使用的内存）
有新的内存需要分配时，首先会在 小内存和大内存中查找，如果找不到 再mmap 256K大小的内存， 余下的内存 根据大小 是放到小内存里，还是放到大内存里
假设在大内存里找到了相应的内存，就要把这个结点删除，其实就是二叉有序树的删除，但php相关的源码还是看不懂
如果待删除的结点 同时有左子树和右子树，这时有两种方式
1）查找右子树中最小的结点a，特点就是该 结点 没有 左子树， 假设a的右子树为b,a的父结点为c,那么 c.左子树为b,同时b的父结点为c
2)查找左子树中最大的结点a,特点是该结点没有 右子树，只有左子树，假设 a的左子树为b, a的父结点为c,那么 c的左子树为b,同时b的父结点为c
假设现在的二叉树为
160
/
92
/
84 98
/ /
76 86 96 106
97
删除92 采用第一种方法，在92的右子树中查找最小左值，就是96，同时97做为98的左结点
160
/
96
/
84 98
/ /
76 86 97 106
static inline void zend_mm_remove_from_free_list(zend_mm_heap *heap, zend_mm_free_block *mm_block) { zend_mm_free_block *prev = mm_block->prev_free_block; zend_mm_free_block *next = mm_block->next_free_block; ZEND_MM_CHECK_MAGIC(mm_block, MEM_BLOCK_FREED); if (EXPECTED(prev == mm_block)) { zend_mm_free_block **rp, **cp; rp = &mm_block->child[mm_block->child[1] != NULL]; prev = *rp; if (EXPECTED(prev == NULL)) { } else { while (*(cp = &(prev->child[prev->child[1] != NULL])) != NULL) { prev = *cp; rp = cp; } *rp = NULL; subst_block: ZEND_MM_CHECK_TREE(mm_block); *mm_block->parent = prev; prev->parent = mm_block->parent; if ((prev->child[0] = mm_block->child[0])) { ZEND_MM_CHECK_TREE(prev->child[0]); prev->child[0]->parent = &prev->child[0]; } if ((prev->child[1] = mm_block->child[1])) { ZEND_MM_CHECK_TREE(prev->child[1]); prev->child[1]->parent = &prev->child[1]; } } } }
假设现在的二叉树为
160
/
92
/
84 98
/ /
76 96 106
现在要删除结点92,按上面的代码
rp = &mm_block->child[mm_block->child[1] != NULL]; rp为92的右子树，即98的地址
prev = *rp; prev为8
while (*(cp = &(prev->child[prev->child[1] != NULL])) != NULL) { prev = *cp; rp = cp; }
while( *(cp = &98[1]) != NULL){
prev = 106;
}
prev->parent = mm_block->parent; if ((prev->child[0] = mm_block->child[0])) { ZEND_MM_CHECK_TREE(prev->child[0]); prev->child[0]->parent = &prev->child[0]; } if ((prev->child[1] = mm_block->child[1])) { ZEND_MM_CHECK_TREE(prev->child[1]); prev->child[1]->parent = &prev->child[1]; }
106的父结点 是92的父结点，即106的父结点是160
106的左了树为 92的左子树 即 106的左子结点为84
106的右子树为 92的右子结，即106的右子结点 为98， 是不是不太对劲，这不符合二叉排序树的规则，因为右子树要大于他的父结点的
160
/
106
/
84 98
/ /
76 96
