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: 339
        
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