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