1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/iterator.c Thu May 23 15:05:24 2024 +0200 1.3 @@ -0,0 +1,106 @@ 1.4 +/* 1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 + * 1.7 + * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. 1.8 + * 1.9 + * Redistribution and use in source and binary forms, with or without 1.10 + * modification, are permitted provided that the following conditions are met: 1.11 + * 1.12 + * 1. Redistributions of source code must retain the above copyright 1.13 + * notice, this list of conditions and the following disclaimer. 1.14 + * 1.15 + * 2. Redistributions in binary form must reproduce the above copyright 1.16 + * notice, this list of conditions and the following disclaimer in the 1.17 + * documentation and/or other materials provided with the distribution. 1.18 + * 1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 + * POSSIBILITY OF SUCH DAMAGE. 1.30 + */ 1.31 + 1.32 +#include "cx/iterator.h" 1.33 + 1.34 +#include <string.h> 1.35 + 1.36 +static bool cx_iter_valid(void const *it) { 1.37 + struct cx_iterator_s const *iter = it; 1.38 + return iter->index < iter->elem_count; 1.39 +} 1.40 + 1.41 +static void *cx_iter_current(void const *it) { 1.42 + struct cx_iterator_s const *iter = it; 1.43 + return iter->elem_handle; 1.44 +} 1.45 + 1.46 +static void cx_iter_next_fast(void *it) { 1.47 + struct cx_iterator_base_s *itbase = it; 1.48 + if (itbase->remove) { 1.49 + struct cx_mut_iterator_s *iter = it; 1.50 + itbase->remove = false; 1.51 + iter->elem_count--; 1.52 + // only move the last element when we are not currently aiming 1.53 + // at the last element already 1.54 + if (iter->index < iter->elem_count) { 1.55 + void *last = ((char *) iter->src_handle) 1.56 + + iter->elem_count * iter->elem_size; 1.57 + memcpy(iter->elem_handle, last, iter->elem_size); 1.58 + } 1.59 + } else { 1.60 + struct cx_iterator_s *iter = it; 1.61 + iter->index++; 1.62 + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; 1.63 + } 1.64 +} 1.65 + 1.66 +static void cx_iter_next_slow(void *it) { 1.67 + struct cx_iterator_base_s *itbase = it; 1.68 + if (itbase->remove) { 1.69 + struct cx_mut_iterator_s *iter = it; 1.70 + itbase->remove = false; 1.71 + iter->elem_count--; 1.72 + 1.73 + // number of elements to move 1.74 + size_t remaining = iter->elem_count - iter->index; 1.75 + if (remaining > 0) { 1.76 + memmove( 1.77 + iter->elem_handle, 1.78 + ((char *) iter->elem_handle) + iter->elem_size, 1.79 + remaining * iter->elem_size 1.80 + ); 1.81 + } 1.82 + } else { 1.83 + struct cx_iterator_s *iter = it; 1.84 + iter->index++; 1.85 + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; 1.86 + } 1.87 +} 1.88 + 1.89 +CxMutIterator cxIterator( 1.90 + void *array, 1.91 + size_t elem_size, 1.92 + size_t elem_count, 1.93 + bool remove_keeps_order 1.94 +) { 1.95 + CxMutIterator iter; 1.96 + 1.97 + iter.index = 0; 1.98 + iter.src_handle = array; 1.99 + iter.elem_handle = array; 1.100 + iter.elem_size = elem_size; 1.101 + iter.elem_count = array == NULL ? 0 : elem_count; 1.102 + iter.base.valid = cx_iter_valid; 1.103 + iter.base.current = cx_iter_current; 1.104 + iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast; 1.105 + iter.base.remove = false; 1.106 + iter.base.mutating = true; 1.107 + 1.108 + return iter; 1.109 +}