VMS/C_Libraries/Hash_impl: ce35f7028eba PrivateHash.c

view PrivateHash.c @ 10:ce35f7028eba

Closing branch

author	Merten Sach <msach@mailbox.tu-berlin.de>
date	Wed, 28 Sep 2011 13:40:38 +0200
parents	e072db5aa783
children

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__strDup( key );

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 }

129

130 int

131 putEntryIntoTable( HashEntry *entry, HashTable *table )

132 { unsigned int hashIdx;

133 HashEntry* testEntry;

134

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 }

153

154 /*Better version

155 */

156 int

157 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

158 { HashEntry *testEntry, *prevEntry = NULL;

159 unsigned int

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

161

162 testEntry = table->entries[ hashIndex ];

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

164 { if( strcmp( testEntry->key, entry->key ) == 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 }

181

182

183

184 bool8

185 deleteEntryFromTable( char *key, HashTable *table )

186 { HashEntry *hashEntry;

187 HashEntry **addrOfHashEntryPtr;

188 unsigned int hashIndex;

189

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

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

192 hashEntry = *addrOfHashEntryPtr;

193 while( hashEntry != NULL )

194 { if( strcmp( hashEntry->key, key ) == 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 }

207

208

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

210 */

211 /*void hashTableToString( HashTable * table )

212 { int i;

213 HashEntry *t;

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

215 { t = entries[i];

216 if( t == NULL )

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

218 else

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

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

221 { strcat_m( retStr, &" " );

222 strcat_m( retStr, t->key );

223 strcat_m( retStr, &"." );

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

225 strcat_m( retStr, &" " );

226 }

227 strcat_m( retStr, &")" );

228 }

229 }

230 }

231 */

232

233 /*

234 void

235 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )

236 {

237 table->freeEntryContentFn = fnPtr;

238 }

239 */

240

241 void

242 freeHashTable( HashTable *table )

243 { int i;

244 HashEntry *hashEntry, *temp, **entries;

245

246 entries = table->entries;

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

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

249 { hashEntry = entries[i];

250 while( hashEntry != NULL )

251 {

252 temp = hashEntry->next;

253 freeHashEntryUsing( hashEntry, table );

254 hashEntry = temp;

255 }

256 }

257 }

258 }

259

260 void

261 freeHashEntryUsing( HashEntry *entry, HashTable *table )

262 {

263 if( entry->content != NULL )

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

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

266 VMS__free( entry );

267 }

268

269 void

270 freeHashEntryButNotContent( HashEntry *entry )

271 {

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

273 VMS__free( entry );

274 }

275

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

view PrivateHash.c @ 10:ce35f7028eba