SGLIB - Reference Manual


Content





About Sglib

SGLIB stands for Simple Generic Library and it consists of single header file written in C programming language. The header file sglib.h provides generic implementation of most common algorithms for arrays, lists, sorted lists and red-black trees. Implementation of double linked lists and hashed tables is envisaged. Also suggestions for new useful functionalities are welcomed. The library is generic and it does not define its own data structures. Rather it acts on existing user defined data structures via a generic interface. It also does not allocate or deallocate any memory and does not depend on any particular memory management. In case od several datatypes, sglib even does not impose its own data representation. For example, sglib list routines can be applied to any user defined structure containing a pointer to the same structure as its field.

All algorithms are implemented in form of macros parametrized by the type of data structure and comparator function (or comparator macro). Several further generic parameters such as the name of 'next' field for linked lists may be required for some algorithms and data structures.

Sglib offers access to algorithms in two level user interface. A level - 0 interface is simply a collection of useful macros. If you do not like large macros or you afraid introduction of symbol clashes after macro expansions you can use a level - 1 interface. This interface generates legal C functions for each particular type. Those functions can be called from the main program without worrying about unwanted effects due to macro expansions.

You can always use level - 0 interface. You can use level - 1 interface only if your base type is named by a single identifier, or if you have defined a typedef for it. It is a question of taste whether you decide to use one of two interfaces. It seems that you get the most advantages by using both interfaces in the same time. You can do this without worrying about implementation clashes, the level - 1 inplementation are just wrappers to level - 0 interface. However, few functions using recursion (red-black trees for example) are implemented exclusively in level - 1 interface.

During the design and implementation of sglib we have followed following rules:



Sglib - Concepts

Comparator

A comparator is a function (or macro) taking two elements and returning an integer value, the value is respectively a negative number, zero or a positive number for cases when the first parameter is less than, equal, or greater than the second. For example the standard C function strcmp is a string comparator which can be directly used in sglib. Also a macro
#define SGLIB_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y)))
is a comparator for integers numbers. By the way, the macro SGLIB_NUMERIC_COMPARATOR with this definition is predefined in sglib and you can use it withount need of your own redefinitions.

Subcomparator

A comparator which is induced from another comparator in a way that it makes several elements equal while otherwise preserving the original ordering is called a subcomparator. More formally, if cmp is a comparator and subcmp is its subcomparator, then:

  cmp(x,y) < 0 implies subcmp(x,y) <= 0
and
  cmp(x,y) > 0 implies subcmp(x,y) >= 0

Subcomparators are used in iterators to iterate over such part of a container which is equal to a given element. For example, let's take that we have a red black tree of strings ordered lexicographically. We can define a subcomparator comparing only the first letter of strings:
#define strsubcmp(x, y) (x[0] - y[0])
Using this subcomparator we can iterate over all strings starting with the same letter.

Array elem_exchanger and simultaneous sorting of multiple arrays

An elem_exchanger is a function (or macro) performing exchange of two elements in an array. It takes following four parameters: the type of array elements, the array on which it operates, and two indexes of elements to exchange. For example the following macro:
#define SGLIB_ARRAY_ELEMENTS_EXCHANGER(type, a, i, j) {type tmp;tmp=a[i];a[i]=a[j];a[j]=tmp;}
is an elem_exchanger usable by sglib. By the way, the macro SGLIB_ARRAY_ELEMENTS_EXCHANGER with this definition is predefined in the sglib and you can use in implementations of your own elem_exchangers. An elem_exchanger can be used to parametrize sorting algorithms. The motivation is that in many projects, several arrays keep related informations. Elemens of different arrays having the same index are related to each other and they form a single record. For example, one can represent a phone annuary by keeping person names in one array (say name) and corresponding phone numbers in another array (say phoneNumbers). In this representation the person name[i] has the phone number phoneNumber[i]. If you decide to sort your annuary alphabetically by names, you have to make corresponding reordering also on numbers.

Sglib modifies arrays exclusively by using an elem_exchanger. You can use your own elem_exchanger as parameter for sorting algorithms. Your implementation can simultaneously exchange elements in several arrays, and hence make sorting to act on multiple related arrays. For example, continuing the annuary example, we can define the following elem_exchanger:

#define ANNUARY_EXCHANGER(type, a, i, j) {  SGLIB_ARRAY_ELEMENTS_EXCHANGER(char *, name, i, j);  SGLIB_ARRAY_ELEMENTS_EXCHANGER(int, phoneNumber, i, j);}
and use it as parameter of a sorting macro. For example we can sort the first 1000 elements of the annuary by the following command:
SGLIB_ARRAY_QUICK_SORT(char*, name, 1000, strcmp, ANNUARY_EXCHANGER);


Container

A container data structure is any data structure containing elements. This is for example an array, list, sorted list, red-black tree, etc.

Linked lists

A linked list is any C structure containing a pointer to the next element. The structure is entirely defined by the user, sglib does not provide any default implementation. Following code defines several lists on which sglib can operate:

struct myintlist {
     int value;
     struct myintlist *next;
};

struct history {
     int order;
     struct historyelem *h;
     // ... any other records
     struct history *previous;
};

// you can even consider special trees as linked lists
struct mytreenode {
     int nodetype;
     union nodeinformations node;
     struct mytrenode **subtrees;
};

Sglib does not contain any allocation or freeing of memory, so your program is responsible for allocating/freeing of each element of the list. Sglib provides macros for ordering and maintaining such lists. Macros, such as insert and delete only affect the next field of elements, so that the element is correctly inserted/deleted into/from the list.

Linked list next element parameter

The next parameter of sglib macros is the name of the field pointing to the next element of the list. For example for structures defined in the previous section this parameter will be respectively words: next, previous and subtrees[1].

Pointer equality versus comparator equality

Sglib distinguishes two notions of equality. Two elements are said pointer equal if they are the same object in the memory and hence they are referenced by the same pointer. Two elements are said comparator equal if the comparator applied on those elements returns zero. In other words, the comparator equality tests the equality of keys. You can have several elements with the same key (hence comparator equal) in a data structure such as list, but only one occurence of each element with the same pointer (otherwise a cyclic data structure occurs).

The difference between pointer and comparator equality remains the difference between == and equals operators in Java language (with the difference that in sglib user has to implement its own comparator).

Pointer and comparator equal membership

Distinction between pointer and comparator equality generates two notions of membership in a container data structure. We say that an element E is a pointer equal member of a container if it is physically part of the data structure, i.e. if the container contains the pointer to E. We say that an element E is a comparator equal member, if the container contains an element which is comparator equal to E. In other words, an element is a comparator equal member of a container if the container contains an element with the same key. Note that if an element is a pointer equal member then it is also a comparator equal member.

Double Linked lists

A double linked list is any C structure containing two pointers interpreted respectively as the previous and the next elements of the list. The structure is entirely defined by the user, sglib does not provide any default implementation. Following code defines several double linked lists on which sglib can operate:

