structure: remove BHeap

1 files changed, 0 insertions, 457 deletions

diff --git a/structure/BHeap.h b/structure/BHeap.h
deleted file mode 100644
index 6eb3e25..0000000
--- a/structure/BHeap.h
+++ /dev/null
@@ -1,457 +0,0 @@
-/**
- * @file BHeap.h
- * @author Ambroz Bizjak <ambrop7@gmail.com>
- * 
- * @section LICENSE
- * 
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the author nor the
- *    names of its contributors may be used to endorse or promote products
- *    derived from this software without specific prior written permission.
- * 
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- * 
- * @section DESCRIPTION
- * 
- * Binary heap.
- */
-
-#ifndef BADVPN_STRUCTURE_BHEAP_H
-#define BADVPN_STRUCTURE_BHEAP_H
-
-//#define BHEAP_DEBUG
-
-#include <stdint.h>
-#include <stddef.h>
-
-#include <misc/debug.h>
-
-/**
- * Handler function called by heap algorithms to compare two values.
- * For any two values, the comparator must always return the same result.
- * The <= relation defined by the comparator must be a total order.
- * Values are obtained like that:
- *   - The value of a node in the heap, or a node that is being inserted is:
- *     (uint8_t *)node + offset.
- *   - The value being looked up is the same as given to the lookup function.
- * 
- * @param user as in {@link BHeap_Init}
- * @param val1 first value
- * @param val2 second value
- * @return -1 if val1 < val2, 0 if val1 = val2, 1 if val1 > val2
- */
-typedef int (*BHeap_comparator) (void *user, void *val1, void *val2);
-
-struct BHeapNode;
-
-/**
- * Binary heap.
- */
-typedef struct {
-    int offset;
-    BHeap_comparator comparator;
-    void *user;
-    struct BHeapNode *root;
-    struct BHeapNode *last;
-    #ifndef NDEBUG
-    int in_handler;
-    #endif
-} BHeap;
-
-/**
- * Binary heap node.
- */
-typedef struct BHeapNode {
-    struct BHeapNode *parent;
-    struct BHeapNode *link[2];
-} BHeapNode;
-
-/**
- * Initializes the heap.
- * 
- * @param o heap to initialize
- * @param offset offset of a value from its node
- * @param comparator value comparator handler function
- * @param user value to pass to comparator
- */
-static void BHeap_Init (BHeap *h, int offset, BHeap_comparator comparator, void *user);
-
-/**
- * Inserts a node into the heap.
- * Must not be called from comparator.
- * 
- * @param o the heap
- * @param node uninitialized node to insert. Must have a valid value (its value
- *             may be passed to the comparator during insertion).
- */
-static void BHeap_Insert (BHeap *h, BHeapNode *node);
-
-/**
- * Removes a node from the heap.
- * Must not be called from comparator.
- * 
- * @param o the heap
- * @param node node to remove
- */
-static void BHeap_Remove (BHeap *h, BHeapNode *node);
-
-/**
- * Returns one of the smallest nodes in the heap.
- * Must not be called from comparator.
- * 
- * @param o the heap
- * @return one of the smallest nodes in the heap, or NULL if there
- *         are no nodes
- */
-static BHeapNode * BHeap_GetFirst (BHeap *h);
-
-static void * _BHeap_node_value (BHeap *o, BHeapNode *n)
-{
-    return ((uint8_t *)n + o->offset);
-}
-
-static int _BHeap_compare_values (BHeap *o, void *v1, void *v2)
-{
-    #ifndef NDEBUG
-    o->in_handler = 1;
-    #endif
-    
-    int res = o->comparator(o->user, v1, v2);
-    
-    #ifndef NDEBUG
-    o->in_handler = 0;
-    #endif
-    
-    ASSERT(res == -1 || res == 0 || res == 1)
-    
-    return res;
-}
-
-static int _BHeap_compare_nodes (BHeap *o, BHeapNode *n1, BHeapNode *n2)
-{
-    return _BHeap_compare_values(o, _BHeap_node_value(o, n1), _BHeap_node_value(o, n2));
-}
-
-#ifdef BHEAP_DEBUG
-#define BHEAP_ASSERT(_h) _BHeap_assert(_h);
-#else
-#define BHEAP_ASSERT(_h)
-#endif
-
-#ifdef BHEAP_DEBUG
-
-struct _BHeap_assert_data {
-    int state;
-    int level;
-    BHeapNode *prev_leaf;
-};
-
-#define BHEAP_ASSERT_STATE_NODEPTH 1
-#define BHEAP_ASSERT_STATE_LOWEST 2
-#define BHEAP_ASSERT_STATE_LOWESTEND 3
-
-static void _BHeap_assert_recurser (BHeap *h, BHeapNode *n, struct _BHeap_assert_data *ad, int level)
-{
-    if (!n->link[0] && !n->link[1]) {
-        if (ad->state == BHEAP_ASSERT_STATE_NODEPTH) {
-            // leftmost none, remember depth
-            ad->state = BHEAP_ASSERT_STATE_LOWEST;
-            ad->level = level;
-        }
-    } else {
-        // drop down
-        if (n->link[0]) {
-            ASSERT(_BHeap_compare_nodes(h, n, n->link[0]) <= 0)
-            ASSERT(n->link[0]->parent == n)
-            _BHeap_assert_recurser(h, n->link[0], ad, level + 1);
-        }
-        if (n->link[1]) {
-            ASSERT(_BHeap_compare_nodes(h, n, n->link[1]) <= 0)
-            ASSERT(n->link[1]->parent == n)
-            _BHeap_assert_recurser(h, n->link[1], ad, level + 1);
-        }
-    }
-    
-    ASSERT(ad->state == BHEAP_ASSERT_STATE_LOWEST || ad->state == BHEAP_ASSERT_STATE_LOWESTEND)
-    
-    if (level < ad->level - 1) {
-        ASSERT(n->link[0] && n->link[1])
-    }
-    else if (level == ad->level - 1) {
-        switch (ad->state) {
-            case BHEAP_ASSERT_STATE_LOWEST:
-                if (!n->link[0]) {
-                    ad->state = BHEAP_ASSERT_STATE_LOWESTEND;
-                    ASSERT(!n->link[1])
-                    ASSERT(ad->prev_leaf == h->last)
-                } else {
-                    if (!n->link[1]) {
-                        ad->state = BHEAP_ASSERT_STATE_LOWESTEND;
-                        ASSERT(ad->prev_leaf == h->last)
-                    }
-                }
-                break;
-            case BHEAP_ASSERT_STATE_LOWESTEND:
-                ASSERT(!n->link[0] && !n->link[1])
-                break;
-        }
-    }
-    else if (level == ad->level) {
-        ASSERT(ad->state == BHEAP_ASSERT_STATE_LOWEST)
-        ASSERT(!n->link[0] && !n->link[1])
-        ad->prev_leaf = n;
-    }
-    else {
-        ASSERT(0)
-    }
-}
-
-static void _BHeap_assert (BHeap *h)
-{
-    struct _BHeap_assert_data ad;
-    ad.state = BHEAP_ASSERT_STATE_NODEPTH;
-    ad.prev_leaf = NULL;
-    
-    if (h->root) {
-        ASSERT(h->last)
-        ASSERT(!h->root->parent)
-        _BHeap_assert_recurser(h, h->root, &ad, 0);
-        if (ad.state == BHEAP_ASSERT_STATE_LOWEST) {
-            ASSERT(ad.prev_leaf == h->last)
-        }
-    } else {
-        ASSERT(!h->last)
-    }
-}
-
-#endif
-
-static void _BHeap_move_one_up (BHeap *h, BHeapNode *n)
-{
-    ASSERT(n->parent)
-    
-    BHeapNode *p = n->parent;
-    
-    if (p->parent) {
-        p->parent->link[p == p->parent->link[1]] = n;
-    } else {
-        h->root = n;
-    }
-    n->parent = p->parent;
-    
-    int nside = (n == p->link[1]);
-    BHeapNode *c = p->link[!nside];
-    
-    p->link[0] = n->link[0];
-    if (p->link[0]) {
-        p->link[0]->parent = p;
-    }
-    
-    p->link[1] = n->link[1];
-    if (p->link[1]) {
-        p->link[1]->parent = p;
-    }
-    
-    n->link[nside] = p;
-    p->parent = n;
-    
-    n->link[!nside] = c;
-    if (c) {
-        c->parent = n;
-    }
-    
-    if (n == h->last) {
-        h->last = p;
-    }
-}
-
-static void _BHeap_replace_node (BHeap *h, BHeapNode *d, BHeapNode *s)
-{
-    if (d->parent) {
-        d->parent->link[d == d->parent->link[1]] = s;
-    } else {
-        h->root = s;
-    }
-    s->parent = d->parent;
-    
-    s->link[0] = d->link[0];
-    if (s->link[0]) {
-        s->link[0]->parent = s;
-    }
-    
-    s->link[1] = d->link[1];
-    if (s->link[1]) {
-        s->link[1]->parent = s;
-    }
-}
-
-void BHeap_Init (BHeap *h, int offset, BHeap_comparator comparator, void *user)
-{
-    h->offset = offset;
-    h->comparator = comparator;
-    h->user = user;
-    h->root = NULL;
-    h->last = NULL;
-    
-    #ifndef NDEBUG
-    h->in_handler = 0;
-    #endif
-    
-    BHEAP_ASSERT(h)
-}
-
-void BHeap_Insert (BHeap *h, BHeapNode *node)
-{
-    ASSERT(!h->in_handler)
-    
-    if (!h->root) {
-        // insert to root
-        h->root = node;
-        h->last = node;
-        node->parent = NULL;
-        node->link[0] = NULL;
-        node->link[1] = NULL;
-        
-        BHEAP_ASSERT(h)
-        return;
-    }
-    
-    // find the node to insert to
-    
-    // start with current last node and walk up left as much as possible.
-    // That is, keep replacing the current node with the parent as long as it
-    // exists and the current node is its right child.
-    BHeapNode *cur = h->last;
-    while (cur->parent && cur == cur->parent->link[1]) {
-        cur = cur->parent;
-    }
-    
-    if (cur->parent) {
-        if (cur->parent->link[1]) {
-            // have parent and parent has right child. Attach the new node
-            // to the leftmost node of the parent's right subtree.
-            cur = cur->parent->link[1];
-            while (cur->link[0]) {
-                cur = cur->link[0];
-            }
-        } else {
-            // have parent, but parent has no right child. This can
-            // only happen when the last node is a right child. So
-            // attach the new node to its parent.
-            cur = cur->parent;
-        }
-    } else {
-        // have no parent, attach the new node to a new level. We're at the
-        // root, so drop down left to obtain the node where we'll attach
-        // the new node.
-        while (cur->link[0]) {
-            cur = cur->link[0];
-        }
-    }
-    
-    ASSERT((!cur->link[0] && !cur->link[1]) || (cur->link[0] && !cur->link[1]))
-    
-    // attach new node
-    // the new node becomes the new last node
-    h->last = node;
-    cur->link[!!cur->link[0]] = node;
-    node->parent = cur;
-    node->link[0] = NULL;
-    node->link[1] = NULL;
-    
-    // restore heap property
-    while (node->parent && _BHeap_compare_nodes(h, node->parent, node) > 0) {
-        _BHeap_move_one_up(h, node);
-    }
-    
-    BHEAP_ASSERT(h)
-}
-
-void BHeap_Remove (BHeap *h, BHeapNode *node)
-{
-    ASSERT(!h->in_handler)
-    
-    if (!node->parent && !node->link[0] && !node->link[1]) {
-        h->root = NULL;
-        h->last = NULL;
-        
-        BHEAP_ASSERT(h)
-        return;
-    }
-    
-    // locate the node before the last node
-    BHeapNode *cur = h->last;
-    while (cur->parent && cur == cur->parent->link[0]) {
-        cur = cur->parent;
-    }
-    if (cur->parent) {
-        ASSERT(cur->parent->link[0])
-        cur = cur->parent->link[0];
-        while (cur->link[1]) {
-            cur = cur->link[1];
-        }
-    } else {
-        while (cur->link[1]) {
-            cur = cur->link[1];
-        }
-    }
-    
-    // disconnect last
-    ASSERT(h->last->parent)
-    h->last->parent->link[h->last == h->last->parent->link[1]] = NULL;
-    
-    if (node == h->last) {
-        // deleting last; set new last
-        h->last = cur;
-    } else {
-        // not deleting last; move last to node's place
-        BHeapNode *srcnode = h->last;
-        _BHeap_replace_node(h, node, srcnode);
-        // set new last unless node=cur; in this case it stays the same
-        if (node != cur) {
-            h->last = cur;
-        }
-        
-        // restore heap property
-        if (srcnode->parent && _BHeap_compare_nodes(h, srcnode, srcnode->parent) < 0) {
-            do {
-                _BHeap_move_one_up(h, srcnode);
-            } while (srcnode->parent && _BHeap_compare_nodes(h, srcnode, srcnode->parent) < 0);
-        } else {
-            while (srcnode->link[0] || srcnode->link[1]) {
-                int side = (srcnode->link[1] && (_BHeap_compare_nodes(h, srcnode->link[0], srcnode->link[1]) >= 0));
-                if (_BHeap_compare_nodes(h, srcnode, srcnode->link[side]) > 0) {
-                    _BHeap_move_one_up(h, srcnode->link[side]);
-                } else {
-                    break;
-                }
-            }
-        }
-    }
-    
-    BHEAP_ASSERT(h)
-}
-
-BHeapNode * BHeap_GetFirst (BHeap *h)
-{
-    ASSERT(!h->in_handler)
-    
-    return h->root;
-}
-
-#endif