userguide.txt

uthash 是一个C语言的哈希表

    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; 

  while(users) { 
    current_user = users;          /* grab pointer to first item */
    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=s->hh.next) {
        printf("user id %d: name %s\n", 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);
}
----------------------------------------------------------------------

.A complete program (part 2 of 2)
----------------------------------------------------------------------
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;
    struct my_struct *s;
    unsigned num_users;

    while (1) {
        printf("1. add user\n");
        printf("2. find user\n");
        printf("3. delete user\n");
        printf("4. delete all users\n");
        printf("5. sort items by name\n");
        printf("6. sort items by id\n");
        printf("7. print users\n");
        printf("8. count users\n");
        gets(in);
        switch(atoi(in)) {
            case 1:
                printf("name?\n");
                add_user(id++, gets(in));
                break;
            case 2:
                printf("id?\n");
                s = find_user(atoi(gets(in)));
                printf("user: %s\n", s ? s->name : "unknown");
                break;
            case 3:
                printf("id?\n");
                s = find_user(atoi(gets(in)));
                if (s) delete_user(s);
                else printf("id unknown\n");
                break;
            case 4:
                delete_all();
                break;
            case 5:
                sort_by_name();
                break;
            case 6:
                sort_by_id();
                break;
            case 7:
                print_users();
                break;
            case 8:
                num_users=HASH_COUNT(users);
                printf("there are %u users\n", num_users);
                break;
        }
    }
}
----------------------------------------------------------------------

This program is included in the distribution in `tests/example.c`. You can run
`make example` in that directory to compile it easily.

Kinds of keys
-------------

Integer keys
~~~~~~~~~~~~
The preceding examples demonstrated use of integer keys. To recap, use the
convenience macros `HASH_ADD_INT` and `HASH_FIND_INT` for structures with
integer keys. (The other operations such as `HASH_DELETE` and `HASH_SORT` are
the same for all types of keys).

String keys
~~~~~~~~~~~
String keys are handled almost the same as integer keys. The convenience macros
for dealing with string keys are called `HASH_ADD_STR` and `HASH_FIND_STR`.

[NOTE]
.char[ ] vs. char* 
================================================================================
The string is 'within' the structure in the next example-- `name` is a
`char[10]` field.  If instead our structure merely 'pointed' to the key (i.e.,
`name` was declared `char *`), we'd use `HASH_ADD_KEYPTR`, described in
<<Appendix_F,Appendix F>>.
================================================================================

.A string-keyed hash
----------------------------------------------------------------------
#include <string.h>  /* strcpy */
#include <stdlib.h>  /* malloc */
#include <stdio.h>   /* printf */
#include "uthash.h"

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