struct mydoublelinkedlist {
     int value;
     struct mydoublelinkedlist *previous, *next;
};

struct history {
     int order;
     struct historyelem *h;
     // ... any other records
     struct history *up, *down;
};

Sglib provides macros for ordering and maintaining such lists. The list is passed to sglib using a pointer to any of its member. Sglib than operates on the whole list accessible via previous and next fields. Macros, such as insert and delete only affect the previous and next fields of elements, the rest of the structure is kept intact.

Previous and next parameters of macros for double linked lists

The previous and next parameters of sglib macros are names of fields pointing respectively to the previous and to the next elements of a double linked list. For example, in the case of the first structure defined in the previous section those parameters will be previous and next. For the second structure those parameters will be up and down.

Binary trees

A binary tree is any structure type containing two pointers to subtrees. The structure is entirely defined by the user, sglib does not provide any default implementation. Following code defines several implementations of binary trees on which sglib can operate:

struct myTreeNode {
     int key;
     struct myTreeNode *left;
     struct myTreeNode *right;
};

struct generalTree {
     struct nodeInfo onfo;
     struct generalTree **subtrees;
};

// you can have a structure which is a tree and a list at the same time
struct listAndTree {
     int key;
     struct listAndTree *left_ptr;
     struct listAndTree *right_ptr;
     struct listAndTree *next_ptr;
};

Left and right parameters of tree macros

The left and right parameters of sglib macros are the names of fields pointing respectively to the left and right subtrees of the given tree node. For example for structures defined in the previous section those parameter will be respectively pairs of words: left, right then subtrees[0], subtrees[1] and finally left_ptr, right_ptr.

Red-Black Trees

A red-black tree is a balanced binary tree with (at least) one bit of additional information storing the color of each node. Nodes in red-black trees can be colored either red or black. Usualy those two colors are represented by 0 and 1 respectively. The structure defining a node in red-black tree is entirely defined by the user, sglib does not provide any default implementation. Our implementation of red-black trees uses recursion, this is why red-black trees are available only in level-1 interface. Following code defines several examples of structures which can be organized as red-black trees:

struct myTreeNode {
     int key;
     char color;
     struct myTreeNode *left;
     struct myTreeNode *right;
};

struct TreeWithOneColorBit {
     struct {
       unsigned key:31;
       unsigned blackLabel:1;
     } bits;
     struct TreeWithOneColorBit *left;
     struct TreeWithOneColorBit *right;
};

Color parameter for red-black tree macros

The color parameter of macros operating on red-black trees is the name of the field containing information about the color of the node. For example for structures defined in the previous section this parameter will be color and bits.blackLabel.



API: level 0

The level 0 application interface is simply a collection of useful generic macros. Those macros are in general parametrized by some kind of C type (probably a C structure) and this is why they can not be implemented by C functions.

By convention, names of all macros start by SGLIB_ prefix. Then goes the identification of the data structure on which the macro operates and finaly the action performed by the macro.

In the design of macros we tried to make macros as generic as possible. This sometimes leads to parameters which may seems useless. However, because macro expansion is done in compile time and the number of macro parameters does not affect the efficiency of the code, we thing that additional parameters do not matter.



Array sorting API: level 0

SGLIB_ARRAY_SINGLE_QUICK_SORT macro SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator)

sort a single array using quicksort.
Parameters:
type - the type of array elements.
a - the array to sort.
max - the number of elements in the array.
comparator - a comparator used to compare elements.
SGLIB_ARRAY_SINGLE_HEAP_SORT macro SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator)

sort a single array using heapsort.
Parameters:
type - the type of array elements.
a - the array to sort.
max - the number of elements in the array.
comparator - a comparator used to compare elements.
SGLIB_ARRAY_QUICK_SORT macro SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, elem_exchanger)

sort possibly multiple arrays using quicksort.
Parameters:
type - the type of array elements.
a - the array to sort.
max - the number of elements in the array.
comparator - a comparator used to compare elements.
elem_exchanger - an elem_exchanger used to exchange two elements in the array.
SGLIB_ARRAY_HEAP_SORT macro SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, elem_exchanger)

sort possibly multiple arrays using heapsort.
Parameters:
type - the type of array elements.
a - the array to sort.
max - the number of elements in the array.
comparator - a comparator used to compare elements.
elem_exchanger - an elem_exchanger used to exchange two elements in the array.
SGLIB_ARRAY_BINARY_SEARCH macro SGLIB_ARRAY_BINARY_SEARCH(type, a, start_index, end_index, key, comparator, found, result_index)

find the key in a sorted array using binary search.
Parameters:
type - the type of array elements.
a - the array.
start_index - the starting index, it is the smallest index possibly containing the key.
end_index - the ending index, it is the largest index possibly containing the key increased by one.
key - the element to search.
comparator - a comparator used to compare elements.
found - (output) is set to non-zero if the key was found, to zero otherwise.
result_index - (output) is set to the index of the element equal to the key. If there is no such element, than result_index is set to the index where the key can be inserted while preserving the array ordering.


Lists API: level 0

SGLIB_LIST_ADD macro SGLIB_LIST_ADD(type, list, elem, next)

add an element to a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to add.
next - the name of the field pointing to the next element of the list.
SGLIB_LIST_ADD_IF_NOT_MEMBER macro SGLIB_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member)

add an element to a list if there is no comparator equal element inside.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to add.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem has been added to the list, otherwise this variable is set to the member of the list which is equal to elem.
SGLIB_LIST_CONCAT macro SGLIB_LIST_CONCAT(type, first, second, next)

concatenate two lists by appending the second at the end of the first.
Parameters:
type - the type of list elements.
first - the first list.
second - the second list.
next - the name of the field pointing to the next element of the list.
SGLIB_LIST_DELETE macro SGLIB_LIST_DELETE(type, list, elem, next)

delete an element from a list. The element must be a pointer equal member of the list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to delete.
next - the name of the field pointing to the next element of the list.
SGLIB_LIST_DELETE_IF_MEMBER macro SGLIB_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member)

remove a comparator equal element from a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to delete.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem was not inside the list, otherwise this variable is set to the deleted element.
SGLIB_LIST_IS_MEMBER macro SGLIB_LIST_IS_MEMBER(type, list, elem, next, result)

determine whether an element is a pointer member of a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to search.
next - the name of the field pointing to the next element of the list.
result - (output) set to zero, if elem is not memebr of the list, non-zero otherwise.
SGLIB_LIST_FIND_MEMBER macro SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, result)

determine whether there is a comparator equal element in a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to search.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
result - (output) set to the resulting member. This variable is NULL if the elem has not been found in the list.
SGLIB_LIST_LEN macro SGLIB_LIST_LEN(type, list, next, result)

