VMS/C_Libraries/Hash_impl: e072db5aa783 PrivateHash.c

view PrivateHash.c @ 5:e072db5aa783

Fixed bug -- strdup snuck a malloc in -- and added better insert Entry

author	Me
date	Tue, 02 Nov 2010 16:45:50 -0700
parents	1ee100564408
children	ec5c00d4023e bac20745c52e

line source

1 /*

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"

18 HashTable *

19 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )

20 { HashTable * retTable;

21 retTable = VMS__malloc( sizeof( HashTable ) );

23 retTable->freeEntryContentFn = freeFn;

25 retTable->entries = VMS__malloc( numHashSlots * sizeof(HashEntry *) );

26 retTable->numEntries = 0;

27 retTable->tableSz = numHashSlots;

29 nullOutTablesArray( retTable );

31 return retTable;

32 }

34 void

35 doubleTableSize( HashTable *table )

36 { int i, oldTableSz, newTableSz;

37 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;

39 oldTableSz = table->tableSz;

40 oldEntries = table->entries;

42 newTableSz = 2 * oldTableSz + 1;

43 newEntries = VMS__malloc( newTableSz * sizeof(HashEntry *) );

45 table->tableSz = newTableSz;

46 table->entries = newEntries;

47 table->numEntries = 0; //about to add them all back!

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 { nextEntry = entry->next;

55 entry->next = NULL;

56 putEntryIntoTable( entry, table ); //does not allocate anything

57 entry = nextEntry;

58 }

59 }

60 }

61 }

63 void

64 nullOutTablesArray( HashTable *table )

65 { int i, tableSz;

66 tableSz = table->tableSz;

67 HashEntry ** entries = table->entries;

68 for( i = 0; i < tableSz; i++ )

69 entries[ i ] = NULL;

70 }

72 unsigned int

73 hashThisKey( char *s, int hashSz )

74 { unsigned int h = 0;

76 for( ; *s != 0; s++ )

77 h = *s + h*31;

78 return h % hashSz;

79 }

81 /*Need this to be separated out, for use in both getParam and putParam

82 */

83 HashEntry *

84 getEntryFromTable( char *key, HashTable * table )

85 { unsigned int

86 hashIndex = hashThisKey( key, table->tableSz );

87 HashEntry*

88 hashEntry = table->entries[ hashIndex ];

89 for( ; hashEntry != NULL; hashEntry = hashEntry->next )

90 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;

91 }

92 return NULL;

93 }

95 void *

96 getValueFromTable( char *key, HashTable * table )

97 { HashEntry *entry;

98 entry = getEntryFromTable( key, table );

99 if( entry == NULL ) return NULL;

100

101 return entry->content;

102 }

103

104

105 /*If key already has a value, clobber the old one and replace it

106 */

107 int

108 addValueIntoTable( char* key, void *content, HashTable *table )

109 { unsigned int hashIdx;

110 HashEntry* hashEntry;

111

112 hashEntry = getEntryFromTable( key, table );

113 if( hashEntry == NULL )

114 { hashIdx = hashThisKey( key, table->tableSz );

115 hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );

116 if( hashEntry == NULL ) return 0;

117 hashEntry->key = VMS__malloc( strlen(key) );

118 if( hashEntry->key == NULL ) return 0;

119 strcpy( hashEntry->key, key );

120 hashEntry->next = (table->entries)[hashIdx];

121 (table->entries)[hashIdx] = hashEntry;

122 table->numEntries += 1;

123 if( table->tableSz < table->numEntries ) doubleTableSize( table );

124 }

125 else

126 { (*(table->freeEntryContentFn))( hashEntry->content );

127 }

128 hashEntry->content = content;

129 return 1;

130 }

131

132 int

133 putEntryIntoTable( HashEntry *entry, HashTable *table )

