framework/delibs/depool/dePoolArray.h

#ifndef _DEPOOLARRAY_H
#define _DEPOOLARRAY_H
/*-------------------------------------------------------------------------
 * drawElements Memory Pool Library
 * --------------------------------
 *
 * Copyright 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 *//*!
 * \file
 * \brief Memory pool array class.
 *//*--------------------------------------------------------------------*/

#include "deDefs.h"
#include "deMemPool.h"

enum
{
	DE_ARRAY_ELEMENTS_PER_PAGE_LOG2	= 4		/*!< \internal 16 */
};

/*--------------------------------------------------------------------*//*!
 * \internal
 * \brief Type-independent version of the array template class.
 *//*--------------------------------------------------------------------*/
typedef struct dePoolArray_s
{
	deMemPool*		pool;				/*!< Pool from which all memory is allocated from.	*/

	int				elementSize;		/*!< Size of the element (in bytes).				*/
	int				numElements;		/*!< Number of elements in the array.				*/
	int				capacity;			/*!< Number of allocated elements in the array.		*/

	int				pageTableCapacity;	/*!< Size of the page table.						*/
	void**			pageTable;			/*!< Pointer to the page table.						*/
} dePoolArray;

DE_BEGIN_EXTERN_C

dePoolArray*	dePoolArray_create			(deMemPool* pool, int elementSize);
deBool			dePoolArray_reserve			(dePoolArray* arr, int capacity);
deBool			dePoolArray_setSize			(dePoolArray* arr, int size);

