VMS/C_Libraries/Hash_impl: 18ec64d06e35 PrivateHash.c

view PrivateHash.c @ 29:18ec64d06e35

Renamed VMS to PR, in new branch

author	Sean Halle <seanhalle@yahoo.com>
date	Mon, 03 Sep 2012 15:03:38 -0700
parents	b032601956bb
children	1d42a512f482

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 void

239 freeHashTable( HashTable *table )

240 { int i;

241 HashEntry *hashEntry, *temp, **entries;

242

243 entries = table->entries;

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

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

246 { hashEntry = entries[i];

247 while( hashEntry != NULL )

248 {

249 temp = hashEntry->next;

250 freeHashEntryUsing( hashEntry, table );

251 hashEntry = temp;

252 }

253 }

254 }

255 }

256

257 void

258 freeHashEntryUsing( HashEntry *entry, HashTable *table )

259 {

260 if( entry->content != NULL )

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

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

263 PR_int__free( entry );

264 }

265

266 void

267 freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )

268 {

269 if( entry->content != NULL )

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

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

272 PR_WL__free( entry );

273 }

274

275 void

276 freeHashTable_WL( HashTable *table )

277 { int i;

278 HashEntry *hashEntry, *temp, **entries;

279

280 entries = table->entries;

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

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

283 { hashEntry = entries[i];

284 while( hashEntry != NULL )

285 {

286 temp = hashEntry->next;

287 freeHashEntryUsing_WL( hashEntry, table );

288 hashEntry = temp;

289 }

290 }

291 }

292 }

293

294

295 void

296 freeHashEntryButNotContent( HashEntry *entry )

297 {

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

299 PR_int__free( entry );

300 }

301

302 void

303 freeHashEntryButNotContent_WL( HashEntry *entry )

304 {

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

306 PR_WL__free( entry );

307 }

308

309

310

311

312 //======================= 32 bit integer key version ======================

313

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

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

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

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

318

319

320 HashTable *

321 makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )

322 { HashTable * retTable;

323 int32 numHashSlots;

324

325 retTable = PR_int__malloc( sizeof( HashTable ) );

326

327 numHashSlots = 1 << powerOf2OfSz;

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

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

330

331 retTable->freeEntryContentFn = freeFn;

332

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

334 retTable->numEntries = 0;

335 retTable->tableSz = numHashSlots;

336

337 nullOutTablesArray( retTable );

338

339 return retTable;

340 }

341

342 HashTable *

343 makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )

344 {

345 return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );

346 }

347

348 HashEntry *

349 makeHashEntry32( uint32 * key )

350 { HashEntry *hashEntry;

351

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

353 if( hashEntry == NULL ) return NULL;

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

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

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

357 hashEntry->next = NULL;

358

359 return hashEntry;

360 }

361

362

363

364 int32

365 putEntryIntoTable32( HashEntry *entry, HashTable *table )

366 { unsigned int hashIdx;

367 HashEntry* testEntry;

368

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

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

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

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

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

374 table->numEntries += 1;

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

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

377 }

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

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

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

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

382 // to elem given to insert into table!

383 testEntry->content = entry->content;

384 entry->content = NULL;

385 freeHashEntryButNotContent( entry );

386 }

387 return 1;

388 }

389

390

391 void

392 doubleTableSize32( HashTable *table )

393 { int i, oldTableSz, newTableSz;

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

395

396 oldTableSz = table->tableSz;

397 oldEntries = table->entries;

398

399 newTableSz = 2 * oldTableSz;

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

401

402 table->tableSz = newTableSz;

403 table->entries = newEntries;

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

405

406 // move all the entries from old to new

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

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

409 { entry = oldEntries[i];

410 while( entry != NULL )

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

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

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

414 entry = nextEntry;

415 }

416 }

417 }

418 }

419

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

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

422 * the array.*/

423 int32

424 hashThisKey32( uint32 *key, HashTable *hashTable )

425 { int32 hashOfKey;

426

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

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

429 hashTable->prevHash = hashOfKey;

430

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

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

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

434 }

435

436

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

438 * rest of the integers in the array

439 */

440 HashEntry *

441 getEntryFromTable32( uint32 *key, HashTable * table )

442 { unsigned int

443 hashIndex = hashThisKey32( key, table );

444 HashEntry*

445 hashEntry = table->entries[ hashIndex ];

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

447 {

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

449 return hashEntry;

450 }

451 return NULL;

452 }

453

454 void *

455 getValueFromTable32( uint32 *key, HashTable * table )

456 { HashEntry *entry;

457 entry = getEntryFromTable32( key, table );

458 if( entry == NULL ) return NULL;

459

460 return entry->content;

461 }

462

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

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

465 HashEntry *

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

467 { unsigned int hashIdx;

468 HashEntry* hashEntry;

469

470 hashEntry = getEntryFromTable32( key, table );

471 if( hashEntry == NULL )

472 { hashIdx = hashThisKey32( key, table );

473 hashEntry = makeHashEntry32( key );

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

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

476 table->numEntries += 1;

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

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

479 }

480 else

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

482 }

483 hashEntry->content = content;

484 return hashEntry;

485 }

486

487

488 bool32

489 deleteEntryFromTable32( uint32 *key, HashTable *table )

490 { HashEntry *hashEntry;

491 HashEntry **addrOfPrevPtr;

492 unsigned int hashIndex;

493

494 hashIndex = hashThisKey32( key, table );

495 hashEntry = table->entries[ hashIndex ];

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

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

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

499 while( hashEntry != NULL )

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

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

502 freeHashEntryButNotContent( hashEntry );

503 table->numEntries -= 1;

504 return TRUE;

505 }

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

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

508 }

509 return FALSE;

510 }

511

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

view PrivateHash.c @ 29:18ec64d06e35