双链表示例
1. 简介
本双链表的实现主要参考了kernel中的双链表。
实现由3个文件组成:
- db_list.h 双链表定义及相关的API
- db_list.c 双链表的实现
- test1.c 测试程序
2. db_list.h
/**
* db_list.h : public header for application
*/
#ifndef DB_LIST_H
#define DB_LIST_H
#include <stdint.h>
/**
* Basic structures
*/
typedef void info_t;
typedef struct node {
info_t *info;
struct node *next;
struct node *prev;
} node_t;
typedef struct list {
node_t *head;
node_t *tail;
node_t *current;
size_t info_size;
unsigned long current_index;
unsigned long list_size;
} list_t;
/**
* Prototypes
*/
/* List initialization routines */
list_t *list_create(list_t ** list);
int list_init(list_t * list, size_t info_size);
void list_destroy(list_t ** list);
/* Status and state routines */
int list_empty(list_t * list);
unsigned long get_list_size(list_t * list);
/* List update routines */
int list_add(list_t * list, info_t * info);
int list_add_tail(list_t * list, info_t * info);
int list_replace(list_t * list, node_t * new_node);
int list_del(list_t * list);
int list_clear(list_t * list);
int list_move(list_t * list, list_t * list_a);
int list_move_tail(list_t * list, list_t * list_a);
/* List search routines */
int find_record(list_t * list, info_t * match, int (*cmp) (info_t *, info_t *));
info_t *get_current_record(list_t * list);
info_t *get_next_record(list_t * list);
info_t *get_prev_record(list_t * list);
info_t *get_first_record(list_t * list);
info_t *get_last_record(list_t * list);
/* Input/Output routines */
int export_list(list_t * list, const char *path);
int import_list(list_t * list, const char *path);
#endif /* DB_LIST_H */2. db_list.c
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <strings.h>
#include "db_list.h"
/**
* create a struct of type list_t
*/
list_t *list_create(list_t ** list)
{
if ((*list = (list_t *) malloc(sizeof(list_t))) == NULL)
return (NULL);
return *list;
}
/**
* initialize double linked list.
*/
int list_init(list_t * list, size_t info_size)
{
if (info_size == (size_t) 0) {
perror("info size should not be zero!\n");
return -1;
}
if (list == NULL) {
perror("list it null\n");
return -1;
}
list->head = NULL;
list->tail = NULL;
list->current = NULL;
list->info_size = info_size;
list->list_size = 0L;
list->current_index = 0L;
return 0;
}
/**
* destroy_list - destroy the list and all of its members
*/
void list_destroy(list_t ** list)
{
if (*list == NULL) {
perror("list it null\n");
return;
}
list_clear(*list);
free(*list);
*list = NULL;
}
/**
* tests whether the list is empty
*/
int list_empty(list_t * list)
{
if ((list->head == NULL) || (list->tail == NULL))
return 0;
return -1;
}
unsigned long get_list_size(list_t * list)
{
if (list_empty(list) == 0)
return 0;
return list->list_size;
}
int list_add(list_t * list, info_t * info)
{
node_t *new_node;
if ((new_node = (node_t *) malloc(sizeof(node_t))) == NULL)
return -1;
/* first node */
if (list->head == NULL) {
new_node->info = info;
new_node->prev = NULL;
new_node->next = NULL;
list->head = new_node;
list->tail = new_node;
list->current = new_node;
list->current_index = 1L;
list->list_size = 1L;
return 0;
}
new_node->info = info;
new_node->prev = list->current;
new_node->next = list->current->next;
if (list->current->next != NULL)
list->current->next->prev = new_node;
else
list->tail = new_node;
list->current->next = new_node;
list->current = new_node;
list->current_index++;
list->list_size++;
return 0;
}
int list_add_tail(list_t * list, info_t * info)
{
node_t *new_node;
if ((new_node = (node_t *) malloc(sizeof(node_t))) == NULL)
return -1;
if (list->head == NULL) {
new_node->info = info;
new_node->prev = NULL;
new_node->next = NULL;
list->head = new_node;
list->tail = new_node;
list->current = new_node;
list->current_index = 1L;
list->list_size = 1;
return 0;
}
new_node->info = info;
new_node->next = NULL;
new_node->prev = list->current;
list->current->next = new_node;
list->current = new_node;
list->tail = new_node;
list->current_index++;
list->list_size++;
return 0;
}
int record_update(list_t * list, info_t * record)
{
return 0;
list_del(list);
list_add(list, record);
}
int list_del(list_t * list)
{
node_t *old_node;
info_t *old_info;
if (list->current == NULL)
return -1;
old_node = list->current;
old_info = list->current->info;
if (list->current == list->head) { /* current is first record */
if (list->current->next != NULL)
list->current->next->prev = NULL;
list->head = list->current->next;
list->current = list->head;
} else if (list->current == list->tail) { /* current is last record */
list->current->prev->next = NULL;
list->tail = list->current->prev;
list->current = list->tail;
list->current_index--;
} else { /* current is a middle record */
list->current->prev->next = list->current->next;
list->current->next->prev = list->current->prev;
list->current = list->current->next;
}
free(old_info);
free(old_node);
list->list_size--;
return 0;
}
int list_clear(list_t * list)
{
node_t *old_node;
info_t *old_info;
if (list->head == NULL)
return -1;
while (list->head) {
old_node = list->head;
old_info = list->head->info;
list->head = list->head->next;
free(old_info);
free(old_node);
}
return 0;
}
int find_record(list_t * list, info_t * match, int (*cmp) (info_t *, info_t *))
{
if (list->head == NULL || cmp == NULL)
return -1;
list_t *tmplist;
tmplist=list_create(&tmplist);
list->current = list->head;
list->current_index = 1;
/* save current state */
tmplist->head = list->head;
tmplist->current = list->current;
tmplist->current_index=list->current_index;
tmplist->tail = list->tail;
while (list->current) {
if ((cmp(list->current->info, match)) != 0) {
list->current = list->current->next;
list->current_index++;
}else {
list->current = tmplist->current;
list->current_index = list->current_index;
free(tmplist);
return 0;
}
}
list->current = tmplist->current;
list->current_index = list->current_index;
free(tmplist);
return -1;
}
info_t *get_current_record(list_t * list)
{
return (list->current == NULL) ? NULL : list->current->info;
}
info_t *get_next_record(list_t * list)
{
return (list->current->next == NULL) ? NULL : list->current->next->info;
}
info_t *get_prev_record(list_t * list)
{
return (list->current->prev == NULL) ? NULL : list->current->prev->info;
}
info_t *get_first_record(list_t * list)
{
return (list->head == NULL) ? NULL : list->head->info;
}
info_t *get_last_record(list_t * list)
{
return (list->tail == NULL) ? NULL : list->tail->info;
}
/* export list to file */
int export_list(list_t * list, const char *path)
{
node_t *p;
FILE *fp;
if ((fp = fopen(path, "wb+")) == NULL) {
perror("fopen error!\n");
return -1;
}
p = list->head;
while (p) {
if ((fwrite(p->info, list->info_size, 1, fp)) !=
list->info_size) {
printf("fwrite error!\n");
fclose(fp);
return -1;
}
p = p->next;
}
fclose(fp);
return 0;
}
/* import list from file */
int import_list(list_t * list, const char *path)
{
info_t *info;
FILE *fp;
list_clear(list);
if ((fp = fopen(path, "rb")) == NULL)
return -1;
if ((info = (info_t *) malloc(list->info_size)) == NULL)
return -1;
while (feof(fp)) {
if (fread(info, list->info_size, 1, fp) != list->info_size)
return -1;
if (list_add_tail(list, info) == -1)
return -1;
}
free(info);
fclose(fp);
return 0;
}
3. test1.c
测试程序实现了一个简单的基于双链表的流表，支持简单的增删改查。
在网络处理中，通常将一个会话称为一个流。流由五元组（sip，dip，sport，dport，ip protocol）组成。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <sys/types.h>
#include <readline/readline.h>
#include <readline/history.h>
#include <unistd.h>
#include <stdint.h>
#include <signal.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include "db_list.h"
typedef struct stream {
uint32_t sip;
uint32_t dip;
uint16_t sport;
uint16_t dport;
unsigned char proto;
}stream_t;
int cmp(void *src, void *dst);
int check_stream(stream_t * s, list_t * list);
void get_prev_stream(list_t * list);
void get_current_stream(list_t * list);
void get_next_stream(list_t * list);
void get_first_stream(list_t * list);
void get_last_stream(list_t * list);
void get_all_stream(list_t * list);
void show_usage();
void show_version();
void process_cmd_add(char **cmd);
void process_cmd_check(char **cmd);
void process_cmd_show(char **cmd,int token_cnt);
void process_cmd_del(char **cmd,int token_cnt);
void process_cmd_size();
void process_cmd_import(char **cmd);
void process_cmd_export(char **cmd);
void process_cmd_clear();
int get_stream_size(list_t * list);
static int parse_cmd_line(char *cl, char **argv, int max_argv);
int get_token_count(char *buffer, char delimit, int *count);
char *stripwhite(char *string);
void sig_int(int a);
list_t *g_slist = NULL;
char *cmd[7]; /* store command tokens */
int main(int argc, char **argv)
{
int i;
int token_cnt;
char *string = NULL;
char *s;
//char *cmd[7]; /* store command tokens */
if ((g_slist = list_create(&g_slist)) == NULL) {
perror("list create error!\n");
exit(1);
}
if (list_init(g_slist, sizeof(stream_t)) != 0) {
perror("list init error!\n");
exit(1);
}
if (argc==2 && strncmp(argv[1], "test", sizeof("test"))==0) {
uint32_t sip, dip;
uint16_t sport, dport;
char buf[80], *tmp;
for(;;){
for (i=0; i<10; i++) {
signal(SIGINT, sig_int);
time_t t;
srand((unsigned)time(&t));
sip = rand()%400000000;
dip = rand()%400000000;
sport = rand()% 65535;
dport = rand()% 65535;
memset(buf, '\0', sizeof(buf));
sprintf(buf, "add %d %d %d %d tcp", sip, dip, sport, dport);
// printf("buf = %s\n", buf);
//char *cmd[6];
tmp = buf;
if (get_token_count(buf, ' ', &token_cnt)!=0)
return (-1);
for (i = 0; i < token_cnt ; i++)
cmd[i] = (char *)malloc(18*sizeof(char));
parse_cmd_line(tmp, cmd, token_cnt);
process_cmd_add(cmd);
for (i=0;i<token_cnt;i++)
free(cmd[i]);
usleep(100);
}
sleep(1);
list_destroy(&g_slist);
return 0;
}
}
/* process command options */
for (;;) {
string = readline("CLI>");
s=stripwhite(string);
if (strlen(s) == 0) {
continue;
}
/* if the command is null */
if (get_token_count(string, ' ', &token_cnt) != 0) {
free(s);
continue;
}
for (i = 0; i < token_cnt; i++) {
cmd[i] = (char *)malloc(18 * sizeof(char));
}
parse_cmd_line(s, cmd, token_cnt);
if ((memcmp("add", cmd[0], sizeof("add")) == 0)&&
token_cnt == 6)
process_cmd_add(cmd);
else if ((memcmp("del", cmd[0], sizeof("del")) == 0) &&
((token_cnt == 1)||(token_cnt == 6)))
process_cmd_del(cmd, token_cnt);
else if ((memcmp("check", cmd[0], sizeof("check")) == 0) &&
token_cnt == 6)
process_cmd_check(cmd);
else if ((memcmp("show", cmd[0], sizeof("show")) == 0) &&
(token_cnt == 1 || token_cnt==2))
process_cmd_show(cmd, token_cnt);
else if ((memcmp("size", cmd[0], sizeof("size")) == 0) &&
token_cnt == 1)
process_cmd_size();
else if ((memcmp("help", cmd[0], sizeof("help")) == 0) &&
token_cnt == 1)
show_usage();
else if ((memcmp("version", cmd[0], sizeof("version")) == 0) &&
token_cnt == 1)
show_version();
else if ((memcmp("exit", cmd[0], sizeof("exit")) == 0) &&
token_cnt == 1)
goto end;
else if ((memcmp("import", cmd[0], sizeof("import")) == 0) &&
token_cnt == 2)
process_cmd_import(cmd);
else if ((memcmp("export", cmd[0], sizeof("export")) == 0) &&
token_cnt == 2)
process_cmd_export(cmd);
else if ((memcmp("clear", cmd[0], sizeof("clear")) == 0) &&
token_cnt == 1)
process_cmd_clear(); //clear all nodes.
for (i = 0; i < token_cnt; i++) {
char *tmp = cmd[i];
free(tmp);
}
free(s);
}
end:
list_destroy(&g_slist);
for (i = 0; i < token_cnt; i++) {
char *tmp = cmd[i];
free(tmp);
}
free(s);
return 0;
}
/**
* cmp two stream
* 0 means equal.
*/
int cmp(void *src, void *dst)
{
stream_t *s, *d;
s = (stream_t *) src;
d = (stream_t *) dst;
if ((s->sip == d->sip) &&
(s->dip == d->dip) &&
(s->sport == d->sport) &&
(s->dport == d->dport) &&
(s->proto == d->proto))
return 0;
return -1;
}
void process_cmd_size()
{
unsigned long int i;
i = get_list_size(g_slist);
if (i == 0) {
printf("empty stream list\n");
return;
}
printf("stream counter:\t%ld\n", i);
}
void process_cmd_add(char **cmd)
{
stream_t *s;
struct in_addr saddr, daddr;
if ((s = (stream_t *) malloc(sizeof(stream_t))) == NULL) {
perror("malloc error in process_cmd_add\n");
return;
}
if ((inet_aton(cmd[1], &saddr) == 0)||
inet_aton(cmd[2], &daddr) == 0){
perror("bad ip addr\n");
free(s);
return;
}
s->sip = saddr.s_addr;
s->dip = daddr.s_addr;
s->sport = atoi(cmd[3]);
s->dport = atoi(cmd[4]);
if (strncmp(cmd[5], "tcp", sizeof("tcp"))==0)
s->proto= 6;
else if (strncmp(cmd[5], "udp", sizeof("udp")) == 0)
s->proto= 11;
else {
perror("not a valid protocol type\n");
free(s);
return;
}
if (list_add(g_slist, (void *)s) != 0) {
perror("add stream error!\n");
free(s);
return;
}
printf("[OK]\n");
}
void process_cmd_check(char **cmd)
{
stream_t s;
struct in_addr saddr, daddr;
if ((inet_aton(cmd[1], &saddr) == 0)||
inet_aton(cmd[2], &daddr) == 0){
perror("bad ip addr\n");
return;
}
s.sip = saddr.s_addr;
s.dip = daddr.s_addr;
s.sport = atoi(cmd[3]);
s.dport = atoi(cmd[4]);
if (strncmp(cmd[5], "tcp", sizeof("tcp"))==0)
s.proto= 6;
else if (strncmp(cmd[5], "udp", sizeof("udp")) == 0)
s.proto= 11;
else {
perror("not a valid protocol type\n");
return;
}
if (find_record(g_slist, &s, cmp) != 0) {
printf("stream not found\n");
return;
}
printf("stream find at\t%ld\n",g_slist->current_index);
}
/**
* del current stream
*/
void process_cmd_del(char **cmd, int token_cnt)
{
if (token_cnt == 1) {/* delete current node */
if (list_del(g_slist) != 0) {
perror("del stream error!\n");
return;
}
} else if (token_cnt == 6) { /* delete specified node */
//not implement
stream_t s;
struct in_addr saddr, daddr;
if ((inet_aton(cmd[1], &saddr) == 0)||
inet_aton(cmd[2], &daddr) == 0){
perror("bad ip addr\n");
return;
}
s.sip = saddr.s_addr;
s.dip = daddr.s_addr;
s.sport = atoi(cmd[3]);
s.dport = atoi(cmd[4]);
if (strncmp(cmd[5], "tcp", sizeof("tcp"))==0)
s.proto= 6;
else if (strncmp(cmd[5], "udp", sizeof("udp")) == 0)
s.proto= 11;
else {
perror("not a valid protocol type\n");
return;
}
if (find_record(g_slist, &s, cmp) != 0) {
perror("stream not found\n");
return;
} else {
if (list_del(g_slist) != 0) {
perror("del stream error!\n");
return;
}
}
}
printf("[OK]\n");
}
/**
* valgrind may report "Invalid read xxx"
* if there is only one token. because
* cmd[1]'s content is not defined.
*/
void process_cmd_show(char **cmd, int token_cnt)
{
if (token_cnt == 1) { /* no argument */
get_current_stream(g_slist);
return;
}
if (strncmp(cmd[1],"all", sizeof("all")) == 0)
get_all_stream(g_slist);
else if (strncmp(cmd[1], "first", sizeof("first")) == 0)
get_first_stream(g_slist);
else if (strncmp(cmd[1], "last", sizeof("last")) == 0)
get_last_stream(g_slist);
else
get_current_stream(g_slist);
}
/**
* split line into token
* return token count.
*/
int parse_cmd_line(char *cl, char **argv, int max_argv)
{
int argc;
char *token;
static const char *seps = " \t\r\n";
token = strtok(cl, seps);
for (argc = 0; token != NULL && argc < max_argv; argc++) {
memset(argv[argc], '\0', 18);
memcpy(argv[argc], token, strlen(token));
token = strtok(NULL, seps);
}
return argc;
}
void __print_stream(stream_t *s)
{
struct in_addr saddr, daddr;
saddr.s_addr = s->sip;
daddr.s_addr = s->dip;
printf(" sip: %s\n", inet_ntoa(saddr));
printf(" dip: %s\n", inet_ntoa(daddr));
printf(" sport: %d\n", s->sport);
printf(" dport: %d\n", s->dport);
if (s->proto == 6)
printf(" protocol: TCP\n");
else if (s->proto == 11)
printf(" protocol: UDP\n");
}
void get_first_stream(list_t * list)
{
if (list->head == NULL) {
perror("stream list is null!");
return;
}
__print_stream(get_first_record(g_slist));
}
void get_prev_stream(list_t * list)
{
if (list->head == NULL) {
perror("stream list is null!\n");
return;
}
__print_stream(get_prev_record(g_slist));
}
void get_current_stream(list_t * list)
{
if (list->head == NULL) {
perror("stream list is null!\n");
return;
}
__print_stream(get_current_record(g_slist));
}
void get_next_stream(list_t * list)
{
if (list->head == NULL) {
perror("stream list is null!");
return;
}
__print_stream(get_next_record(g_slist));
}
void get_last_stream(list_t * list)
{
if (list->head == NULL) {
perror("stream list is null!");
return;
}
__print_stream(get_last_record(g_slist));
}
void get_all_stream(list_t * list)
{
unsigned long int i;
if (list->head == NULL) {
perror("stream list is null!\n");
return;
}
node_t *tmp = g_slist->current;
g_slist->current = g_slist->head;
i = 1; // first node
while (g_slist->current != NULL) {
printf("stream\t%ld\n", i);
__print_stream(get_current_record(g_slist));
g_slist->current = g_slist->current->next;
i++;
}
g_slist->current = tmp;
}
void show_usage()
{
char *MSG = "usage: ./test1 -[command]\n"
"-add add a stream\n"
"-check check a stream if it exist\n"
"-del delete a stream\n"
"-exit exit program\n"
"-import import stream from file\n"
"-export export stream to file\n"
"-show show current stream\n"
"-size show stream counter\n"
"-help show help\n" "-version show version\n";
printf("%s\n", MSG);
}
void show_version()
{
char *VERSION = "0.3";
printf("\nversion: %s\n", VERSION);
}
void process_cmd_import(char **cmd)
{
if (import_list(g_slist, cmd[1]) != 0)
printf("import stream error!\n");
}
void process_cmd_export(char **cmd)
{
char *path = cmd[1];
printf("%s\n", cmd[1]);
if (export_list(g_slist, path) != 0)
printf("export stream error!\n");
}
int get_token_count(char *buffer, char delimit, int *count)
{
char *ptr = NULL;
char *ptr2 = NULL;
*count = 0;
ptr = buffer;
ptr2 = buffer;
while (*ptr) {
if (*ptr == delimit) {
if (ptr == ptr2) {
return -1;
}
*count = *count + 1;
ptr++;
ptr2 = ptr;
} else {
ptr++;
}
}
if (ptr == ptr2) {
return -1;
}
*count = *count + 1;
return 0;
}
char *stripwhite(char *string)
{
register char *s, *t;
for (s = string; isspace(*s); s++) {
}
if (*s == 0) {
return s;
}
t = s + strlen(s) - 1;
while (t > s && isspace(*t)) {
t--;
}
*++t = '\0';
return s;
}
void process_cmd_clear()
{
if (list_clear(g_slist) !=0 ) {
perror("clear stream error!\n");
return;
}
printf("[OK]\n");
}
void sig_int(int a)
{
list_destroy(&g_slist);
exit(0);
}4. Makefile
TARGET = test1
OBJS = db_list.o
OBJ_TEST1 = test1.o
PREFIX = /usr/local
LIBDIR = ${PREFIX}/lib
INCDIR = ${PREFIX}/include
LIB_STATIC = libdblist.a
LIB_DYNAMIC = libdblist.so
LIB = -L. -ldblist -lreadline -ltermcap
AR = ar rc
CC = gcc
SHARED = -shared -fPIC
CFLAGS = -g -Wall
all:
make clean
make dynamic
make static
make test
debug:
dynamic:$(OBJS)
$(CC) $(SHARED) $(FLAGS) -o $(LIB_DYNAMIC) $(OBJS)
static:
$(AR) $(LIB_STATIC) $(OBJS)
test:
make $(TARGET)
$(OBJS):db_list.c db_list.h
$(CC) -c $(CFLAGS) -fPIC db_list.c
# $(CC) -c $(CFLAGS) db_list.c
$(OBJ_TEST1):test1.c db_list.h
$(CC) -c $(CFLAGS) test1.c
$(TARGET):$(OBJ_TEST1)
$(CC) $(FLAGS) $(OBJ_TEST1) -o $(TARGET) $(LIB)
clean:
-rm -f *.o *.so *.a test1
install:
uninstall:
5. 运行结果
[root@localhost dblist]# make
make clean
make[1]: Entering directory `/root/study/c/dblist'
rm -f *.o *.so *.a test1
make[1]: Leaving directory `/root/study/c/dblist'
make dynamic
make[1]: Entering directory `/root/study/c/dblist'
gcc -c -g -Wall -fPIC db_list.c
gcc -shared -fPIC -o libdblist.so db_list.o
make[1]: Leaving directory `/root/study/c/dblist'
make static
make[1]: Entering directory `/root/study/c/dblist'
ar rc libdblist.a db_list.o
make[1]: Leaving directory `/root/study/c/dblist'
make test
make[1]: Entering directory `/root/study/c/dblist'
make test1
make[2]: Entering directory `/root/study/c/dblist'
gcc -c -g -Wall test1.c
gcc test1.o -o test1 -L. -ldblist -lreadline -ltermcap
make[2]: Leaving directory `/root/study/c/dblist'
make[1]: Leaving directory `/root/study/c/dblist'
[root@localhost dblist]# ls
data db_list.c db_list.h db_list.o libdblist.a libdblist.so Lindent Makefile test1 test1.c test1.o
[root@localhost dblist]# ./test1
CLI>help
usage: ./test1 -[command]
-add add a stream
-check check a stream if it exist
-del delete a stream
-exit exit program
-import import stream from file
-export export stream to file
-show show current stream
-size show stream counter
-help show help
-version show version
CLI>add 192.168.1.1 192.168.1.2 8888 9999 tcp
[OK]
CLI>show
sip: 192.168.1.1
dip: 192.168.1.2
sport: 8888
dport: 9999
protocol: TCP
CLI>check 192.168.1.1 192.168.1.2 8888 9999 tcp
stream find at 1
CLI>size
stream counter: 1
CLI>1、Android 中文 API （23） —— MultiAutoCompleteTextView.Tokenizer
2、WinError 10013
3、南阳722--数独（Dfs）
4、Magento安装成功之后，登陆不了后台的解决方法
5、内存缓冲区管理