589 lines
10 KiB
C
589 lines
10 KiB
C
#include "list.h"
|
||
#include "stdlib.h"
|
||
#include "string.h"
|
||
#include "stdio.h"
|
||
#include "board.h"
|
||
#include "mystdlib.h"
|
||
#include "debug.h"
|
||
#include "bytearray.h"
|
||
#include "rtthread.h"
|
||
|
||
#define LIST_APPEND_SKIP 10
|
||
|
||
|
||
typedef struct{
|
||
int32_t next;
|
||
int32_t prev;
|
||
uint32_t data[0];
|
||
}list_node_def;
|
||
|
||
|
||
struct _list_def{
|
||
int32_t all;
|
||
int32_t used;
|
||
int32_t block_size;
|
||
int32_t block_size4;
|
||
rt_mutex_t mutex;
|
||
int32_t head;
|
||
int32_t tail;
|
||
sub_fun_def sub;
|
||
del_fun_def del;
|
||
str_fun_def str;
|
||
uint32_t data[0];
|
||
};
|
||
|
||
//#define list_enter_mutex(l)\
|
||
// rt_mutex_take((l)->mutex,RT_WAITING_FOREVER)
|
||
//
|
||
//#define list_exit_mutex(l)\
|
||
// rt_mutex_release((l)->mutex)
|
||
|
||
#define list_enter_mutex(l)
|
||
#define list_exit_mutex(l)
|
||
#define rt_mutex_create(...) 0
|
||
#define rt_mutex_delete(l)
|
||
|
||
list_def *list_creat(int block_size,sub_fun_def sub,del_fun_def del,str_fun_def str)
|
||
{
|
||
static uint16_t count=0;
|
||
char s1[16]={0};
|
||
sprintf(s1,"list_mut#%d",count);
|
||
int size=0;
|
||
int block_size4;
|
||
list_def *l;
|
||
size+=sizeof(list_def);
|
||
// 4字节对齐
|
||
block_size4=((block_size+3)/4)*4;
|
||
size+=(sizeof(list_node_def)+block_size4)*LIST_APPEND_SKIP;
|
||
l=malloc(size);
|
||
param_check(l);
|
||
l->all=LIST_APPEND_SKIP;
|
||
l->used=0;
|
||
l->block_size=block_size;
|
||
l->block_size4=block_size4;
|
||
l->mutex=rt_mutex_create(s1,RT_IPC_FLAG_FIFO);
|
||
l->head=-1;
|
||
l->tail=-1;
|
||
l->sub=sub;
|
||
l->del=del;
|
||
l->str=str;
|
||
|
||
// 初始化列表
|
||
list_node_def *node;
|
||
node=(list_node_def *)l->data;
|
||
for(int i=0;i<l->all;i++)
|
||
{
|
||
node->next=-1;
|
||
node->prev=-1;
|
||
node=(list_node_def *)((uint32_t)node+sizeof(list_node_def)+l->block_size4);
|
||
}
|
||
count++;
|
||
return l;
|
||
}
|
||
|
||
|
||
// 对于数据里有指针数据的成员,需要提供del函数
|
||
void _list_delete(list_def **l)
|
||
{
|
||
param_check(l);
|
||
param_check(*l);
|
||
list_enter_mutex(*l);
|
||
if((*l)->del)
|
||
{
|
||
for(int i=0;i<(*l)->used;i++)
|
||
{
|
||
(*l)->del(list_get(*l,i));
|
||
}
|
||
}
|
||
list_exit_mutex(*l);
|
||
rt_mutex_delete((*l)->mutex);
|
||
free(*l);
|
||
*l=0;
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
|
||
int list_block_size4(list_def *l)
|
||
{
|
||
param_check(l);
|
||
return l->block_size4;
|
||
}
|
||
|
||
|
||
//static void cpy4byte(uint32_t *dst,uint32_t *src,int num_4byte)
|
||
//{
|
||
// for(int i=0;i<num_4byte;i++)
|
||
// {
|
||
// dst[i]=src[i];
|
||
// }
|
||
//}
|
||
|
||
|
||
|
||
static list_def *list_expend(list_def *l)
|
||
{
|
||
int size=0;
|
||
int cpysize=0;
|
||
list_def *r;
|
||
size+=sizeof(list_def);
|
||
size+=(sizeof(list_node_def)+l->block_size4)*(l->all);
|
||
cpysize=size;
|
||
size+=(sizeof(list_node_def)+l->block_size4)*(LIST_APPEND_SKIP);
|
||
r=malloc(size);
|
||
param_check(r);
|
||
cpy4byte((uint32_t *)r,(uint32_t *)l,cpysize/4);
|
||
// 初始化列表
|
||
list_node_def *node;
|
||
node=(list_node_def *)((uint32_t)r->data+r->all*(sizeof(list_node_def)+r->block_size4));
|
||
for(int i=0;i<LIST_APPEND_SKIP;i++)
|
||
{
|
||
node->next=-1;
|
||
node->prev=-1;
|
||
node=(list_node_def *)((uint32_t)node+sizeof(list_node_def)+r->block_size4);
|
||
}
|
||
r->all+=LIST_APPEND_SKIP;
|
||
free(l);
|
||
return r;
|
||
}
|
||
|
||
// 查找一个未使用的节点
|
||
static list_node_def *list_unused_node(list_def *l,int *index)
|
||
{
|
||
list_node_def *node=0;
|
||
node=(list_node_def *)l->data;
|
||
for(int i=0;i<l->all;i++)
|
||
{
|
||
if((node->next==-1)&&(node->prev==-1)){
|
||
if(index) *index=i;
|
||
return node;
|
||
}
|
||
node=(list_node_def *)((uint32_t)node+sizeof(list_node_def)+l->block_size4);
|
||
}
|
||
return node;
|
||
}
|
||
|
||
// 取得指定序号的节点
|
||
static list_node_def *list_node(list_def *l,int index)
|
||
{
|
||
list_node_def *node;
|
||
param_check(index>=0&&index<l->all);
|
||
node=(list_node_def *)((uint32_t)l->data+index*(sizeof(list_node_def)+l->block_size4));
|
||
return node;
|
||
}
|
||
|
||
|
||
// 取得节点的物理索引
|
||
static int list_phy_index(list_def *l,list_node_def *n)
|
||
{
|
||
return ((uint32_t)n-(uint32_t)l->data)/(sizeof(list_node_def)+l->block_size4);
|
||
}
|
||
|
||
|
||
/*
|
||
// 改为统一使用insert函数
|
||
list_def *list_append(list_def **l,void *data)
|
||
{
|
||
param_check(l);
|
||
param_check(*l);
|
||
list_def *r=*l;
|
||
if((*l)->used>=(*l)->all)
|
||
{
|
||
r=list_expend(*l);
|
||
}
|
||
list_node_def *node;
|
||
int index;
|
||
node=list_unused_node(r,&index);
|
||
param_check(node);
|
||
memcpy(node->data,data,r->block_size);
|
||
if(r->head==-1&&r->tail==-1)
|
||
{
|
||
r->head=index;
|
||
r->tail=index;
|
||
node->next=index;
|
||
node->prev=index;
|
||
}
|
||
else if(r->head!=-1&&r->tail!=-1)
|
||
{
|
||
node->prev=r->tail;
|
||
node->next=list_node(r,r->tail)->next;
|
||
list_node(r,r->tail)->next=index;
|
||
r->tail=index;
|
||
list_node(r,r->head)->prev=index;
|
||
}
|
||
else
|
||
{
|
||
param_check(0);
|
||
}
|
||
r->used++;
|
||
*l=r;
|
||
return r;
|
||
}
|
||
*/
|
||
|
||
|
||
|
||
// 返回指定index的已使用节点
|
||
static list_node_def *list_used_node(list_def *l,int index)
|
||
{
|
||
list_node_def *node=0;
|
||
if(index>l->used/2)
|
||
{
|
||
index=l->used-1-index;
|
||
node=list_node(l,l->tail);
|
||
for(int i=0;i<index;i++)
|
||
{
|
||
node=list_node(l,node->prev);
|
||
}
|
||
}
|
||
else{
|
||
node=list_node(l,l->head);
|
||
for(int i=0;i<index;i++)
|
||
{
|
||
node=list_node(l,node->next);
|
||
}
|
||
}
|
||
return node;
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
// 获取第index项数据,不删除
|
||
// index支持负数，-1表示最后一项
|
||
// 返回数据引用
|
||
void *list_get(list_def *l,int index)
|
||
{
|
||
param_check(l);
|
||
void *ret=0;
|
||
list_enter_mutex(l);
|
||
list_node_def *node;
|
||
if(index<0) index=l->used+index;
|
||
if((index>=0&&index<l->used)==0)
|
||
ret=0;
|
||
else{
|
||
node=list_used_node(l,index);
|
||
param_check(node);
|
||
ret=node->data;
|
||
}
|
||
list_exit_mutex(l);
|
||
return ret;
|
||
}
|
||
|
||
|
||
// 删除第index项数据
|
||
// index支持负数，-1表示最后一项
|
||
void list_remove(list_def *l,int index)
|
||
{
|
||
param_check(l);
|
||
list_node_def *node;
|
||
int phy_index;
|
||
if(index<0) index=l->used+index;
|
||
list_enter_mutex(l);
|
||
if((index>=0&&index<l->used)){
|
||
node=list_used_node(l,index);
|
||
param_check(node);
|
||
phy_index=list_phy_index(l,node);
|
||
if(l->used==1)
|
||
{
|
||
l->head=-1;
|
||
l->tail=-1;
|
||
}
|
||
else
|
||
{
|
||
if(l->head==phy_index)
|
||
{
|
||
l->head=node->next;
|
||
}
|
||
if(l->tail==phy_index)
|
||
{
|
||
l->tail=node->prev;
|
||
}
|
||
list_node(l,node->prev)->next=node->next;
|
||
list_node(l,node->next)->prev=node->prev;
|
||
}
|
||
node->next=-1;
|
||
node->prev=-1;
|
||
if(l->del) l->del(node->data);
|
||
l->used--;
|
||
}
|
||
list_enter_mutex(l);
|
||
}
|
||
|
||
|
||
// 获取指定index的数据，随后删除
|
||
// 返回数据的临时指针
|
||
// 对于存在动态指针的对象，由于take之后会自动删除，take操作会出现野指针
|
||
// 建议使用list_get + list_remove的方式代替list_take
|
||
void *list_take(list_def *l,int index)
|
||
{
|
||
param_check(l);
|
||
void *p;
|
||
p=list_get(l,index);
|
||
void *t=tmalloc(l->block_size);
|
||
param_check(t);
|
||
memcpy(t,p,l->block_size);
|
||
list_remove(l,index);
|
||
return t;
|
||
}
|
||
|
||
|
||
// 清空
|
||
void list_clear(list_def *l)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
while(l->used>0)
|
||
{
|
||
list_remove(l,0);
|
||
}
|
||
list_exit_mutex(l);
|
||
}
|
||
|
||
|
||
int list_length(list_def *l)
|
||
{
|
||
param_check(l);
|
||
return l->used;
|
||
}
|
||
|
||
|
||
|
||
|
||
// 在指定位置插入
|
||
// index为节点插入之后所在的位置
|
||
list_def *_list_insert(list_def **l,void *data,int index)
|
||
{
|
||
param_check(l);
|
||
param_check(*l);
|
||
list_enter_mutex(*l);
|
||
if(index<0) index=(*l)->used+index+1;
|
||
if((index>=0&&index<=(*l)->used)==0){
|
||
list_exit_mutex(*l);
|
||
return *l;
|
||
}
|
||
list_def *r=*l;
|
||
if((*l)->used>=(*l)->all)
|
||
{
|
||
r=list_expend(*l);
|
||
}
|
||
list_node_def *node;
|
||
int phy_index;
|
||
node=list_unused_node(r,&phy_index);
|
||
param_check(node);
|
||
memcpy(node->data,data,r->block_size);
|
||
if(r->head==-1&&r->tail==-1)
|
||
{
|
||
r->head=phy_index;
|
||
r->tail=phy_index;
|
||
node->next=phy_index;
|
||
node->prev=phy_index;
|
||
}
|
||
else if(r->head!=-1&&r->tail!=-1)
|
||
{
|
||
list_node_def *n;
|
||
int n_phy_index;
|
||
if(index<r->used)
|
||
{
|
||
n=list_used_node(r,index);
|
||
n_phy_index=list_phy_index(r,n);
|
||
list_node(r,n->prev)->next=phy_index;
|
||
node->prev=n->prev;
|
||
node->next=n_phy_index;
|
||
n->prev=phy_index;
|
||
if(index==0)
|
||
{
|
||
r->head=phy_index;
|
||
}
|
||
}
|
||
else
|
||
{
|
||
node->prev=r->tail;
|
||
node->next=list_node(r,r->tail)->next;
|
||
list_node(r,r->tail)->next=phy_index;
|
||
r->tail=index;
|
||
list_node(r,r->head)->prev=phy_index;
|
||
}
|
||
}
|
||
else
|
||
{
|
||
param_check(0);
|
||
}
|
||
r->used++;
|
||
*l=r;
|
||
list_exit_mutex(*l);
|
||
return r;
|
||
}
|
||
|
||
|
||
void list_sort(list_def *l)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
if(l->sub){
|
||
_list_sort(l,l->sub);
|
||
}
|
||
else{
|
||
DBG_WARN("obj->sub fun is null.");
|
||
}
|
||
list_exit_mutex(l);
|
||
}
|
||
|
||
|
||
|
||
|
||
// 在列表内返回1，不在返回0
|
||
int list_contains(list_def *l,void *d)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
if(l->sub)
|
||
{
|
||
for(int i=0;i<list_length(l);i++)
|
||
{
|
||
if(l->sub(list_get(l,i),d)==0){
|
||
list_exit_mutex(l);
|
||
return 1;
|
||
}
|
||
}
|
||
}
|
||
else{
|
||
DBG_WARN("obj->sub fun is null.");
|
||
}
|
||
list_exit_mutex(l);
|
||
return 0;
|
||
}
|
||
|
||
|
||
// 交换两个位置
|
||
void list_swap(list_def *l,int index_a,int index_b)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
void *a_=list_get(l,index_a);
|
||
void *b_=list_get(l,index_b);
|
||
void *t_=0;
|
||
if(a_&&b_)
|
||
{
|
||
t_=calloc(1,sizeof(l->block_size4));
|
||
cpy4byte(t_,a_,l->block_size4/4);
|
||
cpy4byte(a_,b_,l->block_size4/4);
|
||
cpy4byte(b_,t_,l->block_size4/4);
|
||
free(t_);
|
||
}
|
||
list_exit_mutex(l);
|
||
}
|
||
|
||
|
||
// 向后循环移动
|
||
void list_shift(list_def *l)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
if(l->used>0){
|
||
l->head=list_node(l,l->head)->next;
|
||
l->tail=list_node(l,l->tail)->next;
|
||
}
|
||
list_exit_mutex(l);
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
// 输出打印字符串
|
||
char *list_string(list_def *l)
|
||
{
|
||
param_check(l);
|
||
list_enter_mutex(l);
|
||
array_def *d=arr_creat();
|
||
param_check(d);
|
||
int len=0;
|
||
char *s=0;
|
||
arr_append(d,'(');
|
||
if(l->str)
|
||
{
|
||
for(int i=0;i<list_length(l);i++)
|
||
{
|
||
s=l->str(list_get(l,i));
|
||
len=strlen(s);
|
||
arr_appends(d,s,len);
|
||
free(s);
|
||
arr_append(d,',');
|
||
arr_append(d,' ');
|
||
}
|
||
}
|
||
arr_append(d,')');
|
||
len=arr_length(d);
|
||
s=malloc(len+1);
|
||
param_check(s);
|
||
memcpy(s,arr_data(d),len);
|
||
arr_delete(d);
|
||
s[len]=0;
|
||
list_exit_mutex(l);
|
||
return s;
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
// int sub函数
|
||
int _list_int_sub(void *a,void *b)
|
||
{
|
||
return *(int *)a-*(int *)b;
|
||
}
|
||
|
||
|
||
// int 打印函数
|
||
char *_list_int_str(void *a)
|
||
{
|
||
char *s=malloc(20);
|
||
param_check(s);
|
||
sprintf(s,"%d",*(int *)a);
|
||
return s;
|
||
}
|
||
|
||
|
||
// str sub函数
|
||
int _list_str_sub(void *a,void *b)
|
||
{
|
||
char *a_=*(char **)a;
|
||
char *b_=*(char **)b;
|
||
return strcmp(a_,b_);
|
||
}
|
||
|
||
|
||
// str删除函数
|
||
int _list_str_del(void *d)
|
||
{
|
||
char **c=d;
|
||
if(*c) free(*c);
|
||
return 0;
|
||
}
|
||
|
||
// str 打印函数
|
||
char *_list_str_str(void *a)
|
||
{
|
||
char *a_=*(char **)a;
|
||
int len=strlen(a_);
|
||
char *s=malloc(len+1);
|
||
param_check(s);
|
||
memcpy(s,a_,len+1);
|
||
return s;
|
||
}
|
||
|
||
|
||
|
||
// 延迟删除，不需要修改指针
|
||
void _list_delete_later(list_def *l)
|
||
{
|
||
_list_delete(&l);
|
||
}
|
||
|
||
|
||
|