1 krisbash 1.1 /*
2 **==============================================================================
3 **
4 ** Open Management Infrastructure (OMI)
5 **
6 ** Copyright (c) Microsoft Corporation
7 **
8 ** Licensed under the Apache License, Version 2.0 (the "License"); you may not
9 ** use this file except in compliance with the License. You may obtain a copy
10 ** of the License at
11 **
12 ** http://www.apache.org/licenses/LICENSE-2.0
13 **
14 ** THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 ** KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
16 ** WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
17 ** MERCHANTABLITY OR NON-INFRINGEMENT.
18 **
19 ** See the Apache 2 License for the specific language governing permissions
20 ** and limitations under the License.
21 **
22 krisbash 1.1 **==============================================================================
23 */
24
25 #ifndef _base_hashmap_h
26 #define _base_hashmap_h
27
28 #include "palcommon.h"
29
30 PAL_BEGIN_EXTERNC
31
32 typedef struct _HashBucket
33 {
34 struct _HashBucket* next;
35 } HashBucket;
36
37 typedef size_t (*HashMapHashProc)(const HashBucket* bucket);
38 typedef int (*HashMapEqualProc)(_In_ const HashBucket* bucket1, _In_ const HashBucket* bucket2);
39 typedef void (*HashMapReleaseProc)(_In_ HashBucket* bucket1);
40
41 typedef struct _HashMap
42 {
43 krisbash 1.1 /* Array of poitners to hash lists */
44 HashBucket** lists;
45 size_t numLists;
46 PAL_Boolean listsOwnedByHashMap;
47
48 /* User-defined hash function */
49 HashMapHashProc hash;
50
51 /* User-defined euqal function (returns non-zeroif equal) */
52 HashMapEqualProc equal;
53
54 /* User-defined function to release a hash bucket */
55 HashMapReleaseProc release;
56 }
57 HashMap;
58
59 typedef struct _HashMapIterator
60 {
61 size_t index;
62 HashBucket *current;
63 }
64 krisbash 1.1 HashMapIterator;
65
66 /* returns:
67 - 0 : success
68 - <0 : out of memory
69 */
70 int HashMap_Init(
71 _Out_ HashMap* self,
72 size_t numLists,
73 _In_ HashMapHashProc hash,
74 _In_ HashMapEqualProc equal,
75 _In_ HashMapReleaseProc release);
76
77 /* to be used with preallocated bucket list
78 (avoiding an extra allocation/deallocation can help boost performance in some scenarios) */
79 void HashMap_Construct(
80 _Out_ HashMap* self,
81 size_t numLists,
82 _Out_writes_(numLists) void** buckets,
83 _In_ HashMapHashProc hash,
84 _In_ HashMapEqualProc equal,
85 krisbash 1.1 _In_ HashMapReleaseProc release);
86
87 void HashMap_Destroy(
88 _In_ _Post_invalid_ HashMap* self);
89
90 /* returns:
91 - non-null : found
92 - null : key not present
93 */
94 _Ret_maybenull_ HashBucket* HashMap_Find(
95 _In_ HashMap* self,
96 _In_ const HashBucket* keyBucket);
97
98 /* returns:
99 - 0 : inserted the new item
100 - 1 : the item is already present (and HashMap was not modified)
101
102 (there are no failure paths / no other return value is possible)
103 */
104 int HashMap_Insert(
105 _In_ HashMap* self,
106 krisbash 1.1 _Pre_notnull_ HashBucket* bucket);
107
108 /* returns:
109 - 0 : success
110 - -1 : key not found - hashmap remains unchanged.
111 */
112 int HashMap_Remove(
113 _In_ HashMap* self,
114 _In_ const HashBucket* keyBucket);
115
116 void HashMap_BeginIteration(
117 _In_ HashMap* self,
118 _Out_ HashMapIterator* iterator);
119
120 /* iterates through hash table entries.
121 - iterator must be zero initialized
122 */
123 _Ret_maybenull_
124 const HashBucket* HashMap_Iterate(
125 _In_ HashMap* self,
126 _Inout_ HashMapIterator* iterator);
127 krisbash 1.1
128 /*
129 Returns one element from the hash table. May be invoked
130 multiple times (e.g. if you remove the element), returning
131 null when empty.
132
133 *iter should be zero initialized before first call
134 */
135 _Ret_maybenull_
136 const HashBucket* HashMap_Top(
137 _In_ HashMap* self,
138 _Inout_ size_t *iter);
139
140 PAL_INLINE size_t HashMap_HashProc_AnsiString(_In_ _Null_terminated_ const char *source)
141 {
142 /* fnv1-a hash, lowercase */
143 size_t h = 2166136261u;
144
145 for( ; *source; source++)
146 {
147 PAL_Char c = *source;
148 krisbash 1.1 h ^= c;
149 h *= 16777619;
150 }
151 return h;
152 }
153
154 PAL_INLINE size_t HashMap_HashProc_PalStringCaseInsensitive(_In_ _Null_terminated_ const PAL_Char *source)
155 {
156 /* fnv1-a hash, lowercase */
157 size_t h = 2166136261u;
158
159 for( ; *source; source++)
160 {
161 PAL_Char c = *source;
162 h ^= PAL_tolower(c);
163 h *= 16777619;
164 }
165 return h;
166 }
167
168 PAL_END_EXTERNC
169 krisbash 1.1
170 #endif /* _base_hashmap_h */
|