returnType (^blockName)(parameterTypes) = ^returnType(parameters) {...};

@property (nonatomic, copy, nullability) returnType (^blockName)(parameterTypes);

- (void)someMethodThatTakesABlock:(returnType (^nullability)(parameterTypes))blockName;

[someObject someMethodThatTakesABlock:^returnType (parameters) {...}];

typedef returnType (^TypeName)(parameterTypes);
TypeName blockName = ^returnType(parameters) {...};

- (void)foo {
    int anInteger = 42;
    void (^testBlock)(void) = ^{
        NSLog(@"Integer is: %i", anInteger);
    };
    testBlock();
}

int __block anInteger = 42

typedef void(^BLK)(void);

- (void)foo
{
    static int staticInt = 5;
    int ret = 5;
    
    BLK globalBlock = ^{
        int a = staticInt;
    };
    BLK mallocBlock = ^{
        int a = ret;
    };

    NSLog(@"global = %@", globalBlock);
    NSLog(@"malloc = %@", mallocBlock);
    NSLog(@"stack = %@", ^{int a = ret;});
}

global = <__NSGlobalBlock__: 0x104bb22b0>
malloc = <__NSMallocBlock__: 0x281a21bf0>
stack  = <__NSStackBlock__:  0x16b8266d8>

- (void)foo
{
    static int staticInt = 5;
    NSObject *commonObject = [[NSObject alloc] init];
    __weak NSObject *weakObject = commonObject;
    __block NSObject *byrefObject = [[NSObject alloc] init];
    __block __weak NSObject *byrefWeakObject = commonObject;
    BLK blockObject = ^{
       NSObject *val = commonObject;
   };

    BLK malocBlock = ^{
        staticInt++;
        NSLog(@"%@", commonObject);
        NSLog(@"%@", byrefWeakObject);
        NSLog(@"%@", weakObject);
        NSLog(@"%@", byrefObject);
        NSLog(@"%@", byrefWeakObject);
        NSLog(@"%@", blockObject);
    };
    NSLog(@"malloc = %@", malocBlock);
}

static void __Block_byref_id_object_copy_131(void *dst, void *src) {
 _Block_object_assign((char*)dst + 40, *(void * *) ((char*)src + 40), 131);
}
static void __Block_byref_id_object_dispose_131(void *src) {
 _Block_object_dispose(*(void * *) ((char*)src + 40), 131);
}

struct __Block_byref_byrefObject_0 {
  void *__isa;
__Block_byref_byrefObject_0 *__forwarding;
 int __flags;
 int __size;
 void (*__Block_byref_id_object_copy)(void*, void*);
 void (*__Block_byref_id_object_dispose)(void*);
 NSObject *__strong byrefObject;
};
struct __Block_byref_byrefWeakObject_1 {
  void *__isa;
__Block_byref_byrefWeakObject_1 *__forwarding;
 int __flags;
 int __size;
 void (*__Block_byref_id_object_copy)(void*, void*);
 void (*__Block_byref_id_object_dispose)(void*);
 NSObject *__weak byrefWeakObject;
};

struct __TestObject__foo_block_impl_0 {
  struct __block_impl impl;
  struct __TestObject__foo_block_desc_0* Desc;
  NSObject *__strong commonObject;
  __TestObject__foo_block_impl_0(void *fp, struct __TestObject__foo_block_desc_0 *desc, NSObject *__strong _commonObject, int flags=0) : commonObject(_commonObject) {
    impl.isa = &_NSConcreteStackBlock;
    impl.Flags = flags;
    impl.FuncPtr = fp;
    Desc = desc;
  }
};
static void __TestObject__foo_block_func_0(struct __TestObject__foo_block_impl_0 *__cself) {
  NSObject *__strong commonObject = __cself->commonObject; // bound by copy

       NSObject *val = commonObject;
   }
