binaryheap.h File Reference

#include "config.h"
#include "thread_compat.hpp"

Include dependency graph for binaryheap.h:

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

Go to the source code of this file.

Classes
struct	binary_heap

Macros
#define	BH_ELEMENT(heap, i)   (((char *) (heap)->members) + (heap)->elem_size * (i))
#define	BH_ROOT(heap)   ((heap)->members)

Typedefs
typedef void *	BH_CMP_ARG
typedef BH_CMP_RESULT(*	bh_key_comparator) (const void *left, const void *right, BH_CMP_ARG arg)
typedef struct binary_heap	BINARY_HEAP

Enumerations
enum	BH_CMP_RESULT { BH_CMP_ERROR = -2, BH_LT = -1, BH_EQ = 0, BH_GT = 1 }
enum	BH_HEAP_STATE { BH_HEAP_INCONSISTENT, BH_HEAP_CONSISTENT, BH_SORTED_ARRAY }
enum	BH_TRY_INSERT_RESULT { BH_TRY_INSERT_REJECTED, BH_TRY_INSERT_ACCEPTED, BH_TRY_INSERT_REPLACED }

Functions
BINARY_HEAP *	bh_create (THREAD_ENTRY *thread_p, int max_capacity, int elem_size, bh_key_comparator cmp_func, BH_CMP_ARG cmp_arg)
void	bh_destroy (THREAD_ENTRY *thread_p, BINARY_HEAP *heap)
int	bh_add (BINARY_HEAP *heap, void *elem)
void	bh_build_heap (BINARY_HEAP *heap)
int	bh_insert (BINARY_HEAP *heap, void *elem)
BH_TRY_INSERT_RESULT	bh_try_insert (BINARY_HEAP *heap, void *elem, void *replaced)
void	bh_down_heap (BINARY_HEAP *heap, int index)
bool	bh_extract_max (BINARY_HEAP *heap, void *extract_elem)
bool	bh_peek_max (BINARY_HEAP *heap, void *peek_elem)
bool	bh_is_consistent (BINARY_HEAP *heap)
void	bh_to_sorted_array (BINARY_HEAP *heap)
void	bh_element_at (BINARY_HEAP *heap, int index, void *elem)
bool	bh_is_full (BINARY_HEAP *heap)

Macro Definition Documentation

#define BH_ELEMENT	(		heap,
			i
	)		(((char *) (heap)->members) + (heap)->elem_size * (i))

Definition at line 79 of file binaryheap.h.

Referenced by bh_add(), bh_element_at(), bh_extract_max(), and bh_insert().

#define BH_ROOT

(

heap

)

((heap)->members)

Definition at line 80 of file binaryheap.h.

Typedef Documentation

typedef void* BH_CMP_ARG

Definition at line 40 of file binaryheap.h.

typedef BH_CMP_RESULT(* bh_key_comparator) (const void *left, const void *right, BH_CMP_ARG arg)

Definition at line 64 of file binaryheap.h.

typedef struct binary_heap BINARY_HEAP

Definition at line 66 of file binaryheap.h.

Enumeration Type Documentation

enum BH_CMP_RESULT

Enumerator
BH_CMP_ERROR
BH_LT
BH_EQ
BH_GT

Definition at line 42 of file binaryheap.h.

enum BH_HEAP_STATE

Enumerator
BH_HEAP_INCONSISTENT
BH_HEAP_CONSISTENT
BH_SORTED_ARRAY

Definition at line 50 of file binaryheap.h.

enum BH_TRY_INSERT_RESULT

Enumerator
BH_TRY_INSERT_REJECTED
BH_TRY_INSERT_ACCEPTED
BH_TRY_INSERT_REPLACED

Definition at line 57 of file binaryheap.h.

Function Documentation

int bh_add	(	BINARY_HEAP *	heap,
		void *	elem
	)

Definition at line 184 of file binaryheap.c.

References ARG_FILE_LINE, assert, BH_ELEMENT, BH_ELEMENT_COPY, BH_HEAP_INCONSISTENT, binary_heap::element_count, ER_BINARY_HEAP_OUT_OF_RANGE, ER_ERROR_SEVERITY, er_set(), binary_heap::max_capacity, NO_ERROR, NULL, and binary_heap::state.

void bh_build_heap

(

BINARY_HEAP *

heap

)

Definition at line 278 of file binaryheap.c.

References assert, bh_down_heap(), BH_HEAP_CONSISTENT, BH_PARENT, binary_heap::element_count, i, NULL, and binary_heap::state.

BINARY_HEAP* bh_create	(	THREAD_ENTRY *	thread_p,
		int	max_capacity,
		int	elem_size,
		bh_key_comparator	cmp_func,
		BH_CMP_ARG	cmp_arg
	)

Definition at line 114 of file binaryheap.c.

