source: trunk/libtransmission/ptrarray.c @ 3773

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

on Darwin, use NSCParameterAssert() instead of assert().

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