134 { unsigned int hashIdx;

135 HashEntry* testEntry;

136

137 testEntry = getEntryFromTable( entry->key, table );

138 if( testEntry == NULL )

139 { hashIdx = hashThisKey( entry->key, table->tableSz );

140 entry->next = (table->entries)[hashIdx];

141 (table->entries)[hashIdx] = entry;

142 table->numEntries += 1;

143 if( table->tableSz < table->numEntries ) doubleTableSize( table );

144 }

145 else

146 { (*(table->freeEntryContentFn))( testEntry->content );

147 //being lazy -- will create bug in code that relies on having ptr to

148 // elem given to insert into table!

149 testEntry->content = entry->content;

150 entry->content = NULL;

151 freeHashEntryButNotContent( entry );

152 }

153 return 1;

154 }

155

156 /*Better version

157 */

158 int

159 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

160 { HashEntry *testEntry, *prevEntry = NULL;

161 unsigned int

162 hashIndex = hashThisKey( entry->key, table->tableSz );

163

164 testEntry = table->entries[ hashIndex ];

165 for( ; testEntry != NULL; testEntry = testEntry->next )

166 { if( strcmp( testEntry->key, entry->key ) == 0 )

167 { if( prevEntry == NULL )

168 { table->entries[hashIndex] = entry;

169 entry->next = testEntry->next;

170 }

171 else

172 { prevEntry->next = entry;

173 entry->next = testEntry->next;

174 }

175 freeHashEntryUsing( testEntry, table ); //frees content too!

176 return;

177 }

178 }

179 //wasn't found, so insert

180 entry->next = table->entries[hashIndex];

181 table->entries[hashIndex] = entry;

182 }

183

184

185

186 bool8

187 deleteEntryFromTable( char *key, HashTable *table )

188 { HashEntry *hashEntry;

189 HashEntry **addrOfHashEntryPtr;

190 unsigned int hashIndex;

191

192 hashIndex = hashThisKey( key, table->tableSz );

193 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );

194 hashEntry = *addrOfHashEntryPtr;

195 while( hashEntry != NULL )

196 { if( strcmp( hashEntry->key, key ) == 0 )

197 {

198 *addrOfHashEntryPtr = hashEntry->next;

199 //TODO: Free the contents of entry?

200 freeHashEntryButNotContent( hashEntry );

201 table->numEntries -= 1;

202 return TRUE;

203 }

204 addrOfHashEntryPtr = &( hashEntry->next );

205 hashEntry = *addrOfHashEntryPtr;

206 }

207 return FALSE;

208 }

209

210

211 /* debugging function displays the hashtable in (key.value) pairs

212 */

213 /*void hashTableToString( HashTable * table )

214 { int i;

215 HashEntry *t;

216 for( i = 0; i < table->tableSz; i++ )

217 { t = entries[i];

218 if( t == NULL )

219 strcat_m( retStr, &"()" );

220 else

221 { strcat_m( retStr, &"(" );

222 for( ; t != NULL; t = t->next )

223 { strcat_m( retStr, &" " );

224 strcat_m( retStr, t->key );

225 strcat_m( retStr, &"." );

226 strcat_m( retStr, paramToString( t->param ) );

227 strcat_m( retStr, &" " );

228 }

229 strcat_m( retStr, &")" );

230 }

231 }

232 }

233 */

234

235 /*

236 void

237 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )

238 {

239 table->freeEntryContentFn = fnPtr;

240 }

241 */

242

243 void

244 freeHashTable( HashTable *table )

245 { int i;

246 HashEntry *hashEntry, *temp, **entries;

247

248 entries = table->entries;

249 for( i=0; i < table->tableSz; i++ )

250 { if( entries[i] != NULL )

251 { hashEntry = entries[i];

252 while( hashEntry != NULL )

253 {

254 temp = hashEntry->next;

255 freeHashEntryUsing( hashEntry, table );

256 hashEntry = temp;

257 }

258 }

259 }

260 }

261

262 void

263 freeHashEntryUsing( HashEntry *entry, HashTable *table )

264 {

265 if( entry->content != NULL )

266 (*(table->freeEntryContentFn))( entry->content );

267 VMS__free( entry->key ); //was VMS__malloc'd above, so free it

268 VMS__free( entry );

269 }

270

271 void

272 freeHashEntryButNotContent( HashEntry *entry )

273 {

274 VMS__free( entry->key ); //was VMS__malloc'd above, so free it

275 VMS__free( entry );

276 }

277

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

view PrivateHash.c @ 5:e072db5aa783