|
|
|
GSK Reference Manual | |
|---|---|---|---|---|
#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)
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
#define GSK_STACK_PUSH(stack, node) 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. |
#define GSK_STACK_POP(stack, rv_node) 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. |
#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. |
#define GSK_STACK_REVERSE(stack) 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. |
#define GSK_STACK_FOREACH(stack, iter_var, code) 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. |
#define GSK_STACK_SORT(stack, comparator) 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) |
#define GSK_STACK_GET_BOTTOM(stack, rv_node) 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. |
#define GSK_STACK_IS_EMPTY(stack) 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). |
#define GSK_QUEUE_ENQUEUE(queue, node) 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. |
#define GSK_QUEUE_DEQUEUE(queue, rv_node) 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. |
#define GSK_QUEUE_PREPEND(queue, node) 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. |
#define GSK_QUEUE_REVERSE(queue) 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. |
#define GSK_QUEUE_SORT(queue, comparator) 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 : |
#define GSK_QUEUE_IS_EMPTY(queue) 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). |
#define GSK_LIST_PREPEND(list, node) 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. |
#define GSK_LIST_APPEND(list, node) 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. |
#define GSK_LIST_REMOVE_FIRST(list) 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. |
#define GSK_LIST_REMOVE_LAST(list) 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. |
#define GSK_LIST_REMOVE(list, node) 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. |
#define GSK_LIST_INSERT_AFTER(list, at, node) 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. |
#define GSK_LIST_INSERT_BEFORE(list, at, node) 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. |
#define GSK_LIST_IS_EMPTY(list) 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). |
#define GSK_LIST_REVERSE(list) 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. |
#define GSK_LIST_SORT(list, comparator) 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) |