VMS/C_Libraries/Hash_impl: bd376656f8ab PrivateHash.c

view PrivateHash.c @ 32:bd376656f8ab

assuming you were not having fun thinking up silly ways to write 0

author	Nina Engelhardt <nengel@mailbox.tu-berlin.de>
date	Wed, 24 Apr 2013 16:35:19 +0200
parents	18a72865dd78
children

line source

1 /*

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 = VMS_int__malloc( sizeof( HashTable ) );

17 retTable->freeEntryContentFn = freeFn;

19 retTable->entries = VMS_int__malloc( numHashSlots * sizeof(HashEntry *) );

20 retTable->numEntries = 0;

21 retTable->tableSz = numHashSlots;

23 nullOutTablesArray( retTable );

25 return retTable;

26 }

28 HashTable *

29 makeHashTable_WL( int numHashSlots, FreeEntryContentFnPtr freeFn )

30 { HashTable * retTable;

31 retTable = VMS_WL__malloc( sizeof( HashTable ) );

33 retTable->freeEntryContentFn = freeFn;

35 retTable->entries = VMS_int__malloc( numHashSlots * sizeof(HashEntry *) );

36 retTable->numEntries = 0;

37 retTable->tableSz = numHashSlots;

39 nullOutTablesArray( retTable );

41 return retTable;

42 }

44 void

45 doubleTableSize( HashTable *table )

46 { printf("***This code is broken; program will probably segfault soon***\n");

48 int i, oldTableSz, newTableSz;

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

51 oldTableSz = table->tableSz;

52 oldEntries = table->entries;

54 newTableSz = 2 * oldTableSz;

55 newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );

57 table->tableSz = newTableSz;

58 table->entries = newEntries;

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

61 // move all the entries from old to new

62 for( i=0; i < oldTableSz; i++ )

63 { if( oldEntries[i] != NULL )

64 { entry = oldEntries[i];

65 while( entry != NULL )

66 { nextEntry = entry->next; //save for later

67 entry->next = NULL;

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

69 entry = nextEntry;

70 }

71 }

72 }

73 }

75 void

76 nullOutTablesArray( HashTable *table )

77 { int i, tableSz;

78 tableSz = table->tableSz;

79 HashEntry ** entries = table->entries;

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

81 entries[ i ] = NULL;

82 }

84 unsigned int

85 hashThisKey( char* s, int hashSz )

86 { unsigned int h = 0;

87 unsigned int i;

88 hashkey_t* key = (hashkey_t*)s;

90 for(i=0 ; i<sizeof(hashkey_t); i++ )

91 h = key->hashable[i] + h*31;

92 return h % hashSz;

93 }

95 /*Copies the string that is the key*/

96 HashEntry *

97 makeHashEntry( char * key )

98 { HashEntry *hashEntry;

100 int32 len = strlen(key);

101

102 hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );

103 if( hashEntry == NULL ) return NULL;

104

105 hashEntry->key = VMS_int__malloc( len + 1 );

106 if( hashEntry->key == NULL ) return NULL;

107 memcpy( hashEntry->key, key, len + 1 );

108 hashEntry->next = NULL;

109

110 return hashEntry;

111 }

112

113

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

115 */

116 HashEntry *

117 getEntryFromTable( char *key, HashTable * table )

118 { uint32

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

120 HashEntry*

121 hashEntry = table->entries[ hashIndex ];

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

123 {

124 if( strcmp( hashEntry->key, key ) == 0 )

125 return hashEntry;

126 }

127 return NULL;

128 }

129

130 void *

131 getValueFromTable( char *key, HashTable * table )

132 { HashEntry *entry;

133 entry = getEntryFromTable( key, table );

134 if( entry == NULL ) return NULL;

135

136 return entry->content;

137 }

138

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

140 */

141 int

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

143 { unsigned int hashIdx;

144 HashEntry* hashEntry;

145

146 hashEntry = getEntryFromTable( key, table );

147 if( hashEntry == NULL )

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

149 hashEntry = makeHashEntry( key );

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

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

152 table->numEntries += 1;

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

154 }

155 else

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

157 }

158 hashEntry->content = content;

159 return 1;

160 }

161

162

163 int

164 putEntryIntoTable( HashEntry *entry, HashTable *table )

165 { unsigned int hashIdx;

166 HashEntry* testEntry;

167

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

169 if( testEntry == NULL )

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

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

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

173 table->numEntries += 1;

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

175 }

176 else

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

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

179 // to elem given to insert into table!

180 testEntry->content = entry->content;

181 entry->content = NULL;

182 freeHashEntryButNotContent( entry );

183 }

184 return 1;

185 }

186

187 /*Better version

188 */

189 void

190 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

