1. uthash簡介

2. uthash的使用

2.1 定義結(jié)構(gòu)體

2.2 添加

2.3 查找

2.4 替換

2.5 刪除

2.6 循環(huán)刪除

2.7 刪除哈希表所有元素

2.8 計(jì)算哈希表元素個(gè)數(shù)

2.9 遍歷哈希表中的所有項(xiàng)目

2.10 排序哈希表

2.11 完整代碼

3. 鍵值的各種類型舉例

3.1 整型鍵值

3.2 字符串鍵值

3.3 指針鍵值

3.4 結(jié)構(gòu)體鍵值

4. 常用宏參考

4.1 類型宏

4.2 通用宏

4.4 參數(shù)說明

1. uthash簡介??由于C語言本身不存在哈希，但是當(dāng)需要使用哈希表的時(shí)候自己構(gòu)建哈希會(huì)異常復(fù)雜。因此，我們可以調(diào)用開源的第三方頭文件，這只是一個(gè)頭文件：uthash.h。我們需要做的就是將頭文件復(fù)制到項(xiàng)目中，然后：#include “uthash.h”。由于uthash僅是頭文件，因此沒有可鏈接的庫代碼。

使用uthash添加，查找和刪除通常是常數(shù)時(shí)間的操作，此哈希的目標(biāo)是簡約高效，大約有1000行代碼。

uthash還包括三個(gè)額外的頭文件，主要提供鏈表，動(dòng)態(tài)數(shù)組和字符串。utlist.h為C結(jié)構(gòu)提供了鏈接列表宏。utarray.h使用宏實(shí)現(xiàn)動(dòng)態(tài)數(shù)組。utstring.h實(shí)現(xiàn)基本的動(dòng)態(tài)字符串。

2. uthash的使用2.1 定義結(jié)構(gòu)體

這里我們將id作為一個(gè)索引值，也就是鍵值，將name作為value。

#include “uthash.h”

struct my_struct {

int id; /* 鍵值 */

char name［10］;

UT_hash_handle hh; /* 使能哈希表 */

};

struct my_struct *users = NULL; //*聲明哈希為NULL指針*/

注意：一定要包含UT_hash_handle hh;hh不需要初始化。它可以命名為任何名稱，但是我們一般都命名為hh。

2.2 添加

HASH_ADD_INT表示添加的鍵值為int類型。

HASH_ADD_STR表示添加的鍵值為字符串類型。

HASH_ADD_PTR表示添加的鍵值為指針類型。

HASH_ADD表示添加的鍵值可以是任意類型。

void add_user（int user_id， char *name） {

struct my_struct *s;

HASH_FIND_INT（users， &user_id， s）; /*重復(fù)性檢查，當(dāng)把兩個(gè)相同key值的結(jié)構(gòu)體添加到哈希表中時(shí)會(huì)報(bào)錯(cuò)*/

if （s==NULL） {

s = （struct my_struct *）malloc（sizeof *s）;///*只有在哈希中不存在ID的情況下，我們才創(chuàng)建該項(xiàng)目并將其添加。否則，我們只修改已經(jīng)存在的結(jié)構(gòu)。*/

s-》id = user_id;

HASH_ADD_INT（ users， id， s ）;

}

strcpy（s-》name， name）;

}

HASH_ADD_INT函數(shù)中，第一個(gè)參數(shù)users是哈希表，第二個(gè)參數(shù)id是鍵字段的名稱。最后一個(gè)參數(shù)s是指向要添加的結(jié)構(gòu)的指針。

2.3 查找

struct my_struct *find_user（int user_id） {

struct my_struct *s;

s = （struct my_struct *）malloc（sizeof *s）;

HASH_FIND_INT（ users， &user_id， s ）; /* s： 返回值 */

return s;

}

在上述代碼中，第一個(gè)參數(shù)users是哈希表，第二個(gè)參數(shù)是user_id的地址（一定要傳遞地址）。最后s是輸出變量。當(dāng)可以在哈希表中找到相應(yīng)鍵值時(shí)，s返回給定鍵的結(jié)構(gòu)，當(dāng)找不到時(shí)s返回NULL。

2.4 替換

HASH_REPLACE宏等效于HASH_ADD宏，HASH_REPLACE會(huì)嘗試查找和刪除項(xiàng)目外。如果找到并刪除了一個(gè)項(xiàng)目，它還將返回該項(xiàng)目的指針作為輸出參數(shù)。

