链表是个好东西，可以实现很多东西，在Linux内核中发现一些宏的封装，感觉非常有意思，于是我也模仿了Linux内核的风格，实现了一个，先来看看头文件:
work.h
#ifndef __WORK_H
#define __WORK_H
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define NR(x) (sizeof(x)/sizeof(x[0]))
typedef unsigned char u8 ;
typedef unsigned int u32;
typedef unsigned short u16;
typedef char s8 ;
typedef int s32;
typedef short s16;
typedef char * pchar;
typedef int * pint ;
typedef short * pshort ;
typedef void No_return;
//重定义函数指针的类型
typedef void (*work_fun)();
#define SUCCESS 0
#define ZERO 0
#define ERROR -1
//不需要排序
#define Not_sorted -1
//按编号从小到大
#define Positive 1
//按编号从大到小
#define Reverse 0
typedef struct __Work
{
//任务编号
//根据任务编号决定工作任务的优先级
//编号越小，优先级越高
s32 work_num ;
//任务名称
pchar work_name ;
//根据相应的任务名称，处理相应的任务
void (*work_handler)();
struct __Work *next ;
}work;
typedef work * _work ;
#define __INIT_WORK(_work) \
do { \
_work = Init_cwork(_work); \
} while (0)
//初始化任务，包括两步
//1.定义一个头指针
//2.初始化头节点
#define INIT_WORK(work_node) \
_work work_node = NULL ; \
__INIT_WORK(work_node);
//注册任务
//1.链表的尾插实现
#define REGISTER_WORK(__work,new_work) \
Register_work_fuc(__work,new_work);
//调度运行任务
//根据传入的direction决定任务的执行顺序，分三类情况
//1.Not_sorted : 不排序
//2.Positive : 按编号从小到大
//3.Reverse : 按编号从大到小
#define SCHEDULING_WORK(work_node,direction,array_size) \
Run_Priority_work(work_node,direction,array_size);
//销毁所有任务
#define DESTROY_WORK(work_node,array) \
work_node = Destroy_work(work_node ,array);
//初始化一个子任务
_work Init_cwork();
//创建一个子任务
_work create_cwork(s32 work_num,pchar work_name ,work_fun work_fuc) ;
//注册子任务
No_return Register_work_fuc(_work __work,_work new_work);
//查找子任务的编号
s32 Find_Work_Num(_work headler,s32 work_num);
//查找子任务的名称
pchar Find_Work_Name(_work headler,pchar work_name) ;
//执行子任务----根据任务名称来执行
s32 Run_work_for_work_name(_work headler,pchar work_name) ;
//销毁一个子任务
s32 Destroy_cwork(_work headler,pchar work_name);
//销毁全部任务
_work Destroy_work(_work headler,_work array);
//工作优先级调度执行--->工作编号小的优先级高，依次类推
s32 Run_Priority_work(_work handler,s32 direction,const s32 work_array_size) ;
#endif //__WORK_H
头文件的实现很简单，就是定义一些基本的数据结构，宏，以及函数的声明。这里，我利用内核的编程思想，将子函数用几个宏封装起来。这里巧妙之处在于INIT_WORK这个宏，当我调用这个宏的时候，我只需要传一个变量名，它就帮我定义好了，然后再次调用__INIT_WORK子宏的时候会调用Init_cwork函数，完成头节点的初始化，并返回一个指针，这样，指针就初始化完毕了。内核链表，工作队列，也是利用很多这样的宏进行了封装，这样显得很方便。
下面看一下work.c的实现:
#include "work.h"
//初始化头节点
_work Init_cwork()
{
_work handler = NULL ;
handler = malloc(sizeof(work)) ;
assert(handler != NULL);
memset(handler,ZERO,sizeof(work));
handler->work_num = 0 ;
handler->work_name = NULL ;
handler->work_handler = NULL ;
handler->next = NULL ;
return handler ;
}
//创建一个子任务
_work create_cwork(s32 work_num , pchar work_name, work_fun work_fuc)
{
_work handler = NULL ;
handler = malloc(sizeof(work)) ;
assert(handler != NULL);
memset(handler,ZERO,sizeof(work));
handler->work_num = work_num ;
handler->work_name = work_name ;
handler->work_handler = work_fuc ;
handler->next = NULL ;
return handler ;
}
//注册任务，实际上就是尾插
No_return Register_work_fuc(_work __work,_work new_work)
{
assert(__work != NULL);
_work work_handler = __work ;
while(NULL != work_handler->next)
work_handler = work_handler->next ;
work_handler->next = new_work ;
}
//寻找任务的编号，就是结构体中的work_num
s32 Find_Work_Num(_work headler,s32 work_num)
{
assert(headler != NULL);
_work temp = headler->next ;
while(NULL != temp->next)
{
if(temp->work_num == work_num)
return temp->work_num ;
temp = temp->next;
}
return temp->work_num ;
}
//寻找任务的名称，就是结构体中的work_name
pchar Find_Work_Name(_work headler,pchar work_name)
{
assert(headler != NULL);
_work temp = headler->next ;
while(NULL != temp->next)
{
if(temp->work_name == work_name)
return temp->work_name ;
temp = temp->next;
}
return temp->work_name ;
}
//匹配对应的work_name，执行对应的任务(work_handler是一个函数)
s32 Run_work_for_work_name(_work headler,pchar work_name)
{
assert(headler != NULL);
_work temp = headler->next ;
while(NULL != temp->next)
{
if(temp->work_name == work_name){
temp->work_handler();
return SUCCESS;
}
temp = temp->next;
}
if(temp->work_name == work_name){
temp->work_handler();
return SUCCESS ;
}
printf("not this work , return ERROR!\n");
return ERROR;
}
//匹配对应的work_num，执行对应的任务(work_handler是一个函数)
static s32 Run_work_for_work_num(_work headler,s32 work_num)
{
assert(headler != NULL);
_work temp = headler->next ;
while(NULL != temp->next)
{
if(temp->work_num == work_num){
temp->work_handler();
return SUCCESS;
}
temp = temp->next;
}
if(temp->work_num == work_num){
temp->work_handler();
return SUCCESS ;
}
printf("not this work , return ERROR!\n");
return ERROR;
}
//对任务编号进行排序(正向，反向，不排)
static No_return Sort_work_num(s32 *buf, s32 len ,int direction)
{
s32 min;
s32 index;
s32 i, j , n;
if(direction == Positive)
{
for(i = ZERO; i < len - 1; i++)
{
min = buf[i];
index = i;
for(j = i; j < len; j++)
{
if(buf[j] < min)
{
min = buf[j];
index = j;
}
}
buf[index] = buf[i];
buf[i] = min;
}
}
else if(direction == Reverse)
{
for(i = 0 ; i < len ; i++)
{
for(j = 0 ; j < len ; j++)
{
if(buf[i] < buf[i+1])
{
n = buf[i] ;
buf[i] = buf[i+1] ;
buf[i+1] = n ;
}
}
}
}
else
{
return ;
}
}
//执行任务
s32 Run_Priority_work(_work handler,s32 direction,const s32 work_array_size)
{
s32 count = 0 ;
s32 i ;
assert(handler != NULL);
_work temp = handler->next ;
s32 Curent_node_Array[work_array_size];
while(temp != NULL){
Curent_node_Array[count] = temp->work_num ;
temp = temp->next ;
if(count < work_array_size)
count++ ;
}
Sort_work_num(Curent_node_Array,NR(Curent_node_Array),direction) ;
for(i = 0 ; i < NR(Curent_node_Array) ; i++)
Run_work_for_work_num(handler,Curent_node_Array[i]);
return SUCCESS ;
}
//根据work_name销毁子任务
s32 Destroy_cwork(_work headler,pchar work_name)
{
assert(headler != NULL);
_work temp = headler ;
_work temp_header_prev = NULL ;
while(NULL != temp->next)
{
temp_header_prev = temp ;
temp = temp->next ;
if(temp->work_name == work_name)
{
if(temp->next != NULL)
{
temp_header_prev->next = temp->next ;
free(temp);
temp = NULL ;
}
else
{
temp_header_prev->next = NULL ;
free(temp);
temp = NULL ;
}
return SUCCESS ;
}
}
printf("Not Work node\n");
return ERROR ;
}
//销毁所有的任务
_work Destroy_work(_work headler,_work array)
{
s32 i ;
assert(headler != NULL);
_work temp = headler ;
for(i = ZERO ; i < NR(array) ; i++)
Destroy_cwork(headler,array[i].work_name);
headler = NULL ;
return headler ;
}
基本设计思想，运用了单链表的尾插，删除，遍历，查找等。
接下来看一下测试结果：test_work.c
#include<stdio.h>
#include "work.h"
void work1()
{
printf("hello world! \n");
}
void work2()
{
printf("hello kitty! \n");
}
void work3()
{
printf("hello debug! \n");
}
work work_Register[] = {
{3,"hello world",work1},
{1,"hello kitty",work2},
{2,"hello debug",work3},
};
int main(void)
{
s32 i ;
INIT_WORK(work_node);
for(i = ZERO ; i < NR(work_Register) ; i++)
{
REGISTER_WORK(work_node , create_cwork(work_Register[i].work_num ,work_Register[i].work_name , work_Register[i].work_handler));
}
SCHEDULING_WORK(work_node,Positive,NR(work_Register));
DESTROY_WORK(work_node,work_Register);
printf("work_node:%p\n",work_node);
return 0 ;
}
运行结果：
调用SCHEDULING_WORK这个宏的时候，根据传入的为Positive，那么链表会进行排序，最终根据编号从小到大输出。
于是，上面的结果为：
hello kitty
hello debug
hello world
我们看到Android的expr语言中有这样一个函数，它其实是将这些函数全部存在一个fn_table的结构体数组里。
当然下面我们就会看到它使用realloc进行分配空间，然后再将数据放到这个结构体数组里。
这个fn_entries就类似是一个引用计数，这样，每次调用RegisterFunction，传入名称和函数，调用一次，引用计数加一，就把数据存到结构体数组里面去了，这不就是典型的线性表嘛。
// -----------------------------------------------------------------
// the function table
// -----------------------------------------------------------------
static int fn_entries = 0;
static int fn_size = 0;
NamedFunction* fn_table = NULL;
void RegisterFunction(const char* name, Function fn) {
if (fn_entries >= fn_size) {
fn_size = fn_size*2 + 1;
fn_table = realloc(fn_table, fn_size * sizeof(NamedFunction));
}
fn_table[fn_entries].name = name;
fn_table[fn_entries].fn = fn;
++fn_entries;
}那么这个表肯定也是一个数据结构：
typedef struct {
const char* name;
Function fn;
} NamedFunction;其中Function是一个重定义的函数指针，实现如下：
typedef struct {
int type;
ssize_t size;
char* data;
} Value;
typedef Value* (*Function)(const char* name, State* state,
int argc, Expr* argv[]);下面应用它的时候,expr语言中实现了一个函数，对函数进行注册操作：
void RegisterBuiltins() {
RegisterFunction("ifelse", IfElseFn);
RegisterFunction("abort", AbortFn);
RegisterFunction("assert", AssertFn);
RegisterFunction("concat", ConcatFn);
RegisterFunction("is_substring", SubstringFn);
RegisterFunction("stdout", StdoutFn);
RegisterFunction("sleep", SleepFn);
RegisterFunction("less_than_int", LessThanIntFn);
RegisterFunction("greater_than_int", GreaterThanIntFn);
}然后调用FinishRegistration进行排序
static int fn_entry_compare(const void* a, const void* b) {
const char* na = ((const NamedFunction*)a)->name;
const char* nb = ((const NamedFunction*)b)->name;
return strcmp(na, nb);
}
void FinishRegistration() {
qsort(fn_table, fn_entries, sizeof(NamedFunction), fn_entry_compare);
}设计思想与这个类似，上面写的工作任务用的是链式存储，而这里直接用结构体数组进行管理。
