source: trunk/libtransmission/ptrarray.c @ 6073

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

#800 initial support for GetRight?-style fetching of data through http and ftp servers specified in the .torrent's "url-list" tag

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