References ARG_FILE_LINE, BH_HEAP_CONSISTENT, binary_heap::cmp_arg, binary_heap::cmp_func, db_private_alloc, db_private_free, binary_heap::elem_size, binary_heap::element_count, ER_ERROR_SEVERITY, ER_OUT_OF_VIRTUAL_MEMORY, er_set(), binary_heap::max_capacity, binary_heap::members, NULL, binary_heap::state, and binary_heap::swap_buf.

Referenced by fpcache_initialize(), qexec_setup_topn_proc(), xcache_cleanup(), and xcache_initialize().

Here is the caller graph for this function:

void bh_destroy	(	THREAD_ENTRY *	thread_p,
		BINARY_HEAP *	heap
	)

Definition at line 157 of file binaryheap.c.

References db_private_free, binary_heap::members, NULL, and binary_heap::swap_buf.

Referenced by fpcache_finalize(), qexec_clear_xasl(), qexec_setup_topn_proc(), qexec_topn_tuples_to_list_id(), xcache_cleanup(), and xcache_finalize().

Here is the caller graph for this function:

void bh_down_heap	(	BINARY_HEAP *	heap,
		int	index
	)

Definition at line 79 of file binaryheap.c.

References BH_CMP, bh_down_heap(), BH_GT, BH_LEFT, BH_RIGHT, and BH_SWAP.

Referenced by bh_build_heap(), bh_down_heap(), bh_extract_max(), bh_replace_max(), bh_to_sorted_array(), and qexec_add_tuple_to_topn().

Here is the caller graph for this function:

void bh_element_at	(	BINARY_HEAP *	heap,
		int	index,
		void *	elem
	)

Definition at line 442 of file binaryheap.c.

References assert, BH_ELEMENT, BH_ELEMENT_COPY, and NULL.

Referenced by fpcache_cleanup(), and xcache_cleanup().

Here is the caller graph for this function:

bool bh_extract_max	(	BINARY_HEAP *	heap,
		void *	extract_elem
	)

Definition at line 304 of file binaryheap.c.

References assert, bh_down_heap(), BH_ELEMENT, BH_ELEMENT_COPY, binary_heap::element_count, and NULL.

int bh_insert	(	BINARY_HEAP *	heap,
		void *	elem
	)

Definition at line 209 of file binaryheap.c.

References ARG_FILE_LINE, assert, assert_release, BH_ELEMENT, BH_ELEMENT_COPY, BH_HEAP_CONSISTENT, bh_up_heap(), binary_heap::element_count, ER_BINARY_HEAP_OUT_OF_RANGE, ER_ERROR_SEVERITY, er_set(), binary_heap::max_capacity, NO_ERROR, NULL, and binary_heap::state.

Referenced by bh_try_insert(), and qexec_add_tuple_to_topn().

Here is the caller graph for this function:

bool bh_is_consistent

(

BINARY_HEAP *

heap

)

Definition at line 457 of file binaryheap.c.

References assert, BH_HEAP_CONSISTENT, NULL, and binary_heap::state.

bool bh_is_full

(

BINARY_HEAP *

heap

)

Definition at line 469 of file binaryheap.c.

References assert, binary_heap::element_count, binary_heap::max_capacity, and NULL.

Referenced by qexec_add_tuple_to_topn().

Here is the caller graph for this function:

bool bh_peek_max	(	BINARY_HEAP *	heap,
		void *	peek_elem
	)

Definition at line 357 of file binaryheap.c.

References assert, BH_ELEMENT_COPY, binary_heap::element_count, and NULL.

Referenced by qexec_add_tuple_to_topn().

Here is the caller graph for this function:

void bh_to_sorted_array

(

BINARY_HEAP *

heap

)

Definition at line 378 of file binaryheap.c.

References assert, BH_CMP, bh_down_heap(), BH_HEAP_CONSISTENT, BH_HEAP_INCONSISTENT, BH_LT, BH_PARENT, BH_SORTED_ARRAY, BH_SWAP, binary_heap::element_count, i, NULL, and binary_heap::state.

Referenced by qexec_topn_tuples_to_list_id().

Here is the caller graph for this function:

BH_TRY_INSERT_RESULT bh_try_insert	(	BINARY_HEAP *	heap,
		void *	elem,
		void *	replaced
	)

Definition at line 249 of file binaryheap.c.

References assert, BH_ELEMENT_COPY, BH_GT, bh_insert(), bh_replace_max(), BH_TRY_INSERT_ACCEPTED, BH_TRY_INSERT_REJECTED, BH_TRY_INSERT_REPLACED, binary_heap::cmp_arg, binary_heap::cmp_func, binary_heap::element_count, binary_heap::max_capacity, and NULL.

Referenced by fpcache_cleanup(), and xcache_cleanup().

Here is the caller graph for this function: