浏览器

开发平台：
Visual C++

list.h.svn-base：源码内容
							/***********************************************************************
 *                           特殊用法
 * FOREACH(container, var, field)       : 遍历容器各个元素.(暂时仅支持FIFO,STACK,LIST)
 **********************************************************************/
/***********************************************************************
 *                            FIFO 使用说明
 *
 * FIFO(type)                           : 定义一个FIFO.
 * FIFO_V(type)                         : 定义一个FIFO,其中FIFO_COUNT是volatile类型.
 * FIFO_ENTRY(type)                     : 定义FIFO的节点,需要处于结构体中.
 *
 * FIFO_FIRST(fifo)                     : 返回FIFO的首个元素.
 * FIFO_LAST(fifo)                      : 返回FIFO的末尾元素.
 * FIFO_COUNT(fifo)                     : 返回FIFO的元素个数.
 * FIFO_NEXT(elm, field)                : 返回elm的后一个元素.
 *
 * FIFO_INIT(fifo)                      : 初始化FIFO.
 * FIFO_INITIALIZER                     : 静态初始化FIFO.
 * FIFO_POP(fifo, var, field)           : 获取FIFO的元素,该元素从FIFO中移除.
 * FIFO_UNPOP(fifo, elm, field)         : 撤销从FIFO中获取元素的动作.
 * FIFO_PUSH(fifo, elm, field)          : 把元素放到FIFO中.
 *
 ***********************************************************************/
/***********************************************************************
 *                            LIST 使用说明
 *
 * LIST(type)                           : 定义一个LIST.
 * LIST_V(type)                         : 定义一个LIST,其中LIST_COUNT是volatile类型.
 * LIST_ENTRY(type)                     : 定义LIST的节点,需要处于结构体中.
 *
 * LIST_FIRST(fifo)                     : 返回LIST的首个元素.
 * LIST_LAST(fifo)                      : 返回LIST的末尾元素.
 * LIST_COUNT(fifo)                     : 返回LIST的元素个数.
 * LIST_NEXT(elm, field)                : 返回elm的后一个元素.
 * LIST_PREV(elm, field)                : 返回elm的前一个元素.
 *
 * LIST_INIT(fifo)                      : 初始化LIST.
 * LIST_INITIALIZER                     : 静态初始化LIST.
 * LIST_POP_FRONT(list, var, field)     : 获取LIST的首个元素,该元素从LIST中移除.
 * LIST_POP_BACK(list, var, field)      : 获取LIST的末尾元素,该元素从LIST中移除.
 * LIST_PUSH_FRONT(list, elm, field)    : 把元素elm放到LIST的首位.
 * LIST_PUSH_BACK(list, elm, field)     : 把元素elm放到LIST的末尾.
 * LIST_REMOVE(list, elm, field)        : 从LIST中移除元素elm.
 * LIST_MOVE(dstlist, srclist)          : 将srclist中的所有元素移到dstlist中 
 *
 ***********************************************************************/
/***********************************************************************
 *                            MIN_HEAP 使用说明
 *
 * MIN_HEAP(type)                       : 定义一个MIN_HEAP.
 * MIN_HEAP_ENTRY(type)                 : 定义MIN_HEAP的节点,需要处于结构体中.
 *
 * MIN_HEAP_SIZE(heap)                  : 返回heap的容量.
 * MIN_HEAP_COUNT(heap)                 : 返回heap的元素个数.
 *
 * MIN_HEAP_INIT(heap, cmp)             : 初始化heap,cmp为比较函数,cmp返回值是参数1-参数2的结果.
 * MIN_HEAP_INITIALIZER(cmp)            : 静态初始化MIN_HEAP.
 * MIN_HEAP_DESTROY(heap)               : 销毁heap.
 *
 * MIN_HEAP_TOP(heap)                   : 返回heap的首个元素.
 * MIN_HEAP_POP(heap, elm, field)       : 返回heap的最小值.
 * MIN_HEAP_PUSH(heap, elm, field)      : 将元素elm放入heap中.
 * MIN_HEAP_REMOVE(heap, elm, field)    : 把元素elm从heap中移除.
 * MIN_HEAP_FOREACH(heap, index, var, node): 遍历heap的各个元素.
 *
 ***********************************************************************/
#ifndef _LIB_BASE_LIST_H_
#define _LIB_BASE_LIST_H_
#include <stdlib.h>
#define FOREACH(container, var, field)                                
        for ((var) = (container)->first; (var); (var) = (var)->field.next)
/***********************************************************************
 *                            FIFO 数据结构
 ***********************************************************************/
#define FIFO_V(type)                                                    
struct {                                                                
        type *first, *last;                                             
        volatile int count;                                             
}
#define FIFO(type)                                                      
struct {                                                                
        type *first, *last;                                             
        int count;                                                      
}
#define FIFO_ENTRY(type)                                                
struct {                                                                
        type *next;                                                     
}
/***********************************************************************
 *                            FIFO 访问方法
 ***********************************************************************/
