C实现一个环形链表

小灰灰 2022-12-28 04:12 125阅读 0赞

# 实现 #

## 初始化链表的哨兵节点 ##

1、需要什么？

*  链表的首地址

2、无需返回值

3、怎么做：  
(1) 如果链表的首地址为NULL，直接返回；否则跳到(2)  
(2)令ring的前驱后续以及parent都指向ring，以及初始化ring.len = 0

void acl_ring_init(ACL_RING *ring){
        
        if(ring == NULL){
        
            return;
        }
    
        ring->pred = ring->succ = ring;
        ring->parent = ring;
        ring->len = 0;
    }

## 获取当前数据环元素个数 ##

1、需要什么？

*  链表的首地址

2、返回数组个数

3、怎么做：  
(1) 如果链表的首地址为NULL，直接返回-1；否则跳到(2)  
(2) 返回ring.len

## 将一个新元素添加进环的头部 ##

1、需要什么

*  链表的首地址
 *  待添加的环地址entry

2、无需返回值

3、怎么做：  
(1) 如果环为NULL或者新元素为NULL直接返回  
(2) 令 `entry`的后继指向哨兵节点的后继（则`哨兵节点`后继的前驱为`entry`）  
令`entry`的前驱指向哨兵节点（则`哨兵节点`的后继为`entry`）  
令`entry.parent = ring.parent, ring.parent.len++`

void acl_ring_append(ACL_RING *ring, ACL_RING *entry)
    {
        
    	if (ring == NULL || entry == NULL)
    		return;
    	entry->succ      = ring->succ;
    	entry->pred      = ring;
    	entry->parent    = ring->parent;
    	ring->succ->pred = entry;
    	ring->succ       = entry;
    	ring->parent->len++;
    }

## 将一个新元素添加进环的尾部 ##

1、需要什么

*  链表的首地址
 *  待添加的环地址entry

2、无需返回值

3、怎么做：  
(1) 如果环为NULL或者新元素为NULL直接返回  
(2) 令 `entry`的前驱指向哨兵节点的后继（则`哨兵节点`后继的前驱为`entry`）  
令`entry`的后继指向哨兵节点（则`哨兵节点`的前驱为`entry`）  
令`entry.parent = ring.parent, ring.parent.len++`

void acl_ring_prepend(ACL_RING *ring, ACL_RING *entry)
    {
        
    	if (ring == NULL || entry == NULL)
    		return;
    	entry->pred      = ring->pred;
    	entry->succ      = ring;
    	entry->parent    = ring->parent;
    	ring->pred->succ = entry;
    	ring->pred       = entry;
    	ring->parent->len++;
    }

## 将一个环元素从数据环中删除 ##

1、需要什么  
待删除元素的地址entry

2、无需返回值

3、怎么做  
（1）如果entry为NULL或者entry为哨兵节点，直接返回  
（2）取得entry的前驱与后继

*  如果前驱或者后继为NULL（环只有哨兵节点，还没有其他数据），直接返回
 *  令entry的前驱的后继指向后继；后继的前驱指向前驱

（3）令entry.parent.len++；entry的前驱、后继、parent都指向自身、entry.len = 0

void acl_ring_detach(ACL_RING *entry)
    {
        
    	ACL_RING   *succ;
    	ACL_RING   *pred;
    
    	if (entry == NULL || entry->parent == entry)
    		return;
    	succ = entry->succ;
    	pred = entry->pred;
    	if (succ == NULL || pred == NULL)
    		return;
    	pred->succ = succ;
    	succ->pred = pred;
    
    	entry->parent->len--;
    
    	entry->succ = entry->pred = entry;
    	entry->parent = entry;
    	entry->len = 0;
    }

## 从环中弹出头部环元素 ##

1、需要什么：

*  环地址

2、返回值：

*  头部环元素，如果返回NULL表示该数据环为NULL

3、怎么做  
（1）如果ring=NULL，返回NULL  
（2）取出ring的后继，如果后继为NULL，则直接返回；否则跳到（3）  
（3）将后继从环中删除，然后返回这个元素

ACL_RING *acl_ring_pop_head(ACL_RING *ring)
    {
        
    	ACL_RING   *succ;
    
    	if (ring == NULL)
    		return NULL;
    
    	succ = ring->succ;
    	if (succ == ring)
    		return NULL;
    
    	acl_ring_detach(succ);
    
    	return succ;
    }

