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 */