source: trunk/libtransmission/ptrarray.c @ 12553

Last change on this file since 12553 was 12553, checked in by jordan, 10 years ago

(trunk libT) fix minor compiler warning when compiling with assertions disabled

  • Property svn:keywords set to Date Rev Author Id
File size: 5.7 KB
Line 
1/*
2 * This file Copyright (C) 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 12553 2011-07-17 14:33:20Z jordan $
11 */
12
13#include <assert.h>
14#include <stdlib.h> /* tr_renew() -> realloc() */
15#include <string.h> /* memmove */
16
17#include "ptrarray.h"
18#include "utils.h"
19
20#define FLOOR 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
60int
61tr_ptrArrayInsert( tr_ptrArray * t,
62                   void        * ptr,
63                   int           pos )
64{
65    if( t->n_items >= t->n_alloc )
66    {
67        t->n_alloc = MAX( FLOOR, t->n_alloc * 2 );
68        t->items = tr_renew( void*, t->items, t->n_alloc );
69    }
70
71    if( pos < 0 || pos > t->n_items )
72        pos = t->n_items;
73    else
74        memmove( t->items + pos + 1,
75                 t->items + pos,
76                 sizeof( void* ) * ( t->n_items - pos ) );
77
78    t->items[pos] = ptr;
79    t->n_items++;
80    return pos;
81}
82
83void*
84tr_ptrArrayPop( tr_ptrArray* t )
85{
86    void * ret = NULL;
87
88    if( t->n_items )
89        ret = t->items[--t->n_items];
90
91    return ret;
92}
93
94void
95tr_ptrArrayErase( tr_ptrArray * t,
96                  int           begin,
97                  int           end )
98{
99    assert( begin >= 0 );
100    if( end < 0 ) end = t->n_items;
101    assert( begin < end );
102    assert( end <= t->n_items );
103
104    memmove( t->items + begin,
105             t->items + end,
106             sizeof( void* ) * ( t->n_items - end ) );
107
108    t->n_items -= ( end - begin );
109}
110
111/**
112***
113**/
114
115#ifndef NDEBUG
116static int
117lowerBound2( const tr_ptrArray * t,
118             const void * ptr,
119             int compare( const void *, const void * ),
120             bool * exact_match )
121{
122    int i;
123    const int len = t->n_items;
124
125    for( i=0; i<len; ++i )
126    {
127        const int c = compare( t->items[i], ptr );
128
129        if( c == 0 ) {
130            *exact_match = true;
131            return i;
132        }
133
134        if( c < 0 )
135            continue;
136
137        *exact_match = false;
138        return i;
139    }
140
141    *exact_match = false;
142    return len;
143}
144#endif
145
146int
147tr_ptrArrayLowerBound( const tr_ptrArray  * t,
148                       const void         * ptr,
149                       int                  compare( const void *, const void * ),
150                       bool               * exact_match )
151{
152    int pos = -1;
153    bool match = false;
154#ifndef NDEBUG
155    bool match_2;
156#endif
157
158    if( t->n_items == 0 )
159    {
160        pos = 0;
161    }
162    else
163    {
164        int first = 0;
165        int last = t->n_items - 1;
166
167        for( ;; )
168        {
169            const int half = (last - first) / 2;
170            const int c = compare( t->items[first + half], ptr );
171
172            if( c < 0 ) {
173                const int new_first = first + half + 1;
174                if( new_first > last ) {
175                    pos = new_first;
176                    break;
177                }
178                first = new_first;
179            }
180            else if( c > 0 ) {
181                const int new_last = first + half - 1;
182                if( new_last < first ) {
183                    pos = first;
184                    break;
185                }
186                last = new_last;
187            }
188            else {
189                match = true;
190                pos = first + half;
191                break;
192            }
193        }
194    }
195
196    assert( pos == lowerBound2( t, ptr, compare, &match_2 ) );
197    assert( match == match_2 );
198
199    if( exact_match )
200        *exact_match = match;
201    return pos;
202}
203
204static void
205assertSortedAndUnique( const tr_ptrArray * t UNUSED,
206                       int compare(const void*, const void*) UNUSED )
207{
208#if 1
209    int i;
210
211    for( i = 0; i < t->n_items - 2; ++i )
212        assert( compare( t->items[i], t->items[i + 1] ) < 0 );
213#endif
214}
215
216int
217tr_ptrArrayInsertSorted( tr_ptrArray * t,
218                         void *        ptr,
219                         int           compare(const void*, const void*) )
220{
221    int pos;
222    int ret;
223
224    assertSortedAndUnique( t, compare );
225
226    pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
227    ret = tr_ptrArrayInsert( t, ptr, pos );
228
229    assertSortedAndUnique( t, compare );
230    return ret;
231}
232
233void*
234tr_ptrArrayFindSorted( tr_ptrArray * t,
235                       const void *  ptr,
236                       int           compare(const void*, const void*) )
237{
238    bool match = false;
239    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
240    return match ? t->items[pos] : NULL;
241}
242
243void*
244tr_ptrArrayRemoveSorted( tr_ptrArray * t,
245                         const void  * ptr,
246                         int           compare(const void*, const void*) )
247{
248    bool match;
249    void * ret = NULL;
250    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
251    assertSortedAndUnique( t, compare );
252
253    if( match )
254    {
255        ret = t->items[pos];
256        assert( compare( ret, ptr ) == 0 );
257        tr_ptrArrayErase( t, pos, pos + 1 );
258    }
259    assertSortedAndUnique( t, compare );
260    assert( ( ret == NULL ) || ( compare( ret, ptr ) == 0 ) );
261    return ret;
262}
Note: See TracBrowser for help on using the repository browser.