void			dePoolArray_selfTest		(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool array class.
 * \param TYPENAME	Type name of the declared array.
 * \param VALUETYPE	Type of the value contained in the array.
 *
 * This macro declares a pool array with all the necessary functions for
 * operating with it. All allocated memory is taken from the memory pool
 * given to the constructor.
 *
 * The array is implemented by having a set of pages (which store the
 * elements) and a page table with pointers to each of them. The pages
 * are allocated individually whenever they are needed, but the page
 * table grows exponentially. This keeps the memory overhead for large
 * arrays very small. On the other hand, the relative overhead for very
 * small arrays is prohibitive (the minimum allocation is 16 elements).
 *
 * The functions for operating the array are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * Array*   Array_create            (deMemPool* pool);
 * int      Array_getNumElements    (const Array* array);
 * deBool   Array_reserve           (Array* array, int size);
 * deBool   Array_setSize           (Array* array, int size);
 * void		Array_reset				(Array* array);
 * Element  Array_get               (Array* array, int ndx);
 * deBool   Array_set               (Array* array, int ndx, Element elem);
 * deBool   Array_pushBack          (Array* array, Element elem);
 * Element  Array_popBack           (Array* array);
 * void     Array_swap              (Array* array, int aNdx, int bNdx);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_ARRAY(TYPENAME, VALUETYPE)		\
    \
typedef struct TYPENAME##_s					\
{											\
	deMemPool*			pool;				\
											\
	int					elementSize;		\
	int					numElements;		\
	int					capacity;			\
											\
	int					pageTableCapacity;	\
	DE_PTR_TYPE(VALUETYPE)*	pageTable;		\
} TYPENAME; /* NOLINT(TYPENAME) */			\
\
DE_INLINE TYPENAME*	TYPENAME##_create			(deMemPool* pool);															\
DE_INLINE int		TYPENAME##_getNumElements	(const TYPENAME* arr)									DE_UNUSED_FUNCTION;	\
DE_INLINE deBool	TYPENAME##_reserve			(DE_PTR_TYPE(TYPENAME) arr, int capacity)				DE_UNUSED_FUNCTION;	\
DE_INLINE deBool	TYPENAME##_setSize			(DE_PTR_TYPE(TYPENAME) arr, int size)					DE_UNUSED_FUNCTION;	\
DE_INLINE void		TYPENAME##_reset			(DE_PTR_TYPE(TYPENAME) arr)								DE_UNUSED_FUNCTION;	\
DE_INLINE VALUETYPE	TYPENAME##_get				(const TYPENAME* arr, int ndx)							DE_UNUSED_FUNCTION;	\
DE_INLINE void		TYPENAME##_set				(DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem)	DE_UNUSED_FUNCTION;	\
DE_INLINE deBool	TYPENAME##_pushBack			(DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem)				DE_UNUSED_FUNCTION;	\
DE_INLINE VALUETYPE	TYPENAME##_popBack			(DE_PTR_TYPE(TYPENAME) arr)								DE_UNUSED_FUNCTION;	\
DE_INLINE deBool	TYPENAME##_copy				(DE_PTR_TYPE(TYPENAME) dst, const TYPENAME* src)		DE_UNUSED_FUNCTION;	\
DE_INLINE void		TYPENAME##_swap				(DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx)			DE_UNUSED_FUNCTION;	\
\
DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool)    \
{    \
	return (TYPENAME*)dePoolArray_create(pool, sizeof(VALUETYPE));    \
}    \
\
DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* arr)    \
{    \
	return arr->numElements;    \
}    \
\
DE_INLINE deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) arr, int capacity)    \
{    \
	if (capacity > arr->capacity)    \
		return dePoolArray_reserve((dePoolArray*)arr, capacity);    \
	return  DE_TRUE;    \
}    \
\
DE_INLINE deBool TYPENAME##_setSize (DE_PTR_TYPE(TYPENAME) arr, int size)    \
{    \
	if (size > arr->capacity)    \
		return dePoolArray_setSize((dePoolArray*)arr, size);    \
\
	arr->numElements = size;    \
	return DE_TRUE;    \
}    \
\
DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) arr)    \
{    \
	arr->numElements = 0;    \
}    \
\
DE_INLINE VALUETYPE TYPENAME##_get (const TYPENAME* arr, int ndx)    \
{    \
	DE_ASSERT(ndx >= 0 && ndx < arr->numElements);    \
	{    \
		int pageNdx	= (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
		int subNdx	= ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
		return ((VALUETYPE*)arr->pageTable[pageNdx])[subNdx];    \
	}    \
}    \
\
DE_INLINE void TYPENAME##_set (DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem)    \
{    \
	DE_ASSERT(ndx >= 0 && ndx < arr->numElements);    \
	{    \
		int pageNdx	= (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
		int subNdx	= ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
		((VALUETYPE*)arr->pageTable[pageNdx])[subNdx] = elem;    \
	}    \
}    \
\
DE_INLINE deBool TYPENAME##_pushBack (DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem)    \
{    \
	if ((arr->numElements + 1 >= arr->capacity) && !TYPENAME##_reserve(arr, arr->numElements + 1)) \
		return DE_FALSE; \
	arr->numElements++; \
	TYPENAME##_set(arr, arr->numElements - 1, elem); \
	return DE_TRUE;    \
}    \
\
DE_INLINE VALUETYPE TYPENAME##_popBack (DE_PTR_TYPE(TYPENAME) arr)    \
{    \
	int ndx		= arr->numElements - 1; \
	int pageNdx	= (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
	int subNdx	= ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
	DE_ASSERT(arr->numElements > 0); \
	arr->numElements--; \
	/* \note We access a value which is out-of-bounds, but we know it to be safe. */ \
	return ((VALUETYPE*)arr->pageTable[pageNdx])[subNdx];    \
}    \
\
DE_INLINE deBool TYPENAME##_copy (DE_PTR_TYPE(TYPENAME) dst, const TYPENAME* src)		\
{																			\
	DE_ASSERT(dst && src);													\
	{																		\
		int numElements = src->numElements;									\
		int ndx;															\
		if (!TYPENAME##_setSize(dst, numElements))							\
			return DE_FALSE;												\
		for (ndx = 0; ndx < numElements; ndx++)								\
			TYPENAME##_set(dst, ndx, TYPENAME##_get(src, ndx));				\
	}																		\
	return DE_TRUE;															\
}																			\
\
DE_INLINE void TYPENAME##_swap (DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx)	\
{	\
	VALUETYPE tmp = TYPENAME##_get(arr, aNdx);	\
	TYPENAME##_set(arr, aNdx, TYPENAME##_get(arr, bNdx));	\
	TYPENAME##_set(arr, bNdx, tmp);	\
}	\
\
struct TYPENAME##Unused_s { int unused; }

/*--------------------------------------------------------------------*//*!
 * \brief Declare a sort function for an array.
 * \param TYPENAME	Type name of the declared array.
 * \param VALUETYPE	Type of the value contained in the array.
 * \param SORTNAME	Name for this specific sort.
 * \param CMPFUNC	Comparison function for sorting.
 *
 * This macro declares a sort function for an array declared using
 * DE_DECLARE_POOL_ARRAY macro.
 *
 * Sorting algorithm is heap sort since it requires constant amount of
 * auxiliary space and is in-place sort. Worst-case run-time is O(n log n)
 * and sort is NOT stable.
 *
 * CMPFUNC is used to compare elements in array. It must accept two
 * parameters and return negative integer if first is smaller than, 0 if
 * both are equal and positive integer if first is larger than second.
 *
 * The functions for sorting array are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * void		Array_sortName			(Array* array);
 * void		Array_sortNameHeapify	(Array* array);
 * void		Array_sortNameShiftDown	(Array* array, int start, int end);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_ARRAY_SORT(TYPENAME, VALUETYPE, SORTNAME, CMPFUNC)	\
\
DE_INLINE void TYPENAME##_##SORTNAME##ShiftDown (DE_PTR_TYPE(TYPENAME) arr, int startNdx, int endNdx)	\
{	\
	int rootNdx = startNdx;	\
	\
	while (rootNdx * 2 + 1 <= endNdx)	\
	{	\
		int childNdx = rootNdx * 2 + 1;	\
		\
		if ((childNdx + 1 <= endNdx) && (CMPFUNC(TYPENAME##_get(arr, childNdx), TYPENAME##_get(arr, childNdx + 1)) < 0))	\
			childNdx += 1;	\
		\
		if (CMPFUNC(TYPENAME##_get(arr, rootNdx), TYPENAME##_get(arr, childNdx)) < 0)	\
		{	\
			TYPENAME##_swap(arr, rootNdx, childNdx);	\
			rootNdx = childNdx;	\
		}	\
		else	\
			break;	\
	}	\
}	\
\
DE_INLINE void TYPENAME##_##SORTNAME##Heapify (DE_PTR_TYPE(TYPENAME) arr)	\
{	\
	int startNdx = (TYPENAME##_getNumElements(arr) - 2) / 2;	\
	\
	while (startNdx >= 0)	\
	{	\
		TYPENAME##_##SORTNAME##ShiftDown(arr, startNdx, TYPENAME##_getNumElements(arr) - 1);	\
		startNdx -= 1;	\
	}	\
}	\
\
DE_INLINE void TYPENAME##_##SORTNAME (DE_PTR_TYPE(TYPENAME) arr)	\
{	\
	int endNdx = TYPENAME##_getNumElements(arr) - 1;	\
	\
	TYPENAME##_##SORTNAME##Heapify(arr);	\
	\
	while (endNdx > 0)	\
	{	\
		TYPENAME##_swap(arr, endNdx, 0);	\
		endNdx -= 1;	\
		TYPENAME##_##SORTNAME##ShiftDown(arr, 0, endNdx);	\
	}	\
}	\
\
struct TYPENAME##SORTNAME##unused_s { int unused; }

/* Basic array types. */

DE_DECLARE_POOL_ARRAY(deIntArray, int);
DE_DECLARE_POOL_ARRAY(deInt8Array, deInt8);
DE_DECLARE_POOL_ARRAY(deUint8Array, deUint8);
DE_DECLARE_POOL_ARRAY(deInt16Array, deInt16);
DE_DECLARE_POOL_ARRAY(deUint16Array, deUint16);
DE_DECLARE_POOL_ARRAY(deInt32Array, deInt32);
DE_DECLARE_POOL_ARRAY(deUint32Array, deUint32);

#endif /* _DEPOOLARRAY_H */