gfsmxlCLCFibPriv.h
Go to the documentation of this file.
1 /*-
2  * Copyright 1997, 1999-2003 John-Mark Gurney.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $Id: gfsmxlCLCFibPriv.h 460 2008-01-07 11:23:27Z moocow $
27  *
28  * + modified by moocow Tue, 18 Dec 2007 08:27:14 +0100
29  * - specialized for gfsmxlCascadeLookupConfig elements
30  *
31  */
32 
33 #ifndef _GFSMXL_CLC_FIBPRIV_H_
34 #define _GFSMXL_CLC_FIBPRIV_H_
35 
36 struct gfsmxlCLCFibHeap_el;
37 struct gfsmxlCascadeLookupConfig_;
38 
39 /*
40  * global heap operations
41  */
42 struct gfsmxlCLCFibHeap {
43  int fh_n;
44  int fh_Dl;
45  struct gfsmxlCLCFibHeap_el **fh_cons;
46  struct gfsmxlCLCFibHeap_el *fh_min;
47  struct gfsmxlCLCFibHeap_el *fh_root;
48  struct gfsmxlCascadeLookupConfig_ *fh_neginf;
49  /*int fh_keys : 1; */
50 #ifdef GFSMXL_CLC_FH_STATS
51  int fh_maxn;
52  int fh_ninserts;
53  int fh_nextracts;
54 #endif
55 };
56 
57 static void gfsmxl_clc_fh_initheap(struct gfsmxlCLCFibHeap *);
58 static void gfsmxl_clc_fh_insertrootlist(struct gfsmxlCLCFibHeap *, struct gfsmxlCLCFibHeap_el *);
59 static void gfsmxl_clc_fh_removerootlist(struct gfsmxlCLCFibHeap *, struct gfsmxlCLCFibHeap_el *);
60 static void gfsmxl_clc_fh_consolidate(struct gfsmxlCLCFibHeap *);
61 static void gfsmxl_clc_fh_heaplink(struct gfsmxlCLCFibHeap *h, struct gfsmxlCLCFibHeap_el *y,
62  struct gfsmxlCLCFibHeap_el *x);
63 static void gfsmxl_clc_fh_cut(struct gfsmxlCLCFibHeap *, struct gfsmxlCLCFibHeap_el *, struct gfsmxlCLCFibHeap_el *);
64 static void gfsmxl_clc_fh_cascading_cut(struct gfsmxlCLCFibHeap *, struct gfsmxlCLCFibHeap_el *);
65 static struct gfsmxlCLCFibHeap_el *gfsmxl_clc_fh_extractminel(struct gfsmxlCLCFibHeap *);
66 static void gfsmxl_clc_fh_checkcons(struct gfsmxlCLCFibHeap *h);
67 static void gfsmxl_clc_fh_destroyheap(struct gfsmxlCLCFibHeap *h);
68 
69 /*
70 static int gfsmxl_clc_fh_compare (struct gfsmxlCLCFibHeap *h,
71  struct gfsmxlCLCFibHeap_el *a,
72  struct gfsmxlCLCFibHeap_el *b
73  );
74 static int gfsmxl_clc_fh_comparedata(struct gfsmxlCLCFibHeap *h,
75  int key,
76  struct gfsmxlCascadeLookupConfig_ *data,
77  struct gfsmxlCLCFibHeap_el *b
78  );
79 */
80 static int gfsmxl_clc_fh_compare (struct gfsmxlCLCFibHeap_el *a, struct gfsmxlCLCFibHeap_el *b);
81 static int gfsmxl_clc_fh_comparedata(struct gfsmxlCascadeLookupConfig_ *data, struct gfsmxlCLCFibHeap_el *b);
82 
83 
84 static void gfsmxl_clc_fh_insertel(struct gfsmxlCLCFibHeap *h, struct gfsmxlCLCFibHeap_el *x);
85 static void gfsmxl_clc_fh_deleteel(struct gfsmxlCLCFibHeap *h, struct gfsmxlCLCFibHeap_el *x);
86 
87 /*
88  * specific node operations
89  */
90 struct gfsmxlCLCFibHeap_el {
91  int fhe_degree;
92  int fhe_mark;
93  struct gfsmxlCLCFibHeap_el *fhe_p;
94  struct gfsmxlCLCFibHeap_el *fhe_child;
95  struct gfsmxlCLCFibHeap_el *fhe_left;
96  struct gfsmxlCLCFibHeap_el *fhe_right;
97  //--
98  //int fhe_key;
99  struct gfsmxlCascadeLookupConfig_ *fhe_data;
100 };
101 
102 static struct gfsmxlCLCFibHeap_el *gfsmxl_clc_fhe_newelem(void);
103 static void gfsmxl_clc_fhe_initelem(struct gfsmxlCLCFibHeap_el *);
104 static void gfsmxl_clc_fhe_insertafter(struct gfsmxlCLCFibHeap_el *a, struct gfsmxlCLCFibHeap_el *b);
105 static inline void gfsmxl_clc_fhe_insertbefore(struct gfsmxlCLCFibHeap_el *a, struct gfsmxlCLCFibHeap_el *b);
106 static struct gfsmxlCLCFibHeap_el *gfsmxl_clc_fhe_remove(struct gfsmxlCLCFibHeap_el *a);
107 #define gfsmxl_clc_fhe_destroy(x) free((x))
108 
109 /*
110  * general functions
111  */
112 static inline int ceillog2(unsigned int a);
113 
114 #endif /* _FIBPRIV_H_ */
Generated on Mon Oct 20 2014 10:48:47 for libgfsmxl by   doxygen 1.8.1.2