1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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
RtRemoveKeyFromVaHashTable(
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
|
