SGLIB - A Simple Generic Library for C

1.) What is it about?

• sorting arrays
• manipulating linked lists
• manipulating sorted linked lists
• manipulating double linked lists
• manipulating red-black trees
• manipulating hashed containers

Sglib provides algorithms, not data structures. Algorithms implemented in Sglib operate on user's types, for example, list macros are operational for any data structure containing a pointer to the same type.

Sglib consists of a single header file without any binary code. In order to use it just put #include "sglib.h" into your source code.

The library is implemented in the C programming language and written for C programmers, however it is freely inspired by the Standard Template Library.

Although I wish to keep the library as simple as possible all suggestions for new functionalities are welcomed. Currently, the implementation of queues, priority queues, hashed tables and AVL trees is in progress.

2.) Why is it different from existing C libraries?

• Sglib is general.

  Sglib does not require its own data structures. You do not need to design your program to be used with Sglib from the beginning. You can start using Sglib at any stage of the development of your project with your existing data types.

  For example, let's suppose that you have a program working on a list of historical events represented by the structure:

  struct event {
    int time;
    char *title;
    char *description;
    struct category *category;
    struct event *nextEvent;
  };
  

  Let's suppose that you have a list of such events ordered by time. You are supposed to insert a new event to such list. First, you need to define a comparator. A comparator is a macro or function returning respectively a positive, negative or zero value for cases when the first parameter is greater, less or equal to the second. For example, the following macro is the comparator we need:

  #define CMP_EVENT(x,y) (x->time - y->time)
  

  Now you can insert a new event into the list (while keeping the list sorted) with the following code:

  SGLIB_SORTED_LIST_ADD(struct event, theList, newEvent, CMP_EVENT, nextEvent);
  

  This macro is expanded into a code inserting the newEvent onto the right place of theList.

  Note that the macro is also parameterized by the type of the list, the comparator used to order elements and by the name of the field pointing to the next element of the list. In consequence, the macro is very general and usable in nearly any circumstances.

• Sglib is generic.

  Sglib is generic in the sense that each functionality is parametrized by the type on which it operates. It defines algorithms independent on types. In C++ this can be done easily using templates, in C this is achieved with the preprocessor. Preprocessor does not matter whether macro parameters are types or values. However, because the preprocessor is purely textual and does not respect the underlying programming language, an additional effort is required to prevent macros from a misuse.

  For example, let's take a program defining an array of two-dimensional points represented by their coordinates. The corresponding definition in C is:

  struct point {
     int x;
     int y;
  } thePointArray[SIZE];
  

  and a macro defining lexicographical ordering on points:

  #define CMP_POINT(p1,p2) ((p1.x!=p2.x)?(p1.x-p2.x):(p1.y-p2.y))
  

  In such case the following line of code is sorting the array using heap sort:

    SGLIB_ARRAY_SINGLE_HEAP_SORT(struct point, thePointArray, SIZE, CMP_POINT);
  

  Note that no pointers are involved in this implementation.

• Sglib is fast.

  Sglib operates directly on your data structures. It does not require an additional pointer stored in its internal data representation. It does not contain any allocations and freeing of internal data structures neither. Moreover, macros are expanded in compile time saving the overhead related to function invocations.

• Sglib is independent on memory management system.

  Sglib does not create/allocate or destruct/free any datas. It only manipulates them. For example, macros manipulating balanced trees are exclusively modifiying the "left_son" and "right_son" (or whatever names user chooses) fields of allocated cells. In consequence, Sglib is absolutely independent on any memory management system. It never calls malloc or similar function. It is perfectly usable in projects requiring high discipline in memory allocation.

• Sglib is safe.

  Macros are known as being source of bugs because macro parameters may be evaluated several times and symbols inside parameters are resolved in the scope where parameters are used, not in the scope where the macro is invoked. For example, let's take the macro:

  #define LIST_LEN(type, list, result) {\\
    int i;\\
    type l;\\
    for(i=0,l=list; l!=NULL; l=l->next, i++) ;\\
    result = i;\\
  }
  

  invoked in the situation:

  int ilistlen(ilist *l) {
    int res;
    LIST_LEN(ilist, l, res);
    return(res);
  }
  

  Here, the symbol l in the line LIST_LEN(struct ilist, l, res); is logically expected to be resolved to the formal parameter of the function ilistlen. However in reality it is resolved to the local variable l defined by the line type l;\ inside the macro. This usually provokes compiler to complain about a use of an uninitialized variable.

  Sglib offers two mechanisms to avoid such problems.

  • First, Sglib is using particular naming conventions. All variables defined inside macros begins and ends with _ (underscore). As it is unusual to use such names in normal code this reduces the risk of conflicts. The above macro computing length of a list would be implemented as:

    #define LIST_LEN(type, list, result) { \\
      int _i_; \\
      type _l_; \\
      for(_i_=0,_l_=(list); _l_!=NULL; _l_=_l_->next, _i_++) ; \\
      (result) = _i_; \\
    }
    

  • Second, Sglib offers all its functionalities not only in form of macros, but also in form of standard C functions.

    Internally we call macros as a level - 0 user interface and functions as a level - 1 user interface. The level - 1 interface provides legal C functions for each particular type and those functions can be called from the main program without worrying about unwanted effects due to macro expansions.

    The level - 1 interface in praxis means, that you invoke one large macro at the beginning of your program. This macro is parametrized by the type and it generates all available functions for this type. Names of those functions will be composed from the prefix sglib_ followed by the name of your type and finishing by the name of the operation they implement.

    For example the invocation:

    SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(ilist, ilist_comparator, next)
    

    is expanded into definitions of functions, such as sglib_ilist_len, sglib_ilist_sort, sglib_ilist_add, sglib_ilist_delete, etc. Those functions take parameter of the type ilist and they use the function (or macro) ilist_comparator to compare elements. You can use those functions without worrying about macro expansions. For example, the above function computing the length of a list would be:

    int ilistlen(ilist *l) {
      int res;
      res = sglib_ilist_len(l);
      return(res);
    }
    

    Note that there is practically no danger of conflicts when invoking the SGLIB_DEFINE_SORTED_LIST_FUNCTIONS macro, because this macro is invoked in the top level scope and because it is using exclusively non-expression parameters.

3.) Why to do it?

In opposition to many cake eaters from my university, I believe that ideas behind Sglib are good because of my former research on modern (and generic) programming languages and because of my current work on a refactoring browser for C. From previous works I know that many generic constructions are implemented via some form of preprocessor. When working on the C refactoring browser I have written my own C preprocessor. During this work I have realized how much the preprocessor is standardized and how precisely it is defined in the current ANSI standard. Hence, even very advanced (you may say strange) preprocessor constructions are perfectly portable through compilers implementing ANSI standard.

4.) Is there any publication or documentation available?

For referencing Sglib in any kind of article, please cite:

M. Vittek, P. Borovansky, P.E. Moreau: A Simple Generic Library for C, in Reuse of Off-the-Shelf Components: Proceedings of
 9th International Conference on Software Reuse, Turin, pp. 423-426, 2006.

@Inproceedings{vittekBorovanskyMoreauTurin2006,
  author =       "Marian Vittek and Peter Borovansky and Pierre-Etienne Moreau",
  title =        "A Simple Generic Library for C",
  year =         "2006",
  pages =        "423-426",
  booktitle =    { Reuse of Off-the-Shelf Components: ,  Proceedings of 9th International Conference on Software Reuse, Tur
in, Italy},
  publisher =    {{Springer}}
}