T must be a subclass of InternalQueue::Node. More...

#include <internal-queue.h>

Collaboration diagram for impala::InternalQueue< T >:

Classes
struct	Node

Public Member Functions
	InternalQueue ()

T *	head () const

T *	tail ()

void	Enqueue (T *n)
	Enqueue node onto the queue's tail. This is O(1). More...

T *	Dequeue ()

T *	PopBack ()

void	Remove (T *n)

void	Clear ()
	Clears all elements in the list. More...

int	size () const

bool	empty () const

bool	Contains (const T *target) const

bool	Validate ()
	Validates the internal structure of the list. More...

std::string	DebugString ()
	Prints the queue ptrs to a string. More...

Private Attributes
SpinLock	lock_

Node *	head_

Node *	tail_

int	size_

Friends
struct	Node

Detailed Description

template<typename T>
class impala::InternalQueue< T >

T must be a subclass of InternalQueue::Node.

Thread safe fifo-queue. This is an internal queue, meaning the links to nodes are maintained in the object itself. This is in contrast to the stl list which allocates a wrapper Node object around the data. Since it's an internal queue, the list pointers are maintained in the Nodes which is memory owned by the user. The nodes cannot be deallocated while the queue has elements. To use: subclass InternalQueue::Node. The internal structure is a doubly-linked list. NULL <– N1 <–> N2 <–> N3 –> NULL (head) (tail) TODO: this is an ideal candidate to be made lock free.

Definition at line 40 of file internal-queue.h.

Constructor & Destructor Documentation

template<typename T>

impala::InternalQueue< T >::InternalQueue ( )

inline

Definition at line 66 of file internal-queue.h.

Member Function Documentation

template<typename T>

void impala::InternalQueue< T >::Clear ( )

inline

Clears all elements in the list.

Definition at line 184 of file internal-queue.h.

Referenced by impala::TEST().

template<typename T>

bool impala::InternalQueue< T >::Contains ( const T * target ) const

inline

Returns if the target is on the queue. This is O(1) and intended to be used for debugging.

Definition at line 202 of file internal-queue.h.

Referenced by impala::AdmissionController::AdmitQuery().

template<typename T>

std::string impala::InternalQueue< T >::DebugString ( )

inline

Prints the queue ptrs to a string.

Definition at line 234 of file internal-queue.h.

template<typename T>

T* impala::InternalQueue< T >::Dequeue ( )

inline

Dequeues an element from the queue's head. Returns NULL if the queue is empty. This is O(1).

Definition at line 103 of file internal-queue.h.

Referenced by impala::ConsumerThread(), impala::AdmissionController::DequeueLoop(), and impala::TEST().

template<typename T>

bool impala::InternalQueue< T >::empty ( ) const

inline

Definition at line 198 of file internal-queue.h.

Referenced by impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Dequeue(), impala::AdmissionController::DequeueLoop(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::head(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::PopBack(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::tail(), and impala::TEST().

template<typename T>

void impala::InternalQueue< T >::Enqueue ( T * n )

inline

Enqueue node onto the queue's tail. This is O(1).

Definition at line 85 of file internal-queue.h.

Referenced by impala::AdmissionController::AdmitQuery(), impala::ProducerThread(), and impala::TEST().

template<typename T>

T* impala::InternalQueue< T >::head ( ) const

inline

Returns the element at the head of the list without dequeuing or NULL if the queue is empty. This is O(1).

Definition at line 70 of file internal-queue.h.

Referenced by impala::AdmissionController::DequeueLoop(), and impala::TEST().

template<typename T>

T* impala::InternalQueue< T >::PopBack ( )

inline

Dequeues an element from the queue's tail. Returns NULL if the queue is empty. This is O(1).

Definition at line 125 of file internal-queue.h.

Referenced by impala::TEST().

template<typename T>

void impala::InternalQueue< T >::Remove ( T * n )

inline

Removes 'node' from the queue. This is O(1). No-op if node is not on the list.

Definition at line 147 of file internal-queue.h.

Referenced by impala::AdmissionController::AdmitQuery(), and impala::TEST().

template<typename T>

int impala::InternalQueue< T >::size ( ) const

inline

Definition at line 197 of file internal-queue.h.

Referenced by impala::TEST(), and impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Validate().

template<typename T>

T* impala::InternalQueue< T >::tail ( )

inline

Returns the element at the end of the list without dequeuing or NULL if the queue is empty. This is O(1).

Definition at line 78 of file internal-queue.h.

Referenced by impala::TEST().

template<typename T>

bool impala::InternalQueue< T >::Validate ( )

inline

Validates the internal structure of the list.

Definition at line 207 of file internal-queue.h.

Referenced by impala::ConsumerThread(), impala::ProducerThread(), and impala::TEST().

Friends And Related Function Documentation

template<typename T>

friend struct Node

friend

Definition at line 250 of file internal-queue.h.

Referenced by impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Clear(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::DebugString(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Dequeue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Enqueue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::PopBack(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Remove(), and impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Validate().

Member Data Documentation

template<typename T>

Node* impala::InternalQueue< T >::head_

private

Definition at line 252 of file internal-queue.h.

template<typename T>

SpinLock impala::InternalQueue< T >::lock_

mutableprivate

Definition at line 251 of file internal-queue.h.

template<typename T>

int impala::InternalQueue< T >::size_

private

Definition at line 253 of file internal-queue.h.

Referenced by impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Clear(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Dequeue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Enqueue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::PopBack(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Remove(), and impala::InternalQueue< impala::DiskIoMgr::WriteRange >::size().

template<typename T>

Node * impala::InternalQueue< T >::tail_

private

Definition at line 252 of file internal-queue.h.

Referenced by impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Clear(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Dequeue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Enqueue(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::PopBack(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Remove(), impala::InternalQueue< impala::DiskIoMgr::WriteRange >::tail(), and impala::InternalQueue< impala::DiskIoMgr::WriteRange >::Validate().

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

be/src/util/internal-queue.h

Classes

Public Member Functions

Private Attributes

Friends

Detailed Description

template<typename T> class impala::InternalQueue< T >

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename T>
class impala::InternalQueue< T >