redis源码阅读-数据结构篇-字典dict

@

目录

4. 字典实现 dict.h 和 dict.c

数据结构定义

  • 状态码

    #define DICT_OK 0	// 操作成功
    #define DICT_ERR 1	// 操作失败(或出错)
    
  • 哈希表kv节点

    typedef struct dictEntry {
      void *key;  		    // 键
      union {
          void *val;
          uint64_t u64;
          int64_t s64;
      } v;        	            // 值
      struct dictEntry *next; // 指向下个哈希表节点,形成链表
    } dictEntry;
    
  • 哈希表

    typedef struct dictht {
        dictEntry **table; 			// 哈希表数组
        unsigned long size;		// 哈希表大小
        unsigned long sizemask; 	// 哈希表大小掩码,用于计算索引值,总是等于 size - 1
        unsigned long used; 		// 该哈希表已有节点的数量
    } dictht;
    
  • kv操作函数

    typedef struct dictType {
        unsigned int (*hashFunction)(const void *key);	// 计算哈希值的函数
        void *(*keyDup)(void *privdata, const void *key);// 复制键的函数
        void *(*valDup)(void *privdata, const void *obj);// 复制值的函数
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 对比键的函数
        void (*keyDestructor)(void *privdata, void *key); // 销毁键的函数
        void (*valDestructor)(void *privdata, void *obj); // 销毁值的函数
    } dictType;
    
  • dict主角

    typedef struct dict {
        dictType *type;		// 类型特定函数
        void *privdata;		// 私有数据
        dictht ht[2]; 		// 哈希表, 存在一个时占第一个,存在两个时正在rehash
        int rehashidx;		// rehash 索引, 当 rehash 不在进行时,值为 -1
        int iterators;		// 目前正在运行的安全迭代器的数量
    } dict;
    
  • dict 迭代器

    typedef struct dictIterator {
        dict *d;    // 被迭代的字典
        // table :正在被迭代的哈希表号码,值可以是 0 或 1 。
        // index :迭代器当前所指向的哈希表索引位置。
        // safe :标识这个迭代器是否安全
        int table, index, safe;
        // entry :当前迭代到的节点的指针
        // nextEntry :当前迭代节点的下一个节点
        //             因为在安全迭代器运作时, entry 所指向的节点可能会被修改,
        //             所以需要一个额外的指针来保存下一节点的位置,
        //             从而防止指针丢失
        dictEntry *entry, *nextEntry;
        long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
    } dictIterator;
    

部分宏定义

#define DICT_HT_INITIAL_SIZE     4  												// 哈希表初始大小
// 释放给定字典节点的值
#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)
// 设置给定字典节点的值
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        entry->v.val = (_val_); \
} while(0)
...
// 比对两个键
#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d)->privdata, key1, key2) : \
        (key1) == (key2))
#define dictHashKey(d, key) (d)->type->hashFunction(key)  // 计算给定键的哈希值
#define dictGetKey(he) ((he)->key) 												// 返回获取给定节点的键
...

哈希函数(本部分可选跳过)

  • Thomas Wang's 32 bit Mix Function

    unsigned int dictIntHashFunction(unsigned int key) {
        key += ~(key << 15);
        key ^=  (key >> 10);
        key +=  (key << 3);
        key ^=  (key >> 6);
        key += ~(key << 11);
        key ^=  (key >> 16);
        return key;
    }
    
  • Identity hash function for integer keys

    unsigned int dictIdentityHashFunction(unsigned int key) {
        return key;
    }
    
  • MurmurHash2, by Austin Appleby

    unsigned int dictGenHashFunction(const void *key, int len) {
        /* 'm' and 'r' are mixing constants generated offline.
         They're not really 'magic', they just happen to work well.  */
        uint32_t seed = dict_hash_function_seed;
        const uint32_t m = 0x5bd1e995;
        const int r = 24;
        /* Initialize the hash to a 'random' value */
        uint32_t h = seed ^ len;
        /* Mix 4 bytes at a time into the hash */
        const unsigned char *data = (const unsigned char *)key;
        while(len >= 4) {
            uint32_t k = *(uint32_t*)data;
            k *= m;
            k ^= k >> r;
            k *= m;
            h *= m;
            h ^= k;
            data += 4;
            len -= 4;
        }
        /* Handle the last few bytes of the input array  */
        switch(len) {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0]; h *= m;
        };
        /* Do a few final mixes of the hash to ensure the last few
         * bytes are well-incorporated. */
        h ^= h >> 13;
        h *= m;
        h ^= h >> 15;
        return (unsigned int)h;
    }
    
  • a case insensitive hash function (based on djb hash)

    unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
        unsigned int hash = (unsigned int)dict_hash_function_seed;
        while (len--)
            hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
        return hash;
    }
    

