comparison: src/list.c
src/list.c
- changeset 875
- ee84ac776cbc
- parent 856
- 6bbbf219251d
- child 876
- f4ce7df9cff0
equal
deleted
inserted
replaced
| 874:cdce47f34d48 | 875:ee84ac776cbc |
|---|---|
| 215 __attribute__((__unused__)) bool remove | 215 __attribute__((__unused__)) bool remove |
| 216 ) { | 216 ) { |
| 217 return -1; | 217 return -1; |
| 218 } | 218 } |
| 219 | 219 |
| 220 static int cx_emptyl_compare( | |
| 221 __attribute__((__unused__)) struct cx_list_s const *list, | |
| 222 struct cx_list_s const *other | |
| 223 ) { | |
| 224 if (other->collection.size == 0) return 0; | |
| 225 return -1; | |
| 226 } | |
| 227 | |
| 228 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { | 220 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { |
| 229 return false; | 221 return false; |
| 230 } | 222 } |
| 231 | 223 |
| 232 static CxIterator cx_emptyl_iterator( | 224 static CxIterator cx_emptyl_iterator( |
| 250 cx_emptyl_noop, | 242 cx_emptyl_noop, |
| 251 NULL, | 243 NULL, |
| 252 cx_emptyl_at, | 244 cx_emptyl_at, |
| 253 cx_emptyl_find_remove, | 245 cx_emptyl_find_remove, |
| 254 cx_emptyl_noop, | 246 cx_emptyl_noop, |
| 255 cx_emptyl_compare, | 247 NULL, |
| 256 cx_emptyl_noop, | 248 cx_emptyl_noop, |
| 257 cx_emptyl_iterator, | 249 cx_emptyl_iterator, |
| 258 }; | 250 }; |
| 259 | 251 |
| 260 CxList cx_empty_list = { | 252 CxList cx_empty_list = { |
| 274 | 266 |
| 275 CxList *const cxEmptyList = &cx_empty_list; | 267 CxList *const cxEmptyList = &cx_empty_list; |
| 276 | 268 |
| 277 // </editor-fold> | 269 // </editor-fold> |
| 278 | 270 |
| 271 #define invoke_list_func(name, list, ...) \ | |
| 272 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \ | |
| 273 (list, __VA_ARGS__) | |
| 274 | |
| 275 size_t cx_list_default_insert_array( | |
| 276 struct cx_list_s *list, | |
| 277 size_t index, | |
| 278 void const *data, | |
| 279 size_t n | |
| 280 ) { | |
| 281 size_t elem_size = list->collection.elem_size; | |
| 282 char const *src = data; | |
| 283 size_t i = 0; | |
| 284 for (; i < n; i++) { | |
| 285 if (0 != invoke_list_func(insert_element, | |
| 286 list, index + i, src + (i * elem_size))) { | |
| 287 return i; | |
| 288 } | |
| 289 } | |
| 290 return i; | |
| 291 } | |
| 292 | |
| 293 void cx_list_default_sort(struct cx_list_s *list) { | |
| 294 size_t elem_size = list->collection.elem_size; | |
| 295 size_t list_size = list->collection.size; | |
| 296 void *tmp = malloc(elem_size * list_size); | |
| 297 if (tmp == NULL) abort(); | |
| 298 | |
| 299 // copy elements from source array | |
| 300 char *loc = tmp; | |
| 301 for (size_t i = 0; i < list_size; i++) { | |
| 302 void *src = invoke_list_func(at, list, i); | |
| 303 memcpy(loc, src, elem_size); | |
| 304 loc += elem_size; | |
| 305 } | |
| 306 | |
| 307 // qsort | |
| 308 qsort(tmp, list_size, elem_size, | |
| 309 list->collection.cmpfunc); | |
| 310 | |
| 311 // copy elements back | |
| 312 loc = tmp; | |
| 313 for (size_t i = 0; i < list_size; i++) { | |
| 314 void *dest = invoke_list_func(at, list, i); | |
| 315 memcpy(dest, loc, elem_size); | |
| 316 loc += elem_size; | |
| 317 } | |
| 318 | |
| 319 free(tmp); | |
| 320 } | |
| 321 | |
| 322 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) { | |
| 323 if (i == j) return 0; | |
| 324 if (i >= list->collection.size) return 1; | |
| 325 if (j >= list->collection.size) return 1; | |
| 326 | |
| 327 size_t elem_size = list->collection.elem_size; | |
| 328 | |
| 329 void *tmp = malloc(elem_size); | |
| 330 if (tmp == NULL) return 1; | |
| 331 | |
| 332 void *ip = invoke_list_func(at, list, i); | |
| 333 void *jp = invoke_list_func(at, list, j); | |
| 334 | |
| 335 memcpy(tmp, ip, elem_size); | |
| 336 memcpy(ip, jp, elem_size); | |
| 337 memcpy(jp, tmp, elem_size); | |
| 338 | |
| 339 free(tmp); | |
| 340 | |
| 341 return 0; | |
| 342 } | |
| 343 | |
| 279 void cxListDestroy(CxList *list) { | 344 void cxListDestroy(CxList *list) { |
| 280 list->cl->destructor(list); | 345 list->cl->destructor(list); |
| 281 } | 346 } |
| 282 | 347 |
| 283 int cxListCompare( | 348 int cxListCompare( |
| 284 CxList const *list, | 349 CxList const *list, |
| 285 CxList const *other | 350 CxList const *other |
| 286 ) { | 351 ) { |
| 287 if ( | 352 bool cannot_optimize = false; |
| 288 // if one is storing pointers but the other is not | 353 |
| 289 (list->collection.store_pointer ^ other->collection.store_pointer) || | 354 // if one is storing pointers but the other is not |
| 290 | 355 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; |
| 291 // if one class is wrapped but the other is not | 356 |
| 292 ((list->climpl == NULL) ^ (other->climpl == NULL)) || | 357 // if one class is wrapped but the other is not |
| 293 | 358 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); |
| 294 // if the resolved compare functions are not the same | 359 |
| 295 ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != | 360 // if the compare functions do not match or both are NULL |
| 296 (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) | 361 if (!cannot_optimize) { |
| 297 ) { | 362 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ? |
| 363 list->climpl->compare : list->cl->compare); | |
| 364 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ? | |
| 365 other->climpl->compare : other->cl->compare); | |
| 366 cannot_optimize |= list_cmp != other_cmp; | |
| 367 cannot_optimize |= list_cmp == NULL; | |
| 368 } | |
| 369 | |
| 370 if (cannot_optimize) { | |
| 298 // lists are definitely different - cannot use internal compare function | 371 // lists are definitely different - cannot use internal compare function |
| 299 if (list->collection.size == other->collection.size) { | 372 if (list->collection.size == other->collection.size) { |
| 300 CxIterator left = list->cl->iterator(list, 0, false); | 373 CxIterator left = list->cl->iterator(list, 0, false); |
| 301 CxIterator right = other->cl->iterator(other, 0, false); | 374 CxIterator right = other->cl->iterator(other, 0, false); |
| 302 for (size_t i = 0; i < list->collection.size; i++) { | 375 for (size_t i = 0; i < list->collection.size; i++) { |