void replace_user（HashHead *head， HashNode *newNode） {

HashNode *oldNode = find_user（*head， newNode-》id）;

if （oldNode）

HASH_REPLACE_INT（*head， id， newNode， oldNode）;

}

2.5 刪除

要從哈希表中刪除結(jié)構(gòu)，必須具有指向它的指針。（如果只有鍵，請(qǐng)先執(zhí)行HASH_FIND以獲取結(jié)構(gòu)指針）。

void delete_user（struct my_struct *user） {

HASH_DEL（users， user）; /* user： 將要?jiǎng)h除的結(jié)構(gòu)體指針 */

free（user）;

}

同樣，這里users是哈希表，user是指向我們要從哈希中刪除的結(jié)構(gòu)的指針。

刪除結(jié)構(gòu)只是將其從哈希表中刪除，并非free 。何時(shí)釋放結(jié)構(gòu)的選擇完全取決于自己；uthash永遠(yuǎn)不會(huì)主動(dòng)釋放結(jié)構(gòu)。

2.6 循環(huán)刪除

HASH_ITER是一個(gè)宏定義，程序執(zhí)行時(shí)被替換為一個(gè)循環(huán)。

void delete_all（） {

struct my_struct *current_user， *tmp;

HASH_ITER（hh， users， current_user， tmp） {

HASH_DEL（users，current_user）;

free（current_user）;

}

}

2.7 刪除哈希表所有元素

如果只想刪除所有項(xiàng)目，但不釋放它們或進(jìn)行每個(gè)元素的清理，則可以通過一次操作更有效地做到這一點(diǎn)：

HASH_CLEAR（hh，users）;

之后，列表頭（此處為users）將設(shè)置為NULL。

2.8 計(jì)算哈希表元素個(gè)數(shù)

unsigned int num_users;

num_users = HASH_COUNT（users）;

printf（“there are %u users

”， num_users）;

當(dāng)users為NULL時(shí)，HASH_COUNT會(huì)返回0。

2.9 遍歷哈希表中的所有項(xiàng)目

void print_users（） {

struct my_struct *s;

for（s=users; s ！= NULL; s=s-》hh.next） {

printf（“user id %d： name %s

”， s-》id， s-》name）;

}

}

還有一個(gè)hh.prev指針，可用于從任何已知項(xiàng)開始向后迭代哈希。

由于hh.prev和hh.next字段的緣故，可以在哈希中向前和向后迭代?？梢酝ㄟ^遍歷這些指針來訪問哈希中的所有項(xiàng)目，因此哈希也是雙鏈表。

2.10 排序哈希表

HASH_SORT（ users， name_sort ）;

第二個(gè)參數(shù)是指向比較函數(shù)的指針。它必須接受兩個(gè)指針參數(shù)（要比較的項(xiàng)目），并且如果第一個(gè)項(xiàng)目分別在第二個(gè)項(xiàng)目之前，等于或之后排序，則必須返回小于零，零或大于零的int。 （這與標(biāo)準(zhǔn)C庫中的strcmp或qsort使用的方法相同）。

int sort_function（void *a， void *b） {

/* 將a與b比較*/

if （a 《 b） return （int） -1;

if （a == b） return （int） 0 ;

if （a 》 b） return （int） 1;

}

name_sort和id_sort的兩個(gè)排序函數(shù)示例。

int name_sort（struct my_struct *a， struct my_struct *b） {

return strcmp（a-》name，b-》name）;

}

int id_sort（struct my_struct *a， struct my_struct *b） {

return （a-》id - b-》id）;

}

void sort_by_name（） {

HASH_SORT（users， name_sort）;

}

void sort_by_id（） {

HASH_SORT（users， id_sort）;

}

2.11 完整代碼

/*

* @Description： UTHASH的使用

* @Version： V1.0

* @Autor： 公眾號(hào)【嵌入式與Linux那些事】

* @Date： 2020-2-2 2112

* @LastEditors： 公眾號(hào)【嵌入式與Linux那些事】

* @LastEditTime： 2020-2-2 2246

*/

#include 《stdio.h》 /* gets */

#include 《stdlib.h》 /* atoi， malloc */

#include 《string.h》 /* strcpy */

#include “uthash.h”

struct my_struct {

int id; /* 鍵值 */

char name［10］;

UT_hash_handle hh; /* 使能結(jié)構(gòu)體 */

};

struct my_struct *users = NULL;

