一、简介

1.1 介绍

utlist.h中包含了一组用于C结构体的通用链表宏。使用起来非常简单，只需要将utlist.h拷贝到你的项目，并包含进你的源码即可：

#include "utlist.h"

utlist.h宏提供了基本的链表操作：添加、删除、排序、遍历。

1.2 源码获取

utlist.h的源码可以在GitHub上直接获取(src/utlist.h)：

https://github.com/troydhanson/uthash

1.3 链表类型

utlist.h支持下面三种类型的链表：

• 单向链表
• 双向链表
• 环形双向链表

1.4 使用效率

• 头部添加：对所有的链表类型都是常量；
• 尾部添加：单向链表O(n)；双向链表是常量；
• 删除：单向链表O(n)；双向链表是常量；
• 排序：对所有链表类型都是O(n log(n))；
• 有序链表遍历：对所有链表类型都是O(n)；
• 无序链表遍历：对所有链表类型都是O(n)；

二、使用

2.1 定义结构体

你可以对任何数据结构使用utlist.h宏。只需要在你的结构体中定义一个next指针即可使用单向链表，再定义一个prev即可使用双向链表。

typedef struct element {
    char *name;
    struct element *prev; /* needed for a doubly-linked list only */
    struct element *next; /* needed for singly- or doubly-linked lists */
} element;

2.2 定义链表头

链表头是一个简单的指针，你可以按自己喜好命名，但需要注意：定义时必须初始化为NULL。

element *head = NULL;

2.3 常用操作

下表列出了utlist.h支持的所有插入、删除、排序和遍历宏。

Singly-linked	Doubly-linked	Circular, doubly-linked
LL_PREPEND(head,add);	DL_PREPEND(head,add);	CDL_PREPEND(head,add);
LL_PREPEND_ELEM(head,ref,add);	DL_PREPEND_ELEM(head,ref,add);	CDL_PREPEND_ELEM(head,ref,add);
LL_APPEND_ELEM(head,ref,add);	DL_APPEND_ELEM(head,ref,add);	CDL_APPEND_ELEM(head,ref,add);
LL_REPLACE_ELEM(head,del,add);	DL_REPLACE_ELEM(head,del,add);	CDL_REPLACE_ELEM(head,del,add);
LL_APPEND(head,add);	DL_APPEND(head,add);	CDL_APPEND(head,add);
LL_INSERT_INORDER(head,add,cmp);	DL_INSERT_INORDER(head,add,cmp);	CDL_INSERT_INORDER(head,add,cmp);
LL_CONCAT(head1,head2);	DL_CONCAT(head1,head2);
LL_DELETE(head,del);	DL_DELETE(head,del);	CDL_DELETE(head,del);
LL_SORT(head,cmp);	DL_SORT(head,cmp);	CDL_SORT(head,cmp);
LL_FOREACH(head,elt) {…}	DL_FOREACH(head,elt) {…}	CDL_FOREACH(head,elt) {…}
LL_FOREACH_SAFE(head,elt,tmp) {…}	DL_FOREACH_SAFE(head,elt,tmp) {…}	CDL_FOREACH_SAFE(head,elt,tmp1,tmp2) {…}
LL_SEARCH_SCALAR(head,elt,mbr,val);	DL_SEARCH_SCALAR(head,elt,mbr,val);	CDL_SEARCH_SCALAR(head,elt,mbr,val);
LL_SEARCH(head,elt,like,cmp);	DL_SEARCH(head,elt,like,cmp);	CDL_SEARCH(head,elt,like,cmp);
LL_LOWER_BOUND(head,elt,like,cmp);	DL_LOWER_BOUND(head,elt,like,cmp);	CDL_LOWER_BOUND(head,elt,like,cmp);
LL_COUNT(head,elt,count);	DL_COUNT(head,elt,count);	CDL_COUNT(head,elt,count);

宏使用说明：

• PREPEND是向链表头插入一个元素，然后修改链表头指向刚插入的元素；
• APPEND是向链表尾插入一个元素，新插入的元素变成链表的尾；
• CONCAT用于连接两个链表，将第二个链表连接到第一个链表尾；
• 若想在任意元素位置（而不是链表头部）前面进行插入，请使用_PREPEND_ELEM宏家族；
• 若想在任意元素位置（而不是列表尾部）后面进行追加，请使用_APPEND_ELEM宏家族；
• 若想用另一个元素替换任意表元素，请使用_REPLACE_ELEM宏家族；
• SORT排序操作从不会移动元素在内存的位置，而仅仅是调整元素的prev和next指针。因此也可能会修改链表头指向另一个链表中的元素；
• FOREACH是一个简单的遍历链表的方法，你也可以通过prev和next来遍历链表，不过如果你在遍历时删除元素，建议你使用FOREACH_SAFE；
• SEARCH是在搜索特定元素的快捷方法（相对FOREACH而言，并不是更快，而是更好用而已）：SEARCH_SCALAR版本使用简单的比较函数来搜索；SEARCH则使用用户指定的cmp函数进行比较；
• LOWER_BOUND从链表中寻找第一个不大于like的元素，比较方法使用用户提供的cmp函数；
• COUNT操作遍历链表，并将计数统计到count中；

宏使用的参数说明：

