libuv源码阅读(3)--heap-inl.h

#ifndef UV_SRC_HEAP_H_
#define UV_SRC_HEAP_H_

#include <stddef.h>  /* NULL */

#if defined(__GNUC__)
# define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
#else
# define HEAP_EXPORT(declaration) static declaration
#endif

struct heap_node {
  struct heap_node* left;
  struct heap_node* right;
  struct heap_node* parent;
};

/* A binary min heap.  The usual properties hold: the root is the lowest
 * element in the set, the height of the tree is at most log2(nodes) and
 * it's always a complete binary tree.
 *
 * The heap function try hard to detect corrupted tree nodes at the cost
 * of a minor reduction in performance.  Compile with -DNDEBUG to disable.
 */
struct heap {
  struct heap_node* min;
  unsigned int nelts;
};

/* Return non-zero if a < b. */
typedef int (*heap_compare_fn)(const struct heap_node* a,
                               const struct heap_node* b);

/* Public functions. */
HEAP_EXPORT(void heap_init(struct heap* heap));
HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
HEAP_EXPORT(void heap_insert(struct heap* heap,
                             struct heap_node* newnode,
                             heap_compare_fn less_than));
HEAP_EXPORT(void heap_remove(struct heap* heap,
                             struct heap_node* node,
                             heap_compare_fn less_than));
HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));

/* Implementation follows. */

HEAP_EXPORT(void heap_init(struct heap* heap)) {
  heap->min = NULL;
  heap->nelts = 0;
}

HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
  return heap->min;
}

/* Swap parent with child. Child moves closer to the root, parent moves away. */
static void heap_node_swap(struct heap* heap,
                           struct heap_node* parent,
                           struct heap_node* child) {
  struct heap_node* sibling;
  struct heap_node t;

  t = *parent;
  *parent = *child;
  *child = t;

  parent->parent = child;
  if (child->left == child) {
    child->left = parent;
    sibling = child->right;
  } else {
    child->right = parent;
    sibling = child->left;
  }
  if (sibling != NULL)
    sibling->parent = child;

  if (parent->left != NULL)
    parent->left->parent = parent;
  if (parent->right != NULL)
    parent->right->parent = parent;

  if (child->parent == NULL)
    heap->min = child;
  else if (child->parent->left == parent)
    child->parent->left = child;
  else
    child->parent->right = child;
}

HEAP_EXPORT(void heap_insert(struct heap* heap,
                             struct heap_node* newnode,
                             heap_compare_fn less_than)) {
  struct heap_node** parent;
  struct heap_node** child;
  unsigned int path;
  unsigned int n;
  unsigned int k;

  newnode->left = NULL;
  newnode->right = NULL;
  newnode->parent = NULL;

  /* Calculate the path from the root to the insertion point.  This is a min
   * heap so we always insert at the left-most free node of the bottom row.
   */
  path = 0;
  for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
    path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */
  parent = child = &heap->min;
  while (k > 0) {
    parent = child;
    if (path & 1)
      child = &(*child)->right;
    else
      child = &(*child)->left;
    path >>= 1;
    k -= 1;
  }

  /* Insert the new node. */
  newnode->parent = *parent;
  *child = newnode;
  heap->nelts += 1;

  /* Walk up the tree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.
   */
  while (newnode->parent != NULL && less_than(newnode, newnode->parent))
    heap_node_swap(heap, newnode->parent, newnode);
}

