source: trunk/libtransmission/ptrarray.c @ 4876

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

#667: remote crash exploit in bencode parser

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