static void __TestObject__foo_block_copy_0(struct __TestObject__foo_block_impl_0*dst, struct __TestObject__foo_block_impl_0*src) {_Block_object_assign((void*)&dst->commonObject, (void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);}

static void __TestObject__foo_block_dispose_0(struct __TestObject__foo_block_impl_0*src) {_Block_object_dispose((void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);}

static struct __TestObject__foo_block_desc_0 {
  size_t reserved;
  size_t Block_size;
  void (*copy)(struct __TestObject__foo_block_impl_0*, struct __TestObject__foo_block_impl_0*);
  void (*dispose)(struct __TestObject__foo_block_impl_0*);
} __TestObject__foo_block_desc_0_DATA = { 0, sizeof(struct __TestObject__foo_block_impl_0), __TestObject__foo_block_copy_0, __TestObject__foo_block_dispose_0};

struct __TestObject__foo_block_impl_1 {
  struct __block_impl impl;
  struct __TestObject__foo_block_desc_1* Desc;
  int *staticInt;
  NSObject *__strong commonObject;
  NSObject *__weak weakObject;
  __strong BLK blockObject;
  __Block_byref_byrefWeakObject_1 *byrefWeakObject; // by ref
  __Block_byref_byrefObject_0 *byrefObject; // by ref
  __TestObject__foo_block_impl_1(void *fp, struct __TestObject__foo_block_desc_1 *desc, int *_staticInt, NSObject *__strong _commonObject, NSObject *__weak _weakObject, __strong BLK _blockObject, __Block_byref_byrefWeakObject_1 *_byrefWeakObject, __Block_byref_byrefObject_0 *_byrefObject, int flags=0) : staticInt(_staticInt), commonObject(_commonObject), weakObject(_weakObject), blockObject(_blockObject), byrefWeakObject(_byrefWeakObject->__forwarding), byrefObject(_byrefObject->__forwarding) {
    impl.isa = &_NSConcreteStackBlock;
    impl.Flags = flags;
    impl.FuncPtr = fp;
    Desc = desc;
  }
};
static void __TestObject__foo_block_func_1(struct __TestObject__foo_block_impl_1 *__cself) {
  __Block_byref_byrefWeakObject_1 *byrefWeakObject = __cself->byrefWeakObject; // bound by ref
  __Block_byref_byrefObject_0 *byrefObject = __cself->byrefObject; // bound by ref
  int *staticInt = __cself->staticInt; // bound by copy
  NSObject *__strong commonObject = __cself->commonObject; // bound by copy
  NSObject *__weak weakObject = __cself->weakObject; // bound by copy
  __strong BLK blockObject = __cself->blockObject; // bound by copy

        (*staticInt)++;
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_0, commonObject);
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_1, (byrefWeakObject->__forwarding->byrefWeakObject));
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_2, weakObject);
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_3, (byrefObject->__forwarding->byrefObject));
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_4, (byrefWeakObject->__forwarding->byrefWeakObject));
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_5, blockObject);
    }
