Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c

changeset 986
38fa7e41194c
parent 985
68754c7de906
equal deleted inserted replaced
985:68754c7de906 986:38fa7e41194c
86 }; 86 };
87 } 87 }
88 88
89 // LOW LEVEL ARRAY LIST FUNCTIONS 89 // LOW LEVEL ARRAY LIST FUNCTIONS
90 90
91 enum cx_array_result cx_array_copy( 91 int cx_array_copy(
92 void **target, 92 void **target,
93 size_t *size, 93 size_t *size,
94 size_t *capacity, 94 size_t *capacity,
95 size_t index, 95 size_t index,
96 const void *src, 96 const void *src,
99 CxArrayReallocator *reallocator 99 CxArrayReallocator *reallocator
100 ) { 100 ) {
101 // assert pointers 101 // assert pointers
102 assert(target != NULL); 102 assert(target != NULL);
103 assert(size != NULL); 103 assert(size != NULL);
104 assert(capacity != NULL);
104 assert(src != NULL); 105 assert(src != NULL);
106 assert(reallocator != NULL);
105 107
106 // determine capacity 108 // determine capacity
107 size_t cap = capacity == NULL ? *size : *capacity; 109 size_t cap = *capacity;
108 assert(*target != NULL || cap == 0); 110 assert(*target != NULL || cap == 0);
109 111
110 // check if resize is required 112 // check if resize is required
111 size_t minsize = index + elem_count; 113 size_t minsize = index + elem_count;
112 size_t newsize = *size < minsize ? minsize : *size; 114 size_t newsize = *size < minsize ? minsize : *size;
113 bool needrealloc = newsize > cap;
114 115
115 // reallocate if possible 116 // reallocate if possible
116 if (needrealloc) { 117 if (newsize > cap) {
117 // a reallocator and a capacity variable must be available
118 if (reallocator == NULL || capacity == NULL) {
119 return CX_ARRAY_REALLOC_NOT_SUPPORTED;
120 }
121
122 // check, if we need to repair the src pointer 118 // check, if we need to repair the src pointer
123 uintptr_t targetaddr = (uintptr_t) *target; 119 uintptr_t targetaddr = (uintptr_t) *target;
124 uintptr_t srcaddr = (uintptr_t) src; 120 uintptr_t srcaddr = (uintptr_t) src;
125 bool repairsrc = targetaddr <= srcaddr 121 bool repairsrc = targetaddr <= srcaddr
126 && srcaddr < targetaddr + cap * elem_size; 122 && srcaddr < targetaddr + cap * elem_size;
132 // perform reallocation 128 // perform reallocation
133 void *newmem = reallocator->realloc( 129 void *newmem = reallocator->realloc(
134 *target, cap, elem_size, reallocator 130 *target, cap, elem_size, reallocator
135 ); 131 );
136 if (newmem == NULL) { 132 if (newmem == NULL) {
137 return CX_ARRAY_REALLOC_FAILED; 133 return 1;
138 } 134 }
139 135
140 // repair src pointer, if necessary 136 // repair src pointer, if necessary
141 if (repairsrc) { 137 if (repairsrc) {
142 src = ((char *) newmem) + (srcaddr - targetaddr); 138 src = ((char *) newmem) + (srcaddr - targetaddr);
154 // copy elements and set new size 150 // copy elements and set new size
155 memmove(start, src, elem_count * elem_size); 151 memmove(start, src, elem_count * elem_size);
156 *size = newsize; 152 *size = newsize;
157 153
158 // return successfully 154 // return successfully
159 return CX_ARRAY_SUCCESS; 155 return 0;
160 } 156 }
161 157
162 enum cx_array_result cx_array_insert_sorted( 158 int cx_array_insert_sorted(
163 void **target, 159 void **target,
164 size_t *size, 160 size_t *size,
165 size_t *capacity, 161 size_t *capacity,
166 cx_compare_func cmp_func, 162 cx_compare_func cmp_func,
167 const void *sorted_data, 163 const void *sorted_data,
191 *target, new_capacity, elem_size, reallocator 187 *target, new_capacity, elem_size, reallocator
192 ); 188 );
193 if (new_mem == NULL) { 189 if (new_mem == NULL) {
194 // give it up right away, there is no contract 190 // give it up right away, there is no contract
195 // that requires us to insert as much as we can 191 // that requires us to insert as much as we can
196 return CX_ARRAY_REALLOC_FAILED; 192 return 1;
197 } 193 }
198 *target = new_mem; 194 *target = new_mem;
199 *capacity = new_capacity; 195 *capacity = new_capacity;
200 } 196 }
201 197
265 } 261 }
266 262
267 // still buffer elements left? 263 // still buffer elements left?
268 // don't worry, we already moved them to the correct place 264 // don't worry, we already moved them to the correct place
269 265
270 return CX_ARRAY_SUCCESS; 266 return 0;
271 } 267 }
272 268
273 size_t cx_array_binary_search_inf( 269 size_t cx_array_binary_search_inf(
274 const void *arr, 270 const void *arr,
275 size_t size, 271 size_t size,
456 const char *first_to_move = (const char *) arl->data; 452 const char *first_to_move = (const char *) arl->data;
457 first_to_move += index * list->collection.elem_size; 453 first_to_move += index * list->collection.elem_size;
458 size_t elems_to_move = list->collection.size - index; 454 size_t elems_to_move = list->collection.size - index;
459 size_t start_of_moved = index + n; 455 size_t start_of_moved = index + n;
460 456
461 if (CX_ARRAY_SUCCESS != cx_array_copy( 457 if (cx_array_copy(
462 &arl->data, 458 &arl->data,
463 &list->collection.size, 459 &list->collection.size,
464 &arl->capacity, 460 &arl->capacity,
465 start_of_moved, 461 start_of_moved,
466 first_to_move, 462 first_to_move,
476 // note that if we had to move the elements, the following operation 472 // note that if we had to move the elements, the following operation
477 // is guaranteed to succeed, because we have the memory already allocated 473 // is guaranteed to succeed, because we have the memory already allocated
478 // therefore, it is impossible to leave this function with an invalid array 474 // therefore, it is impossible to leave this function with an invalid array
479 475
480 // place the new elements 476 // place the new elements
481 if (CX_ARRAY_SUCCESS == cx_array_copy( 477 if (cx_array_copy(
482 &arl->data, 478 &arl->data,
483 &list->collection.size, 479 &list->collection.size,
484 &arl->capacity, 480 &arl->capacity,
485 index, 481 index,
486 array, 482 array,
487 list->collection.elem_size, 483 list->collection.elem_size,
488 n, 484 n,
489 &arl->reallocator 485 &arl->reallocator
490 )) { 486 )) {
491 return n;
492 } else {
493 // array list implementation is "all or nothing" 487 // array list implementation is "all or nothing"
494 return 0; 488 return 0;
489 } else {
490 return n;
495 } 491 }
496 } 492 }
497 493
498 static size_t cx_arl_insert_sorted( 494 static size_t cx_arl_insert_sorted(
499 struct cx_list_s *list, 495 struct cx_list_s *list,
501 size_t n 497 size_t n
502 ) { 498 ) {
503 // get a correctly typed pointer to the list 499 // get a correctly typed pointer to the list
504 cx_array_list *arl = (cx_array_list *) list; 500 cx_array_list *arl = (cx_array_list *) list;
505 501
506 if (CX_ARRAY_SUCCESS == cx_array_insert_sorted( 502 if (cx_array_insert_sorted(
507 &arl->data, 503 &arl->data,
508 &list->collection.size, 504 &list->collection.size,
509 &arl->capacity, 505 &arl->capacity,
510 list->collection.cmpfunc, 506 list->collection.cmpfunc,
511 sorted_data, 507 sorted_data,
512 list->collection.elem_size, 508 list->collection.elem_size,
513 n, 509 n,
514 &arl->reallocator 510 &arl->reallocator
515 )) { 511 )) {
516 return n;
517 } else {
518 // array list implementation is "all or nothing" 512 // array list implementation is "all or nothing"
519 return 0; 513 return 0;
514 } else {
515 return n;
520 } 516 }
521 } 517 }
522 518
523 static int cx_arl_insert_element( 519 static int cx_arl_insert_element(
524 struct cx_list_s *list, 520 struct cx_list_s *list,

Mercurial Repository: ucx

mercurial