source: trunk/libtransmission/ptrarray.c @ 3221

Last change on this file since 3221 was 3221, checked in by charles, 13 years ago

add more assertion tests to try to hunt down the tracker.c bug reported by John_Clay

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