• head：The list head (a pointer to your list element structure).
• add：A pointer to the list element structure you are adding to the list.
• del：A pointer to the list element structure you are replacing or deleting from the list.
• elt：A pointer that will be assigned to each list element in succession (see example) in the case of iteration macros; or, the output pointer from the search macros.
• ref：Reference element for prepend and append operations that will be prepended before or appended after. If ref is a pointer with value NULL, the new element will be appended to the list for _PREPEND_ELEM() operations and prepended for _APPEND_ELEM() operations. ref must be the name of a pointer variable and cannot be literally NULL, use _PREPEND() and _APPEND() macro family instead.
• like：An element pointer, having the same type as elt, for which the search macro seeks a match (if found, the match is stored in elt). A match is determined by the given cmp function.
• cmp：pointer to comparison function which accepts two arguments-- these are pointers to two element structures to be compared. The comparison function must return an int that is negative, zero, or positive, which specifies whether the first item should sort before, equal to, or after the second item, respectively. (In other words, the same convention that is used by strcmp). Note that under Visual Studio 2008 you may need to declare the two arguments as void * and then cast them back to their actual types.
• tmp：A pointer of the same type as elt. Used internally. Need not be initialized.
• mbr：In the scalar search macro, the name of a member within the elt structure which will be tested (using ==) for equality with the value val.
• val：In the scalar search macro, specifies the value of (of structure member field) of the element being sought.
• count：integer which will be set to the length of the list

2.4 一个例程

下面的例子用于从文件读取所有名字，并将读取到的名字添加到一个双向链表中，然后对其进行排序后输出。

/* A doubly-linked list */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utlist.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next, *prev;
} el;

int namecmp(el *a, el *b) {
    return strcmp(a->bname,b->bname);
}

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *name, *elt, *tmp, etmp;

    char linebuf[BUFLEN];
    int count;
    FILE *file;

    if ( (file = fopen( "test11.dat", "r" )) == NULL ) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf,BUFLEN,file) != NULL) {
        if ( (name = (el *)malloc(sizeof *name)) == NULL) exit(-1);
        strcpy(name->bname, linebuf);
        DL_APPEND(head, name);
    }
    DL_SORT(head, namecmp);
    DL_FOREACH(head,elt) printf("%s", elt->bname);
    DL_COUNT(head, elt, count);
    printf("%d number of elements in list\n", count);

    memcpy(&etmp.bname, "WES\n", 5);
    DL_SEARCH(head,elt,&etmp,namecmp);
    if (elt) printf("found %s\n", elt->bname);

    /* now delete each element, use the safe iterator */
    DL_FOREACH_SAFE(head,elt,tmp) {
      DL_DELETE(head,elt);
      free(elt);
    }

    fclose(file);

    return 0;
}

2.5 其他操作

当你定义的prev和next名字不是标准的prev与next，你可以使用下面所提供的宏。

Singly-linked	Doubly-linked	Circular, doubly-linked
LL_PREPEND2(head,add,next);	DL_PREPEND2(head,add,prev,next);	CDL_PREPEND2(head,add,prev,next);
LL_PREPEND_ELEM2(head,ref,add,next);	DL_PREPEND_ELEM2(head,ref,add,prev,next);	CDL_PREPEND_ELEM2(head,ref,add,prev,next);
LL_APPEND_ELEM2(head,ref,add,next);	DL_APPEND_ELEM2(head,ref,add,prev,next);	CDL_APPEND_ELEM2(head,ref,add,prev,next);
LL_REPLACE_ELEM2(head,del,add,next);	DL_REPLACE_ELEM2(head,del,add,prev,next);	CDL_REPLACE_ELEM2(head,del,add,prev,next);
LL_APPEND2(head,add,next);	DL_APPEND2(head,add,prev,next);	CDL_APPEND2(head,add,prev,next);
LL_INSERT_INORDER2(head,add,cmp,next);	DL_INSERT_INORDER2(head,add,cmp,prev,next);	CDL_INSERT_INORDER2(head,add,cmp,prev,next);
LL_CONCAT2(head1,head2,next);	DL_CONCAT2(head1,head2,prev,next);
LL_DELETE2(head,del,next);	DL_DELETE2(head,del,prev,next);	CDL_DELETE2(head,del,prev,next);
LL_SORT2(head,cmp,next);	DL_SORT2(head,cmp,prev,next);	CDL_SORT2(head,cmp,prev,next);
LL_FOREACH2(head,elt,next) {…}	DL_FOREACH2(head,elt,next) {…}	CDL_FOREACH2(head,elt,next) {…}
LL_FOREACH_SAFE2(head,elt,tmp,next) {…}	DL_FOREACH_SAFE2(head,elt,tmp,next) {…}	CDL_FOREACH_SAFE2(head,elt,tmp1,tmp2,prev,next) {…}
LL_SEARCH_SCALAR2(head,elt,mbr,val,next);	DL_SEARCH_SCALAR2(head,elt,mbr,val,next);	CDL_SEARCH_SCALAR2(head,elt,mbr,val,next);
LL_SEARCH2(head,elt,like,cmp,next);	DL_SEARCH2(head,elt,like,cmp,next);	CDL_SEARCH2(head,elt,like,cmp,next);
LL_LOWER_BOUND2(head,elt,like,cmp,next);	DL_LOWER_BOUND2(head,elt,like,cmp,next);	CDL_LOWER_BOUND2(head,elt,like,cmp,next);
LL_COUNT2(head,elt,count,next);	DL_COUNT2(head,elt,count,next);	CDL_COUNT2(head,elt,count,next);