userguide.txt

uthash 是一个C语言的哈希表

uthash User Guide
=================
Troy D. Hanson <[e-mail]>
v1.5, February 2009

include::sflogo.txt[]
include::topnav.txt[]

A hash in C
-----------
include::toc.txt[]

This document is written for C programmers. Since you're reading this, chances
are that you know a hash is used for looking up items using a key. In scripting
languages like Perl, hashes are used all the time.  In C, hashes don't exist in
the language itself. This software provides a hash table for C structures.  

What can it do?
~~~~~~~~~~~~~~~~~
This software supports these basic operations on items in a hash table:

1. add
2. find
3. delete
4. count
5. iterate
6. sort

Is it fast?
~~~~~~~~~~~
Add, find and delete are normally constant-time operations. This is influenced
by your key domain and the hash function. 

This hash aims to be minimalistic and efficient. It's around 600 lines of C.
It inlines automatically because it's implemented as macros. It's fast as long
as the hash function is suited to your keys. You can use the default hash
function, or easily compare performance and choose from among several other
<<Appendix_A,built-in hash functions>>. 

Is it a library?
~~~~~~~~~~~~~~~~
No, it's just a single header file: `uthash.h`.  All you need to do is copy
the header file into your project, and:

    #include "uthash.h"

Since uthash is a header file only, there is no library code to link against.

C/C++ and platforms
~~~~~~~~~~~~~~~~~~~
This software can be used in C and C++ programs.  It has been tested on:

 * Linux
 * Mac OS X
 * Solaris 
 * OpenBSD
 * Cygwin
 * MinGW

Test suite
^^^^^^^^^^
You can run the test suite on these platforms, or any prospective Unix-like
platform, in this way:

  cd tests/
  make


BSD licensed
~~~~~~~~~~~~
This software is made available under the 
link:license.html[revised BSD license]. 
It is free and open source. 

Obtaining uthash
~~~~~~~~~~~~~~~~
Please follow the link to download on the 
http://uthash.sourceforge.net[uthash website] at http://uthash.sourceforge.net.

Getting help
~~~~~~~~~~~~
Feel free to mailto:[e-mail][email the author] at
[e-mail].

Resources
~~~~~~~~~
News::
 The author has a news feed for http://troydhanson.wordpress.com/feed/[software updates] image:img/rss.png[(RSS)].

Who's using it?
~~~~~~~~~~~~~~~
Since releasing uthash in 2006, it has been downloaded thousands of times,
incorporated into commerical software, academic research, and into other
open-source software.  

Your structure
--------------

In uthash, a hash table is comprised of structures. Each structure represents a
key-value association. One or more of the structure fields constitute the key;
the structure itself is the value.

.Defining a structure that can be hashed
----------------------------------------------------------------------
#include "uthash.h"

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

The key
~~~~~~~
There are no restrictions on the data type or name of the key field. The key
can also comprise multiple contiguous fields, having any names and data types.

.Any data type... really?
*****************************************************************************
Yes, your key and structure can have any data type. Unlike function calls with
fixed prototypes, uthash consists of macros-- whose arguments are untyped-- and
thus able to work with any type of structure or key.  
*****************************************************************************

Unique keys
^^^^^^^^^^^
As with any hash, every item must have a unique key.  Your application must
enforce key uniqueness. Before you add an item to the hash table, you must
first know (if in doubt, check!) that the key is not already in use.  You
can check whether a key already exists in the hash table using `HASH_FIND`.

The hash handle
~~~~~~~~~~~~~~~
The `UT_hash_handle` field must be present in your structure.  It is used for
the internal bookkeeping that makes the hash work.  It does not require
initialization. It can be named anything, but you can simplify matters by
naming it `hh`. This allows you to use the easier "convenience" macros to add,
find and delete items.

Add, find, delete, count, sort, iterate
---------------------------------------

This section introduces the uthash macros by example. For a more succinct
listing, see <<Appendix_F,Appendix F: Macro Reference>>. 

.Convenience vs. general macros:
*****************************************************************************
The uthash macros fall into two categories. The 'convenience' macros can be used
with integer or string keys (and require that you chose the conventional
name `hh` for the `UT_hash_handle` field).  The convenience macros take fewer
arguments than the general macros, making their usage a bit simpler for these
common types of keys. 

The 'general' macros can be used for any types of keys, or for multi-field keys,
or when the `UT_hash_handle` has been named something other than `hh`. These
macros take more arguments and offer greater flexibility in return. But if the
convenience macros suit your needs, use them-- your code will be more readable.
*****************************************************************************

Declare the hash
~~~~~~~~~~~~~~~~
Your hash must be declared as a `NULL`-initialized pointer to your structure.

  struct my_struct *users = NULL;    /* important! initialize to NULL */

Add item
~~~~~~~~
Allocate and initialize your structure as you see fit. The only aspect
of this that matters to uthash is that your key must be initialized to
a unique value. Then call `HASH_ADD`. (Here we use the convenience macro
`HASH_ADD_INT`, which offers simplified usage for keys of type `int`).

.Add an item to a hash
----------------------------------------------------------------------
int add_user(int user_id, char *name) {
    struct my_struct *s;

    s = malloc(sizeof(struct my_struct));
    s->id = user_id;
    strcpy(s->name, name);
    HASH_ADD_INT( users, id, s );  /* id: name of key field */
}
----------------------------------------------------------------------

The first parameter to `HASH_ADD_INT` is the hash table, and the
second parameter is the 'name' of the key field. Here, this is `id`. The
last parameter is a pointer to the structure being added.

