source: trunk/libtransmission/list.c @ 12313

Last change on this file since 12313 was 12313, checked in by jordan, 11 years ago

(trunk libT) keep a pool of reusable tr_list nodes

  • Property svn:keywords set to Date Rev Author Id
File size: 4.0 KB
Line 
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 12313 2011-04-05 00:56:56Z jordan $
11 */
12
13#include "transmission.h"
14#include "list.h"
15#include "utils.h"
16
17static const tr_list TR_LIST_CLEAR = { NULL, NULL, NULL };
18
19static tr_list * recycled_nodes = NULL;
20
21static tr_list*
22node_alloc( void )
23{
24    tr_list * ret;
25
26    if( recycled_nodes == NULL )
27        ret = tr_new( tr_list, 1 );
28    else {
29        ret = recycled_nodes;
30        recycled_nodes = recycled_nodes->next;
31    }
32
33    *ret = TR_LIST_CLEAR;
34    return ret;
35}
36
37static void
38node_free( tr_list* node )
39{
40    *node = TR_LIST_CLEAR;
41    node->next = recycled_nodes;
42    recycled_nodes = node;
43}
44
45/***
46****
47***/
48
49void
50tr_list_free( tr_list**         list,
51              TrListForeachFunc data_free_func )
52{
53    while( *list )
54    {
55        tr_list *node = *list;
56        *list = ( *list )->next;
57        if( data_free_func )
58            data_free_func( node->data );
59        node_free( node );
60    }
61}
62
63void
64tr_list_prepend( tr_list ** list,
65                 void *     data )
66{
67    tr_list * node = node_alloc ( );
68
69    node->data = data;
70    node->next = *list;
71    if( *list )
72        ( *list )->prev = node;
73    *list = node;
74}
75
76void
77tr_list_append( tr_list ** list,
78                void *     data )
79{
80    tr_list * node = node_alloc( );
81
82    node->data = data;
83    if( !*list )
84        *list = node;
85    else
86    {
87        tr_list * l = *list;
88        while( l->next )
89            l = l->next;
90
91        l->next = node;
92        node->prev = l;
93    }
94}
95
96static tr_list*
97tr_list_find_data( tr_list *    list,
98                   const void * data )
99{
100    for( ; list; list = list->next )
101        if( list->data == data )
102            return list;
103
104    return NULL;
105}
106
107static void*
108tr_list_remove_node( tr_list ** list,
109                     tr_list *  node )
110{
111    void *    data;
112    tr_list * prev = node ? node->prev : NULL;
113    tr_list * next = node ? node->next : NULL;
114
115    if( prev ) prev->next = next;
116    if( next ) next->prev = prev;
117    if( *list == node ) *list = next;
118    data = node ? node->data : NULL;
119    node_free( node );
120    return data;
121}
122
123void*
124tr_list_pop_front( tr_list ** list )
125{
126    void * ret = NULL;
127
128    if( *list )
129    {
130        ret = ( *list )->data;
131        tr_list_remove_node( list, *list );
132    }
133    return ret;
134}
135
136void*
137tr_list_remove_data( tr_list **   list,
138                     const void * data )
139{
140    return tr_list_remove_node( list, tr_list_find_data( *list, data ) );
141}
142
143void*
144tr_list_remove( tr_list **        list,
145                const void *      b,
146                TrListCompareFunc compare_func )
147{
148    return tr_list_remove_node( list, tr_list_find( *list, b, compare_func ) );
149}
150
151tr_list*
152tr_list_find( tr_list *         list,
153              const void *      b,
154              TrListCompareFunc func )
155{
156    for( ; list; list = list->next )
157        if( !func( list->data, b ) )
158            return list;
159
160    return NULL;
161}
162
163void
164tr_list_insert_sorted( tr_list            ** list,
165                       void                * data,
166                       TrListCompareFunc     compare )
167{
168    /* find l, the node that we'll insert this data before */
169    tr_list * l;
170
171    for( l = *list; l != NULL; l = l->next )
172    {
173        const int c = (compare)( data, l->data );
174        if( c <= 0 )
175            break;
176    }
177
178    if( l == NULL )
179        tr_list_append( list, data );
180    else if( l == *list )
181        tr_list_prepend( list, data );
182    else {
183        tr_list * node = node_alloc( );
184        node->data = data;
185        node->prev = l->prev;
186        node->next = l;
187        node->prev->next = node;
188        node->next->prev = node;
189    }
190}
191
192int
193tr_list_size( const tr_list * list )
194{
195    int size = 0;
196
197    while( list )
198    {
199        ++size;
200        list = list->next;
201    }
202
203    return size;
204}
Note: See TracBrowser for help on using the repository browser.