compute the length of a list.
Parameters:
type - the type of list elements.
list - the list.
next - the name of the field pointing to the next element of the list.
result - (output) the length of the list.
SGLIB_LIST_MAP_ON_ELEMENTS macro SGLIB_LIST_MAP_ON_ELEMENTS(type, list, var, next, command)

apply a command on all elements of a list.
Parameters:
type - the type of list elements.
list - the list.
var - the variable which will run through each element of the list.
next - the name of the field pointing to the next element of the list.
command - any (possibly composed) statement of the C language. In the statement you can use the variable var (third parameter of the macro) going through all elements of the list.
SGLIB_LIST_REVERSE macro SGLIB_LIST_REVERSE(type, list, next)

reverse a list.
Parameters:
type - the type of list elements.
list - the list to reverse.
next - the name of the field pointing to the next element of the list.
SGLIB_LIST_SORT macro SGLIB_LIST_SORT(type, list, comparator, next)

sort a list using mergesort.
Parameters:
type - the type of list elements.
list - the list to sort
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.


Sorted Lists API: level 0

SGLIB_SORTED_LIST_ADD macro SGLIB_SORTED_LIST_ADD(type, list, elem, comparator, next)

insert an element into a sorted list.
Parameters:
type - the type of list elements.
list - the list where to insert the new element.
elem - the element to insert.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER macro SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member)

insert an element into a sorted list if there is no comparator equal element inside.
Parameters:
type - the type of list elements.
list - the list where to add the element.
elem - the element to add.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem has been added to the list, otherwise this variable is set to the member of the list which is equal to elem.
SGLIB_SORTED_LIST_DELETE macro SGLIB_SORTED_LIST_DELETE(type, list, elem, next)

delete an element from a sorted list. The element must be a pointer equal member of the list.
Parameters:
type - the type of list elements.
list - the list where to delete the element.
elem - the element to delete. It must be a pointer equal member of the list.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
SGLIB_SORTED_LIST_DELETE_IF_MEMBER macro SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member)

remove a comparator equal element from a sorted list.
Parameters:
type - the type of list elements.
list - the list where to delete the element.
elem - the element to delete.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem was not inside the list, otherwise this variable is set to the deleted element.
SGLIB_SORTED_LIST_IS_MEMBER macro SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result)

determine whether an element is a pointer member of a sorted list.
Parameters:
type - the type of list elements.
list - the list to search.
elem - the element to search.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
result - (output) set to zero, if the elem is not member of the list. Non-zero otherwise.
SGLIB_SORTED_LIST_FIND_MEMBER macro SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, result)

determine whether an element is a comparator member of a sorted list.
Parameters:
type - the type of list elements.
list - the list to search.
elem - the element to search.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
result - (output) set to the resulting member. This variable is NULL if the elem has not been found in the list.
SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE macro SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, comparator_result, member_ptr)

determine whether an element is a comparator member of a sorted list, if not, find the place where to insert it.
Parameters:
type - the type of list elements.
list - the list where to search the element.
elem - the element to search.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
comparator_result - (output) the last comparator result. This is zero if the element was present in the list, non-zero otherwise.
member_ptr - (output) the place where to insert elem. It is the pointer to the pointer which will be set to elem by insertion. If comparator_result is zero, then this is the pointer to the pointer to the element equal to elem.
SGLIB_SORTED_LIST_LEN macro SGLIB_SORTED_LIST_LEN(type, list, next, result)

compute the length of a list.
Parameters:
type - the type of list elements.
list - the list.
next - the name of the field pointing to the next element of the list.
result - (output) variable set to the length of the list.
SGLIB_SORTED_LIST_MAP_ON_ELEMENTS macro SGLIB_SORTED_LIST_MAP_ON_ELEMENTS(type, list, var, next, command)

apply a command on all elements of a list.
Parameters:
type - the type of list elements.
list - the list.
var - the variable which will run through each element of the list.
next - the name of the field pointing to the next element of the list.
command - any (possibly composed) statement of the C language. In the statement you can use the variable var (third parameter of the macro) going through all elements of the list.


Double Linked Lists API: level 0

SGLIB_DL_LIST_ADD macro SGLIB_DL_LIST_ADD(type, list, elem, previous, next)

add an element to a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to add.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_ADD_BEFORE macro SGLIB_DL_LIST_ADD_BEFORE(type, list, elem, previous, next)

add an element to a list. Elem will be inserted before the element pointed by list.
Parameters:
type - the type of list elements.
list - the list (also specifying the place where to insert the new element).
elem - the element to add.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_ADD_AFTER macro SGLIB_DL_LIST_ADD_AFTER(type, list, elem, previous, next)

add an element to a list. Elem will be inserted after the element pointed by list.
Parameters:
type - the type of list elements.
list - the list (also specifying the place where to insert the new element).
elem - the element to add.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_ADD_IF_NOT_MEMBER macro SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member)

add an element to a list if there is no comparator equal element inside.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to add.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem has been added to the list, otherwise this variable is set to the member of the list which is equal to elem.
SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER macro SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member)

add an element to a list if there is no comparator equal element inside. Elem will be inserted before the element pointed by list.
Parameters:
type - the type of list elements.
list - the list (also specifying the place where to insert the new element).
elem - the element to add.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem has been added to the list, otherwise this variable is set to the member of the list which is equal to elem.
SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER macro SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member)

add an element to a list if there is no comparator equal element inside. Elem will be inserted after the element pointed by list.
Parameters:
type - the type of list elements.
list - the list (also specifying the place where to insert the new element).
elem - the element to add.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem has been added to the list, otherwise this variable is set to the member of the list which is equal to elem.
SGLIB_DL_LIST_CONCAT macro SGLIB_DL_LIST_CONCAT(type, first, second, previous, next)

concatenate two lists by appending the second at the end of the first.
Parameters:
type - the type of list elements.
first - the first list.
second - the second list.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_DELETE macro SGLIB_DL_LIST_DELETE(type, list, elem, previous, next)

delete an element from a list. The element must be a pointer equal member of the list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to delete.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_DELETE_IF_MEMBER macro SGLIB_DL_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, previous, next, member)

remove a comparator equal element from a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to delete.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
member - (output) NULL, if the elem was not inside the list, otherwise this variable is set to the deleted element.
SGLIB_DL_LIST_IS_MEMBER macro SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result)

determine whether an element is a pointer member of a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to search.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
result - (output) set to zero, if elem is not memebr of the list, non-zero otherwise.
SGLIB_DL_LIST_FIND_MEMBER macro SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, result)

determine whether there is a comparator equal element in a list.
Parameters:
type - the type of list elements.
list - the list.
elem - the element to search.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
result - (output) set to the resulting member. This variable is NULL if the elem has not been found in the list.
SGLIB_DL_LIST_GET_FIRST macro SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result)

