rtems 4.6
涉及文件
chain.h (cpukitlibcsupportinclude)提供用户程序接口，用户程序接口无下划线开头，内核程序使用下划线开头
/* chain.h * * This include file contains all the constants and structures associated * with doubly linked chains. This file actually just provides an * interface to the chain object in rtems. * * COPYRIGHT (c) 1989-1997. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may in * the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. * * $ld: */ #ifndef __CHAIN_h #define __CHAIN_h #include <rtems.h> /* * Chain_Initialize * * This routine initializes the_chain structure to manage the * contiguous array of number_nodes nodes which starts at * starting_address. Each node is of node_size bytes. * * Chain_Control *the_chain, * IN * * void *starting_address, * IN * * rtems_unsigned32 number_nodes, * IN * * rtems_unsigned32 node_size * IN * */ #define Chain_Initialize( the_chain, starting_address, number_nodes, node_size ) _Chain_Initialize( the_chain, starting_address, number_nodes, node_size ) /* * Chain_Initialize_empty * * This routine initializes the specified chain to contain zero nodes. * * Chain_Control *the_chain * IN * */ #define Chain_Initialize_empty( the_chain ) _Chain_Initialize_empty( the_chain ) /* * Chain_Are_nodes_equal * * This function returns TRUE if LEFT and RIGHT are equal, * and FALSE otherwise. * * Chain_Node *left, * IN * * Chain_Node *right * IN * */ #define Chain_Are_nodes_equal( left, right ) _Chain_Are_nodes_equal( left, right ) /* * Chain_Extract_unprotected * * This routine extracts the_node from the chain on which it resides. * It does NOT disable interrupts to insure the atomicity of the * extract operation. * * Chain_Node *the_node * IN * */ #define Chain_Extract_unprotected( the_node ) _Chain_Extract_unprotected( the_node ) /* * Chain_Extract * * This routine extracts the_node from the chain on which it resides. * It disables interrupts to insure the atomicity of the * extract operation. * * Chain_Node *the_node * IN * */ #define Chain_Extract( the_node ) _Chain_Extract( the_node ) /* * Chain_Get_unprotected * * This function removes the first node from the_chain and returns * a pointer to that node. If the_chain is empty, then NULL is returned. * It does NOT disable interrupts to insure the atomicity of the * get operation. * * Chain_Control *the_chain * IN * */ #define Chain_Get_unprotected( the_chain ) _Chain_Get_unprotected( the_chain ) /* * Chain_Get * * This function removes the first node from the_chain and returns * a pointer to that node. If the_chain is empty, then NULL is returned. * It disables interrupts to insure the atomicity of the * get operation. * * Chain_Control *the_chain * IN * */ #define Chain_Get( the_chain ) _Chain_Get( the_chain ) /* * Chain_Get_first_unprotected * * This function removes the first node from the_chain and returns * a pointer to that node. It does NOT disable interrupts to insure * the atomicity of the get operation. * * Chain_Control *the_chain * IN * */ #define Chain_Get_first_unprotected( the_chain ) _Chain_Get_first_unprotected( the_chain ) /* * Chain_Insert_unprotected * * This routine inserts the_node on a chain immediately following * after_node. It does NOT disable interrupts to insure the atomicity * of the extract operation. * * Chain_Node *after_node, * IN * * Chain_Node *the_node * IN * */ #define Chain_Insert_unprotected( after_node, the_node ) _Chain_Insert_unprotected( after_node, the_node ) /* * Chain_Insert * * This routine inserts the_node on a chain immediately following * after_node. It disables interrupts to insure the atomicity * of the extract operation. * * Chain_Node *after_node, * IN * * Chain_Node *the_node * IN * */ #define Chain_Insert( after_node, the_node ) _Chain_Insert( after_node, the_node ) /* * Chain_Append_unprotected * * This routine appends the_node onto the end of the_chain. * It does NOT disable interrupts to insure the atomicity of the * append operation. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Append_unprotected( the_chain, the_node ) _Chain_Append_unprotected( the_chain, the_node ) /* * Chain_Append * * This routine appends the_node onto the end of the_chain. * It disables interrupts to insure the atomicity of the * append operation. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Append( the_chain, the_node ) _Chain_Append( the_chain, the_node ) /* * Chain_Prepend_unprotected * * This routine prepends the_node onto the front of the_chain. * It does NOT disable interrupts to insure the atomicity of the * prepend operation. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Prepend_unprotected( the_chain, the_node ) _Chain_Prepend_unprotected( the_chain, the_node ) /* * Chain_Prepend * * This routine prepends the_node onto the front of the_chain. * It disables interrupts to insure the atomicity of the * prepend operation. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Prepend( the_chain, the_node ) _Chain_Prepend( the_chain, the_node ) /* * Chain_Head * * This function returns a pointer to the first node on the chain. * * Chain_Control *the_chain * IN * */ #define Chain_Head( the_chain ) _Chain_Head( the_chain ) /* * Chain_Tail * * This function returns a pointer to the last node on the chain. * * Chain_Control *the_chain * IN * */ #define Chain_Tail( the_chain ) _Chain_Tail( the_chain ) /* * Chain_Is_head * * This function returns TRUE if the_node is the head of the_chain and * FALSE otherwise. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Is_head( the_chain, the_node ) _Chain_Is_head( the_chain, the_node ) /* * Chain_Is_tail * * This function returns TRUE if the_node is the tail of the_chain and * FALSE otherwise. * * Chain_Control *the_chain, * IN * * Chain_Node *the_node * IN * */ #define Chain_Is_tail( the_chain, the_node ) _Chain_Is_tail( the_chain, the_node ) /* * Chain_Is_first * * This function returns TRUE if the_node is the first node on a chain and * FALSE otherwise. * * Chain_Node *the_node * IN * */ #define Chain_Is_first( the_node ) _Chain_Is_first( the_node ) /* * Chain_Is_last * * This function returns TRUE if the_node is the last node on a chain and * FALSE otherwise. * * Chain_Node *the_node * IN * */ #define Chain_Is_last( the_node ) _Chain_Is_last( the_node ) /* * Chain_Is_empty * * This function returns TRUE if there are no nodes on the_chain and * FALSE otherwise. * * Chain_Control *the_chain * IN * */ #define Chain_Is_empty( the_chain ) _Chain_Is_empty( the_chain ) /* * Chain_Has_only_one_node * * This function returns TRUE if there is only one node on the_chain and * FALSE otherwise. * * Chain_Control *the_chain * IN * */ #define Chain_Has_only_one_node( the_chain ) _Chain_Has_only_one_node( the_chain ) /* * Chain_Is_null * * This function returns TRUE if the_chain is NULL and FALSE otherwise. * * Chain_Control *the_chain * IN * */ #define Chain_Is_null( the_chain ) _Chain_Is_null( the_chain ) /* * Chain_Is_null_node * * This function returns TRUE if the_node is NULL and FALSE otherwise. * * Chain_Node *the_node * IN * */ #define Chain_Is_null_node( the_node ) _Chain_Is_null_node( the_node ) #undef __RTEMS_APPLICATION__ #include <rtems/score/chain.inl> #define __RTEMS_APPLICATION__ #endif /* end of include file */
chain.h (doc oolsmenu)，doc下有一个chain.h和chain.c
chain.h（cpukitscoreinclude temsscore）score下也有一个，实际用到应该是这一个
/* chain.h * * This include file contains all the constants and structures associated * with the Doubly Linked Chain Handler. * * COPYRIGHT (c) 1989-1999. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. * * chain.h,v 1.11.6.1 2003/09/04 18:55:05 joel Exp */ #ifndef __RTEMS_CHAIN_h #define __RTEMS_CHAIN_h #ifdef __cplusplus extern "C" { #endif #include <rtems/score/address.h> /* * This is used to manage each element (node) which is placed * on a chain. * * NOTE: Typically, a more complicated structure will use the * chain package. The more complicated structure will * include a chain node as the first element in its * control structure. It will then call the chain package * with a pointer to that node element. The node pointer * and the higher level structure start at the same address * so the user can cast the pointers back and forth. * */ typedef struct Chain_Node_struct Chain_Node; struct Chain_Node_struct { Chain_Node *next; Chain_Node *previous; }; /* * This is used to manage a chain. A chain consists of a doubly * linked list of zero or more nodes. * * NOTE: This implementation does not require special checks for * manipulating the first and last elements on the chain. * To accomplish this the chain control structure is * treated as two overlapping chain nodes. The permanent * head of the chain overlays a node structure on the * first and permanent_null fields. The permanent tail * of the chain overlays a node structure on the * permanent_null and last elements of the structure. * */ typedef struct { Chain_Node *first; Chain_Node *permanent_null; Chain_Node *last; } Chain_Control; /* * _Chain_Initialize * * DESCRIPTION: * * This routine initializes the_chain structure to manage the * contiguous array of number_nodes nodes which starts at * starting_address. Each node is of node_size bytes. * */ void _Chain_Initialize( Chain_Control *the_chain, void *starting_address, unsigned32 number_nodes, unsigned32 node_size ); /* * _Chain_Get_first_unprotected */ #ifndef USE_INLINES Chain_Node *_Chain_Get_first_unprotected( Chain_Control *the_chain ); #endif /* * _Chain_Extract * * DESCRIPTION: * * This routine extracts the_node from the chain on which it resides. * It disables interrupts to insure the atomicity of the * extract operation. * */ void _Chain_Extract( Chain_Node *the_node ); /* * _Chain_Get * * DESCRIPTION: * * This function removes the first node from the_chain and returns * a pointer to that node. If the_chain is empty, then NULL is returned. * It disables interrupts to insure the atomicity of the * get operation. * */ Chain_Node *_Chain_Get( Chain_Control *the_chain ); /* * _Chain_Insert * * DESCRIPTION: * * This routine inserts the_node on a chain immediately following * after_node. It disables interrupts to insure the atomicity * of the extract operation. * */ void _Chain_Insert( Chain_Node *after_node, Chain_Node *the_node ); /* * _Chain_Append * * DESCRIPTION: * * This routine appends the_node onto the end of the_chain. * It disables interrupts to insure the atomicity of the * append operation. * */ void _Chain_Append( Chain_Control *the_chain, Chain_Node *the_node ); #ifndef __RTEMS_APPLICATION__ #include <rtems/score/chain.inl> #endif #ifdef __cplusplus } #endif #endif /* end of include file */
chain.c (cpukitscoresrc)
/* * Chain Handler * * NOTE: * * The order of this file is to allow proper compilation due to the * order of inlining required by the compiler. * * COPYRIGHT (c) 1989-1999. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. * * chain.c,v 1.10.6.1 2003/09/04 18:52:47 joel Exp */ #include <rtems/system.h> #include <rtems/score/address.h> #include <rtems/score/chain.h> #include <rtems/score/isr.h> /*PAGE * * _Chain_Initialize * * This kernel routine initializes a doubly linked chain. * * Input parameters: * the_chain - pointer to chain header * starting_address - starting address of first node * number_nodes - number of nodes in chain * node_size - size of node in bytes * * Output parameters: NONE */ void _Chain_Initialize( Chain_Control *the_chain, void *starting_address, unsigned32 number_nodes, unsigned32 node_size ) { unsigned32 count; Chain_Node *current; Chain_Node *next; count = number_nodes; current = _Chain_Head( the_chain ); the_chain->permanent_null = NULL; next = (Chain_Node *)starting_address; while ( count-- ) { current->next = next; next->previous = current; current = next; next = (Chain_Node *) _Addresses_Add_offset( (void *) next, node_size ); } current->next = _Chain_Tail( the_chain ); the_chain->last = current; } /*PAGE * * _Chain_Get_first_unprotected */ #ifndef USE_INLINES Chain_Node *_Chain_Get_first_unprotected( Chain_Control *the_chain ) { Chain_Node *return_node; Chain_Node *new_first; return_node = the_chain->first; new_first = return_node->next; the_chain->first = new_first; new_first->previous = _Chain_Head( the_chain ); return return_node; } #endif /* USE_INLINES */ /*PAGE * * _Chain_Get * * This kernel routine returns a pointer to a node taken from the * given chain. * * Input parameters: * the_chain - pointer to chain header * * Output parameters: * return_node - pointer to node in chain allocated * CHAIN_END - if no nodes available * * INTERRUPT LATENCY: * only case */ Chain_Node *_Chain_Get( Chain_Control *the_chain ) { ISR_Level level; Chain_Node *return_node; return_node = NULL; _ISR_Disable( level ); if ( !_Chain_Is_empty( the_chain ) ) return_node = _Chain_Get_first_unprotected( the_chain ); _ISR_Enable( level ); return return_node; } /*PAGE * * _Chain_Append * * This kernel routine puts a node on the end of the specified chain. * * Input parameters: * the_chain - pointer to chain header * node - address of node to put at rear of chain * * Output parameters: NONE * * INTERRUPT LATENCY: * only case */ void _Chain_Append( Chain_Control *the_chain, Chain_Node *node ) { ISR_Level level; _ISR_Disable( level ); _Chain_Append_unprotected( the_chain, node ); _ISR_Enable( level ); } /*PAGE * * _Chain_Extract * * This kernel routine deletes the given node from a chain. * * Input parameters: * node - pointer to node in chain to be deleted * * Output parameters: NONE * * INTERRUPT LATENCY: * only case */ void _Chain_Extract( Chain_Node *node ) { ISR_Level level; _ISR_Disable( level ); _Chain_Extract_unprotected( node ); _ISR_Enable( level ); } /*PAGE * * _Chain_Insert * * This kernel routine inserts a given node after a specified node * a requested chain. * * Input parameters: * after_node - pointer to node in chain to be inserted after * node - pointer to node to be inserted * * Output parameters: NONE * * INTERRUPT LATENCY: * only case */ void _Chain_Insert( Chain_Node *after_node, Chain_Node *node ) { ISR_Level level; _ISR_Disable( level ); _Chain_Insert_unprotected( after_node, node ); _ISR_Enable( level ); }
chain用到了inline和macro，对于这两种形式，分别单独定义在不同的文件中
chain.inl (cpukitscoreinline temsscore)
/* inline/chain.inl * * This include file contains the bodies of the routines which are * associated with doubly linked chains and inlined. * * NOTE: The routines in this file are ordered from simple * to complex. No other Chain Handler routine is referenced * unless it has already been defined. * * COPYRIGHT (c) 1989-1999. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. * * chain.inl,v 1.9.6.1 2003/09/04 18:55:06 joel Exp */ #ifndef __INLINE_CHAIN_inl #define __INLINE_CHAIN_inl /*PAGE * * _Chain_Are_nodes_equal * * DESCRIPTION: * * This function returns TRUE if LEFT and RIGHT are equal, * and FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Are_nodes_equal( Chain_Node *left, Chain_Node *right ) { return left == right; } /*PAGE * * _Chain_Is_null * * DESCRIPTION: * * This function returns TRUE if the_chain is NULL and FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_null( Chain_Control *the_chain ) { return ( the_chain == NULL ); } /*PAGE * * _Chain_Is_null_node * * DESCRIPTION: * * This function returns TRUE if the_node is NULL and FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_null_node( Chain_Node *the_node ) { return ( the_node == NULL ); } /*PAGE * * _Chain_Head * * DESCRIPTION: * * This function returns a pointer to the first node on the chain. */ RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Head( Chain_Control *the_chain ) { return (Chain_Node *) the_chain; } /*PAGE * * _Chain_Tail * * DESCRIPTION: * * This function returns a pointer to the last node on the chain. */ RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Tail( Chain_Control *the_chain ) { return (Chain_Node *) &the_chain->permanent_null; } /*PAGE * * _Chain_Is_empty * * DESCRIPTION: * * This function returns TRUE if there a no nodes on the_chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_empty( Chain_Control *the_chain ) { return ( the_chain->first == _Chain_Tail( the_chain ) ); } /*PAGE * * _Chain_Is_first * * DESCRIPTION: * * This function returns TRUE if the_node is the first node on a chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_first( Chain_Node *the_node ) { return ( the_node->previous == NULL ); } /*PAGE * * _Chain_Is_last * * DESCRIPTION: * * This function returns TRUE if the_node is the last node on a chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_last( Chain_Node *the_node ) { return ( the_node->next == NULL ); } /*PAGE * * _Chain_Has_only_one_node * * DESCRIPTION: * * This function returns TRUE if there is only one node on the_chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Has_only_one_node( Chain_Control *the_chain ) { return ( the_chain->first == the_chain->last ); } /*PAGE * * _Chain_Is_head * * DESCRIPTION: * * This function returns TRUE if the_node is the head of the_chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_head( Chain_Control *the_chain, Chain_Node *the_node ) { return ( the_node == _Chain_Head( the_chain ) ); } /*PAGE * * _Chain_Is_tail * * DESCRIPTION: * * This function returns TRUE if the_node is the tail of the_chain and * FALSE otherwise. */ RTEMS_INLINE_ROUTINE boolean _Chain_Is_tail( Chain_Control *the_chain, Chain_Node *the_node ) { return ( the_node == _Chain_Tail( the_chain ) ); } /*PAGE * * Chain_Initialize_empty * * DESCRIPTION: * * This routine initializes the specified chain to contain zero nodes. */ RTEMS_INLINE_ROUTINE void _Chain_Initialize_empty( Chain_Control *the_chain ) { the_chain->first = _Chain_Tail( the_chain ); the_chain->permanent_null = NULL; the_chain->last = _Chain_Head( the_chain ); } /*PAGE * * _Chain_Extract_unprotected * * DESCRIPTION: * * This routine extracts the_node from the chain on which it resides. * It does NOT disable interrupts to insure the atomicity of the * extract operation. */ RTEMS_INLINE_ROUTINE void _Chain_Extract_unprotected( Chain_Node *the_node ) { Chain_Node *next; Chain_Node *previous; next = the_node->next; previous = the_node->previous; next->previous = previous; previous->next = next; } /*PAGE * * _Chain_Get_first_unprotected * * DESCRIPTION: * * This function removes the first node from the_chain and returns * a pointer to that node. It does NOT disable interrupts to insure * the atomicity of the get operation. */ RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_first_unprotected( Chain_Control *the_chain ) { Chain_Node *return_node; Chain_Node *new_first; return_node = the_chain->first; new_first = return_node->next; the_chain->first = new_first; new_first->previous = _Chain_Head( the_chain ); return return_node; } /*PAGE * * Chain_Get_unprotected * * DESCRIPTION: * * This function removes the first node from the_chain and returns * a pointer to that node. If the_chain is empty, then NULL is returned. * It does NOT disable interrupts to insure the atomicity of the * get operation. */ RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_unprotected( Chain_Control *the_chain ) { if ( !_Chain_Is_empty( the_chain ) ) return _Chain_Get_first_unprotected( the_chain ); else return NULL; } /*PAGE * * _Chain_Insert_unprotected * * DESCRIPTION: * * This routine inserts the_node on a chain immediately following * after_node. It does NOT disable interrupts to insure the atomicity * of the extract operation. */ RTEMS_INLINE_ROUTINE void _Chain_Insert_unprotected( Chain_Node *after_node, Chain_Node *the_node ) { Chain_Node *before_node; the_node->previous = after_node; before_node = after_node->next; after_node->next = the_node; the_node->next = before_node; before_node->previous = the_node; } /*PAGE * * _Chain_Append_unprotected * * DESCRIPTION: * * This routine appends the_node onto the end of the_chain. * It does NOT disable interrupts to insure the atomicity of the * append operation. */ RTEMS_INLINE_ROUTINE void _Chain_Append_unprotected( Chain_Control *the_chain, Chain_Node *the_node ) { Chain_Node *old_last_node; the_node->next = _Chain_Tail( the_chain ); old_last_node = the_chain->last; the_chain->last = the_node; old_last_node->next = the_node; the_node->previous = old_last_node; } /*PAGE * * _Chain_Prepend_unprotected * * DESCRIPTION: * * This routine prepends the_node onto the front of the_chain. * It does NOT disable interrupts to insure the atomicity of the * prepend operation. */ RTEMS_INLINE_ROUTINE void _Chain_Prepend_unprotected( Chain_Control *the_chain, Chain_Node *the_node ) { _Chain_Insert_unprotected( _Chain_Head( the_chain ), the_node ); } /*PAGE * * _Chain_Prepend * * DESCRIPTION: * * This routine prepends the_node onto the front of the_chain. * It disables interrupts to insure the atomicity of the * prepend operation. */ RTEMS_INLINE_ROUTINE void _Chain_Prepend( Chain_Control *the_chain, Chain_Node *the_node ) { _Chain_Insert( _Chain_Head( the_chain ), the_node ); } #endif /* end of include file */
chain.inl (cpukitscoremacros temsscore)
链表结构
下面对于Chain_Control的解释说，将control的前两个成员看成永久头，将后两个成员看成永久尾。
/* * This is used to manage a chain. A chain consists of a doubly * linked list of zero or more nodes. * * NOTE: This implementation does not require special checks for * manipulating the first and last elements on the chain. * To accomplish this the chain control structure is * treated as two overlapping chain nodes. The permanent * head of the chain overlays a node structure on the * first and permanent_null fields. The permanent tail * of the chain overlays a node structure on the * permanent_null and last elements of the structure. */ typedef struct { Chain_Node *first; Chain_Node *permanent_null; Chain_Node *last; } Chain_Control;
实际是通过下面两个头和尾获取函数实现的，将control指针类型转换为node指针类型：
1 /*PAGE 2 * 3 * _Chain_Head 4 * 5 * DESCRIPTION: 6 * 7 * This function returns a pointer to the first node on the chain. 8 */ 9 10 RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Head( 11 Chain_Control *the_chain 12 ) 13 { 14 return (Chain_Node *) the_chain; 15 } 16 17 /*PAGE 18 * 19 * _Chain_Tail 20 * 21 * DESCRIPTION: 22 * 23 * This function returns a pointer to the last node on the chain. 24 */ 25 26 RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Tail( 27 Chain_Control *the_chain 28 ) 29 { 30 return (Chain_Node *) &the_chain->permanent_null; 31 }
形成下图的效果：注意，永久头位于上半部分，永久尾位于下半部分。队列last指向永久头，队列first指向永久尾。
通过上面的结构，可以实现，对非空队列添加节点和对空队列添加节点的操作一致，删除也是一致。
比如对于空链表插入节点操作，
19行，相当于将插入节点的next设置链表永久尾。
20行，相当于将链表永久头赋值给old_last_node
21行，因为只有这1个节点，所以，last指向该节点
22行，old_last_node的next相当于control的first，因为只有这1个节点，所以，first也指向该节点
23行，插入节点的prev指向永久头节点
1 /*PAGE 2 * 3 * _Chain_Append_unprotected 4 * 5 * DESCRIPTION: 6 * 7 * This routine appends the_node onto the end of the_chain.10 */ 11 12 RTEMS_INLINE_ROUTINE void _Chain_Append_unprotected( 13 Chain_Control *the_chain, 14 Chain_Node *the_node 15 ) 16 { 17 Chain_Node *old_last_node; 18 19 the_node->next = _Chain_Tail( the_chain ); 20 old_last_node = the_chain->last; 21 the_chain->last = the_node; 22 old_last_node->next = the_node; 23 the_node->previous = old_last_node; 24 }
对于正常情况，
19行将插入节点的next指向队尾
23行将插入节点的prev指向最后一个节点
21行将队列最后节点指向插入节点
22行，原最后节点的next指向插入节点。
链表使用
链表使用时，需要将node放在实际节点的起始地址，后面再放实际节点的成员或指针。
rtems提供了一个初始化链表的函数_Chain_Initialize：该函数将starting_address起始的连续内存区域，划分为大小为node_size的连续内存块，内存块个数为number_nodes，然后，将这些内存块串成一个链表。
1 /*PAGE 2 * 3 * _Chain_Initialize 4 * 5 * This kernel routine initializes a doubly linked chain. 6 * 7 * Input parameters: 8 * the_chain - pointer to chain header 9 * starting_address - starting address of first node 10 * number_nodes - number of nodes in chain 11 * node_size - size of node in bytes 12 * 13 * Output parameters: NONE 14 */ 15 16 void _Chain_Initialize( 17 Chain_Control *the_chain, 18 void *starting_address, 19 unsigned32 number_nodes, 20 unsigned32 node_size 21 ) 22 { 23 unsigned32 count; 24 Chain_Node *current; 25 Chain_Node *next; 26 27 count = number_nodes; 28 current = _Chain_Head( the_chain ); 29 the_chain->permanent_null = NULL; 30 next = (Chain_Node *)starting_address; 31 while ( count-- ) { 32 current->next = next; 33 next->previous = current; 34 current = next; 35 next = (Chain_Node *) 36 _Addresses_Add_offset( (void *) next, node_size ); 37 } 38 current->next = _Chain_Tail( the_chain ); 39 the_chain->last = current; 40 }
其中，_Addresses_Add_offset定义如下
1 RTEMS_INLINE_ROUTINE void *_Addresses_Add_offset ( 2 void *base, 3 unsigned32 offset 4 ) 5 { 6 return (void *)((char *)base + offset); 7 }
链表使用例子
在FillLinePool in bmenu2.c (doc oolsmenu)中有个使用例子，pool为分配的连续内存区域，大小为100*size，输入给_Chain_Initialize的参数未连续内存起始地址，内存块数量，内存块大小。内存块即为节点的大小。
1 void FillLinePool( void ) 2 { 3 void *pool; 4 5 #define LINE_POOL_FILL_COUNT 100 6 7 pool = malloc( sizeof( Line_Control ) * LINE_POOL_FILL_COUNT ); 8 assert( pool ); 9 10 _Chain_Initialize( 11 &Line_Pool, 12 pool, 13 LINE_POOL_FILL_COUNT, 14 sizeof( Line_Control ) 15 ); 16 }
其中，定义如下：
1 typedef struct { 2 Chain_Node Node; 3 Keyword_indices_t keyword; /* unused is unknown/undecided */ 4 ExtraFormat_info_t format; 5 int number; 6 int level; 7 char Contents[ PARAGRAPH_SIZE ]; 8 } Line_Control;