Blame src/heap-inl.h

Packit Service 7c31a4
/* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
Packit Service 7c31a4
 *
Packit Service 7c31a4
 * Permission to use, copy, modify, and/or distribute this software for any
Packit Service 7c31a4
 * purpose with or without fee is hereby granted, provided that the above
Packit Service 7c31a4
 * copyright notice and this permission notice appear in all copies.
Packit Service 7c31a4
 *
Packit Service 7c31a4
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
Packit Service 7c31a4
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
Packit Service 7c31a4
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
Packit Service 7c31a4
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
Packit Service 7c31a4
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
Packit Service 7c31a4
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
Packit Service 7c31a4
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
Packit Service 7c31a4
 */
Packit Service 7c31a4
Packit Service 7c31a4
#ifndef UV_SRC_HEAP_H_
Packit Service 7c31a4
#define UV_SRC_HEAP_H_
Packit Service 7c31a4
Packit Service 7c31a4
#include <stddef.h>  /* NULL */
Packit Service 7c31a4
Packit Service 7c31a4
#if defined(__GNUC__)
Packit Service 7c31a4
# define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
Packit Service 7c31a4
#else
Packit Service 7c31a4
# define HEAP_EXPORT(declaration) static declaration
Packit Service 7c31a4
#endif
Packit Service 7c31a4
Packit Service 7c31a4
struct heap_node {
Packit Service 7c31a4
  struct heap_node* left;
Packit Service 7c31a4
  struct heap_node* right;
Packit Service 7c31a4
  struct heap_node* parent;
Packit Service 7c31a4
};
Packit Service 7c31a4
Packit Service 7c31a4
/* A binary min heap.  The usual properties hold: the root is the lowest
Packit Service 7c31a4
 * element in the set, the height of the tree is at most log2(nodes) and
Packit Service 7c31a4
 * it's always a complete binary tree.
Packit Service 7c31a4
 *
Packit Service 7c31a4
 * The heap function try hard to detect corrupted tree nodes at the cost
Packit Service 7c31a4
 * of a minor reduction in performance.  Compile with -DNDEBUG to disable.
Packit Service 7c31a4
 */
Packit Service 7c31a4
struct heap {
Packit Service 7c31a4
  struct heap_node* min;
Packit Service 7c31a4
  unsigned int nelts;
Packit Service 7c31a4
};
Packit Service 7c31a4
Packit Service 7c31a4
/* Return non-zero if a < b. */
Packit Service 7c31a4
typedef int (*heap_compare_fn)(const struct heap_node* a,
Packit Service 7c31a4
                               const struct heap_node* b);
Packit Service 7c31a4
Packit Service 7c31a4
/* Public functions. */
Packit Service 7c31a4
HEAP_EXPORT(void heap_init(struct heap* heap));
Packit Service 7c31a4
HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
Packit Service 7c31a4
HEAP_EXPORT(void heap_insert(struct heap* heap,
Packit Service 7c31a4
                             struct heap_node* newnode,
Packit Service 7c31a4
                             heap_compare_fn less_than));
Packit Service 7c31a4
HEAP_EXPORT(void heap_remove(struct heap* heap,
Packit Service 7c31a4
                             struct heap_node* node,
Packit Service 7c31a4
                             heap_compare_fn less_than));
