Changeset 13654
- Timestamp:
- Dec 13, 2012, 1:47:40 AM (10 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/libtransmission/ptrarray.c
r13625 r13654 25 25 tr_ptrArrayDestruct (tr_ptrArray * p, PtrArrayForeachFunc func) 26 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)); 27 assert (p != NULL); 28 assert (p->items || !p->n_items); 29 30 if (func) 31 tr_ptrArrayForeach (p, func); 32 33 tr_free (p->items); 36 34 } 37 35 38 36 void 39 tr_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]); 37 tr_ptrArrayForeach (tr_ptrArray * t, PtrArrayForeachFunc func) 38 { 39 int i; 40 41 assert (t); 42 assert (t->items || !t->n_items); 43 assert (func); 44 45 for (i=0; i<t->n_items; ++i) 46 func (t->items[i]); 50 47 } 51 48 52 49 void** 53 tr_ptrArrayPeek (tr_ptrArray * t, 54 int * size) 55 { 56 *size = t->n_items; 57 return t->items; 50 tr_ptrArrayPeek (tr_ptrArray * t, int * size) 51 { 52 *size = t->n_items; 53 return t->items; 58 54 } 59 55 60 56 int 61 tr_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; 57 tr_ptrArrayInsert (tr_ptrArray * t, void * ptr, int pos) 58 { 59 if (t->n_items >= t->n_alloc) 60 { 61 t->n_alloc = MAX (FLOOR, t->n_alloc * 2); 62 t->items = tr_renew (void*, t->items, t->n_alloc); 63 } 64 65 if (pos < 0 || pos > t->n_items) 66 pos = t->n_items; 67 else 68 memmove (t->items+pos+1, t->items+pos, sizeof(void*)*(t->n_items-pos)); 69 70 t->items[pos] = ptr; 71 t->n_items++; 72 return pos; 81 73 } 82 74 … … 84 76 tr_ptrArrayPop (tr_ptrArray* t) 85 77 { 86 87 88 89 90 91 78 void * ret = NULL; 79 80 if (t->n_items) 81 ret = t->items[--t->n_items]; 82 83 return ret; 92 84 } 93 85 94 86 void 95 tr_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); 87 tr_ptrArrayErase (tr_ptrArray * t, int begin, int end) 88 { 89 if (end < 0) 90 end = t->n_items; 91 92 assert (begin >= 0); 93 assert (begin < end); 94 assert (end <= t->n_items); 95 96 memmove (t->items+begin, t->items+end, sizeof(void*)*(t->n_items-end)); 97 98 t->n_items -= (end - begin); 109 99 } 110 100 … … 119 109 bool * exact_match) 120 110 { 121 122 123 124 125 { 126 127 } 128 129 { 130 131 132 133 111 int pos = -1; 112 bool match = false; 113 114 if (t->n_items == 0) 115 { 116 pos = 0; 117 } 118 else 119 { 120 int first = 0; 121 int last = t->n_items - 1; 122 123 for (;;) 134 124 { 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; 125 const int half = (last - first) / 2; 126 const int c = compare (t->items[first + half], ptr); 127 128 if (c < 0) 129 { 130 const int new_first = first + half + 1; 131 if (new_first > last) 132 { 133 pos = new_first; 134 break; 143 135 } 144 136 first = new_first; 145 137 } 146 else if (c > 0) { 147 const int new_last = first + half - 1; 148 if (new_last < first) { 149 pos = first; 150 break; 138 else if (c > 0) 139 { 140 const int new_last = first + half - 1; 141 if (new_last < first) 142 { 143 pos = first; 144 break; 151 145 } 152 146 last = new_last; 153 147 } 154 else { 155 match = true; 156 pos = first + half; 157 break; 148 else 149 { 150 match = true; 151 pos = first + half; 152 break; 158 153 } 159 154 } 160 155 } 161 156 162 if (exact_match) 163 *exact_match = match; 164 return pos; 157 if (exact_match != NULL) 158 *exact_match = match; 159 160 return pos; 165 161 } 166 162 … … 170 166 { 171 167 #ifndef NDEBUG 172 173 174 for (i = 0; i < t->n_items -2; ++i)175 assert (compare (t->items[i], t->items[i +1]) < 0);168 int i; 169 170 for (i=0; i<t->n_items-2; ++i) 171 assert (compare (t->items[i], t->items[i+1]) < 0); 176 172 #endif 177 173 } … … 179 175 int 180 176 tr_ptrArrayInsertSorted (tr_ptrArray * t, 181 void *ptr,177 void * ptr, 182 178 int compare (const void*, const void*)) 183 179 { 184 185 186 187 188 189 190 191 192 193 180 int pos; 181 int ret; 182 183 assertSortedAndUnique (t, compare); 184 185 pos = tr_ptrArrayLowerBound (t, ptr, compare, NULL); 186 ret = tr_ptrArrayInsert (t, ptr, pos); 187 188 assertSortedAndUnique (t, compare); 189 return ret; 194 190 } 195 191 196 192 void* 197 193 tr_ptrArrayFindSorted (tr_ptrArray * t, 198 const void *ptr,194 const void * ptr, 199 195 int compare (const void*, const void*)) 200 196 { 201 202 203 197 bool match = false; 198 const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match); 199 return match ? t->items[pos] : NULL; 204 200 } 205 201 … … 209 205 int compare (const void*, const void*)) 210 206 { 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 } 207 bool match; 208 void * ret = NULL; 209 const int pos = tr_ptrArrayLowerBound (t, ptr, compare, &match); 210 211 assertSortedAndUnique (t, compare); 212 213 if (match) 214 { 215 ret = t->items[pos]; 216 assert (compare (ret, ptr) == 0); 217 tr_ptrArrayErase (t, pos, pos + 1); 218 } 219 220 assertSortedAndUnique (t, compare); 221 assert ((ret == NULL) || (compare (ret, ptr) == 0)); 222 return ret; 223 }
Note: See TracChangeset
for help on using the changeset viewer.