1 mike  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 mike  1.1 **==============================================================================
 23           */
 24           
 25           #include "hashtable.h"
 26           
 27           int HashTable_Init(
 28               HashTable* self,
 29               size_t numLists,
 30               size_t (*hash)(const HashBucket* bucket),
 31               int (*equal)(const HashBucket* bucket1, const HashBucket* bucket2),
 32               void (*release)(HashBucket* bucket))
 33           {
 34               /* Allocate array of hash chains */
 35           
 36               self->lists = calloc(1, sizeof(HashBucket*) * numLists);
 37           
 38               if (!self->lists)
 39                   return -1;
 40           
 41               /* Save the function arguments */
 42           
 43 mike  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 HashTable_Destroy(
 52               HashTable* self)
 53           {
 54               size_t i;
 55           
 56               for (i = 0; i < self->numLists; i++)
 57               {
 58                   HashBucket* p;
 59           
 60                   for (p = self->lists[i]; p; )
 61                   {
 62                       HashBucket* next = p->next;
 63                       self->release(p);
 64 mike  1.1             p = next;
 65                   }
 66               }
 67           
 68               free(self->lists);
 69           }
 70           
 71           HashBucket* HashTable_Find(
 72               HashTable* self,
 73               const HashBucket* keyBucket)
 74           {
 75               size_t index;
 76               HashBucket* p;
 77           
 78               /* Hash the key */
 79           
 80               index = self->hash(keyBucket) % self->numLists;
 81           
 82               /* Search for matching bucket */
 83           
 84               for (p = self->lists[index]; p; p = p->next)
 85 mike  1.1     {
 86                   if (self->equal(p, keyBucket))
 87                   {
 88                       return p;
 89                   }
 90               }
 91           
 92               /* Not found */
 93               return 0;
 94           }
 95           
 96           int HashTable_Insert(
 97               HashTable* self,
 98               HashBucket* bucket)
 99           {
100               size_t index;
101               HashBucket* p;
102           
103               /* Hash the key */
104           
105               index = self->hash(bucket) % self->numLists;
106 mike  1.1 
107               /* Search for matching bucket */
108           
109               for (p = self->lists[index]; p; p = p->next)
110               {
111                   if (self->equal(p, bucket))
112                   {
113                       /* Already exists */
114                       return 1;
115                   }
116               }
117           
118               /* Insert at front of hash list */
119           
120               bucket->next = self->lists[index];
121               self->lists[index] = bucket;
122           
123               return 0;
124           }
125           
126           int HashTable_Remove(
127 mike  1.1     HashTable* self,
128               const HashBucket* keyBucket)
129           {
130               size_t index;
131               HashBucket* p;
132           
133               /* Hash the key */
134           
135               index = self->hash(keyBucket) % self->numLists;
136           
137               /* Search for matching bucket */
138               {
139                   HashBucket* prev = 0;
140           
141                   for (p = self->lists[index]; p; p = p->next)
142                   {
143                       if (self->equal(p, keyBucket))
144                       {
145                           if (prev)
146                               prev->next = p->next;
147                           else
148 mike  1.1                     self->lists[index] = p->next;
149           
150                           self->release(p);
151                           return 0;
152                       }
153           
154                       prev = p;
155                   }
156               }
157           
158               /* Not found */
159               return -1;
160           }