## 从环中弹出尾部环元素 ##

ACL_RING *acl_ring_pop_tail(ACL_RING *ring)
    {
        
    	ACL_RING   *pred;
    
    	if (ring == NULL)
    		return NULL;
    
    	pred = ring->pred;
    	if (pred == ring)
    		return NULL;
    
    	acl_ring_detach(pred);
    
    	return pred;
    }

# 总结 #

#include <lzma.h>
    #include "acl_ring.h"
    /* acl_ring_init - initialize ring head */
    void acl_ring_init(ACL_RING *ring)
    {
        
        if (ring == NULL)
            return;
        ring->pred   = ring->succ = ring;
        ring->parent = ring;
        ring->len    = 0;
    }
    
    /* acl_ring_size - the entry number in the ring */
    
    int acl_ring_size(const ACL_RING *ring)
    {
        
        if (ring == NULL)
            return -1;
    
        return ring->len;
    }
    
    /* acl_ring_append - insert entry after ring head */
    
    void acl_ring_append(ACL_RING *ring, ACL_RING *entry)
    {
        
        if (ring == NULL || entry == NULL)
            return;
        entry->succ      = ring->succ;
        entry->pred      = ring;
        entry->parent    = ring->parent;
        ring->succ->pred = entry;
        ring->succ       = entry;
        ring->parent->len++;
    }
    
    /* acl_ring_prepend - insert new entry before ring head */
    void acl_ring_prepend(ACL_RING *ring, ACL_RING *entry)
    {
        
        if (ring == NULL || entry == NULL)
            return;
        entry->pred      = ring->pred;
        entry->succ      = ring;
        entry->parent    = ring->parent;
        ring->pred->succ = entry;
        ring->pred       = entry;
        ring->parent->len++;
    }
    
    /* acl_ring_detach - remove entry from ring */
    
    void acl_ring_detach(ACL_RING *entry)
    {
        
        ACL_RING   *succ;
        ACL_RING   *pred;
    
        if (entry == NULL || entry->parent == entry)
            return;
        succ = entry->succ;
        pred = entry->pred;
        if (succ == NULL || pred == NULL)
            return;
        pred->succ = succ;
        succ->pred = pred;
    
        entry->parent->len--;
    
        entry->succ = entry->pred = entry;
        entry->parent = entry;
        entry->len = 0;
    }
    
    /* acl_ring_pop_head - pop ring's head entry out from ring */
    
    ACL_RING *acl_ring_pop_head(ACL_RING *ring)
    {
        
        ACL_RING   *succ;
    
        if (ring == NULL)
            return NULL;
    
        succ = ring->succ;
        if (succ == ring)
            return NULL;
    
        acl_ring_detach(succ);
    
        return succ;
    }
    
    /* acl_ring_pop_tail - pop ring's tail entry out from ring */
    
    ACL_RING *acl_ring_pop_tail(ACL_RING *ring)
    {
        
        ACL_RING   *pred;
    
        if (ring == NULL)
            return NULL;
    
        pred = ring->pred;
        if (pred == ring)
            return NULL;
    
        acl_ring_detach(pred);
    
        return pred;
    }

acl\_ring.h

