source: trunk/libtransmission/ptrarray.c @ 12512

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

(trunk libT) the edge condition bug in ptrarray's bsearch code seems to be fixed, so let's commit the fix with lots of assert()ions enabled so that the nightly build users can show me where I'm wrong :)

  • 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 12512 2011-06-24 18:25:56Z 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,
206                    int compare(const void*, const void*) )
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.