source: trunk/libtransmission/ptrarray.c @ 5389

Last change on this file since 5389 was 5389, checked in by charles, 13 years ago

change ptrarray.[ch] license to MIT so that bencode, which relies on it, can be used in other projects w/o GPL

  • Property svn:keywords set to Date Rev Author Id
File size: 6.1 KB
Line 
1/******************************************************************************
2 * $Id: ptrarray.c 5389 2008-03-25 19:49:32Z charles $
3 *
4 * This file Copyright (C) 2007-2008 Charles Kerr <charles@rebelbase.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
23 *****************************************************************************/
24
25#include <assert.h>
26#include <stdlib.h>
27#include <string.h> /* memmove */
28
29#include "ptrarray.h"
30#include "utils.h"
31
32#define GROW 32
33
34struct tr_ptrArray
35{
36    void ** items;
37    int n_items;
38    int n_alloc;
39};
40
41tr_ptrArray*
42tr_ptrArrayNew( void )
43{
44    tr_ptrArray * p;
45
46    p = tr_new( tr_ptrArray, 1 );
47    p->n_items = 0;
48    p->n_alloc = GROW;
49    p->items = tr_new( void*, p->n_alloc );
50
51    return p;
52}
53
54tr_ptrArray*
55tr_ptrArrayDup( tr_ptrArray* in )
56{
57    tr_ptrArray * out;
58
59    out = tr_new( tr_ptrArray, 1 );
60    out->n_items = in->n_items;
61    out->n_alloc = in->n_items;
62    out->items = tr_new( void*, out->n_alloc );
63    memcpy( out->items, in->items, out->n_items * sizeof(void*) );
64
65    return out;
66}
67
68void
69tr_ptrArrayForeach( tr_ptrArray * t, PtrArrayForeachFunc func )
70{
71    int i;
72
73    assert( t != NULL );
74    assert( t->items != NULL );
75    assert( func != NULL );
76
77    for( i=0; i<t->n_items; ++i )
78        func( t->items[i] );
79}
80
81void
82tr_ptrArrayFree( tr_ptrArray * t, PtrArrayForeachFunc func )
83{
84    assert( t != NULL );
85    assert( t->items != NULL );
86
87    if( func != NULL )
88        tr_ptrArrayForeach( t, func );
89
90    tr_free( t->items );
91    tr_free( t );
92}
93
94void**
95tr_ptrArrayPeek( tr_ptrArray * t, int * size )
96{
97    *size = t->n_items;
98    return t->items;
99}
100
101void*
102tr_ptrArrayNth( tr_ptrArray* t, int i )
103{
104    assert( t != NULL  );
105    assert( i >= 0 );
106    assert( i < t->n_items );
107
108    return t->items[i];
109}
110
111void*
112tr_ptrArrayBack( tr_ptrArray* t )
113{
114    assert( t->n_items > 0 );
115
116    return tr_ptrArrayNth( t, t->n_items-1 );
117}
118
119int
120tr_ptrArraySize( const tr_ptrArray * t )
121{
122    return t->n_items;
123}
124
125int
126tr_ptrArrayEmpty( const tr_ptrArray * t )
127{
128    return t->n_items == 0;
129}
130
131void
132tr_ptrArrayClear( tr_ptrArray * t )
133{
134    t->n_items = 0;
135}
136
137int
138tr_ptrArrayInsert( tr_ptrArray * t, void * ptr, int pos )
139{
140    if( pos<0 || pos>t->n_items )
141        pos = t->n_items;
142
143    if( t->n_items >= t->n_alloc ) {
144        t->n_alloc = t->n_items + GROW;
145        t->items = tr_renew( void*, t->items, t->n_alloc );
146    }
147
148    memmove( t->items + pos + 1,
149             t->items + pos,
150             sizeof(void*) * (t->n_items - pos));
151
152    t->items[pos] = ptr;
153    t->n_items++;
154    return pos;
155}
156
157int
158tr_ptrArrayAppend( tr_ptrArray * t, 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, int begin, int end )
176{
177    assert( begin >= 0 );
178    if( end < 0 ) end = t->n_items;
179    assert( end > begin );
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
193int
194tr_ptrArrayLowerBound( const tr_ptrArray * t,
195                       const void        * ptr,
196                       int                 compare( const void *,const void * ),
197                       int               * exact_match )
198{
199    int len = t->n_items;
200    int first = 0;
201
202    while( len > 0 )
203    {
204        int half = len / 2;
205        int middle = first + half;
206        const int c = compare( t->items[middle], ptr );
207        if( c < 0 ) {
208            first = middle + 1;
209            len = len - half - 1;
210        } else if (!c ) {
211            if( exact_match )
212                *exact_match = 1;
213            return middle;
214            break;
215        } else {
216            len = half;
217        }
218    }
219
220    if( exact_match )
221        *exact_match = 0;
222
223    return first;
224}
225
226static void
227assertSortedAndUnique( const tr_ptrArray * t,
228                       int compare(const void*, const void*) )
229{
230    int i;
231    for( i=0; i<t->n_items-2; ++i )
232        assert( compare( t->items[i], t->items[i+1] ) < 0 );
233}
234
235int
236tr_ptrArrayInsertSorted( tr_ptrArray  * t,
237                         void         * ptr,
238                         int            compare(const void*,const void*) )
239{
240    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
241    const int ret = tr_ptrArrayInsert( t, ptr, pos );
242    assertSortedAndUnique( t, compare );
243    return ret;
244}
245
246void*
247tr_ptrArrayFindSorted( tr_ptrArray  * t,
248                       const void   * ptr,
249                       int            compare(const void*,const void*) )
250{
251    int match;
252    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
253    return match ? t->items[pos] : NULL;
254}
255
256void*
257tr_ptrArrayRemoveSorted( tr_ptrArray  * t,
258                         void         * ptr,
259                         int            compare(const void*,const void*) )
260{
261    void * ret = NULL;
262    int match;
263    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
264    if( match ) {
265        ret = t->items[pos];
266        tr_ptrArrayErase( t, pos, pos+1 );
267    }
268    assertSortedAndUnique( t, compare );
269    return ret;
270}
Note: See TracBrowser for help on using the repository browser.