#pragma once
    #include <stddef.h>
    typedef struct ACL_RING ACL_RING;
    
    /**
     * 数据环结构类型定义
     */
    struct ACL_RING {
        
        ACL_RING *succ;           /**< successor */
        ACL_RING *pred;           /**< predecessor */
    
        ACL_RING *parent;         /**< the header of all the rings */
        int len;                  /**< the count in the ring */
    };
    
    typedef struct ACL_RING_ITER {
        
        ACL_RING *ptr;
    } ACL_RING_ITER;
    
    
    /**
     * 初始化数据环
     * @param ring {ACL_RING*} 数据环
     */
    void acl_ring_init(ACL_RING *ring);
    /**
     * 获得当前数据环内元素个数
     * @param ring {ACL_RING*} 数据环
     * @return {int} 数据环内元素个数
     */
     int  acl_ring_size(const ACL_RING *ring);
    
    /**
     * 将一个新元素添加进环的头部
     * @param ring {ACL_RING*} 数据环
     * @param entry {ACL_RING*} 新的元素
     */
    void acl_ring_prepend(ACL_RING *ring, ACL_RING *entry);
    
    /**
     * 将一个新元素添加进环的尾部
     * @param ring {ACL_RING*} 数据环
     * @param entry {ACL_RING*} 新的元素
     */
    void acl_ring_append(ACL_RING *ring, ACL_RING *entry);
    
    /**
     * 将一个环元素从数据环中删除
     * @param entry {ACL_RING*} 环元素
     */
    void acl_ring_detach(ACL_RING *entry);
    
    /**
     * 从环中弹出头部环元素
     * @param ring {ACL_RING*} 数据环
     * @return {ACL_RING*} 头部环元素，如果返回空则表示该数据环为空
     */
    ACL_RING *acl_ring_pop_head(ACL_RING *ring);
    
    /**
     * 从环中弹出尾部环元素
     * @param ring {ACL_RING*} 数据环
     * @return {ACL_RING*} 尾部环元素，如果返回空则表示该数据环为空
     */
    ACL_RING *acl_ring_pop_tail(ACL_RING *ring);
    
    /*--------------------  一些方便快捷的宏操作 --------------------------------*/
    
    /**
     * 返回当前环元素的下一个环元素
     */
    #define ACL_RING_SUCC(c) ((c)->succ)
    #define	acl_ring_succ	ACL_RING_SUCC
    
    /**
     * 返回当前环元素的前一个环元素
     */
    #define ACL_RING_PRED(c) ((c)->pred)
    #define	acl_ring_pred	ACL_RING_PRED
    
    /**
     * 将环元素指针转换成应用的自定义类型的指针地址
     * @param ring_ptr {ACL_RING*} 环元素指针
     * @param app_type 应用自定义类型
     * @param ring_member {ACL_RING*} 环元素在应用自定义结构中的成员名称
     * @return {app_type*} 应用自定义结构类型的对象地址
     */
    #define ACL_RING_TO_APPL(ring_ptr, app_type, ring_member) \
        ((app_type *) (((char *) (ring_ptr)) - offsetof(app_type,ring_member)))
    
    #define	acl_ring_to_appl	ACL_RING_TO_APPL
    
    
    #define	ACL_RING_FOREACH(iter, head_ptr) \
            for ((iter).ptr = acl_ring_succ((head_ptr)); (iter).ptr != (head_ptr);  \
                 (iter).ptr = acl_ring_succ((iter).ptr))
    
    #define	acl_ring_foreach		ACL_RING_FOREACH
    
    /**
     * 从尾部至头部遍历数据环中的所有环元素
     * @param iter {ACL_RING_ITER}
     * @param head_ptr {ACL_RING*} 数据环的头指针
     */
    #define	ACL_RING_FOREACH_REVERSE(iter, head_ptr) \
            for ((iter).ptr = acl_ring_pred((head_ptr)); (iter).ptr != (head_ptr);  \
                 (iter).ptr = acl_ring_pred((iter).ptr))
    
    #define	acl_ring_foreach_reverse	ACL_RING_FOREACH_REVERSE
    
    /**
     * 返回数据环中第一个环元素指针
     * @param head {ACL_RING*} 环头指针
     * @return {ACL_RING*} NULL: 环为空
     */
    #define ACL_RING_FIRST(head) \
    	(acl_ring_succ(head) != (head) ? acl_ring_succ(head) : 0)
    
    #define	acl_ring_first		ACL_RING_FIRST
    
    /**
     * 返回数据环中头第一个环元素指针同时将其转换应用自定义结构类型的对象地址
     * @param head {ACL_RING*} 环头指针
     * @param app_type 应用自定义结构类型
     * @param ring_member {ACL_RING*} 环元素在应用自定义结构中的成员名称
     * @return {app_type*} 应用自定义结构类型的对象地址
     */
    #define ACL_RING_FIRST_APPL(head, app_type, ring_member) \
    	(acl_ring_succ(head) != (head) ? \
    	 ACL_RING_TO_APPL(acl_ring_succ(head), app_type, ring_member) : 0)
    
    #define	acl_ring_first_appl	ACL_RING_FIRST_APPL
    
    /**
     * 返回数据环中最后一个环元素指针
     * @param head {ACL_RING*} 环头指针
     * @return {ACL_RING*} NULL: 环为空
     */
    #define ACL_RING_LAST(head) \
           (acl_ring_pred(head) != (head) ? acl_ring_pred(head) : 0)
    
    #define	acl_ring_last		ACL_RING_LAST
    
    /**
     * 返回数据环中最后一个环元素指针同时将其转换应用自定义结构类型的对象地址
     * @param head {ACL_RING*} 环头指针
     * @param app_type 应用自定义结构类型
     * @param ring_member {ACL_RING*} 环元素在应用自定义结构中的成员名称
     * @return {app_type*} 应用自定义结构类型的对象地址
     */
    #define ACL_RING_LAST_APPL(head, app_type, ring_member) \
           (acl_ring_pred(head) != (head) ? \
    	ACL_RING_TO_APPL(acl_ring_pred(head), app_type, ring_member) : 0)
    
    #define	acl_ring_last_appl	ACL_RING_LAST_APPL
    
    /**
     * 将一个新元素添加进环的尾部
     * @param ring {ACL_RING*} 数据环
     * @param entry {ACL_RING*} 新的元素
     */
    #define	ACL_RING_APPEND(ring_in, entry_in) do {  \
    	ACL_RING *ring_ptr = (ring_in), *entry_ptr = (entry_in);  \
            entry_ptr->succ      = ring_ptr->succ;  \
            entry_ptr->pred      = ring_ptr;  \
            entry_ptr->parent    = ring_ptr->parent;  \
            ring_ptr->succ->pred = entry_ptr;  \
            ring_ptr->succ       = entry_ptr;  \
            ring_ptr->parent->len++;  \
    } while (0)
    
    /**
     * 将一个新元素添加进环的头部
     * @param ring {ACL_RING*} 数据环
     * @param entry {ACL_RING*} 新的元素
     */
    #define	ACL_RING_PREPEND(ring_in, entry_in) do {  \
    	ACL_RING *ring_ptr = (ring_in), *entry_ptr = (entry_in);  \
    	entry_ptr->pred      = ring_ptr->pred;  \
    	entry_ptr->succ      = ring_ptr;  \
    	entry_ptr->parent    = ring_ptr->parent;  \
    	ring_ptr->pred->succ = entry_ptr;  \
    	ring_ptr->pred       = entry_ptr;  \
    	ring_ptr->parent->len++;  \
    } while (0)
    
    /**
     * 将一个环元素从数据环中删除
     * @param entry {ACL_RING*} 环元素
     */
    #define	ACL_RING_DETACH(entry_in) do {  \
    	ACL_RING   *succ, *pred, *entry_ptr = (entry_in);  \
    	succ = entry_ptr->succ;  \
    	pred = entry_ptr->pred;  \
    	if (succ != NULL && pred != NULL) {  \
    		pred->succ = succ;  \
    		succ->pred = pred;  \
    		entry_ptr->parent->len--;  \
    		entry_ptr->succ = entry_ptr->pred = NULL;  \
    	}  \
    } while (0)

3、main.c

#include <stdio.h>
    #include "stdlib.h"
    #include "acl_ring.h"
    
    typedef struct {
        
        char  name[32];
        ACL_RING entry;
    } DUMMY;
    
    void test()
    {
        
        ACL_RING head;
        DUMMY *dummy;
        ACL_RING_ITER iter;
        int   i;
    
        acl_ring_init(&head);
    
        for (i = 0; i < 10; i++) {
        
            dummy = (DUMMY*) calloc(1, sizeof(DUMMY));
            snprintf(dummy->name, sizeof(dummy->name), "dummy:%d", i);
            acl_ring_append(&head, &dummy->entry);
        }
    
        acl_ring_foreach(iter, &head) {
        
            dummy = acl_ring_to_appl(iter.ptr, DUMMY, entry);
            printf("name: %s\n", dummy->name);
        }
    
        while (1) {
        
            iter.ptr = acl_ring_pop_head(&head);
            if (iter.ptr == NULL)
                break;
            dummy = acl_ring_to_appl(iter.ptr, DUMMY, entry);
            free(dummy);
        }
    }
    int main(void)
    {
        
        test();
        return 0;
    }