src/array_list.c

changeset 856
6bbbf219251d
parent 855
35bcb3216c0d
child 874
cdce47f34d48
equal deleted inserted replaced
855:35bcb3216c0d 856:6bbbf219251d
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->base.simple_destructor) { 194 if (list->collection.simple_destructor) {
195 for (size_t i = 0; i < list->base.size; i++) { 195 for (size_t i = 0; i < list->collection.size; i++) {
196 cx_invoke_simple_destructor(list, ptr); 196 cx_invoke_simple_destructor(list, ptr);
197 ptr += list->base.elem_size; 197 ptr += list->collection.elem_size;
198 } 198 }
199 } 199 }
200 if (list->base.advanced_destructor) { 200 if (list->collection.advanced_destructor) {
201 for (size_t i = 0; i < list->base.size; i++) { 201 for (size_t i = 0; i < list->collection.size; i++) {
202 cx_invoke_advanced_destructor(list, ptr); 202 cx_invoke_advanced_destructor(list, ptr);
203 ptr += list->base.elem_size; 203 ptr += list->collection.elem_size;
204 } 204 }
205 } 205 }
206 206
207 cxFree(list->base.allocator, arl->data); 207 cxFree(list->collection.allocator, arl->data);
208 cxFree(list->base.allocator, list); 208 cxFree(list->collection.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->base.size || n == 0) return 0; 218 if (index > list->collection.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->base.size) { 224 if (index < list->collection.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->base.elem_size; 226 first_to_move += index * list->collection.elem_size;
227 size_t elems_to_move = list->base.size - index; 227 size_t elems_to_move = list->collection.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->base.size, 232 &list->collection.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->base.elem_size, 236 list->collection.elem_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->base.size, 252 &list->collection.size,
253 &arl->capacity, 253 &arl->capacity,
254 index, 254 index,
255 array, 255 array,
256 list->base.elem_size, 256 list->collection.elem_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->base.size) { 281 if (iter->index < list->collection.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->base.elem_size; 289 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
290 } 290 }
291 return result; 291 return result;
292 } else { 292 } else {
293 int result = cx_arl_insert_element(list, list->base.size, elem); 293 int result = cx_arl_insert_element(list, list->collection.size, elem);
294 iter->index = list->base.size; 294 iter->index = list->collection.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->base.size) { 306 if (index >= list->collection.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->base.elem_size); 311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size);
312 312
313 // short-circuit removal of last element 313 // short-circuit removal of last element
314 if (index == list->base.size - 1) { 314 if (index == list->collection.size - 1) {
315 list->base.size--; 315 list->collection.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->base.size, 322 &list->collection.size,
323 &arl->capacity, 323 &arl->capacity,
324 index, 324 index,
325 ((char *) arl->data) + (index + 1) * list->base.elem_size, 325 ((char *) arl->data) + (index + 1) * list->collection.elem_size,
326 list->base.elem_size, 326 list->collection.elem_size,
327 list->base.size - index - 1, 327 list->collection.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->base.size--; 335 list->collection.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->base.size == 0) return; 341 if (list->collection.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->base.simple_destructor) { 346 if (list->collection.simple_destructor) {
347 for (size_t i = 0; i < list->base.size; i++) { 347 for (size_t i = 0; i < list->collection.size; i++) {
348 cx_invoke_simple_destructor(list, ptr); 348 cx_invoke_simple_destructor(list, ptr);
349 ptr += list->base.elem_size; 349 ptr += list->collection.elem_size;
350 } 350 }
351 } 351 }
352 if (list->base.advanced_destructor) { 352 if (list->collection.advanced_destructor) {
353 for (size_t i = 0; i < list->base.size; i++) { 353 for (size_t i = 0; i < list->collection.size; i++) {
354 cx_invoke_advanced_destructor(list, ptr); 354 cx_invoke_advanced_destructor(list, ptr);
355 ptr += list->base.elem_size; 355 ptr += list->collection.elem_size;
356 } 356 }
357 } 357 }
358 358
359 memset(arl->data, 0, list->base.size * list->base.elem_size); 359 memset(arl->data, 0, list->collection.size * list->collection.elem_size);
360 list->base.size = 0; 360 list->collection.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->base.size || j >= list->base.size) return 1; 368 if (i >= list->collection.size || j >= list->collection.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->base.elem_size, i, j); 370 cx_array_swap(arl->data, list->collection.elem_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->base.size) { 378 if (index < list->collection.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->base.elem_size; 381 return space + index * list->collection.elem_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->base.cmpfunc != NULL); 392 assert(list->collection.cmpfunc != NULL);
393 assert(list->base.size < SIZE_MAX / 2); 393 assert(list->collection.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->base.size; i++) { 396 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
397 if (0 == list->base.cmpfunc(elem, cur)) { 397 if (0 == list->collection.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->base.elem_size; 408 cur += list->collection.elem_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->base.cmpfunc != NULL); 415 assert(list->collection.cmpfunc != NULL);
416 qsort(((cx_array_list *) list)->data, 416 qsort(((cx_array_list *) list)->data,
417 list->base.size, 417 list->collection.size,
418 list->base.elem_size, 418 list->collection.elem_size,
419 list->base.cmpfunc 419 list->collection.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->base.cmpfunc != NULL); 427 assert(list->collection.cmpfunc != NULL);
428 if (list->base.size == other->base.size) { 428 if (list->collection.size == other->collection.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->base.size; i++) { 431 for (size_t i = 0; i < list->collection.size; i++) {
432 int d = list->base.cmpfunc(left, right); 432 int d = list->collection.cmpfunc(left, right);
433 if (d != 0) { 433 if (d != 0) {
434 return d; 434 return d;
435 } 435 }
436 left += list->base.elem_size; 436 left += list->collection.elem_size;
437 right += other->base.elem_size; 437 right += other->collection.elem_size;
438 } 438 }
439 return 0; 439 return 0;
440 } else { 440 } else {
441 return list->base.size < other->base.size ? -1 : 1; 441 return list->collection.size < other->collection.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->base.size < 2) return; 446 if (list->collection.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->base.size / 2; 448 size_t half = list->collection.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->base.elem_size, i, list->base.size - 1 - i); 450 cx_array_swap(data, list->collection.elem_size, i, list->collection.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->base.size; 457 return iter->index < list->collection.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;
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)->base.elem_size; 474 + ((struct cx_list_s const *) iter->src_handle.c)->collection.elem_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;
481 if (iter->base.remove) { 481 if (iter->base.remove) {
482 iter->base.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.base.size) { 486 if (iter->index < list->base.collection.size) {
487 iter->elem_handle = ((char *) list->data) 487 iter->elem_handle = ((char *) list->data)
488 + iter->index * list->base.base.elem_size; 488 + iter->index * list->base.collection.elem_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->base.elem_size; 503 iter.elem_size = list->collection.elem_size;
504 iter.elem_count = list->base.size; 504 iter.elem_count = list->collection.size;
505 iter.base.valid = cx_arl_iter_valid; 505 iter.base.valid = cx_arl_iter_valid;
506 iter.base.current = cx_arl_iter_current; 506 iter.base.current = cx_arl_iter_current;
507 iter.base.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.base.remove = false; 508 iter.base.remove = false;
509 iter.base.mutating = false; 509 iter.base.mutating = false;
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.base.allocator = allocator; 544 list->base.collection.allocator = allocator;
545 list->capacity = initial_capacity; 545 list->capacity = initial_capacity;
546 546
547 if (elem_size > 0) { 547 if (elem_size > 0) {
548 list->base.base.elem_size = elem_size; 548 list->base.collection.elem_size = elem_size;
549 list->base.base.cmpfunc = comparator; 549 list->base.collection.cmpfunc = comparator;
550 } else { 550 } else {
551 elem_size = sizeof(void *); 551 elem_size = sizeof(void *);
552 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; 552 list->base.collection.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 elem_size is known 556 // allocate the array after the real elem_size is known
557 list->data = cxCalloc(allocator, initial_capacity, elem_size); 557 list->data = cxCalloc(allocator, initial_capacity, elem_size);

mercurial