source: trunk/libtransmission/ptrarray.c @ 9059

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

(trunk libT) make tr_ptrArrayErase() private

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