## gsklistmacros

gsklistmacros — macro-based list macros

## Synopsis

    #define             GSK_LOG2_MAX_LIST_SIZE
    #define             GSK_STACK_PUSH                      (stack, node)
    #define             GSK_STACK_POP                       (stack, rv_node)
    #define             GSK_STACK_INSERT_AFTER              (stack, above_node, new_node)
    #define             GSK_STACK_REVERSE                   (stack)
    #define             GSK_STACK_FOREACH                   (stack, iter_var, code)
    #define             GSK_STACK_SORT                      (stack, comparator)
    #define             GSK_STACK_GET_BOTTOM                (stack, rv_node)
    #define             GSK_STACK_IS_EMPTY                  (stack)
    #define             GSK_QUEUE_ENQUEUE                   (queue, node)
    #define             GSK_QUEUE_DEQUEUE                   (queue, rv_node)
    #define             GSK_QUEUE_PREPEND                   (queue, node)
    #define             GSK_QUEUE_REVERSE                   (queue)
    #define             GSK_QUEUE_SORT                      (queue, comparator)
    #define             GSK_QUEUE_IS_EMPTY                  (queue)
    #define             GSK_LIST_PREPEND                    (list, node)
    #define             GSK_LIST_APPEND                     (list, node)
    #define             GSK_LIST_REMOVE_FIRST               (list)
    #define             GSK_LIST_REMOVE_LAST                (list)
    #define             GSK_LIST_REMOVE                     (list, node)
    #define             GSK_LIST_INSERT_AFTER               (list, at, node)
    #define             GSK_LIST_INSERT_BEFORE              (list, at, node)
    #define             GSK_LIST_IS_EMPTY                   (list)
    #define             GSK_LIST_REVERSE                    (list)
    #define             GSK_LIST_SORT                       (list, comparator)

## Description

These macros define several kinds of "invasive" list structures. We call them invasive because their members must be placed in structures which you are in charge of allocating: for example, if you are using a doubly-linked list, you must place two link pointers in your structures.

Perhaps an example will help to illustrate:

    typedef struct _IntNode IntNode;
    struct _IntNode
    {
      int value;
      IntNode *prev, *next;
    };
    IntNode *first_int = NULL, *last_int = NULL;
    #define GET_INT_LIST() IntNode *, first_int, last_int, prev, next
      IntNode *add = g_new (IntNode, 1);
      add->a = 42;
      GSK_LIST_APPEND (GET_INT_LIST(), add);

In other words, your "list" is just the presence of the members "prev", "next", "first_int", "last_int" and the macro definition "`GET_INT_LIST()`".

You might see why this is useful immediately, but here's a few neat implications of a macro-based system:

- they are as fast as writing the list code yourself.

- they allow you to manage memory as you want.

- it is easy to have the nodes be members of several lists, or other invasive data structures

Here are the types of lists, along with some examples:

stack

A stack is a singly-linked list where we only keep track of one end.

To define a stack, you should make a macro defining the type of node, the end-pointer, and the member-name.

Here is a stack:

    typedef struct _StackNode StackNode;
    struct _StackNode
    {
      int value;
      StackNode *next;
    };
    StackNode *stack_top = NULL;
    #define GET_STACK()  StackNode *, stack_top, next

queue

A queue is a singly-linked list where we keep track of both ends.

To define a queue, you should make a macro defining the type of node, the first and last pointers, and the member-name.

Here is a queue:

    typedef struct _QueueNode QueueNode;
    struct _QueueNode
    {
      int value;
      QueueNode *next;
    };
    QueueNode *head = NULL, *tail = NULL;
    #define GET_QUEUE()  QueueNode *, head, tail, next

This defines a queue such that "prepending" to the queue means inserting an element at its "head" end. To put an element at the tail end, use "enqueue", and to remove from the head end, use "dequeue". It is not possible to remove from the tail end.

list

A list is a doubly-linked list where we keep track of both ends.

To define a list, you should make a macro defining the type of node, the first and last pointers, and the names of the members corresponding to the previous and next pointers.

Here is a list:

    typedef struct _ListNode ListNode;
    struct _ListNode
    {
      int value;
      ListNode *prev, *next;
    };
    ListNode *head = NULL, *tail = NULL;
    #define GET_LIST()  ListNode *, head, tail, prev, next

This defines a list such that "prepending" means inserting an element at its "head" end, and "appending" means inserting an element at its "tail" end. Similarly "remove_first" will remove the head element and "remove_last" will remove the tail element. And, since this is a doubly-linked list, you can also remove an arbitrary element.

The sorting routines all take "comparator macros". These take three arguments: two nodes and a variable which should be set to -1, 0, or +1 if the first node is less than, equal to, or greater than the second node.

For the list example, here's a comparator macro:

    #define COMPARATOR(a,b,rv) \

      rv = (a->value < b->value) ? -1 : (a->value > b->value) ? 1 : 0

## Details

### GSK_LOG2_MAX_LIST_SIZE

    #define             GSK_LOG2_MAX_LIST_SIZE

### GSK_STACK_PUSH()

    #define             GSK_STACK_PUSH(stack, node)

Push an entry onto the stack.

`stack` : | the stack (a list of three arguments provided by a macro) to affect.
`node` : | the node to add to the stack.

### GSK_STACK_POP()

    #define             GSK_STACK_POP(stack, rv_node)

Pop an entry off the stack. This will segfault if the stack is empty.

`stack` : | the stack (a list of three arguments provided by a macro) to affect.
`rv_node` : | this variable is set to the node that was removed from the stack.

### GSK_STACK_INSERT_AFTER()

    #define             GSK_STACK_INSERT_AFTER(stack, above_node, new_node)

Put an element onto the stack after another element. After doing this, `above_node`'s next pointer will be set to `new_node`.

