UTHash Use Tutorial

quick get start

To get started with this module, visit: Introduction, Data Interface, Sample Code

introduce

Hash: Hash, accessed by mapping data to a location in memory storage through functions on key values. This process is called Hash, a mapping function called a hash function, and an array of records is called a hash table, or hash table.

There is no special hash handler in C, so uthash, a library written by a third party, is usually used.

UtHash is a C-language hash header file that is processed using macro definitions. So adding utHash only requires #include "uthash.h" to complete the efficient hash operation.

When using hash tables in general, you want to make efficient additions and deletions to a set of data structures.

• Source github website: https://github.com/troydhanson/uthash
• Official Tutorial website: https://troydhanson.github.io/uthash/
• Official reference example: uthash-master/tests/example.c
• If you can't find the sample code, you can also refer to this blogger's excerpt, which is also from the official sample https://blog.csdn.net/fan_h_l/article/details/107241520

data interface

1. Define hash structure

Suppose we want to define a hash table with {key: value} as {id: data}, we need to define it as follows.

typedef struct example_user_t {
    int id;
    int data;
    UT_hash_handle hh;
} example_user_t;

2. Interfaces Introduce INT-type interfaces (macros)

uthash's interfaces are macro definitions, so you need to know whether each input parameter is a variable or an escape identifier.

First, several concepts are introduced to facilitate subsequent understanding:

• Hash structure - represents example_above User_ T-structure
• Hash key variable - represents id in int id above
• The value of the hash key variable - if int id = 8 above, then 8 is the value
• Hash value variable - represents int data above
• The value of the hash variable - represents the actual value of the data above
• Hash Header - Usually after a hash table has been created, a hash header is needed to index it, and each hash macro needs to pass in this parameter, usually a head
• Hash Key Value Pair - A pointer variable that represents a hash structure declaration, such as example_user_t *user;

Macro Name	usage	Meaning
HASH_ADD_INT	usage:[ HASH_ADD_INT(head, id, user) ]	Add a key-value pair structure corresponding to the INT key variable id to the head that contains the user
HASH_FIND_INT	usage:[ HASH_FIND_INT(head, &user_id, user) ]	Find the value user_of INT type key variable in head er Key-value pair structure user corresponding to ID
HASH_DEL	usage:[ HASH_DEL(head, user)]	Delete the key-value pair structure in the head er whose key-value pair structure is user

uthash INT sample code: student management system

1. The overall idea is as follows

• Create a hash table to map the int type to the StudentInfo structure. That is {int: StudentInfo};

• Implement CRUD add-delete check function

2. Structure Design

// Now that you're using hash tables, first, build the hash table structure [int, StudentInfo, UT_hash_handle]
// UT_hash_handle is the structure necessary to create a hash index and call a hash macro
// Adding the StudentInfo structure, the content of this case is only name and examPerform, name and achievement, which can be added as needed in the application scenario.
// Finally, set up g_Class's global variable holds the hash table header.
typedef struct StudentInfo {
	char name[50];
	int examPerform;
} StudentInfo;

typedef struct peopleManger_int {
    int id;
    StudentInfo *stuInfo;
    UT_hash_handle hh;
} peopleManger_int;

/* Global variables as hash tables */
peopleManger_int *g_Class;

3. uthash function encapsulation

// Because our hash table keys are int. So the core macros used are
// HASH_ ADD_ INT usage:[HASH_ADD_INT (hash header, key variable name, current hash structure added)]
// HASH_ FIND_ INT usage:[HASH_FIND_INT (hash header, value of key variable, used to store current added hash structure)]
// HASH_ DEL usage:[HASH_DEL (hash header, pointer to value variable to delete)]
// -------------------------------------------------------------------------------------
// The **item here is an externally declared value variable pointer that requests memory internally, so you need to use a double pointer for the address.
static void __createStudent(peopleManger_int **item, int stuID)
{
	*item = (peopleManger_int *)malloc(sizeof(peopleManger_int));
	(*item)->id = stuID;
	HASH_ADD_INT(g_Class, id, *item);

}

// As you can see here, look for HASH_ FIND_ When INT, an empty hash structure item is usually requested, and the corresponding hash structure of the key variable ID in the global hash header is passed to the item
static peopleManger_int * __findStudent(int stuID)
{
	peopleManger_int *item = NULL;
	HASH_FIND_INT(g_Class, &stuID, item);
	return item;
}

// The space on the heap needs to be freed after the hash is deleted.
static void __deleteStudent(peopleManger_int *item)
{
    HASH_DEL(g_Class, item);
    free(item->stuInfo);
    free(item);
}

4. Additions, deletions, alterations and checks

// Based on the above encapsulation functions, we can complete four interfaces
/* increase */
int pm_createStudent(int stuID, char *stuName, int exam)
{
	peopleManger_int *pmHashItem = NULL;

	pmHashItem = __findStudent(stuID);
	if (pmHashItem != NULL) {
		printf("has student already, please use update\n");
		return -1;
	}

	__createStudent(&pmHashItem, stuID);

    /* Filling in Student Information */
	pmHashItem->stuInfo = (StudentInfo *)malloc(sizeof(StudentInfo));
	memcpy(pmHashItem->stuInfo->name, stuName, sizeof(char) * (strlen(stuName) + 1));
	pmHashItem->stuInfo->examPerform = exam;

	return 0;
}

/* Delete */
int pm_deleteStudent(int stuID)
{
	peopleManger_int *pmHashItem = NULL;
	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("can not find item: %d\n", stuID);
		return -1;
	}

	__deleteStudent(pmHashItem);
	printf("stuID %d delete successfully\n");
	return 0;
}

