source: trunk/libtransmission/ptrarray.c @ 6953

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

(libT) a small, simple memory optimization

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