heap.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_heap_node
struct	_heap

Macros
#define	heap_gen_key(hp, md)   ((hp)->gen_key((md),(hp)->age))
#define	heap_nodes(heap)   ((heap)->last)
#define	heap_empty(heap)   ((heap)->last <= 0 ? 1 : 0)

Typedefs
typedef unsigned long	heap_mutex_t
typedef void *	heap_t
typedef double	heap_key
typedef heap_key	heap_key_func(heap_t, heap_key)
typedef struct _heap_node	heap_node
typedef struct _heap	heap

Functions
SQUIDCEXTERN heap *	new_heap (int init_size, heap_key_func gen_key)
SQUIDCEXTERN void	delete_heap (heap *)
SQUIDCEXTERN heap_node *	heap_insert (heap *hp, heap_t dat)
SQUIDCEXTERN heap_t	heap_delete (heap *, heap_node *elm)
SQUIDCEXTERN heap_t	heap_update (heap *, heap_node *elm, heap_t dat)
SQUIDCEXTERN heap_t	heap_extractmin (heap *)
SQUIDCEXTERN heap_t	heap_extractlast (heap *hp)
SQUIDCEXTERN heap_key	heap_peepminkey (heap *)
SQUIDCEXTERN heap_key	heap_peepkey (heap *, int n)
SQUIDCEXTERN heap_t	heap_peepmin (heap *)
SQUIDCEXTERN heap_t	heap_peep (heap *, int n)
SQUIDCEXTERN void	heap_print (heap *)
SQUIDCEXTERN void	heap_printnode (char *msg, heap_node *elm)
SQUIDCEXTERN int	verify_heap_property (heap *)

Macro Definition Documentation

heap_empty

#define heap_empty

(

heap

)

((heap)->last <= 0 ? 1 : 0)

Definition at line 142 of file heap.h.

heap_gen_key

#define heap_gen_key	(		hp,
			md
	)		((hp)->gen_key((md),(hp)->age))

Definition at line 105 of file heap.h.

heap_nodes

#define heap_nodes

(

heap

)

((heap)->last)

Definition at line 141 of file heap.h.

Typedef Documentation

heap

typedef struct _heap heap

heap_key

typedef double heap_key

Definition at line 33 of file heap.h.

heap_key_func

typedef heap_key heap_key_func(heap_t, heap_key)

Definition at line 34 of file heap.h.

heap_mutex_t

typedef unsigned long heap_mutex_t

Definition at line 31 of file heap.h.

heap_node

typedef struct _heap_node heap_node

heap_t

typedef void* heap_t

Definition at line 32 of file heap.h.

Function Documentation

delete_heap()

SQUIDCEXTERN void delete_heap

(

heap *

hp

)

Definition at line 95 of file heap.c.

References assert, _heap::last, _heap::nodes, NULL, and xfree.

heap_delete()

SQUIDCEXTERN heap_t heap_delete	(	heap *	hp,
		heap_node *	elm
	)

Definition at line 142 of file heap.c.

References _heap_ify_down(), _heap_ify_up(), _heap_node_exist(), _heap_swap_element(), assert, _heap_node::data, heap_extractlast(), _heap_node::id, _heap_node::key, _heap::last, _heap::nodes, and Parent.

Referenced by heap_extractmin(), and heap_remove().

heap_extractlast()

SQUIDCEXTERN heap_t heap_extractlast

(

heap *

hp

)

Definition at line 210 of file heap.c.

References _heap_node_exist(), assert, _heap_node::data, _heap::last, _heap::nodes, and xfree.

Referenced by heap_delete().

heap_extractmin()

SQUIDCEXTERN heap_t heap_extractmin

(

heap *

hp

)

Definition at line 188 of file heap.c.

References _heap_node::data, heap_delete(), _heap::last, _heap::lock, mutex_lock, mutex_unlock, _heap::nodes, and NULL.

Referenced by heap_purgeNext().

heap_insert()

SQUIDCEXTERN heap_node * heap_insert	(	heap *	hp,
		heap_t	dat
	)

Definition at line 117 of file heap.c.

References _heap_grow(), _heap_ify_up(), _heap_should_grow(), _heap_node::data, heap_gen_key, _heap_node::id, _heap_node::key, _heap::last, _heap::nodes, and xmalloc.

Referenced by heap_add(), and heap_purgeDone().

heap_peep()

SQUIDCEXTERN heap_t heap_peep	(	heap *	hp,
		int	n
	)

Definition at line 281 of file heap.c.

References _heap_node_exist(), assert, _heap_node::data, and _heap::nodes.

Referenced by heap_walkNext().

heap_peepkey()

SQUIDCEXTERN heap_key heap_peepkey	(	heap *	hp,
		int	n
	)

Definition at line 268 of file heap.c.

References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.

heap_peepmin()

SQUIDCEXTERN heap_t heap_peepmin

(

heap *

hp

)

Definition at line 247 of file heap.c.

References _heap_node_exist(), assert, _heap_node::data, and _heap::nodes.

heap_peepminkey()

SQUIDCEXTERN heap_key heap_peepminkey

(

heap *

hp

)

Definition at line 257 of file heap.c.

References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.

Referenced by heap_purgeNext().

heap_print()

SQUIDCEXTERN void heap_print

(

heap *

)

heap_printnode()

SQUIDCEXTERN void heap_printnode	(	char *	msg,
		heap_node *	elm
	)

heap_update()

SQUIDCEXTERN heap_t heap_update	(	heap *	hp,
		heap_node *	elm,
		heap_t	dat
	)

Definition at line 228 of file heap.c.

References _heap_ify_down(), _heap_ify_up(), _heap_node::data, heap_gen_key, _heap_node::id, _heap_node::key, _heap::nodes, and Parent.

Referenced by heap_referenced().

new_heap()

SQUIDCEXTERN heap * new_heap	(	int	init_size,
		heap_key_func	gen_key
	)

Definition at line 72 of file heap.c.

References _heap::age, assert, _heap::gen_key, _heap::last, MinSize, _heap::nodes, NULL, _heap::size, xcalloc(), and xmalloc.

Referenced by createRemovalPolicy_heap().

verify_heap_property()

SQUIDCEXTERN int verify_heap_property

(

heap *

hp

)

Definition at line 436 of file heap.c.

References _heap_node_exist(), heap_print_inorder(), _heap_node::key, _heap::last, Left, _heap::nodes, and Right.