HEAP_EXPORT(void heap_remove(struct heap* heap,
                             struct heap_node* node,
                             heap_compare_fn less_than)) {
  struct heap_node* smallest;
  struct heap_node** max;
  struct heap_node* child;
  unsigned int path;
  unsigned int k;
  unsigned int n;

  if (heap->nelts == 0)
    return;

  /* Calculate the path from the min (the root) to the max, the left-most node
   * of the bottom row.
   */
  path = 0;
  for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
    path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */
  max = &heap->min;
  while (k > 0) {
    if (path & 1)
      max = &(*max)->right;
    else
      max = &(*max)->left;
    path >>= 1;
    k -= 1;
  }

  heap->nelts -= 1;

  /* Unlink the max node. */
  child = *max;
  *max = NULL;

  if (child == node) {
    /* We're removing either the max or the last node in the tree. */
    if (child == heap->min) {
      heap->min = NULL;
    }
    return;
  }

  /* Replace the to be deleted node with the max node. */
  child->left = node->left;
  child->right = node->right;
  child->parent = node->parent;

  if (child->left != NULL) {
    child->left->parent = child;
  }

  if (child->right != NULL) {
    child->right->parent = child;
  }

  if (node->parent == NULL) {
    heap->min = child;
  } else if (node->parent->left == node) {
    node->parent->left = child;
  } else {
    node->parent->right = child;
  }

  /* Walk down the subtree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.  If the parent is bigger,
   * swap it with the smallest child.
   */
  for (;;) {
    smallest = child;
    if (child->left != NULL && less_than(child->left, smallest))
      smallest = child->left;
    if (child->right != NULL && less_than(child->right, smallest))
      smallest = child->right;
    if (smallest == child)
      break;
    heap_node_swap(heap, child, smallest);
  }

  /* Walk up the subtree and check that each parent is less than the node
   * this is required, because `max` node is not guaranteed to be the
   * actual maximum in tree
   */
  while (child->parent != NULL && less_than(child, child->parent))
    heap_node_swap(heap, child->parent, child);
}

HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
  heap_remove(heap, heap->min, less_than);
}

#undef HEAP_EXPORT

#endif  /* UV_SRC_HEAP_H_ */

// 初始化堆
HEAP_EXPORT(void heap_init(struct heap* heap));

// min指向最小元素(libuv定义的某种定时器结构体) nelts 堆中总元素的计数器
HEAP_EXPORT(void heap_init(struct heap* heap)) {
  heap->min = NULL;
  heap->nelts = 0;
}

// 取得最小元素的指针
HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
  return heap->min;
}

// 把 parent节点和child节点交换 child靠近根节点 parent远离根节点
static void heap_node_swap(struct heap* heap,
                           struct heap_node* parent,
                           struct heap_node* child) {
  struct heap_node* sibling;
  struct heap_node t;

  // 交换 2个 指针所分别指向的 某个heap_node结构体的地址 
  t = *parent;
  *parent = *child;
  *child = t;

  // 现在 parent 和 child 2个指针还是原来2个指针 但是它们通过 -> 引用的内容的却相反了 现在的 parent->xx 就是之前的child节点的xxx
  // 把原来child的parent指向现在新parent，即 child指针
  parent->parent = child;
  // 原parent的left如果是原来的child指针的话 说明 之前的child是之前的parent的左子节点
  if (child->left == child) {
    child->left = parent;
    sibling = child->right;
  } else {
    child->right = parent;
    sibling = child->left;
  }
  if (sibling != NULL)
    sibling->parent = child;

  // 原来的 child节点如果有左子节点 需要重新连接它的parent指向新的 child 指针 也就是 parent
  if (parent->left != NULL)
    parent->left->parent = parent;
  if (parent->right != NULL)
    parent->right->parent = parent;

  // 如果之前的parent 就是根节点 我们需要更新堆的min指针 让他重新指向新的根节点 child
  if (child->parent == NULL)
    heap->min = child;
  // 否则的话 重新建立 原 parent 的  parent 和新 parent 也就是 child指针的 联系
  else if (child->parent->left == parent)
    child->parent->left = child;
  else
    child->parent->right = child;
}

