/* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/src/skewheap.c * \brief Skew heaps. * \ingroup lib */ #include "common/std.h" #include "lib/heap.h" void heap_node_init (heap_node_t *node) { node->father = NULL; node->left = node->right = NULL; } heap_node_t * heap_node_merge (heap_node_t *root1, heap_node_t *root2, heap_node_less_t less) { heap_node_t *h1, *h2, *h, *root; dbg_assert (!root1 || !root1->father); dbg_assert (!root2 || !root2->father); dbg_assert (less); /* Trivial cases. */ if (!root1) return root2; else if (!root2) return root1; h1 = root1; h2 = root2; /* Skew merge root. * h1 and h2: current "read" node. * h: current "write" node. * h->left: where the next node will be put. */ if (less (h1, h2)) { h = h1; h1 = h1->right; } else { h = h2; h2 = h2->right; } root = h; h->right = h->left; /* Skew merge loop. */ while (h1 || h2) { if (!h2 || (h1 && less (h1, h2))) { h1->father = h; h->left = h1; h = h1; h1 = h1->right; } else { h2->father = h; h->left = h2; h = h2; h2 = h2->right; } h->right = h->left; } h->left = NULL; return root; } void heap_insert (heap_t *heap, heap_node_t *node) { dbg_assert (heap && heap->less); dbg_assert (node); heap->root = heap_node_merge (heap->root, node, heap->less); } void heap_remove_root (heap_t *heap) { heap_node_t *root; dbg_assert (heap); dbg_assert (!heap_empty (heap)); root = heap->root; if (root->left) root->left->father = NULL; if (root->right) root->right->father = NULL; heap->root = heap_node_merge (root->left, root->right, heap->less); root->father = root->left = root->right = NULL; } void heap_remove (heap_t *heap, heap_node_t *node) { heap_node_t **r; dbg_assert (heap); dbg_assert (!heap_empty (heap)); dbg_assert (node); /* Where to store the merged tree? */ if (!node->father) { dbg_assert (node == heap->root); r = &heap->root; } else if (node->father->right == node) { r = &node->father->right; } else { dbg_assert (node->father->left == node); r = &node->father->left; } /* Need NULL father pointer. */ if (node->left) node->left->father = NULL; if (node->right) node->right->father = NULL; /* Merge left and right subtree. */ *r = heap_node_merge (node->left, node->right, heap->less); if (*r) (*r)->father = node->father; /* Swap father children. */ if (node->father) XCH (node->father->left, node->father->right); /* Detach the removed node. */ node->father = node->left = node->right = NULL; }