#define FIFO_FIRST(fifo)                ((fifo)->first)
#define FIFO_LAST(fifo)                 ((fifo)->last)
#define FIFO_COUNT(fifo)                ((fifo)->count)
#define FIFO_NEXT(elm, field)           ((elm)->field.next)
/***********************************************************************
 *                            FIFO 函数
 ***********************************************************************/
#define FIFO_INIT(fifo)                 (fifo)->first = (fifo)->last = NULL, (fifo)->count = 0
#define FIFO_INITIALIZER                {NULL, NULL, 0}
#ifndef WIN32
#define FIFO_POP(fifo, var, field)                ({                    
        if (((var) = FIFO_FIRST(fifo))) {                               
                FIFO_FIRST(fifo) = FIFO_NEXT(var, field);               
                if (!--FIFO_COUNT(fifo)) FIFO_LAST(fifo) = NULL;        
                FIFO_NEXT(var, field) = NULL;                           
        }                                                               
        (var);                                                          
})
#else
#define FIFO_POP(fifo, var, field)					do {                
        if (((var) = FIFO_FIRST(fifo))) {                               
                FIFO_FIRST(fifo) = FIFO_NEXT(var, field);               
                if (!--FIFO_COUNT(fifo)) FIFO_LAST(fifo) = NULL;        
                FIFO_NEXT(var, field) = NULL;                           
        }                                                               
} while(0)
#endif
#define FIFO_UNPOP(fifo, elm, field)              do {                  
        FIFO_NEXT(elm, field) = FIFO_FIRST(fifo);                       
        FIFO_FIRST(fifo) = (elm);                                       
        if (!FIFO_COUNT(fifo)++) FIFO_LAST(fifo) = (elm);               
} while (0)
#define FIFO_PUSH(fifo, elm, field)               do {                  
        if (FIFO_COUNT(fifo)++)                                         
                FIFO_NEXT(FIFO_LAST(fifo), field) = (elm);              
        else                                                            
                FIFO_FIRST(fifo) = (elm);                               
        FIFO_LAST(fifo) = (elm);                                        
        FIFO_NEXT(elm, field) = NULL;                                   
} while (0)
////////////////////////////////////////////////////////////////////////
/***********************************************************************
 *                            LIST 数据结构
 ***********************************************************************/
#define LIST_V(type)                                                    
struct {                                                                
        type *first, *last;                                             
        volatile int count;                                             
}
#define LIST(type)                                                      
struct {                                                                
        type *first, *last;                                             
        int count;                                                      
}
#define LIST_ENTRY(type)                                                
struct {                                                                
        type *prev, *next;                                              
}
/***********************************************************************
 *                            LIST 访问方法
 ***********************************************************************/
#define LIST_FIRST(list)                ((list)->first)
#define LIST_LAST(list)                 ((list)->last)
#define LIST_COUNT(list)                ((list)->count)
#define LIST_NEXT(elm, field)           ((elm)->field.next)
#define LIST_PREV(elm, field)           ((elm)->field.prev)
/***********************************************************************
 *                            LIST 数据结构
 ***********************************************************************/
