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 #include "hashmap.h"
26
27 int HashMap_Init(
28 _Out_ HashMap* self,
29 size_t numLists,
30 _In_ HashMapHashProc hash,
31 _In_ HashMapEqualProc equal,
32 _In_ HashMapReleaseProc release)
33 {
34 /* Allocate array of hash chains */
35
36 self->lists = SystemCalloc(numLists, sizeof(HashBucket*));
37 if (!self->lists)
38 return -1;
39 self->listsOwnedByHashMap = PAL_TRUE;
40
41 /* Save the function arguments */
42
43 krisbash 1.1 self->numLists = numLists;
44 self->hash = hash;
45 self->equal = equal;
46 self->release = release;
47
48 return 0;
49 }
50
51 void HashMap_Construct(
52 _Out_ HashMap* self,
53 size_t numLists,
54 _Out_writes_(numLists) void** buckets,
55 _In_ HashMapHashProc hash,
56 _In_ HashMapEqualProc equal,
57 _In_ HashMapReleaseProc release)
58 {
59 /* Remember pointer to the array of hash chains */
60
61 self->lists = (HashBucket**) buckets;
62 memset(self->lists, 0, sizeof(void*) * numLists);
63 self->listsOwnedByHashMap = PAL_FALSE;
64 krisbash 1.1
65 /* Save the function arguments */
66
67 self->numLists = numLists;
68 self->hash = hash;
69 self->equal = equal;
70 self->release = release;
71 }
72
73 void HashMap_Destroy(
74 _In_ _Post_invalid_ HashMap* self)
75 {
76 size_t i;
77
78 for (i = 0; i < self->numLists; i++)
79 {
80 HashBucket* p;
81
82 for (p = self->lists[i]; p; )
83 {
84 HashBucket* next = p->next;
85 krisbash 1.1 self->release(p);
86 p = next;
87 }
88 }
89
90 if (self->listsOwnedByHashMap)
91 {
92 SystemFree(self->lists);
93 }
94 }
95
96 _Ret_maybenull_ HashBucket* HashMap_Find(
97 _In_ HashMap* self,
98 _In_ const HashBucket* keyBucket)
99 {
100 size_t index;
101 HashBucket* p;
102
103 /* Hash the key */
104
105 index = self->hash(keyBucket) % self->numLists;
106 krisbash 1.1
107 /* Search for matching bucket */
108
109 for (p = self->lists[index]; p; p = p->next)
110 {
111 if (self->equal(p, keyBucket))
112 {
113 return p;
114 }
115 }
116
117 /* Not found */
118 return 0;
119 }
120
121 int HashMap_Insert(
122 _In_ HashMap* self,
123 _Pre_notnull_ HashBucket* bucket)
124 {
125 size_t index;
126 HashBucket* p;
127 krisbash 1.1
128 /* Hash the key */
129
130 index = self->hash(bucket) % self->numLists;
131
132 /* Search for matching bucket */
133
134 for (p = self->lists[index]; p; p = p->next)
135 {
136 if (self->equal(p, bucket))
137 {
138 /* Already exists */
139 return 1;
140 }
141 }
142
143 /* Insert at front of hash list */
144
145 bucket->next = self->lists[index];
146 self->lists[index] = bucket;
147
148 krisbash 1.1 return 0;
149 }
150
151 int HashMap_Remove(
152 _In_ HashMap* self,
153 _In_ const HashBucket* keyBucket)
154 {
155 size_t index;
156 HashBucket* p;
157
158 /* Hash the key */
159
160 index = self->hash(keyBucket) % self->numLists;
161
162 /* Search for matching bucket */
163 {
164 HashBucket* prev = 0;
165
166 for (p = self->lists[index]; p; p = p->next)
167 {
168 if (self->equal(p, keyBucket))
169 krisbash 1.1 {
170 if (prev)
171 prev->next = p->next;
172 else
173 self->lists[index] = p->next;
174
175 self->release(p);
176 return 0;
177 }
178
179 prev = p;
180 }
181 }
182
183 /* Not found */
184 return -1;
185 }
186
187 void HashMap_BeginIteration(
188 _In_ HashMap* self,
189 _Out_ HashMapIterator* iterator)
190 krisbash 1.1 {
191 if (self->numLists > 0)
192 {
193 iterator->index = 0;
194 iterator->current = self->lists[0];
195 }
196 else
197 {
198 iterator->index = 0;
199 iterator->current = NULL;
200 }
201 }
202
203 _Ret_maybenull_
204 const HashBucket* HashMap_Iterate(
205 _In_ HashMap* self,
206 _Inout_ HashMapIterator* iterator)
207 {
208 const HashBucket *result;
209
210 if (iterator->index >= self->numLists)
211 krisbash 1.1 return NULL;
212
213 while (!iterator->current)
214 {
215 size_t index = ++iterator->index;
216
217 if (index >= self->numLists)
218 return NULL;
219
220 iterator->current = self->lists[index];
221 }
222
223 result = iterator->current;
224 iterator->current = result->next;
225
226 return result;
227 }
228
229 _Ret_maybenull_
230 const HashBucket* HashMap_Top(
231 _In_ HashMap* self,
232 krisbash 1.1 _Inout_ size_t *iter)
233 {
234 for (; *iter < self->numLists; ++*iter)
235 {
236 HashBucket *bucket = self->lists[*iter];
237 if (bucket)
238 {
239 return bucket;
240 }
241 }
242 return NULL;
243 }
244
|
Return to
hashmap.c
CVS log
Up to [OMI] / omi / pal