void add_user（int user_id， char *name） {

struct my_struct *s;

HASH_FIND_INT（users， &user_id， s）;

if （s==NULL） {

s = （struct my_struct *）malloc（sizeof *s）;

s-》id = user_id;

HASH_ADD_INT（ users， id， s ）;

}

strcpy（s-》name， name）;

}

struct my_struct *find_user（int user_id） {

struct my_struct *s;

s = （struct my_struct *）malloc（sizeof *s）;

HASH_FIND_INT（ users， &user_id， s ）;

return s;

}

void delete_user（struct my_struct *user） {

HASH_DEL（users， user）;

free（user）;

}

void delete_all（） {

struct my_struct *current_user， *tmp;

HASH_ITER（hh， users， current_user， tmp） {

HASH_DEL（users， current_user）;

free（current_user）;

}

}

void print_users（） {

struct my_struct *s;

for（s=users; s ！= NULL; s=（struct my_struct*）（s-》hh.next）） {

printf（“user id %d： name %s

”， s-》id， s-》name）;

}

}

int name_sort（struct my_struct *a， struct my_struct *b） {

return strcmp（a-》name，b-》name）;

}

int id_sort（struct my_struct *a， struct my_struct *b） {

return （a-》id - b-》id）;

}

void sort_by_name（） {

HASH_SORT（users， name_sort）;

}

void sort_by_id（） {

HASH_SORT（users， id_sort）;

}

int main（int argc， char *argv［］） {

char in［10］;

int id=1， running=1;

struct my_struct *s;

unsigned num_users;

while （running） {

printf（“ 1. add user

”）;

printf（“ 2. add/rename user by id

”）;

printf（“ 3. find user

”）;

printf（“ 4. delete user

”）;

printf（“ 5. delete all users

”）;

printf（“ 6. sort items by name

”）;

printf（“ 7. sort items by id

”）;

printf（“ 8. print users

”）;

printf（“ 9. count users

”）;

printf（“10. quit

”）;

gets（in）;

switch（atoi（in）） {

case 1：

printf（“name？

”）;

add_user（id++， gets（in））;

break;

case 2：

printf（“id？

”）;

gets（in）; id = atoi（in）;

printf（“name？

”）;

add_user（id， gets（in））;

break;

case 3：

printf（“id？

”）;

s = find_user（atoi（gets（in）））;

printf（“user： %s

”， s ？ s-》name ： “unknown”）;

break;

case 4：

printf（“id？

”）;

s = find_user（atoi（gets（in）））;

if （s） delete_user（s）;

else printf（“id unknown

”）;

break;

case 5：

delete_all（）;

break;

case 6：

sort_by_name（）;

break;

case 7：

sort_by_id（）;

break;

case 8：

print_users（）;

break;

case 9：

num_users=HASH_COUNT（users）;

printf（“there are %u users

”， num_users）;

break;

case 10：

running=0;

break;

}

}

delete_all（）;

return 0;

}

3. 鍵值的各種類型舉例3.1 整型鍵值

當(dāng)鍵值為整型時(shí)，可以使用HASH_ADD_INT和HASH_FIND_INT。（對(duì)于所有類型的鍵，其他操作（例如HASH_DELETE和）HASH_SORT都是相同的）。

3.2 字符串鍵值

當(dāng)鍵值為字符串時(shí)，具體要使用那個(gè)函數(shù)取決于結(jié)構(gòu)體中的鍵值為字符串?dāng)?shù)組還是字符串指針。 這一點(diǎn)很重要。當(dāng)結(jié)構(gòu)體中的鍵值為字符串?dāng)?shù)組時(shí)，使用HASH_ADD_STR。鍵值為字符串指針時(shí)使用HASH_ADD_KEYPTR。接下來給出兩個(gè)例子參考。

當(dāng)結(jié)構(gòu)體中的鍵值為字符串?dāng)?shù)組時(shí)

#include 《string.h》 /* strcpy */

#include 《stdlib.h》 /* malloc */

#include 《stdio.h》 /* printf */

#include “uthash.h”

struct my_struct {

char name［10］;

int id;

UT_hash_handle hh;

};

int main（int argc， char *argv［］） {

const char *names［］ = { “joe”， “bob”， “betty”， NULL };

struct my_struct *s， *tmp， *users = NULL;

for （int i = 0; names［i］; ++i） {

s = （struct my_struct *）malloc（sizeof *s）;

strcpy（s-》name， names［i］）;

s-》id = i;

HASH_ADD_STR（ users， name， s ）;

}

HASH_FIND_STR（ users， “betty”， s）;

if （s） printf（“betty‘s id is %d

”， s-》id）;

HASH_ITER（hh， users， s， tmp） {

HASH_DEL（users， s）;

free（s）;

}

return 0;

}

