IOS – SideTable

Understand hashTables

A hash table is also a hash table

It’s the same as binary trees, linked lists, things like that. It is a data structure designed to hold data

What basic knowledge is needed

• Pointers and arrays
• The list
• Modular arithmetic

Hash table construction method

Why is it called a Hash table, because it has a Hash function

Key words: X -> F (x) -> subscript

The key of a hash table is an array, which obtains a hash function f(key) based on the key, then obtains the index, and then obtains the value in the index

The hash function

Hash function is based on the keyword design, there are many kinds of functions, the main principle is based on the size of the array modular operation.

(Keyword) % (array size)

Example: 20048157%7 (results in 0-16)

The size of an array is generally designed to be a bit prime because it needs to be evenly spread

What about conflicts?

Linked list solution

Add a next pointer when writing a structure (like a linked list)

Data | | next – > data next

In case of conflict, write the data to the next location

eg:

Array size 7

Hash function: subscript = keyword mod 7

Open address (this piece needs to find by yourself)

Instead of using the next pointer, open all other subscripts to the public

Methods of opening addresses:

• Linear detection method
• Square detection
• Double hash

Why do you design hash tables

Because hash table lookup is fast, it is faster than searching binary trees

Disadvantages of hash tables

The more full the table, the more conflicts and the worse the performance.

SideTable

SideTable is just a hash table

The SideTable serves as a container for memory management information and stores multiple memory management information in the system. The system binds the hash value of the instance object to the SideTable.

An instance object corresponds to a SideTable, and a SideTable can be shared by multiple instance objects

Source structure

struct SideTable {
    /** spin lock */
    spinlock_t slock;
    // Reference count
    RefcountMap refcnts;
    // Weak reference table, hash table
    weak_table_t weak_table;

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

    ~SideTable() {
      // Can't delete SideTable
        _objc_fatal("Do not delete SideTable.");
    }

    / / lock
    void lock(a) { slock.lock(a); }void unlock(a) { slock.unlock(a); }// Reset the lock
    void forceReset(a) { 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);
};

// Returns a SideTable pointer with memory aligned
alignas(StripedMap<SideTable>) static uint8_t 
    SideTableBuf[sizeof(StripedMap<SideTable>)];

// Initialize SideTable
static void SideTableInit(a) {
    new (SideTableBuf) StripedMap<SideTable>();
}


// Get the SideTable array
static StripedMap<SideTable>& SideTables(a) {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}
Copy the code

Libc calls SideTable before C++ initializes the object and does not use a global pointer. Therefore, this method is used for initialization.

SideTables is a pointer to an instance of the StripedMap template class initialized with the SideTable structure. StripedMap is a class implemented using a split lock, with an array of internal members indexed by a hash algorithm. Its algorithm is as follows:

enum { StripeCount = 8 };

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

SideTable hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash