source: trunk/libtransmission/ptrarray.c @ 9836

Last change on this file since 9836 was 9836, checked in by charles, 11 years ago

(trunk libT) fix various minor compiler warnings that show up when you build libtransmission with NDEBUG defined

  • Property svn:keywords set to Date Rev Author Id
File size: 4.8 KB
Line 
1/*
2 * This file Copyright (C) 2008-2009 Mnemosyne LLC
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 9836 2009-12-28 23:27:17Z 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
38void
39tr_ptrArrayForeach( tr_ptrArray *       t,
40                    PtrArrayForeachFunc func )
41{
42    int i;
43
44    assert( t );
45    assert( t->items || !t->n_items );
46    assert( func );
47
48    for( i = 0; i < t->n_items; ++i )
49        func( t->items[i] );
50}
51
52void**
53tr_ptrArrayPeek( tr_ptrArray * t,
54                 int *         size )
55{
56    *size = t->n_items;
57    return t->items;
58}
59
60void*
61tr_ptrArrayNth( tr_ptrArray* t,
62                int          i )
63{
64    assert( t );
65    assert( i >= 0 );
66    assert( i < t->n_items );
67
68    return t->items[i];
69}
70
71void*
72tr_ptrArrayBack( tr_ptrArray* t )
73{
74    assert( t->n_items > 0 );
75
76    return tr_ptrArrayNth( t, t->n_items - 1 );
77}
78
79int
80tr_ptrArrayInsert( tr_ptrArray * t,
81                   void        * ptr,
82                   int           pos )
83{
84    if( pos < 0 || pos > t->n_items )
85        pos = t->n_items;
86
87    if( t->n_items >= t->n_alloc )
88    {
89        t->n_alloc = t->n_items + GROW;
90        t->items = tr_renew( void*, t->items, t->n_alloc );
91    }
92
93    memmove( t->items + pos + 1,
94             t->items + pos,
95             sizeof( void* ) * ( t->n_items - pos ) );
96
97    t->items[pos] = ptr;
98    t->n_items++;
99    return pos;
100}
101
102void*
103tr_ptrArrayPop( tr_ptrArray* t )
104{
105    void * ret = NULL;
106
107    if( t->n_items )
108        ret = t->items[--t->n_items];
109
110    return ret;
111}
112
113static void
114tr_ptrArrayErase( tr_ptrArray * t,
115                  int           begin,
116                  int           end )
117{
118    assert( begin >= 0 );
119    if( end < 0 ) end = t->n_items;
120    assert( end - begin > 0 );
121    assert( end <= t->n_items );
122
123    memmove( t->items + begin,
124            t->items + end,
125            sizeof( void* ) * ( t->n_items - end ) );
126
127    t->n_items -= ( end - begin );
128}
129
130/**
131***
132**/
133
134static int
135tr_ptrArrayLowerBound( const tr_ptrArray *                t,
136                       const void *                       ptr,
137                       int                 compare( const void *,
138                                                    const void * ),
139                       int *                              exact_match )
140{
141    int len = t->n_items;
142    int first = 0;
143
144    while( len > 0 )
145    {
146        int       half = len / 2;
147        int       middle = first + half;
148        const int c = compare( t->items[middle], ptr );
149        if( c < 0 )
150        {
151            first = middle + 1;
152            len = len - half - 1;
153        }
154        else if( !c )
155        {
156            if( exact_match )
157                *exact_match = 1;
158            return middle;
159            break;
160        }
161        else
162        {
163            len = half;
164        }
165    }
166
167    if( exact_match )
168        *exact_match = 0;
169
170    return first;
171}
172
173#ifdef NDEBUG
174#define assertSortedAndUnique(a,b)
175#else
176static void
177assertSortedAndUnique( const tr_ptrArray * t,
178                        int compare(const void*, const void*) )
179{
180    int i;
181
182    for( i = 0; i < t->n_items - 2; ++i )
183        assert( compare( t->items[i], t->items[i + 1] ) <= 0 );
184}
185#endif
186
187int
188tr_ptrArrayInsertSorted( tr_ptrArray * t,
189                         void *        ptr,
190                          int            compare(const void*, const void*) )
191{
192    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
193    const int ret = tr_ptrArrayInsert( t, ptr, pos );
194
195    assertSortedAndUnique( t, compare );
196    return ret;
197}
198
199void*
200tr_ptrArrayFindSorted( tr_ptrArray * t,
201                       const void *  ptr,
202                        int            compare(const void*, const void*) )
203{
204    int       match;
205    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
206
207    return match ? t->items[pos] : NULL;
208}
209
210void*
211tr_ptrArrayRemoveSorted( tr_ptrArray * t,
212                         void *        ptr,
213                          int            compare(const void*, const void*) )
214{
215    void *    ret = NULL;
216    int       match;
217    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
218
219    if( match )
220    {
221        ret = t->items[pos];
222        tr_ptrArrayErase( t, pos, pos + 1 );
223    }
224    assertSortedAndUnique( t, compare );
225    return ret;
226}
227
Note: See TracBrowser for help on using the repository browser.