1. uthash簡介

2. uthash的使用

2.1 定義結構體

2.2 添加

2.3 查找

2.4 替換

2.5 刪除

2.6 循環刪除

2.7 刪除哈希表所有元素

2.8 計算哈希表元素個數

2.9 遍歷哈希表中的所有項目

2.10 排序哈希表

2.11 完整代碼

3. 鍵值的各種類型舉例

3.1 整型鍵值

3.2 字符串鍵值

3.3 指針鍵值

3.4 結構體鍵值

4. 常用宏參考

4.1 類型宏

4.2 通用宏

4.4 參數說明

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

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

uthash還包括三個額外的頭文件，主要提供鏈表，動態數組和字符串。utlist.h為C結構提供了鏈接列表宏。utarray.h使用宏實現動態數組。utstring.h實現基本的動態字符串。

2. uthash的使用2.1 定義結構體

這里我們將id作為一個索引值，也就是鍵值，將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）; /*重復性檢查，當把兩個相同key值的結構體添加到哈希表中時會報錯*/

if （s==NULL） {

s = （struct my_struct *）malloc（sizeof *s）;///*只有在哈希中不存在ID的情況下，我們才創建該項目并將其添加。否則，我們只修改已經存在的結構。*/

s-》id = user_id;

HASH_ADD_INT（ users， id， s ）;

}

strcpy（s-》name， name）;

}

HASH_ADD_INT函數中，第一個參數users是哈希表，第二個參數id是鍵字段的名稱。最后一個參數s是指向要添加的結構的指針。

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;

}

在上述代碼中，第一個參數users是哈希表，第二個參數是user_id的地址（一定要傳遞地址）。最后s是輸出變量。當可以在哈希表中找到相應鍵值時，s返回給定鍵的結構，當找不到時s返回NULL。

2.4 替換

HASH_REPLACE宏等效于HASH_ADD宏，HASH_REPLACE會嘗試查找和刪除項目外。如果找到并刪除了一個項目，它還將返回該項目的指針作為輸出參數。

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 刪除

要從哈希表中刪除結構，必須具有指向它的指針。（如果只有鍵，請先執行HASH_FIND以獲取結構指針）。

void delete_user（struct my_struct *user） {

HASH_DEL（users， user）; /* user： 將要刪除的結構體指針 */

free（user）;

}

同樣，這里users是哈希表，user是指向我們要從哈希中刪除的結構的指針。

刪除結構只是將其從哈希表中刪除，并非free 。何時釋放結構的選擇完全取決于自己；uthash永遠不會主動釋放結構。

2.6 循環刪除

HASH_ITER是一個宏定義，程序執行時被替換為一個循環。

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 刪除哈希表所有元素

如果只想刪除所有項目，但不釋放它們或進行每個元素的清理，則可以通過一次操作更有效地做到這一點：

HASH_CLEAR（hh，users）;

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

2.8 計算哈希表元素個數

unsigned int num_users;

num_users = HASH_COUNT（users）;

printf（“there are %u users

”， num_users）;

當users為NULL時，HASH_COUNT會返回0。

2.9 遍歷哈希表中的所有項目

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

}

}

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

由于hh.prev和hh.next字段的緣故，可以在哈希中向前和向后迭代。可以通過遍歷這些指針來訪問哈希中的所有項目，因此哈希也是雙鏈表。

2.10 排序哈希表

HASH_SORT（ users， name_sort ）;

第二個參數是指向比較函數的指針。它必須接受兩個指針參數（要比較的項目），并且如果第一個項目分別在第二個項目之前，等于或之后排序，則必須返回小于零，零或大于零的int。 （這與標準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的兩個排序函數示例。

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： 公眾號【嵌入式與Linux那些事】

* @Date： 2020-2-2 2112

* @LastEditors： 公眾號【嵌入式與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; /* 使能結構體 */

};

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 整型鍵值

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

3.2 字符串鍵值

當鍵值為字符串時，具體要使用那個函數取決于結構體中的鍵值為字符串數組還是字符串指針。 這一點很重要。當結構體中的鍵值為字符串數組時，使用HASH_ADD_STR。鍵值為字符串指針時使用HASH_ADD_KEYPTR。接下來給出兩個例子參考。

當結構體中的鍵值為字符串數組時

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

}

當結構體中的鍵值為字符串指針時

#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 結構體鍵值

在將項目添加到哈希或查找項目之前，必須將結構體鍵值中的元素清零。

#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）;/*結構體鍵值清零*/

r-》key.a = ‘a’;

r-》key.b = 1;

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

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

l.key.a = ‘a’;

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 參數說明

hh_name：UT_hash_handle結構中字段的 名稱。俗稱 hh。

head：結構指針變量，用作哈希的“頭”。如此命名是因為它最初指向添加到哈希中的第一項。

keyfield_name：結構中鍵字段的名稱。（對于多字段鍵，這是鍵的第一個字段）。

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

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

hashv：提供的鍵的哈希值。這是BYHASHVALUE宏的輸入參數。如果要重復查找相同的鍵，則重用緩存的哈希值可以優化性能。

item_ptr：指向要添加，刪除，替換或查找的結構的指針，或迭代期間的當前指針。這是HASH_ADD， HASH_DELETE和HASH_REPLACE宏的輸入參數，輸出參數為HASH_FIND 和HASH_ITER。（當HASH_ITER用于迭代時，tmp_item_ptr 是與item_ptr內部使用的類型相同的另一個變量）。

replace_item_ptr：用于HASH_REPLACE宏。這是一個輸出參數，設置為指向替換的項目（如果沒有替換的項目，則設置為NULL）。

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

condition：接受單個參數的函數或宏（指向結構的空指針，需要將其強制轉換為適當的結構類型）。如果應“選擇”結構以將其添加到目標哈希中，則函數或宏的值應為非零值。

原文標題：你知道uthash嗎？

文章出處：【微信公眾號：FPGA之家】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq