ilists

The Engine Internals: Lists

Data Structures

:::C
typedef struct _node_t { 
    struct _node_t* next;
    struct _node_t* prev;
} node_t;

This data structure is used for chaining nodes in a doubly-linked list. Use it as an aggregate at the beginning of your own structure to chain nodes together.

:::C
typedef struct _list_t { node_t head, tail; } list_t;

This data structure is used as a list data structure. It contains two nodes, a head node and a tail node, which are meant only for bookkeeping purposes. Hence, the user-supplied nodes are always between the head node and the tail node.

When a list is empty, head and tail node point to each other.

Functions

:::C
void initNode( node_t* n );

Initializes a node to (0,0), i.e. the fields are cleared. This makes it easier to detect whether a node is installed into a list.

:::C
void linkNode( node_t* p, node_t* c, node_t* n ); 

Internal function that shouldn't be used directly. It directly chains three nodes together, by modifying their pointers. p specifies the previous node, c specifies the current or middle node, and n specifies the next node.

:::C
void unlinkNode( node_t* n );

Function to remove a node if it was in a list. It first checks if both next and prev fields are set, and if so, unlinks the node from the list and clears the next and prev fields.

:::C
void initList( list_t* l );

Initialize a list so that head and tail point to each other.

:::C
void addHead( list_t* l, node_t* n ); 

Insert a node at the beginning of a list (after the head node).

:::C
void addTail( list_t* l, node_t* n ); 

Insert a node at the end of a list (after the tail node).

:::C
bool listEmpty( list_t* l ); 

Test if a list is empty.

:::C
node_t* firstNode( list_t* l );

Returns the first node of a list, or 0. The first node is the node following the head node, unless the head node points to the tail node.

:::C
node_t* lastNode( list_t* l ); 

Returns the last node of a list, or 0. The last node is the node preceding the tail node, unless the tail node points to the head node.

:::C
node_t* nextNode( node_t* n );

Returns the next node following the specified node, or 0, if n was the last node of the list.

:::C
node_t* prevNode( node_t* n );

Returns the previous node preceding the specified node, or 0, if p was the first node of the list.

:::C
node_t* remHead( list_t* l ); 

Obtains the first node of a list, removes it and returns it, unless the list was empty. Returns 0 in that case.

:::C
node_t* remTail( list_t* l ); 

Obtains the last node of a list, removes it and returns it, unless the list was empty. Returns 0 in that case.

---

Project Admins:

• Ekkehard Morgenstern