static void __TestObject__foo_block_copy_1(struct __TestObject__foo_block_impl_1*dst, struct __TestObject__foo_block_impl_1*src) {_Block_object_assign((void*)&dst->commonObject, (void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_assign((void*)&dst->byrefWeakObject, (void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_assign((void*)&dst->weakObject, (void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_assign((void*)&dst->byrefObject, (void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_assign((void*)&dst->blockObject, (void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);}

static void __TestObject__foo_block_dispose_1(struct __TestObject__foo_block_impl_1*src) {_Block_object_dispose((void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_dispose((void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_dispose((void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_dispose((void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_dispose((void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);}

static struct __TestObject__foo_block_desc_1 {
  size_t reserved;
  size_t Block_size;
  void (*copy)(struct __TestObject__foo_block_impl_1*, struct __TestObject__foo_block_impl_1*);
  void (*dispose)(struct __TestObject__foo_block_impl_1*);
} __TestObject__foo_block_desc_1_DATA = { 0, sizeof(struct __TestObject__foo_block_impl_1), __TestObject__foo_block_copy_1, __TestObject__foo_block_dispose_1};

static void _I_TestObject_foo(TestObject * self, SEL _cmd) {
    static int staticInt = 5;
    NSObject *commonObject = ((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("NSObject"), sel_registerName("alloc")), sel_registerName("init"));
    __attribute__((objc_ownership(weak))) NSObject *weakObject = commonObject;
    __attribute__((__blocks__(byref))) __Block_byref_byrefObject_0 byrefObject = {(void*)0,(__Block_byref_byrefObject_0 *)&byrefObject, 33554432, sizeof(__Block_byref_byrefObject_0), __Block_byref_id_object_copy_131, __Block_byref_id_object_dispose_131, ((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("NSObject"), sel_registerName("alloc")), sel_registerName("init"))};
    __attribute__((__blocks__(byref))) __attribute__((objc_ownership(weak))) __Block_byref_byrefWeakObject_1 byrefWeakObject = {(void*)0,(__Block_byref_byrefWeakObject_1 *)&byrefWeakObject, 33554432, sizeof(__Block_byref_byrefWeakObject_1), __Block_byref_id_object_copy_131, __Block_byref_id_object_dispose_131, commonObject};
    BLK blockObject = ((void (*)())&__TestObject__foo_block_impl_0((void *)__TestObject__foo_block_func_0, &__TestObject__foo_block_desc_0_DATA, commonObject, 570425344));

    BLK malocBlock = ((void (*)())&__TestObject__foo_block_impl_1((void *)__TestObject__foo_block_func_1, &__TestObject__foo_block_desc_1_DATA, &staticInt, commonObject, weakObject, blockObject, (__Block_byref_byrefWeakObject_1 *)&byrefWeakObject, (__Block_byref_byrefObject_0 *)&byrefObject, 570425344));
    NSLog((NSString *)&__NSConstantStringImpl__var_folders_h0_ybj03b8d0mj52n8dx82v2br40000gn_T_TestObject_1a9b07_mi_6, malocBlock);
}

#define BLOCK_DESCRIPTOR_1 1
struct Block_descriptor_1 {
    uintptr_t reserved;
    uintptr_t size;
};

#define BLOCK_DESCRIPTOR_2 1
struct Block_descriptor_2 {
    // requires BLOCK_HAS_COPY_DISPOSE
    void (*copy)(void *dst, const void *src);
    void (*dispose)(const void *);
};

#define BLOCK_DESCRIPTOR_3 1
struct Block_descriptor_3 {
    // requires BLOCK_HAS_SIGNATURE
    const char *signature;
    const char *layout;     // contents depend on BLOCK_HAS_EXTENDED_LAYOUT
};

struct Block_layout {
    void *isa;
    volatile int32_t flags; // contains ref count
    int32_t reserved; 
    void (*invoke)(void *, ...);
    struct Block_descriptor_1 *descriptor;
    // imported variables
};

struct SampleA {
    int a;
    int b;
    int c;
};

struct SampleB {
    int a;
    struct Part1 {
        int b;
    };
    struct Part2 {
        int c;
    };
};

struct __block_impl {
  void *isa;
  int Flags;
  int Reserved;
  void *FuncPtr;
};

struct __TestObject__foo_block_impl_1 {
  struct __block_impl impl;
  struct __TestObject__foo_block_desc_1* Desc;
  int *staticInt;
  NSObject *__strong commonObject;
  NSObject *__weak weakObject;
  __strong BLK blockObject;
  __Block_byref_byrefWeakObject_1 *byrefWeakObject; // by ref
  __Block_byref_byrefObject_0 *byrefObject; // by ref
  __TestObject__foo_block_impl_1(void *fp, struct __TestObject__foo_block_desc_1 *desc, int *_staticInt, NSObject *__strong _commonObject, NSObject *__weak _weakObject, __strong BLK _blockObject, __Block_byref_byrefWeakObject_1 *_byrefWeakObject, __Block_byref_byrefObject_0 *_byrefObject, int flags=0) : staticInt(_staticInt), commonObject(_commonObject), weakObject(_weakObject), blockObject(_blockObject), byrefWeakObject(_byrefWeakObject->__forwarding), byrefObject(_byrefObject->__forwarding) {
    impl.isa = &_NSConcreteStackBlock;
    impl.Flags = flags;
    impl.FuncPtr = fp;
    Desc = desc;
  }
};

int *staticInt;
NSObject *__strong commonObject;
NSObject *__weak weakObject;
__strong BLK blockObject;
__Block_byref_byrefWeakObject_1 *byrefWeakObject; // by ref
__Block_byref_byrefObject_0 *byrefObject; // by ref

struct Block_byref {
    void *isa;
    struct Block_byref *forwarding;
    volatile int32_t flags; // contains ref count
    uint32_t size;
};

struct Block_byref_2 {
    // requires BLOCK_BYREF_HAS_COPY_DISPOSE
    void (*byref_keep)(struct Block_byref *dst, struct Block_byref *src);
    void (*byref_destroy)(struct Block_byref *);
};

struct Block_byref_3 {
    // requires BLOCK_BYREF_LAYOUT_EXTENDED
    const char *layout;
};

struct __Block_byref_byrefObject_0 {
  void *__isa;
__Block_byref_byrefObject_0 *__forwarding;
 int __flags;
 int __size;
 void (*__Block_byref_id_object_copy)(void*, void*);
 void (*__Block_byref_id_object_dispose)(void*);
 NSObject *__strong byrefObject;
};

_TestObject__foo_block_impl_1(void *fp, struct __TestObject__foo_block_desc_1 *desc, int *_staticInt, NSObject *__strong _commonObject, NSObject *__weak _weakObject, __strong BLK _blockObject, __Block_byref_byrefWeakObject_1 *_byrefWeakObject, __Block_byref_byrefObject_0 *_byrefObject, int flags=0) : staticInt(_staticInt), commonObject(_commonObject), weakObject(_weakObject), blockObject(_blockObject), byrefWeakObject(_byrefWeakObject->__forwarding), byrefObject(_byrefObject->__forwarding) {
    impl.isa = &_NSConcreteStackBlock;
    impl.Flags = flags;
    impl.FuncPtr = fp;
    Desc = desc;
  }

static void __TestObject__foo_block_func_1(struct __TestObject__foo_block_impl_1 *__cself) {
  __Block_byref_byrefWeakObject_1 *byrefWeakObject = __cself->byrefWeakObject; // bound by ref
  __Block_byref_byrefObject_0 *byrefObject = __cself->byrefObject; // bound by ref
  int *staticInt = __cself->staticInt; // bound by copy
  NSObject *__strong commonObject = __cself->commonObject; // bound by copy
  NSObject *__weak weakObject = __cself->weakObject; // bound by copy
  __strong BLK blockObject = __cself->blockObject; // bound by copy

        (*staticInt)++;

       // 省略。。。
           }

static struct __TestObject__foo_block_desc_1 {
  size_t reserved;
  size_t Block_size;
  void (*copy)(struct __TestObject__foo_block_impl_1*, struct __TestObject__foo_block_impl_1*);
  void (*dispose)(struct __TestObject__foo_block_impl_1*);
} __TestObject__foo_block_desc_1_DATA = { 0, sizeof(struct __TestObject__foo_block_impl_1), __TestObject__foo_block_copy_1, __TestObject__foo_block_dispose_1};

static void __TestObject__foo_block_copy_1(struct __TestObject__foo_block_impl_1*dst, struct __TestObject__foo_block_impl_1*src) {_Block_object_assign((void*)&dst->commonObject, (void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_assign((void*)&dst->byrefWeakObject, (void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_assign((void*)&dst->weakObject, (void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_assign((void*)&dst->byrefObject, (void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_assign((void*)&dst->blockObject, (void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);}

static void __TestObject__foo_block_dispose_1(struct __TestObject__foo_block_impl_1*src) {_Block_object_dispose((void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_dispose((void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_dispose((void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);_Block_object_dispose((void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);_Block_object_dispose((void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);}

static void __Block_byref_id_object_copy_131(void *dst, void *src) {
 _Block_object_assign((char*)dst + 40, *(void * *) ((char*)src + 40), 131);
}
static void __Block_byref_id_object_dispose_131(void *src) {
 _Block_object_dispose(*(void * *) ((char*)src + 40), 131);
}

struct Block_byref {
    void *isa;
    struct Block_byref *forwarding;
    int flags; /* refcount; */
    int size;
    void (*byref_keep)(struct Block_byref *dst, struct Block_byref *src);
    void (*byref_destroy)(struct Block_byref *);
    /* long shared[0]; */
};

void *_Block_copy(const void *arg) {
    return _Block_copy_internal(arg, WANTS_ONE);
}

static void __TestObject__foo_block_copy_1(struct __TestObject__foo_block_impl_1*dst, struct __TestObject__foo_block_impl_1*src) 
{
_Block_object_assign((void*)&dst->commonObject, (void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);
_Block_object_assign((void*)&dst->byrefWeakObject, (void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);
_Block_object_assign((void*)&dst->weakObject, (void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);
_Block_object_assign((void*)&dst->byrefObject, (void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);
_Block_object_assign((void*)&dst->blockObject, (void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);
}

static void _Block_retain_object_default(const void *ptr) {
	(void)ptr;
}

static void _Block_assign_default(void *value, void **destptr) {
    *destptr = value;
}

struct Block_byref_2 *src2 = (struct Block_byref_2 *)(src+1);

static void _Block_assign_default(void *value, void **destptr) {
    *destptr = value;
}

static void _Block_assign_weak_default(const void *ptr, void *dest) {
    *(void **)dest = (void *)ptr;
}

_Block_call_dispose_helper(aBlock);
_Block_destructInstance(aBlock);
_Block_deallocator(aBlock);

static void _Block_call_dispose_helper(struct Block_layout *aBlock)
{
    struct Block_descriptor_2 *desc = _Block_descriptor_2(aBlock);
    if (!desc) return;

    (*desc->dispose)(aBlock);
}

static void __TestObject__foo_block_dispose_1(struct __TestObject__foo_block_impl_1*src) 
{
_Block_object_dispose((void*)src->byrefInt, 8/*BLOCK_FIELD_IS_BYREF*/);
_Block_object_dispose((void*)src->commonObject, 3/*BLOCK_FIELD_IS_OBJECT*/);
_Block_object_dispose((void*)src->byrefWeakObject, 8/*BLOCK_FIELD_IS_BYREF*/);
_Block_object_dispose((void*)src->weakObject, 3/*BLOCK_FIELD_IS_OBJECT*/);
_Block_object_dispose((void*)src->byrefObject, 8/*BLOCK_FIELD_IS_BYREF*/);
_Block_object_dispose((void*)src->blockObject, 7/*BLOCK_FIELD_IS_BLOCK*/);
}

static void _Block_release_object_default(const void *ptr) {
	(void)ptr;
}

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

    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }

    ~SideTable() {
        _objc_fatal("Do not delete SideTable.");
    }

    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // Address-ordered lock discipline for a pair of side tables.

    template<HaveOld, HaveNew>
    static void lockTwo(SideTable *lock1, SideTable *lock2);
    template<HaveOld, HaveNew>
    static void unlockTwo(SideTable *lock1, SideTable *lock2);
};

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];
    }

    // pointer arithmetic operators omitted 
    // because we don't currently use them anywhere
};

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

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; 
  }
};

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

  // FIXME: Switch to inheriting constructors when we drop support for older
  //        clang versions.
  // NOTE: This default constructor is declared with '{}' rather than
  //       '= default' to work around a separate bug in clang-3.8. This can
  //       also go when we switch to inheriting constructors.
  DenseMapPair() {}
}

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>;

  // Lift some types from the dependent base class into this class for
  // simplicity of referring to them.
  using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;

  BucketT *Buckets;
  unsigned NumEntries;
  unsigned NumTombstones;
  unsigned NumBuckets;

public:
  /// Create a DenseMap wth an optional \p InitialReserve that guarantee that
  /// this number of elements can be inserted in the map without grow()
  explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
}

friend class DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;

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

explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }

struct weak_table_t {
    weak_entry_t *weak_entries;
    size_t    num_entries;
    uintptr_t mask;
    uintptr_t max_hash_displacement;
};

struct weak_entry_t {
    DisguisedPtr<objc_object> referent;
    union {
        struct {
            weak_referrer_t *referrers;
            uintptr_t        out_of_line_ness : 2;
            uintptr_t        num_refs : PTR_MINUS_2;
            uintptr_t        mask;
            uintptr_t        max_hash_displacement;
        };
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }
    weak_entry_t& operator=(const weak_entry_t& other) {
        memcpy(this, &other, sizeof(other));
        return *this;
    }

    weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
        : referent(newReferent)
    {
        inline_referrers[0] = newReferrer;
        for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
            inline_referrers[i] = nil;
        }
    }
};

static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) {
    	 // 使用内部数组来保存弱引用者. 遍历内部数组, 如果有空位则用该空位保存弱引用者并返回
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }

		 // 如果执行到这里, 说明内部数组都被使用了. 所以需要扩容, 即创建一个外部数组来保存弱引用者
		 // 先初始化一个跟内部数组长度一样的数组, 并将内部数组的数据转移过去
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i];
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    ASSERT(entry->out_of_line());
    // 如果外部数组中有 3/4 的元素都被使用了, 则进行扩容
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        // 扩容的长度为原来的 2 倍, 最小值为 8.
        return grow_refs_and_insert(entry, new_referrer);
    }
    // 根据指针的哈希值来计算位置 index
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    while (entry->referrers[index] != nil) {
        // 发生了哈希碰撞, 则增加下标, 查看下一个位置是否为空
        hash_displacement++;
        index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
    }
    // 重新计算 entry 的最大哈希偏移量
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
    // 将新的弱引用者保存到弱引用条目中
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    // num_refs + 1
    entry->num_refs++;
}

template <HaveOld haveOld, HaveNew haveNew,
          CrashIfDeallocating crashIfDeallocating>
static id 
storeWeak(id *location, objc_object *newObj)
{
    ASSERT(haveOld  ||  haveNew);
    if (!haveNew) ASSERT(newObj == nil);

    Class previouslyInitializedClass = nil;
    id oldObj;
    SideTable *oldTable;
    SideTable *newTable;

    // Acquire locks for old and new values.
    // Order by lock address to prevent lock ordering problems. 
    // Retry if the old value changes underneath us.
 retry:
    if (haveOld) {
        oldObj = *location;
        oldTable = &SideTables()[oldObj];
    } else {
        oldTable = nil;
    }
    if (haveNew) {
        newTable = &SideTables()[newObj];
    } else {
        newTable = nil;
    }

    SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);

    if (haveOld  &&  *location != oldObj) {
        SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
        goto retry;
    }

    // Prevent a deadlock between the weak reference machinery
    // and the +initialize machinery by ensuring that no 
    // weakly-referenced object has an un-+initialized isa.
    if (haveNew  &&  newObj) {
        Class cls = newObj->getIsa();
        if (cls != previouslyInitializedClass  &&  
            !((objc_class *)cls)->isInitialized()) 
        {
            SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
            class_initialize(cls, (id)newObj);

            // If this class is finished with +initialize then we're good.
            // If this class is still running +initialize on this thread 
            // (i.e. +initialize called storeWeak on an instance of itself)
            // then we may proceed but it will appear initializing and 
            // not yet initialized to the check above.
            // Instead set previouslyInitializedClass to recognize it on retry.
            previouslyInitializedClass = cls;

            goto retry;
        }
    }

    // Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
    }

    // Assign new value, if any.
    if (haveNew) {
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected

        // Set is-weakly-referenced bit in refcount table.
        if (newObj  &&  !newObj->isTaggedPointer()) {
            newObj->setWeaklyReferenced_nolock();
        }

        // Do not set *location anywhere else. That would introduce a race.
        *location = (id)newObj;
    }
    else {
        // No new value. The storage is not changed.
    }
    
    SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);

    return (id)newObj;
}

static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
    if (! entry->out_of_line()) {
        //使用内部数组保存弱引用者, 此时遍历该数组, 找到对应的弱引用者, 如果找到的话则将其从数组中移除
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == old_referrer) {
                entry->inline_referrers[i] = nil;
                return;
            }
        }
        _objc_inform("Attempted to unregister unknown __weak variable "
                     "at %p. This is probably incorrect use of "
                     "objc_storeWeak() and objc_loadWeak(). "
                     "Break on objc_weak_error to debug.\n", 
                     old_referrer);
        objc_weak_error();
        return;
    }
    // 此时使用外部数组来保存弱引用者
    // 根据弱引用者的哈希值来得到对应元素的 index 
    size_t begin = w_hash_pointer(old_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    while (entry->referrers[index] != old_referrer) {
        // 如果发生了哈希碰撞, 则偏移+1 往下继续查找该弱引用者.当偏移量超过最大偏移量时程序崩溃
        index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
        hash_displacement++;
        if (hash_displacement > entry->max_hash_displacement) {
            _objc_inform("Attempted to unregister unknown __weak variable "
                         "at %p. This is probably incorrect use of "
                         "objc_storeWeak() and objc_loadWeak(). "
                         "Break on objc_weak_error to debug.\n", 
                         old_referrer);
            objc_weak_error();
            return;
        }
    }
    // 找到对应弱引用则将其从外部数组中移除
    entry->referrers[index] = nil;
    entry->num_refs--;
}

static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
{
    // remove entry
    // 如果使用的外部数组, 则将外部数组销毁. 如果使用内部数组, 则会在销毁条目时将内部数组也销毁
    if (entry->out_of_line()) free(entry->referrers);
    // 销毁弱引用条目
    bzero(entry, sizeof(*entry));

    weak_table->num_entries--;
	 // 当条目数量超过 1024, 并且使用了不到 1/16, 则将条目数量缩小为原来的 1/8
    weak_compact_maybe(weak_table);
}

void 
weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 
{
    // referent 表示引用对象, 即这里要被销毁的对象
    objc_object *referent = (objc_object *)referent_id;
    // 根据引用对象找到对应的弱引用条目
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) {
        /// XXX shouldn't happen, but does with mismatched CF/objc
        //printf("XXX no entry for clear deallocating %p\n", referent);
        return;
    }

    // zero out references
    // 数组指针
    weak_referrer_t *referrers;
    // 数组长度
    size_t count;
    
    if (entry->out_of_line()) {
        referrers = entry->referrers;
        count = TABLE_SIZE(entry);
    } 
    else {
        referrers = entry->inline_referrers;
        count = WEAK_INLINE_COUNT;
    }
    
    for (size_t i = 0; i < count; ++i) {
        objc_object **referrer = referrers[i];
        if (referrer) {
            // 将弱引用者置为 nil
            if (*referrer == referent) {
                *referrer = nil;
            }
            else if (*referrer) {
                _objc_inform("__weak variable at %p holds %p instead of %p. "
                             "This is probably incorrect use of "
                             "objc_storeWeak() and objc_loadWeak(). "
                             "Break on objc_weak_error to debug.\n", 
                             referrer, (void*)*referrer, (void*)referent);
                objc_weak_error();
            }
        }
    }
    // 将所有弱引用者置为 nil 后, 将该条目从弱引用表中删除
    weak_entry_remove(weak_table, entry);
}

// 创建一个 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);
    }
}

NSNumber *a = [NSNumber numberWithInt:1];

#if OBJC_MSB_TAGGED_POINTERS
#   define _OBJC_TAG_MASK (1UL<<63)
#   define _OBJC_TAG_INDEX_SHIFT 60
#else
#   define _OBJC_TAG_MASK 1UL
#   define _OBJC_TAG_INDEX_SHIFT 1
#endif

extern "C" { 
    extern Class objc_debug_taggedpointer_classes[_OBJC_TAG_SLOT_COUNT];
    extern Class objc_debug_taggedpointer_ext_classes[_OBJC_TAG_EXT_SLOT_COUNT];
}

enum
{
    // 60-bit payloads
    OBJC_TAG_NSAtom            = 0, 
    OBJC_TAG_1                 = 1, 
    OBJC_TAG_NSString          = 2, 
    OBJC_TAG_NSNumber          = 3, 
    OBJC_TAG_NSIndexPath       = 4, 
    OBJC_TAG_NSManagedObjectID = 5, 
    OBJC_TAG_NSDate            = 6,
}

enum
{
	// ...
	// 52-bit payloads
    OBJC_TAG_Photos_1          = 8,
    OBJC_TAG_Photos_2          = 9,
    OBJC_TAG_Photos_3          = 10,
    OBJC_TAG_Photos_4          = 11,
    OBJC_TAG_XPC_1             = 12,
    OBJC_TAG_XPC_2             = 13,
    OBJC_TAG_XPC_3             = 14,
    OBJC_TAG_XPC_4             = 15,
    OBJC_TAG_NSColor           = 16,
    OBJC_TAG_UIColor           = 17,
    OBJC_TAG_CGColor           = 18,
    OBJC_TAG_NSIndexSet        = 19,
    // ...
}

- (void)boo
{
    NSNumber *a = [NSNumber numberWithInt:1];
    NSNumber *b = [NSNumber numberWithInt:2];
    NSNumber *c = [NSNumber numberWithInt:16];
    
    NSLog(@"pointer a is %lx", a);
    NSLog(@"pointer b is %lx", b);
    NSLog(@"pointer c is %lx", c);
    NSLog(@"pointer d is %lx", d);
}

pointer a is ef59c3d36981ed4b
pointer b is ef59c3d36981ed7b
pointer c is ef59c3d36981ec5b

static inline void * _Nonnull
_objc_encodeTaggedPointer(uintptr_t ptr)
{
    return (void *)(objc_debug_taggedpointer_obfuscator ^ ptr);
}

extern uintptr_t objc_debug_taggedpointer_obfuscator;

- (void)foo
{
    NSNumber *a = [NSNumber numberWithInt:1];
    NSNumber *b = [NSNumber numberWithInt:2];
    NSNumber *c = [NSNumber numberWithInt:16];

    NSLog(@"pointer a real value is %lx", ((uintptr_t)a ^ objc_debug_taggedpointer_obfuscator));
    NSLog(@"pointer b real value is %lx", ((uintptr_t)b ^ objc_debug_taggedpointer_obfuscator));
    NSLog(@"pointer c real value is %lx", ((uintptr_t)c ^ objc_debug_taggedpointer_obfuscator));
}

pointer a real value is b000000000000012
pointer b real value is b000000000000022
pointer c real value is b000000000000102

- (void)foo
{
    NSNumber *d = [NSNumber numberWithLongLong:-0x7FFFFFFFFFFFFF];
    NSLog(@"pointer a real value is %lx", ((uintptr_t)d ^ objc_debug_taggedpointer_obfuscator));
}

pointer d real value is b800000000000013

NSNumber *a = [NSNumber numberWithInt:1];
NSNumber *b = [NSNumber numberWithShort:2];
NSNumber *c = [NSNumber numberWithFloat:1.];
NSNumber *d = [NSNumber numberWithLongLong:-0x7FFFFFFFFFFFFF];

NSLog(@"pointer a real value is %lx", ((uintptr_t)a ^ objc_debug_taggedpointer_obfuscator));
NSLog(@"pointer b real value is %lx", ((uintptr_t)b ^ objc_debug_taggedpointer_obfuscator));
NSLog(@"pointer c real value is %lx", ((uintptr_t)c ^ objc_debug_taggedpointer_obfuscator));
NSLog(@"pointer d real value is %lx", ((uintptr_t)d ^ objc_debug_taggedpointer_obfuscator));

pointer a real value is b000000000000012
pointer b real value is b000000000000021
pointer c real value is b000000000000014
pointer d real value is b800000000000013

struct load_command {
	uint32_t cmd;		/* 载入命令类型 */
	uint32_t cmdsize;	/* total size of command in bytes */
};

struct section_64 { /* for 64-bit architectures */
	char		sectname[16];	/* name of this section */
	char		segname[16];	/* segment this section goes in */
	uint64_t	addr;		/* memory address of this section */
	uint64_t	size;		/* size in bytes of this section */
	uint32_t	offset;		/* file offset of this section */
	uint32_t	align;		/* section alignment (power of 2) */
	uint32_t	reloff;		/* file offset of relocation entries */
	uint32_t	nreloc;		/* number of relocation entries */
	uint32_t	flags;		/* flags (section type and attributes)*/
	uint32_t	reserved1;	/* reserved (for offset or index) */
	uint32_t	reserved2;	/* reserved (for count or sizeof) */
	uint32_t	reserved3;	/* reserved */
};

void _objc_init(void)
{
    // 省略...
    _dyld_objc_notify_register(&map_images, load_images, unmap_image);
}

@interface Father : NSObject
@property (nonatomic, copy) NSString *name;
@end

@implementation ViewController
- (void)foo {
    Father *father1 = [Father new];
    father1.name = @"001";
    id father2 = [Father new];
}
@end

(lldb) x/8xg father1
0x6000000128f0: 0x000000010be34050(Class) 0x000000010bdcc058(name)                            
0x600000012900: 0x00006000000128a0 0x0000000100000002
0x600000012910: 0x000000010f8f8e58 0x0000000000000000
0x600000012920: 0x0000000000000000 0x0000000000000000

(lldb) x/8xg father2
0x600000012490: 0x000000010be34050(Class) 0x0000000000000000(name)
0x6000000124a0: 0xbadd2dcdc19dbead 0x00006000000124f0
0x6000000124b0: 0x0000000000000000 0x0000000000000000
0x6000000124c0: 0x00007f8ae3c140c0 0x00006080000092b0

(lldb) po (Class)0x000000010be34050
Father

(lldb) po (id)0x000000010bdcc058
001