CUBRID Engine: src/base/binaryheap.c File Reference

CUBRID Engine latest

#include <stdlib.h>
#include <assert.h>
#include "binaryheap.h"
#include "memory_alloc.h"
#include "error_manager.h"

Include dependency graph for binaryheap.c:

Go to the source code of this file.

Macros
#define	BH_PARENT(i) ((i - 1)/2)

#define	BH_LEFT(i) (2*(i) + 1)

#define	BH_RIGHT(i) (2*(i)+2)

#define	BH_ELEMENT_COPY(heap, dest, src) (memcpy (dest, src, (heap)->elem_size))

#define	BH_SWAP(heap, left, right)

#define	BH_CMP(heap, l, r) (heap->cmp_func (BH_ELEMENT (heap, l), BH_ELEMENT (heap, r), heap->cmp_arg))

Functions
static void	bh_up_heap (BINARY_HEAP *heap, int index)

static void	bh_replace_max (BINARY_HEAP heap, void elem)

void	bh_down_heap (BINARY_HEAP *heap, int index)

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)

int	bh_insert (BINARY_HEAP heap, void elem)

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

void	bh_build_heap (BINARY_HEAP *heap)

bool	bh_extract_max (BINARY_HEAP heap, void extract_elem)

bool	bh_peek_max (BINARY_HEAP heap, void peek_elem)

void	bh_to_sorted_array (BINARY_HEAP *heap)

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

bool	bh_is_consistent (BINARY_HEAP *heap)

bool	bh_is_full (BINARY_HEAP *heap)

Macro Definition Documentation

#define BH_CMP	(		heap,
			l,
			r
	)		(heap->cmp_func (BH_ELEMENT (heap, l), BH_ELEMENT (heap, r), heap->cmp_arg))

Definition at line 42 of file binaryheap.c.

Referenced by bh_down_heap(), bh_to_sorted_array(), and bh_up_heap().

#define BH_ELEMENT_COPY	(		heap,
			dest,
			src
	)		(memcpy (dest, src, (heap)->elem_size))

Definition at line 31 of file binaryheap.c.

Referenced by bh_add(), bh_element_at(), bh_extract_max(), bh_insert(), bh_peek_max(), bh_replace_max(), and bh_try_insert().

#define BH_LEFT ( i ) (2*(i) + 1)

Definition at line 29 of file binaryheap.c.

Referenced by bh_down_heap().

#define BH_PARENT ( i ) ((i - 1)/2)

Definition at line 28 of file binaryheap.c.

Referenced by bh_build_heap(), bh_to_sorted_array(), and bh_up_heap().

#define BH_RIGHT ( i ) (2*(i)+2)

Definition at line 30 of file binaryheap.c.

Referenced by bh_down_heap().

#define BH_SWAP	(		heap,
			left,
			right
	)

Value:

do                                            \
    {                                             \
      BH_ELEMENT_COPY (heap, (heap)->swap_buf, BH_ELEMENT (heap, left));          \
      BH_ELEMENT_COPY (heap, BH_ELEMENT (heap, left), BH_ELEMENT (heap, right));      \
      BH_ELEMENT_COPY (heap, BH_ELEMENT (heap, right), (heap)->swap_buf);         \
    }                                             \
  while (0)

Definition at line 33 of file binaryheap.c.

Referenced by bh_down_heap(), bh_to_sorted_array(), and bh_up_heap().

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_replace_max	(	BINARY_HEAP *	heap,
		void *	elem
	)

static

Definition at line 340 of file binaryheap.c.

References assert, bh_down_heap(), BH_ELEMENT_COPY, and NULL.

Referenced by bh_try_insert().

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:

static void bh_up_heap	(	BINARY_HEAP *	heap,
		int	index
	)

static

Definition at line 56 of file binaryheap.c.

References BH_CMP, BH_LT, BH_PARENT, and BH_SWAP.

Referenced by bh_insert().

Here is the caller graph for this function:

src
base
binaryheap.c
Generated by 1.8.11