redis源码解析（九）字典结构体函数介绍之四

约定不等于承诺〃 2022-04-13 06:30 148阅读 0赞

### 1. 简介 ###

本文完成字典结构体剩余函数源码解析。

### 2. 源码解析 ###

具体源码解析如下：

/* 反转比特位 * Function to reverse bits. Algorithm from: * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
    static unsigned long rev(unsigned long v) { 
        unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
        unsigned long mask = ~0;
        while ((s >>= 1) > 0) { 
            mask ^= (mask << s);
            v = ((v >> s) & mask) | ((v << s) & ~mask);
        }
        return v;
    }
    
    /* 高级字典迭代器 * dictScan() is used to iterate over the elements of a dictionary. * * Iterating works the following way: * * 1) Initially you call the function using a cursor (v) value of 0. * 2) The function performs one step of the iteration, and returns the * new cursor value you must use in the next call. * 3) When the returned cursor is 0, the iteration is complete. * * The function guarantees all elements present in the * dictionary get returned between the start and end of the iteration. * However it is possible some elements get returned multiple times. * * For every element returned, the callback argument 'fn' is * called with 'privdata' as first argument and the dictionary entry * 'de' as second argument. * * HOW IT WORKS. * * The iteration algorithm was designed by Pieter Noordhuis. * The main idea is to increment a cursor starting from the higher order * bits. That is, instead of incrementing the cursor normally, the bits * of the cursor are reversed, then the cursor is incremented, and finally * the bits are reversed again. * * This strategy is needed because the hash table may be resized between * iteration calls. * * dict.c hash tables are always power of two in size, and they * use chaining, so the position of an element in a given table is given * by computing the bitwise AND between Hash(key) and SIZE-1 * (where SIZE-1 is always the mask that is equivalent to taking the rest * of the division between the Hash of the key and SIZE). * * For example if the current hash table size is 16, the mask is * (in binary) 1111. The position of a key in the hash table will always be * the last four bits of the hash output, and so forth. * * WHAT HAPPENS IF THE TABLE CHANGES IN SIZE? * * If the hash table grows, elements can go anywhere in one multiple of * the old bucket: for example let's say we already iterated with * a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16). * * If the hash table will be resized to 64 elements, then the new mask will * be 111111. The new buckets you obtain by substituting in ??1100 * with either 0 or 1 can be targeted only by keys we already visited * when scanning the bucket 1100 in the smaller hash table. * * By iterating the higher bits first, because of the inverted counter, the * cursor does not need to restart if the table size gets bigger. It will * continue iterating using cursors without '1100' at the end, and also * without any other combination of the final 4 bits already explored. * * Similarly when the table size shrinks over time, for example going from * 16 to 8, if a combination of the lower three bits (the mask for size 8 * is 111) were already completely explored, it would not be visited again * because we are sure we tried, for example, both 0111 and 1111 (all the * variations of the higher bit) so we don't need to test it again. * * WAIT... YOU HAVE *TWO* TABLES DURING REHASHING! * * Yes, this is true, but we always iterate the smaller table first, then * we test all the expansions of the current cursor into the larger * table. For example if the current cursor is 101 and we also have a * larger table of size 16, we also test (0)101 and (1)101 inside the larger * table. This reduces the problem back to having only one table, where * the larger one, if it exists, is just an expansion of the smaller one. * * LIMITATIONS * * This iterator is completely stateless, and this is a huge advantage, * including no additional memory used. * * The disadvantages resulting from this design are: * * 1) It is possible we return elements more than once. However this is usually * easy to deal with in the application level. * 2) The iterator must return multiple elements per call, as it needs to always * return all the keys chained in a given bucket, and all the expansions, so * we are sure we don't miss keys moving during rehashing. * 3) The reverse cursor is somewhat hard to understand at first, but this * comment is supposed to help. */
    unsigned long dictScan(dict *d,
                           unsigned long v,
                           dictScanFunction *fn,
                           dictScanBucketFunction *bucketfn,
                           void *privdata)
    { 
        dictht *t0, *t1;
        const dictEntry *de, *next;
        unsigned long m0, m1;
    
        if (dictSize(d) == 0) return 0;
    
        if (!dictIsRehashing(d)) { 
            t0 = &(d->ht[0]);
            m0 = t0->sizemask;
    
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
            de = t0->table[v & m0];
            while (de) { 
                next = de->next;
                fn(privdata, de);
                de = next;
            }
    
            /* Set unmasked bits so incrementing the reversed cursor * operates on the masked bits */
            v |= ~m0;
    
            /* Increment the reverse cursor */
            v = rev(v);
            v++;
            v = rev(v);
    
        } else { 
            t0 = &d->ht[0];
            t1 = &d->ht[1];
    
            /* Make sure t0 is the smaller and t1 is the bigger table */
            if (t0->size > t1->size) { 
                t0 = &d->ht[1];
                t1 = &d->ht[0];
            }
    
            m0 = t0->sizemask;
            m1 = t1->sizemask;
    
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
            de = t0->table[v & m0];
            while (de) { 
                next = de->next;
                fn(privdata, de);
                de = next;
            }
    
            /* Iterate over indices in larger table that are the expansion * of the index pointed to by the cursor in the smaller table */
            do { 
                /* Emit entries at cursor */
                if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
                de = t1->table[v & m1];
                while (de) { 
                    next = de->next;
                    fn(privdata, de);
                    de = next;
                }
    
                /* Increment the reverse cursor not covered by the smaller mask.*/
                v |= ~m1;
                v = rev(v);
                v++;
                v = rev(v);
    
                /* Continue while bits covered by mask difference is non-zero */
            } while (v & (m0 ^ m1));
        }
    
        return v;
    }
    
    /* ------------------------- private functions ------------------------------ */
    
    /* 哈希表扩展，主要使用dictIsRehashing()，dictExpand()实现 * Expand the hash table if needed */
    static int _dictExpandIfNeeded(dict *d)
    { 
        /* Incremental rehashing already in progress. Return. */
        if (dictIsRehashing(d)) return DICT_OK;
    
        /* If the hash table is empty expand it to the initial size. */
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    
        /* 使用过半则扩展 * If we reached the 1:1 ratio, and we are allowed to resize the hash * table (global setting) or we should avoid it but the ratio between * elements/buckets is over the "safe" threshold, we resize doubling * the number of buckets. */
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
        { 
            return dictExpand(d, d->ht[0].used*2);
        }
        return DICT_OK;
    }
    
    /* 实现2的指数级扩容 * Our hash table capability is a power of two */
    static unsigned long _dictNextPower(unsigned long size)
    { 
        unsigned long i = DICT_HT_INITIAL_SIZE;
    
        if (size >= LONG_MAX) return LONG_MAX + 1LU;
        while(1) { 
            if (i >= size)
                return i;
            i *= 2;
        }
    }
    
    /* Returns the index of a free slot that can be populated with * a hash entry for the given 'key'. * If the key already exists, -1 is returned * and the optional output parameter may be filled. * * Note that if we are in the process of rehashing the hash table, the * index is always returned in the context of the second (new) hash table. */
    static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
    { 
        unsigned long idx, table;
        dictEntry *he;
        if (existing) *existing = NULL;
    
        /* Expand the hash table if needed */
        if (_dictExpandIfNeeded(d) == DICT_ERR)
            return -1;
        for (table = 0; table <= 1; table++) { 
            idx = hash & d->ht[table].sizemask;
            /* Search if this slot does not already contain the given key */
            he = d->ht[table].table[idx];
            while(he) { 
                if (key==he->key || dictCompareKeys(d, key, he->key)) { 
                    if (existing) *existing = he;
                    return -1;
                }
                he = he->next;
            }
            if (!dictIsRehashing(d)) break;
        }
        return idx;
    }
    
    void dictEmpty(dict *d, void(callback)(void*)) { 
        _dictClear(d,&d->ht[0],callback);
        _dictClear(d,&d->ht[1],callback);
        d->rehashidx = -1;
        d->iterators = 0;
    }
    
    void dictEnableResize(void) { 
        dict_can_resize = 1;
    }
    
    void dictDisableResize(void) { 
        dict_can_resize = 0;
    }
    
    uint64_t dictGetHash(dict *d, const void *key) { 
        return dictHashKey(d, key);
    }
    
    /* 根据dict中的oldptr找key * Finds the dictEntry reference by using pointer and pre-calculated hash. * oldkey is a dead pointer and should not be accessed. * the hash value should be provided using dictGetHash. * no string / key comparison is performed. * return value is the reference to the dictEntry if found, or NULL if not found. */
    dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash) 
    { 
        dictEntry *he, **heref;
        unsigned long idx, table;
    
        if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
        for (table = 0; table <= 1; table++) { 
            idx = hash & d->ht[table].sizemask;
            heref = &d->ht[table].table[idx];
            he = *heref;
            while(he) { 
                if (oldptr==he->key)
                    return heref;
                heref = &he->next;
                he = *heref;
            }
            if (!dictIsRehashing(d)) return NULL;
        }
        return NULL;
    }
    
    /* ------------------------------- Debugging ---------------------------------*/
    
    #define DICT_STATS_VECTLEN 50
    size_t _dictGetStatsHt(char *buf, size_t bufsize, dictht *ht, int tableid) 
    { 
        unsigned long i, slots = 0, chainlen, maxchainlen = 0;
        unsigned long totchainlen = 0;
        unsigned long clvector[DICT_STATS_VECTLEN];
        size_t l = 0;
    
        if (ht->used == 0) { 
            return snprintf(buf,bufsize,
                "No stats available for empty dictionaries\n");
        }
    
        /* Compute stats. */
        for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
        for (i = 0; i < ht->size; i++) { 
            dictEntry *he;
    
            if (ht->table[i] == NULL) { 
                clvector[0]++;
                continue;
            }
            slots++;
            /* For each hash entry on this slot... */
            chainlen = 0;
            he = ht->table[i];
            while(he) { 
                chainlen++;
                he = he->next;
            }
            clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
            if (chainlen > maxchainlen) maxchainlen = chainlen;
            totchainlen += chainlen;
        }
    
        /* Generate human readable stats. */
        l += snprintf(buf+l,bufsize-l,
            "Hash table %d stats (%s):\n"
            " table size: %ld\n"
            " number of elements: %ld\n"
            " different slots: %ld\n"
            " max chain length: %ld\n"
            " avg chain length (counted): %.02f\n"
            " avg chain length (computed): %.02f\n"
            " Chain length distribution:\n",
            tableid, (tableid == 0) ? "main hash table" : "rehashing target",
            ht->size, ht->used, slots, maxchainlen,
            (float)totchainlen/slots, (float)ht->used/slots);
    
        for (i = 0; i < DICT_STATS_VECTLEN-1; i++) { 
            if (clvector[i] == 0) continue;
            if (l >= bufsize) break;
            l += snprintf(buf+l,bufsize-l,
                " %s%ld: %ld (%.02f%%)\n",
                (i == DICT_STATS_VECTLEN-1)?">= ":"",
                i, clvector[i], ((float)clvector[i]/ht->size)*100);
        }
    
        /* Unlike snprintf(), teturn the number of characters actually written. */
        if (bufsize) buf[bufsize-1] = '\0';
        return strlen(buf);
    }
    
    void dictGetStats(char *buf, size_t bufsize, dict *d) { 
        size_t l;
        char *orig_buf = buf;
        size_t orig_bufsize = bufsize;
    
        l = _dictGetStatsHt(buf,bufsize,&d->ht[0],0);
        buf += l;
        bufsize -= l;
        if (dictIsRehashing(d) && bufsize > 0) { 
            _dictGetStatsHt(buf,bufsize,&d->ht[1],1);
        }
        /* Make sure there is a NULL term at the end. */
        if (orig_bufsize) orig_buf[orig_bufsize-1] = '\0';
    }