greenplumn CList 源码

greenplumn CList 代码

文件路径：/src/backend/gporca/libgpos/include/gpos/common/CList.h

//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright (C) 2008 - 2010 Greenplum, Inc.
//
//	@filename:
//		CList.h
//
//	@doc:
//		Template-based list class;
//		In order to be useful for system programming the class must be
//		allocation-less, i.e. manage elements without additional allocation,
//		to work in exception or OOM situations
//---------------------------------------------------------------------------
#ifndef GPOS_CList_H
#define GPOS_CList_H

#include "gpos/common/CLink.h"
#include "gpos/task/ITask.h"
#include "gpos/types.h"
#include "gpos/utils.h"

namespace gpos
{
// forward declaration
template <class T>
class CSyncList;

//---------------------------------------------------------------------------
//	@class:
//		CList<class T>
//
//	@doc:
//		Allocation-less list class; requires T to have SLink embedded and
//		N being the offset of this member;
//
//		Unfortunately not all compilers support use of an offset macro as
//		template parameter; hence, we have to provide offset as parameter to
//		constructor
//
//---------------------------------------------------------------------------
template <class T>
class CList
{
	// friends
	friend class CSyncList<T>;

private:
	// offest of link element
	ULONG m_offset{gpos::ulong_max};

	// size
	ULONG m_size{0};

	// head element
	T *m_head;

	// tail element
	T *m_tail;

	// extract link from element
	SLink &
	Link(const void *pv) const
	{
		GPOS_ASSERT(MAX_ALIGNED(pv));
		GPOS_ASSERT(MAX_ALIGNED(m_offset));

		GPOS_ASSERT(gpos::ulong_max != m_offset &&
					"Link offset not initialized.");
		SLink &link = *(SLink *) (((BYTE *) pv) + m_offset);
		return link;
	}

public:
	CList(const CList &) = delete;

	// ctor
	CList() : m_head(nullptr), m_tail(nullptr)
	{
	}

	// init function to facilitate arrays
	void
	Init(ULONG offset)
	{
		GPOS_ASSERT(MAX_ALIGNED(offset));
		m_offset = offset;
	}

	// Insert by prepending/appending to current list
	void
	Prepend(T *elem)
	{
		GPOS_ASSERT(nullptr != elem);

		// inserting first element?
		if (nullptr == m_head)
		{
			GPOS_ASSERT(nullptr == m_tail);
			GPOS_ASSERT(0 == m_size);
			SLink &link = Link(elem);

			link.m_next = nullptr;
			link.m_prev = nullptr;

			m_head = elem;
			m_tail = elem;

			m_size++;
		}
		else
		{
			Prepend(elem, m_head);
		}

		GPOS_ASSERT(0 != m_size);
	}

	void
	Append(T *elem)
	{
		GPOS_ASSERT(nullptr != elem);

		if (nullptr == m_tail)
		{
			Prepend(elem);
		}
		else
		{
			Append(elem, m_tail);
		}

		GPOS_ASSERT(0 != m_size);
	}

	// Insert by prepending/appending relative to given position
	void
	Prepend(T *elem, T *next_elem)
	{
		GPOS_ASSERT(nullptr != elem);
		GPOS_ASSERT(nullptr != next_elem);
		T *prev = static_cast<T *>(Link(next_elem).m_prev);

		SLink &link = Link(elem);
		link.m_next = next_elem;
		link.m_prev = prev;

		Link(next_elem).m_prev = elem;
		if (nullptr != prev)
		{
			// inserted not at head, ie valid prev element
			Link(prev).m_next = elem;
		}
		else
		{
			// prepended to head
			m_head = elem;
		}

		m_size++;
	}