关于hash函数,留坑待填,有时间会整理常见hash函数

Helper函数(可跳过,需要时阅读)

  • 时间函数 O(1)

    long long timeInMilliseconds(void) {
        struct timeval tv;
        gettimeofday(&tv,NULL);
        return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
    }
    
  • Fingerprint函数 O(1)

    long long dictFingerprint(dict *d) {
        long long integers[6], hash = 0;
        int j;
        integers[0] = (long) d->ht[0].table;
        integers[1] = d->ht[0].size;
        integers[2] = d->ht[0].used;
        integers[3] = (long) d->ht[1].table;
        integers[4] = d->ht[1].size;
        integers[5] = d->ht[1].used;
        for (j = 0; j < 6; j++) {
            hash += integers[j];
            hash = (~hash) + (hash << 21); 
            hash = hash ^ (hash >> 24);
            hash = (hash + (hash << 3)) + (hash << 8); 
            hash = hash ^ (hash >> 14);
            hash = (hash + (hash << 2)) + (hash << 4); 
            hash = hash ^ (hash >> 28);
            hash = hash + (hash << 31);
        }
        return hash;
    }
    
  • 重置/初始化 hashtable,不涉及内存 O(1)

    static void _dictReset(dictht *ht) {
        ht->table = NULL;
        ht->size = 0;
        ht->sizemask = 0;
        ht->used = 0;
    }
    
  • 重置/初始化dict,不涉及内存 O(1)

    int _dictInit(dict *d, dictType *type, void *privDataPtr) {
        _dictReset(&d->ht[0]);		// 初始化两个哈希表的各项属性值
        _dictReset(&d->ht[1]);		// 但暂时还不分配内存给哈希表数组
        d->type = type; 			// 设置类型特定函数
        d->privdata = privDataPtr;  // 设置私有数据
        d->rehashidx = -1;			// 设置哈希表 rehash 状态
        d->iterators = 0;			// 设置字典的安全迭代器数量
        return DICT_OK;
    }
    
  • dict进行一步rehash O(1)

    static void _dictRehashStep(dict *d) {
        if (d->iterators == 0) dictRehash(d,1);
    }
    
  • 遍历释放某个hashtable,用户自定义释放内存,并重置 O(n)

    int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
        unsigned long i;
        for (i = 0; i < ht->size && ht->used > 0; i++) {    					// 遍历整个哈希表 T = O(N)
            dictEntry *he, *nextHe;
            if (callback && (i & 65535) == 0) callback(d->privdata);
            if ((he = ht->table[i]) == NULL) continue;   							// 跳过空索引
            while(he) {   			// 遍历整个链表 T = O(1)
                nextHe = he->next;
                dictFreeKey(d, he); // 删除键
                dictFreeVal(d, he); // 删除值
                zfree(he); 			// 释放节点
                ht->used--;			// 更新已使用节点计数
                he = nextHe; 		// 处理下个节点
            }
        }
        zfree(ht->table); 			// 释放哈希表结构
        _dictReset(ht);  			// 重置哈希表属性
        return DICT_OK; 			/* never fails */
    }
    
  • 尝试expand,符合条件调用expand函数 O(1) / O(n)

    static int _dictExpandIfNeeded(dict *d) {
        // 渐进式 rehash 已经在进行了,直接返回
        if (dictIsRehashing(d)) return DICT_OK;
        // 如果字典(的 0 号哈希表)为空,那么创建并返回初始化大小的 0 号哈希表 T = O(1)
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
        // 一下两个条件同时为真时,对字典进行扩展
        // 1)字典已使用节点数和字典大小之间的比率大于 1
        // 2)dict_can_resize 为真 或者 已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
            // 新哈希表的大小至少是目前已使用节点数的两倍 T = O(N)
            return dictExpand(d, d->ht[0].used * 2);
        }
        return DICT_OK;
    }
    
  • 返回合适的hashtable size O(1)

    static unsigned long _dictNextPower(unsigned long size) {
        unsigned long i = DICT_HT_INITIAL_SIZE;
        if (size >= LONG_MAX) return LONG_MAX;
        while(1) {
            if (i >= size)
                return i;
            i *= 2;
        }
    }
    
  • 返回合适的新key对应的index O(1)

    static int _dictKeyIndex(dict *d, const void *key) {
        unsigned int h, idx, table;
        dictEntry *he;
        if (_dictExpandIfNeeded(d) == DICT_ERR)   	// rehash O(1) / O(N)
            return -1;
        h = dictHashKey(d, key);					// 计算 key 的哈希值
        for (table = 0; table <= 1; table++) {
            idx = h & d->ht[table].sizemask; 		// 计算索引值
            he = d->ht[table].table[idx];  			// 查找 key 是否存在 T = O(1)
            while(he) {
                if (dictCompareKeys(d, key, he->key))
                    return -1;						// 存在返回 -1
                he = he->next;
            }
            if (!dictIsRehashing(d)) break;			// 如果这时 rehash 正在进行,那么继续对 1 号哈希表进行 rehash
        }
        return idx;									// 返回索引值
    }
    
  • 返回合适的hashtable size

    static unsigned long _dictNextPower(unsigned long size) {
        unsigned long i = DICT_HT_INITIAL_SIZE;
        if (size >= LONG_MAX) return LONG_MAX;
        while(1) {
            if (i >= size)
                return i;
            i *= 2;
        }
    }
    

