5 kx
5 kx /**********************************************************************
5 kx
5 kx Copyright 2019 Andrey V.Kosteltsev
5 kx
9 kx Licensed under the Radix cross Linux License, Version 1.0 .
5 kx you may not use this file except in compliance with the License.
5 kx You may obtain a copy of the License at
5 kx
9 kx https://radix-linux.su/licenses/LICENSE-1.0-en_US.txt
5 kx
5 kx Unless required by applicable law or agreed to in writing, software
5 kx distributed under the License is distributed on an "AS IS" BASIS,
5 kx WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
5 kx implied.
5 kx
5 kx **********************************************************************/
5 kx
5 kx #include <config.h>
5 kx
5 kx #include <stdlib.h>
5 kx #include <stdio.h>
5 kx #include <string.h>
5 kx
5 kx #include <msglog.h>
5 kx
5 kx #include <dlist.h>
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 ) { FATAL_ERROR( "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 WARNING( "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 WARNING( "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 }
Radix cross Linux Package Tools
Package Tools – is a set of utilities to create, install, and update RcL packages
11 Commits
0 Branches
2 Tags