Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl

comparison PrivateHash.c @ 0:ee3ad252427e

find changesets by author, revision, files, or words in the commit message
Initial add
author Me
date Sat, 22 May 2010 19:49:28 -0700
parents
children 5900d90f5d71
comparison
equal deleted inserted replaced
-1:000000000000 0:f0e4ce38c5d6
1 /*
2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2
4 *
5 * NOTE: this version of SRSW correct as of April 25, 2010
6 *
7 * Author: seanhalle@yahoo.com
8 */
9
10
11 #include <stdio.h>
12 #include <string.h>
13 #include <errno.h>
14 #include <stdlib.h>
15
16 #include "PrivateHash.h"
17
18
19 HashTable *
20 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
21 { HashTable * retTable;
22 retTable = malloc( sizeof( HashTable ) );
23
24 retTable->freeEntryContentFn = freeFn;
25
26 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
27 retTable->tableSz = numHashSlots;
28
29 nullOutTablesArray( retTable );
30
31 return retTable;
32 }
33
34 void
35 doubleTableSize( HashTable *table )
36 { int i, oldTableSz, newTableSz;
37 HashEntry *entry, **oldEntries, **newEntries;
38
39 oldTableSz = table->tableSz;
40 oldEntries = table->entries;
41
42 newTableSz = 2 * oldTableSz + 1;
43 newEntries = malloc( newTableSz * sizeof(HashEntry *) );
44
45 table->tableSz = newTableSz;
46 table->entries = newEntries;
47 table->numEntries = 0; //about to add them all back!
48
49 // move all the entries from old to new
50 for( i=0; i < oldTableSz; i++ )
51 { if( oldEntries[i] != NULL )
52 { entry = oldEntries[i];
53 while( entry != NULL )
54 {
55 addEntryToTable( entry, table ); //does not allocate anything
56 entry = entry->next;
57 }
58 }
59 }
60 }
61
62 void
63 nullOutTablesArray( HashTable *table )
64 { int i, tableSz;
65 tableSz = table->tableSz;
66 HashEntry ** entries = table->entries;
67 for( i = 0; i < tableSz; i++ )
68 entries[ i ] = NULL;
69 }
70
71 unsigned int
72 hashThisKey( char *s, int hashSz )
73 { unsigned int h = 0;
74
75 for( ; *s != 0; s++ )
76 h = *s + h*31;
77 return h % hashSz;
78 }
79
80 /*Need this to be separated out, for use in both getParam and putParam
81 */
82 HashEntry *
83 getEntryFromTable( char *key, HashTable * table )
84 { unsigned int
85 hashIndex = hashKey( key, table->tableSz );
86 HashEntry*
87 hashEntry = table->entries[ hashIndex ];
88 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
89 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;
90 }
91 return NULL;
92 }
93
94 void *
95 getValueFromTable( char *key, HashTable * table )
96 { HashEntry *entry;
97 entry = lookupKeyInHash( key, table );
98 if( entry == NULL ) return NULL;
99
100 return entry->content;
101 }
102
103 int
104 addToTable( char* key, void *content, HashTable *table )
105 { unsigned int hashIdx;
106 HashEntry* hashEntry;
107
108 hashEntry = getEntryFromTable( key, table );
109 if( hashEntry == NULL )
110 { hashIdx = hashThisKey( key, table->tableSz );
111 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
112 if( hashEntry == NULL ) return 0;
113 hashEntry->key = strdup_m( key ); //TODO: figure out soln for incr Sz
114 if( hashEntry->key == NULL ) return 0;
115 hashEntry->next = (table->entries)[hashIdx];
116 (table->entries)[hashIdx] = hashEntry;
117 table->numEntries += 1;
118 if( table->tableSz < table->numEntries ) doubleTableSize( table );
119 }
120 else
121 { (*(table->freeEntryContentFn))( hashEntry->content );
122 }
123 hashEntry->content = content;
124 return 1;
125 }
126
127 int
128 addEntryToTable( HashEntry *entry, HashTable *table )
129 { unsigned int hashIdx;
130 HashEntry* testEntry;
131
132 testEntry = getEntryFromTable( entry->key, table );
133 if( testEntry == NULL )
134 { hashIdx = hashThisKey( entry->key, table->tableSz );
135 entry->next = (table->entries)[hashIdx];
136 (table->entries)[hashIdx] = entry;
137 table->numEntries += 1;
138 if( table->tableSz < table->numEntries ) doubleTableSize( table );
139 }
140 else
141 { (*(table->freeEntryContentFn))( testEntry->content );
142 testEntry->content = entry->content;
143 entry->content = NULL;
144 freeHashEntryUsing( entry, table );
145 }
146 return 1;
147 }
148
149 bool8
150 deleteEntryFromTable( char *key, HashTable *table )
151 {
152 table->numEntries -= 1;
153
154 }
155
156
157 char*
158 strdup_m( char *o )
159 { int len = strlen(o)+1;
160 char *ns = (char*) malloc( len * sizeof(char) );
161 strcpy( ns, o );
162 return ns;
163 }
164
165 /* debugging function displays the hashtable in (key.value) pairs
166 */
167 /*void hashTableToString( HashTable * table )
168 { int i;
169 HashEntry *t;
170 for( i = 0; i < table->tableSz; i++ )
171 { t = entries[i];
172 if( t == NULL )
173 strcat_m( retStr, &"()" );
174 else
175 { strcat_m( retStr, &"(" );
176 for( ; t != NULL; t = t->next )
177 { strcat_m( retStr, &" " );
178 strcat_m( retStr, t->key );
179 strcat_m( retStr, &"." );
180 strcat_m( retStr, paramToString( t->param ) );
181 strcat_m( retStr, &" " );
182 }
183 strcat_m( retStr, &")" );
184 }
185 }
186 }
187 */
188
189 /*
190 void
191 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
192 {
193 table->freeEntryContentFn = fnPtr;
194 }
195 */
196
197 void
198 freeHashTable( HashTable *table )
199 { int i;
200 HashEntry *hashEntry, *temp, **entries;
201
202 entries = table->entries;
203 for( i=0; i < table->tableSz; i++ )
204 { if( entries[i] != NULL )
205 { hashEntry = entries[i];
206 while( hashEntry != NULL )
207 {
208 temp = hashEntry->next;
209 freeHashEntryUsing( hashEntry, table );
210 hashEntry = temp;
211 }
212 }
213 }
214 }
215
216 void
217 freeHashEntryUsing( HashEntry *entry, HashTable *table )
218 {
219 if( entry->content != NULL )
220 (*(table->freeEntryContentFn))( entry->content );
221 free( entry->key ); //was malloc'd above, so free it
222 free( entry );
223 }
224