1 /* 2 Copyright 2007, 2008 Daniel Zerbino (zerbino@ebi.ac.uk) 3 4 This file is part of Velvet. 5 6 Velvet is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2 of the License, or 9 (at your option) any later version. 10 11 Velvet is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with Velvet; if not, write to the Free Software 18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 19 20 */ 21 /*- 22 * Copyright 1997, 1999-2003 John-Mark Gurney. 23 * All rights reserved. 24 * 25 * Redistribution and use in source and binary forms, with or without 26 * modification, are permitted provided that the following conditions 27 * are met: 28 * 1. Redistributions of source code must retain the above copyright 29 * notice, this list of conditions and the following disclaimer. 30 * 2. Redistributions in binary form must reproduce the above copyright 31 * notice, this list of conditions and the following disclaimer in the 32 * documentation and/or other materials provided with the distribution. 33 * 34 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 37 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 44 * SUCH DAMAGE. 45 * 46 * $Id: dfibpriv.h,v 1.8 2007/10/09 09:56:46 zerbino Exp $ 47 * 48 */ 49 50 #ifndef _DFIBPRIV_H_ 51 #define _DFIBPRIV_H_ 52 53 #include "globals.h" 54 55 /* 56 * specific node operations 57 */ 58 struct dfibheap_el { 59 DFibHeapNode *dfhe_p; 60 DFibHeapNode *dfhe_child; 61 DFibHeapNode *dfhe_left; 62 DFibHeapNode *dfhe_right; 63 void *dfhe_data; 64 Time dfhe_key; 65 int dfhe_degree; 66 boolean dfhe_mark; 67 } ATTRIBUTE_PACKED; 68 69 static DFibHeapNode *dfhe_newelem(DFibHeap *); 70 static void dfhe_insertafter(DFibHeapNode * a, DFibHeapNode * b); 71 static inline void dfhe_insertbefore(DFibHeapNode * a, DFibHeapNode * b); 72 static DFibHeapNode *dfhe_remove(DFibHeapNode * a); 73 74 /* 75 * global heap operations 76 */ 77 struct dfibheap { 78 RecycleBin *nodeMemory; 79 DFibHeapNode **dfh_cons; 80 DFibHeapNode *dfh_min; 81 DFibHeapNode *dfh_root; 82 IDnum dfh_n; 83 IDnum dfh_Dl; 84 } ATTRIBUTE_PACKED; 85 86 static void dfh_insertrootlist(DFibHeap *, DFibHeapNode *); 87 static void dfh_removerootlist(DFibHeap *, DFibHeapNode *); 88 static void dfh_consolidate(DFibHeap *); 89 static void dfh_heaplink(DFibHeap * h, DFibHeapNode * y, DFibHeapNode * x); 90 static void dfh_cut(DFibHeap *, DFibHeapNode *, DFibHeapNode *); 91 static void dfh_cascading_cut(DFibHeap *, DFibHeapNode *); 92 static DFibHeapNode *dfh_extractminel(DFibHeap *); 93 static void dfh_checkcons(DFibHeap * h); 94 static int dfh_compare(DFibHeap * h, DFibHeapNode * a, DFibHeapNode * b); 95 static int dfh_comparedata(DFibHeap * h, Time key, 96 void *data, DFibHeapNode * b); 97 static void dfh_insertel(DFibHeap * h, DFibHeapNode * x); 98 99 100 /* 101 * general functions 102 */ 103 static inline IDnum ceillog2(IDnum a); 104 105 #endif /* _FIBPRIV_H_ */ 106