dict 构造函数 O(1)

dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d, type, privDataPtr);  //不涉及 hashtable 内存
    return d;
}

dict 析构函数 O(N)

void dictRelease(dict *d) {
    // 删除并清空两个哈希表
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    // 释放节点结构
    zfree(d);
}

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

hashtable 构造函数 O(1)

int dictExpand(dict *d, unsigned long size) {
    dictht n;  																			// 新哈希表
    unsigned long realsize = _dictNextPower(size); // 根据 size 参数,计算哈希表的大小
    // 不能在字典正在 rehash 时进行
    // 新 size 的值也不能小于 0 号哈希表的当前已使用节点
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));// 为哈希表分配空间,并将所有指针指向 NULL
    n.used = 0;
    if (d->ht[0].table == NULL) { 	// 如果 0 号哈希表为空,那么这是一次初始化:
        d->ht[0] = n;				//程序将新哈希表赋给 0 号哈希表的指针,然后字典就可以开始处理键值对了。
        return DICT_OK;
    }
    // 否则这是一次 rehash :
    d->ht[1] = n;  					// 程序将新哈希表设置为 1 号哈希表,
    d->rehashidx = 0;				// 并将字典的 rehash 标识打开,让程序可以开始对字典进行 rehash
    return DICT_OK;
	// 此函数并没初始化kv 或者 rehash kv,因此 O(1)
}

dict resize O(1)

用于初始化hashtable 或者 rehash

int dictResize(dict *d) {
    int minimal;
    // 不能在关闭 rehash 或者正在 rehash 的时候调用
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    // 计算让比率接近 1:1 所需要的最少节点数量
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal); // 调整字典的大小 O(1)
}

rehash O(m)

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;   	// 只可以在 rehash 进行中时执行
    while(n--) {  							// 进行 N 步迁移,N 为函数参数,N 为槽的个数
        dictEntry *de, *nextde;
        if (d->ht[0].used == 0) {			// 如果旧 0 号哈希表为空,那么表示 rehash 执行完毕
            zfree(d->ht[0].table); 			// 释放旧 0 号哈希表
            d->ht[0] = d->ht[1];			// 0 号哈希表 指向 rehash 完毕的 1 号哈希表
            _dictReset(&d->ht[1]); 			// 重置 1 号哈希表
            d->rehashidx = -1;				// 关闭 rehash 标识
            return 0; 						// 返回 0 ,向调用者表示 rehash 已经完成
        }
        // 略过数组中为空的索引,找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        de = d->ht[0].table[d->rehashidx]; 	// 指向该索引的链表表头节点
        while(de) {  																			
        	// 将链表中的所有节点迁移到新哈希表 T = O(1)
            unsigned int h;
            nextde = de->next; 															
            // 保存下个节点的指针
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;// 计算新哈希表的哈希值,以及节点插入的索引位置
            de->next = d->ht[1].table[h];										
            // 插入节点到新哈希表
            d->ht[1].table[h] = de;
            d->ht[0].used--;          											
            // 更新计数器
            d->ht[1].used++;
            de = nextde;   																	
            // 继续处理下个节点
        }
        d->ht[0].table[d->rehashidx] = NULL; // 将刚迁移完的哈希表索引的指针设为空
        d->rehashidx++;    																 	
        // 更新 rehash 索引
    }
    return 1;
}

