fib.c File Reference

#include <fib.h>
#include <fibpriv.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

Macros
#define	swap(type, a, b)
#define	INT_BITS   (sizeof(int) * 8)

Functions
static int	ceillog2 (unsigned int a)
static void	fh_deleteel (struct fibheap *h, struct fibheap_el *x)
static void	fh_initheap (struct fibheap *new)
static void	fh_destroyheap (struct fibheap *h)
struct fibheap *	fh_makekeyheap ()
struct fibheap *	fh_makeheap ()
voidcmp	fh_setcmp (struct fibheap *h, voidcmp fnct)
void *	fh_setneginf (struct fibheap *h, void *data)
struct fibheap *	fh_union (struct fibheap *ha, struct fibheap *hb)
void	fh_deleteheap (struct fibheap *h)
struct fibheap_el *	fh_insertkey (struct fibheap *h, int key, void *data)
int	fh_minkey (struct fibheap *h)
int	fh_replacekey (struct fibheap *h, struct fibheap_el *x, int key)
void *	fh_replacekeydata (struct fibheap *h, struct fibheap_el *x, int key, void *data)
struct fibheap_el *	fh_insert (struct fibheap *h, void *data)
void *	fh_min (struct fibheap *h)
void *	fh_extractmin (struct fibheap *h)
void *	fh_replacedata (struct fibheap *h, struct fibheap_el *x, void *data)
void *	fh_delete (struct fibheap *h, struct fibheap_el *x)
static struct fibheap_el *	fh_extractminel (struct fibheap *h)
static void	fh_insertrootlist (struct fibheap *h, struct fibheap_el *x)
static void	fh_removerootlist (struct fibheap *h, struct fibheap_el *x)
static void	fh_consolidate (struct fibheap *h)
static void	fh_heaplink (struct fibheap *h, struct fibheap_el *y, struct fibheap_el *x)
static void	fh_cut (struct fibheap *h, struct fibheap_el *x, struct fibheap_el *y)
static void	fh_cascading_cut (struct fibheap *h, struct fibheap_el *y)
static struct fibheap_el *	fhe_newelem ()
static void	fhe_initelem (struct fibheap_el *e)
static void	fhe_insertafter (struct fibheap_el *a, struct fibheap_el *b)
static void	fhe_insertbefore (struct fibheap_el *a, struct fibheap_el *b)
static struct fibheap_el *	fhe_remove (struct fibheap_el *x)
static void	fh_checkcons (struct fibheap *h)
static int	fh_compare (struct fibheap *h, struct fibheap_el *a, struct fibheap_el *b)
static int	fh_comparedata (struct fibheap *h, int key, void *data, struct fibheap_el *b)
static void	fh_insertel (struct fibheap *h, struct fibheap_el *x)

Macro Definition Documentation

INT_BITS

#define INT_BITS   (sizeof(int) * 8)

swap

#define swap	(		type,
			a,
			b
	)

Value:

                do {                    \
                        type c;         \
                        c = a;          \
                        a = b;          \
                        b = c;          \
                } while (0)             \

Function Documentation

ceillog2()

static int ceillog2 ( unsigned int  a )

static

References INT_BITS.

Referenced by fh_checkcons().

fh_cascading_cut()

static void fh_cascading_cut ( struct fibheap *  h, struct fibheap_el *  y  )

static

References fh_cut(), fibheap_el::fhe_mark, and fibheap_el::fhe_p.

Referenced by fh_replacekeydata().

fh_checkcons()

static void fh_checkcons ( struct fibheap *  h )

static

References ceillog2(), fibheap::fh_cons, fibheap::fh_Dl, and fibheap::fh_n.

Referenced by fh_consolidate().

fh_compare()

static int fh_compare ( struct fibheap *  h, struct fibheap_el *  a, struct fibheap_el *  b  )

static

References fibheap::fh_cmp_fnct, fibheap::fh_keys, fibheap_el::fhe_data, and fibheap_el::fhe_key.

Referenced by fh_comparedata(), fh_consolidate(), fh_replacekeydata(), and fh_union().

fh_comparedata()

static int fh_comparedata ( struct fibheap *  h, int  key, void *  data, struct fibheap_el *  b  )

static

References data, fh_compare(), fibheap_el::fhe_data, fibheap_el::fhe_key, and key.

Referenced by fh_replacekeydata().

fh_consolidate()

