VMS/C_Libraries/Hash_impl: 1d42a512f482 PrivateHash.c

view PrivateHash.c @ 31:1d42a512f482

Renamed VMS to PR, in new branch

author	Sean Halle <seanhalle@yahoo.com>
date	Fri, 08 Mar 2013 05:44:24 -0800
parents	18ec64d06e35
children	049a8d8917c5

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

17 retTable->freeEntryContentFn = freeFn;

19 retTable->entries = PR_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 = PR_WL__malloc( sizeof( HashTable ) );

33 retTable->freeEntryContentFn = freeFn;

35 retTable->entries = PR_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 { int i, oldTableSz, newTableSz;

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

49 oldTableSz = table->tableSz;

50 oldEntries = table->entries;

52 newTableSz = 2 * oldTableSz;

53 newEntries = PR_int__malloc( newTableSz * sizeof(HashEntry *) );

55 table->tableSz = newTableSz;

56 table->entries = newEntries;

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

59 // move all the entries from old to new

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

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

62 { entry = oldEntries[i];

63 while( entry != NULL )

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

65 entry->next = NULL;

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

67 entry = nextEntry;

68 }

69 }

70 }

71 }

73 void

74 nullOutTablesArray( HashTable *table )

75 { int i, tableSz;

76 tableSz = table->tableSz;

77 HashEntry ** entries = table->entries;

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

79 entries[ i ] = NULL;

80 }

82 unsigned int

83 hashThisKey( char* s, int hashSz )

84 { unsigned int h = 0;

85 unsigned int i;

86 hashkey_t* key = (hashkey_t*)s;

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

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

90 return h % hashSz;

91 }

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

94 inline HashEntry *

95 makeHashEntry( char * key )

96 { HashEntry *hashEntry;

98 int32 len = strlen(key);

100 hashEntry = (HashEntry*) PR_int__malloc( sizeof( HashEntry ) );

101 if( hashEntry == NULL ) return NULL;

102

103 hashEntry->key = PR_int__malloc( len + 1 );

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

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

106 hashEntry->next = NULL;

107

108 return hashEntry;

109 }

110

111

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

113 */

114 HashEntry *

115 getEntryFromTable( char *key, HashTable * table )

116 { uint32

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

118 HashEntry*

119 hashEntry = table->entries[ hashIndex ];

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

121 {

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

123 return hashEntry;

124 }

125 return NULL;

126 }

127

128 void *

129 getValueFromTable( char *key, HashTable * table )

130 { HashEntry *entry;

131 entry = getEntryFromTable( key, table );

132 if( entry == NULL ) return NULL;

133

134 return entry->content;

135 }

136

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

138 */

139 int

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

141 { unsigned int hashIdx;

142 HashEntry* hashEntry;

143

144 hashEntry = getEntryFromTable( key, table );

145 if( hashEntry == NULL )

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

147 hashEntry = makeHashEntry( key );

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

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

150 table->numEntries += 1;

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

152 }

153 else

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

155 }

156 hashEntry->content = content;

157 return 1;

158 }

159

160

161 int

162 putEntryIntoTable( HashEntry *entry, HashTable *table )

163 { unsigned int hashIdx;

164 HashEntry* testEntry;

165

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

167 if( testEntry == NULL )

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

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

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

171 table->numEntries += 1;

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

173 }

174 else

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

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

177 // to elem given to insert into table!

178 testEntry->content = entry->content;

179 entry->content = NULL;

180 freeHashEntryButNotContent( entry );

181 }

182 return 1;

183 }

184

185 /*Better version

186 */

187 void

188 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

189 { HashEntry *testEntry, *prevEntry = NULL;

190 unsigned int

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

192

193 testEntry = table->entries[ hashIndex ];

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

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

196 { if( prevEntry == NULL )

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

198 entry->next = testEntry->next;

199 }

200 else

201 { prevEntry->next = entry;

202 entry->next = testEntry->next;

203 }

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

205 return;

206 }

207 }

208 //wasn't found, so insert

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

210 table->entries[hashIndex] = entry;

211 }

212

213

214 bool8

215 deleteEntryFromTable( char *key, HashTable *table )

216 { HashEntry *hashEntry;

217 HashEntry **addrOfPrevPtr;

218 unsigned int hashIndex;

219

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

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

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

223 while( hashEntry != NULL )

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

225 {

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

227 //TODO: Free the contents of entry?

228 freeHashEntryButNotContent( hashEntry );

229 table->numEntries -= 1;

230 return TRUE;

231 }

232 addrOfPrevPtr = &( hashEntry->next );

233 hashEntry = *addrOfPrevPtr;

234 }

235 return FALSE;

236 }

237

