source: trunk/libtransmission/ptrarray.c @ 7627

Last change on this file since 7627 was 7627, checked in by jhujhiti, 12 years ago

(trunk libT) Fix an assertion failure in ptrarrays when values are equal.

This bug manifest itself due to a subtle change in tr_compareAddresses(), but
was always there. An assertion would fail if two (obviously adjacent) values
were equal.

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