source: trunk/libtransmission/ptrarray.c @ 7524

Last change on this file since 7524 was 7524, checked in by charles, 12 years ago

(trunk libT) avoid some unnecessary memory fragmentation... for composited objects that have a tr_ptrArray, contain the tr_ptrArray directly rather than a pointer to one allocated elsewhere on the heap.

  • Property svn:keywords set to Date Rev Author Id
File size: 5.7 KB
Line 
1/*
2 * This file Copyright (C) 2008 Charles Kerr <charles@transmissionbt.com>
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: ptrarray.c 7524 2008-12-29 08:54:36Z charles $
11 */
12
13#include <assert.h>
14#include <stdlib.h>
15#include <string.h> /* memmove */
16
17#include "ptrarray.h"
18#include "utils.h"
19
20#define GROW 32
21
22const tr_ptrArray TR_PTR_ARRAY_INIT = { NULL, 0, 0 };
23
24void
25tr_ptrArrayDestruct( tr_ptrArray * p, PtrArrayForeachFunc func )
26{
27    assert( p );
28    assert( p->items || !p->n_items );
29
30    if( func )
31        tr_ptrArrayForeach( p, func );
32
33    tr_free( p->items );
34
35    memset( p, ~0, sizeof( tr_ptrArray ) );
36}
37
38tr_ptrArray*
39tr_ptrArrayNew( void )
40{
41    tr_ptrArray * p = tr_new( tr_ptrArray, 1 );
42    *p = TR_PTR_ARRAY_INIT;
43    return p;
44}
45
46tr_ptrArray*
47tr_ptrArrayDup( tr_ptrArray* in )
48{
49    tr_ptrArray * out;
50
51    out = tr_new( tr_ptrArray, 1 );
52    out->n_items = out->n_alloc = in->n_items;
53    out->items = tr_memdup( in->items, out->n_items * sizeof( void* ) );
54
55    return out;
56}
57
58void
59tr_ptrArrayForeach( tr_ptrArray *       t,
60                    PtrArrayForeachFunc func )
61{
62    int i;
63
64    assert( t );
65    assert( t->items || !t->n_items );
66    assert( func );
67
68    for( i = 0; i < t->n_items; ++i )
69        func( t->items[i] );
70}
71
72void
73tr_ptrArrayFree( tr_ptrArray *       t,
74                 PtrArrayForeachFunc func )
75{
76    tr_ptrArrayDestruct( t, func );
77    tr_free( t );
78}
79
80void**
81tr_ptrArrayPeek( tr_ptrArray * t,
82                 int *         size )
83{
84    *size = t->n_items;
85    return t->items;
86}
87
88void**
89tr_ptrArrayBase( tr_ptrArray * t )
90{
91    return t->items;
92}
93
94void*
95tr_ptrArrayNth( tr_ptrArray* t,
96                int          i )
97{
98    assert( t );
99    assert( i >= 0 );
100    assert( i < t->n_items );
101
102    return t->items[i];
103}
104
105void*
106tr_ptrArrayBack( tr_ptrArray* t )
107{
108    assert( t->n_items > 0 );
109
110    return tr_ptrArrayNth( t, t->n_items - 1 );
111}
112
113int
114tr_ptrArraySize( const tr_ptrArray * t )
115{
116    return t->n_items;
117}
118
119int
120tr_ptrArrayEmpty( const tr_ptrArray * t )
121{
122    return t->n_items == 0;
123}
124
125void
126tr_ptrArrayClear( tr_ptrArray * t )
127{
128    t->n_items = 0;
129}
130
131int
132tr_ptrArrayInsert( tr_ptrArray * t,
133                   void *        ptr,
134                   int           pos )
135{
136    if( pos < 0 || pos > t->n_items )
137        pos = t->n_items;
138
139    if( t->n_items >= t->n_alloc )
140    {
141        t->n_alloc = t->n_items + GROW;
142        t->items = tr_renew( void*, t->items, t->n_alloc );
143    }
144
145    memmove( t->items + pos + 1,
146            t->items + pos,
147            sizeof( void* ) * ( t->n_items - pos ) );
148
149    t->items[pos] = ptr;
150    t->n_items++;
151    return pos;
152}
153
154int
155tr_ptrArrayAppend( tr_ptrArray * t,
156                   void *        ptr )
157{
158    return tr_ptrArrayInsert( t, ptr, -1 );
159}
160
161void*
162tr_ptrArrayPop( tr_ptrArray* t )
163{
164    void * ret = NULL;
165
166    if( t->n_items )
167        ret = t->items[--t->n_items];
168
169    return ret;
170}
171
172void
173tr_ptrArrayErase( tr_ptrArray * t,
174                  int           begin,
175                  int           end )
176{
177    assert( begin >= 0 );
178    if( end < 0 ) end = t->n_items;
179    assert( end - begin > 0 );
180    assert( end <= t->n_items );
181
182    memmove( t->items + begin,
183            t->items + end,
184            sizeof( void* ) * ( t->n_items - end ) );
185
186    t->n_items -= ( end - begin );
187}
188
189/**
190***
191**/
192
193static int
194tr_ptrArrayLowerBound( const tr_ptrArray *                t,
195                       const void *                       ptr,
196                       int                 compare( const void *,
197                                                    const void * ),
198                       int *                              exact_match )
199{
200    int len = t->n_items;
201    int first = 0;
202
203    while( len > 0 )
204    {
205        int       half = len / 2;
206        int       middle = first + half;
207        const int c = compare( t->items[middle], ptr );
208        if( c < 0 )
209        {
210            first = middle + 1;
211            len = len - half - 1;
212        }
213        else if( !c )
214        {
215            if( exact_match )
216                *exact_match = 1;
217            return middle;
218            break;
219        }
220        else
221        {
222            len = half;
223        }
224    }
225
226    if( exact_match )
227        *exact_match = 0;
228
229    return first;
230}
231
232static void
233assertSortedAndUnique( const tr_ptrArray * t,
234                        int compare(const void*, const void*) )
235{
236    int i;
237
238    for( i = 0; i < t->n_items - 2; ++i )
239        assert( compare( t->items[i], t->items[i + 1] ) < 0 );
240}
241
242int
243tr_ptrArrayInsertSorted( tr_ptrArray * t,
244                         void *        ptr,
245                          int            compare(const void*, const void*) )
246{
247    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
248    const int ret = tr_ptrArrayInsert( t, ptr, pos );
249
250    assertSortedAndUnique( t, compare );
251    return ret;
252}
253
254void*
255tr_ptrArrayFindSorted( tr_ptrArray * t,
256                       const void *  ptr,
257                        int            compare(const void*, const void*) )
258{
259    int       match;
260    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
261
262    return match ? t->items[pos] : NULL;
263}
264
265void*
266tr_ptrArrayRemoveSorted( tr_ptrArray * t,
267                         void *        ptr,
268                          int            compare(const void*, const void*) )
269{
270    void *    ret = NULL;
271    int       match;
272    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
273
274    if( match )
275    {
276        ret = t->items[pos];
277        tr_ptrArrayErase( t, pos, pos + 1 );
278    }
279    assertSortedAndUnique( t, compare );
280    return ret;
281}
282
Note: See TracBrowser for help on using the repository browser.