C 工具库1：list-白红宇

C 工具库1：list

阅读量：7154 次

发布时间：2019-06-29

本文共 10139 字，大约阅读时间需要 33 分钟。

近来考虑将项目基础框架的开发语言从C++换成C，免不了要编写一大堆的基础工具。

本篇为第一篇，list,提供的接口和操作方式与std::list相似.后续将会陆续贴出map,vector,memory pool,

hash_table等工具。

list.h

#ifndef _LIST_H #define _LIST_H struct list; struct node; struct fix_obj_pool; struct list_iter {
   struct node **next; struct node *n; }; struct fix_obj_pool *list_create_obj_pool(unsigned int val_size,int default_size,int align4); struct list* list_create(unsigned int val_size,struct fix_obj_pool*); void   list_destroy(struct list**); struct list_iter list_begin(struct list*); struct list_iter list_end(struct list*); struct list_iter list_rbegin(struct list*); struct list_iter list_rend(struct list*); unsigned int list_size(struct list*); void   list_insert_before(struct list*,struct list_iter,void*); void   list_insert_after(struct list*,struct list_iter,void*); void   list_push_back(struct list*,void*); void   list_push_front(struct list*,void*); void   list_pop_back(struct list*,void*); void   list_pop_front(struct list*,void*); int    list_is_empty(struct list*); #ifndef LIST_INSERT_BEFORE #define LIST_INSERT_BEFORE(TYPE,LIST,IT,VAL)\     {TYPE val = VAL;list_insert_before(LIST,IT,&val);} #endif #ifndef LIST_INSERT_AFTER #define LIST_INSERT_AFTER(TYPE,LIST,IT,VAL)\     {TYPE val = VAL;list_insert_after(LIST,IT,&val);} #endif #ifndef LIST_PUSH_BACK #define LIST_PUSH_BACK(TYPE,LIST,VAL)\     {TYPE val = VAL;list_push_back(LIST,&val);} #endif #ifndef LIST_PUSH_FRONT #define LIST_PUSH_FRONT(TYPE,LIST,VAL)\     {TYPE val = VAL;list_push_front(LIST,&val);} #endif #ifndef LIST_POP_FRONT #define LIST_POP_FRONT(TYPE,LIST)\    ({ TYPE __result;\ do list_pop_front(LIST,&__result);\ while(0);\        __result;}) #endif #ifndef LIST_POP_BACK #define LIST_POP_BACK(TYPE,LIST)\    ({ TYPE __result;\ do list_pop_back(LIST,&__result);\ while(0);\        __result;}) #endif struct list_iter list_find(struct list*,void*); #ifndef LIST_FIND #define LIST_FIND(TYPE,L,VAL)\    ({ TYPE val = VAL;struct list_iter it;\ do it = list_find(L,&val);\ while(0);\        it;}) #endif int    list_remove(struct list*,void*); #ifndef LIST_REMOVE #define LIST_REMOVE(TYPE,L,VAL)\    ({ TYPE val = VAL;int ret;\ do ret = list_remove(L,&val);\ while(0);\        ret;}) #endif struct list_iter list_erase(struct list*,struct list_iter); struct list_iter iter_next(struct list_iter); void *iter_get_val(struct list_iter,void*); void  iter_set_val(struct list_iter,void*); int   iter_is_equal(struct list_iter a,struct list_iter b); #ifndef ITER_GET_VAL #define ITER_GET_VAL(TYPE,NODE)\    ({ TYPE __result;\ do iter_get_val(NODE,&__result);\ while(0);\        __result;}) #endif #ifndef ITER_SET_VAL #define ITER_SET_VAL(TYPE,NODE,VAL)\     {TYPE val=VAL;iter_set_val(NODE,&val);} #endif #endif

