Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl
view PrivateHash.c @ 15:093cad17d992
Removed VMS__malloc and free, added .brch__default (expls why removed)
| author | Me@portablequad |
|---|---|
| date | Sat, 11 Feb 2012 18:00:56 -0800 |
| parents | 7c4d2bf121a9 |
| children |
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 */
9 #include "PrivateHash.h"
12 HashTable *
13 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
14 { HashTable * retTable;
15 retTable = malloc( sizeof( HashTable ) );
17 retTable->freeEntryContentFn = freeFn;
19 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
20 retTable->numEntries = 0;
21 retTable->tableSz = numHashSlots;
23 nullOutTablesArray( retTable );
25 return retTable;
26 }
28 void
29 doubleTableSize( HashTable *table )
30 { int i, oldTableSz, newTableSz;
31 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
33 oldTableSz = table->tableSz;
34 oldEntries = table->entries;
36 newTableSz = 2 * oldTableSz + 1;
37 newEntries = malloc( newTableSz * sizeof(HashEntry *) );
39 table->tableSz = newTableSz;
40 table->entries = newEntries;
41 table->numEntries = 0; //about to add them all back!
43 // move all the entries from old to new
44 for( i=0; i < oldTableSz; i++ )
45 { if( oldEntries[i] != NULL )
46 { entry = oldEntries[i];
47 while( entry != NULL )
48 { nextEntry = entry->next;
49 entry->next = NULL;
50 putEntryIntoTable( entry, table ); //does not allocate anything
51 entry = nextEntry;
52 }
53 }
54 }
55 }
57 void
58 nullOutTablesArray( HashTable *table )
59 { int i, tableSz;
60 tableSz = table->tableSz;
61 HashEntry ** entries = table->entries;
62 for( i = 0; i < tableSz; i++ )
63 entries[ i ] = NULL;
64 }
66 unsigned int
67 hashThisKey( char* s, int hashSz )
68 { unsigned int h = 0;
69 unsigned int i;
70 hashkey_t* key = (hashkey_t*)s;
72 for(i=0 ; i<sizeof(hashkey_t); i++ )
73 h = key->hashable[i] + h*31;
74 return h % hashSz;
75 }
77 /*Need this to be separated out, for use in both getParam and putParam
78 */
79 HashEntry *
80 getEntryFromTable( char *key, HashTable * table )
81 { unsigned int
82 hashIndex = hashThisKey( key, table->tableSz );
83 HashEntry*
84 hashEntry = table->entries[ hashIndex ];
85 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
86 {
87 if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
88 return hashEntry;
89 }
90 return NULL;
91 }
93 void *
94 getValueFromTable( char *key, HashTable * table )
95 { HashEntry *entry;
96 entry = getEntryFromTable( key, table );
97 if( entry == NULL ) return NULL;
99 return entry->content;
100 }
103 /*If key already has a value, clobber the old one and replace it
104 */
105 int
106 addValueIntoTable( char* key, void *content, HashTable *table )
107 { unsigned int hashIdx;
108 HashEntry* hashEntry;
110 hashEntry = getEntryFromTable( key, table );
111 if( hashEntry == NULL )
112 { hashIdx = hashThisKey( key, table->tableSz );
113 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
114 if( hashEntry == NULL ) return 0;
115 hashEntry->key = malloc( sizeof(hashkey_t) );
116 if( hashEntry->key == NULL ) return 0;
117 memcpy( hashEntry->key, key, sizeof(hashkey_t) );
118 hashEntry->next = (table->entries)[hashIdx];
119 (table->entries)[hashIdx] = hashEntry;
120 table->numEntries += 1;
121 if( table->tableSz < table->numEntries ) doubleTableSize( table );
122 }
123 else
124 { (*(table->freeEntryContentFn))( hashEntry->content );
125 }
126 hashEntry->content = content;
127 return 1;
128 }
130 int
131 putEntryIntoTable( HashEntry *entry, HashTable *table )
132 { unsigned int hashIdx;
133 HashEntry* testEntry;
135 testEntry = getEntryFromTable( entry->key, table );
136 if( testEntry == NULL )
137 { hashIdx = hashThisKey( entry->key, table->tableSz );
138 entry->next = (table->entries)[hashIdx];
139 (table->entries)[hashIdx] = entry;
140 table->numEntries += 1;
141 if( table->tableSz < table->numEntries ) doubleTableSize( table );
142 }
143 else
144 { (*(table->freeEntryContentFn))( testEntry->content );
145 //being lazy -- will create bug in code that relies on having ptr to
146 // elem given to insert into table!
147 testEntry->content = entry->content;
148 entry->content = NULL;
149 freeHashEntryButNotContent( entry );
150 }
151 return 1;
152 }
154 /*Better version
155 */
156 void
157 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
158 { HashEntry *testEntry, *prevEntry = NULL;
159 unsigned int
160 hashIndex = hashThisKey( entry->key, table->tableSz );
162 testEntry = table->entries[ hashIndex ];
163 for( ; testEntry != NULL; testEntry = testEntry->next )
164 { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
165 { if( prevEntry == NULL )
166 { table->entries[hashIndex] = entry;
167 entry->next = testEntry->next;
168 }
169 else
170 { prevEntry->next = entry;
171 entry->next = testEntry->next;
172 }
173 freeHashEntryUsing( testEntry, table ); //frees content too!
174 return;
175 }
176 }
177 //wasn't found, so insert
178 entry->next = table->entries[hashIndex];
179 table->entries[hashIndex] = entry;
180 }
184 bool8
185 deleteEntryFromTable( char *key, HashTable *table )
186 { HashEntry *hashEntry;
187 HashEntry **addrOfHashEntryPtr;
188 unsigned int hashIndex;
190 hashIndex = hashThisKey( key, table->tableSz );
191 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
192 hashEntry = *addrOfHashEntryPtr;
193 while( hashEntry != NULL )
194 { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
195 {
196 *addrOfHashEntryPtr = hashEntry->next;
197 //TODO: Free the contents of entry?
198 freeHashEntryButNotContent( hashEntry );
199 table->numEntries -= 1;
200 return TRUE;
201 }
202 addrOfHashEntryPtr = &( hashEntry->next );
203 hashEntry = *addrOfHashEntryPtr;
204 }
205 return FALSE;
206 }
208 void
209 freeHashTable( HashTable *table )
210 { int i;
211 HashEntry *hashEntry, *temp, **entries;
213 entries = table->entries;
214 for( i=0; i < table->tableSz; i++ )
215 { if( entries[i] != NULL )
216 { hashEntry = entries[i];
217 while( hashEntry != NULL )
218 {
219 temp = hashEntry->next;
220 freeHashEntryUsing( hashEntry, table );
221 hashEntry = temp;
222 }
223 }
224 }
225 }
227 void
228 freeHashEntryUsing( HashEntry *entry, HashTable *table )
229 {
230 if( entry->content != NULL )
231 (*(table->freeEntryContentFn))( entry->content );
232 free( entry->key ); //was malloc'd above, so free it
233 free( entry );
234 }
236 void
237 freeHashEntryButNotContent( HashEntry *entry )
238 {
239 free( entry->key ); //was malloc'd above, so free it
240 free( entry );
241 }