comparison: src/array_list.c
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)); |