static void fh_consolidate ( struct fibheap *  h )

static

References D, fh_checkcons(), fh_compare(), fibheap::fh_cons, fibheap::fh_Dl, fh_heaplink(), fh_insertrootlist(), fibheap::fh_min, fh_removerootlist(), fibheap::fh_root, fibheap_el::fhe_degree, and swap.

Referenced by fh_extractminel().

fh_cut()

static void fh_cut ( struct fibheap *  h, struct fibheap_el *  x, struct fibheap_el *  y  )

static

References fh_insertrootlist(), fibheap_el::fhe_degree, fibheap_el::fhe_mark, fibheap_el::fhe_p, and fhe_remove().

Referenced by fh_cascading_cut(), and fh_replacekeydata().

fh_delete()

void* fh_delete	(	struct fibheap *	h,
		struct fibheap_el *	x
	)

References fh_extractmin(), fibheap::fh_keys, fibheap::fh_neginf, fh_replacedata(), fh_replacekey(), and fibheap_el::fhe_data.

Referenced by main(), and route_graph_point_update().

fh_deleteel()

static void fh_deleteel ( struct fibheap *  h, struct fibheap_el *  x  )

static

References data, fh_extractminel(), fibheap::fh_keys, fibheap::fh_neginf, fh_replacedata(), fh_replacekey(), fibheap_el::fhe_data, fibheap_el::fhe_key, and key.

Referenced by fh_replacekeydata().

fh_deleteheap()

void fh_deleteheap

(

struct fibheap *

h

)

References fh_destroyheap(), fh_extractminel(), fibheap::fh_min, and fhe_destroy.

Referenced by gui_internal_cmd_pois(), main(), route_graph_destroy(), and traffic_route_flood_graph().

fh_destroyheap()

static void fh_destroyheap ( struct fibheap *  h )

static

References fibheap::fh_cmp_fnct, fibheap::fh_cons, and fibheap::fh_neginf.

Referenced by fh_deleteheap(), and fh_union().

fh_extractmin()

void* fh_extractmin

(

struct fibheap *

h

)

References fh_extractminel(), fibheap::fh_min, fibheap_el::fhe_data, and fhe_destroy.

Referenced by fh_delete(), gui_internal_cmd_pois(), main(), route_graph_compute_shortest_path(), route_graph_reset(), and traffic_route_flood_graph().

fh_extractminel()

static struct fibheap_el* fh_extractminel ( struct fibheap *  h )

static

References fh_consolidate(), fh_insertrootlist(), fibheap::fh_min, fibheap::fh_n, fh_removerootlist(), fibheap_el::fhe_child, fibheap_el::fhe_p, and fibheap_el::fhe_right.

Referenced by fh_deleteel(), fh_deleteheap(), and fh_extractmin().

fh_heaplink()

static void fh_heaplink ( struct fibheap *  h, struct fibheap_el *  y, struct fibheap_el *  x  )

static

References fibheap_el::fhe_child, fibheap_el::fhe_degree, fhe_insertbefore(), fibheap_el::fhe_mark, and fibheap_el::fhe_p.

Referenced by fh_consolidate().

fh_initheap()

static void fh_initheap ( struct fibheap *  new )

static

Referenced by fh_makeheap(), and fh_makekeyheap().

fh_insert()

struct fibheap_el* fh_insert	(	struct fibheap *	h,
		void *	data
	)

References data, fh_insertel(), fibheap_el::fhe_data, and fhe_newelem().

Referenced by main().

fh_insertel()

static void fh_insertel ( struct fibheap *  h, struct fibheap_el *  x  )

static

References fibheap::fh_cmp_fnct, fh_insertrootlist(), fibheap::fh_keys, fibheap::fh_min, fibheap::fh_n, fibheap_el::fhe_data, and fibheap_el::fhe_key.

Referenced by fh_insert(), fh_insertkey(), and fh_replacekeydata().

fh_insertkey()

struct fibheap_el* fh_insertkey	(	struct fibheap *	h,
		int	key,
		void *	data
	)

References data, fh_insertel(), fibheap_el::fhe_data, fibheap_el::fhe_key, fhe_newelem(), and key.

Referenced by gui_internal_cmd_pois(), main(), route_graph_init(), route_graph_point_update(), and traffic_route_flood_graph().

fh_insertrootlist()

static void fh_insertrootlist ( struct fibheap *  h, struct fibheap_el *  x  )

