VMS/C_Libraries/Hash_impl: 14c289b351ff PrivateHash.c

view PrivateHash.c @ 36:14c289b351ff

added nb project

author	Sean Halle <seanhalle@yahoo.com>
date	Mon, 30 Sep 2013 01:05:39 -0700
parents	049a8d8917c5
children

line source

1 /*

3 * Licensed under GNU General Public License version 2

4 *

5 *

6 * Author: seanhalle@yahoo.com

7 */

9 #include <PR__include/prhash.h>

10 #include <PR__include/prmalloc.h>

12 HashTable *

13 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )

14 { HashTable * retTable;

15 retTable = PR__malloc( sizeof( HashTable ) );

17 retTable->freeEntryContentFn = freeFn;

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

20 retTable->numEntries = 0;

21 retTable->tableSz = numHashSlots;

23 nullOutTablesArray( retTable );

25 return retTable;

26 }

28 void

29 doubleTableSize( HashTable *table )

30 { int i, oldTableSz, newTableSz;

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

33 oldTableSz = table->tableSz;

34 oldEntries = table->entries;

36 newTableSz = 2 * oldTableSz;

37 newEntries = PR__malloc( newTableSz * sizeof(HashEntry *) );

39 table->tableSz = newTableSz;

40 table->entries = newEntries;

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

43 // move all the entries from old to new

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

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

46 { entry = oldEntries[i];

47 while( entry != NULL )

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

49 entry->next = NULL;

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

51 entry = nextEntry;

52 }

53 }

54 }

55 }

57 void

58 nullOutTablesArray( HashTable *table )

59 { int i, tableSz;

60 tableSz = table->tableSz;

61 HashEntry ** entries = table->entries;

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

63 entries[ i ] = NULL;

64 }

66 unsigned int

67 hashThisKey( char* s, int hashSz )

68 { unsigned int h = 0;

69 unsigned int i;

70 hashkey_t* key = (hashkey_t*)s;

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

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

74 return h % hashSz;

75 }

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

78 inline HashEntry *

79 makeHashEntry( char * key )

80 { HashEntry *hashEntry;

82 int32 len = strlen(key);

84 hashEntry = (HashEntry*) PR__malloc( sizeof( HashEntry ) );

85 if( hashEntry == NULL ) return NULL;

87 hashEntry->key = PR__malloc( len + 1 );

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

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

90 hashEntry->next = NULL;

92 return hashEntry;

93 }

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

97 */

98 HashEntry *

99 getEntryFromTable( char *key, HashTable * table )

100 { uint32

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

102 HashEntry*

103 hashEntry = table->entries[ hashIndex ];

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

105 {

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

107 return hashEntry;

108 }

109 return NULL;

110 }

111

112 void *

113 getValueFromTable( char *key, HashTable * table )

114 { HashEntry *entry;

115 entry = getEntryFromTable( key, table );

116 if( entry == NULL ) return NULL;

117

118 return entry->content;

119 }

120

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

122 */

123 int

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

125 { unsigned int hashIdx;

126 HashEntry* hashEntry;

127

128 hashEntry = getEntryFromTable( key, table );

129 if( hashEntry == NULL )

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

131 hashEntry = makeHashEntry( key );

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

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

134 table->numEntries += 1;

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

136 }

137 else

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

139 }

140 hashEntry->content = content;

141 return 1;

142 }

143

144

145 int

146 putEntryIntoTable( HashEntry *entry, HashTable *table )

147 { unsigned int hashIdx;

148 HashEntry* testEntry;

149

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

151 if( testEntry == NULL )

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

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

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

155 table->numEntries += 1;

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

157 }

158 else

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

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

161 // to elem given to insert into table!

162 testEntry->content = entry->content;

163 entry->content = NULL;

164 freeHashEntryButNotContent( entry );

165 }

166 return 1;

167 }

168

169 /*Better version

170 */

171 void

172 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )

173 { HashEntry *testEntry, *prevEntry = NULL;

174 unsigned int

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

176

177 testEntry = table->entries[ hashIndex ];

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

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

180 { if( prevEntry == NULL )

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

182 entry->next = testEntry->next;

183 }

184 else

185 { prevEntry->next = entry;

186 entry->next = testEntry->next;

187 }

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

189 return;

190 }

191 }

192 //wasn't found, so insert

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

194 table->entries[hashIndex] = entry;

195 }

196

197

198 bool8

199 deleteEntryFromTable( char *key, HashTable *table )

200 { HashEntry *hashEntry;

201 HashEntry **addrOfPrevPtr;

202 unsigned int hashIndex;

203

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

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

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

207 while( hashEntry != NULL )

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

209 {

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

211 //TODO: Free the contents of entry?

212 freeHashEntryButNotContent( hashEntry );

213 table->numEntries -= 1;

214 return TRUE;

215 }

216 addrOfPrevPtr = &( hashEntry->next );

217 hashEntry = *addrOfPrevPtr;

218 }

219 return FALSE;

220 }

221

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

223 * entry.

224 */

225 void

226 freeHashTable( HashTable *table )

227 { int i;

228 HashEntry *hashEntry, *temp, **entries;

229

230 entries = table->entries;

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

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

233 { hashEntry = entries[i];

234 while( hashEntry != NULL )

235 {

236 temp = hashEntry->next;

237 freeHashEntryUsing( hashEntry, table );

238 hashEntry = temp;

239 }

240 }

241 }

