ucx: src/iterator.c@adb4e0737c33

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/iterator.h"

    31 #include <string.h>

    33 static bool cx_iter_valid(void const *it) {

    34     struct cx_iterator_s const *iter = it;

    35     return iter->index < iter->elem_count;

    36 }

    38 static void *cx_iter_current(void const *it) {

    39     struct cx_iterator_s const *iter = it;

    40     return iter->elem_handle;

    41 }

    43 static void cx_iter_next_fast(void *it) {

    44     struct cx_iterator_base_s *itbase = it;

    45     if (itbase->remove) {

    46         struct cx_mut_iterator_s *iter = it;

    47         itbase->remove = false;

    48         iter->elem_count--;

    49         // only move the last element when we are not currently aiming

    50         // at the last element already

    51         if (iter->index < iter->elem_count) {

    52             void *last = ((char *) iter->src_handle)

    53                          + iter->elem_count * iter->elem_size;

    54             memcpy(iter->elem_handle, last, iter->elem_size);

    55         }

    56     } else {

    57         struct cx_iterator_s *iter = it;

    58         iter->index++;

    59         iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size;

    60     }

    61 }

    63 static void cx_iter_next_slow(void *it) {

    64     struct cx_iterator_base_s *itbase = it;

    65     if (itbase->remove) {

    66         struct cx_mut_iterator_s *iter = it;

    67         itbase->remove = false;

    68         iter->elem_count--;

    70         // number of elements to move

    71         size_t remaining = iter->elem_count - iter->index;

    72         if (remaining > 0) {

    73             memmove(

    74                     iter->elem_handle,

    75                     ((char *) iter->elem_handle) + iter->elem_size,

    76                     remaining * iter->elem_size

    77             );

    78         }

    79     } else {

    80         struct cx_iterator_s *iter = it;

    81         iter->index++;

    82         iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size;

    83     }

    84 }

    86 CxMutIterator cxMutIterator(

    87         void *array,

    88         size_t elem_size,

    89         size_t elem_count,

    90         bool remove_keeps_order

    91 ) {

    92     CxMutIterator iter;

    94     iter.index = 0;

    95     iter.src_handle = array;

    96     iter.elem_handle = array;

    97     iter.elem_size = elem_size;

    98     iter.elem_count = array == NULL ? 0 : elem_count;

    99     iter.base.valid = cx_iter_valid;

   100     iter.base.current = cx_iter_current;

   101     iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast;

   102     iter.base.remove = false;

   103     iter.base.mutating = true;

   105     return iter;

   106 }

   108 CxIterator cxIterator(

   109         void const *array,

   110         size_t elem_size,

   111         size_t elem_count

   112 ) {

   113     CxMutIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false);

   114     iter.base.mutating = false;

   116     // we know the iterators share the same memory layout

   117     CxIterator ret;

   118     memcpy(&ret, &iter, sizeof(CxIterator));

   119     return ret;

   120 }

Mercurial > hg > ucx / file revision