Linked List

#ifndef __LIST_H__ #define __LIST_H__ #include <stdint.h> #define LIST_ITEM_VAR() LIST_ITEM_T item #define LIST_ITEM_PTR(x) LIST_ITEM_T * x #define LIST_ITEM_PAIR(x, y) LIST_ITEM_T * x, * y //#define list_entry(pItem, T) ( (T *)(pItem) ) #define LIST_ITEM_U8_PTR( pItem ) ( (uint8_t *)(pItem) ) #define LIST_ITEM_OFFSET( T, mItem ) ( (uint32_t) ( &( (T *) 0)->mItem) ) #define list_entry(T, pItem ) \ ( (T *) ( LIST_ITEM_U8_PTR( pItem ) - LIST_ITEM_OFFSET( T, item ) ) ) // iterate over a list safe against removal of list entry // // pList : LIST_T // pItem : LIST_ITEM_T < loop counter > // pTempItem : LIST_ITEM_T < temporary storage > // #define list_for_each( pList, pItem, pTemp ) \ for ( pItem = ((pList)->Head).pNext, \ pTemp = pItem->pNext; \ pItem != (& (pList)->Head ); \ pItem = pTemp, pTemp = pItem->pNext ) typedef struct _LIST_ITEM { struct _LIST_ITEM * pNext; struct _LIST_ITEM * pPrev; } LIST_ITEM_T; typedef struct { LIST_ITEM_T Head; uint32_t count; } LIST_T; void list_init( LIST_T * pList ); void list_remove( LIST_T * pList, LIST_ITEM_T * pItem ); void list_insert( LIST_T * pList, LIST_ITEM_T * pItem ); void list_append( LIST_T * pList, LIST_ITEM_T * pItem ); void list_make_first( LIST_T * pList, LIST_ITEM_T * pItem ); void list_make_last( LIST_T * pList, LIST_ITEM_T * pItem ); #endif /* __LIST_H__ */ #include "list.h" void list_item_init( LIST_ITEM_T * pItem ) { pItem->pNext = pItem; pItem->pPrev = pItem; } void list_item_replace( LIST_ITEM_T *pNew, LIST_ITEM_T *pOld ) { pNew->pNext = pOld->pNext; pNew->pNext->pPrev = pNew; pNew->pPrev = pOld->pPrev; pNew->pPrev->pNext = pNew; list_item_init( pOld ); } // Insert a new entry between two known consecutive entries void list_item_add( // LIST_ITEM_T *pItem, LIST_ITEM_T *pPrev, LIST_ITEM_T *pNext ) { pNext->pPrev = pItem; pItem->pNext = pNext; pItem->pPrev = pPrev; pPrev->pNext = pItem; } // Delete a list entry by making the prev/next entries point to each other void list_item_del( LIST_ITEM_T *pPrev, LIST_ITEM_T *pNext ) { pNext->pPrev = pPrev; pPrev->pNext = pNext; } void list_init( LIST_T * pList ) { pList->count = 0; list_item_init( &pList->Head ); } // tests whether a list is empty unsigned int list_empty( LIST_T * pList ) { return ( pList->count == 0 ); // return ( &( pList->Head ).pNext = &( pList->Head ) ); // return ( &( pList->Head ).pPrev = &( pList->Head ) ); } void list_insert( LIST_T * pList, LIST_ITEM_T * pItem ) { list_item_add( pItem, &pList->Head, ( &pList->Head )->pNext ); pList->count++; } void list_append( LIST_T * pList, LIST_ITEM_T * pItem ) { list_item_add( pItem, ( &pList->Head )->pPrev, ( &pList->Head ) ); pList->count++; } // deletes entry from list and reinitialize it void list_remove( LIST_T * pList, LIST_ITEM_T * pItem ) { list_item_del( pItem->pPrev, pItem->pNext ); list_item_init( pItem ); pList->count--; } void list_make_first( LIST_T * pList, LIST_ITEM_T * pItem ) { list_remove( pList, pItem ); list_insert( pList, pItem ); } void list_make_last( LIST_T * pList, LIST_ITEM_T * pItem ) { list_remove( pList, pItem ); list_append( pList, pItem ); } void list_demo_func( int * pi ) { ( *pi )++; } #define ITEM_COUNT ( 4 ) void list_demo( void ) { typedef struct { LIST_ITEM_VAR(); void (*func)( int * pi ); int a; } STRUCT_T; LIST_T list; STRUCT_T items[ ITEM_COUNT ]; STRUCT_T * pStruct; list_init( &list ); // Head <--> Items[0] <--> Items[1] <--> Items[2] <--> Items[3] <--> Head for ( unsigned int i = 0; i < ITEM_COUNT; i++ ) list_append( &list, &items[ i ].item ); unsigned int x = 0; LIST_ITEM_PAIR( pItem, pTemp ); list_for_each( &list, pItem, pTemp) { pStruct = list_entry( STRUCT_T, pItem ); pStruct->a = x++; pStruct->func = list_demo_func; pStruct->func( &pStruct->a ); } // Head <--> Items[0] <--> Items[1] <--> Items[3] <--> Head list_for_each( &list, pItem, pTemp) { pStruct = list_entry( STRUCT_T, pItem ); if ( pStruct->a == 3 ) list_remove( &list, pItem ); } }

 