242 }

243

244 void

245 freeHashEntryUsing( HashEntry *entry, HashTable *table )

246 {

247 if( entry->content != NULL )

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

249 PR__free( entry->key ); //was PR__malloc'd above, so free it

250 PR__free( entry );

251 }

252

253 /* obsolete -- delete

254

255 HashTable *

256 makeHashTable_WL( int numHashSlots, FreeEntryContentFnPtr freeFn )

257 { HashTable * retTable;

258 retTable = PR__malloc( sizeof( HashTable ) );

259

260 retTable->freeEntryContentFn = freeFn;

261

262 retTable->entries = PR__malloc( numHashSlots * sizeof(HashEntry *) );

263 retTable->numEntries = 0;

264 retTable->tableSz = numHashSlots;

265

266 nullOutTablesArray( retTable );

267

268 return retTable;

269 }

270

271 void

272 freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )

273 {

274 if( entry->content != NULL )

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

276 PR__free( entry->key ); //was PR__malloc'd above, so free it

277 PR__free( entry );

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

303 PR__free( entry );

304 }

305

306

307

308

309 //======================= 32 bit integer key version ======================

310

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

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

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

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

315

316

317 HashTable *

318 makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )

319 { HashTable * retTable;

320 int32 numHashSlots;

321

322 retTable = PR__malloc( sizeof( HashTable ) );

323

324 numHashSlots = 1 << powerOf2OfSz;

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

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

327

328 retTable->freeEntryContentFn = freeFn;

329

330 retTable->entries = PR__malloc( numHashSlots * sizeof(HashEntry *));

331 retTable->numEntries = 0;

332 retTable->tableSz = numHashSlots;

333

334 nullOutTablesArray( retTable );

335

336 return retTable;

337 }

338

339 HashTable *

340 makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )

341 {

342 return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );

343 }

344

345 HashEntry *

346 makeHashEntry32( uint32 * key )

347 { HashEntry *hashEntry;

348

349 hashEntry = (HashEntry*) PR__malloc( sizeof( HashEntry ) );

350 if( hashEntry == NULL ) return NULL;

351 hashEntry->key = PR__malloc( sizeOfKey(key) );

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

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

354 hashEntry->next = NULL;

355

356 return hashEntry;

357 }

358

359

360

361 int32

362 putEntryIntoTable32( HashEntry *entry, HashTable *table )

363 { unsigned int hashIdx;

364 HashEntry* testEntry;

365

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

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

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

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

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

371 table->numEntries += 1;

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

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

374 }

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

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

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

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

379 // to elem given to insert into table!

380 testEntry->content = entry->content;

381 entry->content = NULL;

382 freeHashEntryButNotContent( entry );

383 }

384 return 1;

385 }

386

387

388 void

389 doubleTableSize32( HashTable *table )

390 { int i, oldTableSz, newTableSz;

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

392

393 oldTableSz = table->tableSz;

394 oldEntries = table->entries;

395

396 newTableSz = 2 * oldTableSz;

397 newEntries = PR__malloc( newTableSz * sizeof(HashEntry *) );

398

399 table->tableSz = newTableSz;

400 table->entries = newEntries;

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

402

403 // move all the entries from old to new

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

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

406 { entry = oldEntries[i];

407 while( entry != NULL )

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

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

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

411 entry = nextEntry;

412 }

413 }

414 }

415 }

416

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

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

419 * the array.*/

420 int32

421 hashThisKey32( uint32 *key, HashTable *hashTable )

422 { int32 hashOfKey;

423

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

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

426 hashTable->prevHash = hashOfKey;

427

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

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

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

431 }

432

433

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

435 * rest of the integers in the array

436 */

437 HashEntry *

438 getEntryFromTable32( uint32 *key, HashTable * table )

439 { unsigned int

440 hashIndex = hashThisKey32( key, table );

441 HashEntry*

442 hashEntry = table->entries[ hashIndex ];

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

444 {

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

446 return hashEntry;

447 }

448 return NULL;

449 }

450

451 void *

452 getValueFromTable32( uint32 *key, HashTable * table )

453 { HashEntry *entry;

454 entry = getEntryFromTable32( key, table );

455 if( entry == NULL ) return NULL;

456

457 return entry->content;

458 }

459

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

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

462 HashEntry *

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

464 { unsigned int hashIdx;

465 HashEntry* hashEntry;

466

467 hashEntry = getEntryFromTable32( key, table );

468 if( hashEntry == NULL )

469 { hashIdx = hashThisKey32( key, table );

470 hashEntry = makeHashEntry32( key );

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

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

473 table->numEntries += 1;

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

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

476 }

477 else

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

479 }

480 hashEntry->content = content;

481 return hashEntry;

482 }

483

484

485 bool32

486 deleteEntryFromTable32( uint32 *key, HashTable *table )

487 { HashEntry *hashEntry;

488 HashEntry **addrOfPrevPtr;

489 unsigned int hashIndex;

490

491 hashIndex = hashThisKey32( key, table );

492 hashEntry = table->entries[ hashIndex ];

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

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

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

496 while( hashEntry != NULL )

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

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

499 freeHashEntryButNotContent( hashEntry );

500 table->numEntries -= 1;

501 return TRUE;

502 }

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

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

505 }

506 return FALSE;

507 }

508

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

view PrivateHash.c @ 36:14c289b351ff