// 创建一个 Tagged Pointer 对象
NSNumber *n1 = [NSNumber numberWithInt:1];
NSLog(@"n1 rc = %ld", CFGetRetainCount((__bridge CFTypeRef)(n1)));

union isa_t {
    isa_t() { }
    isa_t(uintptr_t value) : bits(value) { }

    Class cls;
    uintptr_t bits;

    struct {
#   define ISA_MASK        0x0000000ffffffff8ULL
#   define ISA_MAGIC_MASK  0x000003f000000001ULL
#   define ISA_MAGIC_VALUE 0x000001a000000001ULL
#   define ISA_BITFIELD                                                      \
      uintptr_t nonpointer        : 1;                                       \
      uintptr_t has_assoc         : 1;                                       \
      uintptr_t has_cxx_dtor      : 1;                                       \
      uintptr_t shiftcls          : 33; /*MACH_VM_MAX_ADDRESS 0x1000000000*/ \
      uintptr_t magic             : 6;                                       \
      uintptr_t weakly_referenced : 1;                                       \
      uintptr_t deallocating      : 1;                                       \
      uintptr_t has_sidetable_rc  : 1;                                       \
      uintptr_t extra_rc          : 19
#   define RC_ONE   (1ULL<<45)
#   define RC_HALF  (1ULL<<18)
    };
#endif
};

void foo(void) {
	NSObject *o1 = [[NSObject alloc] init];
	for (int i = 0; i < 500; i++) {
	    _objc_rootRetain(o1);
	}
}

ALWAYS_INLINE id 
objc_object::rootRetain(bool tryRetain, bool handleOverflow)
{
    if (isTaggedPointer()) return (id)this;

    bool sideTableLocked = false;
    bool transcribeToSideTable = false;

    isa_t oldisa;
    isa_t newisa;

    do {
    	 // 是否将引用计数转移到索引表中
        transcribeToSideTable = false;
        // LoadExclusive 的作用是让读取操作原子化
        oldisa = LoadExclusive(&isa.bits);
        newisa = oldisa;
        // if (slowpath) else ()，表示大概率执行 else 后面的语句，用来提高效率。
        // fastpath 则表示大概率执行 if 后面的语句
        if (slowpath(!newisa.nonpointer)) {
        	  // arm64 架构下，一般的对象 nonpointer 为YES，但也有特例，例如 block 的 nonpointer 为 False，即不使用 isa 保存额外信息
            ClearExclusive(&isa.bits);
            if (rawISA()->isMetaClass()) return (id)this;
            if (!tryRetain && sideTableLocked) sidetable_unlock();
            if (tryRetain) return sidetable_tryRetain() ? (id)this : nil;
            else return sidetable_retain();
        }
        // don't check newisa.fast_rr; we already called any RR overrides
        if (slowpath(tryRetain && newisa.deallocating)) {
            ClearExclusive(&isa.bits);
            if (!tryRetain && sideTableLocked) sidetable_unlock();
            return nil;
        }
        // 用来表示 isa 指针的值是否溢出。因为引用计数存储在指针的高位，当引用计数增加到一定程度，会超过最高位的数字，此时 carry 的值不等于 0，表示溢出
        uintptr_t carry;
        // addc() 是一个内置函数，作用是将 isa 里面的引用计数 + 1 后保存
        newisa.bits = addc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc++

        if (slowpath(carry)) {
            // newisa.extra_rc++ overflowed
            // 移除的话则需要对多余的引用计数保存到索引表中。
            // 刚开始进入的时候 handleOverflow == false
            if (!handleOverflow) {
                ClearExclusive(&isa.bits);
                return rootRetain_overflow(tryRetain);
            }
            // 加锁
            if (!tryRetain && !sideTableLocked) sidetable_lock();
            // 此时 isa 指针存储的引用计数应该是满的， extra_rc 的 19 位都是 1，将 extra_rc 赋值为原来的一半，也就是将 isa 的最高位赋值为 0，这样做的目的是下次引用计数增加的时候可以直接存储在 isa 中，而不需要调用索引表来存储。将 has_sidetable_rc 赋值为 1，标记有额外的引用计数存储在索引表中
            sideTableLocked = true;
            transcribeToSideTable = true;
            newisa.extra_rc = RC_HALF;
            newisa.has_sidetable_rc = true;
        }
       // StoreExclusive(), 如果&isa.bits和oldisa.bits相等，那么就把newisa.bits的值赋给&isa.bits，并且返回true。
    } while (slowpath(!StoreExclusive(&isa.bits, oldisa.bits, newisa.bits)));

    if (slowpath(transcribeToSideTable)) {
        // Copy the other half of the retain counts to the side table.
        // 如果溢出的话，则将 isa 存储的引用计数赋值为最大值的一半，即 RC_HALF，那么减少的一半则转移到索引表中
        sidetable_addExtraRC_nolock(RC_HALF);
    }
	
    if (slowpath(!tryRetain && sideTableLocked)) sidetable_unlock();
    return (id)this;
}

