src/array_list.c

changeset 889
f549fd9fbd8f
parent 888
6f44b1f1275c
child 890
54565fd74e74
equal deleted inserted replaced
888:6f44b1f1275c 889:f549fd9fbd8f
168 size_t si = 0, di = 0; 168 size_t si = 0, di = 0;
169 char const *src = sorted_data; 169 char const *src = sorted_data;
170 char *dest = *target; 170 char *dest = *target;
171 171
172 // find the first insertion point 172 // find the first insertion point
173 while (di < old_size) { 173 di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
174 if (cmp_func(src, dest) < 0) { 174 dest += di * elem_size;
175 break;
176 }
177 di++;
178 dest += elem_size;
179 }
180 175
181 // move the remaining elements in the array completely to the right 176 // move the remaining elements in the array completely to the right
182 // we will call it the "buffer" for parked elements 177 // we will call it the "buffer" for parked elements
183 size_t buf_size = old_size - di; 178 size_t buf_size = old_size - di;
184 size_t bi = new_size - buf_size; 179 size_t bi = new_size - buf_size;
187 182
188 // while there are both source and buffered elements left, 183 // while there are both source and buffered elements left,
189 // copy them interleaving 184 // copy them interleaving
190 while (si < elem_count && bi < new_size) { 185 while (si < elem_count && bi < new_size) {
191 // determine how many source elements can be inserted 186 // determine how many source elements can be inserted
192 size_t copy_len = 1; 187 size_t copy_len, bytes_copied;
193 si++; 188 copy_len = cx_array_binary_search_sup(
194 char const *next_src = src + elem_size; 189 src,
195 while (si < elem_count) { 190 elem_count - si,
196 if (cmp_func(bptr, next_src) < 0) { 191 elem_size,
197 break; 192 bptr,
198 } 193 cmp_func
199 copy_len++; 194 );
200 si++;
201 next_src += elem_size;
202 }
203 195
204 // copy the source elements 196 // copy the source elements
205 memcpy(dest, src, copy_len * elem_size); 197 bytes_copied = copy_len * elem_size;
206 dest += copy_len * elem_size; 198 memcpy(dest, src, bytes_copied);
207 src = next_src; 199 dest += bytes_copied;
200 src += bytes_copied;
201 si += copy_len;
202
203 // when all source elements are in place, we are done
204 if (si >= elem_count) break;
208 205
209 // determine how many buffered elements need to be restored 206 // determine how many buffered elements need to be restored
210 copy_len = 1; 207 copy_len = cx_array_binary_search_sup(
211 bi++; 208 bptr,
212 char *next_bptr = bptr + elem_size; 209 new_size - bi,
213 while (bi < new_size) { 210 elem_size,
214 if (cmp_func(src, next_bptr) < 0) { 211 src,
215 break; 212 cmp_func
216 } 213 );
217 copy_len++;
218 bi++;
219 next_bptr += elem_size;
220 }
221 214
222 // restore the buffered elements 215 // restore the buffered elements
223 memmove(dest, bptr, copy_len * elem_size); 216 bytes_copied = copy_len * elem_size;
224 dest += copy_len * elem_size; 217 memmove(dest, bptr, bytes_copied);
225 bptr = next_bptr; 218 dest += bytes_copied;
219 bptr += bytes_copied;
220 bi += copy_len;
226 } 221 }
227 222
228 // still source elements left? simply append them 223 // still source elements left? simply append them
229 if (si < elem_count) { 224 if (si < elem_count) {
230 memcpy(dest, src, elem_size * (elem_count - si)); 225 memcpy(dest, src, elem_size * (elem_count - si));

mercurial