[[validc]]
.Wait.. the field name is a parameter?
*******************************************************************************
If you find it strange that `id`, which is the 'name of a field' in the
structure, can be passed as a parameter, welcome to the world of macros. Don't
worry- the C preprocessor expands this to valid C code. 
*******************************************************************************

Key must not be modified while in-use
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Once a structure has been added to the hash, do not change the value of its key.
Instead, delete the item from the hash, change the key, and then re-add it.

Find item 
~~~~~~~~~
To look up a structure in a hash, you need its key.  Then call `HASH_FIND`.
(Here we use the convenience macro `HASH_FIND_INT` for keys of type `int`).

.Find a structure using its key
----------------------------------------------------------------------
struct my_struct *find_user(int user_id) {
    struct my_struct *s;

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

Here, the hash table is `users`, and `&user_id` points to the key (an integer
in this case).  Last, `s` is the 'output' variable of `HASH_FIND_INT`. The 
final result is that `s` points to the structure with the given key, or
is `NULL` if the key wasn't found in the hash.

[NOTE]
The middle argument is a 'pointer' to the key. You can't pass a literal key
value to `HASH_FIND`. Instead assign the literal value to a variable, and pass
a pointer to the variable.


Delete item
~~~~~~~~~~~
To delete a structure from a hash, you must have a pointer to it. (If you only
have the key, first do a `HASH_FIND` to get the structure pointer).

.Delete an item from a hash
----------------------------------------------------------------------
void delete_user(struct my_struct *user) {
    HASH_DEL( users, user);  /* user: pointer to deletee */
    free(user);              /* optional; it's up to you! */
}
----------------------------------------------------------------------

Here again, `users` is the hash table, and `user` is a pointer to the
structure we want to remove from the hash.

uthash never frees your structure
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Deleting a structure just removes it from the hash table-- it doesn't `free`
it.  The choice of when to free your structure is entirely up to you; uthash
will never free your structure.

Delete can change the pointer
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The hash table pointer (which initially points to the first item added to the
hash) can change in response to `HASH_DEL` (i.e. if you delete the first item
in the hash table).

Delete all items
~~~~~~~~~~~~~~~~
To delete all the structures in a hash table, you need to iteratively delete.
It's easy: just keep deleting the first item. If you plan to free it, copy the
pointer beforehand since the delete will advance the "first item" to the next.

.Delete all items from a hash
----------------------------------------------------------------------
void delete_all() {
  user_struct *current_user; 

  while(users) { 
    current_user = users;          /* copy pointer to first item     */
    HASH_DEL(users,current_user);  /* delete; users advances to next */
    free(current_user);            /* optional- if you want to free  */
  } 
}
----------------------------------------------------------------------

If you only want to delete all the items, but not free them, you can write this
even more concisely as 

  while (users) HASH_DEL(users,users);

Count items
~~~~~~~~~~~

The number of items in the hash table can be obtained using `HASH_COUNT`:

.Count of items in the hash table
----------------------------------------------------------------------
unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);
----------------------------------------------------------------------

Incidentally, this works even the list (`users`, here) is `NULL`, in 
which case the count is 0.

Iterating and sorting 
~~~~~~~~~~~~~~~~~~~~~

You can loop over the items in the hash by starting from the beginning and
following the `hh.next` pointer.

.Iterating over all the items in a hash
----------------------------------------------------------------------
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);
    }
}
----------------------------------------------------------------------

There is also an `hh.prev` pointer you could use to iterate backwards through
the hash, starting from any known item.

.A hash is also a doubly-linked list.
*******************************************************************************
Iterating backward and forward through the items in the hash is possible
because of the `hh.prev` and `hh.next` fields. All the items in the hash can
be reached by repeatedly following these pointers, thus the hash is also a
doubly-linked list. 
*******************************************************************************

If you're using uthash in a C++ program, you need an extra cast on the `for`
iterator, e.g., `s=(struct my_struct*)s->hh.next`.

Sorted iteration
^^^^^^^^^^^^^^^^
The items in the hash are, by default, traversed in the order they were added
("insertion order") when you follow the `hh.next` pointer. But you can sort
the items into a new order using `HASH_SORT`. E.g.,

    HASH_SORT( users, name_sort );

The second argument is a pointer to a comparison function. It must accept two
arguments which are pointers to two items to compare. Its return value should
be less than zero, zero, or greater than zero, if the first item sorts before,
equal to, or after the second item, respectively. (Just like `strcmp`).

.Sorting the items in the hash
----------------------------------------------------------------------
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);
}
----------------------------------------------------------------------

When the items in the hash are sorted, the first item may change position.  In
the example above, `users` may point to a different structure after calling
`HASH_SORT`.

A complete example
~~~~~~~~~~~~~~~~~~

We'll repeat all the code and embellish it with a `main()` function to form a
working example. 

If this code was placed in a file called `example.c` in the same directory as
`uthash.h`, it could be compiled and run like this:

    cc -o example example.c
    ./example

Follow the prompts to try the program, and type `Ctrl-C` when done.

.A complete program (part 1 of 2)
----------------------------------------------------------------------
#include <stdio.h>   /* gets */
#include <stdlib.h>  /* atoi, malloc */
#include <string.h>  /* strcpy */
#include "uthash.h"

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

struct my_struct *users = NULL;

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

    s = malloc(sizeof(struct my_struct));
    s->id = user_id;
    strcpy(s->name, name);
    HASH_ADD_INT( users, id, s );  /* id: name of key field */
}

struct my_struct *find_user(int user_id) {