HR's Blog

Swimming 🏊 in the sea🌊of code!

0%

Weak 4.扩容和缩容的调取时机

Posted on Edited on In Disqus:

.

扩容和缩容的调取时机

添加和删除弱应用的指针是通过weak_register_no_lock和weak_unregister_no_lock来实现的。

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
id weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, bool crashIfDeallocating)
{
    objc_object *referent = (objc_object *)referent_id;
    objc_object **referrer = (objc_object **)referrer_id;
    
    ...
    
       weak_entry_t *entry;
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        //添加到之前的weak_entry_t表
        append_referrer(entry, referrer);
    }
    else {
        
        weak_entry_t new_entry(referent, referrer);
        //确保容量，不够的话就扩容
        weak_grow_maybe(weak_table);
        weak_entry_insert(weak_table, &new_entry);
    }
    return referent_id;
}

扩容

初始容量为64，当容量达到3/4时对数组进行扩容，每次扩容为原来的2倍。weak_resize(weak_table, old_size ? old_size*2 : 64);。
调用weak_resize重新对元素进行Hash值计算。

1
2
3
4
5
6
7
8
9
10
#pragma mark - 扩容操作
// Grow the given zone's table of weak references if it is full.
static void weak_grow_maybe(weak_table_t *weak_table) {
    size_t old_size = TABLE_SIZE(weak_table);
    
    // Grow if at least 3/4 full.
    if (weak_table->num_entries >= old_size * 3 / 4) {
        weak_resize(weak_table, old_size ? old_size*2 : 64);
    }
}

缩容

缩容规则当表大于1024但是只放了16分之一的数据的时候，就会缩容，缩小到原来的八分之一，调用weak_resize重新对元素进行Hash值计算。

1
2
3
4
5
6
7
8
9
10
11
#pragma mark - 缩容操作
// Shrink the table if it is mostly empty.
static void weak_compact_maybe(weak_table_t *weak_table) {
    size_t old_size = TABLE_SIZE(weak_table);
    
    // Shrink if larger than 1024 buckets and at most 1/16 full.
    if (old_size >= 1024  && old_size / 16 >= weak_table->num_entries) {
        weak_resize(weak_table, old_size / 8);
        // leaves new table no more than 1/2 full
    }
}

weak_resize

weak_resize传入weak_table和一个新的尺寸，根据传入的尺寸重新生成新的new_entries，遍历之前的entries，然后把找到的对象通过weak_entry_insert函数插入到新的weak_table_t（此时的weak_table_t已经扩容了），通过weak_entry_insert插入后，元素的位置也会改变，因为容量改变以后hash index的值都会重新计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void weak_resize(weak_table_t *weak_table, size_t new_size) {
    size_t old_size = TABLE_SIZE(weak_table);
    
    weak_entry_t *old_entries = weak_table->weak_entries;
    weak_entry_t *new_entries = (weak_entry_t *)calloc(new_size, sizeof(weak_entry_t));
    
    weak_table->mask = new_size - 1;
    weak_table->weak_entries = new_entries;
    weak_table->max_hash_displacement = 0;
    weak_table->num_entries = 0;  // restored by weak_entry_insert below
    
    if (old_entries) {
        weak_entry_t *entry;
        weak_entry_t *end = old_entries + old_size;
        for (entry = old_entries; entry < end; entry++) {
            if (entry->referent) {
                weak_entry_insert(weak_table, entry);
            }
        }
        free(old_entries);
    }
}