source: trunk/libtransmission/ptrarray.c @ 6389

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

(libT) make the licensing consistent across all the files which only contain my code

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