限时rehash

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();// 记录开始时间
    int rehashes = 0;
    while(dictRehash(d,100)) {// 100 为步长
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break; // 如果时间已过,跳出
    }
    return rehashes;																// 返回rehash数量
}

set k O(1)

dictEntry *dictAddRaw(dict *d, void *key) {
    int index;
    dictEntry *entry;
    dictht *ht;
    // 如果条件允许的话,进行单步 rehash  T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if ((index = _dictKeyIndex(d, key)) == -1) // 计算键在哈希表中的索引值,存在返回null
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];// rehash 添加到 1 号哈希表,否则 0 号
    entry = zmalloc(sizeof(*entry));				// 为新节点分配空间
    entry->next = ht->table[index];					// 将新节点插入到链表表头
    ht->table[index] = entry;
    ht->used++;										// 更新哈希表已使用节点数量
    dictSetKey(d, entry, key);						// 设置新节点的键
    return entry;
}

set kv O(1)

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d,key);	// 尝试添加键到字典,并返回包含了这个键的新哈希节点
    if (!entry) return DICT_ERR;   			// 键已存在,添加失败
    dictSetVal(d, entry, val); 				// 键不存在,设置节点的值
    return DICT_OK;
}

get k O(1)

dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;
    if (d->ht[0].size == 0) return NULL;  		// 空
    // 如果条件允许的话,进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);					// 计算键的哈希值
    for (table = 0; table <= 1; table++) {		// 在字典的哈希表中查找这个键
        idx = h & d->ht[table].sizemask;		// 计算索引值
        he = d->ht[table].table[idx];			// 遍历给定索引上的链表的所有节点,查找 key
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;	// 没找到, rehash时 继续查找 1 号哈希表
    }
    return NULL;   																// 进行到这里时,说明两个哈希表都没找到
}

void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    he = dictFind(d,key);
    return he ? dictGetVal(he) : NULL;
}

update k O(1)

dictEntry *dictReplaceRaw(dict *d, void *key) {
    dictEntry *entry = dictFind(d,key);
    return entry ? entry : dictAddRaw(d,key); //存在直接返回节点,不存在新建节点
}

update kv O(1)

int dictReplace(dict *d, void *key, void *val) {
    dictEntry *entry, auxentry;
    // 尝试set
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;
    // key 已经存在
    entry = dictFind(d, key);
    auxentry = *entry; 				// 先保存原有的值的指针
    dictSetVal(d, entry, val);   	// 然后设置新的值
    dictFreeVal(d, &auxentry);   	// 然后释放旧值
    return 0;
}

delete kv O(1)

static int dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;
    if (d->ht[0].size == 0) return DICT_ERR; 	// 空
    // 进行单步 rehash ,T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);					// 计算哈希值
    for (table = 0; table <= 1; table++) { 		// 选择哈希表  T = O(1)
        idx = h & d->ht[table].sizemask;		// 计算索引值 
        he = d->ht[table].table[idx];			// 指向该索引上的链表
        prevHe = NULL;
        while(he) { 							// 遍历链表上的所有节点  T = O(1)
            if (dictCompareKeys(d, key, he->key)) { // 超找目标节点
                if (prevHe) 						// 从链表中删除
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {						// 释放调用键和值的释放函数?
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);							// 释放节点本身
                d->ht[table].used--;				// 更新已使用节点数量
                return DICT_OK; 					// 返回已找到信号
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;				// 没找到, rehash时 继续查找 1 号哈希表
    }
    return DICT_ERR; 																// 没找到
}

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}
int dictDeleteNoFree(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

get iter O(1)

dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));
    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    i->safe = 1;
    return i;
}

delete iter O(1)

void dictReleaseIterator(dictIterator *iter) {
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)		// 释放安全迭代器时,安全迭代器计数器减一
            iter->d->iterators--;
        else				// 释放不安全迭代器时,验证指纹是否有变化
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

迭代 O(1)