`stack` : | the stack (a list of three arguments provided by a macro) to affect.
`above_node` : | a node in the stack whose next pointer will be set to `new_node`.
`new_node` : | the node to insert into the stack.

### GSK_STACK_REVERSE()

    #define             GSK_STACK_REVERSE(stack)

Reverse the order of a stack. The top of the stack will now point to the node that was the bottom.

`stack` : | the stack (a list of three arguments provided by a macro) to affect.

### GSK_STACK_FOREACH()

    #define             GSK_STACK_FOREACH(stack, iter_var, code)

Run code on each element of the list.

`stack` : | the stack (a list of three arguments provided by a macro).
`iter_var` : | variable to set to each element of the list in turn.
`code` : | code to invoke on each element of the list.

### GSK_STACK_SORT()

    #define             GSK_STACK_SORT(stack, comparator)

Sort a stack.

`stack` : | the stack (a list of three arguments provided by a macro).
`comparator` : | a macro that takes three arguments: two nodes, and an integer which should be assigned -1, 0, or 1 if the first node is lesser, equal to, or greater than the second node, respectively. (See example at top of this section)

### GSK_STACK_GET_BOTTOM()

    #define             GSK_STACK_GET_BOTTOM(stack, rv_node)

Find the bottom of the stack.

`stack` : | the stack (a list of three arguments provided by a macro).
`rv_node` : | This will assigned to the bottom of the stack, or NULL if the stack is empty.

### GSK_STACK_IS_EMPTY()

    #define             GSK_STACK_IS_EMPTY(stack)

Evaluates to TRUE iff the stack is empty.

`stack` : | the stack (a list of three arguments provided by a macro).

### GSK_QUEUE_ENQUEUE()

    #define             GSK_QUEUE_ENQUEUE(queue, node)

Append a node to the queue.

`queue` : | the queue (a list of four arguments provided by a macro) to affect.
`node` : | the node to append.

### GSK_QUEUE_DEQUEUE()

    #define             GSK_QUEUE_DEQUEUE(queue, rv_node)

Remove a node from the front of the queue.

`queue` : | the queue (a list of four arguments provided by a macro) to affect.
`rv_node` : | this pointer will be set to the node that was the front of the queue, or NULL if the queue was empty.

### GSK_QUEUE_PREPEND()

    #define             GSK_QUEUE_PREPEND(queue, node)

Prepend a node to the queue.

`queue` : | the queue (a list of four arguments provided by a macro) to affect.
`node` : | the node to prepend.

### GSK_QUEUE_REVERSE()

    #define             GSK_QUEUE_REVERSE(queue)

Reverse the order of a queue. The front of the queue will point to what used to be the back of the queue, and vice versa.

This operation runs in O(N) time.

`queue` : | the queue to reverse.

### GSK_QUEUE_SORT()

    #define             GSK_QUEUE_SORT(queue, comparator)

Sort the elements of the queue.

`queue` : | the queue (a list of four arguments provided by a macro) to affect.
`comparator` : | a macro that takes three arguments: two nodes, and an integer which should be assigned -1, 0, or 1 if the first node is lesser, equal to, or greater than the second node, respectively. (See example at top of this section)

### GSK_QUEUE_IS_EMPTY()

    #define             GSK_QUEUE_IS_EMPTY(queue)

Evaluates to TRUE iff the queue is empty.

`queue` : | the queue (a list of four arguments provided by a macro).

### GSK_LIST_PREPEND()

    #define             GSK_LIST_PREPEND(list, node)

Prepend a node to the list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`node` : | the node to prepend.

### GSK_LIST_APPEND()

    #define             GSK_LIST_APPEND(list, node)

Append a node to the list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`node` : | the node to append.

### GSK_LIST_REMOVE_FIRST()

    #define             GSK_LIST_REMOVE_FIRST(list)

Remove the first element from the list. The list must not be empty initially.

`list` : | the list (a list of five arguments provided by a macro) to affect.

### GSK_LIST_REMOVE_LAST()

    #define             GSK_LIST_REMOVE_LAST(list)

Remove the last element from the list. The list must not be empty initially.

`list` : | the list (a list of five arguments provided by a macro) to affect.

### GSK_LIST_REMOVE()

    #define             GSK_LIST_REMOVE(list, node)

Remove a node from a list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`node` : | the node to remove from the list.

### GSK_LIST_INSERT_AFTER()

    #define             GSK_LIST_INSERT_AFTER(list, at, node)

Insert the new node `node` after the node `at` in the list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`at` : | the node in the list telling where to insert `node`.
`node` : | the node to insert into the list.

### GSK_LIST_INSERT_BEFORE()

    #define             GSK_LIST_INSERT_BEFORE(list, at, node)

Insert the new node `node` before the node `at` in the list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`at` : | the node in the list telling where to insert `node`.
`node` : | the node to insert into the list.

### GSK_LIST_IS_EMPTY()

    #define             GSK_LIST_IS_EMPTY(list)

Evaluates to TRUE iff the list is empty.

`list` : | the list (a list of five arguments provided by a macro).

### GSK_LIST_REVERSE()

    #define             GSK_LIST_REVERSE(list)

Reverse the order of a list. The first and last pointers and next/prev pointers are switched.

`list` : | the list (a list of five arguments provided by a macro) to affect.

### GSK_LIST_SORT()

    #define             GSK_LIST_SORT(list, comparator)

Sort the elements of the list.

`list` : | the list (a list of five arguments provided by a macro) to affect.
`comparator` : | a macro that takes three arguments: two nodes, and an integer which should be assigned -1, 0, or 1 if the first node is lesser, equal to, or greater than the second node, respectively. (See example at top of this section)

## See Also

gskrbtreemacros, gskqsortmacro