mirror of
git://git.sv.gnu.org/emacs.git
synced 2026-03-10 08:52:40 -07:00
cc1aa65f17
Ephemerons solve the key-in-value problem for weak key/value pairs. It seems that it's not possible to solve that problem with weak pointers or finalizers. Basically we want a weak key/value pair that implements the rule: The value is reachable, if the key is reachable. The key-in-value problem occurs if all paths to the key go through the value. In this situation, the key is considered reachable only if the value is "externally reachable", i.e. the value is reachable through a path other than through the weak pair. Such weak pairs seem to need an extra phase in the GC algorithm. See [1] for some variants of the algorithm. https://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html * mps/code/mpmst.h (SegStruct): Add fields propagationNeeded, marksChanged, and propagationFinished. * mps/code/mpmtypes.h (RANK_LIST): Add EPHEMERON rank. * mps/code/mps.s (mps_rank_ephemeron): New prototype. * mps/code/mpscawl.h (mps_class_aeph, mps_fix_weak_pair) (mps_fix_weak_or_pair, mps_fix_weak_and_pair): New prototypes. * mps/code/mpsi.c (mps_rank_ephemeron): New function. * mps/code/poolawl.c (AEPHSegStruct, AEPHPoolStruct): New. The implementation the ephemeron pool. * mps/code/seg.c (segAbsInit): Initialize propagationNeeded, marksChanged, and propagationFinished. * mps/code/trace.c (traceBandRetreat, tracePropagateToLowerRanks) (moveSegToEndOfGreyRing): New helpers. (TraceRankForAccess): Handle the RankEPHEMERON. (traceFindGrey, traceScanSegRes): Add special handling for ephemeron segments. * mps/test/function/eph1.c: New test file. * mps/test/function/eph2.c: New test file. * mps/test/function/eph3.c: New test file. * mps/test/function/eph4.c: New test file. * mps/test/test/testlib/ephfmt.c: New file. * mps/test/test/testlib/ephfmt.h: New file. * mps/test/test/testlib/manifest: Add ephfmt.c. * mps/test/testsets/passing: Include eph{1,2,3,4}.c.
90 lines
2.7 KiB
C
90 lines
2.7 KiB
C
/*
|
|
TEST_HEADER
|
|
id = $Id$
|
|
summary = test mps_fix_weak_and_pair
|
|
language = c
|
|
link = testlib.o ephfmt.o
|
|
END_HEADER
|
|
*/
|
|
|
|
#include "ephfmt.h"
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
static void test_reachable_key(mmp mm, oop s[ROOT_COUNT])
|
|
{
|
|
comment("test_reachable_key");
|
|
s[0] = string_from_cstr(mm->amc_ap, "a");
|
|
s[1] = string_from_cstr(mm->amc_ap, "b");
|
|
make_pair(mm->amc_ap, s[0], s[1]);
|
|
s[3] = make_weak_and_pair(mm->eph_ap, s[0], s[1]);
|
|
s[1] = NULL;
|
|
asserts(s[3]->weak_pair.key == s[0], "key == s[0]");
|
|
die(mps_arena_collect(mm->arena), "mps_arena_collect");
|
|
asserts(s[3]->weak_pair.key == NULL, "key unreachable");
|
|
asserts(s[3]->weak_pair.value == NULL, "value unreachable");
|
|
}
|
|
|
|
static void test_unreachable_key(mmp mm, oop s[ROOT_COUNT])
|
|
{
|
|
comment("test_unreachable_key");
|
|
s[0] = string_from_cstr(mm->amc_ap, "a");
|
|
s[1] = string_from_cstr(mm->amc_ap, "b");
|
|
make_pair(mm->amc_ap, s[0], s[1]);
|
|
s[3] = make_weak_and_pair(mm->eph_ap, s[0], s[1]);
|
|
s[0] = NULL;
|
|
die(mps_arena_collect(mm->arena), "mps_arena_collect");
|
|
asserts(s[3]->weak_pair.key == NULL, "key unreachable");
|
|
asserts(s[3]->weak_pair.value == NULL, "value unreachable");
|
|
}
|
|
|
|
static void test_both_unreachable(mmp mm, oop s[ROOT_COUNT])
|
|
{
|
|
comment("test_both_unreachable");
|
|
s[0] = string_from_cstr(mm->amc_ap, "a");
|
|
s[1] = string_from_cstr(mm->amc_ap, "b");
|
|
make_pair(mm->amc_ap, s[0], s[1]);
|
|
s[3] = make_weak_and_pair(mm->eph_ap, s[0], s[1]);
|
|
s[0] = NULL;
|
|
s[1] = NULL;
|
|
die(mps_arena_collect(mm->arena), "mps_arena_collect");
|
|
asserts(s[3]->weak_pair.key == NULL, "key unreachable");
|
|
asserts(s[3]->weak_pair.value == NULL, "value unreachable");
|
|
}
|
|
|
|
static void test_both_reachable(mmp mm, oop s[ROOT_COUNT])
|
|
{
|
|
comment("test_both_reachable");
|
|
s[0] = string_from_cstr(mm->amc_ap, "a");
|
|
s[1] = string_from_cstr(mm->amc_ap, "b");
|
|
make_pair(mm->amc_ap, s[0], s[1]);
|
|
s[3] = make_weak_and_pair(mm->eph_ap, s[0], s[1]);
|
|
die(mps_arena_collect(mm->arena), "mps_arena_collect");
|
|
asserts(s[3]->weak_pair.key != NULL, "key reachable");
|
|
asserts(s[3]->weak_pair.value != NULL, "value reachable");
|
|
check_string(s[3]->weak_pair.key, "a");
|
|
check_string(s[3]->weak_pair.value, "b");
|
|
asserts(s[3]->weak_pair.key == s[0], "key == s[0]");
|
|
asserts(s[3]->weak_pair.value == s[1], "value == s[1]");
|
|
}
|
|
|
|
static void test(mmp mm, void* closure)
|
|
{
|
|
typedef void (*fun)(mmp, oop s[ROOT_COUNT]);
|
|
fun funs[] = { test_reachable_key,
|
|
test_unreachable_key,
|
|
test_both_unreachable,
|
|
test_both_reachable };
|
|
size_t i;
|
|
for (i = 0; i < sizeof funs / sizeof funs[0]; i++) {
|
|
memset(mm->roots, 0, sizeof mm->roots);
|
|
funs[i](mm, mm->roots);
|
|
}
|
|
}
|
|
|
|
int main(int argc, char* argv[])
|
|
{
|
|
run_eph_test(test, NULL);
|
|
pass();
|
|
return 0;
|
|
}
|