| #ifndef _DEPOOLHASHARRAY_H |
| #define _DEPOOLHASHARRAY_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 hash-array class. |
| *//*--------------------------------------------------------------------*/ |
| |
| #include "deDefs.h" |
| #include "dePoolHash.h" |
| #include "dePoolArray.h" |
| |
| DE_BEGIN_EXTERN_C |
| |
| void dePoolHashArray_selfTest (void); |
| |
| DE_END_EXTERN_C |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Declare a template pool hash-array (array with hash) class interface. |
| * \param TYPENAME Type name of the declared hash-array. |
| * \param KEYTYPE Type of the key. |
| * \param VALUETYPE Type of the value. |
| * \param KEYARRAYTYPE Type of the key array. |
| * \param VALUEARRAYTYPE Type of the value array. |
| * |
| * \todo [petri] Description. |
| * |
| * The functions for operating the hash are: |
| * \todo [petri] Figure out how to comment these in Doxygen-style. |
| * |
| * \todo [pyry] HashArray_find() will break if dePoolArray implementation changes. |
| * |
| * \code |
| * HashArray* HashArray_create (deMemPool* pool); |
| * int HashArray_getNumElements (const HashArray* hashArray); |
| * Value* HashArray_find (Hash* hashArray, Key key); |
| * deBool HashArray_insert (Hash* hashArray, Key key, Value value); |
| * deBool HashArray_copyToArray (Hash* hashArray, KeyArray* keys, ValueArray* values); |
| * \endcode |
| *//*--------------------------------------------------------------------*/ |
| #define DE_DECLARE_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE) \ |
| \ |
| DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE); \ |
| DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \ |
| \ |
| typedef struct TYPENAME_s \ |
| { \ |
| TYPENAME##Hash* hash; \ |
| TYPENAME##Array* array; \ |
| } TYPENAME; /* NOLINT(TYPENAME) */ \ |
| \ |
| TYPENAME* TYPENAME##_create (deMemPool* pool); \ |
| deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value); \ |
| deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values); \ |
| \ |
| DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray) DE_UNUSED_FUNCTION; \ |
| DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key) DE_UNUSED_FUNCTION; \ |
| DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray) DE_UNUSED_FUNCTION; \ |
| \ |
| DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray) \ |
| { \ |
| return TYPENAME##Array_getNumElements(hashArray->array); \ |
| } \ |
| \ |
| DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key) \ |
| { \ |
| int* ndxPtr = TYPENAME##Hash_find(hashArray->hash, key); \ |
| if (!ndxPtr) \ |
| return DE_NULL; \ |
| else \ |
| { \ |
| int ndx = *ndxPtr; \ |
| DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements); \ |
| { \ |
| int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2); \ |
| int subNdx = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1); \ |
| return &((VALUETYPE*)hashArray->array->pageTable[pageNdx])[subNdx]; \ |
| } \ |
| } \ |
| } \ |
| \ |
| DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray) \ |
| { \ |
| TYPENAME##Hash_reset(hashArray->hash); \ |
| TYPENAME##Array_reset(hashArray->array); \ |
| } \ |
| \ |
| struct TYPENAME##Dummy_s { int dummy; } |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Implement a template pool hash-array class. |
| * \param TYPENAME Type name of the declared hash. |
| * \param KEYTYPE Type of the key. |
| * \param VALUETYPE Type of the value. |
| * \param KEYARRAYTYPE Type of the key array. |
| * \param VALUEARRAYTYPE Type of the value array. |
| * \param HASHFUNC Function used for hashing the key. |
| * \param CMPFUNC Function used for exact matching of the keys. |
| * |
| * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. |
| * Usually this macro should be used from a .c file, since the macro expands |
| * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters |
| * must match those of the declare macro. |
| *//*--------------------------------------------------------------------*/ |
| #define DE_IMPLEMENT_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE, KEYHASHFUNC, KEYCMPFUNC) \ |
| \ |
| DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC); \ |
| \ |
| TYPENAME* TYPENAME##_create (deMemPool* pool) \ |
| { \ |
| DE_PTR_TYPE(TYPENAME) hashArray = DE_POOL_NEW(pool, TYPENAME); \ |
| if (!hashArray) return DE_NULL; \ |
| if ((hashArray->hash = TYPENAME##Hash_create(pool)) == DE_NULL) \ |
| return DE_NULL; \ |
| if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL) \ |
| return DE_NULL; \ |
| return hashArray; \ |
| } \ |
| \ |
| deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value) \ |
| { \ |
| int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ |
| DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ |
| DE_ASSERT(!TYPENAME##Hash_find(hashArray->hash, key)); \ |
| if (!TYPENAME##Array_setSize(hashArray->array, numElements+1) || \ |
| !TYPENAME##Hash_insert(hashArray->hash, key, numElements)) \ |
| return DE_FALSE; \ |
| TYPENAME##Array_set(hashArray->array, numElements, value); \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values) \ |
| { \ |
| int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ |
| TYPENAME##Hash* hash = hashArray->hash; \ |
| TYPENAME##HashIter iter; \ |
| DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ |
| if ((keys && !KEYARRAYTYPE##_setSize(keys, numElements)) || \ |
| (values && !VALUEARRAYTYPE##_setSize(values, numElements))) \ |
| return DE_FALSE; \ |
| for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ |
| { \ |
| KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ |
| int ndx = TYPENAME##HashIter_getValue(&iter); \ |
| if (keys) KEYARRAYTYPE##_set(keys, ndx, key); \ |
| if (values) VALUEARRAYTYPE##_set(values, ndx, TYPENAME##Array_get(hashArray->array, ndx)); \ |
| } \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| struct TYPENAME##Dummy2_s { int dummy; } |
| |
| #endif /* _DEPOOLHASHARRAY_H */ |
