Lines Matching refs:table
64 PL_DHashAllocTable(PLDHashTable *table, PRUint32 nbytes)
74 PL_DHashFreeTable(PLDHashTable *table, void *ptr)
84 PL_DHashStringKey(PLDHashTable *table, const void *key)
96 PL_DHashGetKeyStub(PLDHashTable *table, PLDHashEntryHdr *entry)
104 PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key)
110 PL_DHashMatchEntryStub(PLDHashTable *table,
120 PL_DHashMatchStringKey(PLDHashTable *table,
132 PL_DHashMoveEntryStub(PLDHashTable *table,
136 memcpy(to, from, table->entrySize);
140 PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry)
142 memset(entry, 0, table->entrySize);
146 PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry)
155 memset(entry, 0, table->entrySize);
159 PL_DHashFinalizeStub(PLDHashTable *table)
185 PLDHashTable *table;
188 table = (PLDHashTable *) RTMemAlloc(sizeof *table);
190 table = (PLDHashTable *) malloc(sizeof *table);
192 if (!table)
194 if (!PL_DHashTableInit(table, ops, data, entrySize, capacity)) {
196 RTMemFree(table);
198 free(table);
202 return table;
206 PL_DHashTableDestroy(PLDHashTable *table)
208 PL_DHashTableFinish(table);
210 RTMemFree(table);
212 free(table);
217 PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data,
226 "pldhash: for the table at address %p, the given entrySize"
228 (void *)table,
234 table->ops = ops;
235 table->data = data;
242 table->hashShift = PL_DHASH_BITS - log2;
243 table->maxAlphaFrac = 0xC0; /* .75 */
244 table->minAlphaFrac = 0x40; /* .25 */
245 table->entrySize = entrySize;
246 table->entryCount = table->removedCount = 0;
247 table->generation = 0;
250 table->entryStore = ops->allocTable(table, nbytes);
251 if (!table->entryStore)
253 memset(table->entryStore, 0, nbytes);
254 METER(memset(&table->stats, 0, sizeof table->stats));
259 * Compute max and min load numbers (entry counts) from table params.
261 #define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
262 #define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
265 PL_DHashTableSetAlphaBounds(PLDHashTable *table,
298 size = PL_DHASH_TABLE_SIZE(table);
302 table->maxAlphaFrac = (uint8)(maxAlpha * 256);
303 table->minAlphaFrac = (uint8)(minAlpha * 256);
307 * Double hashing needs the second hash code to be relatively prime to table
323 * assist iterator writers who inspect table->entryStore directly.
336 /* Compute the address of the indexed entry in table. */
337 #define ADDRESS_ENTRY(table, index) \
338 ((PLDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
341 PL_DHashTableFinish(PLDHashTable *table)
354 PL_DHashTableDumpMeter(table, NULL, dumpfp);
360 table->ops->finalize(table);
363 entryAddr = table->entryStore;
364 entrySize = table->entrySize;
365 entryLimit = entryAddr + PL_DHASH_TABLE_SIZE(table) * entrySize;
369 METER(table->stats.removeEnums++);
370 table->ops->clearEntry(table, entry);
376 table->ops->freeTable(table, table->entryStore);
380 SearchTable(PLDHashTable *table, const void *key, PLDHashNumber keyHash,
389 METER(table->stats.searches++);
393 hashShift = table->hashShift;
395 entry = ADDRESS_ENTRY(table, hash1);
399 METER(table->stats.misses++);
404 matchEntry = table->ops->matchEntry;
405 if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
406 METER(table->stats.hits++);
411 sizeLog2 = PL_DHASH_BITS - table->hashShift;
425 METER(table->stats.steps++);
429 entry = ADDRESS_ENTRY(table, hash1);
431 METER(table->stats.misses++);
436 matchEntry(table, entry, key)) {
437 METER(table->stats.hits++);
455 ChangeTable(PLDHashTable *table, int deltaLog2)
466 PR_ASSERT(table->generation != PR_UINT32_MAX);
467 if (table->generation == PR_UINT32_MAX)
472 oldLog2 = PL_DHASH_BITS - table->hashShift;
478 entrySize = table->entrySize;
481 newEntryStore = table->ops->allocTable(table, nbytes);
485 /* We can't fail from here on, so update table parameters. */
486 table->hashShift = PL_DHASH_BITS - newLog2;
487 table->removedCount = 0;
488 table->generation++;
490 if (table->generation == PR_UINT32_MAX)
491 table->generation++;
494 /* Assign the new entry store to table. */
496 oldEntryAddr = oldEntryStore = table->entryStore;
497 table->entryStore = newEntryStore;
498 getKey = table->ops->getKey;
499 moveEntry = table->ops->moveEntry;
506 newEntry = SearchTable(table, getKey(table, oldEntry),
509 moveEntry(table, oldEntry, newEntry);
515 table->ops->freeTable(table, oldEntryStore);
520 PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op)
527 keyHash = table->ops->hashKey(table, key);
536 METER(table->stats.lookups++);
537 entry = SearchTable(table, key, keyHash, op);
542 * If alpha is >= .75, grow or compress the table. If key is already
543 * in the table, we may grow once more than necessary, but only if we
546 size = PL_DHASH_TABLE_SIZE(table);
547 if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
549 if (table->removedCount >= size >> 2) {
550 METER(table->stats.compresses++);
553 METER(table->stats.grows++);
558 * Grow or compress table, returning null if ChangeTable fails and
561 if (!ChangeTable(table, deltaLog2) &&
562 table->entryCount + table->removedCount == size - 1) {
563 METER(table->stats.addFailures++);
570 * then skip it while growing the table and re-add it after.
572 entry = SearchTable(table, key, keyHash, op);
575 METER(table->stats.addMisses++);
577 METER(table->stats.addOverRemoved++);
578 table->removedCount--;
581 if (table->ops->initEntry &&
582 !table->ops->initEntry(table, entry, key)) {
584 memset(entry + 1, 0, table->entrySize - sizeof *entry);
588 table->entryCount++;
590 METER(else table->stats.addHits++);
594 entry = SearchTable(table, key, keyHash, op);
597 METER(table->stats.removeHits++);
598 PL_DHashTableRawRemove(table, entry);
600 /* Shrink if alpha is <= .25 and table isn't too small already. */
601 size = PL_DHASH_TABLE_SIZE(table);
605 table->generation != PR_UINT32_MAX &&
607 table->entryCount <= MIN_LOAD(table, size)) {
608 METER(table->stats.shrinks++);
609 (void) ChangeTable(table, -1);
612 METER(else table->stats.removeMisses++);
625 PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry)
631 table->ops->clearEntry(table, entry);
634 table->removedCount++;
636 METER(table->stats.removeFrees++);
639 table->entryCount--;
643 PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg)
663 generation = table->generation;
664 table->generation = PR_UINT32_MAX;
666 entryAddr = table->entryStore;
667 entrySize = table->entrySize;
668 capacity = PL_DHASH_TABLE_SIZE(table);
675 op = etor(table, entry, i++, arg);
677 PR_ASSERT(table->generation == PR_UINT32_MAX);
680 METER(table->stats.removeEnums++);
681 PL_DHashTableRawRemove(table, entry);
690 table->generation = generation;
695 * if the table is underloaded according to the configured minimum alpha,
697 * non-removing enumerations can count on stable table->entryStore until
701 (table->removedCount >= capacity >> 2 ||
703 table->entryCount <= MIN_LOAD(table, capacity)))) {
704 METER(table->stats.enumShrinks++);
705 capacity = table->entryCount;
709 (void) ChangeTable(table,
711 - (PL_DHASH_BITS - table->hashShift));
720 PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp)
730 entryAddr = table->entryStore;
731 entrySize = table->entrySize;
732 hashShift = table->hashShift;
734 tableSize = PL_DHASH_TABLE_SIZE(table);
747 probe = ADDRESS_ENTRY(table, hash1);
759 probe = ADDRESS_ENTRY(table, hash1);
770 entryCount = table->entryCount;
784 fprintf(fp, " table size (in entries): %u\n", tableSize);
785 fprintf(fp, " number of entries: %u\n", table->entryCount);
786 fprintf(fp, " number of removed entries: %u\n", table->removedCount);
787 fprintf(fp, " number of searches: %u\n", table->stats.searches);
788 fprintf(fp, " number of hits: %u\n", table->stats.hits);
789 fprintf(fp, " number of misses: %u\n", table->stats.misses);
790 fprintf(fp, " mean steps per search: %g\n", table->stats.searches ?
791 (double)table->stats.steps
792 / table->stats.searches :
797 fprintf(fp, " number of lookups: %u\n", table->stats.lookups);
798 fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
799 fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
800 fprintf(fp, " adds that found an entry: %u\n", table->stats.addHits);
801 fprintf(fp, " add failures: %u\n", table->stats.addFailures);
802 fprintf(fp, " useful removes: %u\n", table->stats.removeHits);
803 fprintf(fp, " useless removes: %u\n", table->stats.removeMisses);
804 fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
805 fprintf(fp, " removes while enumerating: %u\n", table->stats.removeEnums);
806 fprintf(fp, " number of grows: %u\n", table->stats.grows);
807 fprintf(fp, " number of shrinks: %u\n", table->stats.shrinks);
808 fprintf(fp, " number of compresses: %u\n", table->stats.compresses);
809 fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
815 entry = ADDRESS_ENTRY(table, hash1);
818 if (dump(table, entry, i++, fp) != PL_DHASH_NEXT)
822 entry = ADDRESS_ENTRY(table, hash1);