source: trunk/libtransmission/ptrarray.c @ 3242

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

experimental better peer management.

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