VMS/C_Libraries/Hash_impl: ec5c00d4023e PrivateHash.c

view PrivateHash.c @ 6:ec5c00d4023e

Build process fix

author	Merten Sach <msach@mailbox.tu-berlin.de>
date	Wed, 22 Jun 2011 16:51:29 +0200
parents	e072db5aa783
children	8b225987970d

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"

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;

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

78 h = *s + h*31;

79 return h % hashSz;

80 }

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

83 */

84 HashEntry *

85 getEntryFromTable( char *key, HashTable * table )

86 { unsigned int

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

88 HashEntry*

89 hashEntry = table->entries[ hashIndex ];

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

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

92 }

93 return NULL;

94 }

96 void *

97 getValueFromTable( char *key, HashTable * table )

98 { HashEntry *entry;

99 entry = getEntryFromTable( key, table );

100 if( entry == NULL ) return NULL;

101

102 return entry->content;

103 }

104

105

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

107 */

108 int

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

110 { unsigned int hashIdx;

111 HashEntry* hashEntry;

112

113 hashEntry = getEntryFromTable( key, table );

114 if( hashEntry == NULL )

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

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

117 if( hashEntry == NULL ) return 0;

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

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

120 strcpy( hashEntry->key, key );

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

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

123 table->numEntries += 1;

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

125 }

126 else

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

128 }

129 hashEntry->content = content;

130 return 1;

131 }

132

133 int

134 putEntryIntoTable( HashEntry *entry, HashTable *table )

135 { unsigned int hashIdx;

136 HashEntry* testEntry;

137

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

139 if( testEntry == NULL )

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

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

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

143 table->numEntries += 1;

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

145 }

146 else

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

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

149 // elem given to insert into table!

150 testEntry->content = entry->content;

151 entry->content = NULL;

152 freeHashEntryButNotContent( entry );

153 }

154 return 1;

155 }

156

157 /*Better version

158 */

159 int

160 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

161 { HashEntry *testEntry, *prevEntry = NULL;

162 unsigned int

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

164

165 testEntry = table->entries[ hashIndex ];

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

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

168 { if( prevEntry == NULL )

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

170 entry->next = testEntry->next;

171 }

172 else

173 { prevEntry->next = entry;

174 entry->next = testEntry->next;

175 }

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

177 return;

178 }

179 }

180 //wasn't found, so insert

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

182 table->entries[hashIndex] = entry;

183 }

184

185

186

187 bool8

188 deleteEntryFromTable( char *key, HashTable *table )

189 { HashEntry *hashEntry;

190 HashEntry **addrOfHashEntryPtr;

191 unsigned int hashIndex;

192

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

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

195 hashEntry = *addrOfHashEntryPtr;

196 while( hashEntry != NULL )

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

198 {

199 *addrOfHashEntryPtr = hashEntry->next;

200 //TODO: Free the contents of entry?

201 freeHashEntryButNotContent( hashEntry );

202 table->numEntries -= 1;

203 return TRUE;

204 }

205 addrOfHashEntryPtr = &( hashEntry->next );

206 hashEntry = *addrOfHashEntryPtr;

207 }

208 return FALSE;

209 }

210

211

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

213 */

214 /*void hashTableToString( HashTable * table )

215 { int i;

216 HashEntry *t;

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

218 { t = entries[i];

219 if( t == NULL )

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

221 else

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

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

224 { strcat_m( retStr, &" " );

225 strcat_m( retStr, t->key );

226 strcat_m( retStr, &"." );

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

228 strcat_m( retStr, &" " );

229 }

230 strcat_m( retStr, &")" );

231 }

232 }

233 }

234 */

235

236 /*

237 void

238 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )

239 {

240 table->freeEntryContentFn = fnPtr;

241 }

242 */

243

244 void

245 freeHashTable( HashTable *table )

246 { int i;

247 HashEntry *hashEntry, *temp, **entries;

248

249 entries = table->entries;

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

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

252 { hashEntry = entries[i];

253 while( hashEntry != NULL )

254 {

255 temp = hashEntry->next;

256 freeHashEntryUsing( hashEntry, table );

257 hashEntry = temp;

258 }

259 }

260 }

261 }

262

263 void

264 freeHashEntryUsing( HashEntry *entry, HashTable *table )

265 {

266 if( entry->content != NULL )

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

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

269 VMS__free( entry );

270 }

271

272 void

273 freeHashEntryButNotContent( HashEntry *entry )

274 {

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

276 VMS__free( entry );

277 }

278

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

view PrivateHash.c @ 6:ec5c00d4023e