當(dāng)結(jié)構(gòu)體中的鍵值為字符串指針時(shí)

#include 《string.h》 /* strcpy */

#include 《stdlib.h》 /* malloc */

#include 《stdio.h》 /* printf */

#include “uthash.h”

struct my_struct {

const char *name;

int id;

UT_hash_handle hh;

};

int main（int argc， char *argv［］） {

const char *names［］ = { “joe”， “bob”， “betty”， NULL };

struct my_struct *s， *tmp， *users = NULL;

for （int i = 0; names［i］; ++i） {

s = （struct my_struct *）malloc（sizeof *s）;

s-》name = names［i］;

s-》id = i;

HASH_ADD_KEYPTR（ hh， users， s-》name， strlen（s-》name）， s ）;

}

HASH_FIND_STR（ users， “betty”， s）;

if （s） printf（“betty’s id is %d

”， s-》id）;

HASH_ITER（hh， users， s， tmp） {

HASH_DEL（users， s）;

free（s）;

}

return 0;

}

3.3 指針鍵值

#include 《stdio.h》

#include 《stdlib.h》

#include “uthash.h”

typedef struct {

void *key;

int i;

UT_hash_handle hh;

} el_t;

el_t *hash = NULL;

char *someaddr = NULL;

int main（） {

el_t *d;

el_t *e = （el_t *）malloc（sizeof *e）;

if （！e） return -1;

e-》key = （void*）someaddr;

e-》i = 1;

HASH_ADD_PTR（hash，key，e）;

HASH_FIND_PTR（hash， &someaddr， d）;

if （d） printf（“found

”）;

/* release memory */

HASH_DEL（hash，e）;

free（e）;

return 0;

}

3.4 結(jié)構(gòu)體鍵值

在將項(xiàng)目添加到哈希或查找項(xiàng)目之前，必須將結(jié)構(gòu)體鍵值中的元素清零。

#include 《stdlib.h》

#include 《stdio.h》

#include “uthash.h”

typedef struct {

char a;

int b;

} record_key_t;

typedef struct {

record_key_t key;

UT_hash_handle hh;

} record_t;

int main（int argc， char *argv［］） {

record_t l， *p， *r， *tmp， *records = NULL;

r = （record_t *）malloc（sizeof *r）;

memset（r， 0， sizeof *r）;/*結(jié)構(gòu)體鍵值清零*/

r-》key.a = ‘a(chǎn)’;

r-》key.b = 1;

HASH_ADD（hh， records， key， sizeof（record_key_t）， r）;

memset（&l， 0， sizeof（record_t））;

l.key.a = ‘a(chǎn)’;

l.key.b = 1;

HASH_FIND（hh， records， &l.key， sizeof（record_key_t）， p）;

if （p） printf（“found %c %d

”， p-》key.a， p-》key.b）;

HASH_ITER（hh， records， p， tmp） {

HASH_DEL（records， p）;

free（p）;

}

return 0;

}

4. 常用宏參考4.1 類型宏

HASH_ADD_INT（head， keyfield_name， item_ptr）

HASH_REPLACE_INT（head， keyfiled_name， item_ptr，replaced_item_ptr）

HASH_FIND_INT（head， key_ptr， item_ptr）

HASH_ADD_STR（head， keyfield_name， item_ptr）

HASH_REPLACE_STR（head，keyfield_name， item_ptr， replaced_item_ptr）

HASH_FIND_STR（head， key_ptr， item_ptr）

HASH_ADD_PTR（head， keyfield_name， item_ptr）

HASH_REPLACE_PTR（head， keyfield_name， item_ptr， replaced_item_ptr）

HASH_FIND_PTR（head， key_ptr， item_ptr）

HASH_DEL（head， item_ptr）

HASH_SORT（head， cmp）

HASH_COUNT（head）

4.2 通用宏

HASH_ADD（hh_name， head， keyfield_name， key_len， item_ptr）

HASH_ADD_BYHASHVALUE（hh_name， head， keyfield_name， key_len， hashv， item_ptr）

HASH_ADD_KEYPTR（hh_name， head， key_ptr， key_len， item_ptr）

HASH_ADD_KEYPTR_BYHASHVALUE（hh_name， head， key_ptr， key_len， hashv， item_ptr）

