source: trunk/libtransmission/ptrarray.c @ 2757

Last change on this file since 2757 was 2757, checked in by charles, 14 years ago

get some pieces of the new tracker code into svn...

File size: 3.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
11#include <assert.h>
12#include <stdlib.h>
13#include <string.h> /* memmove */
14
15#include "ptrarray.h"
16#include "utils.h"
17
18#define GROW 32
19
20struct tr_ptrArray_s
21{
22    void ** items;
23    int n_items;
24    int n_alloc;
25};
26
27tr_ptrArray_t*
28tr_ptrArrayNew( void )
29{
30    tr_ptrArray_t * p;
31
32    p = tr_new( tr_ptrArray_t, 1 );
33    p->n_items = 0;
34    p->n_alloc = GROW;
35    p->items = tr_new( void*, p->n_alloc );
36
37    return p;
38}
39
40void
41tr_ptrArrayFree( tr_ptrArray_t * t )
42{
43    assert( t != NULL );
44    assert( t->items != NULL );
45
46    tr_free( t->items );
47    tr_free( t );
48}
49
50void**
51tr_ptrArrayPeek( tr_ptrArray_t * t, int * size )
52{
53    *size = t->n_items;
54    return t->items;
55}
56
57int
58tr_ptrArraySize( const tr_ptrArray_t * t )
59{
60    return t->n_items;
61}
62
63int
64tr_ptrArrayEmpty( const tr_ptrArray_t * t )
65{
66    return t->n_items == 0;
67}
68
69void
70tr_ptrArrayClear( tr_ptrArray_t * t )
71{
72    t->n_items = 0;
73}
74
75int
76tr_ptrArrayInsert( tr_ptrArray_t * t, void * ptr, int pos )
77{
78    if( pos<0 || pos>t->n_items )
79        pos = t->n_items;
80
81    if( t->n_items >= t->n_alloc ) {
82        t->n_alloc = t->n_items + GROW;
83        t->items = tr_renew( void*, t->items, t->n_alloc );
84    }
85
86    memmove( t->items + pos + 1,
87             t->items + pos,
88             sizeof(void*) * (t->n_items - pos));
89
90    t->items[pos] = ptr;
91    t->n_items++;
92    return pos;
93}
94
95int
96tr_ptrArrayAppend( tr_ptrArray_t * t, void * ptr )
97{
98    return tr_ptrArrayInsert( t, ptr, -1 );
99}
100
101void
102tr_ptrArrayErase( tr_ptrArray_t * t, int begin, int end )
103{
104    assert( begin >= 0 );
105    if( end < 0 ) end = t->n_items;
106    assert( end > begin );
107    assert( end <= t->n_items );
108
109    memmove( t->items + begin,
110             t->items + end,
111             sizeof(void*) * (t->n_items - end) );
112
113    t->n_items -= (end - begin);
114}
115
116/**
117***
118**/
119
120int
121tr_ptrArrayLowerBound( const tr_ptrArray_t * t,
122                       void                * ptr,
123                       int                   compare( const void *,const void * ),
124                       int                 * exact_match )
125{
126    int c = -1;
127    int len = t->n_items;
128    int first = 0;
129
130    while( len > 0 )
131    {
132        int half = len / 2;
133        int middle = first + half;
134        c = compare( t->items[middle], ptr );
135        if( c < 0 ) {
136            first = middle + 1;
137            len = len - half - 1;
138        } else if (!c ) {
139            if( exact_match )
140                *exact_match = 1;
141            return middle;
142            break;
143        } else {
144            len = half;
145        }
146    }
147
148    if( exact_match )
149        *exact_match = 0;
150
151    return first;
152} 
153
154int
155tr_ptrArrayInsertSorted( tr_ptrArray_t  * t,
156                         void           * ptr,
157                         int              compare(const void*,const void*) )
158{
159    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
160    return tr_ptrArrayInsert( t, ptr, pos );
161}
162
163void*
164tr_ptrArrayFindSorted( tr_ptrArray_t  * t,
165                       void           * ptr,
166                       int              compare(const void*,const void*) )
167{
168    int match;
169    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
170    return match ? t->items[pos] : NULL;
171}
172
173void*
174tr_ptrArrayRemoveSorted( tr_ptrArray_t  * t,
175                         void           * ptr,
176                         int              compare(const void*,const void*) )
177{
178    void * ret = NULL;
179    int match;
180    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
181    if( match ) {
182        ret = t->items[pos];
183        tr_ptrArrayErase( t, pos, pos+1 );
184    }
185    return ret;
186}
Note: See TracBrowser for help on using the repository browser.