SGLIB - Reference Manual

Content

• About
• Concepts
• Application Interface - level 0
  • Arrays
  • Linked Lists
  • Sorted Linked Lists
  • Double Linked Lists
  • Binary Trees
• Application Interface - level 1
  • Arrays
  • Hashed Containers
  • Linked Lists
  • Sorted Linked Lists
  • Double Linked Lists
  • Red-Black Trees
• Examples
  • Arrays
  • Hashed Containers
  • Linked Lists
  • Sorted Linked Lists
  • Double Linked Lists
  • Red-Black Trees

About Sglib

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:

• Efficiency. Resulting code must be as efficient as if it was specialized code
• Simplicity. No special tool is needed for generic constructions.
• In order to avoid conflicts with user symbols, each defined macro and function starts by 'SGLIB_' and 'sglib_' prefix respectively.
• In order to avoid situation when actual macro parameter conflicts with symbol defined within macro, all names defined within macros start and finish with underscore character.
• Each occurence of macro parameter giving an expression is always used enclosed into supplementary parentheses.

Sglib - Concepts

Comparator

#define SGLIB_NUMERIC_COMPARATOR(x, y) ((int)((x) - (y)))

Subcomparator

#define strsubcmp(x, y) (x[0] - y[0])

Array elem_exchanger and simultaneous sorting of multiple arrays

#define SGLIB_ARRAY_ELEMENTS_EXCHANGER(type, a, i, j) {type tmp;tmp=a[i];a[i]=a[j];a[j]=tmp;}

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);}

SGLIB_ARRAY_QUICK_SORT(char*, name, 1000, strcmp, ANNUARY_EXCHANGER);

Container

Linked lists

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;
};

Linked list next element parameter

Pointer equality versus comparator equality

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

Double Linked lists

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

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

Previous and next parameters of macros for double linked lists

Binary trees

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

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;
};

API: level 0

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

Lists API: level 0

Sorted Lists API: level 0

Double Linked Lists API: level 0

Binary Trees API: level 0

API: level 1

Arrays API: level 1

Hashed Containers API: level 1

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

Sorted Linked lists API: level 1

Double linked lists API: level 1

Red-Black Trees API: level 1

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);
}