/* change */
int pm_updateStudent(int stuID, char *stuName, int exam)
{
	peopleManger_int *pmHashItem = NULL;

	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("dont have student already, please use create\n");
		return -1;
	}

	pmHashItem->id = stuID;
	memset(pmHashItem->stuInfo->name, 0, sizeof(char) * 50);
	memcpy(pmHashItem->stuInfo->name, stuName, sizeof(char) * (strlen(stuName) + 1));
	pmHashItem->stuInfo->examPerform = exam;

	return 0;
}

/* lookup */
int pm_readStudent(int stuID)
{
	peopleManger_int *pmHashItem = NULL;
	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("can not find item: %d\n", stuID);
		return -1;
	}

	printf("stu id: %d  | ", pmHashItem->id);
	printf("stu name: %s | ", pmHashItem->stuInfo->name);
	printf("stu exam: %d\n", pmHashItem->stuInfo->examPerform);
    return 0;
}

5. Traverse Print All Elements

void pm_printStudentName()
{
    peopleManger_int *pmHashItem = NULL;

    for (pmHashItem = g_Class; pmHashItem != NULL; pmHashItem = (peopleManger_int *)(pmHashItem->hh.next)) {
        printf("stu %d, name %s, exam = %d\n", pmHashItem->id, pmHashItem->stuInfo->name, pmHashItem->stuInfo->examPerform);
    }
}

6. Full code

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "uthash.h"

typedef struct StudentInfo {
	char name[50];
	int examPerform;
} StudentInfo;

typedef struct peopleManger_int {
    int id;
    StudentInfo *stuInfo;
    UT_hash_handle hh;
} peopleManger_int;

/* Global variables as hash tables */
peopleManger_int *g_Class;

static void __createStudent(peopleManger_int **item, int stuID)
{
	*item = (peopleManger_int *)malloc(sizeof(peopleManger_int));
	(*item)->id = stuID;
	HASH_ADD_INT(g_Class, id, *item);

}

static peopleManger_int * __findStudent(int stuID)
{
	peopleManger_int *item = NULL;
	HASH_FIND_INT(g_Class, &stuID, item);
	return item;
}

static void __deleteStudent(peopleManger_int *item)
{
    HASH_DEL(g_Class, item);
    free(item->stuInfo);
    free(item);
}

/* increase */
int pm_createStudent(int stuID, char *stuName, int exam)
{
	peopleManger_int *pmHashItem = NULL;

	pmHashItem = __findStudent(stuID);
	if (pmHashItem != NULL) {
		printf("has student already, please use update\n");
		return -2;
	}

	__createStudent(&pmHashItem, stuID);

	pmHashItem->stuInfo = (StudentInfo *)malloc(sizeof(StudentInfo));
	memcpy(pmHashItem->stuInfo->name, stuName, sizeof(char) * (strlen(stuName) + 1));
	pmHashItem->stuInfo->examPerform = exam;

	return 0;
}

/* Delete */
int pm_deleteStudent(int stuID)
{
	peopleManger_int *pmHashItem = NULL;
	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("can not find item: %d\n", stuID);
		return -1;
	}

	__deleteStudent(pmHashItem);
	printf("stuID %d delete successfully\n");
	return 0;
}

/* change */
int pm_updateStudent(int stuID, char *stuName, int exam)
{
	peopleManger_int *pmHashItem = NULL;

	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("dont have student already, please use create\n");
		return -2;
	}

	pmHashItem->id = stuID;
	memset(pmHashItem->stuInfo->name, 0, sizeof(char) * 50);
	memcpy(pmHashItem->stuInfo->name, stuName, sizeof(char) * (strlen(stuName) + 1));
	pmHashItem->stuInfo->examPerform = exam;

	return 0;
}

/* lookup */
int pm_readStudent(int stuID)
{
	peopleManger_int *pmHashItem = NULL;
	pmHashItem = __findStudent(stuID);
	if (pmHashItem == NULL) {
		printf("can not find item: %d\n", stuID);
		return -1;
	}

	printf("stu id: %d  | ", pmHashItem->id);
	printf("stu name: %s | ", pmHashItem->stuInfo->name);
	printf("stu exam: %d\n", pmHashItem->stuInfo->examPerform);
	return 0;
}

void pm_printStudentName()
{
    peopleManger_int *pmHashItem = NULL;

    for (pmHashItem = g_Class; pmHashItem != NULL; pmHashItem = (peopleManger_int *)(pmHashItem->hh.next)) {
        printf("stu %d, name %s, exam = %d\n", pmHashItem->id, pmHashItem->stuInfo->name, pmHashItem->stuInfo->examPerform);
    }
}

int main()
{
    int i;
    peopleManger_int *stu = NULL;

    /* create elements */
    printf("-----create element-----\n");
    for(i = 0; i < 10; i++) {
    	char name[10] = "a_xiao";
    	name[0] = 'a' + i;
    	printf("here");
		pm_createStudent(i, name, 90 + i);
    }

    printf("-----read element-----\n");
    for(stu=g_Class; stu != NULL; stu=(peopleManger_int *)(stu->hh.next)) {
        printf("stu %d, name %s, exam = %d\n", stu->id, stu->stuInfo->name, stu->stuInfo->examPerform);
    }

    printf("delete a, go over\n");
    pm_deleteStudent(0);
    printf("-----read element-----\n");
	pm_printStudentName();

    pm_updateStudent(1, "xiaoming", 99);
    pm_updateStudent(0, "xiaohua", 99);

    pm_readStudent(1);
    pm_readStudent(0);
    return 0;
}