191 { HashEntry *testEntry, *prevEntry = NULL;

192 unsigned int

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

194

195 testEntry = table->entries[ hashIndex ];

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

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

198 { if( prevEntry == NULL )

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

200 entry->next = testEntry->next;

201 }

202 else

203 { prevEntry->next = entry;

204 entry->next = testEntry->next;

205 }

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

207 return;

208 }

209 }

210 //wasn't found, so insert

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

212 table->entries[hashIndex] = entry;

213 }

214

215

216 bool8

217 deleteEntryFromTable( char *key, HashTable *table )

218 { HashEntry *hashEntry;

219 HashEntry **addrOfPrevPtr;

220 unsigned int hashIndex;

221

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

223 addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node

224 hashEntry = *addrOfPrevPtr; //already did work, might as well use it

225 while( hashEntry != NULL )

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

227 {

228 *addrOfPrevPtr = hashEntry->next; //remove node from list

229 //TODO: Free the contents of entry?

230 freeHashEntryButNotContent( hashEntry );

231 table->numEntries -= 1;

232 return TRUE;

233 }

234 addrOfPrevPtr = &( hashEntry->next );

235 hashEntry = *addrOfPrevPtr;

236 }

237 return FALSE;

238 }

239

240 void

241 freeHashTable( HashTable *table )

242 { int i;

243 HashEntry *hashEntry, *temp, **entries;

244

245 entries = table->entries;

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

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

248 { hashEntry = entries[i];

249 while( hashEntry != NULL )

250 {

251 temp = hashEntry->next;

252 freeHashEntryUsing( hashEntry, table );

253 hashEntry = temp;

254 }

255 }

256 }

257 VMS_WL__free( entries );

258 VMS_WL__free( table );

259 }

260

261 void

262 freeHashEntryUsing( HashEntry *entry, HashTable *table )

263 {

264 if( entry->content != NULL )

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

266 VMS_int__free( entry->key ); //was VMS_int__malloc'd above, so free it

267 VMS_int__free( entry );

268 }

269

270 void

271 freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )

272 {

273 if( entry->content != NULL )

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

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

276 VMS_WL__free( entry );

277 }

278

279 void

280 freeHashTable_WL( HashTable *table )

281 { int i;

282 HashEntry *hashEntry, *temp, **entries;

283

284 entries = table->entries;

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

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

287 { hashEntry = entries[i];

288 while( hashEntry != NULL )

289 {

290 temp = hashEntry->next;

291 freeHashEntryUsing_WL( hashEntry, table );

292 hashEntry = temp;

293 }

294 }

295 }

296 }

297

298

299 void

300 freeHashEntryButNotContent( HashEntry *entry )

301 {

302 VMS_int__free( entry->key ); //was VMS_int__malloc'd above, so free it

303 VMS_int__free( entry );

304 }

305

306 void

307 freeHashEntryButNotContent_WL( HashEntry *entry )

308 {

309 VMS_WL__free( entry->key ); //was VMS_int__malloc'd above, so free it

310 VMS_WL__free( entry );

311 }

312

313

314

315

316 //======================= 32 bit integer key version ======================

317

318 /*key is array of uint32, with first entry being the num ints in key.

319 * that means size of key is content of first entry times 4, plus the

320 * size of first entry itself, which is another 4*/

321 #define sizeOfKey(key) key[0]*4 + 4

322

323

324 HashTable *

325 makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )

326 { HashTable * retTable;

327 int32 numHashSlots;

328

329 retTable = VMS_int__malloc( sizeof( HashTable ) );

330

331 numHashSlots = 1 << powerOf2OfSz;

332 retTable->hashMask = 0xffffffff >> (32 - powerOf2OfSz);

333 retTable->prevHash = (int32)rand();

334

335 retTable->freeEntryContentFn = freeFn;

336

337 retTable->entries = VMS_int__malloc( numHashSlots * sizeof(HashEntry *));

338 retTable->numEntries = 0;

339 retTable->tableSz = numHashSlots;

340

341 nullOutTablesArray( retTable );

342

343 return retTable;

344 }

345

346 HashTable *

347 makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )

348 {

349 return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );

350 }

351

352 HashEntry *

353 makeHashEntry32( uint32 * key )

354 { HashEntry *hashEntry;

355

356 hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );

357 if( hashEntry == NULL ) return NULL;

358 hashEntry->key = VMS_int__malloc( sizeOfKey(key) );

359 if( hashEntry->key == NULL ) return NULL;

360 memcpy( hashEntry->key, key, sizeOfKey(key) );

361 hashEntry->next = NULL;

362

363 return hashEntry;

364 }

365

366

367

368 int32

369 putEntryIntoTable32( HashEntry *entry, HashTable *table )

370 { unsigned int hashIdx;

371 HashEntry* testEntry;

372

373 testEntry = getEntryFromTable32( (uint32 *)entry->key, table );

374 if( testEntry == NULL ) //no entry w/key, so add passed-in as list-head

375 { hashIdx = hashThisKey32( (uint32 *)entry->key, table );

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

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

378 table->numEntries += 1;

379 //keep num entries less than half the num indexes in table

380 if( table->numEntries > (table->tableSz >>1) ) doubleTableSize(table);

381 }

382 else //entry w/key already exists, so free content, then replace then

383 // free the passed-in entry, leaving the entry already in table

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

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

386 // to elem given to insert into table!

387 testEntry->content = entry->content;

388 entry->content = NULL;

389 freeHashEntryButNotContent( entry );

390 }

391 return 1;

392 }

393

394

395 void

396 doubleTableSize32( HashTable *table )

397 { int i, oldTableSz, newTableSz;

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

399

400 oldTableSz = table->tableSz;

401 oldEntries = table->entries;

402

403 newTableSz = 2 * oldTableSz;

404 newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );

405

406 table->tableSz = newTableSz;

407 table->entries = newEntries;

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

409

410 // move all the entries from old to new

411 for( i=0; i < oldTableSz; i++ )

412 { if( oldEntries[i] != NULL )

413 { entry = oldEntries[i];

414 while( entry != NULL )

415 { nextEntry = entry->next; //save for later

416 entry->next = NULL; //null before, so can chain in new

417 putEntryIntoTable32( entry, table ); //doesn't allocate anything

418 entry = nextEntry;

419 }

420 }

421 }

422 }

423

424 /*The key is a self-sized array of 32 bit unsigned ints, with the first

425 * entry being the number of ints in the key, which makes up the rest of

426 * the array.*/

427 int32

428 hashThisKey32( uint32 *key, HashTable *hashTable )

429 { int32 hashOfKey;

430

431 //the hash function takes addr of start of key array, plus num int32s,

432 hashOfKey = jenkHash32( &key[1], *key );

433 hashTable->prevHash = hashOfKey;

434

435 /*The hash is a full 32 bits, but only want hashes that fall within

436 * the size of the table. So, mask off the higher bits. */

437 return ( hashTable->hashMask & hashOfKey ); //reduce to size of table

438 }

439

440

441 /*The first entry of key says the size of the key, while key itself is the

442 * rest of the integers in the array

443 */

444 HashEntry *

445 getEntryFromTable32( uint32 *key, HashTable * table )

446 { unsigned int

447 hashIndex = hashThisKey32( key, table );

448 HashEntry*

449 hashEntry = table->entries[ hashIndex ];

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

451 {

452 if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )

453 return hashEntry;

454 }

455 return NULL;

456 }

457

458 void *

459 getValueFromTable32( uint32 *key, HashTable * table )

460 { HashEntry *entry;

461 entry = getEntryFromTable32( key, table );

462 if( entry == NULL ) return NULL;

463

464 return entry->content;

465 }

466

467 /*Returns NULL if failed to insert, else returns ptr to hash entry

468 * NOTE: does a copy of the key, so key can be alloc'd on stack */

469 HashEntry *

470 addValueIntoTable32( uint32* key, void *content, HashTable *table )

471 { unsigned int hashIdx;

472 HashEntry* hashEntry;

473

474 hashEntry = getEntryFromTable32( key, table );

475 if( hashEntry == NULL )

476 { hashIdx = hashThisKey32( key, table );

477 hashEntry = makeHashEntry32( key );

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

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

480 table->numEntries += 1;

481 //Check if need to make bigger -- keep half-full (hence ">> 1")

482 if( table->numEntries > table->tableSz >>1 ) doubleTableSize( table );

483 }

484 else

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

486 }

487 hashEntry->content = content;

488 return hashEntry;

489 }

490

491

492 bool32

493 deleteEntryFromTable32( uint32 *key, HashTable *table )

494 { HashEntry *hashEntry;

495 HashEntry **addrOfPrevPtr;

496 unsigned int hashIndex;

497

498 hashIndex = hashThisKey32( key, table );

499 hashEntry = table->entries[ hashIndex ];

500 //go down the chained list, checking all with this hash value

501 addrOfPrevPtr = &( table->entries[hashIndex] ); //for removing a node

502 hashEntry = *addrOfPrevPtr; //did ptr chasing, might as well use it

503 while( hashEntry != NULL )

504 { if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )

505 { *addrOfPrevPtr = hashEntry->next; //remove node from list

506 freeHashEntryButNotContent( hashEntry );

507 table->numEntries -= 1;

508 return TRUE;

509 }

510 addrOfPrevPtr = &(hashEntry->next); //chg content of *this* to remove

511 hashEntry = *addrOfPrevPtr; //cheaper than hashEntry->next

512 }

513 return FALSE;

514 }

515

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

view PrivateHash.c @ 32:bd376656f8ab