get the first element of a list.
Parameters:
type - the type of list elements.
list - the list.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
result - (output) the first element of the list.
SGLIB_DL_LIST_GET_LAST macro SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result)

get the last element of a list.
Parameters:
type - the type of list elements.
list - the list.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
result - (output) the last element of the list.
SGLIB_DL_LIST_LEN macro SGLIB_DL_LIST_LEN(type, list, previous, next, result)

compute the length of a list.
Parameters:
type - the type of list elements.
list - the list.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
result - (output) the length of the list.
SGLIB_DL_LIST_MAP_ON_ELEMENTS macro SGLIB_DL_LIST_MAP_ON_ELEMENTS(type, list, var, previous, next, command)

apply a command on all elements of a list. Command will be repeatedly executed for each element of the list accessible via the previous field and then via the next field. The current element of the list is stored in the variable var.
Parameters:
type - the type of list elements.
list - the list.
var - the variable which will run through each element of the list.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
command - any (possibly composed) statement of the C language. In the statement you can use the variable var (third parameter of the macro) going through all elements of the list.
SGLIB_DL_LIST_REVERSE macro SGLIB_DL_LIST_REVERSE(type, list, previous, next)

reverse a list.
Parameters:
type - the type of list elements.
list - the list to reverse.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DL_LIST_SORT macro SGLIB_DL_LIST_SORT(type, list, comparator, previous, next)

sort a list using mergesort. As a side effect the list is set to the first element of the list.
Parameters:
type - the type of list elements.
list - the list to sort
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.


Binary Trees API: level 0

SGLIB_BIN_TREE_MAP_ON_ELEMENTS macro SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, var, left, right, command)

traverse a binary tree and apply command on each element. This is non-recursive implementation of tree traversal. It maintains the path to the current node in the array _path_, the _path_[0] contains the root of the tree. The _path_[_pathi_-1] contains the parent of the var. The maximal deep of the tree is limited by SGLIB_MAX_TREE_DEEP macro.
Parameters:
type - the type of the tree data structure.
tree - the tree.
var - the variable which will run through each element of the tree.
left - the name of the field pointing to the left subtree of the tree.
right - the name of the field pointing to the right subtree of the tree.
command - any (possibly composed) statement of the C language. In the statement you can use the variable var (third parameter of the macro) going through all elements of the tree.






API: level 1

The level - 1 application interface consists of two stages. First you need to invoke a generic macro for given data type and then you can use a collection of functions generated by the macro (see also our samples for the difference between the two interfaces). Function names are composed from the name of the base type given by the user.











Arrays API: level 1

SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES macro SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES(type, comparator)

define headers of array sorting functions. Declared functions are:
sglib_type_array_quick_sort
sglib_type_array_heap_sort
Parameters:
type - the type of array elements. It must be a single identifier.
comparator - a comparator used to compare elements.
SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS macro SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(type, comparator)

define the array sorting functions. Defined functions are:
sglib_type_array_quick_sort
sglib_type_array_heap_sort
Parameters:
type - the type of array elements. It must be a single identifier.
comparator - a comparator used to compare elements.

Functions generated by above macros:

sglib_type_array_quick_sort function sglib_type_array_quick_sort(type *a, int max)

sort an array using quicksort.
Parameters:
a - the array to sort.
max - the number of elements in the array.
Generated by SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS
Parameters:
type - the type of array elements. It must be a single identifier.
comparator - a comparator used to compare elements.
sglib_type_array_heap_sort function sglib_type_array_heap_sort(type *a, int max)

sort an array using heapsort.
Parameters:
a - the array to sort.
max - the number of elements in the array.
Generated by SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS
Parameters:
type - the type of array elements. It must be a single identifier.
comparator - a comparator used to compare elements.













Hashed Containers API: level 1

Usually, in libraries similar to sglib, a hashed container is an array where each cell contains a (possibly empty) list of elements. In sglib we use a more abstract notion of hashed container. A hashed container is a table of fixed size containing another (we say base) container in each cell. Once an object is going to be inserted into the hashed container, the hash function is used to determine the cell where it belongs and then the object is inserted into the base container stored in this cell. The base container is usualy a list, however it can be a sorted list, double linked list or a red-black tree as well. Sglib's hashed container is parametrized by the name of the base container.

Hashed containers are provided only in level-1 interface because they require a uniform interface for operations applied on the base container.


SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES macro SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(type, dim, hash_function)

define headers of hashed container functions and iterator. It defines structure sglib_hashed_type_iterator and declares functions:
sglib_hashed_type_init
sglib_hashed_type_add
sglib_hashed_type_add_if_not_member
sglib_hashed_type_delete
sglib_hashed_type_delete_if_member
sglib_hashed_type_is_member
sglib_hashed_type_find_member
sglib_hashed_type_it_init
sglib_hashed_type_it_init_on_equal
sglib_hashed_type_it_next
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS macro SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(type, dim, hash_function)

define the hashed container functions. Defined functions are:
sglib_hashed_type_init
sglib_hashed_type_add
sglib_hashed_type_add_if_not_member
sglib_hashed_type_delete
sglib_hashed_type_delete_if_member
sglib_hashed_type_is_member
sglib_hashed_type_find_member
sglib_hashed_type_it_init
sglib_hashed_type_it_init_on_equal
sglib_hashed_type_it_next
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.

Functions generated by above macros:

sglib_hashed_type_init function void sglib_hashed_type_init(type *table[dim])

set each cell in the table to NULL.
Parameters:
table - the hashed container.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_add function void sglib_hashed_type_add(type *table[dim], type *elem)

Add an element into the hashed container.
Parameters:
table - the hashed container.
elem - the element to be added.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_add_if_not_member function int sglib_hashed_type_add_if_not_member(type *table[dim], type *elem, type **member)

Add an element into the hashed container if there is no comparator equal element inside.
Parameters:
table - the hashed container.
elem - the element to be added.
member - in case if the element is a member of the container, set *member to it.
Returns:
Non-zero if the element was inserted to the container. Zero otherwise.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_delete function void sglib_hashed_type_delete(type *table[dim], type *elem)

delete an element from a hashed container. The element must be a pointer equal member of the hashed container.
Parameters:
table - the hashed container.
elem - the element to be removed.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_delete_if_member function int sglib_hashed_type_delete_if_member(type *table[dim], type *elem, type **member)

find a comparator equal element in the hashed container and remove it.
Parameters:
table - the hashed container.
elem - the element to be removed.
member - in case if the element is a member of the list, set *member to the removed element.
Returns:
Non-zero if the element was removed from the container. Zero otherwise.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_is_member function int sglib_hashed_type_is_member(type *table[dim], type *elem)

determine whether an element is inside a hashed container. The element is searched using pointer equality.
Parameters:
table - the hashed container.
elem - the element to be searched.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_find_member function type *sglib_hashed_type_find_member(type *table[dim], type *elem)

