comparison: src/array_list.c
src/array_list.c
- changeset 854
- fe0d69d72bcd
- parent 853
- d4baf4dd55c3
- child 855
- 35bcb3216c0d
equal
deleted
inserted
replaced
| 853:d4baf4dd55c3 | 854:fe0d69d72bcd |
|---|---|
| 189 static void cx_arl_destructor(struct cx_list_s *list) { | 189 static void cx_arl_destructor(struct cx_list_s *list) { |
| 190 cx_array_list *arl = (cx_array_list *) list; | 190 cx_array_list *arl = (cx_array_list *) list; |
| 191 | 191 |
| 192 char *ptr = arl->data; | 192 char *ptr = arl->data; |
| 193 | 193 |
| 194 if (list->simple_destructor) { | 194 if (list->base.simple_destructor) { |
| 195 for (size_t i = 0; i < list->size; i++) { | 195 for (size_t i = 0; i < list->base.size; i++) { |
| 196 cx_invoke_simple_destructor(list, ptr); | 196 cx_invoke_simple_destructor(list, ptr); |
| 197 ptr += list->item_size; | 197 ptr += list->base.item_size; |
| 198 } | 198 } |
| 199 } | 199 } |
| 200 if (list->advanced_destructor) { | 200 if (list->base.advanced_destructor) { |
| 201 for (size_t i = 0; i < list->size; i++) { | 201 for (size_t i = 0; i < list->base.size; i++) { |
| 202 cx_invoke_advanced_destructor(list, ptr); | 202 cx_invoke_advanced_destructor(list, ptr); |
| 203 ptr += list->item_size; | 203 ptr += list->base.item_size; |
| 204 } | 204 } |
| 205 } | 205 } |
| 206 | 206 |
| 207 cxFree(list->allocator, arl->data); | 207 cxFree(list->base.allocator, arl->data); |
| 208 cxFree(list->allocator, list); | 208 cxFree(list->base.allocator, list); |
| 209 } | 209 } |
| 210 | 210 |
| 211 static size_t cx_arl_insert_array( | 211 static size_t cx_arl_insert_array( |
| 212 struct cx_list_s *list, | 212 struct cx_list_s *list, |
| 213 size_t index, | 213 size_t index, |
| 214 void const *array, | 214 void const *array, |
| 215 size_t n | 215 size_t n |
| 216 ) { | 216 ) { |
| 217 // out of bounds and special case check | 217 // out of bounds and special case check |
| 218 if (index > list->size || n == 0) return 0; | 218 if (index > list->base.size || n == 0) return 0; |
| 219 | 219 |
| 220 // get a correctly typed pointer to the list | 220 // get a correctly typed pointer to the list |
| 221 cx_array_list *arl = (cx_array_list *) list; | 221 cx_array_list *arl = (cx_array_list *) list; |
| 222 | 222 |
| 223 // do we need to move some elements? | 223 // do we need to move some elements? |
| 224 if (index < list->size) { | 224 if (index < list->base.size) { |
| 225 char const *first_to_move = (char const *) arl->data; | 225 char const *first_to_move = (char const *) arl->data; |
| 226 first_to_move += index * list->item_size; | 226 first_to_move += index * list->base.item_size; |
| 227 size_t elems_to_move = list->size - index; | 227 size_t elems_to_move = list->base.size - index; |
| 228 size_t start_of_moved = index + n; | 228 size_t start_of_moved = index + n; |
| 229 | 229 |
| 230 if (CX_ARRAY_SUCCESS != cx_array_copy( | 230 if (CX_ARRAY_SUCCESS != cx_array_copy( |
| 231 &arl->data, | 231 &arl->data, |
| 232 &list->size, | 232 &list->base.size, |
| 233 &arl->capacity, | 233 &arl->capacity, |
| 234 start_of_moved, | 234 start_of_moved, |
| 235 first_to_move, | 235 first_to_move, |
| 236 list->item_size, | 236 list->base.item_size, |
| 237 elems_to_move, | 237 elems_to_move, |
| 238 &arl->reallocator | 238 &arl->reallocator |
| 239 )) { | 239 )) { |
| 240 // if moving existing elems is unsuccessful, abort | 240 // if moving existing elems is unsuccessful, abort |
| 241 return 0; | 241 return 0; |
| 247 // therefore, it is impossible to leave this function with an invalid array | 247 // therefore, it is impossible to leave this function with an invalid array |
| 248 | 248 |
| 249 // place the new elements | 249 // place the new elements |
| 250 if (CX_ARRAY_SUCCESS == cx_array_copy( | 250 if (CX_ARRAY_SUCCESS == cx_array_copy( |
| 251 &arl->data, | 251 &arl->data, |
| 252 &list->size, | 252 &list->base.size, |
| 253 &arl->capacity, | 253 &arl->capacity, |
| 254 index, | 254 index, |
| 255 array, | 255 array, |
| 256 list->item_size, | 256 list->base.item_size, |
| 257 n, | 257 n, |
| 258 &arl->reallocator | 258 &arl->reallocator |
| 259 )) { | 259 )) { |
| 260 return n; | 260 return n; |
| 261 } else { | 261 } else { |
| 276 struct cx_iterator_s *iter, | 276 struct cx_iterator_s *iter, |
| 277 void const *elem, | 277 void const *elem, |
| 278 int prepend | 278 int prepend |
| 279 ) { | 279 ) { |
| 280 struct cx_list_s *list = iter->src_handle.m; | 280 struct cx_list_s *list = iter->src_handle.m; |
| 281 if (iter->index < list->size) { | 281 if (iter->index < list->base.size) { |
| 282 int result = cx_arl_insert_element( | 282 int result = cx_arl_insert_element( |
| 283 list, | 283 list, |
| 284 iter->index + 1 - prepend, | 284 iter->index + 1 - prepend, |
| 285 elem | 285 elem |
| 286 ); | 286 ); |
| 287 if (result == 0 && prepend != 0) { | 287 if (result == 0 && prepend != 0) { |
| 288 iter->index++; | 288 iter->index++; |
| 289 iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; | 289 iter->elem_handle = ((char *) iter->elem_handle) + list->base.item_size; |
| 290 } | 290 } |
| 291 return result; | 291 return result; |
| 292 } else { | 292 } else { |
| 293 int result = cx_arl_insert_element(list, list->size, elem); | 293 int result = cx_arl_insert_element(list, list->base.size, elem); |
| 294 iter->index = list->size; | 294 iter->index = list->base.size; |
| 295 return result; | 295 return result; |
| 296 } | 296 } |
| 297 } | 297 } |
| 298 | 298 |
| 299 static int cx_arl_remove( | 299 static int cx_arl_remove( |
| 301 size_t index | 301 size_t index |
| 302 ) { | 302 ) { |
| 303 cx_array_list *arl = (cx_array_list *) list; | 303 cx_array_list *arl = (cx_array_list *) list; |
| 304 | 304 |
| 305 // out-of-bounds check | 305 // out-of-bounds check |
| 306 if (index >= list->size) { | 306 if (index >= list->base.size) { |
| 307 return 1; | 307 return 1; |
| 308 } | 308 } |
| 309 | 309 |
| 310 // content destruction | 310 // content destruction |
| 311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); | 311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->base.item_size); |
| 312 | 312 |
| 313 // short-circuit removal of last element | 313 // short-circuit removal of last element |
| 314 if (index == list->size - 1) { | 314 if (index == list->base.size - 1) { |
| 315 list->size--; | 315 list->base.size--; |
| 316 return 0; | 316 return 0; |
| 317 } | 317 } |
| 318 | 318 |
| 319 // just move the elements starting at index to the left | 319 // just move the elements starting at index to the left |
| 320 int result = cx_array_copy( | 320 int result = cx_array_copy( |
| 321 &arl->data, | 321 &arl->data, |
| 322 &list->size, | 322 &list->base.size, |
| 323 &arl->capacity, | 323 &arl->capacity, |
| 324 index, | 324 index, |
| 325 ((char *) arl->data) + (index + 1) * list->item_size, | 325 ((char *) arl->data) + (index + 1) * list->base.item_size, |
| 326 list->item_size, | 326 list->base.item_size, |
| 327 list->size - index - 1, | 327 list->base.size - index - 1, |
| 328 &arl->reallocator | 328 &arl->reallocator |
| 329 ); | 329 ); |
| 330 | 330 |
| 331 // cx_array_copy cannot fail, array cannot grow | 331 // cx_array_copy cannot fail, array cannot grow |
| 332 assert(result == 0); | 332 assert(result == 0); |
| 333 | 333 |
| 334 // decrease the size | 334 // decrease the size |
| 335 list->size--; | 335 list->base.size--; |
| 336 | 336 |
| 337 return 0; | 337 return 0; |
| 338 } | 338 } |
| 339 | 339 |
| 340 static void cx_arl_clear(struct cx_list_s *list) { | 340 static void cx_arl_clear(struct cx_list_s *list) { |
| 341 if (list->size == 0) return; | 341 if (list->base.size == 0) return; |
| 342 | 342 |
| 343 cx_array_list *arl = (cx_array_list *) list; | 343 cx_array_list *arl = (cx_array_list *) list; |
| 344 char *ptr = arl->data; | 344 char *ptr = arl->data; |
| 345 | 345 |
| 346 if (list->simple_destructor) { | 346 if (list->base.simple_destructor) { |
| 347 for (size_t i = 0; i < list->size; i++) { | 347 for (size_t i = 0; i < list->base.size; i++) { |
| 348 cx_invoke_simple_destructor(list, ptr); | 348 cx_invoke_simple_destructor(list, ptr); |
| 349 ptr += list->item_size; | 349 ptr += list->base.item_size; |
| 350 } | 350 } |
| 351 } | 351 } |
| 352 if (list->advanced_destructor) { | 352 if (list->base.advanced_destructor) { |
| 353 for (size_t i = 0; i < list->size; i++) { | 353 for (size_t i = 0; i < list->base.size; i++) { |
| 354 cx_invoke_advanced_destructor(list, ptr); | 354 cx_invoke_advanced_destructor(list, ptr); |
| 355 ptr += list->item_size; | 355 ptr += list->base.item_size; |
| 356 } | 356 } |
| 357 } | 357 } |
| 358 | 358 |
| 359 memset(arl->data, 0, list->size * list->item_size); | 359 memset(arl->data, 0, list->base.size * list->base.item_size); |
| 360 list->size = 0; | 360 list->base.size = 0; |
| 361 } | 361 } |
| 362 | 362 |
| 363 static int cx_arl_swap( | 363 static int cx_arl_swap( |
| 364 struct cx_list_s *list, | 364 struct cx_list_s *list, |
| 365 size_t i, | 365 size_t i, |
| 366 size_t j | 366 size_t j |
| 367 ) { | 367 ) { |
| 368 if (i >= list->size || j >= list->size) return 1; | 368 if (i >= list->base.size || j >= list->base.size) return 1; |
| 369 cx_array_list *arl = (cx_array_list *) list; | 369 cx_array_list *arl = (cx_array_list *) list; |
| 370 cx_array_swap(arl->data, list->item_size, i, j); | 370 cx_array_swap(arl->data, list->base.item_size, i, j); |
| 371 return 0; | 371 return 0; |
| 372 } | 372 } |
| 373 | 373 |
| 374 static void *cx_arl_at( | 374 static void *cx_arl_at( |
| 375 struct cx_list_s const *list, | 375 struct cx_list_s const *list, |
| 376 size_t index | 376 size_t index |
| 377 ) { | 377 ) { |
| 378 if (index < list->size) { | 378 if (index < list->base.size) { |
| 379 cx_array_list const *arl = (cx_array_list const *) list; | 379 cx_array_list const *arl = (cx_array_list const *) list; |
| 380 char *space = arl->data; | 380 char *space = arl->data; |
| 381 return space + index * list->item_size; | 381 return space + index * list->base.item_size; |
| 382 } else { | 382 } else { |
| 383 return NULL; | 383 return NULL; |
| 384 } | 384 } |
| 385 } | 385 } |
| 386 | 386 |
| 387 static ssize_t cx_arl_find_remove( | 387 static ssize_t cx_arl_find_remove( |
| 388 struct cx_list_s *list, | 388 struct cx_list_s *list, |
| 389 void const *elem, | 389 void const *elem, |
| 390 bool remove | 390 bool remove |
| 391 ) { | 391 ) { |
| 392 assert(list->cmpfunc != NULL); | 392 assert(list->base.cmpfunc != NULL); |
| 393 assert(list->size < SIZE_MAX / 2); | 393 assert(list->base.size < SIZE_MAX / 2); |
| 394 char *cur = ((cx_array_list const *) list)->data; | 394 char *cur = ((cx_array_list const *) list)->data; |
| 395 | 395 |
| 396 for (ssize_t i = 0; i < (ssize_t) list->size; i++) { | 396 for (ssize_t i = 0; i < (ssize_t) list->base.size; i++) { |
| 397 if (0 == list->cmpfunc(elem, cur)) { | 397 if (0 == list->base.cmpfunc(elem, cur)) { |
| 398 if (remove) { | 398 if (remove) { |
| 399 if (0 == cx_arl_remove(list, i)) { | 399 if (0 == cx_arl_remove(list, i)) { |
| 400 return i; | 400 return i; |
| 401 } else { | 401 } else { |
| 402 return -1; | 402 return -1; |
| 403 } | 403 } |
| 404 } else { | 404 } else { |
| 405 return i; | 405 return i; |
| 406 } | 406 } |
| 407 } | 407 } |
| 408 cur += list->item_size; | 408 cur += list->base.item_size; |
| 409 } | 409 } |
| 410 | 410 |
| 411 return -1; | 411 return -1; |
| 412 } | 412 } |
| 413 | 413 |
| 414 static void cx_arl_sort(struct cx_list_s *list) { | 414 static void cx_arl_sort(struct cx_list_s *list) { |
| 415 assert(list->cmpfunc != NULL); | 415 assert(list->base.cmpfunc != NULL); |
| 416 qsort(((cx_array_list *) list)->data, | 416 qsort(((cx_array_list *) list)->data, |
| 417 list->size, | 417 list->base.size, |
| 418 list->item_size, | 418 list->base.item_size, |
| 419 list->cmpfunc | 419 list->base.cmpfunc |
| 420 ); | 420 ); |
| 421 } | 421 } |
| 422 | 422 |
| 423 static int cx_arl_compare( | 423 static int cx_arl_compare( |
| 424 struct cx_list_s const *list, | 424 struct cx_list_s const *list, |
| 425 struct cx_list_s const *other | 425 struct cx_list_s const *other |
| 426 ) { | 426 ) { |
| 427 assert(list->cmpfunc != NULL); | 427 assert(list->base.cmpfunc != NULL); |
| 428 if (list->size == other->size) { | 428 if (list->base.size == other->base.size) { |
| 429 char const *left = ((cx_array_list const *) list)->data; | 429 char const *left = ((cx_array_list const *) list)->data; |
| 430 char const *right = ((cx_array_list const *) other)->data; | 430 char const *right = ((cx_array_list const *) other)->data; |
| 431 for (size_t i = 0; i < list->size; i++) { | 431 for (size_t i = 0; i < list->base.size; i++) { |
| 432 int d = list->cmpfunc(left, right); | 432 int d = list->base.cmpfunc(left, right); |
| 433 if (d != 0) { | 433 if (d != 0) { |
| 434 return d; | 434 return d; |
| 435 } | 435 } |
| 436 left += list->item_size; | 436 left += list->base.item_size; |
| 437 right += other->item_size; | 437 right += other->base.item_size; |
| 438 } | 438 } |
| 439 return 0; | 439 return 0; |
| 440 } else { | 440 } else { |
| 441 return list->size < other->size ? -1 : 1; | 441 return list->base.size < other->base.size ? -1 : 1; |
| 442 } | 442 } |
| 443 } | 443 } |
| 444 | 444 |
| 445 static void cx_arl_reverse(struct cx_list_s *list) { | 445 static void cx_arl_reverse(struct cx_list_s *list) { |
| 446 if (list->size < 2) return; | 446 if (list->base.size < 2) return; |
| 447 void *data = ((cx_array_list const *) list)->data; | 447 void *data = ((cx_array_list const *) list)->data; |
| 448 size_t half = list->size / 2; | 448 size_t half = list->base.size / 2; |
| 449 for (size_t i = 0; i < half; i++) { | 449 for (size_t i = 0; i < half; i++) { |
| 450 cx_array_swap(data, list->item_size, i, list->size - 1 - i); | 450 cx_array_swap(data, list->base.item_size, i, list->base.size - 1 - i); |
| 451 } | 451 } |
| 452 } | 452 } |
| 453 | 453 |
| 454 static bool cx_arl_iter_valid(void const *it) { | 454 static bool cx_arl_iter_valid(void const *it) { |
| 455 struct cx_iterator_s const *iter = it; | 455 struct cx_iterator_s const *iter = it; |
| 456 struct cx_list_s const *list = iter->src_handle.c; | 456 struct cx_list_s const *list = iter->src_handle.c; |
| 457 return iter->index < list->size; | 457 return iter->index < list->base.size; |
| 458 } | 458 } |
| 459 | 459 |
| 460 static void *cx_arl_iter_current(void const *it) { | 460 static void *cx_arl_iter_current(void const *it) { |
| 461 struct cx_iterator_s const *iter = it; | 461 struct cx_iterator_s const *iter = it; |
| 462 return iter->elem_handle; | 462 return iter->elem_handle; |
| 463 } | 463 } |
| 464 | 464 |
| 465 static void cx_arl_iter_next(void *it) { | 465 static void cx_arl_iter_next(void *it) { |
| 466 struct cx_iterator_s *iter = it; | 466 struct cx_iterator_s *iter = it; |
| 467 if (iter->remove) { | 467 if (iter->base.remove) { |
| 468 iter->remove = false; | 468 iter->base.remove = false; |
| 469 cx_arl_remove(iter->src_handle.m, iter->index); | 469 cx_arl_remove(iter->src_handle.m, iter->index); |
| 470 } else { | 470 } else { |
| 471 iter->index++; | 471 iter->index++; |
| 472 iter->elem_handle = | 472 iter->elem_handle = |
| 473 ((char *) iter->elem_handle) | 473 ((char *) iter->elem_handle) |
| 474 + ((struct cx_list_s const *) iter->src_handle.c)->item_size; | 474 + ((struct cx_list_s const *) iter->src_handle.c)->base.item_size; |
| 475 } | 475 } |
| 476 } | 476 } |
| 477 | 477 |
| 478 static void cx_arl_iter_prev(void *it) { | 478 static void cx_arl_iter_prev(void *it) { |
| 479 struct cx_iterator_s *iter = it; | 479 struct cx_iterator_s *iter = it; |
| 480 cx_array_list const* list = iter->src_handle.c; | 480 cx_array_list const* list = iter->src_handle.c; |
| 481 if (iter->remove) { | 481 if (iter->base.remove) { |
| 482 iter->remove = false; | 482 iter->base.remove = false; |
| 483 cx_arl_remove(iter->src_handle.m, iter->index); | 483 cx_arl_remove(iter->src_handle.m, iter->index); |
| 484 } | 484 } |
| 485 iter->index--; | 485 iter->index--; |
| 486 if (iter->index < list->base.size) { | 486 if (iter->index < list->base.base.size) { |
| 487 iter->elem_handle = ((char *) list->data) | 487 iter->elem_handle = ((char *) list->data) |
| 488 + iter->index * list->base.item_size; | 488 + iter->index * list->base.base.item_size; |
| 489 } | 489 } |
| 490 } | 490 } |
| 491 | 491 |
| 492 | 492 |
| 493 static struct cx_iterator_s cx_arl_iterator( | 493 static struct cx_iterator_s cx_arl_iterator( |
| 498 struct cx_iterator_s iter; | 498 struct cx_iterator_s iter; |
| 499 | 499 |
| 500 iter.index = index; | 500 iter.index = index; |
| 501 iter.src_handle.c = list; | 501 iter.src_handle.c = list; |
| 502 iter.elem_handle = cx_arl_at(list, index); | 502 iter.elem_handle = cx_arl_at(list, index); |
| 503 iter.elem_size = list->item_size; | 503 iter.elem_size = list->base.item_size; |
| 504 iter.elem_count = list->size; | 504 iter.elem_count = list->base.size; |
| 505 iter.valid = cx_arl_iter_valid; | 505 iter.base.valid = cx_arl_iter_valid; |
| 506 iter.current = cx_arl_iter_current; | 506 iter.base.current = cx_arl_iter_current; |
| 507 iter.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; | 507 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; |
| 508 iter.remove = false; | 508 iter.base.remove = false; |
| 509 iter.mutating = false; | 509 iter.base.mutating = false; |
| 510 | 510 |
| 511 return iter; | 511 return iter; |
| 512 } | 512 } |
| 513 | 513 |
| 514 static cx_list_class cx_array_list_class = { | 514 static cx_list_class cx_array_list_class = { |
| 539 | 539 |
| 540 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); | 540 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); |
| 541 if (list == NULL) return NULL; | 541 if (list == NULL) return NULL; |
| 542 | 542 |
| 543 list->base.cl = &cx_array_list_class; | 543 list->base.cl = &cx_array_list_class; |
| 544 list->base.allocator = allocator; | 544 list->base.base.allocator = allocator; |
| 545 list->capacity = initial_capacity; | 545 list->capacity = initial_capacity; |
| 546 | 546 |
| 547 if (item_size > 0) { | 547 if (item_size > 0) { |
| 548 list->base.item_size = item_size; | 548 list->base.base.item_size = item_size; |
| 549 list->base.cmpfunc = comparator; | 549 list->base.base.cmpfunc = comparator; |
| 550 } else { | 550 } else { |
| 551 item_size = sizeof(void *); | 551 item_size = sizeof(void *); |
| 552 list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; | 552 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; |
| 553 cxListStorePointers((CxList *) list); | 553 cxListStorePointers((CxList *) list); |
| 554 } | 554 } |
| 555 | 555 |
| 556 // allocate the array after the real item_size is known | 556 // allocate the array after the real item_size is known |
| 557 list->data = cxCalloc(allocator, initial_capacity, item_size); | 557 list->data = cxCalloc(allocator, initial_capacity, item_size); |