	void
	Append(T *elem, T *prev_elem)
	{
		GPOS_ASSERT(nullptr != elem);
		GPOS_ASSERT(nullptr != prev_elem);
		T *next = static_cast<T *>(Link(prev_elem).m_next);

		SLink &sl = Link(elem);
		sl.m_prev = prev_elem;
		sl.m_next = next;

		Link(prev_elem).m_next = elem;
		if (nullptr != next)
		{
			// inserted not at tail, ie valid next element
			Link(next).m_prev = elem;
		}
		else
		{
			// appended to tail
			m_tail = elem;
		}

		m_size++;
	}

	// remove element by navigating and manipulating its SLink member
	void
	Remove(T *elem)
	{
		GPOS_ASSERT(nullptr != elem);
		GPOS_ASSERT(nullptr != m_head);
		GPOS_ASSERT(nullptr != m_tail);
		GPOS_ASSERT(0 != m_size);

		SLink &link = Link(elem);

		if (link.m_next)
		{
			Link(link.m_next).m_prev = link.m_prev;
		}
		else
		{
			// removing tail element
			GPOS_ASSERT(m_tail == elem);
			m_tail = static_cast<T *>(link.m_prev);
		}

		if (link.m_prev)
		{
			Link(link.m_prev).m_next = link.m_next;
		}
		else
		{
			// removing head element
			GPOS_ASSERT(m_head == elem);
			m_head = static_cast<T *>(link.m_next);
		}

		// unlink element
		link.m_prev = nullptr;
		link.m_next = nullptr;

		m_size--;
	}

	// remove and return first element
	T *
	RemoveHead()
	{
		T *head = m_head;
		Remove(m_head);
		return head;
	}

	// remove and return last element
	T *
	RemoveTail()
	{
		T *tail = m_tail;
		Remove(m_tail);
		return tail;
	}

	// accessor to head of list
	T *
	First() const
	{
		return m_head;
	}

	// accessor to tail of list
	T *
	Last() const
	{
		return m_tail;
	}

	// traversal functions Next and PtPrev assume
	// that the pointer passed is a valid member of the list
	T *
	Next(const T *pt) const
	{
		GPOS_ASSERT(nullptr != pt);
		GPOS_ASSERT(nullptr != m_head);
		GPOS_ASSERT(nullptr != m_tail);

		SLink &sl = Link(pt);
		return static_cast<T *>(sl.m_next);
	}

	// and backward...
	T *
	Prev(const T *pt) const
	{
		GPOS_ASSERT(nullptr != pt);
		GPOS_ASSERT(nullptr != m_head);
		GPOS_ASSERT(nullptr != m_tail);

		SLink &sl = Link(pt);
		return static_cast<T *>(sl.m_prev);
	}

	// get size
	ULONG
	Size() const
	{
		return m_size;
	}

	// check if empty
	BOOL
	IsEmpty() const
	{
		return nullptr == First();
	}

#ifdef GPOS_DEBUG
	// lookup a given element in the list
	GPOS_RESULT
	Find(T *elem) const
	{
		GPOS_ASSERT(nullptr != elem);

		// iterate until found
		T *t = First();
		while (t)
		{
			if (elem == t)
			{
				return GPOS_OK;
			}
			t = Next(t);
		}
		return GPOS_NOT_FOUND;
	}

	// debug print of element addresses
	IOstream &
	OsPrint(IOstream &os) const
	{
		ULONG c = 0;

		T *t = First();

		do
		{
			os << "[" << c++ << "]" << (void *) t
			   << (nullptr == t ? "" : " -> ");
		} while (t && (t = Next(t)));
		os << std::endl;

		return os;
	}
#endif	// GPOS_DEBUG

};	// class CList<T>
}  // namespace gpos

#endif	// !GPOS_CList_H

// EOF

相关信息

greenplumn 源码目录

相关文章

greenplumn CAutoP 源码

greenplumn CAutoRef 源码

greenplumn CAutoRg 源码

greenplumn CAutoTimer 源码

greenplumn CBitSet 源码

greenplumn CBitSetIter 源码

greenplumn CBitVector 源码

greenplumn CDebugCounter 源码

greenplumn CDouble 源码

greenplumn CDynamicPtrArray 源码