find an element in the hashed container. The element is searched using comparator equality.
Parameters:
table - the hashed container.
elem - the element to be searched.
Returns:
The member of the container comparator equal to elem.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_it_init function type *sglib_hashed_type_it_init(struct sglib_type_iterator *it, type *table[dim])

initialize an iterator it to run over elements of table.
Parameters:
it - the iterator.
table - the hashed container.
Returns:
The first iterated element or NULL if there is no element.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_it_init_on_equal function type *sglib_hashed_type_it_init_on_equal(struct sglib_type_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto)

initialize an iterator it to run over those elements of table which are equal to equalto. The equality is considered with respect to the subcomparator which must be a subcomparator of the base container comparator.
Parameters:
it - the iterator.
table - the hashed container.
subcomparator - the comparator used to find equal elements.
equalto - the element used as filter.
Returns:
The first iterated element or NULL if there is no element equal to equalto.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.
sglib_hashed_type_it_next function type *sglib_hashed_type_it_next(struct sglib_type_iterator *it)

get the next element from the iterator it.
Parameters:
it - the iterator.
Returns:
The next iterated element or NULL if there is no next element.
Generated by SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS
Parameters:
type - the type of the base container. It must be a single identifier.
dim - the size of the array.
hash_function - the hashing function mapping elements into unsigned integers.













Linked lists API: level 1

SGLIB_DEFINE_LIST_PROTOTYPES macro SGLIB_DEFINE_LIST_PROTOTYPES(type, comparator, next)

define headers for linked list functions. Declared functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_concat
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_sort
sglib_type_reverse
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
SGLIB_DEFINE_LIST_FUNCTIONS macro SGLIB_DEFINE_LIST_FUNCTIONS(type, comparator, next)

define functions for manipulating linked lists. Defined functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_concat
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_sort
sglib_type_reverse
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.

Functions generated by above macros:

sglib_type_add function void sglib_type_add(type **list, type *elem)

insert an element into a list.
Parameters:
list - the list.
elem - the element to insert.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_add_if_not_member function int sglib_type_add_if_not_member(type **list, type *elem, type **member)

insert an element if there is no comparator equal element in the list.
Parameters:
list - the list.
elem - the element to insert.
member - in case if the element is a member of the list, set *member to it.
Returns:
Non-zero if the element was inserted to the list. Zero otherwise.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_concat function void sglib_type_concat(type **first, type *second)

concatenate two lists by appending second at the end of the first.
Parameters:
first - the first list, it will contain the result of the concatenation.
second - the second list.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_delete function void sglib_type_delete(type **list, type *elem)

delete an element. The element must be a member of the list, it is looked using the pointer equality, not equality generated by comparator.
Parameters:
list - the list.
elem - the element to delete.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_delete_if_member function int sglib_type_delete_if_member(type **list, type *elem, type **result)

find a comparator equal element in the list and remove it.
Parameters:
list - the list.
elem - the element to search.
result - an output variable pointer. The variable will be set to the element removed from the list.
Returns:
Non-zero if the element was removed from the list. Zero otherwise.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_is_member function int sglib_type_is_member(type *list, type *elem)

determine whether an element is inside a list. The element is searched using pointer equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
Non-zero if the element is in the list. Zero otherwise.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_find_member function type *sglib_type_find_member(type **list, type *elem)

find an element in the list. The element is searched using comparator equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
The member of the list comparator equal to elem.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_len function int sglib_type_len(type *list)

compute the length of a list.
Parameters:
list - the list.
Returns:
The lenght of the list.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_sort function void sglib_type_sort(type **list)

sort the list according to comparator.
Parameters:
list - the list.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_reverse function void sglib_type_reverse(type **list)

reverse the list.
Parameters:
list - the list.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init function type *sglib_type_it_init(struct sglib_type_iterator *it, type *list)

initialize an iterator it to run over elements of list.
Parameters:
it - the iterator.
list - the list.
Returns:
The first iterated element or NULL if there is no element.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init_on_equal function type *sglib_type_it_init_on_equal(struct sglib_type_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto)

initialize an iterator it to run over those elements of list which are equal to equalto. The equality is considered with respect to the subcomparator which must be a subcomparator of the comparator.
Parameters:
it - the iterator.
list - the list.
subcomparator - the comparator used to find equal elements.
equalto - the element used as filter.
Returns:
The first iterated element or NULL if there is no element equal to equalto.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_next function type *sglib_type_it_next(struct sglib_type_iterator *it)

get the next element from the iterator it.
Parameters:
it - the iterator.
Returns:
The next iterated element or NULL if there is no next element.
Generated by SGLIB_DEFINE_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.





Sorted Linked lists API: level 1

SGLIB_DEFINE_SORTED_LIST_PROTOTYPES macro SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(type, comparator, next)

define headers for sorted linked list functions. Declared functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_sort
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
SGLIB_DEFINE_SORTED_LIST_FUNCTIONS macro SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(type, comparator, next)

define functions for manipulating sorted linked lists. Defined functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_sort
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.

Functions generated by above macros:

sglib_type_add function void sglib_type_add(type **list, type *elem)

insert an element into a list.
Parameters:
list - the list.
elem - the element to insert.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_add_if_not_member function int sglib_type_add_if_not_member(type **list, type *elem, type **member)

insert an element if there is no comparator equal element in the list.
Parameters:
list - the list.
elem - the element to insert.
member - in case if the element is a member of the list, set *member to it.
Returns:
Non-zero if the element was inserted to the list. Zero otherwise.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_delete function void sglib_type_delete(type **list, type *elem)

delete an element. The element must be a member of the list, it is looked using the pointer equality, not equality generated by comparator.
Parameters:
list - the list.
elem - the element to delete.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_delete_if_member function int sglib_type_delete_if_member(type **list, type *elem, type **result)

find a comparator equal element in the list and remove it.
Parameters:
list - the list.
elem - the element to search.
result - an output variable pointer. The variable will be set to the element removed from the list.
Returns:
Non-zero if the element was removed from the list. Zero otherwise.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_is_member function int sglib_type_is_member(type *list, type *elem)

determine whether an element is inside a list. The element is searched using pointer equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
Non-zero if the element is in the list. Zero otherwise.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_find_member function type *sglib_type_find_member(type **list, type *elem)

find an element in the list. The element is searched using comparator equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
The member of the list comparator equal to elem.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_len function int sglib_type_len(type *list)

compute the length of a list.
Parameters:
list - the list.
Returns:
The lenght of the list.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_sort function void sglib_type_sort(type **list)

sort the list according to comparator. This function does not logically belong to this datatype as it is supposed that lists are kept sorted. However, it can be used to initial sorting, when the list was created by other than sglib functions.
Parameters:
list - the list.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init function type *sglib_type_it_init(struct sglib_type_iterator *it, type *list)

