Linux三方库读书程序员

优秀开源库utash之utlist.h

2019-03-27  本文已影响6人  konishi5202

一、简介

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 使用效率

二、使用

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);

宏使用说明:

宏使用的参数说明:

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);
上一篇 下一篇

猜你喜欢

热点阅读