Next: , Previous: Chain selector, Up: Chains


13.5 Inserting and deleting nodes in a chain

Nodes can be inserted and deleted in a chain either at one end of the chain, or in a sorted fashion. This allows chains to behave as sorted linked lists, queues, or stacks.

13.5.1 Chains as sorted linked lists

— Function: Chainlink * chain_insert (Chain *chain, void *data, Chain_compare_f compare, void *cmp_args)

Creates a node containing data and inserts it at the correct place in chain, such that chain remains sorted increasing according to compare. cmp_args is passed as the last argument to cmp. Returns a pointer to the node thus created, or a null pointer if there was insufficient memory.

13.5.2 Chains as stacks

To use a chain as a stack, insertion and deletion of nodes must be performed only at one end of the chain; the functions here alter the chain only at the front.

— Function: Chainlink * chain_push (Chain *chain, void *data)

Creates a node containing data and inserts it at the front of chain. Returns a pointer to the chainlink thus created, or a null pointer if there was insufficient memory.

— Function: void * chain_pop (Chain *chain)

Removes the node at the front of chain, returning the result of applying ‘chainlink_data’ to that node. chain must contain at least one node.

— Function: void chain_drop (Chain *chain)

Removes the node at the front of chain. Note that this function provides no way to free any dynamically-allocated data stored in that node. chain must contain at least one node.

— Function: Chainlink * chain_top (const Chain *chain)

Returns a reference to the first node in chain; that is, the node which is the top of the stack. If there are no nodes in chain, a null pointer is returned. This function is equivalent to ‘chain_front’.

13.5.3 Chains as queues

To use a chain as a queue, insertions are performed only at the back of the chain, while deletions are performed only at the front.

— Function: Chainlink * chain_enqueue (Chain *chain, void *data)

Creates a node containing data and inserts it at the end of chain. Returns a pointer to the node thus created, or a null pointer if there was insufficient memory.

— Function: void * chain_dequeue (Chain *chain)

Removes the node at the front of chain, returning the result of applying ‘chainlink_data’ to that node. chain must contain at least one node. This function is equivalent to ‘chain_pop’.

13.5.4 Insertion and deletion at specific locations

It is also possible to specify explicitly the end at which an insertion or deletion is to be performed.

— Function: Chainlink * chain_front_insert (Chain *chain, void *data)

Creates a node containing data and inserts it at the front of chain. Returns a pointer to the node thus created, or a null pointer if there was insufficient memory.

— Function: void * chain_front_remove (Chain *chain)

Removes the node at the front of chain, returning the result of applying ‘chainlink_data’ to that node. chain must contain at least one node.

— Function: Chainlink * chain_back_insert (Chain *chain, void *data)
— Function: Chainlink * chain_append (Chain *chain, void *data)

Creates a new node containing data and inserts it at the end of chain. Returns a pointer to the node thus created, or a null pointer if there was insufficient memory. ‘chain_append’ is a synonym for ‘chain_back_insert’.

— Function: void * chain_back_remove (Chain *chain)

Removes the node at the end of chain, returning the result of applying ‘chainlink_data’ to that node. chain must contain at least one node.

13.5.5 Miscellaneous insertion and deletion functions

— Function: void chain_move_front (Chain *chain, Chainlink *node)
— Function: void chain_move_back (Chain *chain, Chainlink *node)

Move node to the front or back respectively of chain. node must be a member of chain.1

— Function: void chain_remove (Chain *chain, Chainlink *node)

Removes node from chain. node must be a member of chain. The contents of node are undefined on return.

— Function: void chain_wipe (Chain *chain)

Deletes all the nodes in chain.

It is also possible to selectively delete more than one object in a chain at once. This requires a `pruning' function.

— Function pointer: Chain_prune_f int (*) (void *obj, void *args)

The type of a function pointer used to determine whether to delete objects in a chain. It is passed a reference to the contents of an element in obj, as well as a pointer to user-supplied arguments in args. It should return zero if and only if the element should not be deleted. Note that if the elements of a chain were dynamically allocated, it is probably a good idea to make the pruning function free this dynamically allocated memory.

— Function: void chain_prune (Chain *chain, Chain_prune_f pruner, void *prune_args)

Deletes any objects in chain for which pruner is true. prune_args is passed as the last argument to pruner.


Footnotes

[1] These functions qualify as `insertion and deletion functions' by virtue of the fact that they correspond to a deletion and insertion performed in one operation.