static

References fibheap::fh_root, fhe_insertafter(), fibheap_el::fhe_left, and fibheap_el::fhe_right.

Referenced by fh_consolidate(), fh_cut(), fh_extractminel(), and fh_insertel().

fh_makeheap()

struct fibheap* fh_makeheap

(

void

)

References fh_initheap().

Referenced by main().

fh_makekeyheap()

struct fibheap* fh_makekeyheap

(

void

)

References fh_initheap(), and fibheap::fh_keys.

Referenced by gui_internal_cmd_pois(), main(), route_graph_build(), and traffic_route_flood_graph().

fh_min()

void* fh_min

(

struct fibheap *

h

)

References fibheap::fh_min, and fibheap_el::fhe_data.

Referenced by route_graph_is_path_computed().

fh_minkey()

int fh_minkey

(

struct fibheap *

h

)

References fibheap::fh_min, and fibheap_el::fhe_key.

Referenced by gui_internal_cmd_pois(), and main().

fh_removerootlist()

static void fh_removerootlist ( struct fibheap *  h, struct fibheap_el *  x  )

static

References fibheap::fh_root, fibheap_el::fhe_left, and fhe_remove().

Referenced by fh_consolidate(), and fh_extractminel().

fh_replacedata()

void* fh_replacedata	(	struct fibheap *	h,
		struct fibheap_el *	x,
		void *	data
	)

References data, fh_replacekeydata(), and fibheap_el::fhe_key.

Referenced by fh_delete(), and fh_deleteel().

fh_replacekey()

int fh_replacekey	(	struct fibheap *	h,
		struct fibheap_el *	x,
		int	key
	)

References fh_replacekeydata(), fibheap_el::fhe_data, fibheap_el::fhe_key, and key.

Referenced by fh_delete(), fh_deleteel(), main(), and traffic_route_flood_graph().

fh_replacekeydata()

void* fh_replacekeydata	(	struct fibheap *	h,
		struct fibheap_el *	x,
		int	key,
		void *	data
	)

References data, fh_cascading_cut(), fh_compare(), fh_comparedata(), fh_cut(), fh_deleteel(), fh_insertel(), fibheap::fh_keys, fibheap::fh_min, fibheap_el::fhe_data, fibheap_el::fhe_key, fibheap_el::fhe_p, and key.

Referenced by fh_replacedata(), and fh_replacekey().

fh_setcmp()

voidcmp fh_setcmp	(	struct fibheap *	h,
		voidcmp	fnct
	)

References fibheap::fh_cmp_fnct.

Referenced by main().

fh_setneginf()

void* fh_setneginf	(	struct fibheap *	h,
		void *	data
	)

References data, and fibheap::fh_neginf.

fh_union()

struct fibheap* fh_union	(	struct fibheap *	ha,
		struct fibheap *	hb
	)

References fh_compare(), fh_destroyheap(), fibheap::fh_min, fibheap::fh_n, fibheap::fh_root, fibheap_el::fhe_left, and fibheap_el::fhe_right.

fhe_initelem()

static void fhe_initelem ( struct fibheap_el *  e )

static

References fibheap_el::fhe_child, fibheap_el::fhe_data, fibheap_el::fhe_degree, fibheap_el::fhe_left, fibheap_el::fhe_mark, fibheap_el::fhe_p, and fibheap_el::fhe_right.

Referenced by fhe_newelem().

fhe_insertafter()

static void fhe_insertafter ( struct fibheap_el *  a, struct fibheap_el *  b  )

static

References fibheap_el::fhe_left, and fibheap_el::fhe_right.

Referenced by fh_insertrootlist(), and fhe_insertbefore().

fhe_insertbefore()

static void fhe_insertbefore ( struct fibheap_el *  a, struct fibheap_el *  b  )

static

References fhe_insertafter(), and fibheap_el::fhe_left.

Referenced by fh_heaplink().

fhe_newelem()

static struct fibheap_el* fhe_newelem ( void  )

static

References fhe_initelem().

Referenced by fh_insert(), and fh_insertkey().

fhe_remove()

static struct fibheap_el* fhe_remove ( struct fibheap_el *  x )

static

References fibheap_el::fhe_child, fibheap_el::fhe_left, fibheap_el::fhe_p, and fibheap_el::fhe_right.

Referenced by fh_cut(), and fh_removerootlist().