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