#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <unistd.h>
#include <dlist.h>
#define DLIST_ERRMSG_SIZE 4096
void dlist_error( const char *fmt, ... )
{
va_list arg_ptr;
char buf[DLIST_ERRMSG_SIZE];
char msg[DLIST_ERRMSG_SIZE];
char *format = "%s: %s\n";
va_start( arg_ptr, fmt );
vsnprintf( msg, DLIST_ERRMSG_SIZE, (const void *)fmt, arg_ptr );
va_end( arg_ptr ); /* Reset variable arguments. */
snprintf( buf, DLIST_ERRMSG_SIZE, format, "dlist", msg );
(void)write( STDERR_FILENO, buf, strlen( buf ) );
exit( 1 );
}
dlist_errfunc dlist_fatal = dlist_error;
struct dlist *__dlist_alloc( void )
{
struct dlist *list = NULL;
list = (struct dlist *)malloc( sizeof( struct dlist ) );
if( !list ) { dlist_fatal( "Cannot allocate memory" ); }
bzero( (void *)list, sizeof( struct dlist ) );
return list;
}
struct dlist *dlist_first( struct dlist *list )
{
while( list && dlist_prev( list ) ) list = dlist_prev( list );
return list;
}
struct dlist *dlist_last( struct dlist *list )
{
while( list && dlist_next( list ) ) list = dlist_next( list );
return list;
}
int dlist_length( struct dlist *list )
{
int n = 0;
while( list )
{
list = dlist_next( list );
++n;
}
return n;
}
struct dlist *dlist_nth( struct dlist *list, int n )
{
while( list && (n-- > 0) )
{
list = dlist_next( list );
}
return list;
}
void *dlist_nth_data( struct dlist *list, int n )
{
while( list && (n-- > 0) )
{
list = dlist_next( list );
}
return list ? list->data : NULL;
}
int dlist_position( struct dlist *list, struct dlist *link )
{
int n = 0;
while( list )
{
if( list == link ) return n;
++n;
list = dlist_next( list );
}
return -1;
}
int dlist_index( struct dlist *list, const void *data )
{
int n = 0;
while( list )
{
if( list->data == data ) return n;
++n;
list = dlist_next( list );
}
return -1;
}
struct dlist *dlist_find( struct dlist *list, const void *data )
{
while( list )
{
if( list->data == data ) { break; }
list = dlist_next( list );
}
return list;
}
struct dlist *dlist_find_data( struct dlist *list, DLCMPF cmp_func, const void *data )
{
if( !list || !cmp_func ) return NULL;
while( list )
{
if( ! cmp_func( list->data, data ) ) { return list; }
list = dlist_next( list );
}
return NULL;
}
struct dlist *dlist_append( struct dlist *list, void *data )
{
struct dlist *node = NULL;
struct dlist *last = NULL;
node = __dlist_alloc();
node->data = data;
if( list )
{
last = dlist_last( list );
dlist_next( last ) = node;
dlist_prev( node ) = last;
return list;
}
return node;
}
struct dlist *dlist_prepend( struct dlist *list, void *data )
{
struct dlist *node = NULL;
struct dlist *first = NULL;
node = __dlist_alloc();
node->data = data;
if( list )
{
first = dlist_first( list );
dlist_prev( first ) = node;
dlist_next( node ) = first;
return node;
}
return node;
}
struct dlist *dlist_insert( struct dlist *list, void *data, int position )
{
struct dlist *node = NULL;
struct dlist *ptr = NULL;
if( position < 0 ) { return dlist_append( list, data ); }
if( position == 0 ) { return dlist_prepend( list, data ); }
ptr = dlist_nth( list, position );
if( !ptr ) { return dlist_append( list, data ); }
node = __dlist_alloc();
node->data = data;
node->prev = ptr->prev;
ptr->prev->next = node;
node->next = ptr;
ptr->prev = node;
return list;
}
struct dlist *dlist_insert_sorted( struct dlist *list, DLCMPF cmp_func, void *data )
{
struct dlist *node = NULL;
struct dlist *ptr = list;
int cmp;
if( !cmp_func ) return list;
if( !list )
{
node = __dlist_alloc();
node->data = data;
return node;
}
cmp = cmp_func( data, ptr->data );
while( (ptr->next) && (cmp > 0) )
{
ptr = ptr->next;
cmp = cmp_func( data, ptr->data );
}
node = __dlist_alloc();
node->data = data;
if( (!ptr->next) && (cmp > 0) )
{
ptr->next = node;
node->prev = ptr;
return list;
}
if( ptr->prev )
{
ptr->prev->next = node;
node->prev = ptr->prev;
}
node->next = ptr;
ptr->prev = node;
if( ptr == list )
return node;
else
return list;
}
struct dlist *dlist_insert_sorted_with_data( struct dlist *list, DLCMPDF cmp_func, void *data, void *user_data )
{
struct dlist *node = NULL;
struct dlist *ptr = list;
int cmp;
if( !cmp_func ) return list;
if( !list )
{
node = __dlist_alloc();
node->data = data;
return node;
}
cmp = cmp_func( data, ptr->data, user_data );
while( (ptr->next) && (cmp > 0) )
{
ptr = ptr->next;
cmp = cmp_func( data, ptr->data, user_data );
}
node = __dlist_alloc();
node->data = data;
if( (!ptr->next) && (cmp > 0) )
{
ptr->next = node;
node->prev = ptr;
return list;
}
if( ptr->prev )
{
ptr->prev->next = node;
node->prev = ptr->prev;
}
node->next = ptr;
ptr->prev = node;
if( ptr == list )
return node;
else
return list;
}
struct dlist *dlist_concat( struct dlist *list1, struct dlist *list2 )
{
struct dlist *ptr = NULL;
if( list2 )
{
ptr = dlist_last( list1 );
if( ptr )
ptr->next = list2;
else
list1 = list2;
list2->prev = ptr;
}
return list1;
}
struct dlist *dlist_insert_list( struct dlist *list1, struct dlist *list2, int position )
{
struct dlist *last = NULL;
struct dlist *ptr = NULL;
if( position < 0 ) { return dlist_concat( list1, list2 ); }
if( position == 0 ) { return dlist_concat( list2, list1 ); }
ptr = dlist_nth( list1, position );
if( !ptr ) { return dlist_concat( list1, list2 ); }
last = dlist_last( list2 );
if( last )
{
list2->prev = ptr->prev;
ptr->prev->next = list2;
last->next = ptr;
ptr->prev = last;
}
return list1;
}
struct dlist *__dlist_remove_link( struct dlist *list, struct dlist *link )
{
if( link == NULL ) return list;
if( link->prev )
{
if( link->prev->next == link )
{
link->prev->next = link->next;
}
else
{
dlist_fatal( "Corrupted double-linked list detected" );
}
}
if( link->next )
{
if( link->next->prev == link )
{
link->next->prev = link->prev;
}
else
{
dlist_fatal( "Corrupted double-linked list detected" );
}
}
if( link == list ) list = list->next;
link->next = NULL;
link->prev = NULL;
return list;
}
struct dlist *dlist_remove( struct dlist *list, const void *data )
{
struct dlist *ptr = list;
while( ptr )
{
if( ptr->data != data )
{
ptr = ptr->next;
}
else
{
list = __dlist_remove_link( list, ptr );
free( ptr );
break;
}
}
return list;
}
struct dlist *dlist_remove_all( struct dlist *list, const void *data )
{
struct dlist *ptr = list;
while( ptr )
{
if( ptr->data != data )
{
ptr = ptr->next;
}
else
{
struct dlist *next = ptr->next;
if( ptr->prev )
ptr->prev->next = next;
else
list = next;
if( next )
next->prev = ptr->prev;
free( ptr );
ptr = next;
}
}
return list;
}
struct dlist *dlist_remove_data( struct dlist *list, DLCMPF cmp_func, DLFUNC free_func, const void *data )
{
struct dlist *ptr = list;
if( !cmp_func ) return list;
while( ptr )
{
if( cmp_func( ptr->data, data ) != 0 )
{
ptr = ptr->next;
}
else
{
list = __dlist_remove_link( list, ptr );
if( free_func ) free_func( ptr->data, (void *)data ); /* free_func() can compare pointers */
free( ptr );
break;
}
}
return list;
}
struct dlist *dlist_remove_data_all( struct dlist *list, DLCMPF cmp_func, DLFUNC free_func, const void *data )
{
struct dlist *ptr = list;
if( !cmp_func ) return list;
while( ptr )
{
if( cmp_func( ptr->data, data ) != 0 )
{
ptr = ptr->next;
}
else
{
struct dlist *next = ptr->next;
if( ptr->prev )
ptr->prev->next = next;
else
list = next;
if( next )
next->prev = ptr->prev;
if( free_func ) free_func( ptr->data, (void *)data ); /* free_func() can compare pointers */
free( ptr );
ptr = next;
}
}
return list;
}
struct dlist *dlist_copy( struct dlist *list )
{
struct dlist *copy = NULL;
while( list )
{
copy = dlist_append( copy, list->data );
list = dlist_next( list );
}
return copy;
}
/* It simply switches the next and prev pointers of each element. */
struct dlist *dlist_reverse( struct dlist *list )
{
struct dlist *last = NULL;
while( list )
{
last = list;
list = last->next;
last->next = last->prev;
last->prev = list;
}
return last;
}
static struct dlist *__dlist_sort_merge( struct dlist *l1, struct dlist *l2, DLCMPF cmp_func )
{
struct dlist list, *l, *lprev;
int cmp;
l = &list;
lprev = NULL;
while( l1 && l2 )
{
cmp = ((DLCMPF) cmp_func)( l1->data, l2->data );
if( cmp <= 0 )
{
l->next = l1;
l1 = l1->next;
}
else
{
l->next = l2;
l2 = l2->next;
}
l = l->next;
l->prev = lprev;
lprev = l;
}
l->next = l1 ? l1 : l2;
l->next->prev = l;
return list.next;
}
static struct dlist *__dlist_sort_merge_with_data( struct dlist *l1, struct dlist *l2, DLCMPDF cmp_func, void *user_data )
{
struct dlist list, *l, *lprev;
int cmp;
l = &list;
lprev = NULL;
while( l1 && l2 )
{
cmp = ((DLCMPDF) cmp_func)( l1->data, l2->data, user_data );
if( cmp <= 0 )
{
l->next = l1;
l1 = l1->next;
}
else
{
l->next = l2;
l2 = l2->next;
}
l = l->next;
l->prev = lprev;
lprev = l;
}
l->next = l1 ? l1 : l2;
l->next->prev = l;
return list.next;
}
static struct dlist *__dlist_sort_real( struct dlist *list, DLCMPF cmp_func )
{
struct dlist *l1, *l2;
if( !list )
return NULL;
if( !list->next )
return list;
l1 = list;
l2 = list->next;
while( (l2 = l2->next) != NULL )
{
if( (l2 = l2->next) == NULL )
break;
l1 = l1->next;
}
l2 = l1->next;
l1->next = NULL;
return __dlist_sort_merge( __dlist_sort_real( list, cmp_func ),
__dlist_sort_real( l2, cmp_func ),
cmp_func );
}
static struct dlist *__dlist_sort_real_with_data( struct dlist *list, DLCMPDF cmp_func, void *user_data )
{
struct dlist *l1, *l2;
if( !list )
return NULL;
if( !list->next )
return list;
l1 = list;
l2 = list->next;
while( (l2 = l2->next) != NULL )
{
if( (l2 = l2->next) == NULL )
break;
l1 = l1->next;
}
l2 = l1->next;
l1->next = NULL;
return __dlist_sort_merge_with_data( __dlist_sort_real_with_data( list, cmp_func, user_data ),
__dlist_sort_real_with_data( l2, cmp_func, user_data ),
cmp_func,
user_data );
}
struct dlist *dlist_sort( struct dlist *list, DLCMPF cmp_func )
{
return __dlist_sort_real( list, cmp_func );
}
struct dlist *dlist_sort_with_data( struct dlist *list, DLCMPDF cmp_func, void *user_data )
{
return __dlist_sort_real_with_data( list, cmp_func, user_data );
}
void dlist_foreach( struct dlist *list, DLFUNC func, void *user_data )
{
struct dlist *next = NULL;
while( list )
{
next = dlist_next( list );
if( func ) { func( list->data, user_data ); }
list = next;
}
}
void __dlist_free( struct dlist *list )
{
struct dlist *next = NULL;
while( list )
{
next = dlist_next( list );
free( list ); list = NULL;
list = next;
}
}
void dlist_free( struct dlist *list, DLFUNC free_func )
{
dlist_foreach( list, free_func, NULL );
__dlist_free( list );
}