source: trunk/libtransmission/ptrarray.c @ 11398

Last change on this file since 11398 was 11398, checked in by charles, 10 years ago

(trunk libT) add some new bugs to the code so that it will crash when vraa tries to use it

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