Changeset 6795 for trunk/libtransmission/ptrarray.c
- Timestamp:
- Sep 23, 2008, 7:11:04 PM (12 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/libtransmission/ptrarray.c
r6699 r6795 4 4 * This file is licensed by the GPL version 2. Works owned by the 5 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. 6 * so that the bulk of its code can remain under the MIT license. 7 7 * This exemption does not extend to derived works not owned by 8 8 * the Transmission project. … … 23 23 { 24 24 void ** items; 25 int n_items;26 int n_alloc;25 int n_items; 26 int n_alloc; 27 27 }; 28 28 … … 47 47 out = tr_new( tr_ptrArray, 1 ); 48 48 out->n_items = out->n_alloc = in->n_items; 49 out->items = tr_memdup( in->items, out->n_items * sizeof( void*) );49 out->items = tr_memdup( in->items, out->n_items * sizeof( void* ) ); 50 50 51 51 return out; … … 53 53 54 54 void 55 tr_ptrArrayForeach( tr_ptrArray * t, PtrArrayForeachFunc func ) 55 tr_ptrArrayForeach( tr_ptrArray * t, 56 PtrArrayForeachFunc func ) 56 57 { 57 58 int i; … … 61 62 assert( func ); 62 63 63 for( i =0; i<t->n_items; ++i )64 for( i = 0; i < t->n_items; ++i ) 64 65 func( t->items[i] ); 65 66 } 66 67 67 68 void 68 tr_ptrArrayFree( tr_ptrArray * t, PtrArrayForeachFunc func ) 69 tr_ptrArrayFree( tr_ptrArray * t, 70 PtrArrayForeachFunc func ) 69 71 { 70 72 assert( t ); … … 79 81 80 82 void** 81 tr_ptrArrayPeek( tr_ptrArray * t, int * size ) 83 tr_ptrArrayPeek( tr_ptrArray * t, 84 int * size ) 82 85 { 83 86 *size = t->n_items; … … 92 95 93 96 void* 94 tr_ptrArrayNth( tr_ptrArray* t, int i ) 97 tr_ptrArrayNth( tr_ptrArray* t, 98 int i ) 95 99 { 96 100 assert( t ); … … 106 110 assert( t->n_items > 0 ); 107 111 108 return tr_ptrArrayNth( t, t->n_items -1 );112 return tr_ptrArrayNth( t, t->n_items - 1 ); 109 113 } 110 114 … … 128 132 129 133 int 130 tr_ptrArrayInsert( tr_ptrArray * t, void * ptr, int pos ) 131 { 132 if( pos<0 || pos>t->n_items ) 134 tr_ptrArrayInsert( tr_ptrArray * t, 135 void * ptr, 136 int pos ) 137 { 138 if( pos < 0 || pos > t->n_items ) 133 139 pos = t->n_items; 134 140 135 if( t->n_items >= t->n_alloc ) { 141 if( t->n_items >= t->n_alloc ) 142 { 136 143 t->n_alloc = t->n_items + GROW; 137 144 t->items = tr_renew( void*, t->items, t->n_alloc ); … … 139 146 140 147 memmove( t->items + pos + 1, 141 142 sizeof(void*) * (t->n_items - pos));148 t->items + pos, 149 sizeof( void* ) * ( t->n_items - pos ) ); 143 150 144 151 t->items[pos] = ptr; … … 148 155 149 156 int 150 tr_ptrArrayAppend( tr_ptrArray * t, void * ptr ) 157 tr_ptrArrayAppend( tr_ptrArray * t, 158 void * ptr ) 151 159 { 152 160 return tr_ptrArrayInsert( t, ptr, -1 ); … … 160 168 if( t->n_items ) 161 169 ret = t->items[--t->n_items]; 162 170 163 171 return ret; 164 172 } 165 173 166 174 void 167 tr_ptrArrayErase( tr_ptrArray * t, int begin, int end ) 175 tr_ptrArrayErase( tr_ptrArray * t, 176 int begin, 177 int end ) 168 178 { 169 179 assert( begin >= 0 ); … … 173 183 174 184 memmove( t->items + begin, 175 176 sizeof(void*) * (t->n_items - end) );177 178 t->n_items -= ( end - begin);185 t->items + end, 186 sizeof( void* ) * ( t->n_items - end ) ); 187 188 t->n_items -= ( end - begin ); 179 189 } 180 190 … … 184 194 185 195 static int 186 tr_ptrArrayLowerBound( const tr_ptrArray * t, 187 const void * ptr, 188 int compare( const void *,const void * ), 189 int * exact_match ) 196 tr_ptrArrayLowerBound( const tr_ptrArray * t, 197 const void * ptr, 198 int compare( const void *, 199 const void * ), 200 int * exact_match ) 190 201 { 191 202 int len = t->n_items; … … 194 205 while( len > 0 ) 195 206 { 196 int half = len / 2;197 int middle = first + half;207 int half = len / 2; 208 int middle = first + half; 198 209 const int c = compare( t->items[middle], ptr ); 199 if( c < 0 ) { 210 if( c < 0 ) 211 { 200 212 first = middle + 1; 201 213 len = len - half - 1; 202 } else if (!c ) { 214 } 215 else if( !c ) 216 { 203 217 if( exact_match ) 204 218 *exact_match = 1; 205 219 return middle; 206 220 break; 207 } else { 221 } 222 else 223 { 208 224 len = half; 209 225 } … … 218 234 static void 219 235 assertSortedAndUnique( const tr_ptrArray * t, 220 int compare(const void*, const void*) )236 int compare(const void*, const void*) ) 221 237 { 222 238 int i; 223 for( i=0; i<t->n_items-2; ++i ) 224 assert( compare( t->items[i], t->items[i+1] ) < 0 ); 225 } 226 227 int 228 tr_ptrArrayInsertSorted( tr_ptrArray * t, 229 void * ptr, 230 int compare(const void*,const void*) ) 239 240 for( i = 0; i < t->n_items - 2; ++i ) 241 assert( compare( t->items[i], t->items[i + 1] ) < 0 ); 242 } 243 244 int 245 tr_ptrArrayInsertSorted( tr_ptrArray * t, 246 void * ptr, 247 int compare(const void*, const void*) ) 231 248 { 232 249 const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL ); 233 250 const int ret = tr_ptrArrayInsert( t, ptr, pos ); 251 234 252 assertSortedAndUnique( t, compare ); 235 253 return ret; … … 237 255 238 256 void* 239 tr_ptrArrayFindSorted( tr_ptrArray 240 const void *ptr,241 int compare(const void*,const void*) )242 { 243 int match;257 tr_ptrArrayFindSorted( tr_ptrArray * t, 258 const void * ptr, 259 int compare(const void*, const void*) ) 260 { 261 int match; 244 262 const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match ); 263 245 264 return match ? t->items[pos] : NULL; 246 265 } 247 266 248 267 void* 249 tr_ptrArrayRemoveSorted( tr_ptrArray 250 void *ptr,251 int compare(const void*,const void*) )252 { 253 void * ret = NULL;254 int match;268 tr_ptrArrayRemoveSorted( tr_ptrArray * t, 269 void * ptr, 270 int compare(const void*, const void*) ) 271 { 272 void * ret = NULL; 273 int match; 255 274 const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match ); 256 if( match ) { 275 276 if( match ) 277 { 257 278 ret = t->items[pos]; 258 tr_ptrArrayErase( t, pos, pos +1 );279 tr_ptrArrayErase( t, pos, pos + 1 ); 259 280 } 260 281 assertSortedAndUnique( t, compare ); 261 282 return ret; 262 283 } 284
Note: See TracChangeset
for help on using the changeset viewer.