dict.h

//定義錯誤相關的碼
#define DICT_OK 0
#define DICT_ERR 1//實際存放數據的地方
typedef struct dictEntry {void *key;void *val;struct dictEntry *next;
} dictEntry;//哈希表的定義
typedef struct dict {//指向實際的哈希表記錄(用數組+開鏈的形式進行保存)dictEntry **table;//type中包含一系列哈希表需要用到的函數dictType *type;//size表示哈希表的大小，為2的指數unsigned long size;//sizemask=size-1,方便哈希值根據size取模unsigned long sizemask;//used記錄了哈希表中有多少記錄unsigned long used;void *privdata;
} dict;//對Hash表進行迭代遍歷時使用的迭代器
typedef struct dictIterator {dict *ht;int index;dictEntry *entry, *nextEntry;
} dictIterator;/* This is the initial size of every hash table */
//每個Hash表的初始大小
#define DICT_HT_INITIAL_SIZE     4

dict.c

#include "fmacros.h"#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <assert.h>
#include <limits.h>#include "dict.h"
#include "zmalloc.h"/* ---------------------------- Utility funcitons --------------------------- *//*** 打印出系統的崩潰信息* C語言中的可變參數的使用va_start va_end*/
static void _dictPanic(const char *fmt, ...)
{va_list ap;va_start(ap, fmt);fprintf(stderr, "\nDICT LIBRARY PANIC: ");vfprintf(stderr, fmt, ap);fprintf(stderr, "\n\n");va_end(ap);
}/* ------------------------- Heap Management Wrappers------------------------ */
/** *  堆分配函數*/
static void *_dictAlloc(size_t size)
{void *p = zmalloc(size);if (p == NULL)_dictPanic("Out of memory");return p;
}/*** 堆釋放函數*/
static void _dictFree(void *ptr) {zfree(ptr);
}/* -------------------------- private prototypes ---------------------------- */static int _dictExpandIfNeeded(dict *ht);
static unsigned long _dictNextPower(unsigned long size);
static int _dictKeyIndex(dict *ht, const void *key);
static int _dictInit(dict *ht, dictType *type, void *privDataPtr);/* -------------------------- hash functions -------------------------------- *//* Thomas Wang's 32 bit Mix Function */
/*** 求Hash的鍵值，可以促使均勻分布*/
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;
}/*** 直接將整數key作為Hash的鍵值*/
/* Identity hash function for integer keys */
unsigned int dictIdentityHashFunction(unsigned int key)
{return key;
}/* Generic hash function (a popular one from Bernstein).* I tested a few and this was the best. */
//Hash函數(通用目的Hash函數)
unsigned int dictGenHashFunction(const unsigned char *buf, int len) {unsigned int hash = 5381;while (len--)hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */return hash;
}/* ----------------------------- API implementation ------------------------- *//* Reset an hashtable already initialized with ht_init().* NOTE: This function should only called by ht_destroy(). */
/*** 重設Hash表* 各種值都設置為0*/
static void _dictReset(dict *ht)
{ht->table = NULL;ht->size = 0;ht->sizemask = 0;ht->used = 0;
}/*** 創建一個新的Hash表* type為可用于Hash表上面的相應函數*/
/* Create a new hash table */
dict *dictCreate(dictType *type,void *privDataPtr)
{dict *ht = _dictAlloc(sizeof(*ht));_dictInit(ht,type,privDataPtr);return ht;
}/* Initialize the hash table */
/*** 初始化Hash表*/
int _dictInit(dict *ht, dictType *type,void *privDataPtr)
{//對Hash表進行初始化_dictReset(ht);//初始化能夠作用于Hash中的相應函數集ht->type = type;//初始化hashtable的私有數據段ht->privdata = privDataPtr;//返回初始化成功return DICT_OK;
}/* Resize the table to the minimal size that contains all the elements,* but with the invariant of a USER/BUCKETS ration near to <= 1 *//*** DICT_HT_INITIAL_SIZE=4表示的是Hash表的初始大小* 重新調整Hash表的大小* 從這里可以看出Hash表的最小的大注為4*/
int dictResize(dict *ht)
{int minimal = ht->used;if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;return dictExpand(ht, minimal);
}/* Expand or create the hashtable */
/*** 創建Hash表，Hash表的大小為size*/
int dictExpand(dict *ht, unsigned long size)
{dict n; /* the new hashtable *///重設Hash表的大小，大小為2的指數unsigned long realsize = _dictNextPower(size);/* the size is invalid if it is smaller than the number of* elements already inside the hashtable *///如果大小比當原Hash表中記錄數目還要小的話，則出錯if (ht->used > size)return DICT_ERR;//初始化_dictInit(&n, ht->type, ht->privdata);n.size = realsize;//保證為素數n.sizemask = realsize-1;n.table = _dictAlloc(realsize*sizeof(dictEntry*));/* Initialize all the pointers to NULL *///將所有的指針初始為空memset(n.table, 0, realsize*sizeof(dictEntry*));/* Copy all the elements from the old to the new table:* note that if the old hash table is empty ht->size is zero,* so dictExpand just creates an hash table.* *///使用的內存記錄數n.used = ht->used;int i;for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;if (ht->table[i] == NULL) continue;//采用的是桶狀鏈表形式/* For each hash entry on this slot... */he = ht->table[i];//在遍歷的過程中對每一個元素又求取出在新Hash表中相應的位置 while(he) {unsigned int h;nextHe = he->next;/* Get the new element index *///dictHashKey(ht,he->key)獲取相應的鍵值key,實際上就是取模運算//求取在新hash表中的元素的位置h = dictHashKey(ht, he->key) & n.sizemask;//采用的是頭插入法進行的插入he->next = n.table[h];n.table[h] = he;ht->used--;/* Pass to the next element */he = nextHe;}}//斷言原Hash表中已經沒有記錄了assert(ht->used == 0);//將原Hash表進行釋放 _dictFree(ht->table);/* Remap the new hashtable in the old *///將新Hash表作為值進行賦值*ht = n;//返回創建成功return DICT_OK;
}/* Add an element to the target hash table */
/*** 向Hash表中增加元素* 增加元素的鍵為key,值為vals*/
int dictAdd(dict *ht, void *key, void *val)
{int index;dictEntry *entry;/* Get the index of the new element, or -1 if* the element already exists. */if ((index = _dictKeyIndex(ht, key)) == -1)return DICT_ERR;/* Allocates the memory and stores key *///分配內存空間entry = _dictAlloc(sizeof(*entry));//將其放入相應的slot里面//采用的是頭插入法進行插入entry->next = ht->table[index];ht->table[index] = entry;/* Set the hash entry fields. */dictSetHashKey(ht, entry, key);dictSetHashVal(ht, entry, val);//使用的記錄數進行+1操作ht->used++;//返回OK標記return DICT_OK;
}/* Add an element, discarding the old if the key already exists */
//向hash表中增加一個元素，如果Hash表中已經有該元素的話
//則將該元素進行替換掉
int dictReplace(dict *ht, void *key, void *val)
{dictEntry *entry;/* Try to add the element. If the key* does not exists dictAdd will suceed. */if (dictAdd(ht, key, val) == DICT_OK)return DICT_OK;/* It already exists, get the entry *///如果已經存在的話，則獲取相應的位置 entry = dictFind(ht, key);/* Free the old value and set the new one *///將原Hash表中該entry的值進行釋放//避免內存泄露dictFreeEntryVal(ht, entry);//給該節點設置新值dictSetHashVal(ht, entry, val);//返回成功標記return DICT_OK;
}/*** 從Hash表中刪除指定的key*/
/* Search and remove an element */
static int dictGenericDelete(dict *ht, const void *key, int nofree)
{unsigned int h;dictEntry *he, *prevHe;if (ht->size == 0)return DICT_ERR;/***  返回key對應的dictEntry*/h = dictHashKey(ht, key) & ht->sizemask;he = ht->table[h];prevHe = NULL;while(he) {if (dictCompareHashKeys(ht, key, he->key)) {/* Unlink the element from the list */if (prevHe)prevHe->next = he->next;elseht->table[h] = he->next;if (!nofree) {//如果需要釋放的情況下，則進行相應的釋放操作dictFreeEntryKey(ht, he);dictFreeEntryVal(ht, he);}_dictFree(he);//記錄數相應的進行減小ht->used--;return DICT_OK;}//進行相應的賦值操作prevHe = he;he = he->next;}//返回錯誤return DICT_ERR; /* not found */
}/*** 釋放指定的鍵值*/
int dictDelete(dict *ht, const void *key) {return dictGenericDelete(ht,key,0);
}/*** 從Hash表中刪除key對應的記錄，但是不* 刪除相應的key以及value*/
int dictDeleteNoFree(dict *ht, const void *key) {return dictGenericDelete(ht,key,1);
}/* Destroy an entire hash table */
/*** 釋放整個Hash表*/
int _dictClear(dict *ht)
{unsigned long i;/* Free all the elements *//*** 將所有的元素進行釋放 */for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;//表標桶狀結構中沒有鏈表元素if ((he = ht->table[i]) == NULL) continue;//循環進行遍歷while(he) {nextHe = he->next;//釋放鍵dictFreeEntryKey(ht, he);//釋放值 dictFreeEntryVal(ht, he);//釋放結構體_dictFree(he);//記錄數作相應的減法ht->used--;he = nextHe;}}/* Free the table and the allocated cache structure *///釋放整個Hash表_dictFree(ht->table);/* Re-initialize the table *///重新初始化整個Hash表，Hash結構還是要保留的_dictReset(ht);return DICT_OK; /* never fails */
}/* Clear & Release the hash table */
/*** 釋放Hash表* 整個Hash表連同Hash結構都將釋放 */
void dictRelease(dict *ht)
{//清除Hash表中的數據_dictClear(ht);//對空間進行釋放 _dictFree(ht);
}/***  從HashTable中查找key的相應的dictEntry*/
dictEntry *dictFind(dict *ht, const void *key)
{dictEntry *he;unsigned int h;//如果Hash表的大小為0,則直接返回NULLif (ht->size == 0) return NULL;h = dictHashKey(ht, key) & ht->sizemask;he = ht->table[h];while(he) {if (dictCompareHashKeys(ht, key, he->key))return he;he = he->next;}return NULL;
}/** * 獲取Hash表中的相應的迭代器*/
dictIterator *dictGetIterator(dict *ht)
{//給迭代器分配內存空間dictIterator *iter = _dictAlloc(sizeof(*iter));//對迭代器進行相應的初始化iter->ht = ht;iter->index = -1;iter->entry = NULL;iter->nextEntry = NULL;return iter;
}/*** 對Hashtable進行迭代遍歷操作*/
dictEntry *dictNext(dictIterator *iter)
{while (1) {if (iter->entry == NULL) {iter->index++;//如果遍歷的index大于整個Hashtable數組的大小時//說明已經遍歷完成，直接跳出if (iter->index >=(signed)iter->ht->size) break;iter->entry = iter->ht->table[iter->index];} else {//遍歷到下一個元素iter->entry = iter->nextEntry;}if (iter->entry) {/* We need to save the 'next' here, the iterator user* may delete the entry we are returning. *///返回遍歷過程中的下一個元素iter->nextEntry = iter->entry->next;//返回當前遍歷的元素return iter->entry;}}return NULL;
}/*** 釋放迭代器把指向的空間*/
void dictReleaseIterator(dictIterator *iter)
{_dictFree(iter);
}/* Return a random entry from the hash table. Useful to* implement randomized algorithms */
/*** 從Hashtable中獲取隨機的key*/
dictEntry *dictGetRandomKey(dict *ht)
{dictEntry *he;unsigned int h;int listlen, listele;//如果整個HashTable中壓根沒有記錄時//直接返回NULLif (ht->used == 0) return NULL;//否則隨機選擇一個HashTable里面的slotdo {h = random() & ht->sizemask;he = ht->table[h];} while(he == NULL);/* Now we found a non empty bucket, but it is a linked* list and we need to get a random element from the list.* The only sane way to do so is to count the element and* select a random index. *///計算出處于這個slot里面的元素數目listlen = 0;while(he) {he = he->next;listlen++;}//從整個slot鏈表中選擇元素的位置listele = random() % listlen;he = ht->table[h];//指針指向該鏈表的位置 while(listele--) he = he->next;return he;
}/* ------------------------- private functions ------------------------------ *//* Expand the hash table if needed */
/*** 判斷Hash表的大小是否需要擴充*/
static int _dictExpandIfNeeded(dict *ht)
{/* If the hash table is empty expand it to the intial size,* if the table is "full" dobule its size. *///如果目前的hashtable的大小為0，則將大小設置為4if (ht->size == 0)return dictExpand(ht, DICT_HT_INITIAL_SIZE);//如果hash表里數據記錄數已經與hashtable的大小相同的話，則將大小擴充為2倍if (ht->used == ht->size)//里面的記錄數已經達到了hashtable的大小時，則需要進行擴充空間return dictExpand(ht, ht->size*2);return DICT_OK;
}/* Our hash table capability is a power of two */
/*** Hash表的大小為2的指數冪*/
static unsigned long _dictNextPower(unsigned long size)
{//將i設置為hash表的初始大小即為4unsigned long i = DICT_HT_INITIAL_SIZE;//返回2的指數冪中與size大小最接近且比size大小的值if (size >= LONG_MAX) return LONG_MAX;while(1) {if (i >= size)return i;//i *= 2;}
}/* Returns the index of a free slot that can be populated with* an hash entry for the given 'key'.* If the key already exists, -1 is returned. */
/*** 返回key在hash表的位置，如果key在Hash表里已經存在，* 則返回-1*/
static int _dictKeyIndex(dict *ht, const void *key)
{unsigned int h;dictEntry *he;/*** 判斷是否需要擴充Hash表*//* Expand the hashtable if needed */if (_dictExpandIfNeeded(ht) == DICT_ERR)return -1;/* Compute the key hash value *//*** 獲取Hash表中key對應元素位置【即Hash表中的位置】 */h = dictHashKey(ht, key) & ht->sizemask;/* Search if this slot does not already contain the given key */he = ht->table[h];while(he) {//如果已經存在了話，即鍵值相等的話if (dictCompareHashKeys(ht, key, he->key))return -1;he = he->next;}//否則的話，就返回相應的slot位置 return h;
}/*** 清空HashTable* 清空后HashTable進行了重新的初始化*/
void dictEmpty(dict *ht) {_dictClear(ht);
}/*** 打印出HashTable表中數據的當前狀態* maxchainlen最大鏈表的長度* chainlen* slot表示Hashtable中已使用的桶數*/
#define DICT_STATS_VECTLEN 50
void dictPrintStats(dict *ht) {unsigned long i, slots = 0, chainlen, maxchainlen = 0;unsigned long totchainlen = 0;unsigned long clvector[DICT_STATS_VECTLEN];//如果Hashtable中為0記錄數，則打印出空Hashtableif (ht->used == 0) {printf("No stats available for empty dictionaries\n");return;}//對clvector數組進行相應的初始化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]記錄Hashtable中的空槽數clvector[0]++;continue;}//否則的知槽數++slots++;/* For each hash entry on this slot... */chainlen = 0;he = ht->table[i];//算出槽中的鏈表長度while(he) {chainlen++;he = he->next;}//如果小于50的話，則clvector相應的記錄增加//例如clvector[2]=10,表示Hashtable中槽里面鏈表長度為2的有10個//超過50的全部放在clvector[49]里面clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;if (chainlen > maxchainlen) maxchainlen = chainlen;totchainlen += chainlen;}//將狀態信息打印出來printf("Hash table stats:\n");//hashtable的大小printf(" table size: %ld\n", ht->size);//hashtable中存在的記錄數printf(" number of elements: %ld\n", ht->used);//hashtalbe中已使用的槽數printf(" different slots: %ld\n", slots);//hashtable中最大鍵的長度printf(" max chain length: %ld\n", maxchainlen);//hashtable中平均鏈表的長度printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);//和上一個值理論上來講應該是一樣的printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);printf(" Chain length distribution:\n");//打印出鏈表中的各個槽里面的鏈表的長度記錄for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {if (clvector[i] == 0) continue;printf("   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);}
}/* ----------------------- StringCopy Hash Table Type ------------------------*//*** Hash函數(字符串復制相關的Hash表函數)*/
static unsigned int _dictStringCopyHTHashFunction(const void *key)
{return dictGenHashFunction(key, strlen(key));
}
/*** 鍵值復制相關的函數*/
static void *_dictStringCopyHTKeyDup(void *privdata, const void *key)
{int len = strlen(key);char *copy = _dictAlloc(len+1);/*** #define DICT_NOTUSED(V) ((void) V);*/DICT_NOTUSED(privdata);//進行鍵值的復制操作memcpy(copy, key, len);//在字符串未尾加了\0標識字符串的結束copy[len] = '\0';return copy;
}/*** HashTable中值復制操作*/
static void *_dictStringKeyValCopyHTValDup(void *privdata, const void *val)
{  //獲取值的長度int len = strlen(val);//分配內存空間char *copy = _dictAlloc(len+1);DICT_NOTUSED(privdata);//進行內存復制的操作memcpy(copy, val, len);copy[len] = '\0';return copy;
}/*** 鍵值的比較函數* 比較key1與key2的值是否相等*/
static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,const void *key2)
{DICT_NOTUSED(privdata);return strcmp(key1, key2) == 0;
}/*** HashTable的析構函數*/
static void _dictStringCopyHTKeyDestructor(void *privdata, void *key)
{DICT_NOTUSED(privdata);//釋放key所占用的內存空間_dictFree((void*)key); /* ATTENTION: const cast */
}/*** HashTable中釋放值*/
static void _dictStringKeyValCopyHTValDestructor(void *privdata, void *val)
{DICT_NOTUSED(privdata);//釋放值所占用的內存空間_dictFree((void*)val); /* ATTENTION: const cast */
}