diff options
author | kx <kx@radix.pro> | 2023-03-24 03:55:33 +0300 |
---|---|---|
committer | kx <kx@radix.pro> | 2023-03-24 03:55:33 +0300 |
commit | bfc1508d26c89c9a36d2d9a827fe2c4ed128884d (patch) | |
tree | 8d41298a7072a3e289e4912f77ece75cbea1bd54 /csvncgi/dlist.c | |
parent | c836ae3775cf72f17e0b7e3792d156fdb389bee3 (diff) | |
download | csvn-ui-bfc1508d26c89c9a36d2d9a827fe2c4ed128884d.tar.xz |
Version 0.1.4
Diffstat (limited to 'csvncgi/dlist.c')
-rw-r--r-- | csvncgi/dlist.c | 691 |
1 files changed, 691 insertions, 0 deletions
diff --git a/csvncgi/dlist.c b/csvncgi/dlist.c new file mode 100644 index 0000000..fc91f2b --- /dev/null +++ b/csvncgi/dlist.c @@ -0,0 +1,691 @@ + +#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 ); +} |