ucx: src/iterator.c@d4baf4dd55c3

     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_s *iter = it;

    45     if (iter->remove) {

    46         iter->remove = false;

    47         iter->elem_count--;

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

    49         // at the last element already

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

    51             void *last = ((char *) iter->src_handle.m)

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

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

    54         }

    55     } else {

    56         iter->index++;

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

    58     }

    59 }

    61 static void cx_iter_next_slow(void *it) {

    62     struct cx_iterator_s *iter = it;

    63     if (iter->remove) {

    64         iter->remove = false;

    65         iter->elem_count--;

    67         // number of elements to move

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

    69         if (remaining > 0) {

    70             memmove(

    71                     iter->elem_handle,

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

    73                     remaining * iter->elem_size

    74             );

    75         }

    76     } else {

    77         iter->index++;

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

    79     }

    80 }

    82 CxIterator cxMutIterator(

    83         void *array,

    84         size_t elem_size,

    85         size_t elem_count,

    86         bool remove_keeps_order

    87 ) {

    88     CxIterator iter;

    90     iter.index = 0;

    91     iter.src_handle.m = array;

    92     iter.elem_handle = array;

    93     iter.elem_size = elem_size;

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

    95     iter.valid = cx_iter_valid;

    96     iter.current = cx_iter_current;

    97     iter.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast;

    98     iter.remove = false;

    99     iter.mutating = true;

   101     return iter;

   102 }

   104 CxIterator cxIterator(

   105         void const *array,

   106         size_t elem_size,

   107         size_t elem_count

   108 ) {

   109     CxIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false);

   110     iter.mutating = false;

   111     return iter;

   112 }

Mercurial > hg > ucx / file revision