initialize an iterator it to run over elements of list.
Parameters:
it - the iterator.
list - the list.
Returns:
The first iterated element or NULL if there is no element.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init_on_equal function type *sglib_type_it_init_on_equal(struct sglib_type_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto)

initialize an iterator it to run over those elements of list which are equal to equalto. The equality is considered with respect to the subcomparator which must be a subcomparator of the comparator.
Parameters:
it - the iterator.
list - the list.
subcomparator - the comparator used to find equal elements.
equalto - the element used as filter.
Returns:
The first iterated element or NULL if there is no element equal to equalto.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.
sglib_type_it_next function type *sglib_type_it_next(struct sglib_type_iterator *it)

get the next element from the iterator it.
Parameters:
it - the iterator.
Returns:
The next iterated element or NULL if there is no next element.
Generated by SGLIB_DEFINE_SORTED_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
next - the name of the field pointing to the next element of the list.





Double linked lists API: level 1

SGLIB_DEFINE_DL_LIST_PROTOTYPES macro SGLIB_DEFINE_DL_LIST_PROTOTYPES(type, comparator, previous, next)

define headers for double linked list functions. Declared functions are:
sglib_type_add
sglib_type_add_before
sglib_type_add_after
sglib_type_add_if_not_member
sglib_type_add_before_if_not_member
sglib_type_add_after_if_not_member
sglib_type_concat
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_get_first
sglib_type_get_last
sglib_type_len
sglib_type_sort
sglib_type_reverse
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
SGLIB_DEFINE_DL_LIST_FUNCTIONS macro SGLIB_DEFINE_DL_LIST_FUNCTIONS(type, comparator, previous, next)

define functions for manipulating linked lists. Defined functions are:
sglib_type_add
sglib_type_add_before
sglib_type_add_after
sglib_type_add_if_not_member
sglib_type_add_before_if_not_member
sglib_type_add_after_if_not_member
sglib_type_concat
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_get_first
sglib_type_get_last
sglib_type_len
sglib_type_sort
sglib_type_reverse
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.

Functions generated by above macros:

sglib_type_add function void sglib_type_add(type **list, type *elem)

insert an element into a list.
Parameters:
list - the list.
elem - the element to insert.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_add_before function void sglib_type_add_before(type **list, type *elem)

insert an element into a list. Elem will be inserted before the element pointed by *list.
Parameters:
list - the list (also the place where to insert the new element).
elem - the element to insert.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_add_after function void sglib_type_add_after(type **list, type *elem)

insert an element into a list. Elem will be inserted after the element pointed by *list.
Parameters:
list - the list (also the place where to insert the new element).
elem - the element to insert.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_add_if_not_member function int sglib_type_add_if_not_member(type **list, type *elem, type **member)

insert an element if there is no comparator equal element in the list.
Parameters:
list - the list.
elem - the element to insert.
member - in case if the element is a member of the list, set *member to it.
Returns:
Non-zero if the element was inserted to the list. Zero otherwise.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_add_before_if_not_member function int sglib_type_add_before_if_not_member(type **list, type *elem)

insert an element if there is no comparator equal element in the list. Elem will be inserted before the element pointed by *list.
Parameters:
list - the list (also the place where to insert the new element).
elem - the element to insert.
Returns:
Non-zero if the element was inserted to the list. Zero otherwise.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_add_after_if_not_member function int sglib_type_add_after_if_not_member(type **list, type *elem)

insert an element if there is no comparator equal element in the list. Elem will be inserted before the element pointed by *list.
Parameters:
list - the list (also the place where to insert the new element).
elem - the element to insert.
Returns:
Non-zero if the element was inserted to the list. Zero otherwise.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_concat function void sglib_type_concat(type **first, type *second)

concatenate two lists by appending second at the end of the first.
Parameters:
first - the first list, it will contain the result of the concatenation.
second - the second list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_delete function void sglib_type_delete(type **list, type *elem)

delete an element. The element must be a pointer equal member of the list.
Parameters:
list - the list.
elem - the element to delete.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_delete_if_member function int sglib_type_delete_if_member(type **list, type *elem, type **result)

find a comparator equal element in the list and remove it.
Parameters:
list - the list.
elem - the element to search.
result - an output variable pointer. The variable will be set to the element removed from the list.
Returns:
Non-zero if the element was removed from the list. Zero otherwise.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_is_member function int sglib_type_is_member(type *list, type *elem)

determine whether an element is inside a list. The element is searched using pointer equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
Non-zero if the element is in the list. Zero otherwise.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_find_member function type *sglib_type_find_member(type **list, type *elem)

find an element in the list. The element is searched using comparator equality.
Parameters:
list - the list.
elem - the element to search.
Returns:
The member of the list comparator equal to elem.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_get_first function type *sglib_type_get_first(type *list)

get the first element of a list.
Parameters:
list - the list.
Returns:
The first element of the list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_get_last function type *sglib_type_get_last(type *list)

get the last element of a list.
Parameters:
list - the list.
Returns:
The last element of the list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_len function int sglib_type_len(type *list)

compute the length of a list.
Parameters:
list - the list.
Returns:
The lenght of the list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_sort function void sglib_type_sort(type **list)

sort the list according to comparator. After the sorting *list will point to the first element of the list.
Parameters:
list - the list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_reverse function void sglib_type_reverse(type **list)

reverse the list.
Parameters:
list - the list.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init function type *sglib_type_it_init(struct sglib_type_iterator *it, type *list)

initialize an iterator it to run over elements of list.
Parameters:
it - the iterator.
list - the list.
Returns:
The first iterated element or NULL if there is no element.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_it_init_on_equal function type *sglib_type_it_init_on_equal(struct sglib_type_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto)

initialize an iterator it to run over those elements of list which are equal to equalto. The equality is considered with respect to the subcomparator which must be a subcomparator of the comparator.
Parameters:
it - the iterator.
list - the list.
subcomparator - the comparator used to find equal elements.
equalto - the element used as filter.
Returns:
The first iterated element or NULL if there is no element equal to equalto.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.
sglib_type_it_next function type *sglib_type_it_next(struct sglib_type_iterator *it)

get the next element from the iterator it.
Parameters:
it - the iterator.
Returns:
The next iterated element or NULL if there is no next element.
Generated by SGLIB_DEFINE_DL_LIST_FUNCTIONS
Parameters:
type - the type of list elements.
comparator - the comparator used to compare elements.
previous - the name of the field pointing to the previous element of the list.
next - the name of the field pointing to the next element of the list.





Red-Black Trees API: level 1

SGLIB_DEFINE_RBTREE_PROTOTYPES macro SGLIB_DEFINE_RBTREE_PROTOTYPES(type, left, right, colorbit, comparator)

define headers for red black tree implementation. Declared functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
SGLIB_DEFINE_RBTREE_FUNCTIONS macro SGLIB_DEFINE_RBTREE_FUNCTIONS(type, left, right, colorbit, comparator)

