bfc1508d (kx 2023-03-24 03:55:33 +0300 1)
bfc1508d (kx 2023-03-24 03:55:33 +0300 2) #ifdef HAVE_CONFIG_H
bfc1508d (kx 2023-03-24 03:55:33 +0300 3) #include <config.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 4) #endif
bfc1508d (kx 2023-03-24 03:55:33 +0300 5)
bfc1508d (kx 2023-03-24 03:55:33 +0300 6) #include <stdlib.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 7) #include <stdio.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 8) #include <string.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 9) #include <stdarg.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 10) #include <unistd.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 11)
bfc1508d (kx 2023-03-24 03:55:33 +0300 12) #include <dlist.h>
bfc1508d (kx 2023-03-24 03:55:33 +0300 13)
bfc1508d (kx 2023-03-24 03:55:33 +0300 14)
bfc1508d (kx 2023-03-24 03:55:33 +0300 15) #define DLIST_ERRMSG_SIZE 4096
bfc1508d (kx 2023-03-24 03:55:33 +0300 16)
bfc1508d (kx 2023-03-24 03:55:33 +0300 17) void dlist_error( const char *fmt, ... )
bfc1508d (kx 2023-03-24 03:55:33 +0300 18) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 19) va_list arg_ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 20) char buf[DLIST_ERRMSG_SIZE];
bfc1508d (kx 2023-03-24 03:55:33 +0300 21) char msg[DLIST_ERRMSG_SIZE];
bfc1508d (kx 2023-03-24 03:55:33 +0300 22) char *format = "%s: %s\n";
bfc1508d (kx 2023-03-24 03:55:33 +0300 23)
bfc1508d (kx 2023-03-24 03:55:33 +0300 24) va_start( arg_ptr, fmt );
bfc1508d (kx 2023-03-24 03:55:33 +0300 25)
bfc1508d (kx 2023-03-24 03:55:33 +0300 26) vsnprintf( msg, DLIST_ERRMSG_SIZE, (const void *)fmt, arg_ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 27)
bfc1508d (kx 2023-03-24 03:55:33 +0300 28) va_end( arg_ptr ); /* Reset variable arguments. */
bfc1508d (kx 2023-03-24 03:55:33 +0300 29)
bfc1508d (kx 2023-03-24 03:55:33 +0300 30) snprintf( buf, DLIST_ERRMSG_SIZE, format, "dlist", msg );
bfc1508d (kx 2023-03-24 03:55:33 +0300 31)
bfc1508d (kx 2023-03-24 03:55:33 +0300 32) (void)write( STDERR_FILENO, buf, strlen( buf ) );
bfc1508d (kx 2023-03-24 03:55:33 +0300 33)
bfc1508d (kx 2023-03-24 03:55:33 +0300 34) exit( 1 );
bfc1508d (kx 2023-03-24 03:55:33 +0300 35) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 36)
bfc1508d (kx 2023-03-24 03:55:33 +0300 37) dlist_errfunc dlist_fatal = dlist_error;
bfc1508d (kx 2023-03-24 03:55:33 +0300 38)
bfc1508d (kx 2023-03-24 03:55:33 +0300 39)
bfc1508d (kx 2023-03-24 03:55:33 +0300 40) struct dlist *__dlist_alloc( void )
bfc1508d (kx 2023-03-24 03:55:33 +0300 41) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 42) struct dlist *list = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 43)
bfc1508d (kx 2023-03-24 03:55:33 +0300 44) list = (struct dlist *)malloc( sizeof( struct dlist ) );
bfc1508d (kx 2023-03-24 03:55:33 +0300 45) if( !list ) { dlist_fatal( "Cannot allocate memory" ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 46)
bfc1508d (kx 2023-03-24 03:55:33 +0300 47) bzero( (void *)list, sizeof( struct dlist ) );
bfc1508d (kx 2023-03-24 03:55:33 +0300 48)
bfc1508d (kx 2023-03-24 03:55:33 +0300 49) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 50) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 51)
bfc1508d (kx 2023-03-24 03:55:33 +0300 52)
bfc1508d (kx 2023-03-24 03:55:33 +0300 53)
bfc1508d (kx 2023-03-24 03:55:33 +0300 54) struct dlist *dlist_first( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 55) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 56) while( list && dlist_prev( list ) ) list = dlist_prev( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 57)
bfc1508d (kx 2023-03-24 03:55:33 +0300 58) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 59) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 60)
bfc1508d (kx 2023-03-24 03:55:33 +0300 61) struct dlist *dlist_last( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 62) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 63) while( list && dlist_next( list ) ) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 64)
bfc1508d (kx 2023-03-24 03:55:33 +0300 65) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 66) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 67)
bfc1508d (kx 2023-03-24 03:55:33 +0300 68) int dlist_length( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 69) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 70) int n = 0;
bfc1508d (kx 2023-03-24 03:55:33 +0300 71)
bfc1508d (kx 2023-03-24 03:55:33 +0300 72) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 73) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 74) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 75) ++n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 76) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 77)
bfc1508d (kx 2023-03-24 03:55:33 +0300 78) return n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 79) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 80)
bfc1508d (kx 2023-03-24 03:55:33 +0300 81) struct dlist *dlist_nth( struct dlist *list, int n )
bfc1508d (kx 2023-03-24 03:55:33 +0300 82) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 83) while( list && (n-- > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 84) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 85) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 86) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 87)
bfc1508d (kx 2023-03-24 03:55:33 +0300 88) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 89) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 90)
bfc1508d (kx 2023-03-24 03:55:33 +0300 91) void *dlist_nth_data( struct dlist *list, int n )
bfc1508d (kx 2023-03-24 03:55:33 +0300 92) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 93) while( list && (n-- > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 94) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 95) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 96) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 97)
bfc1508d (kx 2023-03-24 03:55:33 +0300 98) return list ? list->data : NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 99) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 100)
bfc1508d (kx 2023-03-24 03:55:33 +0300 101) int dlist_position( struct dlist *list, struct dlist *link )
bfc1508d (kx 2023-03-24 03:55:33 +0300 102) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 103) int n = 0;
bfc1508d (kx 2023-03-24 03:55:33 +0300 104)
bfc1508d (kx 2023-03-24 03:55:33 +0300 105) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 106) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 107) if( list == link ) return n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 108) ++n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 109) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 110) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 111)
bfc1508d (kx 2023-03-24 03:55:33 +0300 112) return -1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 113) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 114)
bfc1508d (kx 2023-03-24 03:55:33 +0300 115) int dlist_index( struct dlist *list, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 116) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 117) int n = 0;
bfc1508d (kx 2023-03-24 03:55:33 +0300 118)
bfc1508d (kx 2023-03-24 03:55:33 +0300 119) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 120) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 121) if( list->data == data ) return n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 122) ++n;
bfc1508d (kx 2023-03-24 03:55:33 +0300 123) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 124) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 125)
bfc1508d (kx 2023-03-24 03:55:33 +0300 126) return -1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 127) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 128)
bfc1508d (kx 2023-03-24 03:55:33 +0300 129) struct dlist *dlist_find( struct dlist *list, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 130) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 131) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 132) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 133) if( list->data == data ) { break; }
bfc1508d (kx 2023-03-24 03:55:33 +0300 134) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 135) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 136)
bfc1508d (kx 2023-03-24 03:55:33 +0300 137) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 138) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 139)
bfc1508d (kx 2023-03-24 03:55:33 +0300 140)
bfc1508d (kx 2023-03-24 03:55:33 +0300 141) struct dlist *dlist_find_data( struct dlist *list, DLCMPF cmp_func, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 142) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 143) if( !list || !cmp_func ) return NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 144)
bfc1508d (kx 2023-03-24 03:55:33 +0300 145) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 146) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 147) if( ! cmp_func( list->data, data ) ) { return list; }
bfc1508d (kx 2023-03-24 03:55:33 +0300 148) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 149) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 150)
bfc1508d (kx 2023-03-24 03:55:33 +0300 151) return NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 152) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 153)
bfc1508d (kx 2023-03-24 03:55:33 +0300 154)
bfc1508d (kx 2023-03-24 03:55:33 +0300 155) struct dlist *dlist_append( struct dlist *list, void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 156) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 157) struct dlist *node = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 158) struct dlist *last = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 159)
bfc1508d (kx 2023-03-24 03:55:33 +0300 160) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 161) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 162)
bfc1508d (kx 2023-03-24 03:55:33 +0300 163) if( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 164) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 165) last = dlist_last( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 166)
bfc1508d (kx 2023-03-24 03:55:33 +0300 167) dlist_next( last ) = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 168) dlist_prev( node ) = last;
bfc1508d (kx 2023-03-24 03:55:33 +0300 169)
bfc1508d (kx 2023-03-24 03:55:33 +0300 170) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 171) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 172)
bfc1508d (kx 2023-03-24 03:55:33 +0300 173) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 174) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 175)
bfc1508d (kx 2023-03-24 03:55:33 +0300 176) struct dlist *dlist_prepend( struct dlist *list, void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 177) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 178) struct dlist *node = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 179) struct dlist *first = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 180)
bfc1508d (kx 2023-03-24 03:55:33 +0300 181) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 182) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 183)
bfc1508d (kx 2023-03-24 03:55:33 +0300 184) if( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 185) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 186) first = dlist_first( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 187)
bfc1508d (kx 2023-03-24 03:55:33 +0300 188) dlist_prev( first ) = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 189) dlist_next( node ) = first;
bfc1508d (kx 2023-03-24 03:55:33 +0300 190)
bfc1508d (kx 2023-03-24 03:55:33 +0300 191) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 192) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 193)
bfc1508d (kx 2023-03-24 03:55:33 +0300 194) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 195) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 196)
bfc1508d (kx 2023-03-24 03:55:33 +0300 197) struct dlist *dlist_insert( struct dlist *list, void *data, int position )
bfc1508d (kx 2023-03-24 03:55:33 +0300 198) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 199) struct dlist *node = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 200) struct dlist *ptr = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 201)
bfc1508d (kx 2023-03-24 03:55:33 +0300 202) if( position < 0 ) { return dlist_append( list, data ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 203) if( position == 0 ) { return dlist_prepend( list, data ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 204)
bfc1508d (kx 2023-03-24 03:55:33 +0300 205) ptr = dlist_nth( list, position );
bfc1508d (kx 2023-03-24 03:55:33 +0300 206) if( !ptr ) { return dlist_append( list, data ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 207)
bfc1508d (kx 2023-03-24 03:55:33 +0300 208) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 209) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 210)
bfc1508d (kx 2023-03-24 03:55:33 +0300 211) node->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 212) ptr->prev->next = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 213) node->next = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 214) ptr->prev = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 215)
bfc1508d (kx 2023-03-24 03:55:33 +0300 216) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 217) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 218)
bfc1508d (kx 2023-03-24 03:55:33 +0300 219) struct dlist *dlist_insert_sorted( struct dlist *list, DLCMPF cmp_func, void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 220) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 221) struct dlist *node = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 222) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 223) int cmp;
bfc1508d (kx 2023-03-24 03:55:33 +0300 224)
bfc1508d (kx 2023-03-24 03:55:33 +0300 225) if( !cmp_func ) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 226)
bfc1508d (kx 2023-03-24 03:55:33 +0300 227) if( !list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 228) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 229) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 230) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 231) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 232) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 233)
bfc1508d (kx 2023-03-24 03:55:33 +0300 234) cmp = cmp_func( data, ptr->data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 235)
bfc1508d (kx 2023-03-24 03:55:33 +0300 236) while( (ptr->next) && (cmp > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 237) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 238) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 239) cmp = cmp_func( data, ptr->data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 240) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 241)
bfc1508d (kx 2023-03-24 03:55:33 +0300 242) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 243) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 244)
bfc1508d (kx 2023-03-24 03:55:33 +0300 245) if( (!ptr->next) && (cmp > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 246) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 247) ptr->next = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 248) node->prev = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 249) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 250) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 251)
bfc1508d (kx 2023-03-24 03:55:33 +0300 252) if( ptr->prev )
bfc1508d (kx 2023-03-24 03:55:33 +0300 253) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 254) ptr->prev->next = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 255) node->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 256) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 257) node->next = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 258) ptr->prev = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 259)
bfc1508d (kx 2023-03-24 03:55:33 +0300 260) if( ptr == list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 261) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 262) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 263) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 264) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 265)
bfc1508d (kx 2023-03-24 03:55:33 +0300 266) struct dlist *dlist_insert_sorted_with_data( struct dlist *list, DLCMPDF cmp_func, void *data, void *user_data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 267) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 268) struct dlist *node = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 269) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 270) int cmp;
bfc1508d (kx 2023-03-24 03:55:33 +0300 271)
bfc1508d (kx 2023-03-24 03:55:33 +0300 272) if( !cmp_func ) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 273)
bfc1508d (kx 2023-03-24 03:55:33 +0300 274) if( !list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 275) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 276) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 277) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 278) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 279) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 280)
bfc1508d (kx 2023-03-24 03:55:33 +0300 281) cmp = cmp_func( data, ptr->data, user_data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 282)
bfc1508d (kx 2023-03-24 03:55:33 +0300 283) while( (ptr->next) && (cmp > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 284) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 285) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 286) cmp = cmp_func( data, ptr->data, user_data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 287) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 288)
bfc1508d (kx 2023-03-24 03:55:33 +0300 289) node = __dlist_alloc();
bfc1508d (kx 2023-03-24 03:55:33 +0300 290) node->data = data;
bfc1508d (kx 2023-03-24 03:55:33 +0300 291)
bfc1508d (kx 2023-03-24 03:55:33 +0300 292) if( (!ptr->next) && (cmp > 0) )
bfc1508d (kx 2023-03-24 03:55:33 +0300 293) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 294) ptr->next = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 295) node->prev = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 296) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 297) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 298)
bfc1508d (kx 2023-03-24 03:55:33 +0300 299) if( ptr->prev )
bfc1508d (kx 2023-03-24 03:55:33 +0300 300) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 301) ptr->prev->next = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 302) node->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 303) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 304) node->next = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 305) ptr->prev = node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 306)
bfc1508d (kx 2023-03-24 03:55:33 +0300 307) if( ptr == list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 308) return node;
bfc1508d (kx 2023-03-24 03:55:33 +0300 309) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 310) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 311) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 312)
bfc1508d (kx 2023-03-24 03:55:33 +0300 313) struct dlist *dlist_concat( struct dlist *list1, struct dlist *list2 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 314) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 315) struct dlist *ptr = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 316)
bfc1508d (kx 2023-03-24 03:55:33 +0300 317) if( list2 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 318) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 319) ptr = dlist_last( list1 );
bfc1508d (kx 2023-03-24 03:55:33 +0300 320) if( ptr )
bfc1508d (kx 2023-03-24 03:55:33 +0300 321) ptr->next = list2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 322) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 323) list1 = list2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 324)
bfc1508d (kx 2023-03-24 03:55:33 +0300 325) list2->prev = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 326) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 327)
bfc1508d (kx 2023-03-24 03:55:33 +0300 328) return list1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 329) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 330)
bfc1508d (kx 2023-03-24 03:55:33 +0300 331) struct dlist *dlist_insert_list( struct dlist *list1, struct dlist *list2, int position )
bfc1508d (kx 2023-03-24 03:55:33 +0300 332) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 333) struct dlist *last = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 334) struct dlist *ptr = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 335)
bfc1508d (kx 2023-03-24 03:55:33 +0300 336) if( position < 0 ) { return dlist_concat( list1, list2 ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 337) if( position == 0 ) { return dlist_concat( list2, list1 ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 338)
bfc1508d (kx 2023-03-24 03:55:33 +0300 339) ptr = dlist_nth( list1, position );
bfc1508d (kx 2023-03-24 03:55:33 +0300 340) if( !ptr ) { return dlist_concat( list1, list2 ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 341)
bfc1508d (kx 2023-03-24 03:55:33 +0300 342) last = dlist_last( list2 );
bfc1508d (kx 2023-03-24 03:55:33 +0300 343) if( last )
bfc1508d (kx 2023-03-24 03:55:33 +0300 344) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 345) list2->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 346) ptr->prev->next = list2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 347) last->next = ptr;
bfc1508d (kx 2023-03-24 03:55:33 +0300 348) ptr->prev = last;
bfc1508d (kx 2023-03-24 03:55:33 +0300 349) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 350)
bfc1508d (kx 2023-03-24 03:55:33 +0300 351) return list1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 352) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 353)
bfc1508d (kx 2023-03-24 03:55:33 +0300 354) struct dlist *__dlist_remove_link( struct dlist *list, struct dlist *link )
bfc1508d (kx 2023-03-24 03:55:33 +0300 355) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 356) if( link == NULL ) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 357)
bfc1508d (kx 2023-03-24 03:55:33 +0300 358) if( link->prev )
bfc1508d (kx 2023-03-24 03:55:33 +0300 359) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 360) if( link->prev->next == link )
bfc1508d (kx 2023-03-24 03:55:33 +0300 361) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 362) link->prev->next = link->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 363) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 364) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 365) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 366) dlist_fatal( "Corrupted double-linked list detected" );
bfc1508d (kx 2023-03-24 03:55:33 +0300 367) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 368) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 369) if( link->next )
bfc1508d (kx 2023-03-24 03:55:33 +0300 370) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 371) if( link->next->prev == link )
bfc1508d (kx 2023-03-24 03:55:33 +0300 372) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 373) link->next->prev = link->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 374) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 375) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 376) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 377) dlist_fatal( "Corrupted double-linked list detected" );
bfc1508d (kx 2023-03-24 03:55:33 +0300 378) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 379) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 380)
bfc1508d (kx 2023-03-24 03:55:33 +0300 381) if( link == list ) list = list->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 382)
bfc1508d (kx 2023-03-24 03:55:33 +0300 383) link->next = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 384) link->prev = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 385)
bfc1508d (kx 2023-03-24 03:55:33 +0300 386) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 387) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 388)
bfc1508d (kx 2023-03-24 03:55:33 +0300 389) struct dlist *dlist_remove( struct dlist *list, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 390) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 391) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 392)
bfc1508d (kx 2023-03-24 03:55:33 +0300 393) while( ptr )
bfc1508d (kx 2023-03-24 03:55:33 +0300 394) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 395) if( ptr->data != data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 396) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 397) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 398) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 399) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 400) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 401) list = __dlist_remove_link( list, ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 402) free( ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 403)
bfc1508d (kx 2023-03-24 03:55:33 +0300 404) break;
bfc1508d (kx 2023-03-24 03:55:33 +0300 405) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 406) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 407)
bfc1508d (kx 2023-03-24 03:55:33 +0300 408) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 409) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 410)
bfc1508d (kx 2023-03-24 03:55:33 +0300 411) struct dlist *dlist_remove_all( struct dlist *list, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 412) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 413) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 414)
bfc1508d (kx 2023-03-24 03:55:33 +0300 415) while( ptr )
bfc1508d (kx 2023-03-24 03:55:33 +0300 416) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 417) if( ptr->data != data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 418) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 419) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 420) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 421) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 422) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 423) struct dlist *next = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 424)
bfc1508d (kx 2023-03-24 03:55:33 +0300 425) if( ptr->prev )
bfc1508d (kx 2023-03-24 03:55:33 +0300 426) ptr->prev->next = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 427) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 428) list = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 429)
bfc1508d (kx 2023-03-24 03:55:33 +0300 430) if( next )
bfc1508d (kx 2023-03-24 03:55:33 +0300 431) next->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 432)
bfc1508d (kx 2023-03-24 03:55:33 +0300 433) free( ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 434)
bfc1508d (kx 2023-03-24 03:55:33 +0300 435) ptr = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 436) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 437) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 438)
bfc1508d (kx 2023-03-24 03:55:33 +0300 439) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 440) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 441)
bfc1508d (kx 2023-03-24 03:55:33 +0300 442) struct dlist *dlist_remove_data( struct dlist *list, DLCMPF cmp_func, DLFUNC free_func, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 443) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 444) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 445)
bfc1508d (kx 2023-03-24 03:55:33 +0300 446) if( !cmp_func ) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 447)
bfc1508d (kx 2023-03-24 03:55:33 +0300 448) while( ptr )
bfc1508d (kx 2023-03-24 03:55:33 +0300 449) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 450) if( cmp_func( ptr->data, data ) != 0 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 451) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 452) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 453) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 454) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 455) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 456) list = __dlist_remove_link( list, ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 457) if( free_func ) free_func( ptr->data, (void *)data ); /* free_func() can compare pointers */
bfc1508d (kx 2023-03-24 03:55:33 +0300 458) free( ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 459)
bfc1508d (kx 2023-03-24 03:55:33 +0300 460) break;
bfc1508d (kx 2023-03-24 03:55:33 +0300 461) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 462) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 463)
bfc1508d (kx 2023-03-24 03:55:33 +0300 464) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 465) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 466)
bfc1508d (kx 2023-03-24 03:55:33 +0300 467) struct dlist *dlist_remove_data_all( struct dlist *list, DLCMPF cmp_func, DLFUNC free_func, const void *data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 468) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 469) struct dlist *ptr = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 470)
bfc1508d (kx 2023-03-24 03:55:33 +0300 471) if( !cmp_func ) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 472)
bfc1508d (kx 2023-03-24 03:55:33 +0300 473) while( ptr )
bfc1508d (kx 2023-03-24 03:55:33 +0300 474) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 475) if( cmp_func( ptr->data, data ) != 0 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 476) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 477) ptr = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 478) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 479) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 480) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 481) struct dlist *next = ptr->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 482)
bfc1508d (kx 2023-03-24 03:55:33 +0300 483) if( ptr->prev )
bfc1508d (kx 2023-03-24 03:55:33 +0300 484) ptr->prev->next = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 485) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 486) list = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 487)
bfc1508d (kx 2023-03-24 03:55:33 +0300 488) if( next )
bfc1508d (kx 2023-03-24 03:55:33 +0300 489) next->prev = ptr->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 490)
bfc1508d (kx 2023-03-24 03:55:33 +0300 491) if( free_func ) free_func( ptr->data, (void *)data ); /* free_func() can compare pointers */
bfc1508d (kx 2023-03-24 03:55:33 +0300 492) free( ptr );
bfc1508d (kx 2023-03-24 03:55:33 +0300 493)
bfc1508d (kx 2023-03-24 03:55:33 +0300 494) ptr = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 495) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 496) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 497)
bfc1508d (kx 2023-03-24 03:55:33 +0300 498) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 499) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 500)
bfc1508d (kx 2023-03-24 03:55:33 +0300 501)
bfc1508d (kx 2023-03-24 03:55:33 +0300 502) struct dlist *dlist_copy( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 503) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 504) struct dlist *copy = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 505)
bfc1508d (kx 2023-03-24 03:55:33 +0300 506) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 507) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 508) copy = dlist_append( copy, list->data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 509) list = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 510) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 511)
bfc1508d (kx 2023-03-24 03:55:33 +0300 512) return copy;
bfc1508d (kx 2023-03-24 03:55:33 +0300 513) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 514)
bfc1508d (kx 2023-03-24 03:55:33 +0300 515) /* It simply switches the next and prev pointers of each element. */
bfc1508d (kx 2023-03-24 03:55:33 +0300 516) struct dlist *dlist_reverse( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 517) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 518) struct dlist *last = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 519)
bfc1508d (kx 2023-03-24 03:55:33 +0300 520) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 521) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 522) last = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 523) list = last->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 524) last->next = last->prev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 525) last->prev = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 526) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 527)
bfc1508d (kx 2023-03-24 03:55:33 +0300 528) return last;
bfc1508d (kx 2023-03-24 03:55:33 +0300 529) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 530)
bfc1508d (kx 2023-03-24 03:55:33 +0300 531)
bfc1508d (kx 2023-03-24 03:55:33 +0300 532) static struct dlist *__dlist_sort_merge( struct dlist *l1, struct dlist *l2, DLCMPF cmp_func )
bfc1508d (kx 2023-03-24 03:55:33 +0300 533) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 534) struct dlist list, *l, *lprev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 535) int cmp;
bfc1508d (kx 2023-03-24 03:55:33 +0300 536)
bfc1508d (kx 2023-03-24 03:55:33 +0300 537) l = &list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 538) lprev = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 539)
bfc1508d (kx 2023-03-24 03:55:33 +0300 540) while( l1 && l2 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 541) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 542) cmp = ((DLCMPF) cmp_func)( l1->data, l2->data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 543)
bfc1508d (kx 2023-03-24 03:55:33 +0300 544) if( cmp <= 0 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 545) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 546) l->next = l1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 547) l1 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 548) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 549) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 550) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 551) l->next = l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 552) l2 = l2->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 553) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 554) l = l->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 555) l->prev = lprev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 556) lprev = l;
bfc1508d (kx 2023-03-24 03:55:33 +0300 557) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 558) l->next = l1 ? l1 : l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 559) l->next->prev = l;
bfc1508d (kx 2023-03-24 03:55:33 +0300 560)
bfc1508d (kx 2023-03-24 03:55:33 +0300 561) return list.next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 562) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 563)
bfc1508d (kx 2023-03-24 03:55:33 +0300 564) static struct dlist *__dlist_sort_merge_with_data( struct dlist *l1, struct dlist *l2, DLCMPDF cmp_func, void *user_data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 565) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 566) struct dlist list, *l, *lprev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 567) int cmp;
bfc1508d (kx 2023-03-24 03:55:33 +0300 568)
bfc1508d (kx 2023-03-24 03:55:33 +0300 569) l = &list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 570) lprev = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 571)
bfc1508d (kx 2023-03-24 03:55:33 +0300 572) while( l1 && l2 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 573) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 574) cmp = ((DLCMPDF) cmp_func)( l1->data, l2->data, user_data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 575)
bfc1508d (kx 2023-03-24 03:55:33 +0300 576) if( cmp <= 0 )
bfc1508d (kx 2023-03-24 03:55:33 +0300 577) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 578) l->next = l1;
bfc1508d (kx 2023-03-24 03:55:33 +0300 579) l1 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 580) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 581) else
bfc1508d (kx 2023-03-24 03:55:33 +0300 582) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 583) l->next = l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 584) l2 = l2->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 585) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 586) l = l->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 587) l->prev = lprev;
bfc1508d (kx 2023-03-24 03:55:33 +0300 588) lprev = l;
bfc1508d (kx 2023-03-24 03:55:33 +0300 589) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 590) l->next = l1 ? l1 : l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 591) l->next->prev = l;
bfc1508d (kx 2023-03-24 03:55:33 +0300 592)
bfc1508d (kx 2023-03-24 03:55:33 +0300 593) return list.next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 594) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 595)
bfc1508d (kx 2023-03-24 03:55:33 +0300 596)
bfc1508d (kx 2023-03-24 03:55:33 +0300 597) static struct dlist *__dlist_sort_real( struct dlist *list, DLCMPF cmp_func )
bfc1508d (kx 2023-03-24 03:55:33 +0300 598) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 599) struct dlist *l1, *l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 600)
bfc1508d (kx 2023-03-24 03:55:33 +0300 601) if( !list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 602) return NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 603) if( !list->next )
bfc1508d (kx 2023-03-24 03:55:33 +0300 604) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 605)
bfc1508d (kx 2023-03-24 03:55:33 +0300 606) l1 = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 607) l2 = list->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 608)
bfc1508d (kx 2023-03-24 03:55:33 +0300 609) while( (l2 = l2->next) != NULL )
bfc1508d (kx 2023-03-24 03:55:33 +0300 610) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 611) if( (l2 = l2->next) == NULL )
bfc1508d (kx 2023-03-24 03:55:33 +0300 612) break;
bfc1508d (kx 2023-03-24 03:55:33 +0300 613) l1 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 614) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 615) l2 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 616) l1->next = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 617)
bfc1508d (kx 2023-03-24 03:55:33 +0300 618) return __dlist_sort_merge( __dlist_sort_real( list, cmp_func ),
bfc1508d (kx 2023-03-24 03:55:33 +0300 619) __dlist_sort_real( l2, cmp_func ),
bfc1508d (kx 2023-03-24 03:55:33 +0300 620) cmp_func );
bfc1508d (kx 2023-03-24 03:55:33 +0300 621) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 622)
bfc1508d (kx 2023-03-24 03:55:33 +0300 623) static struct dlist *__dlist_sort_real_with_data( struct dlist *list, DLCMPDF cmp_func, void *user_data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 624) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 625) struct dlist *l1, *l2;
bfc1508d (kx 2023-03-24 03:55:33 +0300 626)
bfc1508d (kx 2023-03-24 03:55:33 +0300 627) if( !list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 628) return NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 629) if( !list->next )
bfc1508d (kx 2023-03-24 03:55:33 +0300 630) return list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 631)
bfc1508d (kx 2023-03-24 03:55:33 +0300 632) l1 = list;
bfc1508d (kx 2023-03-24 03:55:33 +0300 633) l2 = list->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 634)
bfc1508d (kx 2023-03-24 03:55:33 +0300 635) while( (l2 = l2->next) != NULL )
bfc1508d (kx 2023-03-24 03:55:33 +0300 636) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 637) if( (l2 = l2->next) == NULL )
bfc1508d (kx 2023-03-24 03:55:33 +0300 638) break;
bfc1508d (kx 2023-03-24 03:55:33 +0300 639) l1 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 640) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 641) l2 = l1->next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 642) l1->next = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 643)
bfc1508d (kx 2023-03-24 03:55:33 +0300 644) return __dlist_sort_merge_with_data( __dlist_sort_real_with_data( list, cmp_func, user_data ),
bfc1508d (kx 2023-03-24 03:55:33 +0300 645) __dlist_sort_real_with_data( l2, cmp_func, user_data ),
bfc1508d (kx 2023-03-24 03:55:33 +0300 646) cmp_func,
bfc1508d (kx 2023-03-24 03:55:33 +0300 647) user_data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 648) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 649)
bfc1508d (kx 2023-03-24 03:55:33 +0300 650)
bfc1508d (kx 2023-03-24 03:55:33 +0300 651) struct dlist *dlist_sort( struct dlist *list, DLCMPF cmp_func )
bfc1508d (kx 2023-03-24 03:55:33 +0300 652) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 653) return __dlist_sort_real( list, cmp_func );
bfc1508d (kx 2023-03-24 03:55:33 +0300 654) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 655)
bfc1508d (kx 2023-03-24 03:55:33 +0300 656) struct dlist *dlist_sort_with_data( struct dlist *list, DLCMPDF cmp_func, void *user_data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 657) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 658) return __dlist_sort_real_with_data( list, cmp_func, user_data );
bfc1508d (kx 2023-03-24 03:55:33 +0300 659) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 660)
bfc1508d (kx 2023-03-24 03:55:33 +0300 661)
bfc1508d (kx 2023-03-24 03:55:33 +0300 662) void dlist_foreach( struct dlist *list, DLFUNC func, void *user_data )
bfc1508d (kx 2023-03-24 03:55:33 +0300 663) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 664) struct dlist *next = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 665)
bfc1508d (kx 2023-03-24 03:55:33 +0300 666) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 667) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 668) next = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 669) if( func ) { func( list->data, user_data ); }
bfc1508d (kx 2023-03-24 03:55:33 +0300 670) list = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 671) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 672) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 673)
bfc1508d (kx 2023-03-24 03:55:33 +0300 674)
bfc1508d (kx 2023-03-24 03:55:33 +0300 675) void __dlist_free( struct dlist *list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 676) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 677) struct dlist *next = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 678)
bfc1508d (kx 2023-03-24 03:55:33 +0300 679) while( list )
bfc1508d (kx 2023-03-24 03:55:33 +0300 680) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 681) next = dlist_next( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 682) free( list ); list = NULL;
bfc1508d (kx 2023-03-24 03:55:33 +0300 683) list = next;
bfc1508d (kx 2023-03-24 03:55:33 +0300 684) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 685) }
bfc1508d (kx 2023-03-24 03:55:33 +0300 686)
bfc1508d (kx 2023-03-24 03:55:33 +0300 687) void dlist_free( struct dlist *list, DLFUNC free_func )
bfc1508d (kx 2023-03-24 03:55:33 +0300 688) {
bfc1508d (kx 2023-03-24 03:55:33 +0300 689) dlist_foreach( list, free_func, NULL );
bfc1508d (kx 2023-03-24 03:55:33 +0300 690) __dlist_free( list );
bfc1508d (kx 2023-03-24 03:55:33 +0300 691) }
cSvn-UI for SVN Repositories
cGit-UI – is a web interface for Subversion (SVN) Repositories. cSvn CGI script is writen in C and therefore it's fast enough
6 Commits
0 Branches
2 Tags