framework/delibs/depool/dePoolHashArray.h

   1 #ifndef _DEPOOLHASHARRAY_H
   2 #define _DEPOOLHASHARRAY_H
   3 /*-------------------------------------------------------------------------
   4  * drawElements Memory Pool Library
   5  * --------------------------------
   6  *
   7  * Copyright 2014 The Android Open Source Project
   8  *
   9  * Licensed under the Apache License, Version 2.0 (the "License");
  10  * you may not use this file except in compliance with the License.
  11  * You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  *
  21  *//*!
  22  * \file
  23  * \brief Memory pool hash-array class.
  24  *//*--------------------------------------------------------------------*/
  25
  26 #include "deDefs.h"
  27 #include "dePoolHash.h"
  28 #include "dePoolArray.h"
  29
  30 DE_BEGIN_EXTERN_C
  31
  32 void    dePoolHashArray_selfTest                (void);
  33
  34 DE_END_EXTERN_C
  35
  36 /*--------------------------------------------------------------------*//*!
  37  * \brief Declare a template pool hash-array (array with hash) class interface.
  38  * \param TYPENAME                      Type name of the declared hash-array.
  39  * \param KEYTYPE                       Type of the key.
  40  * \param VALUETYPE                     Type of the value.
  41  * \param KEYARRAYTYPE          Type of the key array.
  42  * \param VALUEARRAYTYPE        Type of the value array.
  43  *
  44  * \todo [petri] Description.
  45  *
  46  * The functions for operating the hash are:
  47  * \todo [petri] Figure out how to comment these in Doxygen-style.
  48  *
  49  * \todo [pyry] HashArray_find() will break if dePoolArray implementation changes.
  50  *
  51  * \code
  52  * HashArray*  HashArray_create            (deMemPool* pool);
  53  * int         HashArray_getNumElements    (const HashArray* hashArray);
  54  * Value*      HashArray_find              (Hash* hashArray, Key key);
  55  * deBool      HashArray_insert            (Hash* hashArray, Key key, Value value);
  56  * deBool      HashArray_copyToArray       (Hash* hashArray, KeyArray* keys, ValueArray* values);
  57  * \endcode
  58 *//*--------------------------------------------------------------------*/
  59 #define DE_DECLARE_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE)          \
  60                                                                                                                                                                                                         \
  61 DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE);                                                                                                      \
  62 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int);                                                                                                     \
  63                                                                                                                                                                                                         \
  64 typedef struct TYPENAME_s                                                                                                                                                       \
  65 {                                                                                                                                                                                                       \
  66         TYPENAME##Hash*         hash;                                                                                                                                           \
  67         TYPENAME##Array*        array;                                                                                                                                          \
  68 } TYPENAME; /* NOLINT(TYPENAME) */                                                                                                                                      \
  69                                                                                                                                                                                                         \
  70 TYPENAME*               TYPENAME##_create               (deMemPool* pool);                                                                                      \
  71 deBool                  TYPENAME##_insert               (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value);        \
  72 deBool                  TYPENAME##_copyToArray  (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values);        \
  73                                                                                                                                                                                                         \
  74 DE_INLINE int                   TYPENAME##_getNumElements       (const TYPENAME* hashArray)                                     DE_UNUSED_FUNCTION;     \
  75 DE_INLINE VALUETYPE*    TYPENAME##_find                         (const TYPENAME* hashArray, KEYTYPE key)        DE_UNUSED_FUNCTION;     \
  76 DE_INLINE void                  TYPENAME##_reset                        (DE_PTR_TYPE(TYPENAME) hashArray)                       DE_UNUSED_FUNCTION;     \
  77                                                                                                                                                                                                         \
  78 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray)                                                                     \
  79 {                                                                                                                                                                                                       \
  80         return TYPENAME##Array_getNumElements(hashArray->array);                                                                                \
  81 }                                                                                                                                                                                                       \
  82                                                                                                                                                                                                         \
  83 DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key)                                           \
  84 {                                                                                                                                                                                                       \
  85         int* ndxPtr = TYPENAME##Hash_find(hashArray->hash, key);                                                                                \
  86         if (!ndxPtr)                                                                                                                                                                    \
  87                 return DE_NULL;                                                                                                                                                         \
  88         else                                                                                                                                                                                    \
  89         {                                                                                                                                                                                               \
  90                 int ndx = *ndxPtr;                                                                                                                                                      \
  91                 DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements);                                                                     \
  92                 {                                                                                                                                                                                       \
  93                         int pageNdx     = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);                                                                     \
  94                         int subNdx      = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);                                           \
  95                         return &((VALUETYPE*)hashArray->array->pageTable[pageNdx])[subNdx];                                             \
  96                 }                                                                                                                                                                                       \
  97         }                                                                                                                                                                                               \
  98 }                                                                                                                                                                                                       \
  99                                                                                                                                                                                                         \
 100 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray)                                                                       \
 101 {                                                                                                                                                                                                       \
 102         TYPENAME##Hash_reset(hashArray->hash);                                                                                                                  \
 103         TYPENAME##Array_reset(hashArray->array);                                                                                                                \
 104 }                                                                                                                                                                                                       \
 105                                                                                                                                                                                                         \
 106 struct TYPENAME##Dummy_s { int dummy; }
 107
 108 /*--------------------------------------------------------------------*//*!
 109  * \brief Implement a template pool hash-array class.
 110  * \param TYPENAME                      Type name of the declared hash.
 111  * \param KEYTYPE                       Type of the key.
 112  * \param VALUETYPE                     Type of the value.
 113  * \param KEYARRAYTYPE          Type of the key array.
 114  * \param VALUEARRAYTYPE        Type of the value array.
 115  * \param HASHFUNC                      Function used for hashing the key.
 116  * \param CMPFUNC                       Function used for exact matching of the keys.
 117  *
 118  * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
 119  * Usually this macro should be used from a .c file, since the macro expands
 120  * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters
 121  * must match those of the declare macro.
 122 *//*--------------------------------------------------------------------*/
 123 #define DE_IMPLEMENT_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE, KEYHASHFUNC, KEYCMPFUNC)                       \
 124                                                                                                                                                                                                         \
 125 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC);                                          \
 126                                                                                                                                                                                                         \
 127 TYPENAME* TYPENAME##_create (deMemPool* pool)                                                                                                           \
 128 {                                                                                                                                                                                                       \
 129         DE_PTR_TYPE(TYPENAME) hashArray = DE_POOL_NEW(pool, TYPENAME);                                                                  \
 130         if (!hashArray) return DE_NULL;                                                                                                                                 \
 131         if ((hashArray->hash = TYPENAME##Hash_create(pool)) == DE_NULL)                                                                 \
 132                 return DE_NULL;                                                                                                                                                         \
 133         if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL)                                                               \
 134                 return DE_NULL;                                                                                                                                                         \
 135         return hashArray;                                                                                                                                                               \
 136 }                                                                                                                                                                                                       \
 137                                                                                                                                                                                                         \
 138 deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value)                        \
 139 {                                                                                                                                                                                                       \
 140         int numElements = TYPENAME##Array_getNumElements(hashArray->array);                                                             \
 141         DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements);                                               \
 142         DE_ASSERT(!TYPENAME##Hash_find(hashArray->hash, key));                                                                                  \
 143         if (!TYPENAME##Array_setSize(hashArray->array, numElements+1) ||                                                                \
 144                 !TYPENAME##Hash_insert(hashArray->hash, key, numElements))                                                                      \
 145                 return DE_FALSE;                                                                                                                                                        \
 146         TYPENAME##Array_set(hashArray->array, numElements, value);                                                                              \
 147         return DE_TRUE;                                                                                                                                                                 \
 148 }                                                                                                                                                                                                       \
 149                                                                                                                                                                                                         \
 150 deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values)           \
 151 {                                                                                                                                                                                                       \
 152         int                                     numElements     = TYPENAME##Array_getNumElements(hashArray->array);                             \
 153         TYPENAME##Hash*         hash            = hashArray->hash;                                                                                              \
 154         TYPENAME##HashIter      iter;                                                                                                                                           \
 155         DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements);                                               \
 156         if ((keys && !KEYARRAYTYPE##_setSize(keys, numElements)) ||                                                                             \
 157                 (values && !VALUEARRAYTYPE##_setSize(values, numElements)))                                                                     \
 158                 return DE_FALSE;                                                                                                                                                        \
 159         for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter))   \
 160         {                                                                                                                                                                                               \
 161                 KEYTYPE key     = TYPENAME##HashIter_getKey(&iter);                                                                                             \
 162                 int             ndx     = TYPENAME##HashIter_getValue(&iter);                                                                                   \
 163                 if (keys) KEYARRAYTYPE##_set(keys, ndx, key);                                                                                           \
 164                 if (values) VALUEARRAYTYPE##_set(values, ndx, TYPENAME##Array_get(hashArray->array, ndx));      \
 165         }                                                                                                                                                                                               \
 166         return DE_TRUE;                                                                                                                                                                 \
 167 }                                                                                                                                                                                                       \
 168                                                                                                                                                                                                         \
 169 struct TYPENAME##Dummy2_s { int dummy; }
 170
 171 #endif /* _DEPOOLHASHARRAY_H */