238 /*Frees hash table struct, all entry strucs, and even the contents of each

239 * entry.

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 PR_int__free( entry->key ); //was PR_int__malloc'd above, so free it

266 PR_int__free( entry );

267 }

268

269 void

270 freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )

271 {

272 if( entry->content != NULL )

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

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

275 PR_WL__free( entry );

276 }

277

278 void

279 freeHashTable_WL( HashTable *table )

280 { int i;

281 HashEntry *hashEntry, *temp, **entries;

282

283 entries = table->entries;

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

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

286 { hashEntry = entries[i];

287 while( hashEntry != NULL )

288 {

289 temp = hashEntry->next;

290 freeHashEntryUsing_WL( hashEntry, table );

291 hashEntry = temp;

292 }

293 }

294 }

295 }

296

297

298 void

299 freeHashEntryButNotContent( HashEntry *entry )

300 {

301 PR_int__free( entry->key ); //was PR_int__malloc'd above, so free it

302 PR_int__free( entry );

303 }

304

305 void

306 freeHashEntryButNotContent_WL( HashEntry *entry )

307 {

308 PR_WL__free( entry->key ); //was PR_int__malloc'd above, so free it

309 PR_WL__free( entry );

310 }

311

312

313

314

315 //======================= 32 bit integer key version ======================

316

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

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

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

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

321

322

323 HashTable *

324 makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )

325 { HashTable * retTable;

326 int32 numHashSlots;

327

328 retTable = PR_int__malloc( sizeof( HashTable ) );

329

330 numHashSlots = 1 << powerOf2OfSz;

331 retTable->hashMask = 0xffffffff >> 32 - powerOf2OfSz;

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

333

334 retTable->freeEntryContentFn = freeFn;

335

336 retTable->entries = PR_int__malloc( numHashSlots * sizeof(HashEntry *));

337 retTable->numEntries = 0;

338 retTable->tableSz = numHashSlots;

339

340 nullOutTablesArray( retTable );

341

342 return retTable;

343 }

344

345 HashTable *

346 makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )

347 {

348 return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );

349 }

350

351 HashEntry *

352 makeHashEntry32( uint32 * key )

353 { HashEntry *hashEntry;

354

355 hashEntry = (HashEntry*) PR_int__malloc( sizeof( HashEntry ) );

356 if( hashEntry == NULL ) return NULL;

357 hashEntry->key = PR_int__malloc( sizeOfKey(key) );

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

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

360 hashEntry->next = NULL;

361

362 return hashEntry;

363 }

364

365

366

367 int32

368 putEntryIntoTable32( HashEntry *entry, HashTable *table )

369 { unsigned int hashIdx;

370 HashEntry* testEntry;

371

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

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

374 { hashIdx = hashThisKey32( entry->key, table->tableSz );

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

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

377 table->numEntries += 1;

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

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

380 }

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

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

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

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

385 // to elem given to insert into table!

386 testEntry->content = entry->content;

387 entry->content = NULL;

388 freeHashEntryButNotContent( entry );

389 }

390 return 1;

391 }

392

393

394 void

395 doubleTableSize32( HashTable *table )

396 { int i, oldTableSz, newTableSz;

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

398

399 oldTableSz = table->tableSz;

400 oldEntries = table->entries;

401

402 newTableSz = 2 * oldTableSz;

403 newEntries = PR_int__malloc( newTableSz * sizeof(HashEntry *) );

404

405 table->tableSz = newTableSz;

406 table->entries = newEntries;

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

408

409 // move all the entries from old to new

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

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

412 { entry = oldEntries[i];

413 while( entry != NULL )

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

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

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

417 entry = nextEntry;

418 }

419 }

420 }

421 }

422

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

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

425 * the array.*/

426 int32

427 hashThisKey32( uint32 *key, HashTable *hashTable )

428 { int32 hashOfKey;

429

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

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

432 hashTable->prevHash = hashOfKey;

433

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

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

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

437 }

438

439

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

441 * rest of the integers in the array

442 */

443 HashEntry *

444 getEntryFromTable32( uint32 *key, HashTable * table )

445 { unsigned int

446 hashIndex = hashThisKey32( key, table );

447 HashEntry*

448 hashEntry = table->entries[ hashIndex ];

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

450 {

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

452 return hashEntry;

453 }

454 return NULL;

455 }

456

457 void *

458 getValueFromTable32( uint32 *key, HashTable * table )

459 { HashEntry *entry;

460 entry = getEntryFromTable32( key, table );

461 if( entry == NULL ) return NULL;

462

463 return entry->content;

464 }

465

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

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

468 HashEntry *

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

470 { unsigned int hashIdx;

471 HashEntry* hashEntry;

472

473 hashEntry = getEntryFromTable32( key, table );

474 if( hashEntry == NULL )

475 { hashIdx = hashThisKey32( key, table );

476 hashEntry = makeHashEntry32( key );

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

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

479 table->numEntries += 1;

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

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

482 }

483 else

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

485 }

486 hashEntry->content = content;

487 return hashEntry;

488 }

489

490

491 bool32

492 deleteEntryFromTable32( uint32 *key, HashTable *table )

493 { HashEntry *hashEntry;

494 HashEntry **addrOfPrevPtr;

495 unsigned int hashIndex;

496

497 hashIndex = hashThisKey32( key, table );

498 hashEntry = table->entries[ hashIndex ];

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

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

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

502 while( hashEntry != NULL )

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

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

505 freeHashEntryButNotContent( hashEntry );

506 table->numEntries -= 1;

507 return TRUE;

508 }

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

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

511 }

512 return FALSE;

513 }

514

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

view PrivateHash.c @ 31:1d42a512f482