1 /* 2 * Copyright (c) 2015-2017, Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included 12 * in all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 15 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20 * OTHER DEALINGS IN THE SOFTWARE. 21 */ 22 //! 23 //! \file cm_hal_hashtable.h 24 //! \brief This modules defines hash table implementation used for kernel search in CMHal. 25 //! 26 #ifndef __CM_HAL_HASHTABLE_H__ 27 #define __CM_HAL_HASHTABLE_H__ 28 29 #include "mos_os.h" 30 #include "stdint.h" 31 32 #define CM_HAL_HASHTABLE_INITIAL 128 33 #define CM_HAL_HASHTABLE_INCREMENT 64 34 #define CM_HAL_HASHTABLE_MAX 2048 35 36 typedef struct _CM_HAL_HASH_TABLE_ENTRY 37 { 38 int32_t UniqID; 39 int32_t CacheID; 40 uint16_t wNext; 41 void *pData; 42 } CM_HAL_HASH_TABLE_ENTRY, *PCM_HAL_HASH_TABLE_ENTRY; 43 44 typedef struct _CM_HAL_COALESCED_HASH_TABLE 45 { 46 uint16_t wHead[256]; // Head of bucket list, 0 if empty 47 uint16_t wFree; // Head of the free hash table list, 0 if not present 48 uint16_t wSize; // Size of the hash table currently allocated 49 CM_HAL_HASH_TABLE_ENTRY *pHashEntries; // Dynamically expanding coalescing hash table 50 } CM_HAL_COALESCED_HASH_TABLE, *PCM_HAL_COALESCED_HASH_TABLE; 51 52 typedef struct _CM_HAL_COALESCED_HASH_TABLE *PCM_HAL_COALESCED_HASH_TABLE; 53 54 class CmHashTable 55 { 56 public: 57 MOS_STATUS Init(); 58 void Free(); 59 MOS_STATUS Register(int32_t UniqID, int32_t CacheID, void *pData); 60 void* Search(int32_t UniqID, int32_t CacheID, uint16_t &wSearchIndex); 61 void* Unregister(int32_t UniqID, int32_t CacheID); 62 63 private: 64 uint16_t SimpleHash(int32_t value); 65 MOS_STATUS Extend(); 66 CM_HAL_COALESCED_HASH_TABLE m_hashTable; 67 }; 68 69 #endif // __CM_HAL_HASHTABLE_H__ 70