source: trunk/libtransmission/ptrarray.c @ 6490

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

lots of C correctness tweaks suggested by sparse/cgcc

  • Property svn:keywords set to Date Rev Author Id
File size: 5.1 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 6490 2008-08-11 19:05:02Z 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 );
60    assert( t->items );
61    assert( func );
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 );
71    assert( t->items );
72
73    if( func )
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 );
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
185static int
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.