Packit Service 7c31a4
HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
Packit Service 7c31a4
Packit Service 7c31a4
/* Implementation follows. */
Packit Service 7c31a4
Packit Service 7c31a4
HEAP_EXPORT(void heap_init(struct heap* heap)) {
Packit Service 7c31a4
  heap->min = NULL;
Packit Service 7c31a4
  heap->nelts = 0;
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
Packit Service 7c31a4
  return heap->min;
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
/* Swap parent with child. Child moves closer to the root, parent moves away. */
Packit Service 7c31a4
static void heap_node_swap(struct heap* heap,
Packit Service 7c31a4
                           struct heap_node* parent,
Packit Service 7c31a4
                           struct heap_node* child) {
Packit Service 7c31a4
  struct heap_node* sibling;
Packit Service 7c31a4
  struct heap_node t;
Packit Service 7c31a4
Packit Service 7c31a4
  t = *parent;
Packit Service 7c31a4
  *parent = *child;
Packit Service 7c31a4
  *child = t;
Packit Service 7c31a4
Packit Service 7c31a4
  parent->parent = child;
Packit Service 7c31a4
  if (child->left == child) {
Packit Service 7c31a4
    child->left = parent;
Packit Service 7c31a4
    sibling = child->right;
Packit Service 7c31a4
  } else {
Packit Service 7c31a4
    child->right = parent;
Packit Service 7c31a4
    sibling = child->left;
Packit Service 7c31a4
  }
Packit Service 7c31a4
  if (sibling != NULL)
Packit Service 7c31a4
    sibling->parent = child;
Packit Service 7c31a4
Packit Service 7c31a4
  if (parent->left != NULL)
Packit Service 7c31a4
    parent->left->parent = parent;
Packit Service 7c31a4
  if (parent->right != NULL)
Packit Service 7c31a4
    parent->right->parent = parent;
Packit Service 7c31a4
Packit Service 7c31a4
  if (child->parent == NULL)
Packit Service 7c31a4
    heap->min = child;
Packit Service 7c31a4
  else if (child->parent->left == parent)
Packit Service 7c31a4
    child->parent->left = child;
Packit Service 7c31a4
  else
Packit Service 7c31a4
    child->parent->right = child;
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
HEAP_EXPORT(void heap_insert(struct heap* heap,
Packit Service 7c31a4
                             struct heap_node* newnode,
Packit Service 7c31a4
                             heap_compare_fn less_than)) {
Packit Service 7c31a4
  struct heap_node** parent;
Packit Service 7c31a4
  struct heap_node** child;
Packit Service 7c31a4
  unsigned int path;
Packit Service 7c31a4
  unsigned int n;
Packit Service 7c31a4
  unsigned int k;
Packit Service 7c31a4
Packit Service 7c31a4
  newnode->left = NULL;
Packit Service 7c31a4
  newnode->right = NULL;
Packit Service 7c31a4
  newnode->parent = NULL;
Packit Service 7c31a4
Packit Service 7c31a4
  /* Calculate the path from the root to the insertion point.  This is a min
Packit Service 7c31a4
   * heap so we always insert at the left-most free node of the bottom row.
Packit Service 7c31a4
   */
Packit Service 7c31a4
  path = 0;
Packit Service 7c31a4
  for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
Packit Service 7c31a4
    path = (path << 1) | (n & 1);
Packit Service 7c31a4
Packit Service 7c31a4
  /* Now traverse the heap using the path we calculated in the previous step. */
Packit Service 7c31a4
  parent = child = &heap->min;
Packit Service 7c31a4
  while (k > 0) {
Packit Service 7c31a4
    parent = child;
Packit Service 7c31a4
    if (path & 1)
Packit Service 7c31a4
      child = &(*child)->right;
Packit Service 7c31a4
    else
Packit Service 7c31a4
      child = &(*child)->left;
Packit Service 7c31a4
    path >>= 1;
Packit Service 7c31a4
    k -= 1;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  /* Insert the new node. */
Packit Service 7c31a4
  newnode->parent = *parent;
Packit Service 7c31a4
  *child = newnode;
Packit Service 7c31a4
  heap->nelts += 1;
Packit Service 7c31a4
Packit Service 7c31a4
  /* Walk up the tree and check at each node if the heap property holds.
Packit Service 7c31a4
   * It's a min heap so parent < child must be true.
Packit Service 7c31a4
   */
Packit Service 7c31a4
  while (newnode->parent != NULL && less_than(newnode, newnode->parent))
Packit Service 7c31a4
    heap_node_swap(heap, newnode->parent, newnode);
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
HEAP_EXPORT(void heap_remove(struct heap* heap,
Packit Service 7c31a4
                             struct heap_node* node,
Packit Service 7c31a4
                             heap_compare_fn less_than)) {
Packit Service 7c31a4
  struct heap_node* smallest;
Packit Service 7c31a4
  struct heap_node** max;
Packit Service 7c31a4
  struct heap_node* child;
Packit Service 7c31a4
  unsigned int path;
Packit Service 7c31a4
  unsigned int k;
Packit Service 7c31a4
  unsigned int n;
Packit Service 7c31a4
Packit Service 7c31a4
  if (heap->nelts == 0)
Packit Service 7c31a4
    return;
Packit Service 7c31a4
Packit Service 7c31a4
  /* Calculate the path from the min (the root) to the max, the left-most node
Packit Service 7c31a4
   * of the bottom row.
Packit Service 7c31a4
   */
Packit Service 7c31a4
  path = 0;
Packit Service 7c31a4
  for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
Packit Service 7c31a4
    path = (path << 1) | (n & 1);
Packit Service 7c31a4
Packit Service 7c31a4
  /* Now traverse the heap using the path we calculated in the previous step. */
Packit Service 7c31a4
  max = &heap->min;
Packit Service 7c31a4
  while (k > 0) {
Packit Service 7c31a4
    if (path & 1)
Packit Service 7c31a4
      max = &(*max)->right;
Packit Service 7c31a4
    else
Packit Service 7c31a4
      max = &(*max)->left;
Packit Service 7c31a4
    path >>= 1;
Packit Service 7c31a4
    k -= 1;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  heap->nelts -= 1;
Packit Service 7c31a4
Packit Service 7c31a4
  /* Unlink the max node. */
Packit Service 7c31a4
  child = *max;
Packit Service 7c31a4
  *max = NULL;
Packit Service 7c31a4
Packit Service 7c31a4
  if (child == node) {
Packit Service 7c31a4
    /* We're removing either the max or the last node in the tree. */
Packit Service 7c31a4
    if (child == heap->min) {
Packit Service 7c31a4
      heap->min = NULL;
Packit Service 7c31a4
    }
Packit Service 7c31a4
    return;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  /* Replace the to be deleted node with the max node. */
Packit Service 7c31a4
  child->left = node->left;
Packit Service 7c31a4
  child->right = node->right;
Packit Service 7c31a4
  child->parent = node->parent;
Packit Service 7c31a4
Packit Service 7c31a4
  if (child->left != NULL) {
Packit Service 7c31a4
    child->left->parent = child;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  if (child->right != NULL) {
Packit Service 7c31a4
    child->right->parent = child;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  if (node->parent == NULL) {
Packit Service 7c31a4
    heap->min = child;
Packit Service 7c31a4
  } else if (node->parent->left == node) {
Packit Service 7c31a4
    node->parent->left = child;
Packit Service 7c31a4
  } else {
Packit Service 7c31a4
    node->parent->right = child;
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  /* Walk down the subtree and check at each node if the heap property holds.
Packit Service 7c31a4
   * It's a min heap so parent < child must be true.  If the parent is bigger,
Packit Service 7c31a4
   * swap it with the smallest child.
Packit Service 7c31a4
   */
Packit Service 7c31a4
  for (;;) {
Packit Service 7c31a4
    smallest = child;
Packit Service 7c31a4
    if (child->left != NULL && less_than(child->left, smallest))
Packit Service 7c31a4
      smallest = child->left;
Packit Service 7c31a4
    if (child->right != NULL && less_than(child->right, smallest))
Packit Service 7c31a4
      smallest = child->right;
Packit Service 7c31a4
    if (smallest == child)
Packit Service 7c31a4
      break;
Packit Service 7c31a4
    heap_node_swap(heap, child, smallest);
Packit Service 7c31a4
  }
Packit Service 7c31a4
Packit Service 7c31a4
  /* Walk up the subtree and check that each parent is less than the node
Packit Service 7c31a4
   * this is required, because `max` node is not guaranteed to be the
Packit Service 7c31a4
   * actual maximum in tree
Packit Service 7c31a4
   */
Packit Service 7c31a4
  while (child->parent != NULL && less_than(child, child->parent))
Packit Service 7c31a4
    heap_node_swap(heap, child->parent, child);
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
Packit Service 7c31a4
  heap_remove(heap, heap->min, less_than);
Packit Service 7c31a4
}
Packit Service 7c31a4
Packit Service 7c31a4
#undef HEAP_EXPORT
Packit Service 7c31a4
Packit Service 7c31a4
#endif  /* UV_SRC_HEAP_H_ */