#define LIST_INIT(list)                 (list)->first = (list)->last = NULL, (list)->count = 0
#define LIST_INITIALIZER                {NULL, NULL, 0}
#define LIST_REMOVE(list, elm, field)                  do {             
        if (!LIST_NEXT(elm, field) && !LIST_PREV(elm, field) && LIST_FIRST(list) != (elm)) break;   
        if (LIST_PREV(elm, field)) LIST_NEXT(LIST_PREV(elm, field), field) = LIST_NEXT(elm, field); 
        if (LIST_NEXT(elm, field)) LIST_PREV(LIST_NEXT(elm, field), field) = LIST_PREV(elm, field); 
        if (LIST_FIRST(list) == (elm)) LIST_FIRST(list) = LIST_NEXT(elm, field); 
        if (LIST_LAST(list) == (elm)) LIST_LAST(list) = LIST_PREV(elm, field); 
        LIST_NEXT(elm, field) = LIST_PREV(elm, field) = NULL;           
        -- LIST_COUNT(list);                                            
} while (0)
#define LIST_POP_FRONT(list, var, field)                ({              
        if (((var) = LIST_FIRST(list))) LIST_REMOVE(list, var, field);  
        (var);                                                          
})
#define LIST_POP_BACK(list, var, field)                 ({              
        if (((var) = LIST_LAST(list))) LIST_REMOVE(list, var, field);   
        (var);                                                          
})
#define LIST_PUSH_FRONT(list, elm, field)              do {             
        LIST_PREV(elm, field) = NULL;                                   
        LIST_NEXT(elm, field) = LIST_FIRST(list);                       
        if (LIST_NEXT(elm, field)) LIST_PREV(LIST_NEXT(elm, field), field) = (elm); 
        LIST_FIRST(list) = (elm);                                       
        if (!LIST_COUNT(list)++) LIST_LAST(list) = (elm);               
} while (0)
#define LIST_PUSH_BACK(list, elm, field)               do {             
        LIST_PREV(elm, field) = LIST_LAST(list);                        
        LIST_NEXT(elm, field) = NULL;                                   
        if (LIST_PREV(elm, field)) LIST_NEXT(LIST_PREV(elm, field), field) = (elm); 
        LIST_LAST(list) = (elm);                                        
        if (!LIST_COUNT(list)++) LIST_FIRST(list) = (elm);              
} while (0)
#define LIST_MOVE(dstlist, srclist)                     do {            
        if (LIST_LAST(dstlist)) LIST_NEXT(LIST_LAST(dstlist)) = LIST_FIRST(srclist); 
        if (LIST_FRIST(srclist)) LIST_NEXT(LIST_FRIST(srclist)) = LIST_FIRST(dstlist); 
        LIST_COUNT(dstlist) += LIST_COUNT(srclist);                     
        LIST_INIT(srclist);                                             
} while (0)
/////////////////////////////////////////////////////////////////////////
typedef struct _ListNode TListNode;
struct _ListNode
{
        LIST_ENTRY(TListNode) node;
        void *ptr;
};
typedef LIST(TListNode) TList;
#define list_init(list)                 do {                            
        alloctor_register(sizeof(TListNode));                           
        LIST_INIT(list);                                                
} while (0)
#define list_count(list)                LIST_COUNT(list)
#define list_first(list)                (LIST_FIRST(list)->ptr)
#define list_last(list)                 (LIST_LAST(list)->ptr)
#define list_push_front(list, node)     do {                            
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_PUSH_FRONT(list, n, node);                                 
} while (0)
#define list_push_front(list, node)     do {                            
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_PUSH_FRONT(list, n, node);                                 
} while (0)
#define list_push_back(list, node)     do {                             
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_PUSH_BACK(list, n, node);                                  
} while (0)
#define list_pop_front(list, node)     do {                             
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_POP_FRONT(list, n, node);                                  
} while (0)
#define list_pop_back(list, node)     do {                              
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_POP_BACK(list, n, node);                                   
} while (0)
#define list_push_remove(list, node)     do {                           
        TListNode *n = (TListNode *)alloctor_alloc(sizeof(TListNode));  
        n->ptr = node;                                                  
        LIST_REMOVE(list, n, node);                                     
} while (0)
/***********************************************************************
 *                            MIN_HEAP 数据结构
 ***********************************************************************/
#define MIN_HEAP(type) struct {                                         
        type **elements;                                                
        int size, count;                                                
        int (*cmp)(type *, type *);                                     
}
#define MIN_HEAP_ENTRY(type) struct {                                   
        int index;                                                      
}
/***********************************************************************
 *                            MIN_HEAP 访问方法
 ***********************************************************************/
#define MIN_HEAP_SIZE(heap)             ((heap)->size)
#define MIN_HEAP_COUNT(heap)            ((heap)->count)
#define MIN_HEAP_INDEX(elm, field)      ((elm)->field.index)
#define MIN_HEAP_ELMS(heap)             ((heap)->elements)
#define MIN_HEAP_ELM(heap, index)       ((heap)->elements[index - 1])
#define MIN_HEAP_CMP(heap)              ((heap)->cmp)
#define MIN_HEAP_GREATER(heap, e1, e2)  (((heap)->cmp(e1, e2)) > 0)
/***********************************************************************
 *                            MIN_HEAP 函数
 ***********************************************************************/
