ARC中的数据结构以及寻址方式

iOS ARC中引用计数的实现
iOS weak 的实现
ARC中的数据结构以及寻址方式

一 、 isa中使用了联合体，通过结构体位段的方式存储，

• uintptr_t nonpointer ：1
  0 表示 raw isa，也就是没有结构体的部分，访问对象的 isa 会直接返回一个指向 cls 的指针，也就是在 iPhone 迁移到 64 位系统之前时 isa 的类型。1 表示当前 isa 不是指针，但是其中也有 cls 的信息，只是其中关于类的指针都是保存在 shiftcls 中。
• uintptr_t has_assoc : 1
  存储是否有关联对象
• uintptr_t has_cxx_dtor : 1;
  是否有c++析构函数
• uintptr_t shiftcls : 44;
  用来存储类指针，一共占用44位
• uintptr_t magic : 6;
  magic 的值为 0x3b 用于调试器判断当前对象是真的对象还是没有初始化的空间
• uintptr_t weakly_referenced : 1;
  标志是否有弱引用存储在SideTables中
• uintptr_t deallocating : 1;
  对象正在释放内存
• uintptr_t has_sidetable_rc : 1;
  是否有对于的引用计数存储在SideTables中
• uintptr_t extra_rc : 8;
  8位用来存储引用计数

二 、 SideTables

SideTables 是一个长度为64的hash表，以对象地址进行hash算法获取存储位置，内部存储类型为SideTable结构体，这里使用了分离锁，对每个SideTable对象单独加锁，降低锁的竞争程度。

三 、 SideTable---->RefcountMap

1. SideTable中RefcountMap存储了对象额外的引用计数，RefcountMap内部包含一个c++迭代器，利用std::pair<KeyT, ValueT>，将对象作为Key，引用计数信息作为Value打包存储，
2. 其中Value为size_t类型

#define SIDE_TABLE_WEAKLY_REFERENCED (1UL<<0)
#define SIDE_TABLE_DEALLOCATING      (1UL<<1)  // MSB-ward of weak bit
#define SIDE_TABLE_RC_ONE            (1UL<<2)  // MSB-ward of deallocating bit
#define SIDE_TABLE_RC_PINNED         (1UL<<(WORD_BITS-1))

#define SIDE_TABLE_RC_SHIFT 2
#define SIDE_TABLE_FLAG_MASK (SIDE_TABLE_RC_ONE-1)

• 其中用最后一位，存储SIDE_TABLE_WEAKLY_REFERENCED标识是否有弱引用，
• 倒数第二位，标志对象是否正在释放
• 第一位SIDE_TABLE_RC_PINNED 用来标识引用计数是否已经存满
• 其余所有位保存引用计数
  isa中extra_rc占用8位，最大值为1111 1111，代码中定义了 define RC_HALF (1ULL<<7)也就是RC_HALF = 1000 0000, 所以当extra_rc存储满时，在进行retain，会保存RC_HALF个引用计数到SideTables中，并将extra_rc设置为RC_HALF，两个RC_HALF相加正好等于 1111 1111 + 1(最大值加一)

四 、 SideTable---->weak_table_t

struct weak_table_t {
    weak_entry_t *weak_entries;     弱引用表
    size_t    num_entries;                 当前使用总数量
    uintptr_t mask;                            
    uintptr_t max_hash_displacement;
};

1. weak_table_t 中存储了弱引用表，weak_entries默认存储空间为64，当存储内容num_entries大于总容量的 3 / 4时 空间扩大一倍。
2. 既然是hash表，就要有hash算法来决定存储位置。一般来说会取hash值对数组容量模运算获取要存储的位置，而这里使用了 mask
   hash_pointer(new_entry->referent) & (weak_table->mask);
   mask = 总容量 - 1 而且每次扩张会进行翻倍
   64 0100 0000 63 0011 1111
   128 1000 0000 127 0111 1111
   利用mask与hash值按位与操作，0的位永远为0，1的为返回hash值本身，所以最大值为总容量-1，最小值为0，从而获取要存储的位置。
3. hash表使用了开放寻址法处理冲突，如果有冲突，则依次往下偏移，直到没有冲突位置，并且max_hash_displacement保存最大偏移，
   即比如在插入过程中有5次碰撞，那max_hash_displacement=5，如果下次插入新对象有10次碰撞，max_hash_displacement=10；作用就是在下次查找entry，根据计算得到的索引相继累加查找对象，如果累加次数大于max_hash_displacement就不继续检索了，直接返回nil；避免遍历整个数组去找对象，浪费性能；
4. weak_entry_t保存了一个对象所关联的所有弱引用对象，如果长度超过4，则使用一个hash表，并且查找方式类似于上面