int main(int argc, char *argv[]) {
    char **n, *names[] = { "joe", "bob", "betty", NULL };
    struct my_struct *s, *users = NULL;
    int i=0;

    for (n = names; *n != NULL; n++) {
        s = malloc(sizeof(struct my_struct));
        strcpy(s->name, *n);
        s->id = i++;
        HASH_ADD_STR( users, name, s );  
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d\n", s->id);
}
----------------------------------------------------------------------

This example is included in the distribution in `tests/test15.c`. It prints:

    betty's id is 2

Binary keys
~~~~~~~~~~~
We're using the term "binary" here to simply mean an arbitrary byte sequence.
Your key field can have any data type. To uthash, it is just a sequence of
bytes.  We'll use the general macros `HASH_ADD` and `HASH_FIND` to demonstrate
usage of a floating point key of type `double`.

.A key of type double
----------------------------------------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include "uthash.h"

typedef struct {
    double veloc; 
    /* ... other data ... */
    UT_hash_handle hh;
} veloc_t;

int main(int argc, char *argv[]) {
    veloc_t *v, *v2, *veloc_table = NULL;
    double x = 1/3.0;

    v = malloc( sizeof(*v) );
    v->veloc = x;
    HASH_ADD(hh, veloc_table, veloc, sizeof(double), v);
    HASH_FIND(hh, veloc_table, &x, sizeof(double), v2 );

    if (v2) printf("found (%.2f)\n", v2->veloc);
}
----------------------------------------------------------------------

Note that the general macros require the name of the `UT_hash_handle` to be
passed as the first argument (here, this is `hh`). The general macros are 
documented in <<Appendix_F,Appendix F: Macro Reference>>. 

Multi-field keys
~~~~~~~~~~~~~~~~
Your key can even comprise multiple contiguous fields. 

.A multi-field key
----------------------------------------------------------------------
#include <stdlib.h>    /* malloc       */
#include <stddef.h>    /* offsetof     */
#include <stdio.h>     /* printf       */
#include <string.h>    /* memset       */
#include "uthash.h"

#define UTF32 1

typedef struct {
  UT_hash_handle hh;
  int len;
  char encoding;      /* these two fields */
  int text[];         /* comprise the key */
} msg_t;

int main(int argc, char *argv[]) {
    int keylen;
    msg_t *msg, *msgs = NULL;
    struct { char encoding; int text[]; } *lookup_key;

    int beijing[] = {0x5317, 0x4eac};   /* UTF-32LE for 北京 */

    /* allocate and initialize our structure */
    msg = malloc( sizeof(msg_t) + sizeof(beijing) );
    memset(msg, 0, sizeof(msg_t)+sizeof(beijing)); /* zero fill */
    msg->len = sizeof(beijing);
    msg->encoding = UTF32;
    memcpy(msg->text, beijing, sizeof(beijing));

    /* calculate the key length including padding, using formula */
    keylen =   offsetof(msg_t, text)       /* offset of last key field */
             + sizeof(beijing)             /* size of last key field */
             - offsetof(msg_t, encoding);  /* offset of first key field */

    /* add our structure to the hash table */
    HASH_ADD( hh, msgs, encoding, keylen, msg);

    /* look it up to prove that it worked :-) */
    msg=NULL;

    lookup_key = malloc(sizeof(*lookup_key) + sizeof(beijing));
    memset(lookup_key, 0, sizeof(*lookup_key) + sizeof(beijing));
    lookup_key->encoding = UTF32;
    memcpy(lookup_key->text, beijing, sizeof(beijing));
    HASH_FIND( hh, msgs, &lookup_key->encoding, keylen, msg );
    if (msg) printf("found \n");
    free(lookup_key);
}
----------------------------------------------------------------------

This example is included in the distribution in `tests/test22.c`.

If you use multi-field keys, recognize that the compiler pads adjacent fields
(by inserting unused space between them) in order to fulfill the alignment
requirement of each field. For example a structure containing a `char` followed
by an `int` will normally have 3 "wasted" bytes of padding after the char, in
order to make the `int` field start on a multiple-of-4 address (4 is the length
of the int). 

.Calculating the length of a multi-field key:
*******************************************************************************
To determine the key length when using a multi-field key, you must include any
intervening structure padding the compiler adds for alignment purposes.

An easy way to calculate the key length is to use the `offsetof` macro from
`<stddef.h>`.  The formula is:

     key length =   offsetof(last_key_field) 
                  + sizeof(last_key_field) 
                  - offsetof(first_key_field)

In the example above, the `keylen` variable is set using this formula.
*******************************************************************************

When dealing with a multi-field key, you must zero-fill your structure before
`HASH_ADD`'ing it to a hash table, or using its fields in a `HASH_FIND` key.

In the previous example, `memset` is used to initialize the structure by
zero-filling it. This zeroes out any padding between the key fields. If we
didn't zero-fill the structure, this padding would contain random values.  The
random values would lead to `HASH_FIND` failures; as two "identical" keys will
appear to mismatch if there are any differences within their padding.

Structures in multiple hash tables
----------------------------------

A structure can be added to multiple hash tables. A few reasons you might do
this include:

- each hash table may use an alternative key; 
- each hash table may have its own sort order; 
- or you might simply use multiple hash tables for grouping purposes.  E.g.,
  you could have users in an `admin_users` and a `users` hash table. 

Your structure needs to have a `UT_hash_handle` field for each hash table to
which it might be added. You can name them anything. E.g.,

  UT_hash_handle hh1, hh2;

Alternative keys on the same structure
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
You might create a hash table keyed on an ID field, and another hash table
keyed on username (if they are unique). You can add the same user structure to
both hash tables, then look up a user by either their unique ID or username.

.A structure with two alternative keys
----------------------------------------------------------------------
struct my_struct {
    int id;                    /* key 1 */
    char username[10];         /* key 2 */
    UT_hash_handle hh1,hh2;    /* makes this structure hashable */
};
----------------------------------------------------------------------

In the example above, the structure can now be added to two separate hash
tables. In one hash, `id` is its key, while in the other hash, `username` is
its key.  (There is no requirement that the two hashes have different key
fields. They could both use the same key, such as `id`).

Notice the structure has two hash handles (`hh1` and `hh2`).  In the code
below, notice that each hash handle is used exclusively with a particular hash
table.  (`hh1` is always used with the `users_by_id` hash, while `hh2` is
always used with the `users_by_name` hash table).

.Two keys on a structure
----------------------------------------------------------------------
    struct my_struct *users_by_id = NULL, *users_by_name = NULL, *s;
    int i;
    char *name;

    s = malloc(sizeof(struct my_struct));
    s->id = 1;
    strcpy(s->username, "thanson");

    /* add the structure to both hash tables */
    HASH_ADD(hh1, users_by_id, id, sizeof(int), s);
    HASH_ADD(hh2, users_by_name, username, strlen(s->username), s);

    /* lookup user by ID in the "users_by_id" hash table */
    i=1;
    HASH_FIND(hh1, users_by_id, &i, sizeof(int), s);
    if (s) printf("found id %d: %s\n", i, s->username);

    /* lookup user by username in the "users_by_name" hash table */
    name = "thanson";
    HASH_FIND(hh2, users_by_name, name, strlen(name), s);
    if (s) printf("found user %s: %d\n", name, s->id);
----------------------------------------------------------------------


Multiple sort orders
~~~~~~~~~~~~~~~~~~~~
Extending the previous example, suppose we have many users in our `users_by_id`
and our `users_by_name` hash, and that we want to sort each hash so that we can 
print the keys in order. We'd define two sort functions, then use `HASH_SRT`:

  int sort_by_id(struct my_struct *a, struct my_struct *b) {
    if (a->id == b->id) return 0;
    return (a->id < b->id) ? -1 : 1;
  }

  int sort_by_name(struct my_struct *a, struct my_struct *b) {
    return strcmp(a->username,b->username);
  }

  HASH_SRT(hh1, users_by_id, sort_by_id);
  HASH_SRT(hh2, users_by_name, sort_by_name);

  /* now iterate over users_by_id and users_by_name in sorted order */


[[Appendix_A]]
Appendix A: Built-in hash functions
-----------------------------------
Internally, a hash function transforms a key into a bucket number.  You don't
have to take any action to use the default hash function, Jenkin's hash. 

Some programs may benefit from using another of the built-in hash functions.
There is a simple analysis utility included with uthash to help you determine
if another hash function will give you better performance.

You can use a different hash function by compiling your program with
`-DHASH_FUNCTION=HASH_xyz` where `xyz` is one of the symbolic names listed
below. E.g., 

    cc -DHASH_FUNCTION=HASH_BER -o program program.c

.Built-in hash functions
[width="50%",cols="^5m,20",grid="none",options="header"]
|===============================================================================
|Symbol |   Name    
|JEN    |   Jenkins (default)
|BER    |   Bernstein
|SAX    |   Shift-Add-Xor
|OAT    |   One-at-a-time
|FNV    |   Fowler/Noll/Vo