Redis - 基础概念, 数据结构

/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
 
   dictEntry **table; // 哈希表数组
 
   unsigned long size; // 哈希表大小
 
   unsigned long sizemask; // 哈希表大小掩码，计算索引值
 
   unsigned long used; // 哈希表已有节点数量
 
} dictht;

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

typedef struct dict {
 
   dictType *type; // 类型特定函数
 
   void *privdata; // 私有数据
 
   dictht ht[2]; // 哈希表
 
   long rehashidx; // rehash索引, 当rehash不进行时, 值为-1
 
   unsigned long iterators; // 当前运行的迭代器数量
 
} dict;

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

/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
   int empty_visits = n * 10; /* Max number of empty buckets to visit. */
   if (!dictIsRehashing(d)) return 0;
   while (n-- && d->ht[0].used != 0) {
       dictEntry *de, *nextde;
       /* Note that rehashidx can't overflow as we are sure there are more
        * elements because ht[0].used != 0 */
       assert(d->ht[0].size > (unsigned long) d->rehashidx);
       while (d->ht[0].table[d->rehashidx] == NULL) {
           d->rehashidx++;
           if (--empty_visits == 0) return 1;
      }
       de = d->ht[0].table[d->rehashidx];
       /* Move all the keys in this bucket from the old to the new hash HT */
       while (de) {
           uint64_t h;
           nextde = de->next;
           /* Get the index in the new hash table */
           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++;
  }
   /* Check if we already rehashed the whole table... */
   if (d->ht[0].used == 0) {
       zfree(d->ht[0].table);
       d->ht[0] = d->ht[1];
       _dictReset(&d->ht[1]);
       d->rehashidx = -1;
       return 0;
  }
   /* More to rehash... */
   return 1;
}