#ifndef __LIST_H__ #define __LIST_H__ #include <stdint.h> #define LIST_NODE_HEAD( TAG ) \ typedef struct TAG \ { \ LIST_ITEM_T list_item; #define LIST_NODE_TAIL( NODE ) \ } NODE; typedef struct _LIST_ITEM { struct _LIST_ITEM * pNext; struct _LIST_ITEM * pPrev; } LIST_ITEM_T; typedef struct { LIST_ITEM_T * pHead; uint32_t count; } LIST_T; void list_init( LIST_T * pList ); void list_delete( LIST_T * pList, void * pNode ); void list_insert( LIST_T * pList, void * pNode, uint32_t tail ); void * list_get_head( LIST_T * pList ); void * list_get_next( LIST_T * pList, void * pNode ); #endif /* __LIST_H__ */ #include "list.h" void list_init( LIST_T * pList ) { pList->count = 0; pList->pHead = 0; } void * list_get_head( LIST_T * pList ) { if ( pList->count == 0 ) return 0; return pList->pHead; } void * list_get_next( LIST_T * pList, void * pNode ) { LIST_ITEM_T * pItem = (LIST_ITEM_T *) ( pNode ); if ( pItem->pNext == pList->pHead ) return 0; return pItem->pNext; } void list_insert( LIST_T * pList, void * pNode, uint32_t tail ) { LIST_ITEM_T * pItem = (LIST_ITEM_T *) ( pNode ); if ( pList->count == 0 ) { pItem->pNext = pItem; pItem->pPrev = pItem; } else { pItem->pNext = pList->pHead; pItem->pPrev = pList->pHead->pPrev; pList->pHead->pPrev->pNext = pItem; pList->pHead->pPrev = pItem; } if ( tail ) pList->pHead = pItem->pNext; else pList->pHead = pItem; pList->count++; } void list_delete( LIST_T * pList, void * pNode ) { LIST_ITEM_T * pItem = LIST_ITEM_PTR( pNode ); if ( pList->count ) { if ( pItem == pList->pHead ) pList->pHead = pItem->pNext; pItem->pNext->pPrev = pItem->pPrev; pItem->pPrev->pNext = pItem->pNext; pList->count--; } } LIST_NODE_HEAD( _S ) uint32_t memb; LIST_NODE_TAIL( S ) void list_demo( void ) { LIST_T list; S s[ 4 ]; S * pS; list_init( &list ); for ( uint32_t i = 0; i < 4; i++ ) list_insert( &list, &s[ i ], 1 ); pS = (S *) list_get_head( &list ); while ( pS ) { pS->memb = (uint32_t) pS; pS = (S *) list_get_next( &list, pS ); } for ( uint32_t i = 0; i < 4; i++ ) list_delete( &list, &s[ i ] ); }

 

转载于:https://www.cnblogs.com/shangdawei/archive/2013/04/24/3041313.html

相关资源：数据结构—成绩单生成器