list.c

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include "list.h" #include "../mem/fix_obj_pool/fix_obj_pool.h" struct node {
   struct node *next; struct node *pre;     unsigned int val_size;     union{
   char   value[1];         unsigned int pad;     }; }; struct list {
       unsigned int size; struct node head; struct node end; struct fix_obj_pool *obj_pool;//产生node使用的内存池 }; struct fix_obj_pool *list_create_obj_pool(unsigned int val_size,int default_size,int align4) {
   struct node dummmy;     unsigned int node_size = sizeof(dummmy) + val_size - sizeof(dummmy.pad); struct fix_obj_pool *pool = create_pool(node_size,default_size,align4); return pool; } struct list* list_create(unsigned int val_size,struct fix_obj_pool *obj_pool) {
   struct list *_list = malloc(sizeof(*_list)); if(_list)     {
           _list->size = 0;         _list->head.val_size = _list->end.val_size = val_size;         _list->head.next = &_list->end;         _list->end.pre = &_list->head;         _list->head.pre = _list->end.next = 0;         _list->obj_pool = obj_pool;     } return _list; } void   list_destroy(struct list **_list) {
       assert(_list);     assert(*_list); if((*_list)->size > 0)     {
   struct node *cur = (*_list)->head.next; while(cur != &(*_list)->end)         {
   struct node *next = cur->next; if((*_list)->obj_pool)                 pool_dealloc((*_list)->obj_pool,cur); else                 free(cur);             cur = next;         }     }     free(*_list);     *_list = 0; } inline struct list_iter list_begin(struct list *_list) {
       assert(_list); struct list_iter it;     it.n = _list->head.next;     it.next = &(it.n->next); return it; } inline struct list_iter list_end(struct list *_list) {
       assert(_list); struct list_iter it;     it.n = &_list->end;     it.next = 0; return it; } inline struct list_iter list_rbegin(struct list *_list) {
       assert(_list); struct list_iter it;     it.n = _list->end.pre;     it.next = &(it.n->pre); return it; } inline struct list_iter list_rend(struct list *_list) {
       assert(_list); struct list_iter it;     it.n = &_list->head;     it.next = 0; return it; } inline unsigned int list_size(struct list *_list) {
       assert(_list); return _list->size; } void   list_insert_after(struct list *l,struct list_iter it,void *val) {
       assert(l); struct node *new_node; if(l->obj_pool)         new_node = pool_alloc(l->obj_pool); else         new_node = malloc(sizeof(*new_node) + l->head.val_size - sizeof(new_node->pad)); if(new_node)     {
           new_node->val_size = l->head.val_size;         memcpy(new_node->value,val,l->head.val_size); struct node *n = it.n; struct node *N = n->next;         n->next = N->pre = new_node;         new_node->next = N;         new_node->pre = n;         ++l->size;     } } void   list_insert_before(struct list *l, struct list_iter it,void *val) {
       assert(l); struct node *new_node; if(l->obj_pool)         new_node = pool_alloc(l->obj_pool); else         new_node = malloc(sizeof(*new_node) + l->head.val_size - sizeof(new_node->pad)); if(new_node)     {
           new_node->val_size = l->head.val_size;         memcpy(new_node->value,val,l->head.val_size);    struct node *n = it.n; struct node *P = n->pre;         n->pre = P->next = new_node;         new_node->next = n;         new_node->pre = P;         ++l->size;     }    } void list_push_back(struct list *_list,void *val) {
       assert(_list); struct list_iter end = list_end(_list);     list_insert_before(_list,end,val); } void list_push_front(struct list *_list,void *val) {
       assert(_list); struct list_iter begin = list_begin(_list);     list_insert_before(_list,begin,val);    } void  list_pop_back(struct list *_list,void *out) {
       assert(_list); if(_list->size > 0)     {
   struct node *_node = _list->end.pre;         memcpy(out,_node->value,_node->val_size); struct node *pre = _node->pre; struct node *next = _node->next;         pre->next = next;         next->pre = pre; if(_list->obj_pool)             pool_dealloc(_list->obj_pool,_node); else             free(_node); //free(_node);         --_list->size;     } } void  list_pop_front(struct list *_list,void *out) {
       assert(_list); if(_list->size > 0)     {
   struct node *_node = _list->head.next;         memcpy(out,_node->value,_node->val_size); struct node *pre = _node->pre; struct node *next = _node->next;         pre->next = next;         next->pre = pre; if(_list->obj_pool)             pool_dealloc(_list->obj_pool,_node); else             free(_node);         --_list->size;     } } inline int list_is_empty(struct list *_list) {
       assert(_list); return _list->size == 0; } struct list_iter list_find(struct list *l,void *v) {
       assert(l); struct list_iter it;     it.n = 0; struct node *cur = l->head.next; while(cur != &l->end)     {
   if(memcmp(cur->value,v,l->head.val_size) == 0) //找到目标             break;         cur = cur->next;     } if(cur != &l->end)     {
           it.n = cur;         it.next = &cur->next;     } else     {
           it.n = &l->end;         it.next = 0;     } return it; } int list_remove(struct list *l,void *v) {
       assert(l); struct list_iter it = list_find(l,v); if(it.n == 0) return 0;     list_erase(l,it); return 1; } struct list_iter list_erase(struct list *l,struct list_iter it) {
       assert(l); struct list_iter it_next = iter_next(it); struct node *n = it.n; struct node *P = n->pre; struct node *N = n->next;     P->next = N;     N->pre = P; if(l->obj_pool)         pool_dealloc(l->obj_pool,n); else         free(n);        --l->size; return it_next;    } inline struct list_iter iter_next(struct list_iter it) {
   if(it.next == 0) return it; struct list_iter it_next;     it_next.n = (*it.next); if(it.next == &it.n->next)         it_next.next = &(it_next.n->next); else if(it.next == &it.n->pre)         it_next.next = &(it_next.n->pre); else     {
           assert(0);     } return it_next; } inline int iter_is_equal(struct list_iter a,struct list_iter b) {
   return a.n == b.n; } void *iter_get_val(struct list_iter iter,void *v) {
   struct node *n = iter.n;     memcpy(v,n->value,n->val_size); } void  iter_set_val(struct list_iter iter,void *v) {
   struct node *n = iter.n;     memcpy(n->value,v,n->val_size); }

test.c

#include 
     
       #include "list.h" #include "../mem/fix_obj_pool/fix_obj_pool.h" int main() {
   struct fix_obj_pool *obj_pool = list_create_obj_pool(sizeof(int),4096,0); struct list *l = list_create(sizeof(int),obj_pool);     LIST_PUSH_BACK(int,l,1);     LIST_PUSH_BACK(int,l,2);     LIST_PUSH_BACK(int,l,3);     LIST_PUSH_BACK(int,l,4); struct list_iter it = LIST_FIND(int,l,2);     LIST_INSERT_BEFORE(int,l,it,5);     LIST_INSERT_AFTER(int,l,it,6);     it = list_begin(l); struct list_iter end = list_end(l); for( ; !iter_is_equal(it,end); )     {
   if(ITER_GET_VAL(int,it) == 3)             it = list_erase(l,it); else             it = iter_next(it);     }     it = list_begin(l); while(!iter_is_equal(it,end))     {
           printf("%d\n",ITER_GET_VAL(int,it));         it = iter_next(it);     }     printf("free size:%d\n",get_free_size(obj_pool));     list_destroy(&l);     printf("free size:%d\n",get_free_size(obj_pool));     destroy_pool(&obj_pool); return 0; }