summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/libuv/src/heap-inl.h
diff options
context:
space:
mode:
author Miodrag Milanovic <mmicko@gmail.com>2016-10-07 14:14:08 +0200
committer Miodrag Milanovic <mmicko@gmail.com>2016-10-07 14:14:08 +0200
commit85f4741fcf642f52ac4fa56f0aff1728727c901b (patch)
treeda8cca02913839152d2eb04c0e85a83018bcaed3 /3rdparty/libuv/src/heap-inl.h
parentff01b716711b97c2fcaa709ea97f7650f106aa10 (diff)
Remove libuv library (nw)
Diffstat (limited to '3rdparty/libuv/src/heap-inl.h')
-rw-r--r--3rdparty/libuv/src/heap-inl.h245
1 files changed, 0 insertions, 245 deletions
diff --git a/3rdparty/libuv/src/heap-inl.h b/3rdparty/libuv/src/heap-inl.h
deleted file mode 100644
index 1e2ed60e094..00000000000
--- a/3rdparty/libuv/src/heap-inl.h
+++ /dev/null
@@ -1,245 +0,0 @@
-/* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
- *
- * Permission to use, copy, modify, and/or distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
-#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_ */