static objc::ExplicitInit<StripedMap<SideTable>> SideTablesMap;

static StripedMap<SideTable>& SideTables() {
    return SideTablesMap.get();
}

template <typename Type>
class ExplicitInit {
    alignas(Type) uint8_t _storage[sizeof(Type)];

public:
    template <typename... Ts>
    void init(Ts &&... Args) {
        new (_storage) Type(std::forward<Ts>(Args)...);
    }

    Type &get() {
        return *reinterpret_cast<Type *>(_storage);
    }
};

template<typename T>
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif

    struct PaddedT {
        T value alignas(CacheLineSize);
    };

    PaddedT array[StripeCount];

    static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
    }

 public:
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    // ...省略
}

struct SideTable {
    spinlock_t slock;
    RefcountMap refcnts;
    weak_table_t weak_table;

    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }
    // ...省略
};

typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,RefcountMapValuePurgeable> RefcountMap;

template <typename T>
class DisguisedPtr {
    uintptr_t value;

    static uintptr_t disguise(T* ptr) {
        return -(uintptr_t)ptr;
    }

    static T* undisguise(uintptr_t val) {
        return (T*)-val;
    }

 public:
    DisguisedPtr() { }
    DisguisedPtr(T* ptr) 
        : value(disguise(ptr)) { }
    DisguisedPtr(const DisguisedPtr<T>& ptr) 
        : value(ptr.value) { }

    DisguisedPtr<T>& operator = (T* rhs) {
        value = disguise(rhs);
        return *this;
    }
    DisguisedPtr<T>& operator = (const DisguisedPtr<T>& rhs) {
        value = rhs.value;
        return *this;
    }

    operator T* () const {
        return undisguise(value);
    }
    T* operator -> () const { 
        return undisguise(value);
    }
    T& operator * () const { 
        return *undisguise(value);
    }
    T& operator [] (size_t i) const {
        return undisguise(value)[i];
    }
};

struct RefcountMapValuePurgeable {
    static inline bool isPurgeable(size_t x) {
        return x == 0;
    }
};

template <typename KeyT, typename ValueT,
          typename ValueInfoT = DenseMapValueInfo<ValueT>,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>,
                                     KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT> {
  friend class DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;

  using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;

  BucketT *Buckets;
  unsigned NumEntries;
  unsigned NumTombstones;
  unsigned NumBuckets;
  
  public:
   explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
}

template<typename T>
struct DenseMapInfo<DisguisedPtr<T>> {
  static inline DisguisedPtr<T> getEmptyKey() {
    return DisguisedPtr<T>((T*)(uintptr_t)-1);
  }
  static inline DisguisedPtr<T> getTombstoneKey() {
    return DisguisedPtr<T>((T*)(uintptr_t)-2);
  }
  static unsigned getHashValue(const T *PtrVal) {
      return ptr_hash((uintptr_t)PtrVal);
  }
  static bool isEqual(const DisguisedPtr<T> &LHS, const DisguisedPtr<T> &RHS) {
      return LHS == RHS; 
  }
};

static inline uint32_t ptr_hash(uint64_t key)
{
    key ^= key >> 4;
    key *= 0x8a970be7488fda55;
    key ^= __builtin_bswap64(key);
    return (uint32_t)key;
}

template <typename KeyT, typename ValueT>
struct DenseMapPair : public std::pair<KeyT, ValueT> {
  DenseMapPair() {}

