diff options
Diffstat (limited to 'network/wlan/WDI/HEADER/HashTable.h')
| -rw-r--r-- | network/wlan/WDI/HEADER/HashTable.h | 128 |
1 files changed, 128 insertions, 0 deletions
diff --git a/network/wlan/WDI/HEADER/HashTable.h b/network/wlan/WDI/HEADER/HashTable.h new file mode 100644 index 00000000..7806b10b --- /dev/null +++ b/network/wlan/WDI/HEADER/HashTable.h @@ -0,0 +1,128 @@ +//----------------------------------------------------------------------------- +// File: +// HashTable.h +// +// Description: +// Generic hash table for kernel mode module. +// +// Note: +// 1. Memory allocation is a issue on kernel space for calling context +// and computation time limitation. So we don't re-hash the table even +// it is full. In short, this implementation is not a perfect hash, +// however, if user has a good guess on hash table usage to prevent +// full and colission condition, this implementation is still a +// constant time on put, remove, and get operations. +// +// 2. This implementation is not thread-safe, that is, user have to +// protect related resource and the function exported here by their +// own means. +// +// 070606, by rcnjko. +//----------------------------------------------------------------------------- + +#ifndef __INC_HASH_TABLE_H +#define __INC_HASH_TABLE_H + +#define RT_HASH_KEY unsigned char* + +// +// Description: +// Return a index in [0,Capacity-1] from given key. +// +typedef unsigned int +(*RT_HT_HASH_FUNC)( + IN RT_HASH_KEY Key + ); + + +// +// Definition of a hash entry of an value object. +// +typedef struct _RT_HASH_ENTRY{ + RT_LIST_ENTRY BusyLink; // For list of all value objects in the hash table. + RT_LIST_ENTRY BucketLink; // For list of value objects in the same bucket. + RT_SINGLE_LIST_ENTRY FreeLink; // For list of free objects in the hash table. + RT_HASH_KEY Key; // Key associated. +}RT_HASH_ENTRY, *PRT_HASH_ENTRY; + +// +// This macro must be included in first line of data structure definition of a value object. +// +#define DECLARE_RT_HASH_ENTRY RT_HASH_ENTRY __HashEntry + +// +// Routines to translate from link list entry inside RT_HASH_ENTRY object +// to pointer to the RT_HASH_ENTRY object. +// +#define RT_HASH_ENTRY_FROM_BUSY_LINK(__pBusyLink) (PRT_HASH_ENTRY)(__pBusyLink) +#define RT_HASH_ENTRY_FROM_BUCKET_LINK(__pBucketLink) (PRT_HASH_ENTRY)( (pu1Byte)(__pBucketLink) - sizeof(RT_LIST_ENTRY) ) +#define RT_HASH_ENTRY_FROM_FREE_LINK(__pFreeLink) (PRT_HASH_ENTRY)( (pu1Byte)(__pFreeLink) - (sizeof(RT_LIST_ENTRY)*2) ) + +// +// Definition of the hash table. +// +typedef struct _RT_HASH_TABLE { + // + // Value object pool. + // + unsigned int NumValuesAlloc; // Number of value objects allcoated in pValuesPool. + unsigned int ValueSize; // # bytes of a value object. + void* pValuesBuf; // Pointer to the buffer allocated for value objects. + unsigned int KeySize; // # bytes of the key. + void* pKeysBuf; // Pointer to the buffer to store key of each value object. + RT_SINGLE_LIST_HEAD FreeValuesList; // List of available value object. + + // + // Hash table stuff. + // + RT_HT_HASH_FUNC pfHash; // Hash function. + RT_LIST_ENTRY BusyValuesList; // List of all value object put in Buckets[]. + unsigned int Capacity; // Number of Buckets[] allocated. + RT_LIST_ENTRY Buckets[1]; // Each entry accommodates value objects of the same hash result. +}*RT_HASH_TABLE_HANDLE; + + +// +// Hash Table Operations. +// +RT_HASH_TABLE_HANDLE +RtAllocateHashTable( + IN void* Adapter, + IN unsigned int Capacity, + IN unsigned int ValueSize, + IN unsigned int KeySize, + IN RT_HT_HASH_FUNC pfHash + ); + +void +RtFreeHashTable( + IN RT_HASH_TABLE_HANDLE hHashTable + ); + +void +RtResetHashTable( + IN RT_HASH_TABLE_HANDLE hHashTable + ); + +PRT_HASH_ENTRY +RtPutKeyToHashTable( + IN RT_HASH_TABLE_HANDLE hHashTable, + IN RT_HASH_KEY Key + ); + +void +RtRemvoeKeyFromVaHashTable( + IN RT_HASH_TABLE_HANDLE hHashTable, + IN RT_HASH_KEY Key + ); + +PRT_HASH_ENTRY +RtGetValueFromHashTable( + IN RT_HASH_TABLE_HANDLE hHashTable, + IN RT_HASH_KEY Key + ); + +#define RtGetAllValuesFromHashTable(__hHashTable) &((__hHashTable)->BusyValuesList) + +#endif + |