Move WeakMap and WeakKeyMap code to weakmap.c

These classes don't belong in gc.c as they're not actually part of the
GC. This commit refactors the code by moving all the code into a
weakmap.c file.

1 files changed, 800 insertions, 0 deletions

diff --git a/weakmap.c b/weakmap.c
new file mode 100644
index 0000000000..6915b3c71d
--- /dev/null
+++ b/weakmap.c
@@ -0,0 +1,800 @@
+#include "internal.h"
+#include "internal/gc.h"
+#include "internal/hash.h"
+#include "internal/proc.h"
+#include "internal/sanitizers.h"
+#include "ruby/st.h"
+#include "ruby/st.h"
+
+struct weakmap {
+    st_table *obj2wmap;		/* obj -> [ref,...] */
+    st_table *wmap2obj;		/* ref -> obj */
+    VALUE final;
+};
+
+static void
+wmap_compact(void *ptr)
+{
+    struct weakmap *w = ptr;
+    if (w->wmap2obj) rb_gc_update_tbl_refs(w->wmap2obj);
+    if (w->obj2wmap) rb_gc_update_tbl_refs(w->obj2wmap);
+    w->final = rb_gc_location(w->final);
+}
+
+static void
+wmap_mark(void *ptr)
+{
+    struct weakmap *w = ptr;
+    rb_gc_mark_movable(w->final);
+}
+
+static int
+wmap_free_map(st_data_t key, st_data_t val, st_data_t arg)
+{
+    VALUE *ptr = (VALUE *)val;
+    ruby_sized_xfree(ptr, (ptr[0] + 1) * sizeof(VALUE));
+    return ST_CONTINUE;
+}
+
+static void
+wmap_free(void *ptr)
+{
+    struct weakmap *w = ptr;
+    st_foreach(w->obj2wmap, wmap_free_map, 0);
+    st_free_table(w->obj2wmap);
+    st_free_table(w->wmap2obj);
+    xfree(w);
+}
+
+static int
+wmap_memsize_map(st_data_t key, st_data_t val, st_data_t arg)
+{
+    VALUE *ptr = (VALUE *)val;
+    *(size_t *)arg += (ptr[0] + 1) * sizeof(VALUE);
+    return ST_CONTINUE;
+}
+
+static size_t
+wmap_memsize(const void *ptr)
+{
+    size_t size;
+    const struct weakmap *w = ptr;
+    size = sizeof(*w);
+    size += st_memsize(w->obj2wmap);
+    size += st_memsize(w->wmap2obj);
+    st_foreach(w->obj2wmap, wmap_memsize_map, (st_data_t)&size);
+    return size;
+}
+
+static const rb_data_type_t weakmap_type = {
+    "weakmap",
+    {
+        wmap_mark,
+        wmap_free,
+        wmap_memsize,
+        wmap_compact,
+    },
+    0, 0, RUBY_TYPED_FREE_IMMEDIATELY
+};
+
+static VALUE wmap_finalize(RB_BLOCK_CALL_FUNC_ARGLIST(objid, self));
+
+static VALUE
+wmap_allocate(VALUE klass)
+{
+    struct weakmap *w;
+    VALUE obj = TypedData_Make_Struct(klass, struct weakmap, &weakmap_type, w);
+    w->obj2wmap = rb_init_identtable();
+    w->wmap2obj = rb_init_identtable();
+    w->final = rb_func_lambda_new(wmap_finalize, obj, 1, 1);
+    return obj;
+}
+
+static int
+wmap_live_p(VALUE obj)
+{
+    if (SPECIAL_CONST_P(obj)) return TRUE;
+    /* If rb_gc_is_ptr_to_obj returns false, the page could be in the tomb heap
+     * or have already been freed. */
+    if (!rb_gc_is_ptr_to_obj((void *)obj)) return FALSE;
+
+    void *poisoned = asan_poisoned_object_p(obj);
+    asan_unpoison_object(obj, false);
+
+    enum ruby_value_type t = BUILTIN_TYPE(obj);
+    int ret = (!(t == T_NONE || t >= T_FIXNUM || t == T_ICLASS) &&
+                !rb_objspace_garbage_object_p(obj));
+
+    if (poisoned) {
+        asan_poison_object(obj);
+    }
+
+    return ret;
+}
+
+static int
+wmap_final_func(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
+{
+    VALUE wmap, *ptr, size, i, j;
+    if (!existing) return ST_STOP;
+    wmap = (VALUE)arg, ptr = (VALUE *)*value;
+    for (i = j = 1, size = ptr[0]; i <= size; ++i) {
+        if (ptr[i] != wmap) {
+            ptr[j++] = ptr[i];
+        }
+    }
+    if (j == 1) {
+        ruby_sized_xfree(ptr, i * sizeof(VALUE));
+        return ST_DELETE;
+    }
+    if (j < i) {
+        SIZED_REALLOC_N(ptr, VALUE, j + 1, i);
+        ptr[0] = j;
+        *value = (st_data_t)ptr;
+    }
+    return ST_CONTINUE;
+}
+
+/* :nodoc: */
+static VALUE
+wmap_finalize(RB_BLOCK_CALL_FUNC_ARGLIST(objid, self))
+{
+    st_data_t orig, wmap, data;
+    VALUE obj, *rids, i, size;
+    struct weakmap *w;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    /* Get reference from object id. */
+    if (UNDEF_P(obj = rb_gc_id2ref_obj_tbl(objid))) {
+        rb_bug("wmap_finalize: objid is not found.");
+    }
+
+    /* obj is original referenced object and/or weak reference. */
+    orig = (st_data_t)obj;
+    if (st_delete(w->obj2wmap, &orig, &data)) {
+        rids = (VALUE *)data;
+        size = *rids++;
+        for (i = 0; i < size; ++i) {
+            wmap = (st_data_t)rids[i];
+            st_delete(w->wmap2obj, &wmap, NULL);
+        }
+        ruby_sized_xfree((VALUE *)data, (size + 1) * sizeof(VALUE));
+    }
+
+    wmap = (st_data_t)obj;
+    if (st_delete(w->wmap2obj, &wmap, &orig)) {
+        wmap = (st_data_t)obj;
+        st_update(w->obj2wmap, orig, wmap_final_func, wmap);
+    }
+    return self;
+}
+
+static VALUE
+wmap_inspect_append(VALUE str, VALUE obj)
+{
+    if (SPECIAL_CONST_P(obj)) {
+        return rb_str_append(str, rb_inspect(obj));
+    }
+    else if (wmap_live_p(obj)) {
+        return rb_str_append(str, rb_any_to_s(obj));
+    }
+    else {
+        return rb_str_catf(str, "#<collected:%p>", (void*)obj);
+    }
+}
+
+static int
+wmap_inspect_i(st_data_t key, st_data_t val, st_data_t arg)
+{
+    VALUE str = (VALUE)arg;
+    VALUE k = (VALUE)key, v = (VALUE)val;
+
+    if (RSTRING_PTR(str)[0] == '#') {
+        rb_str_cat2(str, ", ");
+    }
+    else {
+        rb_str_cat2(str, ": ");
+        RSTRING_PTR(str)[0] = '#';
+    }
+    wmap_inspect_append(str, k);
+    rb_str_cat2(str, " => ");
+    wmap_inspect_append(str, v);
+
+    return ST_CONTINUE;
+}
+
+static VALUE
+wmap_inspect(VALUE self)
+{
+    VALUE c = rb_class_name(CLASS_OF(self));
+    struct weakmap *w;
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+
+    VALUE str = rb_sprintf("-<%"PRIsVALUE":%p", c, (void *)self);
+    if (w->wmap2obj) {
+        st_foreach(w->wmap2obj, wmap_inspect_i, (st_data_t)str);
+    }
+    RSTRING_PTR(str)[0] = '#';
+    rb_str_cat2(str, ">");
+    return str;
+}
+
+static inline bool
+wmap_live_entry_p(st_data_t key, st_data_t val)
+{
+    return wmap_live_p((VALUE)key) && wmap_live_p((VALUE)val);
+}
+
+static int
+wmap_each_i(st_data_t key, st_data_t val, st_data_t _)
+{
+    if (wmap_live_entry_p(key, val)) {
+        rb_yield_values(2, (VALUE)key, (VALUE)val);
+        return ST_CONTINUE;
+    }
+    else {
+        return ST_DELETE;
+    }
+}
+
+/* Iterates over keys and objects in a weakly referenced object */
+static VALUE
+wmap_each(VALUE self)
+{
+    struct weakmap *w;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    st_foreach(w->wmap2obj, wmap_each_i, (st_data_t)0);
+    return self;
+}
+
+static int
+wmap_each_key_i(st_data_t key, st_data_t val, st_data_t arg)
+{
+    if (wmap_live_entry_p(key, val)) {
+        rb_yield((VALUE)key);
+        return ST_CONTINUE;
+    }
+    else {
+        return ST_DELETE;
+    }
+}
+
+/* Iterates over keys and objects in a weakly referenced object */
+static VALUE
+wmap_each_key(VALUE self)
+{
+    struct weakmap *w;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    st_foreach(w->wmap2obj, wmap_each_key_i, (st_data_t)0);
+    return self;
+}
+
+static int
+wmap_each_value_i(st_data_t key, st_data_t val, st_data_t arg)
+{
+    if (wmap_live_entry_p(key, val)) {
+        rb_yield((VALUE)val);
+        return ST_CONTINUE;
+    }
+    else {
+        return ST_DELETE;
+    }
+}
+
+/* Iterates over keys and objects in a weakly referenced object */
+static VALUE
+wmap_each_value(VALUE self)
+{
+    struct weakmap *w;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    st_foreach(w->wmap2obj, wmap_each_value_i, (st_data_t)0);
+    return self;
+}
+
+static int
+wmap_keys_i(st_data_t key, st_data_t val, st_data_t arg)
+{
+    VALUE ary = (VALUE)arg;
+
+    if (wmap_live_entry_p(key, val)) {
+        rb_ary_push(ary, (VALUE)key);
+        return ST_CONTINUE;
+    }
+    else {
+        return ST_DELETE;
+    }
+}
+
+/* Iterates over keys and objects in a weakly referenced object */
+static VALUE
+wmap_keys(VALUE self)
+{
+    struct weakmap *w;
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+
+    VALUE ary = rb_ary_new();
+    st_foreach(w->wmap2obj, wmap_keys_i, (st_data_t)ary);
+    return ary;
+}
+
+static int
+wmap_values_i(st_data_t key, st_data_t val, st_data_t arg)
+{
+    VALUE ary = (VALUE)arg;
+
+    if (wmap_live_entry_p(key, val)) {
+        rb_ary_push(ary, (VALUE)val);
+        return ST_CONTINUE;
+    }
+    else {
+        return ST_DELETE;
+    }
+}
+
+/* Iterates over values and objects in a weakly referenced object */
+static VALUE
+wmap_values(VALUE self)
+{
+    struct weakmap *w;
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+
+    VALUE ary = rb_ary_new();
+    st_foreach(w->wmap2obj, wmap_values_i, (st_data_t)ary);
+    return ary;
+}
+
+static int
+wmap_aset_update(st_data_t *key, st_data_t *val, st_data_t arg, int existing)
+{
+    VALUE size, *ptr, *optr;
+    if (existing) {
+        size = (ptr = optr = (VALUE *)*val)[0];
+        ++size;
+        SIZED_REALLOC_N(ptr, VALUE, size + 1, size);
+    }
+    else {
+        optr = 0;
+        size = 1;
+        ptr = ruby_xmalloc(2 * sizeof(VALUE));
+    }
+    ptr[0] = size;
+    ptr[size] = (VALUE)arg;
+    if (ptr == optr) return ST_STOP;
+    *val = (st_data_t)ptr;
+    return ST_CONTINUE;
+}
+
+static VALUE
+nonspecial_obj_id(VALUE obj)
+{
+#if SIZEOF_LONG == SIZEOF_VOIDP
+    return (VALUE)((SIGNED_VALUE)(obj)|FIXNUM_FLAG);
+#elif SIZEOF_LONG_LONG == SIZEOF_VOIDP
+    return LL2NUM((SIGNED_VALUE)(obj) / 2);
+#else
+# error not supported
+#endif
+}
+
+/* Creates a weak reference from the given key to the given value */
+static VALUE
+wmap_aset(VALUE self, VALUE key, VALUE value)
+{
+    struct weakmap *w;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    if (FL_ABLE(value)) {
+        rb_define_finalizer_no_check(value, w->final);
+    }
+    if (FL_ABLE(key)) {
+        rb_define_finalizer_no_check(key, w->final);
+    }
+
+    st_update(w->obj2wmap, (st_data_t)value, wmap_aset_update, key);
+    st_insert(w->wmap2obj, (st_data_t)key, (st_data_t)value);
+    return nonspecial_obj_id(value);
+}
+
+/* Retrieves a weakly referenced object with the given key */
+static VALUE
+wmap_lookup(VALUE self, VALUE key)
+{
+    assert(wmap_live_p(key));
+
+    struct weakmap *w;
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+
+    st_data_t data;
+    if (!st_lookup(w->wmap2obj, (st_data_t)key, &data)) return Qundef;
+
+    VALUE obj = (VALUE)data;
+    if (!wmap_live_p(obj)) return Qundef;
+    return obj;
+}
+
+/* Retrieves a weakly referenced object with the given key */
+static VALUE
+wmap_aref(VALUE self, VALUE key)
+{
+    VALUE obj = wmap_lookup(self, key);
+    return !UNDEF_P(obj) ? obj : Qnil;
+}
+
+/* Returns +true+ if +key+ is registered */
+static VALUE
+wmap_has_key(VALUE self, VALUE key)
+{
+    return RBOOL(!UNDEF_P(wmap_lookup(self, key)));
+}
+
+/* Returns the number of referenced objects */
+static VALUE
+wmap_size(VALUE self)
+{
+    struct weakmap *w;
+    st_index_t n;
+
+    TypedData_Get_Struct(self, struct weakmap, &weakmap_type, w);
+    n = w->wmap2obj->num_entries;
+#if SIZEOF_ST_INDEX_T <= SIZEOF_LONG
+    return ULONG2NUM(n);
+#else
+    return ULL2NUM(n);
+#endif
+}
+
+typedef struct weakkeymap_entry {
+    VALUE obj;
+    st_index_t hash;
+} weakkeymap_entry_t;
+
+struct weakkeymap {
+    st_table *map;
+    st_table *obj2hash;
+    VALUE final;
+};
+
+static int
+weakkeymap_cmp_entry(st_data_t a, st_data_t b)
+{
+    struct weakkeymap_entry *entry_a = (struct weakkeymap_entry *)a;
+    struct weakkeymap_entry *entry_b = (struct weakkeymap_entry *)b;
+    if (entry_a == entry_b) {
+        return 0;
+    }
+    else {
+        return rb_any_cmp(entry_a->obj, entry_b->obj);
+    }
+}
+
+static st_index_t
+weakkeymap_hash_entry(st_data_t a)
+{
+    struct weakkeymap_entry *entry_a = (struct weakkeymap_entry *)a;
+    return entry_a->hash;
+}
+
+static const struct st_hash_type weakkeymap_hash = {
+    weakkeymap_cmp_entry,
+    weakkeymap_hash_entry,
+};
+
+static void
+wkmap_compact(void *ptr)
+{
+    struct weakkeymap *w = ptr;
+    if (w->map) rb_gc_update_tbl_refs(w->map);
+    w->final = rb_gc_location(w->final);
+}
+
+static void
+wkmap_mark(void *ptr)
+{
+    struct weakkeymap *w = ptr;
+    rb_mark_tbl_no_pin(w->map);
+    rb_gc_mark_movable(w->final);
+}
+
+static void
+wkmap_free(void *ptr)
+{
+    struct weakkeymap *w = ptr;
+    st_free_table(w->map);
+    st_free_table(w->obj2hash);
+    xfree(w);
+}
+
+static size_t
+wkmap_memsize(const void *ptr)
+{
+    const struct weakkeymap *w = ptr;
+    return sizeof(struct weakkeymap) + st_memsize(w->map) + st_memsize(w->obj2hash);
+}
+
+static const rb_data_type_t weakkeymap_type = {
+    "weakkeymap",
+    {
+        wkmap_mark,
+        wkmap_free,
+        wkmap_memsize,
+        wkmap_compact,
+    },
+    0, 0, RUBY_TYPED_FREE_IMMEDIATELY
+};
+
+static VALUE
+wkmap_finalize(RB_BLOCK_CALL_FUNC_ARGLIST(objid, self))
+{
+    struct weakkeymap *w;
+    VALUE key;
+
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+
+    /* Get reference from object id. */
+    if ((key = rb_gc_id2ref_obj_tbl(objid)) == Qundef) {
+        rb_bug("wkmap_finalize: objid is not found.");
+    }
+
+    st_index_t hash;
+    if (st_delete(w->obj2hash, (st_data_t *)key, &hash)) {
+        weakkeymap_entry_t lookup_entry = {key, hash};
+        weakkeymap_entry_t *deleted_entry = NULL;
+        if (st_get_key(w->map, (st_data_t)&lookup_entry, (st_data_t *)deleted_entry)) {
+            st_data_t deleted_value;
+            st_delete(w->map, (st_data_t *)deleted_entry, &deleted_value);
+            xfree(deleted_entry);
+        }
+    }
+
+    return self;
+}
+
+static VALUE
+wkmap_allocate(VALUE klass)
+{
+    struct weakkeymap *w;
+    VALUE obj = TypedData_Make_Struct(klass, struct weakkeymap, &weakkeymap_type, w);
+    w->map = st_init_table(&weakkeymap_hash);
+    w->obj2hash = rb_init_identtable();
+    w->final = rb_func_lambda_new(wkmap_finalize, obj, 1, 1);
+    return obj;
+}
+
+static st_index_t
+wkmap_lookup_hash(struct weakkeymap *w, VALUE key)
+{
+    st_index_t hash;
+    if (!st_lookup(w->obj2hash, (st_data_t)key, &hash)) {
+        hash = rb_any_hash(key);
+    }
+    return hash;
+}
+
+static weakkeymap_entry_t*
+wkmap_lookup_entry(struct weakkeymap *w, VALUE key, st_index_t hash)
+{
+    st_data_t data;
+    weakkeymap_entry_t lookup_entry = {key, hash};
+
+    if (st_get_key(w->map, (st_data_t)&lookup_entry, &data)) {
+        return (weakkeymap_entry_t *)data;
+    }
+
+    return NULL;
+}
+
+static VALUE
+wkmap_lookup(VALUE self, VALUE key)
+{
+    st_data_t data;
+    struct weakkeymap *w;
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+
+    st_index_t hash = rb_any_hash(key);
+    weakkeymap_entry_t lookup_entry = {key, hash};
+
+    if (st_lookup(w->map, (st_data_t)&lookup_entry, &data)) {
+        return (VALUE)data;
+    }
+    return Qundef;
+}
+
+/*
+ *  call-seq:
+ *    map[key] -> value
+ *
+ *  Returns the value associated with the given +key+ if found.
+ *
+ *  If +key+ is not found, returns +nil+.
+ */
+static VALUE
+wkmap_aref(VALUE self, VALUE key)
+{
+    VALUE obj = wkmap_lookup(self, key);
+    return obj != Qundef ? obj : Qnil;
+}
+
+/*
+ *  call-seq:
+ *    map[key] = value -> value
+ *
+ *  Associates the given +value+ with the given +key+; returns +value+.
+ *
+ *  The reference to +key+ is weak, so when there is no other reference
+ *  to +key+ it may be garbage collected.
+ *
+ *  If the given +key+ exists, replaces its value with the given +value+;
+ *  the ordering is not affected
+ */
+static VALUE
+wkmap_aset(VALUE self, VALUE key, VALUE value)
+{
+    struct weakkeymap *w;
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+
+    if (!(FL_ABLE(key) && !SYMBOL_P(key) && !RB_BIGNUM_TYPE_P(key))) {
+        rb_raise(rb_eArgError, "WeakKeyMap must be garbage collectable");
+    }
+
+    st_index_t hash = wkmap_lookup_hash(w, key);
+    weakkeymap_entry_t *key_entry = wkmap_lookup_entry(w, key, hash);
+
+    if (!key_entry) {
+        key_entry = ALLOC(weakkeymap_entry_t);
+        key_entry->obj = key;
+        key_entry->hash = hash;
+    }
+
+    if (!st_insert(w->map, (st_data_t)key_entry, (st_data_t)value)) {
+        st_insert(w->obj2hash, (st_data_t)key, (st_data_t)hash);
+        rb_define_finalizer_no_check(key, w->final);
+    }
+
+    return value;
+}
+
+/*
+ *  call-seq:
+ *    map.getkey(key) -> existing_key or nil
+ *
+ *  Returns the existing equal key if it exists, otherwise returns +nil+.
+ */
+static VALUE
+wkmap_getkey(VALUE self, VALUE key)
+{
+    struct weakkeymap *w;
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+
+    st_index_t hash = rb_any_hash(key);
+    weakkeymap_entry_t lookup_entry = {key, hash};
+
+    weakkeymap_entry_t *key_entry = NULL;
+    if (st_get_key(w->map, (st_data_t)&lookup_entry, (st_data_t *)&key_entry)) {
+        assert(key_entry != NULL);
+
+        VALUE obj = key_entry->obj;
+        if (wmap_live_p(obj)) {
+            return obj;
+        }
+    }
+    return Qnil;
+}
+
+/*
+ *  call-seq:
+ *    hash.key?(key) -> true or false
+ *
+ *  Returns +true+ if +key+ is a key in +self+, otherwise +false+.
+ */
+static VALUE
+wkmap_has_key(VALUE self, VALUE key)
+{
+    return RBOOL(wkmap_lookup(self, key) != Qundef);
+}
+
+/*
+ *  call-seq:
+ *    map.clear -> self
+ *
+ *  Removes all map entries; returns +self+.
+ */
+static VALUE
+wkmap_clear(VALUE self)
+{
+    struct weakkeymap *w;
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+    if (w->map) {
+        st_clear(w->map);
+    }
+    if (w->obj2hash) {
+        st_clear(w->obj2hash);
+    }
+    return self;
+}
+
+/*
+ *  call-seq:
+ *    map.inspect -> new_string
+ *
+ *  Returns a new \String containing informations about the map:
+
+ *    m = ObjectSpace::WeakKeyMap.new
+ *    m[key] = value
+ *    m.inspect # => "#<ObjectSpace::WeakKeyMap:0x00000001028dcba8 size=1>"
+ *
+ */
+static VALUE
+wkmap_inspect(VALUE self)
+{
+    struct weakkeymap *w;
+    TypedData_Get_Struct(self, struct weakkeymap, &weakkeymap_type, w);
+
+    st_index_t n = 0;
+    if (w->map) {
+        n = w->map->num_entries;
+    }
+
+#if SIZEOF_ST_INDEX_T <= SIZEOF_LONG
+    const char * format = "#<%"PRIsVALUE":%p size=%lu>";
+#else
+    const char * format = "#<%"PRIsVALUE":%p size=%llu>";
+#endif
+
+    VALUE str = rb_sprintf(format, rb_class_name(CLASS_OF(self)), (void *)self, n);
+    return str;
+}
+
+/*
+ *  Document-class: ObjectSpace::WeakMap
+ *
+ *  An ObjectSpace::WeakMap object holds references to
+ *  any objects, but those objects can get garbage collected.
+ *
+ *  This class is mostly used internally by WeakRef, please use
+ *  +lib/weakref.rb+ for the public interface.
+ */
+
+/*
+ *  Document-class: ObjectSpace::WeakKeyMap
+ *
+ *  An ObjectSpace::WeakKeyMap object holds references to
+ *  any objects, but objects uses as keys can be garbage collected.
+ *
+ *  Objects used as values can't be garbage collected until the key is.
+ */
+
+void
+Init_WeakMap(void)
+{
+    VALUE rb_mObjectSpace = rb_define_module("ObjectSpace");
+
+    VALUE rb_cWeakMap = rb_define_class_under(rb_mObjectSpace, "WeakMap", rb_cObject);
+    rb_define_alloc_func(rb_cWeakMap, wmap_allocate);
+    rb_define_method(rb_cWeakMap, "[]=", wmap_aset, 2);
+    rb_define_method(rb_cWeakMap, "[]", wmap_aref, 1);
+    rb_define_method(rb_cWeakMap, "include?", wmap_has_key, 1);
+    rb_define_method(rb_cWeakMap, "member?", wmap_has_key, 1);
+    rb_define_method(rb_cWeakMap, "key?", wmap_has_key, 1);
+    rb_define_method(rb_cWeakMap, "inspect", wmap_inspect, 0);
+    rb_define_method(rb_cWeakMap, "each", wmap_each, 0);
+    rb_define_method(rb_cWeakMap, "each_pair", wmap_each, 0);
+    rb_define_method(rb_cWeakMap, "each_key", wmap_each_key, 0);
+    rb_define_method(rb_cWeakMap, "each_value", wmap_each_value, 0);
+    rb_define_method(rb_cWeakMap, "keys", wmap_keys, 0);
+    rb_define_method(rb_cWeakMap, "values", wmap_values, 0);
+    rb_define_method(rb_cWeakMap, "size", wmap_size, 0);
+    rb_define_method(rb_cWeakMap, "length", wmap_size, 0);
+    rb_include_module(rb_cWeakMap, rb_mEnumerable);
+
+    VALUE rb_cWeakKeyMap = rb_define_class_under(rb_mObjectSpace, "WeakKeyMap", rb_cObject);
+    rb_define_alloc_func(rb_cWeakKeyMap, wkmap_allocate);
+    rb_define_method(rb_cWeakKeyMap, "[]=", wkmap_aset, 2);
+    rb_define_method(rb_cWeakKeyMap, "[]", wkmap_aref, 1);
+    rb_define_method(rb_cWeakKeyMap, "getkey", wkmap_getkey, 1);
+    rb_define_method(rb_cWeakKeyMap, "key?", wkmap_has_key, 1);
+    rb_define_method(rb_cWeakKeyMap, "clear", wkmap_clear, 0);
+    rb_define_method(rb_cWeakKeyMap, "inspect", wkmap_inspect, 0);
+}