Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Tue, 19 Mar 2024 13:18:42 +0200
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <20240319131842.00002138@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: dont-email.me; posting-host="a8871862f6b018cf47b195a984142ca8";
	logging-data="789293"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1//jQWe8yEbDKd5gM6/zIZZdjXN4sz5XhE="
Cancel-Lock: sha1:uSx1NxoYAKkuC23ZxBRfllhfdBY=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 3224

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++.