dictEntry *dictNext(dictIterator *iter) {
    while (1) {
        // 指向下个候选节点,待下面查
        if (iter->entry == NULL) { // 1) 第一次迭代 2) 链表迭代完成,寻找下个链表
            dictht *ht = &iter->d->ht[iter->table];		// 被迭代的哈希表
            if (iter->index == -1 && iter->table == 0) {// 第一次迭代
                if (iter->safe) 						// 迭代时更新计数
                    iter->d->iterators++;
                else									// 否则计算指纹
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;								// 迭代时增加index
            if (iter->index >= (signed) ht->size) {		// 当索引大于大小时,迭代完毕
                if (dictIsRehashing(iter->d) && iter->table == 0) {// 如果还有1号hashtable
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {								// 迭代彻底完成
                    break;
                }
            }
            iter->entry = ht->table[iter->index];		// 指向 index 的链表头,交给下面判断
        } else {
            iter->entry = iter->nextEntry;				// 正在迭代某个链表,指向链表的下个节点
        }
        if (iter->entry) {								// 如果不为空,记录链表下个节点,返回
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL; // 迭代完毕
}

dict 随机key O(1)

dictEntry *dictGetRandomKey(dict *d) {
    dictEntry *he, *orighe;
    unsigned int h;
    int listlen, listele;
    // 字典为空
    if (dictSize(d) == 0) return NULL;
    // 进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if (dictIsRehashing(d)) {// rehash ,1 号 hashtable 也算在内
        do {
            h = random() % (d->ht[0].size+d->ht[1].size);
            he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                      d->ht[0].table[h];
        } while(he == NULL);
    } else { // 否则,只算 0 号 hashtable
        do {
            h = random() & d->ht[0].sizemask;
            he = d->ht[0].table[h];
        } while(he == NULL);
    }
    listlen = 0;// 从这个链表随机返回一个节点
    orighe = he;
    while(he) { // 链表长度
        he = he->next;
        listlen++;
    }
    listele = random() % listlen;// 链表内索引
    he = orighe;
    while(listele--) he = he->next; // 按索引查找节点
    return he;// 返回随机节点
}

int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
    int j; 			// hashtable id
    int stored = 0; // 返回数量
    if (dictSize(d) < count) count = dictSize(d);//  不超过 dictsize
    while(stored < count) {
        for (j = 0; j < 2; j++) {// 0 1 顺序遍历
            unsigned int i = random() & d->ht[j].sizemask; 	// 随机 index,只取 1 次
            int size = d->ht[j].size;
            while(size--) {// 从 index 处的链表开始,一致向后迭代至 count 个
                dictEntry *he = d->ht[j].table[i];
                while (he) {
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
                i = (i+1) & d->ht[j].sizemask;
            }
            assert(dictIsRehashing(d) != 0);
        }
    }
    return stored;
}

dict scan O(1)

// helper 函数,留坑待填
/* 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); 
    unsigned long mask = ~0;
    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}
// 只迭代 v 的链表,并返回下次迭代的下标
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata) {
    dictht *t0, *t1;
    const dictEntry *de;
    unsigned long m0, m1;
    if (dictSize(d) == 0) return 0;	// 跳过空字典
    if (!dictIsRehashing(d)) { 		// 迭代只有一个哈希表的字典
        t0 = &(d->ht[0]); 			// 指向哈希表
        m0 = t0->sizemask;			// 记录 mask
        de = t0->table[v & m0];		// 指向哈希桶
        while (de) {  				// 遍历桶中的所有节点
            fn(privdata, de);
            de = de->next;
        }
    } else {						// 迭代有两个哈希表的字典,指向两个哈希表
        t0 = &d->ht[0];								
        t1 = &d->ht[1];
        if (t0->size > t1->size) {	// 确保 t0 比 t1 要小
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }
        m0 = t0->sizemask;			// 记录掩码
        m1 = t1->sizemask;
        de = t0->table[v & m0];		// 指向桶,并迭代桶中的所有节点
        while (de) {
            fn(privdata, de);
            de = de->next;
        }
        do {						// 迭代大表中的桶,这些桶被索引的 expansion 所指向
            de = t1->table[v & m1];	// 指向桶,并迭代桶中的所有节点
            while (de) {
                fn(privdata, de);
                de = de->next;
            }
            v = (((v | m0) + 1) & ~m0) | (v & m0);
        } while (v & (m0 ^ m1));
    }
    v |= ~m0;
    v = rev(v);
    v++;
    v = rev(v);
    return v;
}
上一篇:【深度学习入门到精通系列】对比度受限的自适应直方图均衡化(CLAHE)


下一篇:react项目搭建【非全局安装create-react-app】及启动失败解决方法