define functions for manipulating balanced red-black trees. Defined functions are:
sglib_type_add
sglib_type_add_if_not_member
sglib_type_delete
sglib_type_delete_if_member
sglib_type_find_member
sglib_type_is_member
sglib_type_len
sglib_type_it_init
sglib_type_it_init_on_equal
sglib_type_it_next
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.

Functions generated by above macros:

sglib_type_add function void sglib_type_add(type **tree, type *elem)

insert an element into a tree.
Parameters:
tree - the tree.
elem - the element to insert.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_add_if_not_member function int sglib_type_add_if_not_member(type **tree, type *elem, type **member)

insert an element if there is no comparator equal element in the tree.
Parameters:
tree - the tree.
elem - the element to insert.
member - in case if the element is a member of the tree, set *member to it.
Returns:
Non-zero if the element was inserted to the tree. Zero otherwise.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_delete function void sglib_type_delete(type **tree, type *elem)

delete an element. The element must be a member of the tree, it is looked using the pointer equality, not equality generated by comparator.
Parameters:
tree - the tree.
elem - the element to delete.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_delete_if_member function int sglib_type_delete_if_member(type **tree, type *elem, type **result)

find a comparator equal element in the tree and remove it.
Parameters:
tree - the tree.
elem - the element to search.
result - an output variable pointer. The variable will be set to the element removed from the tree.
Returns:
Non-zero if the element was removed from the tree. Zero otherwise.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_is_member function int sglib_type_is_member(type *tree, type *elem)

determine whether an element is inside a tree. The element is searched using pointer equality.
Parameters:
tree - the tree.
elem - the element to search.
Returns:
Non-zero if the element is in the tree. Zero otherwise.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_find_member function type *sglib_type_find_member(type **tree, type *elem)

find an element in the tree. The element is searched using comparator equality.
Parameters:
tree - the tree.
elem - the element to search.
Returns:
The member of the tree comparator equal to elem.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_len function int sglib_type_len(type *tree)

compute the length of a tree, i.e. compute how many elements is inside.
Parameters:
tree - the tree.
Returns:
The number of elements in the tree.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_it_init function type *sglib_type_it_init(struct sglib_type_iterator *it, type *tree)

initialize an iterator it to run over elements of tree.
Parameters:
it - the iterator.
tree - the tree.
Returns:
The first iterated element or NULL if there is no element.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_it_init_on_equal function type *sglib_type_it_init_on_equal(struct sglib_type_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto)

initialize an iterator it to run over those elements of the tree which are equal to equalto. The equality is considered with respect to the subcomparator which must be a subcomparator of the comparator.
Parameters:
it - the iterator.
tree - the tree.
subcomparator - the comparator used to find equal elements.
equalto - the element used as filter.
Returns:
The first iterated element or NULL if there is no element equal to equalto.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.
sglib_type_it_next function type *sglib_type_it_next(struct sglib_type_iterator *it)

get the next element from the iterator it.
Parameters:
it - the iterator.
Returns:
The next iterated element or NULL if there is no next element.
Generated by SGLIB_DEFINE_RBTREE_FUNCTIONS
Parameters:
type - the type of tree elements.
left - the name of the field containing left subtree of a node.
right - the name of the field containing right subtree of a node.
colorbit - the name of the field containing the color of a node.
comparator - a comparator used to compare elements.







Simple Examples



Arrays samples

// This program sorts its parameters using 
// array sort level 0 interface. 
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include "sglib.h"

#define MAX_ELEMS 1000

int main(int argc, char **argv) {
  int i,size;
  int a[MAX_ELEMS];
  size = argc-1;
  for (i=0; i<size; i++) {
    sscanf(argv[i+1],"%d", &a[i]);
  }
  SGLIB_ARRAY_SINGLE_QUICK_SORT(int, a, size, SGLIB_NUMERIC_COMPARATOR);
  for (i=0; i<size; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return(0);
}

// This program sorts its parameters using
// array sort level 1 interface. 
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include "sglib.h"

#define MAX_ELEMS 1000

SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(int, SGLIB_NUMERIC_COMPARATOR)

int main(int argc, char **argv) {
  int i,size;
  int a[MAX_ELEMS];
  size = argc-1;
  for (i=0; i<size; i++) {
    sscanf(argv[i+1],"%d", &a[i]);
  }
  sglib_int_array_heap_sort(a, size);
  for (i=0; i<size; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return(0);
}

// This program sorts its parameters using
// binary search to implement insert sort.
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sglib.h"

#define MAX_ELEMS 1000

int main(int argc, char **argv) {
  int i, size, found, index, tmp;
  int a[MAX_ELEMS];
  size = argc-1;
  for (i=0; i<size; i++) {
    sscanf(argv[i+1],"%d", &a[i]);
  }
  for(i=1; i<size; i++) {
    tmp = a[i];
    SGLIB_ARRAY_BINARY_SEARCH(int, a, 0, i, tmp, SGLIB_NUMERIC_COMPARATOR, found, index);
    memmove(a+index+1, a+index, (i-index)*sizeof(int));
    a[index]=tmp;
  }
  for (i=0; i<size; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return(0);
}


List Sample

// This program sorts its parameters using 
// list sort (level 0 interface).
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "sglib.h"

struct ilist {
    int i;
    struct ilist *next_ptr;
};

#define ILIST_COMPARATOR(e1, e2) (e1->i - e2->i)

int main(int argc, char **argv) {
  int i,a;
  struct ilist *l, *the_list, *ll;
  the_list = NULL;
  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &a);
    l = malloc(sizeof(struct ilist));
    l->i = a;
    SGLIB_LIST_ADD(struct ilist, the_list, l, next_ptr);
  }
  // it is useless, but anyway, get parameters in the right order
  SGLIB_LIST_REVERSE(struct ilist, the_list, next_ptr);
  // now sort them
  SGLIB_LIST_SORT(struct ilist, the_list, ILIST_COMPARATOR, next_ptr);
  // print the list
  SGLIB_LIST_MAP_ON_ELEMENTS(struct ilist, the_list, ll, next_ptr, {
    printf("%d ", ll->i);
  });
  printf("\n");
  // free all
  SGLIB_LIST_MAP_ON_ELEMENTS(struct ilist, the_list, ll, next_ptr, {
    free(ll);
  });
  return(0);
}


Sorted List Samples


// This program sorts its parameters using 
// insertion into sorted list (level 0 interface). 
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "sglib.h"

struct ilist {
    int i;
    struct ilist *next_ptr;
};

#define ILIST_COMPARATOR(e1, e2) (e1->i - e2->i)

int main(int argc, char **argv) {
  int i,a;
  struct ilist *l, *the_list, *ll;
  the_list = NULL;
  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &a);
    l = malloc(sizeof(struct ilist));
    l->i = a;
    // insert the new element into the list while keeping it sorted
    SGLIB_SORTED_LIST_ADD(struct ilist, the_list, l, ILIST_COMPARATOR, next_ptr);
  }
  SGLIB_LIST_MAP_ON_ELEMENTS(struct ilist, the_list, ll, next_ptr, {
    printf("%d ", ll->i);
  });
  printf("\n");
  SGLIB_LIST_MAP_ON_ELEMENTS(struct ilist, the_list, ll, next_ptr, {
    free(ll);
  });
  return(0);
}

