Figure 3.1
This manual is for ABL (Abstract Basic List) (version 1.0, 2007-10-25 Thursday).
ABL is a basic list library.
Copyright © 2004–2007 Anton Kulchitsky
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is not included in the manual itself. The manual must be distributed with the file containing the full text of the license though.
ABL is a flexible list library. It can be used to define
linked lists of arbitrary type elements in C programs. It allows
easily to define and effectively use complicated types like list of
lists. ABL contains tools to make memory management easy. It
also includes basic high order functions for searching, filtering,
mapping, and effective reverse.
The library is implemented using (or abusing) C preprocessor rather than usual approach with void pointers. (Void pointers approach is described for example in “Mastering Algorithms with C” by Kyle Loudon.) The main difference between these approaches is that ABL is more designed as an extension to the language rather than a library. In our opinion, it allows more abstract definitions for a user and more flexible usage similar that is provided by template libraries in C++.
ABL also defines and was inspired by Lisp lists which maybe more convenient for Lisp/Scheme programmers to use.
The ABL can be included in any other libraries or programs that are compatible with LGPL by just copying a single header file.
ABL is not designed for huge lists that occupy a significant part of computer memory. ABL does not use any advancesd garbage collection techniques neither it tries to keep allocated memory continues. However, the flexibility allows it to perform some tasks very effectively operating just on pointers.
Advantages of ABL are: flexibility, convenience, speciality, everything is in one header file (no linkage), and sometimes effectiveness. Finally, it is free software distributed under GNU LGPL condition.
Note: ABL is designed exclusively as a list library. It will remain a list library only. Different types of lists can be included in it later though.
To install the library in a standard location, use
./configure
make
su -c "make install"
In the case you installing it locally or to non-standard location, use
./configure --prefix=/desired/location
make
make install
instead. Do not forget to change C_INCLUDE_PATH to be able to reach the library.
You also may want just to use the code of the library without
installing it. In this case, just copy file abl.h from
src to your program files and use #include "abl.h"
instead of #include <abl.h>.
ABL defines an abstract linked list of elements of uniform type. (To use this list for storing elements of different types, one may use void pointers.) An element of the list consists of a pointer and a content. A pointer (cdr) points to the next element of the list. The content (car) contains the meaning of the element.
ABL list stores the pointer head to the first element of the list, the pointer pointer to some another element of the list, and the length of the list which is the number of elements in the list. It also may store pointers to functions make and destroy of car if necessary. See Make and Destroy. The cdr of the last element in the list is nil.
To start to use the ABL in your program, all you need to do is to include abl.h into your code:
#include <abl.h>
Then, you can start to declare your own list types with the macro abl_typedef_list.
The macro
abl_typedef_listis used for a new list type definition. It must be used in the global name space outside of any function definition . It accepts two parameters. The first parameter is the type of the list element content (car). It can be a keyword or any type defined earlier bytypedefor#definecommands. It also can be a list type defined by the second parameter ofabl_typedef_listcommand as well (see below).The second parameter is your list type which is also a prefix to your list functions. It can be any C identifier. This macro introduces a new type (using
typedef) for the list and a set of functions (interface) to work with this type.
For example, if you need a list of integers, you may define this type by the following command somewhere in the global name space of your program (outside of all function definitions):
abl_typedef_list( int, int_list )
You need to type this macro without ; at the end.
Now you can declare variables of your list type (if you are from C++
world, you may think about them as objects of this list class):
int_list a,b,c;
for our example of int_list. You also can declare pointers to
this type and then use malloc for allocation of memory for this
type and, of course, sizeof function to determine the size of
the type:
int_list* pa = (int_list*) malloc( sizeof(int_list) );
You can produce types using new declared list type. For example, you may type
abl_typedef_list( int_list, intlists_list )
to determine the list of lists of integers.
Defining the type, you define the whole set of functions to work with
it. Every function has a prefix which is your list type followed by
the underscore. The following description is defined without that
prefix. Thus, to call init on your list of integers defined in
the previous section, you need to call actually int_list_init
for it. The first parameter of any interface function is a pointer to
a variable of this list type.
These functions must be used before any other functions are
applied. Function init must be called before list
usage. Function set_md is optional.
initinitializes the list pointed by plist before any usage. This function must be called before of any other operation on the particular variable of your list type. This function set make and destroy to NULL. See Make and Destroy.
set_mdset make and destroy functions for the list content. Either make or destroy (or both) can be set to NULL. In this case, these make or destroy will be ignored. See Make and Destroy.
Adds a head and copies the content from
pcarto element's content. It returnsABL_ERR_ALLOCif there was a memory allocation error orABL_OKon success.
Creates a new head of the list. The previous head becomes the second element. It does not initialize the added head content explicitly. However, the element can be initialized by
makefunction. Ifmakeis set byset_mdfunction,create_head_ccalls themakewithcparamas a parameter on a new allocated car (content). See Make and Destroy. It returnsABL_ERR_ALLOCif there was a memory allocation error, any error code returned by themake, orABL_OKon success. You can setcparamtoNULLif you do not usemake. Note:makecan be used to initialize the element. See Examples.
Removes all elements from the list. It calls
del_headuntil the list is empty. This function must be called at least once after all work on the list unless it is absolutely clear that the list is empty.
Deletes the head element from the list and move the head to the next element. It releases the memory from the head content and from the head. It also calls the
destroyon the car if thedestroyis notNULL. See Make and Destroy. Programmers that do not use thedestroy, must care about memory freeing if the content contains pointers.del_headdoes nothing for the empty list.
Deletes the element next after the point from the list. It releases the memory from the element content and from the element. It also calls the
destroyon the car if thedestroyis notNULL. See Make and Destroy. Programmers that do not usedestroyfunction must care about memory freeing if content contains pointers.If the pointer or the next element after the pointer is abl_nil, nothing is done and error code is returned.
Error codes:
- ABL_OK if the element was deleted successfully
- ABL_ERR_NIL if pointer points to nil or list is empty
- ABL_ERR_DELNIL if the next element is NIL
Moves the point to the next element. If point points to nil, it does nothing.
same as
get_car,get_headreturns the car (pointer to the content) of the head element.
same as
get_head,get_carreturns the pointer to the content of the head element.
get_pointreturns the car (pointer to the content) of the element pointed by the point. It returns NULL if the pointer points toabl_nil.
Returns the pointer to the content of the element next after the list pointer or NULL if there is no such an element.
These functions return the state of the list: if it is empty, where the point is, the length of the list.
Returns 1 if the point points to the nil that means to the end of the list.
Returns the number of elements in the list. Operation order is O(1) due to list stores the length in the internal variable.
Reverse (destructively) the list in order. The operation is of O(n) order (performs 4 assignments per element).
These class of functions contains operators on the list that apply some functions to the elements or content and modify the list or return some values.
Deletes all elements in the list that satisfy the filter_cond. The function
filter_condmust return 0 if the element is not to be deleted.deleteifreturns the error code (ABL_OKmeans no errors).
Returns pointer to the element content (car) of the list that first satisfies of the
predicatecondition.
Applies
fto every element in the list.
The loop macro is defined to simplify routine looping code.
Starts the loop for every element of the list
lst. The reference to the element is performed byget_pointfunction. Two parameters are necessary: the list type and the pointer to the list. See Examples.
Ending of the loop facility. See ABL_BEGIN_LOOP for details.
Make and destroy feature intend to improve the memory management of
the list. They are created to automate memory allocation and
deallocation for list of pointers of list of elements that contains
some pointers. The simplest example can be a list of char*, see
examples below. Make also proved to be useful beyond this narrow
application.
Destroy is a function that returns void. It has only one parameter, a pointer to the car type. Thus, if the list was declared
abl_typedef_list( char*, str_list )
then the destructor must be declared
void mydestr( char** );
(mydestr can be replaced by any desired name.) Then
the destroy can be set for the list by str_list_set_md
function.
If destroy is different from NULL, it is called by any deletion
function on the car of the element to delete. See Deletion of Elements. Usually, destroy contains only calls of free
function. Thus, for the example above, we would have
void mydestr( char** pstr )
{
free( *pstr );
}
The make is a function that returns int, the error code. It
must return ABL_OK on success. Otherwise, it can return any
error code but 0. This error code will be returned by some addition
functions that call the make (namely create_head). The
constructor has two parameters: (1) The pointer to the car of the
element to construct and (2) The void pointer to some initialization
value. This value is used to determine what kind of initialization is
to be done.
The constructor is called by create_head if and only if the
constructor set to any other value than NULL. The last
parameter of these functions is sent to the make.
The program creates a list of integers, initializes it with 0,1,2,3,4 in a loop, and prints all elements from the head to the tail. It uses the simplest functions and the LOOP macro for printing elements.
#include <stdio.h>
#include <stdlib.h>
#include <abl.h>
/* declare the int_list type */
abl_typedef_list( int, int_list )
int main()
{
int_list lst; /* list of ints */
int i; /* iterator */
int_list_init( &lst ); /* initialize the list */
/* initialize list elements by meaning of loop index */
for( i=0; i<5; ++i ) int_list_add_head( &lst, &i );
/* print all elements from the list */
ABL_BEGIN_LOOP( int_list, &lst ) {
printf( "%d\n", *int_list_get_point(&lst) );
} ABL_END_LOOP( int_list, &lst );
/* clean the list */
int_list_clean( &lst );
return 0;
}
This example demonstrates more advanced usage of list.
The program creates a list of integers, initializes it with
0,1,2,3,4,5,6,7,8,9,10 in a loop, finds and prints the first element
that divides 4 (it is 8 of course), deletes all odd elements from the
list, reverse the list, and prints all elements from the head to the
tail using mapcar function.
#include <stdio.h>
#include <stdlib.h>
#include <abl.h>
/* declare the int_list type */
abl_typedef_list( int, int_list )
/* print an elements */
void printint( int* a )
{
printf( "%d\n", *a );
}
int isodd( int* a )
{
return ( *a % 2 == 1 );
}
int isdiv4( int *a )
{
return ( *a % 4 == 0 );
}
int main()
{
int_list lst; /* list of ints */
int i; /* iterator */
int_list_init( &lst ); /* initialize the list */
/* initialize list elements by meaning of loop index */
for( i=0; i<=11; ++i ) int_list_add_head( &lst, &i );
/* find the first element that %4==0, and print it */
printf( "The first element that divides 4 is [%d]\n",
*int_list_findif( &lst, isdiv4 ) );
/* delete all odd elements */
int_list_deleteif( &lst, isodd );
/* reverse the list to make a head == 0 */
int_list_nreverse( &lst );
/* print all elements from the list */
int_list_mapcar( &lst, printint );
/* clean the list */
int_list_clean( &lst );
return 0;
}
This program creates a list of strings, add two elements "First String" and "Second String" to it, print the list content and then cleans the list properly.
This example is created to demonstrate how to allocate memory for the elements without make/destroy usage.
#include <stdio.h>
#include <stdlib.h>
#include <abl.h>
abl_typedef_list( char*, str_list )
int main()
{
str_list lst;
char* cc;
/* List initialization */
str_list_init( &lst );
/* Set two list elements "First String" and "Second String" */
str_list_create_head( &lst, NULL );
*str_list_get_head( &lst ) = strdup("First String");
str_list_create_head( &lst, NULL );
*str_list_get_head( &lst ) = strdup("Second String");
/* Print the list */
ABL_BEGIN_LOOP( str_list, &lst ) {
printf( "%s\n", *str_list_get_point( &lst ) );
} ABL_END_LOOP( str_list, &lst );
/* Free the memory from each string */
ABL_BEGIN_LOOP( str_list, &lst ) {
free( *str_list_get_point( &lst ) );
} ABL_END_LOOP( str_list, &lst );
/* Delete all elements */
str_list_clean( &lst );
return 0;
}
This program creates a list of strings, add two elements "First String" and "Second String" to it, print the list content with mapcar, and then cleans the list properly.
This test is created to demonstrate how to allocate and initialize memory for the elements WITH make/destroy usage.
#include <stdio.h>
#include <stdlib.h>
#include <abl.h>
abl_typedef_list( char*, str_list )
void printstr( char** pstr )
{
printf( "%s\n", *pstr );
}
int str_list_make( char** pstr, void* inistr )
{
*pstr = strdup( (char*)inistr );
if( !(*pstr) ) return ABL_ERR_ALLOC;
return ABL_OK;
}
void str_list_destroy( char** pstr )
{
free( *pstr );
}
int main()
{
str_list lst;
/* List initialization */
str_list_init( &lst );
str_list_set_md( &lst, str_list_make, str_list_destroy );
/* Set two list elements "First String" and "Second String" */
str_list_create_head( &lst, "First String" );
str_list_create_head( &lst, "Second String" );
/* Print the list */
str_list_mapcar( &lst, printstr );
/* Delete all elements */
str_list_clean( &lst );
return 0;
}
This section is a short list of planned features with explanations.
add_after_point and add_after_point_c.
New in version 1.0 compare to version 0.99
This is a major release with a lot of big changes.
add_head_c is deleted! See Interface.
create_head_c is deleted. Function create_head
was modify to unify both creation methods. See Interface.
New in version 0.99 compare to version 0.98
This is a major release in spite of the minor change in numbers. After extensive testing, it supposed to be version 1.0.
mapcar, add_head_c, create_head,
create_head_c. See Interface.
New in version 0.98 compare to version 0.9/0.95
del_after_point and get_point_next.
See Interface.
ABL_BEGIN_LOOP and ABL_END_LOOP. See The Loop Macro.
point_next changed the name to move_point_next.
Thanks k_andy (Andrei from Donetsk) from http://linux.org.ru for discovering a design bug and advising how to fix it in transition from version 0.99 to version 1.0.
This documentation is free.
I like the GNU FDL, however, it seems for me too large to include into the documentation. Moreover, I do not like all examples in the text to be dual-licensed. Thus, this documentation is distributed under the GNU GPLv3 license. See Free Software Foundation web site for details on it.
ABL_BEGIN_LOOP on abl: The Loop MacroABL_END_LOOP on abl: The Loop Macroabl_typedef_list: List Declarationadd_head: Addition of Elementsclean: Deletion of Elementscreate_head_c: Addition of Elementsdel_after_point: Deletion of Elementsdel_head: Deletion of Elementsdeleteif: Higher-Order Functionsfindif: Higher-Order Functionsget_car: Getting Elementsget_head: Getting Elementsget_point: Getting Elementsget_point_next: Getting Elementsinit: Initializationis_empty: List Stateis_point_nil: List Statelength: List Statemapcar: Higher-Order Functionsmove_point_head: Point Movementmove_point_next: Point Movementnreverse: Reorderingset_md: Initialization