#define MIN_HEAP_TOP(heap)                              ({              
        (MIN_HEAP_COUNT(heap) ? *(MIN_HEAP_ELMS(heap)) : NULL);         
})
#define MIN_HEAP_SHIFT_UP(heap, index, elm, field)      do {            
        int _up_i = index;                                              
        int _parent = (_up_i) / 2;                                      
        while (_up_i > 1 && MIN_HEAP_GREATER(heap, MIN_HEAP_ELM(heap, _parent), elm)) { 
                MIN_HEAP_ELM(heap, _up_i) = MIN_HEAP_ELM(heap, _parent); 
                MIN_HEAP_INDEX(MIN_HEAP_ELM(heap, _up_i), field) = _up_i; 
                _up_i = _parent;                                        
                _parent = (_up_i) / 2;                                  
        }                                                               
        MIN_HEAP_ELM(heap, _up_i) = elm;                                
        MIN_HEAP_INDEX(MIN_HEAP_ELM(heap, _up_i), field) = _up_i;       
} while (0)
#define MIN_HEAP_SHIFT_DOWN(heap, index, elm, field)    do {            
        int _down_i = index;                                            
        int _child = 2 * (_down_i) + 1;                                 
        while (_child <= (MIN_HEAP_COUNT(heap) + 1)) {                  
                if (_child == MIN_HEAP_COUNT(heap) + 1 ||               
                                MIN_HEAP_GREATER(heap, MIN_HEAP_ELM(heap, _child), MIN_HEAP_ELM(heap, _child - 1))) { 
                        --_child;                                       
                }                                                       
                if (!MIN_HEAP_GREATER(heap, elm, MIN_HEAP_ELM(heap, _child))) { 
                        break;                                          
                }                                                       
                MIN_HEAP_ELM(heap, _down_i) = MIN_HEAP_ELM(heap, _child); 
                MIN_HEAP_INDEX(MIN_HEAP_ELM(heap, _down_i), field) = _down_i; 
                _down_i = _child;                                       
                _child = 2 * (_down_i) + 1;                             
        }                                                               
        MIN_HEAP_SHIFT_UP(heap, _down_i, elm, field);                   
} while (0)
#define MIN_HEAP_INITIALIZER(cmp)               {NULL, 0, 0, cmp}
#define MIN_HEAP_INIT(heap, cmp)                        do {            
        MIN_HEAP_ELMS(heap) = NULL;                                     
        MIN_HEAP_SIZE(heap) = 0;                                        
        MIN_HEAP_COUNT(heap) = 0;                                       
        MIN_HEAP_CMP(heap) = cmp;                                       
} while (0)
#define MIN_HEAP_DESTROY(heap)                          do {            
        free(MIN_HEAP_ELMS(heap));                                      
        MIN_HEAP_ELMS(heap) = NULL;                                     
        MIN_HEAP_COUNT(heap) = MIN_HEAP_SIZE(heap) = 0;                 
} while (0)
#define MIN_HEAP_ADD_SIZE(size)                 (size) = ((size) > 256 ? (size) * 3 / 2 : (size) ? (size) * 2 : 8)
#define MIN_HEAP_PUSH(heap, elm, field)                 do {            
        if (MIN_HEAP_COUNT(heap) >= MIN_HEAP_SIZE(heap)) {              
                MIN_HEAP_ADD_SIZE(MIN_HEAP_SIZE(heap));                 
                MIN_HEAP_ELMS(heap) = realloc(MIN_HEAP_ELMS(heap), MIN_HEAP_SIZE(heap) * sizeof(elm)); 
        } else if (MIN_HEAP_SIZE(heap) / 2 > MIN_HEAP_COUNT(heap) && MIN_HEAP_SIZE(heap) > 8) { 
                MIN_HEAP_SIZE(heap) = MIN_HEAP_SIZE(heap) * 3 / 4;      
                MIN_HEAP_ELMS(heap) = realloc(MIN_HEAP_ELMS(heap), MIN_HEAP_SIZE(heap) * sizeof(elm)); 
        }                                                               
        if (MIN_HEAP_COUNT(heap) < MIN_HEAP_SIZE(heap))                 
                MIN_HEAP_SHIFT_UP(heap, ++MIN_HEAP_COUNT(heap), elm, field); 
} while (0)
#define MIN_HEAP_POP(heap, elm, field)                  ({              
        if (MIN_HEAP_COUNT(heap)) {                                     
                elm = MIN_HEAP_TOP(heap);                               
                --MIN_HEAP_COUNT(heap);                                 
                MIN_HEAP_SHIFT_DOWN(heap, 1, MIN_HEAP_ELM(heap, MIN_HEAP_COUNT(heap) + 1), field); 
                MIN_HEAP_INDEX(elm, field) = 0;                         
        }                                                               
        else {                                                          
                (elm) = NULL;                                           
        }                                                               
        (elm);                                                          
})
#define MIN_HEAP_REMOVE(heap, elm, field)               do {            
        if (MIN_HEAP_INDEX(elm, field)) {                               
                --MIN_HEAP_COUNT(heap);                                 
                MIN_HEAP_SHIFT_DOWN(heap, MIN_HEAP_INDEX(elm, field), MIN_HEAP_ELM(heap, MIN_HEAP_COUNT(heap) + 1), field); 
                MIN_HEAP_INDEX(elm, field) = 0;                         
        }                                                               
} while (0)
#define MIN_HEAP_FREE(head)                             do {            
        free(MIN_HEAP_ELMS(heap));                                      
} while (0)
#define MIN_HEAP_FOREACH(heap, index, var, node)                        
        for ((index) = 1, (var) = MIN_HEAP_ELM(heap, index);            
                        (index) <= MIN_HEAP_COUNT(heap); ++(index), (var) = MIN_HEAP_ELM(heap, index))
#endif
// vim: ts=8 sw=8 expandtab

						