Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl
view PrivateHash.c @ 12:40ec8f9583d8
include statements adapted to the new folder structure
| author | hausers |
|---|---|
| date | Thu, 09 Feb 2012 15:49:46 +0100 |
| parents | 8b225987970d |
| children | 5b89d57e5d10 093cad17d992 |
line source
1 /*
2 * Copyright 2009 OpenSourceStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2
4 *
5 *
6 * Author: seanhalle@yahoo.com
7 */
10 #include <stdio.h>
11 #include <string.h>
12 #include <errno.h>
13 #include <stdlib.h>
15 #include "PrivateHash.h"
16 #include "../vmalloc.h"
19 HashTable *
20 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
21 { HashTable * retTable;
22 retTable = VMS__malloc( sizeof( HashTable ) );
24 retTable->freeEntryContentFn = freeFn;
26 retTable->entries = VMS__malloc( numHashSlots * sizeof(HashEntry *) );
27 retTable->numEntries = 0;
28 retTable->tableSz = numHashSlots;
30 nullOutTablesArray( retTable );
32 return retTable;
33 }
35 void
36 doubleTableSize( HashTable *table )
37 { int i, oldTableSz, newTableSz;
38 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
40 oldTableSz = table->tableSz;
41 oldEntries = table->entries;
43 newTableSz = 2 * oldTableSz + 1;
44 newEntries = VMS__malloc( newTableSz * sizeof(HashEntry *) );
46 table->tableSz = newTableSz;
47 table->entries = newEntries;
48 table->numEntries = 0; //about to add them all back!
50 // move all the entries from old to new
51 for( i=0; i < oldTableSz; i++ )
52 { if( oldEntries[i] != NULL )
53 { entry = oldEntries[i];
54 while( entry != NULL )
55 { nextEntry = entry->next;
56 entry->next = NULL;
57 putEntryIntoTable( entry, table ); //does not allocate anything
58 entry = nextEntry;
59 }
60 }
61 }
62 }
64 void
65 nullOutTablesArray( HashTable *table )
66 { int i, tableSz;
67 tableSz = table->tableSz;
68 HashEntry ** entries = table->entries;
69 for( i = 0; i < tableSz; i++ )
70 entries[ i ] = NULL;
71 }
73 unsigned int
74 hashThisKey( char* s, int hashSz )
75 { unsigned int h = 0;
76 unsigned int i;
77 hashkey_t* key = (hashkey_t*)s;
79 for(i=0 ; i<sizeof(hashkey_t); i++ )
80 h = key->hashable[i] + h*31;
81 return h % hashSz;
82 }
84 /*Need this to be separated out, for use in both getParam and putParam
85 */
86 HashEntry *
87 getEntryFromTable( char *key, HashTable * table )
88 { unsigned int
89 hashIndex = hashThisKey( key, table->tableSz );
90 HashEntry*
91 hashEntry = table->entries[ hashIndex ];
92 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
93 {
94 if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
95 return hashEntry;
96 }
97 return NULL;
98 }
100 void *
101 getValueFromTable( char *key, HashTable * table )
102 { HashEntry *entry;
103 entry = getEntryFromTable( key, table );
104 if( entry == NULL ) return NULL;
106 return entry->content;
107 }
110 /*If key already has a value, clobber the old one and replace it
111 */
112 int
113 addValueIntoTable( char* key, void *content, HashTable *table )
114 { unsigned int hashIdx;
115 HashEntry* hashEntry;
117 hashEntry = getEntryFromTable( key, table );
118 if( hashEntry == NULL )
119 { hashIdx = hashThisKey( key, table->tableSz );
120 hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );
121 if( hashEntry == NULL ) return 0;
122 hashEntry->key = VMS__malloc( sizeof(hashkey_t) );
123 if( hashEntry->key == NULL ) return 0;
124 memcpy( hashEntry->key, key, sizeof(hashkey_t) );
125 hashEntry->next = (table->entries)[hashIdx];
126 (table->entries)[hashIdx] = hashEntry;
127 table->numEntries += 1;
128 if( table->tableSz < table->numEntries ) doubleTableSize( table );
129 }
130 else
131 { (*(table->freeEntryContentFn))( hashEntry->content );
132 }
133 hashEntry->content = content;
134 return 1;
135 }
137 int
138 putEntryIntoTable( HashEntry *entry, HashTable *table )
139 { unsigned int hashIdx;
140 HashEntry* testEntry;
142 testEntry = getEntryFromTable( entry->key, table );
143 if( testEntry == NULL )
144 { hashIdx = hashThisKey( entry->key, table->tableSz );
145 entry->next = (table->entries)[hashIdx];
146 (table->entries)[hashIdx] = entry;
147 table->numEntries += 1;
148 if( table->tableSz < table->numEntries ) doubleTableSize( table );
149 }
150 else
151 { (*(table->freeEntryContentFn))( testEntry->content );
152 //being lazy -- will create bug in code that relies on having ptr to
153 // elem given to insert into table!
154 testEntry->content = entry->content;
155 entry->content = NULL;
156 freeHashEntryButNotContent( entry );
157 }
158 return 1;
159 }
161 /*Better version
162 */
163 void
164 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
165 { HashEntry *testEntry, *prevEntry = NULL;
166 unsigned int
167 hashIndex = hashThisKey( entry->key, table->tableSz );
169 testEntry = table->entries[ hashIndex ];
170 for( ; testEntry != NULL; testEntry = testEntry->next )
171 { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
172 { if( prevEntry == NULL )
173 { table->entries[hashIndex] = entry;
174 entry->next = testEntry->next;
175 }
176 else
177 { prevEntry->next = entry;
178 entry->next = testEntry->next;
179 }
180 freeHashEntryUsing( testEntry, table ); //frees content too!
181 return;
182 }
183 }
184 //wasn't found, so insert
185 entry->next = table->entries[hashIndex];
186 table->entries[hashIndex] = entry;
187 }
191 bool8
192 deleteEntryFromTable( char *key, HashTable *table )
193 { HashEntry *hashEntry;
194 HashEntry **addrOfHashEntryPtr;
195 unsigned int hashIndex;
197 hashIndex = hashThisKey( key, table->tableSz );
198 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
199 hashEntry = *addrOfHashEntryPtr;
200 while( hashEntry != NULL )
201 { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
202 {
203 *addrOfHashEntryPtr = hashEntry->next;
204 //TODO: Free the contents of entry?
205 freeHashEntryButNotContent( hashEntry );
206 table->numEntries -= 1;
207 return TRUE;
208 }
209 addrOfHashEntryPtr = &( hashEntry->next );
210 hashEntry = *addrOfHashEntryPtr;
211 }
212 return FALSE;
213 }
215 void
216 freeHashTable( HashTable *table )
217 { int i;
218 HashEntry *hashEntry, *temp, **entries;
220 entries = table->entries;
221 for( i=0; i < table->tableSz; i++ )
222 { if( entries[i] != NULL )
223 { hashEntry = entries[i];
224 while( hashEntry != NULL )
225 {
226 temp = hashEntry->next;
227 freeHashEntryUsing( hashEntry, table );
228 hashEntry = temp;
229 }
230 }
231 }
232 }
234 void
235 freeHashEntryUsing( HashEntry *entry, HashTable *table )
236 {
237 if( entry->content != NULL )
238 (*(table->freeEntryContentFn))( entry->content );
239 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
240 VMS__free( entry );
241 }
243 void
244 freeHashEntryButNotContent( HashEntry *entry )
245 {
246 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
247 VMS__free( entry );
248 }