  DenseMapPair(const KeyT &Key, const ValueT &Value)
      : std::pair<KeyT, ValueT>(Key, Value) {}

  DenseMapPair(KeyT &&Key, ValueT &&Value)
      : std::pair<KeyT, ValueT>(std::move(Key), std::move(Value)) {}

  template <typename AltKeyT, typename AltValueT>
  DenseMapPair(AltKeyT &&AltKey, AltValueT &&AltValue,
               typename std::enable_if<
                   std::is_convertible<AltKeyT, KeyT>::value &&
                   std::is_convertible<AltValueT, ValueT>::value>::type * = 0)
      : std::pair<KeyT, ValueT>(std::forward<AltKeyT>(AltKey),
                                std::forward<AltValueT>(AltValue)) {}

  template <typename AltPairT>
  DenseMapPair(AltPairT &&AltPair,
               typename std::enable_if<std::is_convertible<
                   AltPairT, std::pair<KeyT, ValueT>>::value>::type * = 0)
      : std::pair<KeyT, ValueT>(std::forward<AltPairT>(AltPair)) {}

  KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
  const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
  ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
  const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
};

int a = 1;
int& b = a;
b = 10;

template<typename LookupKeyT>
  bool LookupBucketFor(const LookupKeyT &Val,
                       const BucketT *&FoundBucket) const {
    // 返回成员变量 Buckets
    const BucketT *BucketsPtr = getBuckets();
    // 返回成员变量 NumBuckets
    const unsigned NumBuckets = getNumBuckets();

    if (NumBuckets == 0) {
      FoundBucket = nullptr;
      return false;
    }
    
    // 保存在查找过程中碰到的墓碑
    const BucketT *FoundTombstone = nullptr;
    // DenseMapInfo 的内联函数 getEmptyKey 
    const KeyT EmptyKey = getEmptyKey();
    // DenseMapInfo 的内联函数 getTombstoneKey 
    const KeyT TombstoneKey = getTombstoneKey();
    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
           !KeyInfoT::isEqual(Val, TombstoneKey) &&
           "Empty/Tombstone value shouldn't be inserted into map!");

	 //DenseMapInfo 的静态函数 getHashValue 计算哈希值，并与 NumBuckets-1 进行与运算，得到对应 BucketT 实例的 index
    unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
    // 查找次数
    unsigned ProbeAmt = 1;
    while (true) {
      const BucketT *ThisBucket = BucketsPtr + BucketNo;
      // Found Val's bucket?  If so, return it.
      // 找到了对应的 BucketT 实例
      if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
        FoundBucket = ThisBucket;
        return true;
      }

      // If we found an empty bucket, the key doesn't exist in the set.
      // Insert it and return the default value.
      // 如果对应的 bucket 是空的。如果是第一次查找的话则在这个 bucket 里面插入 key 和 value(在InsertIntoBucket函数中执行)。如果不是第一次并且之前找到了墓碑，则使用墓碑bucket插入key和value
      if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
        // If we've already seen a tombstone while probing, fill it in instead
        // of the empty bucket we eventually probed to.
        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
        return false;
      }

      // If this is a tombstone, remember it.  If Val ends up not in the map, we
      // prefer to return it than something that would require more probing.
      // Ditto for zero values.
      // 如果找到一个墓碑，则使用 FoundTombstone  将这个墓碑记录下来
      if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
          !FoundTombstone)
        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
        // 如果 FoundTombstone 为空并且 对应的 bucket 的 second 是 0，则用FoundTombstone保存下这个bucket
      if (ValueInfoT::isPurgeable(ThisBucket->getSecond())  &&  !FoundTombstone)
        FoundTombstone = ThisBucket;

      // Otherwise, it's a hash collision or a tombstone, continue quadratic
      // probing.
      // 如果查找次数多余 NumBuckets ，则报错
      if (ProbeAmt > NumBuckets) {
        FatalCorruptHashTables(BucketsPtr, NumBuckets);
      }
      // 重新计算 BucketNo，重新查找
      BucketNo += ProbeAmt++;
      BucketNo &= (NumBuckets-1);
    }
  }

