Re: filling area by color atack safety

On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
 
[...]
 
Here is the refinement that uses a resizing rather than
fixed-size buffer.
 
 
typedef     unsigned char               Color;
typedef     unsigned int                UI;
typedef     struct { UI x, y; }         Point;
typedef     unsigned int                Index;
 
static  _Bool  change_it( UI w, UI h, Color [w][h], Point, Color,
Color );
 
void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
new ){ static const Point deltas[4] =  {  {1,0}, {0,1}, {-1,0},
{0,-1},  }; UI     k      =  0;
  UI     n      =  17;
  Point *todo   =  malloc( n * sizeof *todo );
 
    if(  todo  &&  change_it( w, h, pixels, p0, old, new )  )
todo[k++] = p0;
 
    while(  k > 0  ){
        Index j = n-k;
        memmove( todo + j, todo, k * sizeof *todo );
        k = 0;
 
        while(  j < n  ){
            Point p = todo[ j++ ];
            for(  Index i = 0;  i < 4;  i++  ){
                Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
                if(  ! change_it( w, h, pixels, q, old, new )  )
continue; todo[ k++ ] = q;
            }
 
            if(  j-k < 3  ){
                Index new_n = n+n/4;
                Index new_j = new_n - (n-j);
                Point *t = realloc( todo, new_n * sizeof *t );
                if(  !t  ){  k = 0;  break;  }
                memmove( t + new_j, t + j, (n-j) * sizeof *t );
                todo = t,  n = new_n,  j = new_j;
            }
        }
    }
 
    free( todo );
}
 
_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
new ){ if(  p.x >= w  ||  p.y >= h  ||  pixels[p.x][p.y] != old  )
return  0; return  pixels[p.x][p.y] = new,  1;
}

This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Is it the same algorithm?

Besides, I don't think that use of VLA in library code is a good idea.
VLA is optional in latest C standards. And incompatible with C++.