C language hashtable/hashset library summary

stay https://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c Many related libraries are introduced in . After personal screening , Comprehensively consider the execution efficiency 、 The perfection of the document 、 The supported data types are in three aspects , I chose uthash.
Official documents can be found in ：http://troydhanson.github.io/uthash/userguide.html

* If you want to be HashSet use , It only needs value Just assign any value

* If you only need String Type of key and value, You can also consider strmap

* There's no choice python Built in libcfu（ Download address , Official documents ）, Because it's in Android There are many problems when compiling on the environment of .

Brief example ( See official documents for details )

1. initialization

#include "uthash.h"

struct my_struct {
    int id; // key
    char name[10]; //value
    UT_hash_handle hh; //  There has to be , Let this structure hashable
};

struct my_struct *users = NULL; //  important , Must be initialized to NULL

2. add to

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); // id: key Name 
    }
    strcpy(s->name, name);
}

3. lookup

struct my_struct *find_user(int user_id) {
    struct my_struct *s;
    HASH_FIND_INT(users, &user_id, s);
    return s;
}

4. Delete

void delete_user(struct my_struct *user) {
    HASH_DEL(users, user);
    free(user); // Optional 
}

Refer to the official website demo Source code

#include <stdio.h>   /* printf */
#include <stdlib.h>  /* atoi, malloc */
#include <string.h>  /* strcpy */
#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[21];
    UT_hash_handle hh;         /* makes this structure hashable */
};

struct my_struct *users = NULL;

void add_user(int user_id, const char *name)
{
    struct my_struct *s;

    HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
    if (s == NULL) {
        s = (struct my_struct*)malloc(sizeof *s);
        s->id = user_id;
        HASH_ADD_INT(users, id, s);  /* id is the key field */
    }
    strcpy(s->name, name);
}

struct my_struct *find_user(int user_id)
{
    struct my_struct *s;

    HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */
    return s;
}

void delete_user(struct my_struct *user)
{
    HASH_DEL(users, user);  /* user: pointer to deletee */
    free(user);
}

void delete_all()
{
    struct my_struct *current_user;
    struct my_struct *tmp;

    HASH_ITER(hh, users, current_user, tmp) {
        HASH_DEL(users, current_user);  /* delete it (users advances to next) */
        free(current_user);             /* free it */
    }
}

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\n", s->id, s->name);
    }
}

int by_name(const struct my_struct *a, const struct my_struct *b)
{
    return strcmp(a->name, b->name);
}

int by_id(const struct my_struct *a, const struct my_struct *b)
{
    return (a->id - b->id);
}

const char *getl(const char *prompt)
{
    static char buf[21];
    char *p;
    printf("%s? ", prompt); fflush(stdout);
    p = fgets(buf, sizeof(buf), stdin);
    if (p == NULL || (p = strchr(buf, '\n')) == NULL) {
        puts("Invalid input!");
        exit(EXIT_FAILURE);
    }
    *p = '\0';
    return buf;
}

int main()
{
    int id = 1;
    int running = 1;
    struct my_struct *s;
    int temp;

    while (running) {
        printf(" 1. add user\n");
        printf(" 2. add or rename user by id\n");
        printf(" 3. find user\n");
        printf(" 4. delete user\n");
        printf(" 5. delete all users\n");
        printf(" 6. sort items by name\n");
        printf(" 7. sort items by id\n");
        printf(" 8. print users\n");
        printf(" 9. count users\n");
        printf("10. quit\n");
        switch (atoi(getl("Command"))) {
            case 1:
                add_user(id++, getl("Name (20 char max)"));
                break;
            case 2:
                temp = atoi(getl("ID"));
                add_user(temp, getl("Name (20 char max)"));
                break;
            case 3:
                s = find_user(atoi(getl("ID to find")));
                printf("user: %s\n", s ? s->name : "unknown");
                break;
            case 4:
                s = find_user(atoi(getl("ID to delete")));
                if (s) {
                    delete_user(s);
                } else {
                    printf("id unknown\n");
                }
                break;
            case 5:
                delete_all();
                break;
            case 6:
                HASH_SORT(users, by_name);
                break;
            case 7:
                HASH_SORT(users, by_id);
                break;
            case 8:
                print_users();
                break;
            case 9:
                temp = HASH_COUNT(users);
                printf("there are %d users\n", temp);
                break;
            case 10:
                running = 0;
                break;
        }
    }

    delete_all();  /* free any structures */
    return 0;
}

matters needing attention

1. If in Android/gcc Compile times fall-through between switch labels, You can use pragma The sentence put uthash The relevant code is enclosed

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
// uthash Related codes 
#pragma GCC diagnostic pop

Actually, it can be used __attribute__ ((fallthrough)); But the actual measurement did not pragma This method is good .

1. If compiling times padding struct 'struct UT_hash_table' with 4 bytes to align 'tail', May, in accordance with the https://github.com/troydhanson/uthash/issues/118#issue-223582662 Answer , adjustment uthash.h The order of variables in

2. If you want to be HashSet use , You may also need to declare an additional variable , Otherwise, there may be padding The problem of , newspaper padding struct 'struct fd_struct' with 4 bytes to align 'hh', as follows ：

struct fd_struct {
    int fd; // key
    int padding; //  For filling , Or is it char padding[10] And so on. ;
    UT_hash_handle hh;
};