// This program sorts its parameters using 
// insertion into sorted list (level 1 interface). 
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "sglib.h"

typedef struct ilist {
    int i;
    struct ilist *next_ptr;
} iListType;

#define ILIST_COMPARATOR(e1, e2) (e1->i - e2->i)

SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(iListType, ILIST_COMPARATOR, next_ptr)
SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(iListType, ILIST_COMPARATOR, next_ptr)

int main(int argc, char **argv) {
  int                               i,a;
  struct ilist                      *l, *the_list;
  struct sglib_iListType_iterator   it;
  the_list = NULL;
  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &a);
    l = malloc(sizeof(struct ilist));
    l->i = a;
    // insert the new element into the list while keeping it sorted
    sglib_iListType_add(&the_list, l);
  }
  // print the list
  for (l=the_list; l!=NULL; l=l->next_ptr) {
    printf("%d ", l->i);
  }
  printf("\n");
  // free all
  for(l=sglib_iListType_it_init(&it,the_list); l!=NULL; l=sglib_iListType_it_next(&it)) {
    free(l);  
  }
  return(0);
}


Double Linked List Sample


// This program reads parameters, sorts them
// and write them in both directions.
// The program is using level 1 interface.
// For example:
//   a.out 6 7 3 4 1 5
// writes
//   1 3 4 5 6 7
//   7 6 5 4 3 1


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "sglib.h"

typedef struct dllist {
    int i;
    struct dllist *ptr_to_next;
    struct dllist *ptr_to_previous;
} dllist;

#define DLLIST_COMPARATOR(e1, e2) (e1->i - e2->i)

SGLIB_DEFINE_DL_LIST_PROTOTYPES(dllist, DLLIST_COMPARATOR, ptr_to_previous, ptr_to_next);
SGLIB_DEFINE_DL_LIST_FUNCTIONS(dllist, DLLIST_COMPARATOR, ptr_to_previous, ptr_to_next);

int main(int argc, char **argv) {
  int                           i,a;
  dllist                        *l, *the_list;
  struct sglib_dllist_iterator  it;

  the_list = NULL;
  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &a);
    l = malloc(sizeof(dllist));
    l->i = a;
    sglib_dllist_add(&the_list, l);
  }
  // sort the list
  sglib_dllist_sort(&the_list);
  // print the list
  for(l=sglib_dllist_get_first(the_list); l!=NULL; l=l->ptr_to_next) printf("%d ", l->i);
  printf("\n");
  // print the list in reversed direction
  for(l=sglib_dllist_get_last(the_list); l!=NULL; l=l->ptr_to_previous) printf("%d ", l->i);
  printf("\n");
  // free the list
  for(l=sglib_dllist_it_init(&it,the_list); l!=NULL; l=sglib_dllist_it_next(&it)) {
    free(l);
  }
  return(0);
}


Hashed Container Sample

// This program uses hash table containing lists
// to remove multiple occurences of its parameters
// For example:
//   a.out 1 3 1 5 2 3 1 7 11 33 11
// writes:
//   11 1 2 33 3 5 7

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "sglib.h"

#define HASH_TAB_SIZE  10

typedef struct ilist {
  int i;
  struct ilist *next;
} ilist;

ilist *htab[HASH_TAB_SIZE];

#define ILIST_COMPARATOR(e1, e2)    (e1->i - e2->i)

unsigned int ilist_hash_function(ilist *e) {
  return(e->i);
}

SGLIB_DEFINE_LIST_PROTOTYPES(ilist, ILIST_COMPARATOR, next)
SGLIB_DEFINE_LIST_FUNCTIONS(ilist, ILIST_COMPARATOR, next)
SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(ilist, HASH_TAB_SIZE, ilist_hash_function)
SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(ilist, HASH_TAB_SIZE, ilist_hash_function)

int main(int argc, char **argv) {
  int                                   i, ai,aj, n;
  struct ilist                          ii, *nn, *ll;
  struct sglib_hashed_ilist_iterator    it;

  sglib_hashed_ilist_init(htab);

  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &n);
    ii.i = n;
    if (sglib_hashed_ilist_find_member(htab, &ii) == NULL) {
      nn = malloc(sizeof(struct ilist));
      nn->i = n;
      sglib_hashed_ilist_add(htab, nn);
    }
  }

  for(ll=sglib_hashed_ilist_it_init(&it,htab); ll!=NULL; ll=sglib_hashed_ilist_it_next(&it)) {
      printf("%d ", ll->i);
  }
  printf("\n");

  for(ll=sglib_hashed_ilist_it_init(&it,htab); ll!=NULL; ll=sglib_hashed_ilist_it_next(&it)) {
      free(ll);
  }
  return(0);
}


Red Black Tree Sample


// This program uses red-black tree to
// remove multiple occurences of the same
// value from its paramaters.
// For example:
//   a.out 6 7 3 4 1 4 1 3 5
// writes:
//   1 3 4 5 6 7


#include <stdio.h>
#include <stdlib.h>
#include "sglib.h"


typedef struct rbtree {
  int n;
  char color_field;
  struct rbtree *left;
  struct rbtree *right;
} rbtree;

#define CMPARATOR(x,y) ((x->n)-(y->n))

SGLIB_DEFINE_RBTREE_PROTOTYPES(rbtree, left, right, color_field, CMPARATOR);
SGLIB_DEFINE_RBTREE_FUNCTIONS(rbtree, left, right, color_field, CMPARATOR);

int main(int argc, char **argv) {
  int                           i,a;
  struct rbtree                 e, *t, *the_tree, *te;
  struct sglib_rbtree_iterator  it;

  the_tree = NULL;
  for (i=1; i<argc; i++) {
    sscanf(argv[i],"%d", &a);
    e.n = a;
    if (sglib_rbtree_find_member(the_tree, &e)==NULL) {
      t = malloc(sizeof(struct rbtree));
      t->n = a;
      sglib_rbtree_add(&the_tree, t);
    }
  }

  for(te=sglib_rbtree_it_init_inorder(&it,the_tree); te!=NULL; te=sglib_rbtree_it_next(&it)) {
    printf("%d ", te->n);
  }
  printf("\n");

  for(te=sglib_rbtree_it_init(&it,the_tree); te!=NULL; te=sglib_rbtree_it_next(&it)) {
    free(te);
  }

  return(0);
}