source: trunk/libtransmission/ptrarray.c @ 9027

Last change on this file since 9027 was 9027, checked in by charles, 11 years ago

remove unused code

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