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