// 插入新的节点到堆中
HEAP_EXPORT(void heap_insert(struct heap* heap,
                             struct heap_node* newnode,
                             heap_compare_fn less_than)) {
  struct heap_node** parent;
  struct heap_node** child;
  unsigned int path;
  unsigned int n;
  unsigned int k;

  newnode->left = NULL;
  newnode->right = NULL;
  newnode->parent = NULL;

  /* Calculate the path from the root to the insertion point.  This is a min
   * heap so we always insert at the left-most free node of the bottom row.
   */
   
  path = 0;
  for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
    path = (path << 1) | (n & 1);
    
  // 假设插入 child 最终得到的 path 为：
  // 堆元素个数为 0 时， path = 0 k = 0
  // 堆元素个数为 1 时， path = 00 k = 1
  // 堆元素个数为 2 时,  path = 01 k = 1
  // 堆元素个数为 3 时,  path = 000 k = 2
  // 堆元素个数为 4 时,  path = 010 k = 2
  // 堆元素个数为 5 时,  path = 001 k = 2
  // ... k 代表当前节点所在树的层级 path 中 0 和 1 序列 从左往后代表着 子节点是父节点的 左节点还是右节点
  /* Now traverse the heap using the path we calculated in the previous step. */
  parent = child = &heap->min;
  while (k > 0) {
    parent = child;
    if (path & 1)
      child = &(*child)->right;
    else
      child = &(*child)->left;
    path >>= 1;
    k -= 1;
  }
  
  // path 从右往左 即 从上往下 遍历树
  // 遍历过后 parent 是 待插入位置 child 的父节点

  /* Insert the new node. */
  newnode->parent = *parent;
  *child = newnode;
  heap->nelts += 1;

  /* Walk up the tree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.
   */
 
  // 尾部新插入的节点 可能破坏了最小堆的 有序性： 父节点必须要比子节点都要小（即最小元素在根节点）
  // 所以需要从新节点 触发一次 上滤 维持最小堆的有序性
  // less_than 函数 是 用来比较节点的 libuv 就是 比较2个定时器容器的 超时时间的大小 
  while (newnode->parent != NULL && less_than(newnode, newnode->parent))
    heap_node_swap(heap, newnode->parent, newnode);
}

// 从堆中删除 node 
HEAP_EXPORT(void heap_remove(struct heap* heap,
                             struct heap_node* node,
                             heap_compare_fn less_than)) {
  struct heap_node* smallest;
  struct heap_node** max;
  struct heap_node* child;
  unsigned int path;
  unsigned int k;
  unsigned int n;

  if (heap->nelts == 0)
    return;

  /* Calculate the path from the min (the root) to the max, the left-most node
   * of the bottom row.
   */
  path = 0;
  for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
    path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */
  max = &heap->min;
  while (k > 0) {
    if (path & 1)
      max = &(*max)->right;
    else
      max = &(*max)->left;
    path >>= 1;
    k -= 1;
  }
  
  // max 是当前树中最后一个位置的元素

  heap->nelts -= 1;

  /* Unlink the max node. */
  child = *max;
  *max = NULL;
  

  // 我们总是删除最后位置的元素
  // 如果待删除元素刚好是最后一个元素
  if (child == node) {
    /* We're removing either the max or the last node in the tree. */
    // 堆中刚好只有一个元素
    if (child == heap->min) {
      heap->min = NULL;
    }
    return;
  }

  /* Replace the to be deleted node with the max node. */
  // 把待删除节点的 各个指针赋值给 child 的各个指针
  child->left = node->left;
  child->right = node->right;
  child->parent = node->parent;

  // 然后重建 原 node 节点的父子指针 与 现在 child 的关系

  if (child->left != NULL) {
    child->left->parent = child;
  }

  if (child->right != NULL) {
    child->right->parent = child;
  }

  if (node->parent == NULL) {
    heap->min = child;
  } else if (node->parent->left == node) {
    node->parent->left = child;
  } else {
    node->parent->right = child;
  }
  
  // 替换完毕 现在的 child 替换到了 原有 node 所处的位置 

  /* Walk down the subtree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.  If the parent is bigger,
   * swap it with the smallest child.
   */
   
  // 把原先最后的元素 替换到 node 位置后 可能会破坏原有的 堆有序性 需要进行一波 下滤 
  // 从替换节点位置 一直到树的最底层 恢复这部分子树的有序性
  for (;;) {
    smallest = child;
    if (child->left != NULL && less_than(child->left, smallest))
      smallest = child->left;
    if (child->right != NULL && less_than(child->right, smallest))
      smallest = child->right;
    if (smallest == child)
      // 已经有序了
      break;
    heap_node_swap(heap, child, smallest);
  }

  /* Walk up the subtree and check that each parent is less than the node
   * this is required, because `max` node is not guaranteed to be the
   * actual maximum in tree
   */
 
  // 最后从child做一次 上滤 保证一条影响到的路径中 所有节点符合 堆有序性
  while (child->parent != NULL && less_than(child, child->parent))
    heap_node_swap(heap, child->parent, child);
}

// 删除最小节点 删除节点的一种特殊情况
HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
  heap_remove(heap, heap->min, less_than);
}