Bounded_queue< Element_type, Key_type > Class Template Reference

#include <bounded_queue.h>

Public Types
typedef void(*	keymaker_function )(Sort_param *param, Key_type *to, Element_type *from)
typedef int(*	compare_function )(size_t *n, Key_type **a, Key_type **b)

Public Member Functions
int	init (ha_rows max_elements, bool max_at_top, compare_function compare, size_t compare_length, keymaker_function keymaker, Sort_param *sort_param, Key_type **sort_keys)
void	push (Element_type *element)
Key_type **	pop ()
uint	num_elements () const
bool	is_initialized () const

Detailed Description

template<typename Element_type, typename Key_type>
class Bounded_queue< Element_type, Key_type >

A priority queue with a fixed, limited size.

This is a wrapper on top of QUEUE and the queue_xxx() functions. It keeps the top-N elements which are inserted.

Elements of type Element_type are pushed into the queue. For each element, we call a user-supplied keymaker_function, to generate a key of type Key_type for the element. Instances of Key_type are compared with the user-supplied compare_function.

The underlying QUEUE implementation needs one extra element for replacing the lowest/highest element when pushing into a full queue.

Definition at line 42 of file bounded_queue.h.

Member Typedef Documentation

template<typename Element_type, typename Key_type>

typedef int(* Bounded_queue< Element_type, Key_type >::compare_function)(size_t *n, Key_type **a, Key_type **b)

Function for comparing two keys.

Parameters

n	Pointer to number of bytes to compare.
a	First key.
b	Second key.

Return values

-1,0,or

1 depending on whether the left argument is less than, equal to, or greater than the right argument.

Definition at line 73 of file bounded_queue.h.

template<typename Element_type, typename Key_type>

typedef void(* Bounded_queue< Element_type, Key_type >::keymaker_function)(Sort_param *param, Key_type *to, Element_type *from)

Function for making sort-key from input data.

Parameters

param	Sort parameters.
to	Where to put the key.
from	The input data.

Definition at line 61 of file bounded_queue.h.

Member Function Documentation

template<typename Element_type , typename Key_type>

int Bounded_queue< Element_type, Key_type >::init	(	ha_rows	max_elements,
		bool	max_at_top,
		compare_function	compare,
		size_t	compare_length,
		keymaker_function	keymaker,
		Sort_param *	sort_param,
		Key_type **	sort_keys
	)

Initialize the queue.

Parameters

max_elements	The size of the queue.
max_at_top	Set to true if you want biggest element on top. false: We keep the n largest elements. pop() will return the smallest key in the result set. true: We keep the n smallest elements. pop() will return the largest key in the result set.
compare	Compare function for elements, takes 3 arguments. If NULL, we use get_ptr_compare(compare_length).
compare_length	Length of the data (i.e. the keys) used for sorting.
keymaker	Function which generates keys for elements.
sort_param	Sort parameters.
sort_keys	Array of pointers to keys to sort.

Return values

0	OK, 1 Could not allocate memory.

We do not take ownership of any of the input pointer arguments.

Definition at line 149 of file bounded_queue.h.

Here is the caller graph for this function:

template<typename Element_type, typename Key_type>

bool Bounded_queue< Element_type, Key_type >::is_initialized ( ) const

inline

Is the queue initialized?

Definition at line 137 of file bounded_queue.h.

Here is the caller graph for this function:

template<typename Element_type, typename Key_type>

uint Bounded_queue< Element_type, Key_type >::num_elements ( ) const

inline

The number of elements in the queue.

Definition at line 132 of file bounded_queue.h.

template<typename Element_type, typename Key_type>

Key_type** Bounded_queue< Element_type, Key_type >::pop ( )

inline

Removes the top element from the queue.

Return values

Pointer

to the (key of the) removed element.

Note

This function is for unit testing, where we push elements into to the queue, and test that the appropriate keys are retained. Interleaving of push() and pop() operations has not been tested.

Definition at line 118 of file bounded_queue.h.

template<typename Element_type, typename Key_type >

void Bounded_queue< Element_type, Key_type >::push

(

Element_type *

element

)

Pushes an element on the queue. If the queue is already full, we discard one element. Calls keymaker_function to generate a key for the element.

Parameters

element

The element to be pushed.

Definition at line 182 of file bounded_queue.h.

---

The documentation for this class was generated from the following file:

• sql/bounded_queue.h