HASH_ADD_INORDER（hh_name， head， keyfield_name， key_len， item_ptr， cmp）

HASH_ADD_BYHASHVALUE_INORDER（hh_name， head， keyfield_name， key_len， hashv， item_ptr， cmp）

HASH_ADD_KEYPTR_INORDER（hh_name， head， key_ptr， key_len， item_ptr， cmp）

HASH_ADD_KEYPTR_BYHASHVALUE_INORDER（hh_name， head， key_ptr， key_len， hashv， item_ptr， cmp）

HASH_REPLACE（hh_name， head， keyfield_name， key_len， item_ptr， replaced_item_ptr）

HASH_REPLACE_BYHASHVALUE（hh_name， head， keyfield_name， key_len， hashv， item_ptr， replaced_item_ptr）

HASH_REPLACE_INORDER（hh_name， head， keyfield_name， key_len， item_ptr， replaced_item_ptr， cmp）

HASH_REPLACE_BYHASHVALUE_INORDER（hh_name， head， keyfield_name， key_len， hashv， item_ptr， replaced_item_ptr， cmp）

HASH_FIND（hh_name， head， key_ptr， key_len， item_ptr）

HASH_FIND_BYHASHVALUE（hh_name， head， key_ptr， key_len， hashv， item_ptr）

HASH_DELETE（hh_name， head， item_ptr）

HASH_VALUE（key_ptr， key_len， hashv）

HASH_SRT（hh_name， head， cmp）

HASH_CNT（hh_name， head）

HASH_CLEAR（hh_name， head）

HASH_SELECT（dst_hh_name， dst_head， src_hh_name， src_head， condition）

HASH_ITER（hh_name， head， item_ptr， tmp_item_ptr）

HASH_OVERHEAD（hh_name， head）

4.4 參數(shù)說明

hh_name：UT_hash_handle結(jié)構(gòu)中字段的 名稱。俗稱 hh。

head：結(jié)構(gòu)指針變量，用作哈希的“頭”。如此命名是因?yàn)樗畛踔赶蛱砑拥焦Ｖ械牡谝豁?xiàng)。

keyfield_name：結(jié)構(gòu)中鍵字段的名稱。（對(duì)于多字段鍵，這是鍵的第一個(gè)字段）。

key_len：鍵字段的長度（以字節(jié)為單位）。例如，對(duì)于整數(shù)鍵，它是sizeof（int），而對(duì)于字符串鍵，它是strlen（key）。

key_ptr：對(duì)于HASH_FIND，這是指向要在哈希中查找的鍵的指針（由于它是指針，因此不能在此處直接傳遞文字值）。對(duì)于 HASH_ADD_KEYPTR，這是要添加的項(xiàng)的鍵的地址。

hashv：提供的鍵的哈希值。這是BYHASHVALUE宏的輸入?yún)?shù)。如果要重復(fù)查找相同的鍵，則重用緩存的哈希值可以優(yōu)化性能。

item_ptr：指向要添加，刪除，替換或查找的結(jié)構(gòu)的指針，或迭代期間的當(dāng)前指針。這是HASH_ADD， HASH_DELETE和HASH_REPLACE宏的輸入?yún)?shù)，輸出參數(shù)為HASH_FIND 和HASH_ITER。（當(dāng)HASH_ITER用于迭代時(shí)，tmp_item_ptr 是與item_ptr內(nèi)部使用的類型相同的另一個(gè)變量）。

replace_item_ptr：用于HASH_REPLACE宏。這是一個(gè)輸出參數(shù)，設(shè)置為指向替換的項(xiàng)目（如果沒有替換的項(xiàng)目，則設(shè)置為NULL）。

cmp：指向比較函數(shù)的指針，該函數(shù)接受兩個(gè)參數(shù)（指向要比較的項(xiàng)目的指針），并返回一個(gè)int值，該值指定第一個(gè)項(xiàng)目應(yīng)在第二個(gè)項(xiàng)目之前，等于還是之后排序（如strcmp）。

condition：接受單個(gè)參數(shù)的函數(shù)或宏（指向結(jié)構(gòu)的空指針，需要將其強(qiáng)制轉(zhuǎn)換為適當(dāng)?shù)慕Y(jié)構(gòu)類型）。如果應(yīng)“選擇”結(jié)構(gòu)以將其添加到目標(biāo)哈希中，則函數(shù)或宏的值應(yīng)為非零值。

原文標(biāo)題：你知道uthash嗎？

文章出處：【微信公眾號(hào)：FPGA之家】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq