source: trunk/libtransmission/ptrarray.c @ 7582

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

(trunk libT) inline the ptrarray one-liners

  • Property svn:keywords set to Date Rev Author Id
File size: 5.3 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 7582 2009-01-02 20:19:10Z 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_ptrArrayNth( tr_ptrArray* t,
90                int          i )
91{
92    assert( t );
93    assert( i >= 0 );
94    assert( i < t->n_items );
95
96    return t->items[i];
97}
98
99void*
100tr_ptrArrayBack( tr_ptrArray* t )
101{
102    assert( t->n_items > 0 );
103
104    return tr_ptrArrayNth( t, t->n_items - 1 );
105}
106
107int
108tr_ptrArrayInsert( tr_ptrArray * t,
109                   void *        ptr,
110                   int           pos )
111{
112    if( pos < 0 || pos > t->n_items )
113        pos = t->n_items;
114
115    if( t->n_items >= t->n_alloc )
116    {
117        t->n_alloc = t->n_items + GROW;
118        t->items = tr_renew( void*, t->items, t->n_alloc );
119    }
120
121    memmove( t->items + pos + 1,
122            t->items + pos,
123            sizeof( void* ) * ( t->n_items - pos ) );
124
125    t->items[pos] = ptr;
126    t->n_items++;
127    return pos;
128}
129
130void*
131tr_ptrArrayPop( tr_ptrArray* t )
132{
133    void * ret = NULL;
134
135    if( t->n_items )
136        ret = t->items[--t->n_items];
137
138    return ret;
139}
140
141void
142tr_ptrArrayErase( tr_ptrArray * t,
143                  int           begin,
144                  int           end )
145{
146    assert( begin >= 0 );
147    if( end < 0 ) end = t->n_items;
148    assert( end - begin > 0 );
149    assert( end <= t->n_items );
150
151    memmove( t->items + begin,
152            t->items + end,
153            sizeof( void* ) * ( t->n_items - end ) );
154
155    t->n_items -= ( end - begin );
156}
157
158/**
159***
160**/
161
162static int
163tr_ptrArrayLowerBound( const tr_ptrArray *                t,
164                       const void *                       ptr,
165                       int                 compare( const void *,
166                                                    const void * ),
167                       int *                              exact_match )
168{
169    int len = t->n_items;
170    int first = 0;
171
172    while( len > 0 )
173    {
174        int       half = len / 2;
175        int       middle = first + half;
176        const int c = compare( t->items[middle], ptr );
177        if( c < 0 )
178        {
179            first = middle + 1;
180            len = len - half - 1;
181        }
182        else if( !c )
183        {
184            if( exact_match )
185                *exact_match = 1;
186            return middle;
187            break;
188        }
189        else
190        {
191            len = half;
192        }
193    }
194
195    if( exact_match )
196        *exact_match = 0;
197
198    return first;
199}
200
201static void
202assertSortedAndUnique( const tr_ptrArray * t,
203                        int compare(const void*, const void*) )
204{
205    int i;
206
207    for( i = 0; i < t->n_items - 2; ++i )
208        assert( compare( t->items[i], t->items[i + 1] ) < 0 );
209}
210
211int
212tr_ptrArrayInsertSorted( tr_ptrArray * t,
213                         void *        ptr,
214                          int            compare(const void*, const void*) )
215{
216    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
217    const int ret = tr_ptrArrayInsert( t, ptr, pos );
218
219    assertSortedAndUnique( t, compare );
220    return ret;
221}
222
223void*
224tr_ptrArrayFindSorted( tr_ptrArray * t,
225                       const void *  ptr,
226                        int            compare(const void*, const void*) )
227{
228    int       match;
229    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
230
231    return match ? t->items[pos] : NULL;
232}
233
234void*
235tr_ptrArrayRemoveSorted( tr_ptrArray * t,
236                         void *        ptr,
237                          int            compare(const void*, const void*) )
238{
239    void *    ret = NULL;
240    int       match;
241    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
242
243    if( match )
244    {
245        ret = t->items[pos];
246        tr_ptrArrayErase( t, pos, pos + 1 );
247    }
248    assertSortedAndUnique( t, compare );
249    return ret;
250}
251
Note: See TracBrowser for help on using the repository browser.