source: trunk/libtransmission/ptrarray.c @ 2846

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

$Id$

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