Efficient list compacting

Posted by Patrik on Stack Overflow See other posts from Stack Overflow or by Patrik
Published on 2012-09-20T15:20:19Z Indexed on 2012/09/21 9:38 UTC
Read the original article Hit count: 274

Suppose you have a list of unsigned ints. Suppose some elements are equal to 0 and you want to push them back. Currently I use this code (list is a pointer to a list of unsigned ints of size n

for (i = 0; i < n; ++i) 
{    
    if (list[i])
        continue;
    int j;
    for (j = i + 1; j < n && !list[j]; ++j);
    int z;
    for (z = j + 1; z < n && list[z]; ++z);
    if (j == n)
        break;
    memmove(&(list[i]), &(list[j]), sizeof(unsigned int) * (z - j)));
    int s = z - j + i;
    for(j = s; j < z; ++j) 
        list[j] = 0;
    i = s - 1;
} 

Can you think of a more efficient way to perform this task?

The snippet is purely theoretical, in the production code, each element of list is a 64 bytes struct

EDIT: I'll post my solution. Many thanks to Jonathan Leffler.

void RemoveDeadParticles(int * list, int * n)
{
    int i, j = *n - 1;
    for (; j >= 0 && list[j] == 0; --j);
    for (i = 0; i < j; ++i)
    {   
        if (list[i])
            continue;
        memcpy(&(list[i]), &(list[j]), sizeof(int));
        list[j] = 0;
        for (; j >= 0 && list[j] == 0; --j);
        if (i == j)
            break;
    }   

    *n = i + 1;
}

© Stack Overflow or respective owner

Related posts about c

    Related posts about list