source: trunk/libtransmission/ptrarray.c @ 3105

Last change on this file since 3105 was 3105, checked in by livings124, 13 years ago

merge encryption branch to trunk (xcode project is still out of date)

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