template <typename KeyArg, typename... ValueArgs>
  BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
                            ValueArgs &&... Values) {
    TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
	
	 // 保存 key 到 bucket 的成员变量 first 中
    TheBucket->getFirst() = std::forward<KeyArg>(Key);
    // 初始化 ValueT 的实例并保存到 bucket 的成员变量 second 中
    ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
    return TheBucket;
  }

  template <typename LookupKeyT>
  BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
                                BucketT *TheBucket) {
    // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
    // the buckets are empty (meaning that many are filled with tombstones),
    // grow the table.
    //
    // The later case is tricky.  For example, if we had one empty bucket with
    // tons of tombstones, failing lookups (e.g. for insertion) would have to
    // probe almost the entire table until it found the empty bucket.  If the
    // table completely filled with tombstones, no lookup would ever succeed,
    // causing infinite loops in lookup.
    unsigned NewNumEntries = getNumEntries() + 1;
    unsigned NumBuckets = getNumBuckets();
    // 当 buckets 数组已经使用了超过 3/4 或者 空bucket的数量小于 1/8，则增加 buckets 数组的长度。
    if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
      // 扩增原来的 NumBuckets，新的 buckets 长度为旧的两倍，长度至少为 4。新的 buckets 生成后将旧数组里面的数据转移过去，并且旧数组删除
      this->grow(NumBuckets * 2);
      // 因为重新生成了 buckets 数组，所以需要使用LookupBucketFor重新查找对应bucket，并用指针 TheBucket 指向
      LookupBucketFor(Lookup, TheBucket);
      NumBuckets = getNumBuckets();
    } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
                             NumBuckets/8)) {
      this->grow(NumBuckets);
      LookupBucketFor(Lookup, TheBucket);
    }
    ASSERT(TheBucket);

    // Only update the state after we've grown our bucket space appropriately
    // so that when growing buckets we have self-consistent entry count.
    // If we are writing over a tombstone or zero value, remember this.
    if (KeyInfoT::isEqual(TheBucket->getFirst(), getEmptyKey())) {
      // Replacing an empty bucket.
      // 使用空bucket，NumEntries + 1 
      incrementNumEntries();
    } else if (KeyInfoT::isEqual(TheBucket->getFirst(), getTombstoneKey())) {
      // Replacing a tombstone.
      // 使用墓碑 bucket，NumEntries + 1， NumTombstones - 1
      incrementNumEntries();
      decrementNumTombstones();
    } else {      
      // we should be purging a zero. No accounting changes.
      // 如果 second 等于 0，则析构 second
      ASSERT(ValueInfoT::isPurgeable(TheBucket->getSecond()));
      TheBucket->getSecond().~ValueT();
    }

    return TheBucket;
  }

uintptr_t carry;
size_t newRefcnt = 
    addc(oldRefcnt, delta_rc << SIDE_TABLE_RC_SHIFT, 0, &carry);
if (carry) {
    refcntStorage =
        SIDE_TABLE_RC_PINNED | (oldRefcnt & SIDE_TABLE_FLAG_MASK);
    return true;
}
else {
    refcntStorage = newRefcnt;
return false;
}

void aoo(void) {
    NSObject *o1 = [[NSObject alloc] init];
    for (int i = 0; i < 512; i++) {
        _objc_rootRetain(o1);
    }
    for (int i = 0; i < 129; i++) {
        if (i == 128) {
            int a = 1;
        }
        _objc_rootRelease(o1);
    }
}

T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    
static unsigned int indexForPointer(const void *p) {
    uintptr_t addr = reinterpret_cast<uintptr_t>(p);
    return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
} 

uintptr_t
objc_object::sidetable_retainCount()
{
    SideTable& table = SideTables()[this];

    size_t refcnt_result = 1;
    
    table.lock();
    RefcountMap::iterator it = table.refcnts.find(this);
    if (it != table.refcnts.end()) {
        // this is valid for SIDE_TABLE_RC_PINNED too
        refcnt_result += it->second >> SIDE_TABLE_RC_SHIFT;
    }
    table.unlock();
    return refcnt_result;
}

+ (id)new {
    return [callAlloc(self, false/*checkNil*/) init];
}
+ (id)alloc {
    return _objc_rootAlloc(self);
}

callAlloc()
class_createInstance()
_class_createInstanceFromZone
calloc()