diff options
Diffstat (limited to '3rdparty/libuv/src/heap-inl.h')
-rw-r--r-- | 3rdparty/libuv/src/heap-inl.h | 245 |
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_ */ |