aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_db_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_db_hash.c')
-rw-r--r--erts/emulator/beam/erl_db_hash.c164
1 files changed, 117 insertions, 47 deletions
diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c
index 06dac8f161..c2157457a0 100644
--- a/erts/emulator/beam/erl_db_hash.c
+++ b/erts/emulator/beam/erl_db_hash.c
@@ -382,7 +382,7 @@ static HashDbTerm* search_list(DbTableHash* tb, Eterm key,
static void shrink(DbTableHash* tb, int nactive);
static void grow(DbTableHash* tb, int nactive);
static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2,
- DbTableHash*);
+ Uint sz, DbTableHash*);
static int analyze_pattern(DbTableHash *tb, Eterm pattern,
struct mp_info *mpi);
@@ -426,6 +426,7 @@ static int db_select_count_continue_hash(Process *p, DbTable *tbl,
static int db_select_delete_continue_hash(Process *p, DbTable *tbl,
Eterm continuation, Eterm *ret);
+static int db_take_hash(Process *, DbTable *, Eterm, Eterm *);
static void db_print_hash(int to,
void *to_arg,
int show,
@@ -536,6 +537,7 @@ DbTableMethod db_hash =
db_select_delete_continue_hash,
db_select_count_hash,
db_select_count_continue_hash,
+ db_take_hash,
db_delete_all_objects_hash,
db_free_table_hash,
db_free_table_continue_hash,
@@ -646,25 +648,6 @@ restart:
/* ToDo: Maybe try grow/shrink the table as well */
}
-/* Only used by tests
-*/
-Uint db_kept_items_hash(DbTableHash *tb)
-{
- Uint kept_items = 0;
- Uint ix = 0;
- erts_smp_rwmtx_t* lck = RLOCK_HASH(tb,ix);
- HashDbTerm* b;
- do {
- for (b = BUCKET(tb, ix); b != NULL; b = b->next) {
- if (b->hvalue == INVALID_HASH) {
- ++kept_items;
- }
- }
- ix = next_slot(tb, ix, &lck);
- }while (ix);
- return kept_items;
-}
-
int db_create_hash(Process *p, DbTable *tbl)
{
DbTableHash *tb = &tbl->hash;
@@ -879,34 +862,49 @@ Ldone:
return ret;
}
+static Eterm
+get_term_list(Process *p, DbTableHash *tb, Eterm key, HashValue hval,
+ HashDbTerm *b1, HashDbTerm **bend)
+{
+ HashDbTerm* b2 = b1->next;
+ Eterm copy;
+ Uint sz = b1->dbterm.size + 2;
+
+ if (tb->common.status & (DB_BAG | DB_DUPLICATE_BAG)) {
+ while (b2 && has_key(tb, b2, key, hval)) {
+ if (b2->hvalue != INVALID_HASH)
+ sz += b2->dbterm.size + 2;
+
+ b2 = b2->next;
+ }
+ }
+ copy = build_term_list(p, b1, b2, sz, tb);
+ CHECK_TABLES();
+ if (bend) {
+ *bend = b2;
+ }
+ return copy;
+}
+
int db_get_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
{
DbTableHash *tb = &tbl->hash;
HashValue hval;
int ix;
- HashDbTerm* b1;
+ HashDbTerm* b;
erts_smp_rwmtx_t* lck;
hval = MAKE_HASH(key);
lck = RLOCK_HASH(tb,hval);
ix = hash_to_ix(tb, hval);
- b1 = BUCKET(tb, ix);
-
- while(b1 != 0) {
- if (has_live_key(tb,b1,key,hval)) {
- HashDbTerm* b2 = b1->next;
- Eterm copy;
+ b = BUCKET(tb, ix);
- if (tb->common.status & (DB_BAG | DB_DUPLICATE_BAG)) {
- while(b2 != NULL && has_key(tb,b2,key,hval))
- b2 = b2->next;
- }
- copy = build_term_list(p, b1, b2, tb);
- CHECK_TABLES();
- *ret = copy;
+ while(b != 0) {
+ if (has_live_key(tb, b, key, hval)) {
+ *ret = get_term_list(p, tb, key, hval, b, NULL);
goto done;
}
- b1 = b1->next;
+ b = b->next;
}
*ret = NIL;
done:
@@ -1240,7 +1238,7 @@ static int db_slot_hash(Process *p, DbTable *tbl, Eterm slot_term, Eterm *ret)
lck = RLOCK_HASH(tb, slot);
nactive = NACTIVE(tb);
if (slot < nactive) {
- *ret = build_term_list(p, BUCKET(tb, slot), 0, tb);
+ *ret = build_term_list(p, BUCKET(tb, slot), NULL, 0, tb);
retval = DB_ERROR_NONE;
}
else if (slot == nactive) {
@@ -2069,6 +2067,46 @@ trap:
}
+static int db_take_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+{
+ DbTableHash *tb = &tbl->hash;
+ HashDbTerm **bp, *b;
+ HashValue hval = MAKE_HASH(key);
+ erts_smp_rwmtx_t *lck = WLOCK_HASH(tb, hval);
+ int ix = hash_to_ix(tb, hval);
+ int nitems_diff = 0;
+
+ *ret = NIL;
+ for (bp = &BUCKET(tb, ix), b = *bp; b; bp = &b->next, b = b->next) {
+ if (has_live_key(tb, b, key, hval)) {
+ HashDbTerm *bend;
+
+ *ret = get_term_list(p, tb, key, hval, b, &bend);
+ while (b != bend) {
+ --nitems_diff;
+ if (nitems_diff == -1 && IS_FIXED(tb)) {
+ /* Pseudo remove (no need to keep several of same key) */
+ add_fixed_deletion(tb, ix);
+ bp = &b->next;
+ b->hvalue = INVALID_HASH;
+ b = b->next;
+ } else {
+ *bp = b->next;
+ free_term(tb, b);
+ b = *bp;
+ }
+ }
+ break;
+ }
+ }
+ WUNLOCK_HASH(lck);
+ if (nitems_diff) {
+ erts_smp_atomic_add_nob(&tb->common.nitems, nitems_diff);
+ try_shrink(tb);
+ }
+ return DB_ERROR_NONE;
+}
+
/*
** Other interface routines (not directly coupled to one bif)
*/
@@ -2104,10 +2142,38 @@ int db_mark_all_deleted_hash(DbTable *tbl)
static void db_print_hash(int to, void *to_arg, int show, DbTable *tbl)
{
DbTableHash *tb = &tbl->hash;
+ DbHashStats stats;
int i;
erts_print(to, to_arg, "Buckets: %d\n", NACTIVE(tb));
-
+
+#ifdef ERTS_SMP
+ i = tbl->common.is_thread_safe;
+ /* If crash dumping we set table to thread safe in order to
+ avoid taking any locks */
+ if (ERTS_IS_CRASH_DUMPING)
+ tbl->common.is_thread_safe = 1;
+
+ db_calc_stats_hash(&tbl->hash, &stats);
+
+ tbl->common.is_thread_safe = i;
+#else
+ db_calc_stats_hash(&tbl->hash, &stats);
+#endif
+
+ erts_print(to, to_arg, "Chain Length Avg: %f\n", stats.avg_chain_len);
+ erts_print(to, to_arg, "Chain Length Max: %d\n", stats.max_chain_len);
+ erts_print(to, to_arg, "Chain Length Min: %d\n", stats.min_chain_len);
+ erts_print(to, to_arg, "Chain Length Std Dev: %f\n",
+ stats.std_dev_chain_len);
+ erts_print(to, to_arg, "Chain Length Expected Std Dev: %f\n",
+ stats.std_dev_expected);
+
+ if (IS_FIXED(tb))
+ erts_print(to, to_arg, "Fixed: %d\n", stats.kept_items);
+ else
+ erts_print(to, to_arg, "Fixed: false\n");
+
if (show) {
for (i = 0; i < NACTIVE(tb); i++) {
HashDbTerm* list = BUCKET(tb,i);
@@ -2483,23 +2549,23 @@ static int free_seg(DbTableHash *tb, int free_records)
** Copy terms from ptr1 until ptr2
** works for ptr1 == ptr2 == 0 => []
** or ptr2 == 0
+** sz is either precalculated heap size or 0 if not known
*/
static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2,
- DbTableHash* tb)
+ Uint sz, DbTableHash* tb)
{
- int sz = 0;
HashDbTerm* ptr;
Eterm list = NIL;
Eterm copy;
Eterm *hp, *hend;
- ptr = ptr1;
- while(ptr != ptr2) {
-
- if (ptr->hvalue != INVALID_HASH)
- sz += ptr->dbterm.size + 2;
-
- ptr = ptr->next;
+ if (!sz) {
+ ptr = ptr1;
+ while(ptr != ptr2) {
+ if (ptr->hvalue != INVALID_HASH)
+ sz += ptr->dbterm.size + 2;
+ ptr = ptr->next;
+ }
}
hp = HAlloc(p, sz);
@@ -2833,6 +2899,7 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats)
erts_smp_rwmtx_t* lck;
int sum = 0;
int sq_sum = 0;
+ int kept_items = 0;
int ix;
int len;
@@ -2844,6 +2911,8 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats)
len = 0;
for (b = BUCKET(tb,ix); b!=NULL; b=b->next) {
len++;
+ if (b->hvalue == INVALID_HASH)
+ ++kept_items;
}
sum += len;
sq_sum += len*len;
@@ -2855,7 +2924,8 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats)
stats->std_dev_chain_len = sqrt((sq_sum - stats->avg_chain_len*sum) / NACTIVE(tb));
/* Expected standard deviation from a good uniform hash function,
ie binomial distribution (not taking the linear hashing into acount) */
- stats->std_dev_expected = sqrt(stats->avg_chain_len * (1 - 1.0/NACTIVE(tb)));
+ stats->std_dev_expected = sqrt(stats->avg_chain_len * (1 - 1.0/NACTIVE(tb)));
+ stats->kept_items = kept_items;
}
#ifdef HARDDEBUG
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-14 05:15:02 +0000