source: trunk/libtransmission/ptrarray.c @ 3775

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

undoing the r3773-r3774 experiment.

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