Mercurial > hg > webserver / file comparison

comparison: src/ucx/array_list.c

src/ucx/array_list.c

changeset 490
d218607f5a7e
parent 438
22eca559aded
child 504
c094afcdfb27
equal deleted inserted replaced
489:921f83a8943f 490:d218607f5a7e
27 */ 27 */
28 28
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include <assert.h> 30 #include <assert.h>
31 #include <string.h> 31 #include <string.h>
32 #include <stdint.h>
33 32
34 // LOW LEVEL ARRAY LIST FUNCTIONS 33 // LOW LEVEL ARRAY LIST FUNCTIONS
35 34
36 enum cx_array_copy_result cx_array_copy( 35 enum cx_array_copy_result cx_array_copy(
37 void **target, 36 void **target,
101 100
102 // return successfully 101 // return successfully
103 return CX_ARRAY_COPY_SUCCESS; 102 return CX_ARRAY_COPY_SUCCESS;
104 } 103 }
105 104
105 #ifndef CX_ARRAY_SWAP_SBO_SIZE
106 #define CX_ARRAY_SWAP_SBO_SIZE 512 106 #define CX_ARRAY_SWAP_SBO_SIZE 512
107 #endif
107 108
108 void cx_array_swap( 109 void cx_array_swap(
109 void *arr, 110 void *arr,
110 size_t elem_size, 111 size_t elem_size,
111 size_t idx1, 112 size_t idx1,
112 size_t idx2 113 size_t idx2
113 ) { 114 ) {
115 assert(arr != NULL);
116
114 // short circuit 117 // short circuit
115 if (idx1 == idx2) return; 118 if (idx1 == idx2) return;
116 119
117 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; 120 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
118 void *tmp; 121 void *tmp;
145 // HIGH LEVEL ARRAY LIST FUNCTIONS 148 // HIGH LEVEL ARRAY LIST FUNCTIONS
146 149
147 typedef struct { 150 typedef struct {
148 struct cx_list_s base; 151 struct cx_list_s base;
149 void *data; 152 void *data;
153 size_t capacity;
150 struct cx_array_reallocator_s reallocator; 154 struct cx_array_reallocator_s reallocator;
151 } cx_array_list; 155 } cx_array_list;
152 156
153 static void *cx_arl_realloc( 157 static void *cx_arl_realloc(
154 void *array, 158 void *array,
166 static void cx_arl_destructor(struct cx_list_s *list) { 170 static void cx_arl_destructor(struct cx_list_s *list) {
167 cx_array_list *arl = (cx_array_list *) list; 171 cx_array_list *arl = (cx_array_list *) list;
168 cxFree(list->allocator, arl->data); 172 cxFree(list->allocator, arl->data);
169 } 173 }
170 174
171 static int cx_arl_add( 175 static size_t cx_arl_insert_array(
172 struct cx_list_s *list, 176 struct cx_list_s *list,
173 void const *elem 177 size_t index,
174 ) {
175 cx_array_list *arl = (cx_array_list *) list;
176 return cx_array_copy(
177 &arl->data,
178 &list->size,
179 &list->capacity,
180 list->size,
181 elem,
182 list->itemsize,
183 1,
184 &arl->reallocator
185 );
186 }
187
188 static size_t cx_arl_add_array(
189 struct cx_list_s *list,
190 void const *array, 178 void const *array,
191 size_t n 179 size_t n
192 ) { 180 ) {
181 // out of bounds and special case check
182 if (index > list->size || n == 0) return 0;
183
184 // get a correctly typed pointer to the list
193 cx_array_list *arl = (cx_array_list *) list; 185 cx_array_list *arl = (cx_array_list *) list;
186
187 // do we need to move some elements?
188 if (index < list->size) {
189 char const *first_to_move = (char const *) arl->data;
190 first_to_move += index * list->item_size;
191 size_t elems_to_move = list->size - index;
192 size_t start_of_moved = index + n;
193
194 if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
195 &arl->data,
196 &list->size,
197 &arl->capacity,
198 start_of_moved,
199 first_to_move,
200 list->item_size,
201 elems_to_move,
202 &arl->reallocator
203 )) {
204 // if moving existing elems is unsuccessful, abort
205 return 0;
206 }
207 }
208
209 // note that if we had to move the elements, the following operation
210 // is guaranteed to succeed, because we have the memory already allocated
211 // therefore, it is impossible to leave this function with an invalid array
212
213 // place the new elements
194 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( 214 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
195 &arl->data, 215 &arl->data,
196 &list->size, 216 &list->size,
197 &list->capacity, 217 &arl->capacity,
198 list->size, 218 index,
199 array, 219 array,
200 list->itemsize, 220 list->item_size,
201 n, 221 n,
202 &arl->reallocator 222 &arl->reallocator
203 )) { 223 )) {
204 return n; 224 return n;
205 } else { 225 } else {
206 // array list implementation is "all or nothing" 226 // array list implementation is "all or nothing"
207 return 0; 227 return 0;
208 } 228 }
209 } 229 }
210 230
211 static int cx_arl_insert( 231 static int cx_arl_insert_element(
212 struct cx_list_s *list, 232 struct cx_list_s *list,
213 size_t index, 233 size_t index,
214 void const *elem 234 void const *element
215 ) { 235 ) {
216 if (index > list->size) { 236 return 1 != cx_arl_insert_array(list, index, element, 1);
217 return 1;
218 } else if (index == list->size) {
219 return cx_arl_add(list, elem);
220 } else {
221 cx_array_list *arl = (cx_array_list *) list;
222
223 // move elements starting at index to the right
224 if (cx_array_copy(
225 &arl->data,
226 &list->size,
227 &list->capacity,
228 index + 1,
229 ((char *) arl->data) + index * list->itemsize,
230 list->itemsize,
231 list->size - index,
232 &arl->reallocator
233 )) {
234 return 1;
235 }
236
237 // place the element
238 memcpy(((char *) arl->data) + index * list->itemsize,
239 elem, list->itemsize);
240
241 return 0;
242 }
243 } 237 }
244 238
245 static int cx_arl_insert_iter( 239 static int cx_arl_insert_iter(
246 struct cx_mut_iterator_s *iter, 240 struct cx_mut_iterator_s *iter,
247 void const *elem, 241 void const *elem,
248 int prepend 242 int prepend
249 ) { 243 ) {
250 struct cx_list_s *list = iter->src_handle; 244 struct cx_list_s *list = iter->src_handle;
251 if (iter->index < list->size) { 245 if (iter->index < list->size) {
252 int result = cx_arl_insert( 246 int result = cx_arl_insert_element(
253 list, 247 list,
254 iter->index + 1 - prepend, 248 iter->index + 1 - prepend,
255 elem 249 elem
256 ); 250 );
257 if (result == 0 && prepend != 0) { 251 if (result == 0 && prepend != 0) {
258 iter->index++; 252 iter->index++;
259 iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize; 253 iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;
260 } 254 }
261 return result; 255 return result;
262 } else { 256 } else {
263 int result = cx_arl_add(list, elem); 257 int result = cx_arl_insert_element(list, list->size, elem);
264 iter->index = list->size; 258 iter->index = list->size;
265 return result; 259 return result;
266 } 260 }
267 } 261 }
268 262
269 static int cx_arl_remove( 263 static int cx_arl_remove(
270 struct cx_list_s *list, 264 struct cx_list_s *list,
271 size_t index 265 size_t index
272 ) { 266 ) {
267 cx_array_list *arl = (cx_array_list *) list;
268
273 // out-of-bounds check 269 // out-of-bounds check
274 if (index >= list->size) { 270 if (index >= list->size) {
275 return 1; 271 return 1;
276 } 272 }
273
274 // content destruction
275 cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);
277 276
278 // short-circuit removal of last element 277 // short-circuit removal of last element
279 if (index == list->size - 1) { 278 if (index == list->size - 1) {
280 list->size--; 279 list->size--;
281 return 0; 280 return 0;
282 } 281 }
283 282
284 // just move the elements starting at index to the left 283 // just move the elements starting at index to the left
285 cx_array_list *arl = (cx_array_list *) list;
286 int result = cx_array_copy( 284 int result = cx_array_copy(
287 &arl->data, 285 &arl->data,
288 &list->size, 286 &list->size,
289 &list->capacity, 287 &arl->capacity,
290 index, 288 index,
291 ((char *) arl->data) + (index + 1) * list->itemsize, 289 ((char *) arl->data) + (index + 1) * list->item_size,
292 list->itemsize, 290 list->item_size,
293 list->size - index - 1, 291 list->size - index - 1,
294 &arl->reallocator 292 &arl->reallocator
295 ); 293 );
296 if (result == 0) { 294 if (result == 0) {
297 // decrease the size 295 // decrease the size
298 list->size--; 296 list->size--;
299 } 297 }
300 return result; 298 return result;
301 } 299 }
302 300
301 static void cx_arl_clear(struct cx_list_s *list) {
302 if (list->size == 0) return;
303
304 cx_array_list *arl = (cx_array_list *) list;
305 char *ptr = arl->data;
306
307 if (list->simple_destructor) {
308 for (size_t i = 0; i < list->size; i++) {
309 cx_invoke_simple_destructor(list, ptr);
310 ptr += list->item_size;
311 }
312 }
313 if (list->advanced_destructor) {
314 for (size_t i = 0; i < list->size; i++) {
315 cx_invoke_advanced_destructor(list, ptr);
316 ptr += list->item_size;
317 }
318 }
319
320 memset(arl->data, 0, list->size * list->item_size);
321 list->size = 0;
322 }
323
324 static int cx_arl_swap(
325 struct cx_list_s *list,
326 size_t i,
327 size_t j
328 ) {
329 if (i >= list->size || j >= list->size) return 1;
330 cx_array_list *arl = (cx_array_list *) list;
331 cx_array_swap(arl->data, list->item_size, i, j);
332 return 0;
333 }
334
303 static void *cx_arl_at( 335 static void *cx_arl_at(
304 struct cx_list_s const *list, 336 struct cx_list_s const *list,
305 size_t index 337 size_t index
306 ) { 338 ) {
307 if (index < list->size) { 339 if (index < list->size) {
308 cx_array_list const *arl = (cx_array_list const *) list; 340 cx_array_list const *arl = (cx_array_list const *) list;
309 char *space = arl->data; 341 char *space = arl->data;
310 return space + index * list->itemsize; 342 return space + index * list->item_size;
311 } else { 343 } else {
312 return NULL; 344 return NULL;
313 } 345 }
314 } 346 }
315 347
316 static size_t cx_arl_find( 348 static ssize_t cx_arl_find(
317 struct cx_list_s const *list, 349 struct cx_list_s const *list,
318 void const *elem 350 void const *elem
319 ) { 351 ) {
352 assert(list->cmpfunc != NULL);
353 assert(list->size < SIZE_MAX / 2);
320 char *cur = ((cx_array_list const *) list)->data; 354 char *cur = ((cx_array_list const *) list)->data;
321 355
322 for (size_t i = 0; i < list->size; i++) { 356 for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
323 if (0 == list->cmpfunc(elem, cur)) { 357 if (0 == list->cmpfunc(elem, cur)) {
324 return i; 358 return i;
325 } 359 }
326 cur += list->itemsize; 360 cur += list->item_size;
327 } 361 }
328 362
329 return list->size; 363 return -1;
330 } 364 }
331 365
332 static void cx_arl_sort(struct cx_list_s *list) { 366 static void cx_arl_sort(struct cx_list_s *list) {
367 assert(list->cmpfunc != NULL);
333 qsort(((cx_array_list *) list)->data, 368 qsort(((cx_array_list *) list)->data,
334 list->size, 369 list->size,
335 list->itemsize, 370 list->item_size,
336 list->cmpfunc 371 list->cmpfunc
337 ); 372 );
338 } 373 }
339 374
340 static int cx_arl_compare( 375 static int cx_arl_compare(
341 struct cx_list_s const *list, 376 struct cx_list_s const *list,
342 struct cx_list_s const *other 377 struct cx_list_s const *other
343 ) { 378 ) {
379 assert(list->cmpfunc != NULL);
344 if (list->size == other->size) { 380 if (list->size == other->size) {
345 char const *left = ((cx_array_list const *) list)->data; 381 char const *left = ((cx_array_list const *) list)->data;
346 char const *right = ((cx_array_list const *) other)->data; 382 char const *right = ((cx_array_list const *) other)->data;
347 for (size_t i = 0; i < list->size; i++) { 383 for (size_t i = 0; i < list->size; i++) {
348 int d = list->cmpfunc(left, right); 384 int d = list->cmpfunc(left, right);
349 if (d != 0) { 385 if (d != 0) {
350 return d; 386 return d;
351 } 387 }
352 left += list->itemsize; 388 left += list->item_size;
353 right += other->itemsize; 389 right += other->item_size;
354 } 390 }
355 return 0; 391 return 0;
356 } else { 392 } else {
357 return list->size < other->size ? -1 : 1; 393 return list->size < other->size ? -1 : 1;
358 } 394 }
361 static void cx_arl_reverse(struct cx_list_s *list) { 397 static void cx_arl_reverse(struct cx_list_s *list) {
362 if (list->size < 2) return; 398 if (list->size < 2) return;
363 void *data = ((cx_array_list const *) list)->data; 399 void *data = ((cx_array_list const *) list)->data;
364 size_t half = list->size / 2; 400 size_t half = list->size / 2;
365 for (size_t i = 0; i < half; i++) { 401 for (size_t i = 0; i < half; i++) {
366 cx_array_swap(data, list->itemsize, i, list->size - 1 - i); 402 cx_array_swap(data, list->item_size, i, list->size - 1 - i);
367 } 403 }
368 } 404 }
369 405
370 static bool cx_arl_iter_valid(void const *it) { 406 static bool cx_arl_iter_valid(void const *it) {
371 struct cx_iterator_s const *iter = it; 407 struct cx_iterator_s const *iter = it;
387 } else { 423 } else {
388 struct cx_iterator_s *iter = it; 424 struct cx_iterator_s *iter = it;
389 iter->index++; 425 iter->index++;
390 iter->elem_handle = 426 iter->elem_handle =
391 ((char *) iter->elem_handle) 427 ((char *) iter->elem_handle)
392 + ((struct cx_list_s const *) iter->src_handle)->itemsize; 428 + ((struct cx_list_s const *) iter->src_handle)->item_size;
429 }
430 }
431
432 static void cx_arl_iter_prev(void *it) {
433 struct cx_iterator_base_s *itbase = it;
434 struct cx_mut_iterator_s *iter = it;
435 cx_array_list *const list = iter->src_handle;
436 if (itbase->remove) {
437 itbase->remove = false;
438 cx_arl_remove(iter->src_handle, iter->index);
439 }
440 iter->index--;
441 if (iter->index < list->base.size) {
442 iter->elem_handle = ((char *) list->data)
443 + iter->index * list->base.item_size;
393 } 444 }
394 } 445 }
395 446
396 static bool cx_arl_iter_flag_rm(void *it) { 447 static bool cx_arl_iter_flag_rm(void *it) {
397 struct cx_iterator_base_s *iter = it; 448 struct cx_iterator_base_s *iter = it;
403 } 454 }
404 } 455 }
405 456
406 static struct cx_iterator_s cx_arl_iterator( 457 static struct cx_iterator_s cx_arl_iterator(
407 struct cx_list_s const *list, 458 struct cx_list_s const *list,
408 size_t index 459 size_t index,
460 bool backwards
409 ) { 461 ) {
410 struct cx_iterator_s iter; 462 struct cx_iterator_s iter;
411 463
412 iter.index = index; 464 iter.index = index;
413 iter.src_handle = list; 465 iter.src_handle = list;
414 iter.elem_handle = cx_arl_at(list, index); 466 iter.elem_handle = cx_arl_at(list, index);
415 iter.base.valid = cx_arl_iter_valid; 467 iter.base.valid = cx_arl_iter_valid;
416 iter.base.current = cx_arl_iter_current; 468 iter.base.current = cx_arl_iter_current;
417 iter.base.next = cx_arl_iter_next; 469 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
418 iter.base.flag_removal = cx_arl_iter_flag_rm; 470 iter.base.flag_removal = cx_arl_iter_flag_rm;
419 iter.base.remove = false; 471 iter.base.remove = false;
420 iter.base.mutating = false; 472 iter.base.mutating = false;
421 473
422 return iter; 474 return iter;
423 } 475 }
424 476
425 static struct cx_mut_iterator_s cx_arl_mut_iterator(
426 struct cx_list_s *list,
427 size_t index
428 ) {
429 CxIterator it = cx_arl_iterator(list, index);
430 it.base.mutating = true;
431
432 // we know the iterators share the same memory layout
433 CxMutIterator iter;
434 memcpy(&iter, &it, sizeof(CxMutIterator));
435 return iter;
436 }
437
438 static cx_list_class cx_array_list_class = { 477 static cx_list_class cx_array_list_class = {
439 cx_arl_destructor, 478 cx_arl_destructor,
440 cx_arl_add, 479 cx_arl_insert_element,
441 cx_arl_add_array, 480 cx_arl_insert_array,
442 cx_arl_insert,
443 cx_arl_insert_iter, 481 cx_arl_insert_iter,
444 cx_arl_remove, 482 cx_arl_remove,
483 cx_arl_clear,
484 cx_arl_swap,
445 cx_arl_at, 485 cx_arl_at,
446 cx_arl_find, 486 cx_arl_find,
447 cx_arl_sort, 487 cx_arl_sort,
448 cx_arl_compare, 488 cx_arl_compare,
449 cx_arl_reverse, 489 cx_arl_reverse,
450 cx_arl_iterator, 490 cx_arl_iterator,
451 cx_arl_mut_iterator,
452 }; 491 };
453 492
454 CxList *cxArrayListCreate( 493 CxList *cxArrayListCreate(
455 CxAllocator const *allocator, 494 CxAllocator const *allocator,
456 CxListComparator comparator, 495 cx_compare_func comparator,
457 size_t item_size, 496 size_t item_size,
458 size_t initial_capacity 497 size_t initial_capacity
459 ) { 498 ) {
499 if (allocator == NULL) {
500 allocator = cxDefaultAllocator;
501 }
502
460 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 503 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
461 if (list == NULL) return NULL; 504 if (list == NULL) return NULL;
462 505
506 list->base.cl = &cx_array_list_class;
507 list->base.allocator = allocator;
508 list->base.cmpfunc = comparator;
509 list->capacity = initial_capacity;
510
511 if (item_size > 0) {
512 list->base.item_size = item_size;
513 } else {
514 item_size = sizeof(void *);
515 cxListStorePointers((CxList *) list);
516 }
517
518 // allocate the array after the real item_size is known
463 list->data = cxCalloc(allocator, initial_capacity, item_size); 519 list->data = cxCalloc(allocator, initial_capacity, item_size);
464 if (list->data == NULL) { 520 if (list->data == NULL) {
465 cxFree(allocator, list); 521 cxFree(allocator, list);
466 return NULL; 522 return NULL;
467 } 523 }
468 524
469 list->base.cl = &cx_array_list_class;
470 list->base.allocator = allocator;
471 list->base.cmpfunc = comparator;
472 list->base.itemsize = item_size;
473 list->base.capacity = initial_capacity;
474
475 // configure the reallocator 525 // configure the reallocator
476 list->reallocator.realloc = cx_arl_realloc; 526 list->reallocator.realloc = cx_arl_realloc;
477 list->reallocator.ptr1 = (void *) allocator; 527 list->reallocator.ptr1 = (void *) allocator;
478 528
479 return (CxList *) list; 529 return (CxList *) list;

Mercurial Repository: webserver

mercurial