release/src/router/transmission/libtransmission/list.c

   1 /*
   2  * This file Copyright (C) Mnemosyne LLC
   3  *
   4  * This file is licensed by the GPL version 2. Works owned by the
   5  * Transmission project are granted a special exemption to clause 2(b)
   6  * so that the bulk of its code can remain under the MIT license.
   7  * This exemption does not extend to derived works not owned by
   8  * the Transmission project.
   9  *
  10  * $Id: list.c 11709 2011-01-19 13:48:47Z jordan $
  11  */
  12
  13 #include "transmission.h"
  14 #include "list.h"
  15 #include "utils.h"
  16
  17 static tr_list*
  18 node_alloc( void )
  19 {
  20     return tr_new0( tr_list, 1 );
  21 }
  22
  23 static void
  24 node_free( tr_list* node )
  25 {
  26     tr_free( node );
  27 }
  28
  29 /***
  30 ****
  31 ***/
  32
  33 void
  34 tr_list_free( tr_list**         list,
  35               TrListForeachFunc data_free_func )
  36 {
  37     while( *list )
  38     {
  39         tr_list *node = *list;
  40         *list = ( *list )->next;
  41         if( data_free_func )
  42             data_free_func( node->data );
  43         node_free( node );
  44     }
  45 }
  46
  47 void
  48 tr_list_prepend( tr_list ** list,
  49                  void *     data )
  50 {
  51     tr_list * node = node_alloc ( );
  52
  53     node->data = data;
  54     node->next = *list;
  55     if( *list )
  56         ( *list )->prev = node;
  57     *list = node;
  58 }
  59
  60 void
  61 tr_list_append( tr_list ** list,
  62                 void *     data )
  63 {
  64     tr_list * node = node_alloc( );
  65
  66     node->data = data;
  67     if( !*list )
  68         *list = node;
  69     else
  70     {
  71         tr_list * l = *list;
  72         while( l->next )
  73             l = l->next;
  74
  75         l->next = node;
  76         node->prev = l;
  77     }
  78 }
  79
  80 static tr_list*
  81 tr_list_find_data( tr_list *    list,
  82                    const void * data )
  83 {
  84     for( ; list; list = list->next )
  85         if( list->data == data )
  86             return list;
  87
  88     return NULL;
  89 }
  90
  91 static void*
  92 tr_list_remove_node( tr_list ** list,
  93                      tr_list *  node )
  94 {
  95     void *    data;
  96     tr_list * prev = node ? node->prev : NULL;
  97     tr_list * next = node ? node->next : NULL;
  98
  99     if( prev ) prev->next = next;
 100     if( next ) next->prev = prev;
 101     if( *list == node ) *list = next;
 102     data = node ? node->data : NULL;
 103     node_free( node );
 104     return data;
 105 }
 106
 107 void*
 108 tr_list_pop_front( tr_list ** list )
 109 {
 110     void * ret = NULL;
 111
 112     if( *list )
 113     {
 114         ret = ( *list )->data;
 115         tr_list_remove_node( list, *list );
 116     }
 117     return ret;
 118 }
 119
 120 void*
 121 tr_list_remove_data( tr_list **   list,
 122                      const void * data )
 123 {
 124     return tr_list_remove_node( list, tr_list_find_data( *list, data ) );
 125 }
 126
 127 void*
 128 tr_list_remove( tr_list **        list,
 129                 const void *      b,
 130                 TrListCompareFunc compare_func )
 131 {
 132     return tr_list_remove_node( list, tr_list_find( *list, b, compare_func ) );
 133 }
 134
 135 tr_list*
 136 tr_list_find( tr_list *         list,
 137               const void *      b,
 138               TrListCompareFunc func )
 139 {
 140     for( ; list; list = list->next )
 141         if( !func( list->data, b ) )
 142             return list;
 143
 144     return NULL;
 145 }
 146
 147 void
 148 tr_list_insert_sorted( tr_list            ** list,
 149                        void                * data,
 150                        TrListCompareFunc     compare )
 151 {
 152     /* find l, the node that we'll insert this data before */
 153     tr_list * l;
 154
 155     for( l = *list; l != NULL; l = l->next )
 156     {
 157         const int c = (compare)( data, l->data );
 158         if( c <= 0 )
 159             break;
 160     }
 161
 162     if( l == NULL )
 163         tr_list_append( list, data );
 164     else if( l == *list )
 165         tr_list_prepend( list, data );
 166     else {
 167         tr_list * node = node_alloc( );
 168         node->data = data;
 169         node->prev = l->prev;
 170         node->next = l;
 171         node->prev->next = node;
 172         node->next->prev = node;
 173     }
 174 }
 175
 176 int
 177 tr_list_size( const tr_list * list )
 178 {
 179     int size = 0;
 180
 181     while( list )
 182     {
 183         ++size;
 184         list = list->next;
 185     }
 186
 187     return size;
 188 }